# Carmichael number factoring

Unsure whether this is the right forum for this question, worth a try.

The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many resources on the web states that this is easy, however, without further explanation why that is?

Furthermore, since miller-rabbin exits when a nontrivial square root of 1 is found, this can be used to find a factor to the carmichael number: $x^2 \equiv 1 = (x+1)(x-1)\equiv0\ mod\ N$, where N is the carmichael number we want to factor. Hence factors must be found using $\gcd(x+1,N)$ and $\gcd(x-1, N)$, correct?

Due to problems with strong liars, in some cases we will miss out on factors, is this a major problem? Since miller-rabbin tests only passes composites with a probability 1/4 is it correct to say that the chances of finding a factor is > 0.5?

Kind regards!

• Maybe this will help: cs.berkeley.edu/~vazirani/algorithms/all.pdf#page=38 – mikeazo Nov 6 '12 at 14:28
• I think that you have the right sketch: find a witness to the Miller-Rabbin test; since that's a liar to the Fermat test, you can efficiently exhibit a non-trivial factor of $N$ as $\gcd(x-1,N)$ or $\gcd(x+1,N)$, where $x$ is the butlast result in the Miller-Rabbin test. I see no reason why odds of success would not be $\ge3/4$ for each random base tested. – fgrieu Nov 6 '12 at 15:57
• @fgrieu: Thank you for answering. Could you perhaps elaborate a bit more on why you think the success rate should be >= 3/4 – Nyfiken Nov 6 '12 at 16:19
• This is more of a self note but wanted to include any how - believe this website has a good description. Better late than never ! - As I understand it, we basically need to try the exponents (n-1/2), (n-1/4) and so on... – Ravindra HV Jul 30 '17 at 18:39

Yes, using Miller-Rabin with a random witness does give a practical factoring method. When you run the Miller-Rabin algorithm, it can end in one of three ways:

1. The final value is not 1; this case causes Miller-Rabin to output "Composite"

2. An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite"

3. The initial value was 1; or an intermediate value was N-1; this causes Miller-Rabin to output "Probably Prime".

Case 1 will happen only if $W^{N-1} \neq 1 \bmod N$, however, that we get that inequality for Carmichael numbers only if $W$ is a multiple of a factor of $N$; in this case, $gcd(W, N)$ gives us a nontrivial factor.

For Case 2, well, that gives us a nontrivial value $X$ for which $X^2 = 1 \bmod N$; as you correctly point out, a nontrivial square root of $N$ immediately gives us the nontrivial factors $gcd(X+1, N), gcd(X-1, N)$

Hence, in the specific case of Carmichael numbers, if the Miller Rabin test outputs "Composite", we always have enough information to immediately factor. And, when Miller-Rabin is given a composite number, then it will output "Composite" with probability > 3/4; hence, a single iteration will allow us to factor with high probability.

In fact, for Carmichael numbers, the probability of success with Miller Rabin is actually > 7/8; Carmichael numbers are not the worse case for Miller Rabin.

This gives us a practical factorization method; however for pedantic reasons, it doesn't actually answer the question. It's not a poly-time algorithm; it is a probabilistic poly-time algorithm which, per iteration, has a good probability of yielding a factor, but it also has a probability of not finding a factor.

• Is there a rigorous proof somewhere that the probability of composite-declaring is more than $3/4$? – user16972 Mar 7 '20 at 22:24

Try this (a description of the comment above - also blogged the same! + posted same in math.stackexchange.com) :

For each prime base (2,3,5,7,11...) try checking the remainder for the exponents under [(n-1)/2],[(n-1)/4],[(n-1)/8]...and so on. Once a number other than 1 is found then try :

gcd (x-1,n)

or

gcd (x+1,n).

It should result in one of the factors!

For example :

Moduluo : n=561 base : a=2

[a^(n-1/1)] mod (n) : (2^560) mod (561) = 1 [a^(n-1/2)] mod (n) : (2^280) mod (561) = 1 [a^(n-1/4)] mod (n) : (2^140) mod (561) = 67

gcd(561,68)=17

gcd(561,66)=33

561/33=17

561=3*11*17 !!

• Actually, if you choose $a$ randomly, we can show it works signficantly more often than 1/2 the time; IIRC (and as I said in my answer), it works at least 7/8 of the time. That should also be true if you try $a$ in succession (as you suggest); however, we don't have a proof of that... – poncho Jul 31 '17 at 19:40