Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

A Carmichael number $N$ is a probable prime to every base $a$ coprime to $N$, but there is a base $a$ with $1<a<N$ not too big and coprime to $N$ (if it is NOT coprime to $N$, $gcd(a,N)$ is a non-trivial factor), such that $N$ is not strong probable prime to base $a$. $a$ is called a witness.

For such an $a$, you have $\large a^{2^d\times m} \neq -1\ (\ mod\ N)$ for all $d$ with $0\le d \le k$, when $N=2^k\times m+1$ with $m$ odd.

But for some $d$ with $1\le d\le k$ (choose the smallest such $d$) you have $\large a^{2^d\times m}\equiv 1\ mod \ (\ N\ )$.

But the congruence does not hold for the exponent $d-1$ indstead of $d$. Note, that $a^m\equiv 1\ (\ mod\ N)$ is impossible, if a is a witness.

So, you have a congruence $x^2\equiv\ 1\ (\ mod\ N)$ , but $x\ne \pm1\ (\ mod\ N)$ and $gcd(x-1,N)$ is a non-trivial factor of $N$ ($gcd(x+1,N)$ is a non-trivial factor as well).

share|cite|improve this answer

Your Answer


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.