\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} <>= )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}