Carmichael number factoring 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!
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:


The final value is not 1; this case causes Miller-Rabin to output "Composite"
An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite"
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.