10
$\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!

  • 0
    This is more of a self note but wanted to include any how - believe [this](http://mathforum.org/kb/message.jspa?messageID=5488111) 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...2017-07-30

2 Answers 2

2

A Carmichael number $N$ is a probable prime to every base $a$ coprime to $N$, but there is a base $a$ with $1 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).

0

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

  • 1
    Welcome to Mathematics StackExchange. We use MathJax to represent data and equations. An excellent guide is at https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference.2017-07-30