\def\nn{\noindent}
\def\mm{\medskip}
\magnification=\magstep5
\hfuzz=4pt
\baselineskip.5truein
\centerline{RECENT DEVELOPMENTS}

\centerline{IN PRIMALITY TESTING}
\bigskip

\bigskip
\centerline{Jon Grantham}

\centerline{Institute for Defense Analyses}

\centerline{Center for Computing Sciences}

\centerline{Bowie, MD}
\bigskip
\centerline{grantham@super.org}
\medskip
\centerline{http://www.clark.net/pub/grantham/pseudo/}
\vfill\eject
\centerline{\bf Outline}
\vskip.5truein

\noindent{Old Results in Primality Proving}

The $n-1$ Test and its Relatives

The APR Test

\vskip.3truein

\noindent Old Results in Probable Primality Testing

Pseudoprimes

From Pseudoprimes to Provable Primes

\vskip.3truein

\noindent{New Results in Primality Proving}

Updates

Elliptic Curve Methods

New Life for the $n-1$ Test

\vskip.3truein

\noindent{New Results in Probable Prime Testing}

Perrin Pseudoprimes

Carmichael Numbers

Frobenius Pseudoprimes
\vfill\eject

\centerline{\bf Not-So-Recent Developments}
\centerline{\bf in Primality Proving}

\vskip.5truein

\centerline{\bf The Pocklington-Lehmer $n-1$ Test}

\vskip.5truein

Let $n$ be an integer with $n-1=FR$ and $F>\sqrt{n}$.  If there exists
an $a$ with $a^{n-1}\equiv 1 \bmod n$ and 
$$\gcd(a^{{n-1}\over q}-1,n)=1$$
for each prime $q|F$, then $n$ is prime.

\vskip.7truein

Why?  For each prime $p|n$, we have $(a^R)^F\equiv 1 \bmod p$, but
$(a^R)^{F/q}\not\equiv 1$ for any $q|F$.  Thus $a^R$ has order $F$ mod
$p$.  But $a^{p-1}\equiv 1$ mod $p$, and thus $F|(p-1)$.  Therefore,
$p-1\ge F>\sqrt{n}$ for each $p|n$.  This can only happen if $n$ is prime.
\vfill\eject

\centerline{\bf The $n-1$ method and its relatives}

\vskip.5truein

With the $n-1$ method,and the $n+1$, $n^2+1$, $n^2-n+1$ or $n^2-n-1$
methods
(Lucas; Pocklington; Lehmer; Robinson; Brillhart, Lehmer, Selfridge; Williams),
the time required to prove primality is polynomial, {\bf
once you find the factorization of
a factor of $n-1$ (or $n+1$, etc.) that is greater than
$n^{1/3}$} (or $n^{1/2}$, depending on the test).

\vskip.5truein

This is a practical test.  
A version of the $n+1$ test has
been used to prove primality or compositeness of Mersenne numbers
($2^p-~1$), including the current world record prime, $2^{1398269}-1$, which 
was proved prime in $88$ hours on a Pentium-90.
\vfill\eject

\centerline{\bf The APR Test}

\vskip.6truein

The APR test (or the APRCL test)
(Adleman, Pomerance, Rumely; Cohen, H. Lenstra) was first described in 1980.
It involves testing congruences in cyclotomic extensions of the
rationals.

\vskip.5truein

The APR test turns out to have a
 running time of ${O}\left((\log n)^{c\log\log\log n}\right)$.
In one version, the running time is probabilistic; in another, the
running time is deterministic.

\vskip.5truein

The probabilistic version of the APR test is practical.
\vfill\eject
\centerline{\bf Not-So-Recent Developments}
\centerline{\bf in Probable Prime Testing}

\vskip.5truein

\centerline{\bf Pseudoprimes}

\vskip.5truein

By Fermat's Little Theorem, if $p$ is a prime not dividing $a$,
$$a^{p-1}\equiv 1\bmod p.$$

\vskip.4truein

The converse is not true.  $2^{340}\equiv 1\bmod 341$, but $341$ is
not prime.  We call $341$ a {\bf pseudoprime} to the base $2$.

\vskip.6truein

The pseudoprime test, however, is often ``good enough.''  In particular, it
provides a useful way of exposing composites.
\vfill\eject
\centerline{\bf Other Pseudoprimes}

\vskip.4truein

We also know if $p\not| 2a$,
$$a^{{p-1}\over 2}\equiv \left(a\over p\right)\bmod p.$$

The converse does not hold; for example,
$2^{280}\equiv \left(2\over 561\right)$.  We call
$561$ an {\bf Euler pseudoprime} to the base $2$. (Robinson)

\vskip.3truein

If $n\equiv 1 \bmod 4$, we can look at $a^{(n-1)/{2^k}}$ for $k>1$.
A {\bf strong pseudoprime} to the base $a$ is an odd composite
$n=2^rs+1$, with $s$ odd, such that either $a^s\equiv 1 \bmod n$, or
$a^{2^ts}\equiv -1$ for some integer $t$, with $r>t\ge 0$. (Dubois;
Selfridge)

\vskip.3truein
Composites $n$ dividing
$F_{n-{\left(n\over 5\right)}}$
are {\bf Fibonacci pseudoprimes}.  This generalizes to the concept
of {\bf Lucas pseudoprimes}.
\vfill\eject
\centerline{\bf Pseudoprimes to Multiple Bases}
\vskip.4truein

There are numbers which are pseudoprimes to every base.  We call these
numbers {\bf Carmichael numbers}.

\vskip.25truein

No numbers are Euler pseudoprimes to all bases.  In fact, for every
composite $n$, for at least ${1 \over 2}n$ bases less than $n$,
$n$ is {\bf not} an Euler pseudoprime.  (Solovay-Strassen)

\vskip.25truein

Even better --- no composite $n$ can be a strong pseudoprime to more than
${1 \over 4}n$ bases.  (Monier; Rabin)

\vskip.15truein

This means that if we chose bases at random, a composite has at most
a ${1 \over 4}$ chance of passing $1$ iteration of this test, and a
${1 \over 4^k}$ chance of passing $k$ iterations.

\vfill\eject
\centerline{\bf When Probable becomes Provable}

\vskip.4truein
Miller proved a result which is equivalent to this:

Assuming the ERH, if $n$ is composite, there is a
base $b<c\log^2 n$ for which $n$ fails the strong pseudoprime test to the
base $b$.
\vskip.2truein
Since a strong pseudoprime test takes $O(\log^3 n)$ bit operations, we
have a method of primality proving that can be done in $O(\log^5 n)$
bit operations\dots if we can prove the Extended Riemann Hypothesis.
\vskip.2truein
A hard problem in computational number theory
(primality proving in deterministic polynomial time) was reduced
to a hard problem in
analytic number theory (ERH).
\vfill\eject
{\centerline{\bf New Results in Primality Proving}}
\vskip.2truein
{\centerline{\bf Goldwasser-Kilian}}

\vskip.1truein

Goldwasser and Kilian gave a test that heuristically
runs in polynomial time. It runs in polynomial time
for all but a small (infinite) class of primes.  

\vskip.2truein

Replace the group $\left({\bf Z/}n{\bf Z}\right)^*$
in the $n-1$ test with the group of points on an elliptic curve modulo $n$.
Count the points with
Schoof's algorithm (time: $O(\log^8 n)$).  

\vskip.2truein

The Goldwasser--Kilian algorithm isn't very practical, but represents
an important conceptual breakthrough.

\vskip.05truein

This method produces primality
{\bf certificates} which can be checked quickly without repeating the
entire proof.
\vfill\eject
{\centerline{\bf Atkin and Morain's ECPP}}

\vskip.2truein

Atkin developed a similar algorithm; he and Morain implemented it.

\vskip.3truein

They only use curves with complex multiplication.
It is much faster to compute the order of these curves.

\vskip.3truein

As a result, their algorithm is practical.  They have made a
version of it available under the name ECPP (Elliptic Curves and
Primality Proving).

\vskip.3truein

The ECPP program produces certificates that can be checked with a
less complicated program.  
\vfill\eject
{\centerline{\bf Adleman-Huang}}
\vskip.3truein

Adleman and Huang achieved an impressive
theoretical milestone by modifying Goldwasser-Kilian.

\vskip.2truein

Instead of using elliptic curves, they use Jacobians of curves
$y^2=f(x)$; $f(x)$ has degree $6$.  The number of points $m$
will be larger than the prime.  But, if $m$ is
prime, we may be able to prove its primality with the
Goldwasser-Kilian method.

\vskip.1truein
If we can't use that method to prove primality, we can just pick
another polynomial $f(x)$ and try again.
\vskip.2truein

While not practical, this method is the only known polynomial time
primality proving algorithm.  (It is not deterministic.)

\vfill\eject
{\centerline{\bf New life for the $n-1$ test}}

\vskip.5truein

H. Lenstra described a test based on polynomials over a finite
field that has the same running time as the APR test.

\vskip.7truein

Let $n>1$ be an integer.
Let $I,E$ be
integers with $E|n^I-1$ and $E>\sqrt{n}$.  Let
$f(x)\in({\bf Z}/n{\bf Z})[x]$
be a monic polynomial of degree $I$
 such that mod $n$, $f(x)|x^{n^I}-x$ and
$\gcd(f(x),x^{n^{I/p}}-x)=1$ for all $p|I$.  Let
$A=({\bf Z}/n{\bf Z})[x]/(f(x))$.  Let $\alpha\in A$ be such that
$\alpha^E=1$ and $\alpha^{E/q}-1\in A^*$ for all primes $q|E$.  If
$g(T)=(T-\alpha)(T-\alpha^n)\dots(T-\alpha^{n^{I-1}})\in({\bf Z}/n{\bf Z})[T]$
and the least residue $n^j\bmod E$ is
not a proper divisor of $n$ for $1\le j<I$, then $n$ is prime.

\vfill\eject
\centerline{\bf Konyagin-Pomerance}

\vskip.5truein

In a recent paper, Konyagin and Pomerance gave several new versions of
the $n-1$ test.

\vskip.3truein

They gave a practical version if the factored part $F$ of $n-1$ is
greater than $n^{3/10}$.

\vskip.3truein

They gave a version that, if $F$ is greater than
$n^{1/4+\epsilon}$, runs in deterministic polynomial time.

\vskip.3truein

They gave a version that, if the factored part is greater than
$n^\epsilon$ and consists entirely of small primes, runs in
deterministic polynomial time.  This method works for $\gg x^{1-\epsilon}$
primes less than $x$.
\vfill\eject
\centerline{\bf What's new in probable primality testing}
\vskip.5truein
Bach has shown that the bound in the ERH-conditional test can be taken
to be $2\log^2 n$.
\vskip.4truein
If $k$-bit integers ($k>1$) are chosen at random until one is found which
passes $t$ strong pseudoprime tests, then the probability that the
number is composite is less than $4^{-t}$.  (Damgard, Landrock,
Pomerance; Burthe)
\vskip.4truein
There are infinitely many Carmichael numbers!  (Alford, Granville,
Pomerance)  Their proof uses a heuristic of Erd\H os, a version of the
prime number theorem for arithmetic progressions, and other ingredients.
\vfill\eject
\centerline{\bf Perrin Pseudoprimes}
\vskip.5truein
In the 1982, Adams and Shanks introduced a test based on a third-order
sequence known as Perrin's sequence:

$A_n=A_{n-2}+A_{n-3}$, $A_{-1}=-1$, $A_0=3$, $A_1=0$.

\vskip.15truein

The test examines congruence properties mod $n$ of the ``signature''

$(A_{-n-1},A_{-n},A_{-n+1},A_{n-1},A_n,A_{n+1})$.

\vskip.2truein

There are 3 types of acceptable signatures.  The S-signature is

$(1,-1,3,3,0,2)$.

\vskip.2truein

Pseudoprimes for this test are relatively rare.  Adams and Shanks conjectured,
but could not prove, that there are infinitely many.
\vfill\eject
\pageno18
\centerline{\bf How it Generalizes and Strengthens}
\vskip.5truein
When $n\equiv 2$ or $3\bmod 5$, the Fibonacci pseudoprime test asks whether
$F_{n+1}\equiv 0$.

Equivalently, do we have 
$$x^{n+1}-(1-x)^{n+1}\equiv 0 \bmod (n,x^2-x-1)?$$

When $n$ is prime,
$x^n\equiv 1-x$, and 
$(1-~x)^n\equiv x$.
So $$x^{n+1}-(1-x)^{n+1}\equiv (1-x)x-x(1-x)=0.$$

The Frobenius Test, in this case, asks whether $x^n\equiv 1-x$ mod 
$(n,x^2-x-1)$.  From that, it follows that $n$ passes the Fibonacci test.
\vskip.1in
Not vice versa.  $323$ is the first Fibonacci pseudoprime.  $5777$ is the
first Frobenius pseudoprime with respect to $x^2-x-1$.
\vfill\eject
\centerline{\bf Why Should You Buy}
\centerline{\bf a Definition from Me?}
\vskip.5truein
Gurak and Szekeres have given generalizations of the Perrin test.  I should have
to convince you why you should adopt mine.
\vskip.3truein
First of all, it contains their definitions.  This is good, but not sufficient.
\vskip.3truein
Looking at polynomials over finite fields exposes the underlying structure.
\vskip.1truein
I discovered that two types of pseudoprimes --
Lehmer pseudoprimes and Lucas pseudoprimes -- are essentially equivalent.  

Both
notions are over 25 years old.
\vskip.1truein
OK, but what else does it come with?
\vfill\eject
\centerline{\bf Competitors to Monier-Rabin}
\vskip.5truein
Arnault showed that a composite $n$ is a strong Lucas pseudoprime to at most
$4\over{15}$ of the bases.  (Except for some easy to detect cases.)
\vskip.3truein
Jones and Mo showed that a composite is an extra strong Lucas pseudoprime to
at most $1\over 8$ of the bases.  The test takes $2$ times as long
as the strong pseudoprime test.
\vskip.3truein
A version of my test,
the Quadratic Frobenius Test, takes asymptotically $3$ times as long
to run as the strong pseudoprime test.  Any composite passes for less than
$1\over{7710}$ of the bases.
\vfill\eject
\centerline{\bf A Version of the Quadratic Frobenius Test}
\vskip.5truein

Here is one formulation of the Quadratic Frobenius Test for numbers
$n\equiv 1\bmod 4$.
\vskip.1in
1) Verify that $n$ is not a perfect square.

2) Verify that $n$ is not divisible by a prime less than $50000$.

3) Choose $(b,c)$ at random until you find a pair with 
$\left(b^2+4c\over n\right)=-1$.

4) Let $y=x^{{n+1}\over 2}\bmod (n,x^2-bx-c)$.  Verify that $y\in{\bf Z}$ and
$y^2\equiv -c$.

5) Perform a strong pseudoprime test to the base $y$.

\vfill\eject
\centerline{\bf How Many Are There?}
\vskip.5truein
Let $f(x)\in{\bf Z}[x]$
be a monic, squarefree polynomial with splitting field $K$.  There are
infinitely many Frobenius pseudoprimes with respect to $f(x)$.
In fact, there are $\gg N^c$ Frobenius pseudoprimes with respect
to $f(x)$ which are less than $N$, for
some $c=c(K)>0$.  These numbers are Frobenius pseudoprimes for any polynomial
with splitting field $K$.
\vskip.3truein
This theorem answers the 1982 conjecture of Adams and Shanks, as well as 
proving there are infinitely many pseudoprimes in the senses of Gurak and 
Szekeres, {\bf or any other definition that uses the same basic concepts.}
\vfill\eject
\end