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]

Ph.D thesis, University of California at Irvine, 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]

in Algorithmic Number Theory, Math. Sci. Publ., 2013, 1-20. 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]

Ann. Math., 160 (2004), 781-793. doi: 10.4007/annals.2004.160.781.  Google Scholar

[7]

Math. Comp., 61 (1993), 29-68. doi: 10.1090/S0025-5718-1993-1199989-X.  Google Scholar

[8]

Doctoraalscriptie Report, University of Amsterdam 85-12, 1985, available online at http://www.math.ru.nl/ bosma/pubs/PRITwEC1985.pdf Google Scholar

[9]

Adv. Appl. Math., 7 (1986), 385-434. doi: 10.1016/0196-8858(86)90023-0.  Google Scholar

[10]

Springer, New York, 2005. Google Scholar

[11]

J. Number Theory, 128 (2008), 2398-2412. doi: 10.1016/j.jnt.2007.12.009.  Google Scholar

[12]

in STOC '86 - Proc. 18th Annual ACM Symp. Theory Computing, 1986, 316-329. doi: 10.1145/12130.12162.  Google Scholar

[13]

J. ACM, 46 (1999), 450-472. doi: 10.1145/320211.320213.  Google Scholar

[14]

in Théorie des nombres, de Gruyter, Berlin, 1989, 290-305.  Google Scholar

[15]

Springer, Berlin, 1980.  Google Scholar

[16]

Compositio Math., 45 (1982), 155-164.  Google Scholar

[17]

J. Number Theory, 110 (2005), 114-119. doi: 10.1016/j.jnt.2003.11.011.  Google Scholar

[18]

Arch. Math. (Basel), 93 (2009), 555-564. doi: 10.1007/s00013-009-0065-9.  Google Scholar

[19]

Finite Fields Appl., 18 (2012), 222-236. doi: 10.1016/j.ffa.2011.07.011.  Google Scholar

[20]

Exper. Math., 13 (2004), 421-427. doi: 10.1080/10586458.2004.10504550.  Google Scholar

[21]

in Proc. Int. Congr. Math., Amer. Math. Soc., Providence, 1987, 99-120.  Google Scholar

[22]

Ann. Math., 126 (1987), 649-673. doi: 10.2307/1971363.  Google Scholar

[23]

available online at http://www.math.dartmouth.edu/~carlp/aks041411.pdf, 2011.  Google Scholar

[24]

Congr. Numer., 201 (2010), 301-312.  Google Scholar

[25]

J. Number Theory, 129 (2009), 2903-2923. doi: 10.1016/j.jnt.2009.01.020.  Google Scholar

[26]

Math. Comp., 44 (1985), 483-494. doi: 10.2307/2007968.  Google Scholar

[27]

in Proc. Conf. Arith. Geom. Crypt. Coding Theory, Amer. Math. Soc., Providence, 2010, 107-120. doi: 10.1090/conm/521/10277.  Google Scholar

[28]

Rocky Mountain J. Math., 26 (1996), 1115-1138. doi: 10.1216/rmjm/1181072041.  Google Scholar

[29]

Proc. Amer. Math. Soc., 139 (2011), 2697-2703. doi: 10.1090/S0002-9939-2011-10839-6.  Google Scholar

[30]

Ph.D thesis, University of California at Irvine, 2013.  Google Scholar

show all references

References:
[1]

Ph.D thesis, University of California at Irvine, 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]

in Algorithmic Number Theory, Math. Sci. Publ., 2013, 1-20. 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]

Ann. Math., 160 (2004), 781-793. doi: 10.4007/annals.2004.160.781.  Google Scholar

[7]

Math. Comp., 61 (1993), 29-68. doi: 10.1090/S0025-5718-1993-1199989-X.  Google Scholar

[8]

Doctoraalscriptie Report, University of Amsterdam 85-12, 1985, available online at http://www.math.ru.nl/ bosma/pubs/PRITwEC1985.pdf Google Scholar

[9]

Adv. Appl. Math., 7 (1986), 385-434. doi: 10.1016/0196-8858(86)90023-0.  Google Scholar

[10]

Springer, New York, 2005. Google Scholar

[11]

J. Number Theory, 128 (2008), 2398-2412. doi: 10.1016/j.jnt.2007.12.009.  Google Scholar

[12]

in STOC '86 - Proc. 18th Annual ACM Symp. Theory Computing, 1986, 316-329. doi: 10.1145/12130.12162.  Google Scholar

