path: root/src/doc/primesp.spad.pamphlet

\documentclass{article}
\usepackage{../../src/scripts/tex/axiom}
\begin{document}
\title{\$SPAD/src/algebra primesp.spad}
\author{Manindra Agrawal, Neeraj Kayal and Nitin Saxena}
\maketitle
\begin{abstract}
We present a deterministic polynomial-time algorithm that determines
whether an input number $n$ is prime or composite.
\end{abstract}
\begin{quote}
{\sl
"The problem of distinguishing prime numbers from composite numbers and of
resolving the latter into their prime factors is known to be one of the most
important and useful in arithmetic. It has engaged the industry and wisdom
of ancient and modern geometers to such an extent that it should be 
superfluous to discuss the problem at length\ldots Further, the dignity of
the science itself seems to require that every possible means be explored
for the solution of a problem so elegant and so celebrated."}
\begin{flushright}
Karl Friedrich Gauss, {\sl Disquisitiones Arithmeticae}, 1801 (translated
from [Knu98])
\end{flushright}
\end{quote}
\eject
\tableofcontents
\eject
\section{Introduction}
Since ancient times, mathematicians have been fascinated by problems 
concerning prime numbers. One of the fundamental problems concerning prime
numbers is to determine if a given number is prime. In modern times, primality
testing has also become important from a practical perspective because of its
applications in cryptography.

Starting from ancient Chinese and Greek, many have worked on the problem of
finding an efficient algorithm for testing primality. The Sieve of 
Eratosthenes (ca. 240 BC) is the most ancient algorithm that works correctly
for all primes, however, its time complexity ($=\Omega{}(n)$ where $n$ is
input number) is exponential in the size of input. In 17th Century, Fermat
proved what is referred as {\sl Fermat's Little Theorem} stating that for
any prime number $p$, and any number $a$ not divisible by $p$,
$a^{p-1} = 1 (mod p)$. Although the converse of this theorem does not hold
(and in fact fails spectacularly for {\sl Carmichael numbers}, this result
has been the starting point for seeral efficient primality testing algorithms.
In 1976, Miller [Mil76] used this property to obtain a deterministic 
polynomial-time algorithm for primality testing assuming {\sl Extended
Riemann Hypothesis (ERH)}. His test was modified by Rabin [Rab80] to yield
an unconditional but randomized polynomial-time algorithm. Solovay and
Strassen [SS77] obtained another randomized polynomial-time algorithm using
quadratic residues. (Their algorithm can also be derandomized under ERH).
Since then, a number of randomized polynomial-time algorithms have been
proposed for primality testing.

In 1983, Adleman, Pomerance, and Rumely achieved a major breakthrough by
giving a deterministic algorithm for primality that runs in 
$(log n)^{O(log long log n)}$ time (all the previous deterministic
algorithms require exponential time). In 1986, Goldwasser and Killian [GK86] 
proposed a randomized algorithm based on Elliptic curves running in expected
polynomial-time on almost all inputs ({\sl all} inputs under a widely
believed hypothesis) that produces a certificate of primality (until then,
all randomized algorithms produced certificates for compositeness only). A
similar algorithm was developed by Atkin [Atk86]. Adelman and Huang [AH92]
modified Goldwasser-Killian algorithm to obtain a randomized polynomial-time
algorithm that always produced a certificate for primality.

The ultimate goal of this line of research is, of course, to obtain an 
unconditional deterministic polynomial-time algorithm for primality testing.
Despite the impressive progress made in primality testing so far, this goal
has remained elusive. In this paper, we achieve this. We give a deterministic,
$\Omega((log n)^{12})$ time algorithm for testing if a number is prime. 
Heuristically, our algorithm does much better: under a widely believed
conjecture on the density of Sophie Germain primes (primes $p$ such that
$2p+1$ is also prime), the algorithm takes only $\Omega((log n)^{6})$ 
steps. The correctness proof of our algorithm requires only simple tools
of algebra (except for appealing to a sieve theory result on the density
of primes $p$ with $p-1$ having a large prime factor). In contrast, the
correctness proofs of deterministic algorithms of [APR83, GK86, Atk86]
are much more complex.

In section 2, we summarize the basic idea behind our algorithm. In section
3, we state some preliminary theorems and fix the notation used here. 
Thereafter, we state the algorithm in full detail and present the proof
of correctness.

\section{Basic Idea and Approach}
Our test is based on the following identity for prime numbers.
This same identity was basis for a randomized polynomial-time algorithm
in [AB99]:
\vskip .1cm
\noindent
{\bf Identity} 
{\sl Suppose that a is coprime to p. Then p is prime if and only if}
$$(x-a)^p == (x^p - a)(mod\ p)\eqno{1}$$

\noindent
{\sl Proof}. For $0 < i < p$, the coefficient of $x^i$ in 
$((x-a)^p - (x^p - a))$ is $(-1)^i \left(p \over i\right) a^{p-i}$.
Now if $p$ is prime, $\left(p \over i\right) == 0(mod\ p)$
and hence all the coefficients are zero.

\noindent
If $p$ is composite: consider a prime $q$ that is a factor of $p$
and let $q^k \vert\vert p$. Then $q^k$ does not divide 
$\left(p \over q\right)$ and is coprime to $a^{p-q}$ and hence the 
coefficient of $x^q$ is not zero $(mod\ p)$. Thus
$((x-a)^p - (x^p - a))$ is not identically zero over $F_p$.

Thus given a $p$ as input, one could pick a polynomial $P(x) = x - a$
and compute whether the congruence (1) is not satisfied or not. However,
this takes time $\Omega(p)$ because we need to evaluate $p$ coefficients
in the LHS in the worst case. Therefore, to make it feasible we will 
evaluate both sides of (1) modulo a polynomial of the form $x^r - 1$.
One iteration of our algorithm will consist of evaluating whether the
following holds:
$$(x - a)^p == (x^p - a)(mod\ x^r - 1,p)\eqno{2}$$
\noindent
From the identity it is immediate that all primes $p$ satisfy the above
congruence for all values of $a$ and $r$; however some composites $p$ may
also satisfy (2) for a few values of $(a,r)$. The above congruence takes
$O(r^2\ log^3\ p)$ time for verification 
(lhs is evaluated by repeated squaring),
or even better $O(r\ log^2\ p)$ if Fast Fourier Multiplication [Knu98] is used.
Our algorithm first chooses a ``suitable'' $r$. (An $r$ is ``suitable''
for us if it is a prime=$O(log^6\ p)$ and $r-1$ contains a prime factor of
size at least $r^{({1 \over{2}} +\delta)}$, for some constant $\delta > 0$.
[Fou85, BH96] assures us that such a ``suitable'' $r$ exists.)
Thereafter, the algorithm verifies the congruence (2) for a ``small''
$( O(\sqrt{r}\ log\ p))$ number of $a$'s. We prove that this idea works:
i.e., the algorithm correctly determines whether $p$ is prime or not.
\section{Notation and Preliminaries}
This section states some algebraic and number theoretic results which we
will be using in the later proofs.

In the rest of the paper $F_{p^d}$ denotes the finite field, where $p$ is a
prime. Recall that if $p$ is a prime and $h(x)$ is a polynomial of degree
$d$ and irreducible in $F_p$, then $F_p[x]/(h(x))$ is a finite field of 
order $P^d$. In the rest of the paper h(x) will be a factor of
${{x^r-1}\over{x-1}}$ unless stated otherwise.

We will use the $O(t(n))$ for $O(t(n)poly(log\ t(n)))$, where $t(n)$ is some
function of $n$. Unless stated otherwise, log will be to base 2 in this
paper.

We now collect some simple facts from algebra that can be found in any
standard text, e.g. [LN86, Fra90]. We also prove some of these for the
sake of completeness.

\noindent
{\bf Lemma 3.1} 
{\sl Let p and r be prime numbers, $p \ne r$.}
\vskip .1cm
\begin{enumerate}
\item {\sl The multiplicative group of any field $F_{p^t}$ for $t > 0$, denoted
by $F_{p^t}^*$ is cyclic.}
\item {\sl Let $f(x)$ be a polynomial with integral coefficients. Then
$$f(x)^p == f(x^p)(mod\ p)$$}
\item {\sl Let h(x) be any factor of $x^r - 1$. Let $m == m_r(mod\ r)$. Then
$$x^m == x^{m_r}\ (mod\ h(x))$$}
\item {\sl Let $o_r(p)$ be the order of $p\ module\ r$. Then in 
$F_p$, ${{x^r - 1}\over{x-1}}$ factorises into irreducible polynomials
each of degree $o_r(p)$.}
\end{enumerate}
\vskip .2cm
\noindent
{\sl Proof}
\begin{enumerate}
\item See, e.g., [LN86]
\item Let $f(x) = a_0+a_1x+\ldots+a_dx^d$. The coefficient of $x^i$ in 
$f(x)^p$ is
$$\Sigma_{{i_0+\ldots+i_d=p}\over{i_1+2i_2+\ldots+di_d=i}}
a_0^{i_0} \dots a_d^{i_d} {{p!}\over{i_0! \dots i_d!}}$$
Note that this sum is divisible by $p$ unless one of the $i_j$'s is $p$.
In the latter case $i=pj$ and the coefficient of $x^i$ is
$a_j^p = a_j$. This gives us the required congruence.
\item Let $m=kr+m_r$. Now
\vskip .1cm
\begin{tabular}{llllll}
\ \ \ \ \ \ \ \ &     & $x^r$        & $==$ & $1$       & $(mod\ x^r - 1)$\\
\ \ \ \ \ \ \ \ &$=>$ & $x^{kr}$     & $==$ & $1$       & $(mod\ x^r - 1)$\\
\ \ \ \ \ \ \ \ &$=>$ & $x^{kr+m_r}$ & $==$ & $x^{m_r}$ & $(mod\ x^r - 1)$\\
\ \ \ \ \ \ \ \ &$=>$ & $x^m$        & $==$ & $x^{m_r}$ & $(mod\ h(x))$
\end{tabular}
\item Let $d = o_r(p)$ and $Q_r(x) = {{x^r-1}\over{x-1}}$.
Suppose that $Q_r(x)$ has an irreducible factor, $h(x)$ in $F_p$ of
degree $k$. Now $F_p[x]/h(x)$ forms a field of size $p^k$ and the 
multiplicative subgroup of $F_p[x]/h(x)$ is cyclic with a generator,
say $g(x)$. Also, in this galois field, by fact(2) above, we have
\vskip .1cm
\begin{tabular}{llllll}
\ \ \ \ \ \ \ \ &     & $g(x)^p$         & $==$ & $g(x^p)$\\
\ \ \ \ \ \ \ \ &$=>$ & $g(x)^{p^d}$     & $==$ & $g(x^{p^d})$\\
\ \ \ \ \ \ \ \ &$=>$ & $g(x)^{p^d}$     & $==$ & $g(x)$ [By fact (3) above]\\
\ \ \ \ \ \ \ \ &$=>$ & $g(x)^{{p^d}-1}$ & $==$ & $1$
\end{tabular}
\vskip .1cm
Since $(p^k - 1)$ is the order of $g(x)$, we get $(p^k - 1) \vert (p^d - 1)$
which implies that $k \vert d$. We also have that $h(x) \vert (x^r - 1)$ in
$F_p$ and therefore in the field $F_p[x]/h(x)$ we have
$$x^r == 1$$
Thus the order of $x$ in this field must be $r$ (since $r$ is prime and
$x !== 1$). Therefore $r \vert (p^k - 1)$, i.e. $p^k == 1 (mod\ r)$. Hence,
$d \vert k$. Therefore, $k = d$, and the lemma follows.
\end{enumerate}

In addition to the above algebraic facts, we will need the following two 
number theoretic facts.

\noindent
{\bf Lemma 3.2} {\sl [Fou85, BH96] Let $P(n)$ denote the greatest prime
divisor of $n$. There exist constants $c > 0$ and $n_0$ such that,
for all $x \ge n_0$}
$$\vert \{p \vert p\ is\ prime, p \le x\ and\ P(p-1) > x^{{2}\over{3}} \}
\vert \ge c{{x}\over{log\ x}}$$
The above lemma is, in fact, known to hold for exponents up to $0.6683$
(see [BH96] for a summary of results of this kind).
\noindent
{\bf Lemma 3.3}
{\sl [Apo97] Let $\pi(n)$ be the number of primes $\le n$. Then for $n \ge 1$:}
$${{n}\over{6\ log\ n}} \le \pi(n) \le {{8n}\over{log\ n}}$$
\eject
\section{The Algorithm}
\hrule
\vskip .1cm
Input: integer $n > 1$
\begin{enumerate}
\item if ($n$ is of the form $a^b$, $b>1$) output COMPOSITE;
\item $r = 2$;
\item while $(r < n)$ \{
\item \ \ \ \ if ($gcd(n,r) \ne 1$) output COMPOSITE;
\item \ \ \ \ if ($r$ is prime)
\item \ \ \ \ \ \ \ \ let $q$ be the largest prime factor of $r - 1$;
\item \ \ \ \ \ \ \ \ if ($q \ge 4\sqrt{r}\ log\ n$) and ($n^{{r-1}\over{q}} !== 1 (mod\ r)$)
\item \ \ \ \ \ \ \ \ \ \ \ \ break;
\item \ \ \ \ $r \leftarrow r + 1$;
\item \}
\item for $a = 1$ to $2\sqrt{r}\ log\ n$
\item \ \ \ \ if ($(x-a)^n !== (x^n - a)(mod\ x^r-1,n)$) output COMPOSITE;
\item output PRIME;
\end{enumerate}

\hrule
\vskip .3cm

\noindent
{\bf Theorem 4.1}
{\sl The algorithm above returns PRIME if and only if $n$ is prime}

In the remainder of the section, we establish this theorem through a 
sequence of lemmas. First note that the algorithm has two loops. The
first loop tries to find a prime $r$ such that $r-1$ has a large prime
factor $q \ge 4\sqrt{r}\ log\ n$, and that $q \vert o_r(n)$, where $o_r(n)$
is the order of $n\ modulo\ r$. Let us first bound the number of iterations
of the {\bf while} loop after which such an $r$ is found.

\vskip .2cm
\noindent
{\bf Lemma 4.2}
{\sl There exist positive constants $c_1$ and $c_2$ for which there is a
prime $r$ in the interval 
$[c_1 (log\ n)^6, c_2 (log\ n)^6]$ such that $r - 1$ has a prime factor
$q \ge 4 \sqrt{r}\ log\ n$ and $q \vert o_r(n)$.}

\vskip .2cm
\noindent
{\sl Proof}
Let $c$ and $P(n)$ be as given in Lemma 3.2. Thus, the number of prime
$r$'s (lets call them {\sl special} primes) between $c_1(log\ n)^6$ and
$c_2(log\ n)^6$ such that 
$P(r-1) > (c_2(log\ n)^6)^{{2}\over{3}} > r^{{2}\over{3}}$
is (for large enough $n$)
\vskip .1cm
\begin{tabular}{lll}
\ \ \ \ \ \ \ \ & $\ge$ & No of special primes in $[1\dots c_2(log\ n)^6]-$\\
                &       & No of primes in $[1\dots c_1(log\ n)^6]$\\
\ \ \ \ \ \ \ \ & $\ge$ & ${{cc_2(log\ n)^6}\over{7\ log\ log\ n}} - 
{{8c_1(log\ n)^6}\over{6\ log\ log\ n}}$ (using Lemma 3.3)\\
\ \ \ \ \ \ \ \ & $=$   & ${{(log\ n)^6}\over{log\ log\ n}}
\left({{cc_2}\over{7}} - {{8c_1}\over{6}}\right)$
\end{tabular}
\vskip .3cm

\noindent
Choose constants $c_1 \ge 4^6$ and $c_2$ so that the quantity in braces is a 
positive constant, say $c_3$.

Let $x=c_2(log\ n)^6$. Consider the product
$$\Pi = (n-1)(n^2-1)\dots(n^{x^{{1}\over{3}}} - 1)$$

\noindent
This product has at most $x^{{2}\over{3}}\ log\ n$ prime factors. Note that:
$$x^{{2}\over{3}}\ log\ n < {{c_3(log\ n)^6}\over{log\ log\ n}}$$

\noindent
Therefore, there is at least one special prime, say $r$, that does not 
divide the product $\Pi$

This is the required prime: $r-1$ has a large prime factor 
$q \ge r^{{2}\over{3}} \ge 4\sqrt{r}\ log\ n$ 
(since $c_1 \ge 4^6$), and $q \vert o_r(n)$.

Once we know that the {\bf while} loop halts, we are ready to show:

\vskip .3cm
\noindent
{\bf Lemma 4.3} {\sl If $n$ is prime, the algorithm returns PRIME}
\vskip .3cm
\noindent
{\sl Proof}. The {\bf while} loop cannot return COMPOSITE since
$gcd(n,r) = 1$ for all $r \le c_2(log\ n)^6$, where $c_2$ is as in
Lemma 4.2. By Lemma 3.1 (fact 2), the {\bf for} loop also cannot
return COMPOSITE. Thus, algorithm will identify $n$ as PRIME.

Now let us turn our attention to the case where a composite $n$ is input to
our algorithm. The significance of the $r$ found by the {\bf while} loop
arises when $n$ is composite with say $p_i$, $1 \le i \le k$, as its
prime factors. In this case, $o_r(n) \vert lcm_i\{o_r(p_i)\}$ and hence
there exists a prime factor $p$ of $n$ such that $q \vert o_r(p)$, where
$q$ is the largest prime factor of $r-1$. For the remainder of the argument,
let $p$ be such a prime factor of $n$.

The second loop of the algorithm uses the value of $r$ obtained to do
polynomial computations on $l = 2\sqrt{r}\ log\ n$ binomials:
$(x-a)$ for $1 \le n \le l$. By Lemma 3.1 (fact 4), we have a 
polynomial $h(x)$ (factor of $x^r - 1$) of degree $d = o_r(p)$
irreducible in $F_p$. Note that
$$(x-a)^n == (x^n - a)(mod\ x^r - 1,n)$$
implies that
$$(x-a)^n == (x^n - a)(mod\ h(x),p)$$
\vskip .2cm
\noindent
So the identities on each binomial hold in the field $F_p[x]/(h(x))$.
The set of {\sl l} binomials form a large cyclic group in this field:

\noindent
{\bf Lemma 4.4}
{\sl In the field $F_p[x]/(h(x))$, the group generated by the l
binomials: $(x-a)$,$1 \le a \le l$ i.e.,
$$G = \left\{\Pi_{1 \le a \le l} (x-a)^{\alpha_a} \vert \alpha_a \ge 0,
\forall 1 \le a \le l\right\}$$
is cyclic and of size $> \left({d}\over{l}\right)^l$

\noindent
{\sl Proof}
It is clear that $G$ is a group and sinze it is a subgroup of the cyclic
group $(F_p[x]/(h(x)))^*$, it is also cyclic.

Now consider the set
$$S=\left{\Pi_{1 \le a \le l} (x-a)^{\alpha_a} \vert 
\Sigma_{1 \le a \le l} \alpha_a \le d - 1, \alpha_a \ge 0, 
\forall{l} \le a \le l\right}$$

\noindent
The following argument shows that all the elements of $S$ are distinct in
$F_p[x]/(h(x)). The {\tt while} loop ensures that once it halts the final 
$r$ is such that $r > q > 4\sqrt(r)\ log\ n > l$. Also step 4 of the
algorithm checks {\tt gcd} of $r$ and $n$. If any of the $a$'s are
congruent modulo $p$, then $p < l < r$ and thus step 4 of the algorithm
identifies $n$ as composite. Thus, none of the $a$'s are congruent module
$p$. So any two elements of $S$ are distinct module $p$. This implies that 
all of the elements of $S$ are distinct in the field $F_p[x]/(h(x)) since
degree of any element of $S$ is less thatn $d$ -- the degree of h(x).

The crdinality of the set $S$ is:
\begin{tabular}{lll}
$$\left({l + d - 1}\over{l}\right)$$ & $=$ & 
$${l + d - 1)(l + d - 2)\dots(d)}\over{l!}$$\\
& $$\left({d}\over{l}\right)^l$$
\end{tabular}

\noindent
Since $S$ is just a subset of $G$ we get the result.

Since $d \ge 2l$, size of $G$ is $> 2^l = n^{2\sqrt{r}}$. Let $g(x)$ be a
generator of $G$. Clearly, order of $g(x)$ in $F_p[x]/(h(x))$ is 
$> n^{2\sqrt{r}}$. We now define a set related to $g(x)$ which will play an
important role in the remaining arguments. Let
$$I_{g(x)} = \{m \vert g(x)^m \ident g(x^m)(mod\ x^r - 1,p)\}$$

Here is a nice property of $I_{g(x)}$:

\section{package PRIMESP PrimesIsInP}
<<package PRIMESP PrimesIsInP>>=
)abbrev package PRIMESP PrimesIsInP
++ Author: Tim Daly
++ Date Created: Nov 29, 2003
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A deterministic polynomial-time algorith that determines whether an
++ input number is prime or composite
++
AbelianGroup(): Category == CancellationAbelianMonoid with
    --operations
      "-": % -> %                      ++ -x is the additive inverse of x.
      "-": (%,%) -> %                  ++ x-y is the difference of x and y
                                       ++ i.e. \spad{x + (-y)}.
                       -- subsumes the partial subtraction from previous
      "*": (Integer,%) -> %            ++ n*x is the product of x by the integer n.
    add
      (x:% - y:%):% == x+(-y)
      subtractIfCan(x:%, y:%):Union(%, "failed") == (x-y) :: Union(%,"failed")
      n:NonNegativeInteger * x:% == (n::Integer) * x
      import RepeatedDoubling(%)
      if not (% has Ring) then
        n:Integer * x:% ==
          zero? n => 0
          n>0 => double(n pretend PositiveInteger,x)
          double((-n) pretend PositiveInteger,-x)

@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}