# Carmichael number factoring

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!

-

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).