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.

🔗

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

$\begin{equation*} a^{(p-1)/2}\equiv \pm 1\text{ (mod }p)\text{ for any odd prime modulus }p\nmid a \end{equation*}$

🔗

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

We can rewrite and factor the congruence $x^2\equiv 1$ as $p\mid x^2-1=(x+1)(x-1)$ and given that $p$ is 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

$\begin{equation*} a^{(n-1)/2}\not\equiv \pm 1\text{ (mod }n)\text{,} \end{equation*}$

🔗

then that number is definitely not prime.

🔗

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

$a=2\text{.}$

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

🔗

Not again! Try another base – maybe

$a=3\text{?}$

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

🔗

Phew, this works, as

$3^{(561-1)/2}\not\equiv \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.

🔗

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\text{;}$ divide it by two, and then check the power

$\begin{equation*} a^{(n-1)/2}\text{ (mod }n)\text{.} \end{equation*}$

If the result is $-1$ we say $n$ passes Miller's test. If the result is not $\pm 1\text{,}$ we say it fails Miller's test (since if $n$ is prime, the result would certainly be $\pm 1$ ). If the result is $+1\text{,}$ 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\text{,}$ 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\text{,}$ 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\text{,}$ 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}\text{,}$ 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\text{.}$

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\text{.}$ The second time we got $\equiv -1\text{,}$ so we stop and hope the number is prime. (It is, in this case!)