Some remarks on primality proving and elliptic curves

Alice Silverberg

doi:10.3934/amc.2014.8.427

Article Contents

2014, Volume 8, Issue 4: 427-436. Doi: 10.3934/amc.2014.8.427

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

Some remarks on primality proving and elliptic curves

Alice Silverberg^1,

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

Received: December 31, 2013

Published: October 2014

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 11Y11; Secondary: 11G05, 14K22.

Citation:

Related Papers

Cited by

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.