I am a computer science student, I am studying the Algorithms course independently.

During the course I saw this 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.

my solution:

my idea is use Rabin-Miller test: i will check if C is prime i will use Rabin-Miller Primality tests steps:

1. Find n-1=c^k*m
2. choose a: 1 < a < n-1
3. compute b_0 = a^m(mod n), b_i = b_(i-1)^2 (mod n)
4. 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.

algorithm:

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 ?'     

i dont sure how to return the factor of c, for example i run 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)

CodePudding user response：

If Miller–Rabin fails on a Carmichael number n, then as a byproduct you get some x ≢ ±1 mod n such that x² ≡ 1 mod n. Both gcd(x 1, n) and gcd(x − 1, n) are proper divisors of n.

The proof: x ≢ 1 mod n is equivalent to x − 1 ≢ 0 mod n, which is equivalent to x − 1 not being divisible by n. Therefore gcd(x − 1, n) ≠ n. Likewise, x ≢ −1 mod n implies that gcd(x 1, n) ≠ n.

On the other hand, x² ≡ 1 mod n is equivalent to (x 1) (x − 1) being divisible by n, hence gcd((x 1) (x − 1), n) = n. We cannot have gcd(x 1, n) = 1, or else gcd(x − 1, n) = n (since gcd(a b, c) = gcd(a, c) for all b such that gcd(b, c) = 1). Likewise, gcd(x − 1, n) ≠ 1.