American Institute of Mathematical Sciences

November  2014, 8(4): 427-436. doi: 10.3934/amc.2014.8.427

Some remarks on primality proving and elliptic curves

 1 Department of Mathematics, University of California, Irvine, Irvine, CA 92697-3875, United States

Received  January 2014 Published  November 2014

We give an overview of a method for using elliptic curves with complex multiplication to give efficient deterministic polynomial time primality tests for the integers in sequences of a special form. This technique has been used to find the largest proven primes $N$ for which there was no known significant partial factorization of $N-1$ or $N+1$.
Citation: Alice Silverberg. Some remarks on primality proving and elliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 427-436. doi: 10.3934/amc.2014.8.427
References:
 [1] A. Abatzoglou, A CM elliptic curve framework for deterministic primality proving on numbers of special form,, Ph.D thesis, (2014). Google Scholar [2] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at, , (). Google Scholar [3] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at, , (). Google Scholar [4] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, Deterministic elliptic curve primality proving for a special sequence of numbers,, in Algorithmic Number Theory, (2013), 1. doi: 10.2140/obs.2013.1.1. Google Scholar [5] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, A framework for deterministic primality proving using elliptic curves with complex multiplication,, Math. Comp., (). Google Scholar [6] M. Agrawal, N. Kayal and N. Saxena, Primes is in P,, Ann. Math., 160 (2004), 781. doi: 10.4007/annals.2004.160.781. Google Scholar [7] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving,, Math. Comp., 61 (1993), 29. doi: 10.1090/S0025-5718-1993-1199989-X. Google Scholar [8] W. Bosma, Primality Testing with Elliptic Curves,, Doctoraalscriptie Report, (1985), 85. Google Scholar [9] D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests,, Adv. Appl. Math., 7 (1986), 385. doi: 10.1016/0196-8858(86)90023-0. Google Scholar [10] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Second edition,, Springer, (2005). Google Scholar [11] R. Denomme and G. Savin, Elliptic curve primality tests for Fermat and related primes,, J. Number Theory, 128 (2008), 2398. doi: 10.1016/j.jnt.2007.12.009. Google Scholar [12] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified,, in STOC '86 - Proc. 18th Annual ACM Symp. Theory Computing, (1986), 316. doi: 10.1145/12130.12162. Google Scholar [13] S. Goldwasser and J. Kilian, Primality testing using elliptic curves,, J. ACM, 46 (1999), 450. doi: 10.1145/320211.320213. Google Scholar [14] D. M. Gordon, Pseudoprimes on elliptic curves,, in Théorie des nombres, (1989), 290. Google Scholar [15] B. H. Gross, Arithmetic on Elliptic Curves with Complex Multiplication,, Springer, (1980). Google Scholar [16] B. H. Gross, Minimal models for elliptic curves with complex multiplication,, Compositio Math., 45 (1982), 155. Google Scholar [17] B. H. Gross, An elliptic curve test for Mersenne primes,, J. Number Theory, 110 (2005), 114. doi: 10.1016/j.jnt.2003.11.011. Google Scholar [18] A. Gurevich and B. Kunyavskiĭ, Primality testing through algebraic groups,, Arch. Math. (Basel), 93 (2009), 555. doi: 10.1007/s00013-009-0065-9. Google Scholar [19] A. Gurevich and B. Kunyavskiĭ, Deterministic primality tests based on tori and elliptic curves,, Finite Fields Appl., 18 (2012), 222. doi: 10.1016/j.ffa.2011.07.011. Google Scholar [20] M. Kida, Primality tests using algebraic groups,, Exper. Math., 13 (2004), 421. doi: 10.1080/10586458.2004.10504550. Google Scholar [21] H. W. Lenstra, Jr., Elliptic curves and number-theoretic algorithms,, in Proc. Int. Congr. Math., (1987), 99. Google Scholar [22] H. W. Lenstra, Jr., Factoring integers with elliptic curves,, Ann. Math., 126 (1987), 649. doi: 10.2307/1971363. Google Scholar [23] H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods,, available online at , (2011). Google Scholar [24] C. Pomerance, Primality testing: variations on a theme of Lucas,, Congr. Numer., 201 (2010), 301. Google Scholar [25] K. Rubin and A. Silverberg, Point counting on reductions of CM elliptic curves,, J. Number Theory, 129 (2009), 2903. doi: 10.1016/j.jnt.2009.01.020. Google Scholar [26] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$,, Math. Comp., 44 (1985), 483. doi: 10.2307/2007968. Google Scholar [27] A. Silverberg, Group order formulas for reductions of CM elliptic curves,, in Proc. Conf. Arith. Geom. Crypt. Coding Theory, (2010), 107. doi: 10.1090/conm/521/10277. Google Scholar [28] H. Stark, Counting points on CM elliptic curves,, Rocky Mountain J. Math., 26 (1996), 1115. doi: 10.1216/rmjm/1181072041. Google Scholar [29] Y. Tsumura, Primality tests for $2^p + 2^{\frac{p+1}{2}} + 1$ using elliptic curves,, Proc. Amer. Math. Soc., 139 (2011), 2697. doi: 10.1090/S0002-9939-2011-10839-6. Google Scholar [30] A. Wong, Primality Test Using Elliptic Curves with Complex Multiplication by $\mathbbQ(\sqrt{-7})$,, Ph.D thesis, (2013). Google Scholar

