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?