Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further explanation why.

Furthermore, since Miller-Rabin 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 \pmod N$, where N is the Carmichael number we want to factor and $x$ the nontrivial square root of 1. 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-Rabin 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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.