Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.