我是一名計算機科學專業的學生，??我正在獨立學習演算法課程。
在課程中，我看到了這個問題：
展示一個有效的隨機演算法來分解卡邁克爾數（也就是說，我們想要一個多項式時間演算法，給定任何卡邁克爾數 C，至少有 3/4 的概率找到 C 的非平凡因數）。提示：使用 Rabin-Miller 測驗。
我的解決方案：
我的想法是使用 Rabin-Miller 測驗：我將檢查 C 是否為素數我將使用 Rabin-Miller Primality 測驗步驟：
- 求 n-1=c^k*m
- 選擇一個：1 < a < n-1
- 計算 b_0 = a^m(mod n), b_i = b_(i-1)^2 (mod n)
- 如果 b_0 = -/ 1 這是素數，我將不回傳任何內容。如果 b_i = -1 這是素數，將不回傳任何內容。否則如果 = 1 這不是素數，我將回傳 C 的因子。
演算法：
function MillerRabinPrimality(n)
Input: integer n, Carmichael number
Output: return with probability 3/4 nontrivial factor of n
Find integers k,q > 0, q odd, so that (n-1)=2^(k)
Select a random integer a, 1<a<n-1
if a^q mod n = /-1
return 'this prime'
for j = 0 to k-1 do
a = a^2 mod q
if (a = -1)
return 'this prime'
if (a = 1)
return 'this is composite, factor is ?'
我不知道如何回傳 c 的因子，例如我對 561 運行 Rabin-Miller Primality 測驗，第一個 carmichael 數：
n = 561
n-1 = 2(^k)*m => 560
560/2^1 = 280 => 560/2^2 = 140 => 560/2^3 = 70 => **560/2^4 = 35**
k = 4
m = 35
choose a: 1<a<560
a = 2
b_0 = 2^35 mod 561 = 263
b_1 = 263^2 mod 561 = 166
b_2 = 166^2 mod 561 = 67
b_3 = 17^2 mod 561 = 1 --> composite
i found that 561 is composite but not sure how to return his factors (3 / 11 / 17)
uj5u.com熱心網友回復：
如果 Miller-Rabin 在 Carmichael 數 n 上失敗，那么作為副產品，您會得到一些 x ? ±1 mod n，使得 x2 ≡ 1 mod n。gcd(x 1, n) 和 gcd(x ? 1, n) 都是 n 的真因數。
證明：x ? 1 mod n 等價于 x ? 1 ? 0 mod n，等價于 x ? 1 不能被 n 整除。因此 gcd(x ? 1, n) ≠ n。同樣，x ? -1 mod n 意味著 gcd(x 1, n) ≠ n。
另一方面，x2 ≡ 1 mod n 等價于 (x 1) (x - 1) 可被 n 整除，因此 gcd((x 1) (x - 1), n) = n。我們不能有 gcd(x 1, n) = 1，否則 gcd(x ? 1, n) = n (因為 gcd(ab, c) = gcd(a, c) 對于所有 b 使得 gcd(b, c) = 1)。同樣，gcd(x ? 1, n) ≠ 1。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446434.html
標籤：算法