A framework for deterministic primality proving using elliptic curves with complex multiplication
HTML articles powered by AMS MathViewer
- by Alexander Abatzoglou, Alice Silverberg, Andrew V. Sutherland and Angela Wong PDF
- Math. Comp. 85 (2016), 1461-1483 Request permission
Abstract:
We provide a framework for using elliptic curves with complex multiplication to determine the primality or compositeness of integers that lie in special sequences, in deterministic quasi-quadratic time. We use this to find large primes, including the largest prime currently known whose primality cannot feasibly be proved using classical methods.References
- A. Abatzoglou, A CM elliptic curve framework for deterministic primality testing on numbers of special form, University of California at Irvine PhD thesis, 2014.
- Alexander Abatzoglou, Alice Silverberg, Andrew V. Sutherland, and Angela Wong, Deterministic elliptic curve primality proving for a special sequence of numbers, ANTS X—Proceedings of the Tenth Algorithmic Number Theory Symposium, Open Book Ser., vol. 1, Math. Sci. Publ., Berkeley, CA, 2013, pp. 1–20. MR 3207405, DOI 10.2140/obs.2013.1.1
- 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
- A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
- W. Bosma, Primality testing with elliptic curves, Doctoraalscriptie Report 85–12, Department of Mathematics, University of Amsterdam, 1985, http://www.math.ru.nl/~bosma/pubs/PRITwEC1985.pdf.
- D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), no. 4, 385–434. MR 866702, DOI 10.1016/0196-8858(86)90023-0
- Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
- Robert Denomme and Gordan Savin, Elliptic curve primality tests for Fermat and related primes, J. Number Theory 128 (2008), no. 8, 2398–2412. MR 2394827, DOI 10.1016/j.jnt.2007.12.009
- J. Franke, T. Kleinjung, A. Decker, A. Großwendt, Format of the certificate (Version 0.1), available at http://www.math.uni-bonn.de/people/franke/ptest/fmt-0.1.pdf.
- Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
- S. Goldwasser, J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC, Berkeley (California) (1986), 316–329.
- Shafi Goldwasser and Joe Kilian, Primality testing using elliptic curves, J. ACM 46 (1999), no. 4, 450–472. MR 1812127, DOI 10.1145/320211.320213
- Daniel M. Gordon, Pseudoprimes on elliptic curves, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290–305. MR 1024570
- Benedict H. Gross, An elliptic curve test for Mersenne primes, J. Number Theory 110 (2005), no. 1, 114–119. MR 2114676, DOI 10.1016/j.jnt.2003.11.011
- Alexander Gurevich and Boris Kunyavskiĭ, Primality testing through algebraic groups, Arch. Math. (Basel) 93 (2009), no. 6, 555–564. MR 2574789, DOI 10.1007/s00013-009-0065-9
- Alexander Gurevich and Boris Kunyavskiĭ, Deterministic primality tests based on tori and elliptic curves, Finite Fields Appl. 18 (2012), no. 1, 222–236. MR 2874918, DOI 10.1016/j.ffa.2011.07.011
- D. Harvey, J. van der Hoeven, G. Lecerf, Even faster integer multiplication, preprint available at http://arxiv.org/abs/1407.3360, 2014.
- Masanari Kida, Primality tests using algebraic groups, Experiment. Math. 13 (2004), no. 4, 421–427. MR 2118266
- Franz Lemmermeyer, Reciprocity laws, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2000. From Euler to Eisenstein. MR 1761696, DOI 10.1007/978-3-662-12893-0
- F. Lemmermeyer, Reciprocity Laws: From Kummer to Hilbert, Chapter 12: Quadratic Reciprocity in Number Fields (Nov. 19, 2005), http://www.fen.bilkent.edu.tr/~franz/rl2/rlb12.pdf.
- H. W. Lenstra Jr., Elliptic curves and number-theoretic algorithms, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 99–120. MR 934218
- H. W. Lenstra Jr., Carl Pomerance, Primality testing with Gaussian periods, preprint available at http://www.math.dartmouth.edu/~carlp/aks041411.pdf, 2011.
- P. Mihailescu, Dual elliptic primes and applications to cyclotomy primality proving, preprint available at http://arxiv.org/abs/0709.4113, 2007.
- F. Morain, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm, Math. Comp. 76 (2007), no. 257, 493–505. MR 2261033, DOI 10.1090/S0025-5718-06-01890-4
- Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- Carl Pomerance, Very short primality proofs, Math. Comp. 48 (1987), no. 177, 315–322. MR 866117, DOI 10.1090/S0025-5718-1987-0866117-4
- Carl Pomerance, Primality testing: variations on a theme of Lucas, Congr. Numer. 201 (2010), 301–312. MR 2598366
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
- K. Rubin and A. Silverberg, Point counting on reductions of CM elliptic curves, J. Number Theory 129 (2009), no. 12, 2903–2923. MR 2560842, DOI 10.1016/j.jnt.2009.01.020
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- J.-P. Serre, A course in arithmetic, Graduate Texts in Mathematics, No. 7, Springer-Verlag, New York-Heidelberg, 1973. Translated from the French. MR 0344216
- Jean-Pierre Serre, Local fields, Graduate Texts in Mathematics, vol. 67, Springer-Verlag, New York-Berlin, 1979. Translated from the French by Marvin Jay Greenberg. MR 554237
- Goro Shimura, Introduction to the arithmetic theory of automorphic functions, Publications of the Mathematical Society of Japan, vol. 11, Princeton University Press, Princeton, NJ, 1994. Reprint of the 1971 original; Kanô Memorial Lectures, 1. MR 1291394
- Joseph H. Silverman, The arithmetic of elliptic curves, 2nd ed., Graduate Texts in Mathematics, vol. 106, Springer, Dordrecht, 2009. MR 2514094, DOI 10.1007/978-0-387-09494-6
- Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368, DOI 10.1007/978-1-4612-0851-8
- N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org, 2010.
- H. M. Stark, Counting points on CM elliptic curves, Rocky Mountain J. Math. 26 (1996), no. 3, 1115–1138. Symposium on Diophantine Problems (Boulder, CO, 1994). MR 1428490, DOI 10.1216/rmjm/1181072041
- W. A. Stein et al., Sage Mathematics Software (Version 4.7.1), The Sage Development Team, 2011, http://www.sagemath.org.
- Yu Tsumura, Primality tests for $2^p\pm 2^{(p+1)/2}+1$ using elliptic curves, Proc. Amer. Math. Soc. 139 (2011), no. 8, 2697–2703. MR 2801608, DOI 10.1090/S0002-9939-2011-10839-6
- Angela Wong, Primality test using elliptic curves with complex multiplication by Q-7, ProQuest LLC, Ann Arbor, MI, 2013. Thesis (Ph.D.)–University of California, Irvine. MR 3167301
Additional Information
- Alexander Abatzoglou
- Affiliation: Department of Mathematics, University of California, Irvine, California 92697
- Email: aabatzog@math.uci.edu
- Alice Silverberg
- Affiliation: Department of Mathematics, University of California, Irvine, California 92697
- MR Author ID: 213982
- Email: asilverb@math.uci.edu
- Andrew V. Sutherland
- Affiliation: Department of Mathematics, MIT, Cambridge, Massachusetts 02139
- MR Author ID: 852273
- ORCID: 0000-0001-7739-2792
- Email: drew@math.mit.edu
- Angela Wong
- Affiliation: Department of Mathematics, University of California, Irvine, California 92697
- Email: awong@math.uci.edu
- Received by editor(s): March 31, 2014
- Received by editor(s) in revised form: October 11, 2014
- Published electronically: July 20, 2015
- Additional Notes: This work was supported by the National Science Foundation under grants CNS-0831004 and DMS-1115455.
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 1461-1483
- MSC (2010): Primary 11Y11; Secondary 11G05, 14K22, 11A51
- DOI: https://doi.org/10.1090/mcom/3001
- MathSciNet review: 3454371