Some remarks on primality proving and elliptic curves

Previous Article
The geometry of some parameterizations and encodings
AMC Home
This Issue
Next Article
Subexponential time relations in the class group of large degree number fields

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

Abstract
Related Papers

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, University of California at Irvine, 2014.
[2]	A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at http://primes.utm.edu/primes/page.php?id=106847
[3]	A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at http://primes.utm.edu/primes/page.php?id=117544
[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, Math. Sci. Publ., 2013, 1-20. doi: 10.2140/obs.2013.1.1.
[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., to appear.
[6]	M. Agrawal, N. Kayal and N. Saxena, Primes is in P, Ann. Math., 160 (2004), 781-793. doi: 10.4007/annals.2004.160.781.
[7]	A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp., 61 (1993), 29-68. doi: 10.1090/S0025-5718-1993-1199989-X.
[8]	W. Bosma, Primality Testing with Elliptic Curves, Doctoraalscriptie Report, University of Amsterdam 85-12, 1985, available online at http://www.math.ru.nl/ bosma/pubs/PRITwEC1985.pdf
[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-434. doi: 10.1016/0196-8858(86)90023-0.
[10]	R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Second edition, Springer, New York, 2005.
[11]	R. Denomme and G. Savin, Elliptic curve primality tests for Fermat and related primes, J. Number Theory, 128 (2008), 2398-2412. doi: 10.1016/j.jnt.2007.12.009.
[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-329. doi: 10.1145/12130.12162.
[13]	S. Goldwasser and J. Kilian, Primality testing using elliptic curves, J. ACM, 46 (1999), 450-472. doi: 10.1145/320211.320213.
[14]	D. M. Gordon, Pseudoprimes on elliptic curves, in Théorie des nombres, de Gruyter, Berlin, 1989, 290-305.
[15]	B. H. Gross, Arithmetic on Elliptic Curves with Complex Multiplication, Springer, Berlin, 1980.
[16]	B. H. Gross, Minimal models for elliptic curves with complex multiplication, Compositio Math., 45 (1982), 155-164.
[17]	B. H. Gross, An elliptic curve test for Mersenne primes, J. Number Theory, 110 (2005), 114-119. doi: 10.1016/j.jnt.2003.11.011.
[18]	A. Gurevich and B. Kunyavskiĭ, Primality testing through algebraic groups, Arch. Math. (Basel), 93 (2009), 555-564. doi: 10.1007/s00013-009-0065-9.
[19]	A. Gurevich and B. Kunyavskiĭ, Deterministic primality tests based on tori and elliptic curves, Finite Fields Appl., 18 (2012), 222-236. doi: 10.1016/j.ffa.2011.07.011.
[20]	M. Kida, Primality tests using algebraic groups, Exper. Math., 13 (2004), 421-427. doi: 10.1080/10586458.2004.10504550.
[21]	H. W. Lenstra, Jr., Elliptic curves and number-theoretic algorithms, in Proc. Int. Congr. Math., Amer. Math. Soc., Providence, 1987, 99-120.
[22]	H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. Math., 126 (1987), 649-673. doi: 10.2307/1971363.
[23]	H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, available online at http://www.math.dartmouth.edu/~carlp/aks041411.pdf, 2011.
[24]	C. Pomerance, Primality testing: variations on a theme of Lucas, Congr. Numer., 201 (2010), 301-312.
[25]	K. Rubin and A. Silverberg, Point counting on reductions of CM elliptic curves, J. Number Theory, 129 (2009), 2903-2923. doi: 10.1016/j.jnt.2009.01.020.
[26]	R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp., 44 (1985), 483-494. doi: 10.2307/2007968.
[27]	A. Silverberg, Group order formulas for reductions of CM elliptic curves, in Proc. Conf. Arith. Geom. Crypt. Coding Theory, Amer. Math. Soc., Providence, 2010, 107-120. doi: 10.1090/conm/521/10277.
[28]	H. Stark, Counting points on CM elliptic curves, Rocky Mountain J. Math., 26 (1996), 1115-1138. doi: 10.1216/rmjm/1181072041.
[29]	Y. Tsumura, Primality tests for $2^p + 2^{\frac{p+1}{2}} + 1$ using elliptic curves, Proc. Amer. Math. Soc., 139 (2011), 2697-2703. doi: 10.1090/S0002-9939-2011-10839-6.
[30]	A. Wong, Primality Test Using Elliptic Curves with Complex Multiplication by $\mathbbQ(\sqrt{-7})$, Ph.D thesis, University of California at Irvine, 2013.

show all references

References:

[1]	A. Abatzoglou, A CM elliptic curve framework for deterministic primality proving on numbers of special form, Ph.D thesis, University of California at Irvine, 2014.
[2]	A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at http://primes.utm.edu/primes/page.php?id=106847
[3]	A. Abatzoglou, A. Silverberg, A. V. Sutherland and A. Wong, available online at http://primes.utm.edu/primes/page.php?id=117544
[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, Math. Sci. Publ., 2013, 1-20. doi: 10.2140/obs.2013.1.1.
[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., to appear.
[6]	M. Agrawal, N. Kayal and N. Saxena, Primes is in P, Ann. Math., 160 (2004), 781-793. doi: 10.4007/annals.2004.160.781.
[7]	A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp., 61 (1993), 29-68. doi: 10.1090/S0025-5718-1993-1199989-X.
[8]	W. Bosma, Primality Testing with Elliptic Curves, Doctoraalscriptie Report, University of Amsterdam 85-12, 1985, available online at http://www.math.ru.nl/ bosma/pubs/PRITwEC1985.pdf
[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-434. doi: 10.1016/0196-8858(86)90023-0.
[10]	R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Second edition, Springer, New York, 2005.
[11]	R. Denomme and G. Savin, Elliptic curve primality tests for Fermat and related primes, J. Number Theory, 128 (2008), 2398-2412. doi: 10.1016/j.jnt.2007.12.009.
[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-329. doi: 10.1145/12130.12162.
[13]	S. Goldwasser and J. Kilian, Primality testing using elliptic curves, J. ACM, 46 (1999), 450-472. doi: 10.1145/320211.320213.
[14]	D. M. Gordon, Pseudoprimes on elliptic curves, in Théorie des nombres, de Gruyter, Berlin, 1989, 290-305.
[15]	B. H. Gross, Arithmetic on Elliptic Curves with Complex Multiplication, Springer, Berlin, 1980.
[16]	B. H. Gross, Minimal models for elliptic curves with complex multiplication, Compositio Math., 45 (1982), 155-164.
[17]	B. H. Gross, An elliptic curve test for Mersenne primes, J. Number Theory, 110 (2005), 114-119. doi: 10.1016/j.jnt.2003.11.011.
[18]	A. Gurevich and B. Kunyavskiĭ, Primality testing through algebraic groups, Arch. Math. (Basel), 93 (2009), 555-564. doi: 10.1007/s00013-009-0065-9.
[19]	A. Gurevich and B. Kunyavskiĭ, Deterministic primality tests based on tori and elliptic curves, Finite Fields Appl., 18 (2012), 222-236. doi: 10.1016/j.ffa.2011.07.011.
[20]	M. Kida, Primality tests using algebraic groups, Exper. Math., 13 (2004), 421-427. doi: 10.1080/10586458.2004.10504550.
[21]	H. W. Lenstra, Jr., Elliptic curves and number-theoretic algorithms, in Proc. Int. Congr. Math., Amer. Math. Soc., Providence, 1987, 99-120.
[22]	H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. Math., 126 (1987), 649-673. doi: 10.2307/1971363.
[23]	H. W. Lenstra, Jr. and C. Pomerance, Primality testing with Gaussian periods, available online at http://www.math.dartmouth.edu/~carlp/aks041411.pdf, 2011.
[24]	C. Pomerance, Primality testing: variations on a theme of Lucas, Congr. Numer., 201 (2010), 301-312.
[25]	K. Rubin and A. Silverberg, Point counting on reductions of CM elliptic curves, J. Number Theory, 129 (2009), 2903-2923. doi: 10.1016/j.jnt.2009.01.020.
[26]	R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp., 44 (1985), 483-494. doi: 10.2307/2007968.
[27]	A. Silverberg, Group order formulas for reductions of CM elliptic curves, in Proc. Conf. Arith. Geom. Crypt. Coding Theory, Amer. Math. Soc., Providence, 2010, 107-120. doi: 10.1090/conm/521/10277.
[28]	H. Stark, Counting points on CM elliptic curves, Rocky Mountain J. Math., 26 (1996), 1115-1138. doi: 10.1216/rmjm/1181072041.
[29]	Y. Tsumura, Primality tests for $2^p + 2^{\frac{p+1}{2}} + 1$ using elliptic curves, Proc. Amer. Math. Soc., 139 (2011), 2697-2703. doi: 10.1090/S0002-9939-2011-10839-6.
[30]	A. Wong, Primality Test Using Elliptic Curves with Complex Multiplication by $\mathbbQ(\sqrt{-7})$, Ph.D thesis, University of California at Irvine, 2013.

[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]	Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong. Speeding up regular elliptic curve scalar multiplication without precomputation. Advances in Mathematics of Communications, 2020, 14 (4) : 703-726. doi: 10.3934/amc.2020090
[3]	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
[4]	David L. Finn. Convexity of level curves for solutions to semilinear elliptic equations. Communications on Pure and Applied Analysis, 2008, 7 (6) : 1335-1343. doi: 10.3934/cpaa.2008.7.1335
[5]	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
[6]	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.
[7]	Guilin Ji, Changjian Liu. The cyclicity of a class of quadratic reversible centers defining elliptic curves. Discrete and Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021299
[8]	Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete and Continuous Dynamical Systems, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310
[9]	Wei Sun. On uniform estimate of complex elliptic equations on closed Hermitian manifolds. Communications on Pure and Applied Analysis, 2017, 16 (5) : 1553-1570. doi: 10.3934/cpaa.2017074
[10]	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
[11]	Ananta Acharya, R. Shivaji, Nalin Fonseka. $ \Sigma $-shaped bifurcation curves for classes of elliptic systems. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022067
[12]	Bertrand Lods. Variational characterizations of the effective multiplication factor of a nuclear reactor core. Kinetic and Related Models, 2009, 2 (2) : 307-331. doi: 10.3934/krm.2009.2.307
[13]	Christopher C. Tisdell. Reimagining multiplication as diagrammatic and dynamic concepts via cutting, pasting and rescaling actions. STEM Education, 2021, 1 (3) : 170-185. doi: 10.3934/steme.2021013
[14]	Stefano Marò. Relativistic pendulum and invariant curves. Discrete and Continuous Dynamical Systems, 2015, 35 (3) : 1139-1162. doi: 10.3934/dcds.2015.35.1139
[15]	Gian-Italo Bischi, Laura Gardini, Fabio Tramontana. Bifurcation curves in discontinuous maps. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 249-267. doi: 10.3934/dcdsb.2010.13.249
[16]	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
[17]	Vladimir Georgiev, Eugene Stepanov. Metric cycles, curves and solenoids. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1443-1463. doi: 10.3934/dcds.2014.34.1443
[18]	Martin Möller. Shimura and Teichmüller curves. Journal of Modern Dynamics, 2011, 5 (1) : 1-32. doi: 10.3934/jmd.2011.5.1
[19]	Lawrence Ein, Wenbo Niu, Jinhyung Park. On blowup of secant varieties of curves. Electronic Research Archive, 2021, 29 (6) : 3649-3654. doi: 10.3934/era.2021055
[20]	Franziska Nestler, Martin Stoll, Theresa Wagner. Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication. Foundations of Data Science, 2022 doi: 10.3934/fods.2022012

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Alice Silverberg
on Google Scholar
Alice Silverberg

[Back to Top]