From: Gerry Myerson Subject: Re: ARCL Date: Wed, 26 Jul 2000 09:18:04 +1000 Newsgroups: sci.math.research Summary: [missing] In article <8lkbn8$lg0$1@pegasus.tiscalinet.it>, "The_Mandelbrot_Set" wrote: > Does anyone knows as the ARCL test for prime numbers works?? Maybe you mean APRCL, Adleman-Pomerance-Rumely-Cohen-Lenstra. There's a brief discussion in Riesel, Prime Numbers and Computer Methods for Factorization. You may also find these papers (with their reviews from Math Reviews) useful. Mih\u ailescu, Preda(CH-ETHZ-CP) Cyclotomy primality proving---recent developments. (English. English summary) Algorithmic number theory (Portland, OR, 1998), 95--110, Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998. Currently, the only two practical algorithms for proving primality of general large primes use either cyclotomy or elliptic curves. Algorithms using cyclotomy are exemplified by the article of L. M. Adleman, C. Pomerance and R. S. Rumely [Ann. of Math. (2) 117 (1983), no. 1, 173--206; MR 84e:10008]. The paper of S. Goldwasser and J. Kilian [in Proceedings of the Eighteenth Annual ACM Symposium on Theory of computing (Berkeley, CA, 1986), 316--329, ACM, New York, 1986] illustrates the elliptic curve algorithms. The cyclotomy algorithms have superpolynomial run time and lost favor with the invention of practical elliptic curve algorithms by A. O. L. Atkin and F. Morain [Math. Comp. 61 (1993), no. 203, 29--68; MR 93m:11136]. The elliptic curve algorithms run in polynomial time, but they are only moderately fast because the polynomial has degree six. The author reprises the cyclotomy algorithms and proposes a variation of the Jacobi sum test of H. Cohen and H. W. Lenstra, Jr. [Math. Comp. 42 (1984), no. 165, 297--330; MR 86g:11078]. Although the new algorithm does not run in polynomial time, it is faster than the elliptic curve methods, at least for numbers with no more than a few thousand digits. For example, the author proved the primality of $(2\sp {11279}+1)/3$, a number of 3395 decimal digits, in only six days on a workstation. \{For the entire collection see MR 2000g:11002.\} Reviewed by Samuel S. Wagstaff, Jr. 92g:11123 11Y11 (11A51) Lenstra, Arjen K.(1-BELL6) Primality testing. Cryptology and computational number theory (Boulder, CO, 1989), 13--25, Proc. Sympos. Appl. Math., 42, Amer. Math. Soc., Providence, RI, 1990. In this expository paper algorithms to prove the primality of integers are discussed. It is rather easy to establish whether a given integer $n$ is probably prime or not. To find a rigorous proof within a reasonable time is more difficult. The author discusses the two most efficient algorithms known: the Jacobi sum test, due to L. M. Adleman, C. Pomerance and R. S. Rumely [Ann. of Math. (2) 117 (1983), no. 1, 173--206; MR 84e:10008], and the complex multiplication test due to Atkin. At present there are implementations of these algorithms that can handle one-thousand-digit numbers. The key observation, due to H. W. Lenstra, that $n$ is a prime number if and only if all its divisors are powers of $n$, is behind the Jacobi sum test. Certain calculations with Jacobi sums in rings of cyclotomic integers of moderately low degree give the information that all divisors of $n$ are powers of $n$ in rings of the type ${Z}/s{Z}$. When $s$ is sufficiently large, this information can be used to prove that $n$ is prime. The running time of this algorithm is bounded by $O(\log n\sp {{\rm log\,log\,log\,}n})$. The multiplicative group ${G}\sb m({Z}/n{Z})=({Z}/n{Z})\sp *$ can only contain elements of order $d$ dividing $n-1$ with $d$ large, when $n$ is prime. This observation is due to H. C. Pocklington [Proc. Cambridge Philos. Soc. 18 (1914), 29--30; Jbuch 45, 1250]. It is a basic step in Atkin's complex multiplication test. Here the multiplicative group ${G}\sb m$ is replaced by several other algebraic groups, viz. by elliptic curves $E$ with complex multiplication by quadratic orders with relatively small discriminant. The running time of this algorithm is difficult to estimate. Heuristically it is polynomial in $\log n$. Finally the author mentions the work of Adleman and M. A. Huang ["Recognizing primes in random polynomial time", Res. Rep., Dept. Comput. Sci. Univ. Southern California, Los Angeles, CA, 1988; per bibl.]. They constructed a random polynomial time primality test based on Pocklington's theorem, but besides elliptic curves, they employed abelian varieties of dimension 2. \{For the entire collection see MR 91k:11113\}. Reviewed by Rene Schoof 88d:11003 11A51 (11Y11) Guthmann, Andreas(D-KSRL) Primzahltests und Pseudoprimzahlen. (German. English summary) [Tests for primality and pseudoprimes] Diskrete Strukturen, algebraische Methoden und Anwendungen (Bayreuth, 1985). Bayreuth. Math. Schr. No. 21, (1986), 101--116. This paper provides a fairly detailed survey at a relatively elementary level of "primality tests", emphasising that in the first instance such tests detect a wider class of integers, to wit, "pseudoprimes"---that is, primes and those composite integers which the test cannot distinguish from primes. There is an extensive bibliography. The article concludes with an instructive discussion of the Adleman-Pomerance-Rumely-Cohen-Lenstra primality test. Reviewed by A. J. van der Poorten Gerry Myerson (gerry@mpce.mq.edu.au) ============================================================================== From: Fred W. Helenius Subject: Re: ARCL Date: Wed, 26 Jul 2000 07:34:34 -0400 Newsgroups: sci.math "The_Mandelbrot_Set" wrote: >Does anyone knows as the ARCL test for prime numbers works?? >I now it is based on the Fermat theorem, and I would learn >something else... Assuming you mean the APR-CL test (the Adleman-Pomerance-Rumely test as improved by Cohen and Lenstra), it involves some fairly advanced results from algebraic number theory. Essentially, it extends the ideas behind the classical n-1 (Pocklington, Proth, Pepin) and n+1 (Lucas-Lehmer) tests to more general polynomials by utilizing generalized reciprocity laws (or Gauss sums in the Cohen-Lenstra version). There's a short but useful overview at http://www.utm.edu/research/primes/prove/prove4.html#apr , with references to the original articles describing the tests. -- Fred W. Helenius