[13]

J. ACM, 46 (1999), 450-472. doi: 10.1145/320211.320213.  Google Scholar

[14]

in Théorie des nombres, de Gruyter, Berlin, 1989, 290-305.  Google Scholar

[15]

Springer, Berlin, 1980.  Google Scholar

[16]

Compositio Math., 45 (1982), 155-164.  Google Scholar

[17]

J. Number Theory, 110 (2005), 114-119. doi: 10.1016/j.jnt.2003.11.011.  Google Scholar

[18]

Arch. Math. (Basel), 93 (2009), 555-564. doi: 10.1007/s00013-009-0065-9.  Google Scholar

[19]

Finite Fields Appl., 18 (2012), 222-236. doi: 10.1016/j.ffa.2011.07.011.  Google Scholar

[20]

Exper. Math., 13 (2004), 421-427. doi: 10.1080/10586458.2004.10504550.  Google Scholar

[21]

in Proc. Int. Congr. Math., Amer. Math. Soc., Providence, 1987, 99-120.  Google Scholar

[22]

Ann. Math., 126 (1987), 649-673. doi: 10.2307/1971363.  Google Scholar

[23]

available online at http://www.math.dartmouth.edu/~carlp/aks041411.pdf, 2011.  Google Scholar

[24]

Congr. Numer., 201 (2010), 301-312.  Google Scholar

[25]

J. Number Theory, 129 (2009), 2903-2923. doi: 10.1016/j.jnt.2009.01.020.  Google Scholar

[26]

Math. Comp., 44 (1985), 483-494. doi: 10.2307/2007968.  Google Scholar

[27]

in Proc. Conf. Arith. Geom. Crypt. Coding Theory, Amer. Math. Soc., Providence, 2010, 107-120. doi: 10.1090/conm/521/10277.  Google Scholar

[28]

Rocky Mountain J. Math., 26 (1996), 1115-1138. doi: 10.1216/rmjm/1181072041.  Google Scholar

[29]

Proc. Amer. Math. Soc., 139 (2011), 2697-2703. doi: 10.1090/S0002-9939-2011-10839-6.  Google Scholar

[30]

Ph.D thesis, University of California at Irvine, 2013.  Google Scholar

[1]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2021, 13 (1) : 55-72. doi: 10.3934/jgm.2020031
[2]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3295-3317. doi: 10.3934/dcds.2020406
[3]

Thomas Kappeler, Yannick Widmer. On nomalized differentials on spectral curves associated with the sinh-Gordon equation. Journal of Geometric Mechanics, 2021, 13 (1) : 73-143. doi: 10.3934/jgm.2020023
[4]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2619-2633. doi: 10.3934/dcds.2020377
[5]

Wei Xi Li, Chao Jiang Xu. Subellipticity of some complex vector fields related to the Witten Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021047
[6]

Simão Correia, Mário Figueira. A generalized complex Ginzburg-Landau equation: Global existence and stability results. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021056
[7]

Joel Coacalle, Andrew Raich. Compactness of the complex Green operator on non-pseudoconvex CR manifolds. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021061
[8]

Craig Cowan. Supercritical elliptic problems involving a Cordes like operator. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021037
[9]

John Villavert. On problems with weighted elliptic operator and general growth nonlinearities. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021023
[10]

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
[11]

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
[12]

Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021004
[13]

Livia Betz, Irwin Yousept. Optimal control of elliptic variational inequalities with bounded and unbounded operators. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021009
[14]

Meiqiang Feng, Yichen Zhang. Positive solutions of singular multiparameter p-Laplacian elliptic systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021083
[15]

Minh-Phuong Tran, Thanh-Nhan Nguyen. Pointwise gradient bounds for a class of very singular quasilinear elliptic equations. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021043
[16]

Lidan Wang, Lihe Wang, Chunqin Zhou. Classification of positive solutions for fully nonlinear elliptic equations in unbounded cylinders. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1241-1261. doi: 10.3934/cpaa.2021019
[17]

Christos Sourdis. A Liouville theorem for ancient solutions to a semilinear heat equation and its elliptic counterpart. Electronic Research Archive, , () : -. doi: 10.3934/era.2021016
[18]

Guanming Gai, Yuanyuan Nie, Chunpeng Wang. A degenerate elliptic problem from subsonic-sonic flows in convergent nozzles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021070
[19]

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, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[20]

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

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