Carmichael Numbers

Recall Carmichael numbers are composite numbers that almost always fool the Fermat primality test. We can show that Carmichael numbers must have certain properties.

First we show they cannot be of the form $n=pq$ where $p,q$ are distinct primes with $p>q$. By the Chinese Remainder Theorem we have ${\mathbb{Z}}_n={\mathbb{Z}}_p\times {\mathbb{Z}}_q$. Then $$n-1=pq-1=q(p-1)+q-1.$$ Suppose $a$ is not a multiple of $p$. Then $a^{n-1}=(a^{p-1}{)}^q{a}^{q-1}=a^{q-1}(modp)$ (by Fermat we have $a^{p-1}=1(modp)$). Then if $a$ passes the Fermat test, we must have $a^{q-1}=1(modp)$ and hence $a^d=1$, where $d=\gcd (p-1,q-1)$. Since ${\mathbb{Z}}_p^{*}$ is cyclic, there are exactly $d$ choices for $a$ that satisfy $a^d=1$.

Since $q$ is strictly smaller than $p$, the greatest common divisor of $p-1$ and $q-1$ is at most $(p-1)/2$. Thus at most half the choices for $a$ can fool the Fermat test. For primes $p,q$ used in RSA, $d$ is small with high probability, so the product $pq$ will almost never fool the Fermat test, as mentioned earlier.

Next suppose $n$ is not squarefree, that is $n=p^{k}r$ for some prime $p$ and $k\ge 2$. Then by the Chinese Remainder Theorem, ${\mathbb{Z}}_n={\mathbb{Z}}_{p^k}\times {\mathbb{Z}}_r$. Any $a\in {\mathbb{Z}}_{p^k}$ satisfies $a^{\varphi (p^k)}=1$ by Euler's Theorem, so if $a^{n-1}=1$ as well, then we must have $a^d=1$ where $$d=\gcd (n-1,\varphi (p^k))=\gcd (p^{k}r-1,p^{k-1}(p-1)).$$ Since ${\mathbb{Z}}_{p^k}$, is cyclic, exactly $d$ elements $a\in {\mathbb{Z}}_{p^k}$ satisfy $a^d=1$. As $p$ cannot divide $p^{k}r-1$, the largest possible value for $d$ is $p-1$, giving an upper bound of $(p-1)/(p^k-1)\le 1/4$ probability that $n$ will pass the Fermat test.

Hence if $n$ is a Carmichael number, then $n$ is squarefree and is the product of at least three distinct primes.

Solovay-Strassen Test

Recall our first suggestion for improving the Fermat test was to check check that $a^{(n-1)/2}=\pm 1$ after checking $a^{n-1}=1$ (since there are no nontrivial square roots of unity modulo a prime).

We can improve this by checking instead that $$a^{(n-1)/2}=(\frac{a}{n-1}).$$ This is known as the Solovay-Strassen test, which we examine here for historical interest. Recall that the Jacobi symbol can be evaluated quickly using quadratic reciprocity.

Why does this help? From above we know that if $n$ is not squarefree then $n$ fails the Fermat test with probability at least $3/4$. So we need only consider the case when $n$ is squarefree but composite, say $n=pr$ where $p$ is prime.

By the Chinese Remainder Theorem any $x\in {\mathbb{Z}}_n$ can be written as $(a,b)\in {\mathbb{Z}}_p\times {\mathbb{Z}}_r$. For any nonzero $a\in {\mathbb{Z}}_p$ we have $a^{p-1}=1$ by Fermat, so if $a^{n-1}=1$ then we have $a^d=1$ where $d=\gcd (p-1,n-1)$.

If $d<p-1$ then $d$ is at most $(p-1)/2$. Since ${\mathbb{Z}}_p^{*}$ is cyclic, this means at most $(p-1)/2$ elements of $a\in {\mathbb{Z}}_p$ satisfy $a^d=1$. That is, the probability $a$ will pass the Fermat test is at most $1/2$.

On the other hand, if $d=p-1$, then this implies $p-1\mid N-1$. Since $N-1=pr-1=(p-1)r+r-1$ we have $p-1\mid r-1$, so write $r-1=s(p-1)$. Then $$a^{pr-1}=a^{(p-1)r}{a}^{(p-1)s}=1.$$ But we have $$(\frac{x}{n-1})=(\frac{a}{p})(\frac{b}{r})$$ and since there is a $1/2$ chance that $a$ is a quadratic residue, there is a $1/2$ chance that $(x\mid n-1)=-1$ and fail the test.

In other words, for any composite $n$ (even a Carmichael number) the probability $n$ passes the Solovay-Strassen test is at most $1/2$. This was the first algorithm discovered for finding large primes.

Miller-Rabin Test

The Miller-Rabin test surpasses the Solovay-Strassen test in every way: the probability a composite number $n$ passes is only $1/4$, and no Jacobi symbol computations are required. Moreover, any $a$ that exposes the compositeness of $n$ in the Solovay-Strassen test also causes the Miller-Rabin test to fail.