Initial population.

1 files changed, 420 insertions, 0 deletions

diff --git a/src/doc/primesp.spad.pamphlet b/src/doc/primesp.spad.pamphlet
new file mode 100644
index 00000000..be630969
--- /dev/null
+++ b/src/doc/primesp.spad.pamphlet
@@ -0,0 +1,420 @@
+\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}