9
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ This is more of a self note but wanted to include any how - believe this website has a good description. Better late than never ! - As I understand it, we basically need to try the exponents (n-1/2), (n-1/4) and so on... $\endgroup$ – Ravindra HV Jul 30 '17 at 18:41
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.