NTIC Another Primality Test

Section 12.3 Another Primality Test

For a long time it was open whether we might be lucky and show there are only finitely many Carmichael numbers. However, as was proved in the mid-nineties, there are infinitely many Carmichael numbers.

🔗

So now what? Can we find other ways to reliably get primes?

🔗

Subsection 12.3.1 Another pattern

🔗

To answer this, we turn to another result visible in our modular power graphic.

Colored table of powers modulo $n=11$ — 🔗
Figure 12.3.1. Colored table of powers modulo $n = 11$

🔗

As usual, Fermat's Little Theorem is the right-hand column. What's that pattern in the middle column? Can you confirm it in the interactive version?

xxxxxxxxxx
 
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
@interact
def power_table_plot(p=(11,prime_range(100)[2:])):
    mycmap = plt.get_cmap('gist_earth',p-1)
    myloc = IndexLocator(floor(p/5),.5)
    myform = FuncFormatter(lambda x,y: int(x+1))
    cbaropts = {  'ticks':myloc, 'drawedges':True, 'boundaries':srange(.5,p+.5,1)}
    P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p)]),cmap=mycmap, colorbar=True, colorbar_options=cbaropts, ticks=[myloc,myloc], tick_formatter=[None,myform])    
    show(P,figsize=6)

🔗

Theorem 12.3.2. The Square Root of Fermat's Little Theorem.

a^{(p - 1) / 2} \equiv \pm 1 (mod p) for any odd prime modulus p ∤ a

🔗

Proof.

Since $a^{p-1}\equiv 1$ we know that $a^{(p-1)/2}$ is a solution to $x^2\equiv 1\text{.}$ (Note that $p$ is odd so $(p-1)/2$ makes sense.)

As in Section 7.3, we can rewrite and factor the congruence $x^2\equiv 1$ as $p\mid x^2-1=(x+1)(x-1)\text{.}$ Given that $p$ is an odd prime, that means $p\mid x-1$ or $p\mid x+1\text{.}$

Then $x\equiv \pm 1$ (mod $p)\text{.}$ (This is restated in Subsection 16.1.1.) Since $a^{(p-1)/2}$ is one such solution, then $a^{(p-1)/2}\equiv \pm 1$ (mod $p$).

🔗

What is the use for us of this theorem? Think similarly to the pseudoprime situation. Imagine we are testing some number

n

for primality, but we then find that

a^{(n - 1) / 2} ≢ \pm 1 (mod n),

🔗

then that number is definitely not prime.

🔗

Let's try this on our pesky Carmichael number, once again starting with base

a = 2 .

(Remember that we already know

2^{561 - 1} \equiv 1

since

561

is a pseudoprime.)

xxxxxxxxxx
 
mod(2,561)^((561-1)/2)

🔗

Not again! Try another base – maybe

a = 3 ?

xxxxxxxxxx
 
mod(3,561)^((561-1)/2)

🔗

Phew, this works, as

3^{(561 - 1) / 2} ≢ \pm 1

(and

561

is not prime). So this criterion does help us test at least a little better.

🔗

Subsection 12.3.2 Miller's test

🔗

A slightly stronger variant of this test is called Miller's test base

a

for primality, after American computer scientist Gary Miller.

🔗

Algorithm 12.3.3. Miller's test for base $a$ .

We will proceed by repeatedly dividing and then checking a congruence.

Begin with $n - 1;$ divide it by two, and then check the power

$a^{(n - 1) / 2} (mod n) .$

If the result is $- 1$ we say $n$ passes Miller's test. If the result is not $\pm 1,$ we say it fails Miller's test (since if $n$ is prime, the result would certainly be $\pm 1$ ). If the result is $+ 1,$ we continue.
If we have arrived at a point where we can no longer divide $n - 1$ by two, we say $n$ passes Miller's test. Otherwise, assuming $a^{(n - 1) / 2} \equiv 1,$ we continue by dividing the power itself by two and then taking $a$ to that new power. Once again, if the result is $- 1$ we say $n$ passes the test, and if it is not $\pm 1,$ we say it fails.
If the result is $+ 1$ and we can continue dividing the power by two, do so and check the result, as often as need be. If we arrive at the point where we have divided $n - 1$ by all possible powers of two and the result is still $\pm 1,$ then we say $n$ passes the test.

🔗

Example 12.3.4.

Let's see a few examples of this. First, the number $1387$ is a pseudoprime base 2 – but it does not pass Miller's test, which is good since it's composite. Try the following cell to see exactly what happens.

xxxxxxxxxx
 
n=1387
pretty_print(html("We know $%s$ is composite because it factors as $%s$"%(n,factor(n))))
pretty_print(html("Let's check $2^{(%s-1)/2}$ modulo $%s$: it's $%s$"%(n,n,mod(2,n)^((n-1)/2))))

Looking good … But let's try another pseudoprime number (the Mersenne number $M_{11},$ in fact) to see if it passes, just to be sure.

xxxxxxxxxx
 
n=2047
pretty_print(html("We know $%s$ is composite because it factors as $%s$"%(n,factor(n))))
pretty_print(html("Let's check $2^{(%s-1)/2}$ modulo $%s$: it's $%s$"%(n,n,mod(2,n)^((n-1)/2))))

As we can see, this shows that $n = 2047$ passes the first part of Miller's test base 2, and that there is no further to go because $(2047 - 1) / 2 = 1023$ is odd. So, as far as we know thus far, $2047$ is prime (though actually it is the lowest Mersenne number with prime exponent not to be prime).

Let's try Algorithm 12.3.3 with another number, $1009 .$

xxxxxxxxxx
 
n=1009
pretty_print(html("We know $%s$ is prime because it factors as $%s$"%(n,factor(n))))
pretty_print(html("Let's check $2^{(%s-1)/2}$ modulo $%s$: it's $%s$"%(n,n,mod(2,n)^((n-1)/2))))
pretty_print(html("Let's check $2^{(%s-1)/2/2}$ modulo $%s$: it's $%s$"%(n,n,mod(2,n)^((n-1)/2/2))))

This passes Miller's test the first time, but the algorithm keeps going since our first computation was $\equiv 1 .$ The second time we got $\equiv - 1,$ so we stop and hope the number is prime. (It is, in this case!)