In this article, we discuss some ways of improving the basic Fermat test. Recall that for Fermat test, to test if n is prime, one picks a base a < n and checks if We also saw that this method would utterly fail when we throw a Carmichael number at it.
The basic enhancement is as follows.
If is prime and , then
The lemma is quite easy to prove. By the given condition is a multiple of p and since p is prime either (m – 1) or (m + 1) is a multiple of p and the result follows.
In particular, if p is an odd prime and a is not divisible by p, then by Fermat’s theorem we have:
In other words, to test if an odd n is prime, we pick a base a < n and check if If it is not, then n is not prime. This is called the Euler test with base a.
Note that the Euler test is necessarily stronger than the Fermat test since if , then we must have
Consider n = 11305. We pick the smallest base a = 2. This gives us:
Notice that the Fermat with the same base would give Hence a pseudoprime can be picked up by the Euler test.
Suppose we pick n = 10585 as before. We obtain:
so Euler test is not more effective than Fermat test in this case.
Let’s pick the smallest Carmichael number n = 561. We have:
so there are Carmichael numbers which succumb to the Euler test.
In conclusion, the Euler test is strictly stronger than the Fermat test. Furthermore, it’s a little faster since we only need to compute instead of .
As we saw above, even composite n can pass the Euler test for some bases.
If is odd composite and is such that , then we say is an Euler pseudoprime to base
Thus from our above example, 10585 is an Euler pseudoprime to bases 2 and 3.
Clearly, if n is an Euler pseudoprime to base a, then it is also a pseudoprime to base a. However, as example 1 above shows, there are pseudoprimes which are not Euler pseudoprimes (for a fixed given base). As example 3 shows, some Carmichael numbers can fail the Euler test, which spells good news for us.
Unfortunately, not all Carmichael numbers can be identified composite by the Euler test. Specifically, there are odd composite n which is an Euler pseudoprime for all a which are coprime to n. Such numbers are known as absolute Euler pseudoprimes. It turns out Chernick’s construction for Carmichael numbers also gives us absolute Euler pseudoprimes.
Suppose k is a positive integer such that 6k + 1, 12k + 1 and 18k + 1 are prime. Prove that n := (6k + 1)(12k + 1)(18k + 1) is an absolute Euler pseudoprime.
Thus, we are not quite out of the woods yet.
As we noted above, if p is prime then whenever we have This observation helps us to identify the pseudoprime n = 10585 in example 2.
Indeed, we have However, since is even, we can go one step further and check if In our case, we obtain and thus we see that n is composite.
This is the gist of the Rabin-Miller test. The idea is that if and the exponent is even, then we check whether
If it is not, n must be composite.
Suppose is a given base and is odd. Let be the highest power of 2 dividing and compute
Perform the following for iterations.
- If , output PASS.
- Let .
- If , output FAIL.
- Go back to step 1.
If we set n = 10585 and a = 2 as above, then k = 3 and Thus we have
During the first iteration, we skip through step 1, set Thus we skip step 3 as well.
During the second iteration, we skip through step 1, set Thus step 3 says n fails the test.
Effectiveness of Rabin-Miller
Clearly the Rabin-Miller test is stronger than the Euler test, but just how much stronger is it? There are indeed composite numbers which pass the Rabin-Miller test for specific bases. These are called strong pseudoprimes.
Suppose n = 8321 and a = 2. The highest power of 2 dividing n-1 is 27. Hence we have The next iteration then gives so n passes the Rabin-Miller test to base 2.
On the other hand, one easily checks that n fails the Fermat test for base 3 so it is composite.
Thankfully, we do not have the case of Carmichael numbers here.
If is odd composite, it will fail the Rabin-Miller test for 75% of within the range
Thus, for a given odd n we randomly pick for about 20 trials. If n passes all trials, we report that it is most likely prime. Otherwise, if it fails even a single trial, then it is composite. Heuristically, one imagines that the probability of n being composite and passing all trials to be about . In practice 75% is a gross underestimate since for most randomly chosen large n, the Rabin-Miller test will fail for >99% of the bases.
We have here a probabilistic primality testing method, in the sense that if n passes the test, it is overwhelmingly likely to be prime; on the other hand, any failure immediately implies n is composite.
Our confidence in the Rabin-Miller test is further enhanced by the following result.
Assuming the Generalized Riemann Hypothesis (GRH), if passes the Rabin-Miller test for all , then it is prime.
Miller noted that the multiplicative group is generated by elements bounded by and thus it suffices to check for all bases in that bound. The conjecture remains open to this day – if you can prove it, you stand to win a million dollars. We will not delve into this topic since the GRH is an extremely deep result. However, we do note that there is overwhelming computational evidence in support of the conjecture and in practice it is reasonable to run the Rabin-Miller test within the above specified bound.
The Rabin-Miller test is a highly efficient and reliable, albeit probabilistic, primality test. In general, we would like our primality tests to satisfy the following conditions.
- Deterministic: it can tell with absolute certainty if n is prime.
- Efficient: its runtime is polynomial in the length of n (i.e. O((log n)d) for some d.
- Unconditional: it does not assume any open conjecture.
If we run, say, 20 iterations of Rabin-Miller we obtain a probabilistic efficient test, i.e. the second and third conditions are satisfied but not the first. Assuming the GRH, we could test for all bases less than 2(log n)2 and obtain a primality test satisfying the first and second conditions but not the third.
In addition there’s a primality test by Adleman, Pomerance and Rumely which is based on the elliptic curve group. This test is deterministic and unconditional, but its runtime complexity is slightly worse than polynomial time (in log n). Thus, it satisfies the first and third properties but not the second. We may describe this test in a later article.
For years, computer scientists wondered if there is a deterministic, polynomial-time and unconditional primality test. This was finally answered in the affirmative in 2002 by Agrawal, Kayal and Saxena who found a test which satisfied all three conditions. Unfortunately, despite being polynomial in the size of n, the algorithm can only be used on very modestly sized numbers when applied in practice, despite extensive optimization efforts by various people.