American Institute of Mathematical Sciences

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

Some remarks on primality proving and elliptic curves

Alice Silverberg 1,

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$.
Keywords: elliptic curves, complex multiplication., Primality.
Mathematics Subject Classification: Primary: 11Y11; Secondary: 11G05, 14K2.
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]

Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533
[2]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024
[3]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[4]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044
[5]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196
[6]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (41)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences