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: 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).
A: Try this (a description of the comment above - also blogged the same!) :
For each prime base $(2,3,5,7,11...)$ try checking the remainder for the exponents under $\frac{n-1}{2},\frac{n-1}{4},\frac{n-1}{8}\dots$ and so on.  Once a number other than $1$ is found then try : 
$\gcd (x-1,n)$ 
or
$\gcd (x+1,n)$. 
It should result in one of the factors!
For example : 
Moduluo : $n=561$
base : $a=2$
$a^{(n-1/1)}$ $\mod n$ : $(2^{560}) \mod (561) = 1$ 
$a^{(n-1/2)}$ $\mod n$ : $(2^{280}) \mod (561) = 1$ 
$a^{(n-1/4)}$ $\mod n$ : $(2^{140}) \mod (561) = 67$ 
$\gcd(561,68)=17$
$\gcd(561,66)=33$
$561/33=17$
$561=3\cdot 11\cdot 17$ !!
Related links :
http://mathforum.org/kb/message.jspa?messageID=5488111
https://en.wikipedia.org/wiki/Carmichael_number
