# 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
Thanks, ill have a look at it:) –  Nyfiken Nov 6 '12 at 14:37
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

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.

-