show all references

References:
 [1] A. Abatzoglou, A CM elliptic curve framework for deterministic primality proving on numbers of special form,, Ph.D thesis, (2014). Google Scholar [2] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at, , (). Google Scholar [3] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at, , (). Google Scholar [4] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, Deterministic elliptic curve primality proving for a special sequence of numbers,, in Algorithmic Number Theory, (2013), 1. doi: 10.2140/obs.2013.1.1. Google Scholar [5] A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, A framework for deterministic primality proving using elliptic curves with complex multiplication,, Math. Comp., (). Google Scholar [6] M. Agrawal, N. Kayal and N. Saxena, Primes is in P,, Ann. Math., 160 (2004), 781. doi: 10.4007/annals.2004.160.781. Google Scholar [7] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving,, Math. Comp., 61 (1993), 29. doi: 10.1090/S0025-5718-1993-1199989-X. Google Scholar [8] W. Bosma, Primality Testing with Elliptic Curves,, Doctoraalscriptie Report, (1985), 85. Google Scholar [9] D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests,, Adv. Appl. Math., 7 (1986), 385. doi: 10.1016/0196-8858(86)90023-0. Google Scholar [10] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Second edition,, Springer, (2005). Google Scholar [11] R. Denomme and G. Savin, Elliptic curve primality tests for Fermat and related primes,, J. Number Theory, 128 (2008), 2398. doi: 10.1016/j.jnt.2007.12.009. Google Scholar [12] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified,, in STOC '86 - Proc. 18th Annual ACM Symp. Theory Computing, (1986), 316. doi: 10.1145/12130.12162. Google Scholar [13] S. Goldwasser and J. Kilian, Primality testing using elliptic curves,, J. ACM, 46 (1999), 450. doi: 10.1145/320211.320213. Google Scholar [14] D. M. Gordon, Pseudoprimes on elliptic curves,, in Théorie des nombres, (1989), 290. Google Scholar [15] B. H. Gross, Arithmetic on Elliptic Curves with Complex Multiplication,, Springer, (1980). Google Scholar [16] B. H. Gross, Minimal models for elliptic curves with complex multiplication,, Compositio Math., 45 (1982), 155. Google Scholar [17] B. H. Gross, An elliptic curve test for Mersenne primes,, J. Number Theory, 110 (2005), 114. doi: 10.1016/j.jnt.2003.11.011. Google Scholar [18] A. Gurevich and B. Kunyavskiĭ, Primality testing through algebraic groups,, Arch. Math. (Basel), 93 (2009), 555. doi: 10.1007/s00013-009-0065-9. Google Scholar [19] A. Gurevich and B. Kunyavskiĭ, Deterministic primality tests based on tori and elliptic curves,, Finite Fields Appl., 18 (2012), 222. doi: 10.1016/j.ffa.2011.07.011. Google Scholar [20] M. Kida, Primality tests using algebraic groups,, Exper. Math., 13 (2004), 421. doi: 10.1080/10586458.2004.10504550. Google Scholar [21] H. W. Lenstra, Jr., Elliptic curves and number-theoretic algorithms,, in Proc. Int. Congr. Math., (1987), 99. Google Scholar [22] H. W. Lenstra, Jr., Factoring integers with elliptic curves,, Ann. Math., 126 (1987), 649. doi: 10.2307/1971363. Google Scholar [23] H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods,, available online at , (2011). Google Scholar [24] C. Pomerance, Primality testing: variations on a theme of Lucas,, Congr. Numer., 201 (2010), 301. Google Scholar [25] K. Rubin and A. Silverberg, Point counting on reductions of CM elliptic curves,, J. Number Theory, 129 (2009), 2903. doi: 10.1016/j.jnt.2009.01.020. Google Scholar [26] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$,, Math. Comp., 44 (1985), 483. doi: 10.2307/2007968. Google Scholar [27] A. Silverberg, Group order formulas for reductions of CM elliptic curves,, in Proc. Conf. Arith. Geom. Crypt. Coding Theory, (2010), 107. doi: 10.1090/conm/521/10277. Google Scholar [28] H. Stark, Counting points on CM elliptic curves,, Rocky Mountain J. Math., 26 (1996), 1115. doi: 10.1216/rmjm/1181072041. Google Scholar [29] Y. Tsumura, Primality tests for $2^p + 2^{\frac{p+1}{2}} + 1$ using elliptic curves,, Proc. Amer. Math. Soc., 139 (2011), 2697. doi: 10.1090/S0002-9939-2011-10839-6. Google Scholar [30] A. Wong, Primality Test Using Elliptic Curves with Complex Multiplication by $\mathbbQ(\sqrt{-7})$,, Ph.D thesis, (2013). Google Scholar
 [1] Michael J. Jacobson, Jr., Monireh Rezai Rad, Renate Scheidler. Comparison of scalar multiplication on real hyperelliptic curves. Advances in Mathematics of Communications, 2014, 8 (4) : 389-406. doi: 10.3934/amc.2014.8.389 [2] Philip N. J. Eagle, Steven D. Galbraith, John B. Ong. Point compression for Koblitz elliptic curves. Advances in Mathematics of Communications, 2011, 5 (1) : 1-10. doi: 10.3934/amc.2011.5.1 [3] David L. Finn. Convexity of level curves for solutions to semilinear elliptic equations. Communications on Pure & Applied Analysis, 2008, 7 (6) : 1335-1343. doi: 10.3934/cpaa.2008.7.1335 [4] Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101 [5] Ravi Vakil and Aleksey Zinger. A natural smooth compactification of the space of elliptic curves in projective space. Electronic Research Announcements, 2007, 13: 53-59. [6] Wei Sun. On uniform estimate of complex elliptic equations on closed Hermitian manifolds. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1553-1570. doi: 10.3934/cpaa.2017074 [7] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215 [8] Bertrand Lods. Variational characterizations of the effective multiplication factor of a nuclear reactor core. Kinetic & Related Models, 2009, 2 (2) : 307-331. doi: 10.3934/krm.2009.2.307 [9] Gian-Italo Bischi, Laura Gardini, Fabio Tramontana. Bifurcation curves in discontinuous maps. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 249-267. doi: 10.3934/dcdsb.2010.13.249 [10] Stefano Marò. Relativistic pendulum and invariant curves. Discrete & Continuous Dynamical Systems - A, 2015, 35 (3) : 1139-1162. doi: 10.3934/dcds.2015.35.1139 [11] Carlos Munuera, Alonso Sepúlveda, Fernando Torres. Castle curves and codes. Advances in Mathematics of Communications, 2009, 3 (4) : 399-408. doi: 10.3934/amc.2009.3.399 [12] Vladimir Georgiev, Eugene Stepanov. Metric cycles, curves and solenoids. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1443-1463. doi: 10.3934/dcds.2014.34.1443 [13] Martin Möller. Shimura and Teichmüller curves. Journal of Modern Dynamics, 2011, 5 (1) : 1-32. doi: 10.3934/jmd.2011.5.1 [14] Nicholas Hoell, Guillaume Bal. Ray transforms on a conformal class of curves. Inverse Problems & Imaging, 2014, 8 (1) : 103-125. doi: 10.3934/ipi.2014.8.103 [15] M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197 [16] Philip Korman. Curves of equiharmonic solutions, and problems at resonance. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2847-2860. doi: 10.3934/dcds.2014.34.2847 [17] Adrian Tudorascu. On absolutely continuous curves of probabilities on the line. Discrete & Continuous Dynamical Systems - A, 2019, 39 (9) : 5105-5124. doi: 10.3934/dcds.2019207 [18] El Houcein El Abdalaoui, Sylvain Bonnot, Ali Messaoudi, Olivier Sester. On the Fibonacci complex dynamical systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2449-2471. doi: 10.3934/dcds.2016.36.2449 [19] Jonathan P. Desi, Evelyn Sander, Thomas Wanner. Complex transient patterns on the disk. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1049-1078. doi: 10.3934/dcds.2006.15.1049 [20] David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161.

2018 Impact Factor: 0.879