\documentclass[12pt]{amsart}

\newcommand{\lra}{\longrightarrow}
\newcommand{\Z}{{\mathbf Z}}
\newcommand{\Q}{{\mathbf Q}}
\newcommand{\R}{{\mathbf R}}
\newcommand{\C}{{\mathbf C}}
\newcommand{\mymod}{\,\%\,}

\include{xy}
\xyoption{all}
\SelectTips{cm}{}
\CompileMatrices

\include{iJSepsf}
\newcommand{\graphillus}[3]{\epsfysize=#1truein
\vbox{\centerline{\epsffile{#2.eps}}\caption{#3}}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\begin{document}

\title{Large Prime Numbers}
\maketitle

\section{Fermat Pseudoprimes}

{\bf Fermat's Little Theorem} states that for any positive integer~$n$,
$$
\text{\em if $n$ is prime then $b^n\mymod n=b$ for $b=1,\dots,n-1$.}
$$
In the other direction, all we can say is that
$$
\text{\em if $b^n\mymod n=b$ for $b=1,\dots,n-1$ then $n$ might be prime.}
$$
If $b^n\mymod n=b$ where $b\in\{1,\dots,n-1\}$ then $n$ is called a
{\bf Fermat pseudoprime base~$b$}.

There are 669 primes under~5000, but only five values of~$n$ ($561$, $1105$,
$1729$, $2465$, and $2821$) that are Fermat pseudoprimes base~$b$ for $b=2,3,5$
without being prime.
This is a false positive rate of less than~$1\%$.  The false positive rate
under~500,000 just for $b=2,3$ is $0.118\%$.  

On the other hand, the bad news is that checking more bases~$b$ doesn't reduce
the false positive rate much further.  There are infinitely many
{\bf Carmichael numbers}, numbers~$n$ that are Fermat pseudoprimes base~$b$
for all $b\in\{1,\dots,n-1\}$ but are not prime.

In sum, Fermat pseudoprimes are reasonable candidates to be prime.

\vfil\pagebreak

\section{Strong Pseudoprimes}

The {\bf Miller--Rabin test} on a positive integer~$n$ and a positive test
base~$b$ in~$\{1,\dots,n-1\}$ proceeds as follows.
\begin{enumerate}
\item Factor $n-1=2^s\cdot m$ where $m$ is odd.
\item Replace $b$ by $b^m\mymod n$.
\item If $b=1$ or $b=n-1$, return the result that the test suggests that
$n$ is prime.  Otherwise continue.
\item Set $r=0$.
\item If $r<s$, proceed to step~(6).
Otherwise return the result that $n$ is composite.
\item Replace $b$ by $b^2\mymod n$.
\item If $b=n-1$, return the result that the test suggests that
$n$ is prime.  Otherwise continue.
\item If $b=1$, return the result that $n$ is composite.  Otherwise continue.
\item Increment $r$ and return to step~(5).
\end{enumerate}

The idea behind the test is that if $n$ has distinct prime factors
then the equation $x^2\mymod n=1$ has at least four solutions.
So if we find some $b$ such that $b\mymod n$ is not $1$ or~$n-1$,
and yet $b^2\mymod n=1$, then $n$ is composite.

A positive integer $n$ that passes the Miller-Rabin test for some~$b$
is a {\bf strong pseudoprime base~$b$}.

For any~$n$, at least $3/4$ of the $b$-values in~$\{1,\dots,n-1\}$
have the property that if $n$ is a strong pseudoprime base~$b$ then $n$
is really prime.
But according to the theory, up to~$1/4$ of the $b$-values have the property
that $n$ could be a strong pseudoprime base~$b$ but not be prime.
In practice, the percentage of such~$b$'s is much lower.
For $n$ up to~500,000, if $n$ is a strong pseudoprime base~$2$ and base~$3$
then $n$ is prime.

\vfil\pagebreak

\section{Generating Candidate Large Primes}

Given~$n$, a simple approach to finding a candidate prime above~$2n$ is
as follows.  Take the first of $N=2n+1$, $N=2n+3$, $N=2n+5$, \dots to pass
the following test.
\begin{enumerate}
\item Try trial division for a few small primes.  If $N$ passes, continue.
\item Check whether $N$ is a Fermat pseudoprime base~$2$.
If $N$ passes, continue.
\item Check whether $N$ is a strong pseudoprime base~$b$ as $b$ runs through
the first 20 primes.
\end{enumerate}
Any $N$ that passes the test is extremely likely to be prime.  And such an~$N$
should appear quickly.  Indeed, using only the first {\em three} primes in
step~(3) of the previous test finds the following correct candidate primes:
$$
\begin{array}{llll}
\text{The first candidate prime after} & 10^{50} &\text{is} & 10^{50}+151.\\
\text{The first candidate prime after} & 10^{100} &\text{is} & 10^{100}+267.\\
\text{The first candidate prime after} & 10^{200} &\text{is} & 10^{200}+357.\\
\text{The first candidate prime after} & 10^{500} &\text{is} & 10^{500}+331.\\
\text{The first candidate prime after} & 10^{1000} &\text{is} & 10^{1000}+453.
\end{array}
$$

\vfil\pagebreak

\section{Certifiable Large Primes}

The {\bf Lucas--Pocklington--Lehmer Criterion} is as follows.  {\em Suppose
that $N=p\cdot U+1$ where $p$ is prime and $p>U$.  Suppose also that there
is a base~$b$ such that $b^{N-1}\mymod N=1$ but $\gcd(b^U-1,N)=1$.
Then $N$ is prime.}

The proof is just Fermat's Little Theorem and some other basic number theory.

As an example of using the result, start with
$$
p=1000003.
$$
This is small enough that its primality is easily verified by trial division.
A candidate prime above $1000\cdot p$ of the form $p\cdot U+1$ is
$$
N=p\cdot1032+1=1032003097.
$$
And $2^{N-1}\mymod N=1$ and $\gcd(2^{1032}-1,N)=1$, so the LPL Criterion
is satisfied, and $N$ is prime.  Rename it~$p$.

A candidate prime above $10^9\cdot p$ of the form $p\cdot U+1$ is
$$
N=p\cdot(10^9+146)+1=1032003247672452163.
$$
Again $b=2$ works in the LPL Criterion, so $N$ is prime.  Again rename it~$p$.

A candidate prime above $10^{17}\cdot p$ of the form $p\cdot U+1$ is
$$
N=p\cdot(10^{17}+24)+1=103200324767245241068077944138851913.
$$
Again $b=2$ works in the LPL Criterion, so $N$ is prime.  Again rename it~$p$.

A candidate prime above $10^{34}\cdot p$ of the form $p\cdot U+1$ is
\begin{align*}
N=p\cdot(10^{34}+224)+1
=&10320032476724524106807794413885422\\
&46872747862933999249459487102828513.
\end{align*}
Again $b=2$ works in the LPL Criterion, so $N$ is prime.  Again rename it~$p$.

A candidate prime above $10^{60}\cdot p$ of the form $p\cdot U+1$ is
\begin{align*}
N=p\cdot(10^{60}+1362)+1
=&10320032476724524106807794413885422\\
&468727478629339992494608926912518428\\
&801833472215991711945402406825893161\\
&06977763821434052434707.
\end{align*}
Again $b=2$ works in the LPL Criterion, so $N$ is prime.  Again rename it~$p$.

A candidate prime above $10^{120}\cdot p$ of the form $p\cdot U+1$ is
\begin{align*}
N=p\cdot(10^{120}+796)+1
=&10320032476724524106807794413885422\\
&468727478629339992494608926912518428\\
&801833472215991711945402406825893161\\
&069777638222555270198542721189019004\\
&353452796285107072988954634025708705\\
&822364669326259443883929402708540315\\
&83341095621154300001861505738026773.
\end{align*}
Again $b=2$ works in the LPL Criterion, so $N$ is prime.

\end{document}
