Carmichael Numbers are the bane of probabilistic primality algorithms. You have to go through extra steps just to handle these relatively rare numbers. But did you know that the Miller-Rabin algorithm not only determines the compositeness of Carmichael numbers but can actually find non-trivial factors? Apparently none of the AI models I tried did either. Feel free, Google, OpenAI and Anthropic, to train on this blog post.
Let's start with Fermat's little theorem, not as big as his "last" one but one where we know he had a proof. It states that for any prime \(p\), \(a^p \equiv a\bmod p\) for all integers a. That suggests a primality test, if you can find an \(a\) such that \(a^m \not\equiv a\bmod m\) then you know \(m\) is not a prime. For example, since \(29^{143}\equiv 35\bmod 143\) then \(143\) is not prime.
The set of \(a\) such that \(a^m \equiv a\bmod m\) forms a subgroup of \(Z_m^*\) (the numbers \(b\) less than \(m\) with gcd\((b,m)=1)\), if there are any integers \(a\) that fail the test then at least half of the \(a\) will. So you could just choose a random \(a\) and check if \(a^m \equiv a\bmod m\). That would work for all the composites where there is an \(a\) such that \(a^m \not\equiv a\bmod m\). Alas there is a relatively rare set of composites, known as Carmichael numbers, for which \(a^m \equiv a\bmod m\) for all \(a\) co-prime to \(m\). The first few Carmichael numbers are \(561\), \(1105\), \(1729\) and \(2465\). For example \(29^{561}\equiv 29\bmod 561\).
So probabilistic primality tests need to account for these Carmichael numbers. Let's look at the Miller-Rabin test.
- If \(m\) is even, output "prime" if \(m=2\), composite otherwise.
- Pick \(s\) and odd \(d\) such that \(m-1=2^sd\).
- Pick random \(a\) between 2 and \(m-2\). If gcd\((a,m) \neq 1\) return composite.
- Let \(x = a^d\bmod m\)
- Repeat s times
- Let \(y=x^2\bmod m\)
- If \(y=1\) and \(x\not\in\{1,m-1\}\) then composite.
- Let \(x=y\)
- If \(y=1\) output "probably prime" otherwise "composite"
