卡迈克尔数的 Rabin-Miller 检验

Question

我是一名计算机专业的学生，正在自学算法课程。

在课程中我看到了这个问题：

Show an efficient randomized algorithm to factor Carmichael numbers (that is, we want a polynomial time algorithm, that given any Carmichael number C, with probability at least 3/4 finds a nontrivial factor of C). Hint: use the Rabin-Miller test.

我的解决方案：

我的想法是使用Rabin-Miller测试：我将检查 C 是否为素数我将使用 Rabin-Miller 素数测试步骤：

Find n-1=c^k*m

choose a: 1 < a < n-1

compute b_0 = a^m(mod n), b_i = b_(i-1)^2 (mod n)

if b_0 = -/+1 this is prime, i will return nothing. if b_i = -1 this is prime, will return nothing. else if = 1 this is not prime i will return the factor of 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 ?'

我不确定如何 return c 的因子，例如我运行 Rabin-Miller Primality tests for 561, first carmichael number:

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)

Answer 1

如果 Miller–Rabin 在 Carmichael 数 n 上失败，那么作为副产品你会得到一些 x ≢ ±1 mod n 使得 x² ≡ 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.

另一方面，x² ≡ 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(a b, c) = gcd(a, c) 对于所有 b 使得 gcd(b, c) = 1).同样，gcd(x − 1, n) ≠ 1.

卡迈克尔数的 Rabin-Miller 检验

Rabin-Miller test to Carmichael numbers

algorithm