Primality Tests II

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 $a^{n-1} \equiv 1 \pmod n.$ We also saw that this method would utterly fail when we throw a Carmichael number at it.

Euler Test

The basic enhancement is as follows.

Lemma.

If $p$ is prime and $m^2 \equiv 1 \pmod p$ , then $m \equiv \pm 1 \pmod p.$

The lemma is quite easy to prove. By the given condition $m^2 - 1 = (m-1)(m+1)$ 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:

$\left(a^{\frac{p-1} 2}\right)^2 = a^{p-1} \equiv 1 \pmod p \implies a^{\frac{p-1}2} \equiv \pm 1\pmod p.$

In other words, to test if an odd n is prime, we pick a base a < n and check if $a^{\frac{n-1}2}\equiv \pm 1\pmod n.$ 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 $a^{\frac{n-1}2} \equiv \pm 1\pmod n$ , then we must have $a^{n-1}\equiv 1\pmod n.$

Example 1

Consider n = 11305. We pick the smallest base a = 2. This gives us:

$a^{\frac{n-1}2} = 2^{5652} \equiv 10641 \not\equiv \pm 1 \pmod {n}.$

Notice that the Fermat with the same base would give $a^{n-1} \equiv 10641^2 \equiv 1 \pmod n.$ Hence a pseudoprime can be picked up by the Euler test.

Example 2

Suppose we pick n = 10585 as before. We obtain:

$2^{\frac{n-1}2} \equiv 3^{\frac{n-1}2} \equiv 1 \pmod n$

so Euler test is not more effective than Fermat test in this case.

Example 3

Let’s pick the smallest Carmichael number n = 561. We have:

$5^{\frac {n-1} 2} = 5^{280} \equiv 67 \pmod {561}$

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 $a^{\frac {n-1} 2} \mod n$ instead of $a^{n-1} \mod n$ .

blue-lin

Euler Pseudoprimes

As we saw above, even composite n can pass the Euler test for some bases.

Definition.

If $n$ is odd composite and $a\ne 1$ is such that $a^{\frac{n-1}2} \equiv 1 \pmod n$ , then we say $n$ is an Euler pseudoprime to base $a.$

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.

Exercise

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.

blue-lin

Rabin-Miller Test

As we noted above, if p is prime then whenever $m^2\equiv 1\pmod p$ we have $m \equiv \pm 1 \pmod p.$ This observation helps us to identify the pseudoprime n = 10585 in example 2.

Indeed, we have $2^{\frac {n-1}2} \equiv 1 \pmod n.$ However, since $\frac {n-1}2$ is even, we can go one step further and check if $2^{\frac {n-1}4} \equiv \pm 1 \pmod n.$ In our case, we obtain $2^{\frac {n-1}4} \equiv 10294 \not\equiv \pm1 \pmod n$ and thus we see that n is composite.

This is the gist of the Rabin-Miller test. The idea is that if $a^{(n-1)/2^k} \equiv 1 \pmod n$ and the exponent ${\frac {n-1} {2^k}}$ is even, then we check whether

$a^{(n-1)/2^{k+1}} \equiv \pm 1 \pmod n.$

If it is not, n must be composite.

Rabin-Miller Test.

Suppose $a\ne 1$ is a given base and $n$ is odd. Let $2^k$ be the highest power of 2 dividing $n-1$ and compute

$r := a^{(n-1)/2^k} \mod n.$

Perform the following for $k-1$ iterations.

If $r \equiv \pm 1 \pmod n$ , output PASS.

Let $r \leftarrow r^2 \mod n$ .

If $r \equiv +1 \pmod n$ , output FAIL.

Go back to step 1.

Example

If we set n = 10585 and a = 2 as above, then k = 3 and $\frac{n-1} {2^k} = 1323.$ Thus we have $r = 2^{1323} \mod n = 7958.$

During the first iteration, we skip through step 1, set $r\leftarrow r^2 \mod n = 10294.$ Thus we skip step 3 as well.

During the second iteration, we skip through step 1, set $r\leftarrow r^2\mod n = 1.$ Thus step 3 says n fails the test.

blue-lin

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.

Example

Suppose n = 8321 and a = 2. The highest power of 2 dividing n-1 is 2⁷. Hence we have $r = 2^{8320/128} \equiv 8192 \pmod n.$ The next iteration then gives $r \equiv 8192^2 \equiv -1 \pmod n$ 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.

Theorem.

If $n$ is odd composite, it will fail the Rabin-Miller test for 75% of $a$ within the range $1 < a < n.$

Thus, for a given odd n we randomly pick $1 < a < n$ 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 $(\frac 1 4)^{20} = 2^{-40}$ . 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.

Theorem (Miller).

Assuming the Generalized Riemann Hypothesis (GRH), if $n$ passes the Rabin-Miller test for all $1 < a < 2(\log n)^2$ , then it is prime.

Miller noted that the multiplicative group $(\mathbb Z/n\mathbb Z)^*$ is generated by elements bounded by $2(\log n)^2$ 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.

blue-lin

Summary

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)² 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.

blue-lin

Primality Tests II