The Lucas-Pratt primality tree
HTML articles powered by AMS MathViewer
- by Jonathan Bayless PDF
- Math. Comp. 77 (2008), 495-502 Request permission
Abstract:
In 1876, E. Lucas showed that a quick proof of primality for a prime $p$ could be attained through the prime factorization of $p-1$ and a primitive root for $p$. V. Pratt’s proof that PRIMES is in NP, done via Lucas’s theorem, showed that a certificate of primality for a prime $p$ could be obtained in $O(\log ^2 p)$ modular multiplications with integers at most $p$. We show that for all constants $C \in \mathbb {R}$, the number of modular multiplications necessary to obtain this certificate is greater than $C \log p$ for a set of primes $p$ with relative asymptotic density 1.References
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
- W. Banks and I. Shparlinski, On values taken by the largest prime factor of shifted primes, Journal of the Australian Mathematical Society, 82 (2007), 133–147.
- Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
- P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 165–204. MR 1084181, DOI 10.1007/978-1-4612-3464-7_{1}3
- Richard R. Hall and Gérald Tenenbaum, Divisors, Cambridge Tracts in Mathematics, vol. 90, Cambridge University Press, Cambridge, 1988. MR 964687, DOI 10.1017/CBO9780511566004
- G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
- F. Luca and C. Pomerance, Irreducible radical extensions and Euler-function chains, Integers, to appear, (Available at http://math.dartmouth.edu/$\sim$carlp/PDF/radicalpaper5.pdf).
- E. Lucas, Considérations nouvelles sur la théorie des nombres premiers et sur la division géométrique de la circonférence en parties égales, Association Française pour l’Avancement des Sciences, Comptes Rendus, 6 (1877), 159-167.
- H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134. MR 374060, DOI 10.1112/S0025579300004708
- Carl Pomerance, Very short primality proofs, Math. Comp. 48 (1987), no. 177, 315–322. MR 866117, DOI 10.1090/S0025-5718-1987-0866117-4
- Vaughan R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), no. 3, 214–220. MR 391574, DOI 10.1137/0204018
Additional Information
- Jonathan Bayless
- Affiliation: Department of Mathematics, Dartmouth College, Hanover, New Hamphshire 03755-3551
- MR Author ID: 769072
- Email: jonathan.bayless@dartmouth.edu
- Received by editor(s): June 26, 2006
- Received by editor(s) in revised form: November 14, 2006
- Published electronically: May 14, 2007
- Additional Notes: The author was supported by a Dartmouth Graduate Fellowship
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 495-502
- MSC (2000): Primary 11Y16; Secondary 11N37
- DOI: https://doi.org/10.1090/S0025-5718-07-02002-9
- MathSciNet review: 2353963