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 = p q\) 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
Suppose \(a\) is not a multiple of \(p\). By Fermat
Then if \(a\) passes the Fermat test, we must have \(a^{q-1} = 1 \pmod p\) 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 \(p > q\), 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.
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^{\phi(p^k)} = 1\) by Euler’s Theorem, so if \(a^{n-1} = 1\) as well, then we must have \(a^d = 1\) where
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 a candidate \(x\) satisfies \(x^{(n-1)/2} = \pm 1\) after checking \(x^{n-1} = 1\), since there are no nontrivial square roots of unity modulo a prime.
We can improve this by checking instead that
This is known as the Solovay-Strassen test. 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 = p r\) where \(p\) is prime and \(r\) is an odd number greater than 1.
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, at most \((p-1)/2\) elements of \(a \in \mathbb{Z}_p\) satisfy \(a^d = 1\). That is, the probability \(a\) passes the Fermat test is at most \(1/2\).
On the other hand, if \(d = p - 1\), then this implies \(p-1|n-1\). Since \(n - 1 = p r - 1 = (p-1)r + r -1\) we have \(p-1 | r-1\), so write \(r-1=s(p-1)\). Then
But we have
As \(r\) contains at least one odd prime factor, the sign of \((b|r)\) is positive or negative with the same probability, that is, there is a \(1/2\) chance that \(x\) fails the test.
In other words, for any composite \(n\), including Carmichael numbers, the probability \(n\) passes the Solovay-Strassen test is at most \(1/2\).
This was the first algorithm discovered for finding large primes. 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 triggers the Miller-Rabin test.