×

zbMATH — the first resource for mathematics

Implementing the asymptotically fast version of the elliptic curve primality proving algorithm. (English) Zbl 1127.11084
The author of this paper jointly with A. O. L. Atkin [Math. Comput. 61, No. 203, 29–69 (1993; Zbl 0792.11056)] gave the so-called Elliptic Curve Primality Proving (ECPP), which is based on the elliptic version of a classical theorem of Pocklington and uses complex multiplication techniques: let \(D\) be a (fundamental) discriminant such that the number \(N\) to be tested splits in the ring of integers of the quadratic field \(K=\mathbb Q(\sqrt D)\), \(N=\pi\overline{\pi}\) and such that \(m=N+1-\pi-\overline{\pi}\), is a suitable cardinal (\(m=cN'\) for a small integer \(c>1\) and \(N'\) a probable prime). Let \(H_D(X)\in \mathbb Z[X]\) be the polynomial of Hilbert and \(j\) a root of \(H_D(X)\bmod N\). Then any elliptic curve with \(j\)-invariant over \(F_N\) (\(N\) assumed to be prime) has cardinal \(m\).
The ECPP has expected run time polynomial in \(\log(N)\) and their execution provides a certificate for the primality of \(N\).
In this paper the author describes the implementation of an asymptotically fast version of the ECPP (the fastECPP) attributed to J. O. Shallit [see A. K. Lenstra and H. W. Lenstra, Handbook of Theoretical Computer Science, J. van Leeuwen (ed.), North-Holland, 674–715 (1990; Zbl 0900.68250)] with conjectural cost \(\tilde{O}((\log N)^4)\) (where \(\tilde{O}(f)\) means \(O(f\log f)^{O(1)})\)).
Section 3 of the paper gives a sketch of the ECPP algorithm, while fastECPP is described in Section 4. The main difference with the ECPP is in the way of taking the discriminants \(D\), in order to reduce the number of square roots that must be computed.
Section 5 discusses some details of the implementation of fastECPP: computing the class number \(h(-D),\) the Cornacchia algorithm, the factoring of \(m\) (to check the condition \(m=cN'\)), etc. Section 6, Benchmarks, presents the experimental results obtained with the implementation of fastECPP (using the first 20 primes with 1000, 1500 and 2000 digits). Tables 1, 2 and 3 give the timings (min, max and average) for each one of the three mentioned cases.

MSC:
11Y11 Primality
11G05 Elliptic curves over global fields
11G15 Complex multiplication and moduli of abelian varieties
11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
Software:
ECPP; MPC; MPFR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173 – 206. · Zbl 0526.10004 · doi:10.2307/2006975 · doi.org
[2] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781 – 793. · Zbl 1071.11070 · doi:10.4007/annals.2004.160.781 · doi.org
[3] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29 – 68. · Zbl 0792.11056
[4] Mohamed Ayad, Points \?-entiers des courbes elliptiques, Manuscripta Math. 76 (1992), no. 3-4, 305 – 324 (French). · Zbl 0773.14014 · doi:10.1007/BF02567763 · doi.org
[5] D. Bernstein. Proving primality after Agrawal-Kayal-Saxena. http://cr.yp.to/papers /aks.ps, January 2003.
[6] D. Bernstein. Proving primality in essentially quartic expected time. http://cr.yp.to /papers/quartic.ps, January 2003.
[7] Pedro Berrizbeitia, Sharpening ”PRIMES is in \?” for a large family of numbers, Math. Comp. 74 (2005), no. 252, 2043 – 2059. · Zbl 1071.11071
[8] Reinier Bröker and Peter Stevenhagen, Elliptic curves with a given number of points, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 117 – 131. · Zbl 1207.11065 · doi:10.1007/978-3-540-24847-7_8 · doi.org
[9] Qi Cheng, Primality proving via one round in ECPP and one iteration in AKS, Advances in cryptology — CRYPTO 2003, Lecture Notes in Comput. Sci., vol. 2729, Springer, Berlin, 2003, pp. 338 – 348. · Zbl 1122.68456 · doi:10.1007/978-3-540-45146-4_20 · doi.org
[10] H. Cohen and H. W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33 – 62. · doi:10.1007/BFb0099440 · doi.org
[11] H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297 – 330. · Zbl 0578.10004
[12] Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 234 – 243. · Zbl 1057.11026 · doi:10.1007/3-540-45455-1_19 · doi.org
[13] David A. Cox, Primes of the form \?²+\?\?², A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication.
[14] Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. · Zbl 1088.11001
[15] A. Enge. The complexity of class polynomial computations via floating point approximations. Preprint, February 2004. · Zbl 1208.11136
[16] Andreas Enge and François Morain, Comparing invariants for class fields of imaginary quadratric fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 252 – 266. · Zbl 1058.11077 · doi:10.1007/3-540-45455-1_21 · doi.org
[17] Andreas Enge and François Morain, Fast decomposition of polynomials with known Galois group, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 254 – 264. · Zbl 1030.11078 · doi:10.1007/3-540-44828-4_27 · doi.org
[18] Andreas Enge and Reinhard Schertz, Modular curves of composite level, Acta Arith. 118 (2005), no. 2, 129 – 141. · Zbl 1158.11322 · doi:10.4064/aa118-2-3 · doi.org
[19] A. Enge and P. Zimmermann. mpc – a library for multiprecision complex arithmetic with exact rounding, 2002. Version 0.4.1, available from http://www.lix.polytechnique.fr/Labo/Andreas.Enge.
[20] J. Franke, T. Kleinjung, F. Morain, and T. Wirth, Proving the primality of very large numbers with fastECPP, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 194 – 207. · Zbl 1125.11359 · doi:10.1007/978-3-540-24847-7_14 · doi.org
[21] J. Franke, T. Kleinjung, F. Morain, and T. Wirth. A new large primality proof using fastecpp. http://listserv.nodak.edu/archives/nmbrthry.html, July 2004. · Zbl 1125.11359
[22] W. F. Galway. Analytic computation of the prime-counting function. Ph.D. thesis, University of Urbana-Champaign, 2004. http://www.math.uiuc.edu/ galway/PhD_Thesis/.
[23] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. · Zbl 0936.11069
[24] Alice Gee, Class invariants by Shimura’s reciprocity law, J. Théor. Nombres Bordeaux 11 (1999), no. 1, 45 – 72 (English, with English and French summaries). Les XXèmes Journées Arithmétiques (Limoges, 1997). · Zbl 0957.11048
[25] Alice Gee and Peter Stevenhagen, Generating class fields using Shimura reciprocity, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 441 – 453. · Zbl 0912.11045 · doi:10.1007/BFb0054883 · doi.org
[26] GNU. The GNU Multiple Precision arithmetic library. Available from http://www.swox.com/gmp/.
[27] Shafi Goldwasser and Joe Kilian, Primality testing using elliptic curves, J. ACM 46 (1999), no. 4, 450 – 472. · Zbl 1064.11503 · doi:10.1145/320211.320213 · doi.org
[28] G. Hanrot, V. Lefèvre, and P. Zimmermann et. al. mpfr – a library for multiple-precision floating-point computations with exact rounding, 2002. Version contained in GMP. Available from http://www.mpfr.org.
[29] G. Hanrot and F. Morain, Solvability by radicals from an algorithmic point of view, Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2001, pp. 175 – 182. · Zbl 1356.12010 · doi:10.1145/384101.384125 · doi.org
[30] A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673 – 715. · Zbl 0900.68250
[31] H. W. Lenstra, Jr. and C. Pomerance. Primality testing with Gaussian periods. Preprint. Available as http://www.math.dartmouth.edu/ carlp/PDF/complexity072805.pdf, July 2005.
[32] Stéphane Louboutin, Computation of class numbers of quadratic number fields, Math. Comp. 71 (2002), no. 240, 1735 – 1743. · Zbl 1030.11079
[33] P. Mihailescu. Fast convolutions meet Montgomery. Preprint, March 2004. · Zbl 1183.11081
[34] P. Mihailescu and R. Avanzi. Efficient quasi-deterministic primality test improving AKS. Available from http://www-math.uni-paderborn.de/ preda/papers/myaks1.ps, April 2003.
[35] F. Morain, Primality proving using elliptic curves: an update, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 111 – 127. · Zbl 0908.11061 · doi:10.1007/BFb0054855 · doi.org
[36] François Morain, La primalité en temps polynomial (d’après Adleman, Huang; Agrawal, Kayal, Saxena), Astérisque 294 (2004), viii, 205 – 230 (French, with French summary). · Zbl 1097.11059
[37] Władysław Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN — Polish Scientific Publishers, Warsaw, 1974. Monografie Matematyczne, Tom 57. · Zbl 0276.12002
[38] Abderrahmane Nitaj, L’algorithme de Cornacchia, Exposition. Math. 13 (1995), no. 4, 358 – 365 (French, with English summary). · Zbl 0852.11074
[39] Reinhard Schertz, Weber’s class invariants revisited, J. Théor. Nombres Bordeaux 14 (2002), no. 1, 325 – 343 (English, with English and French summaries). · Zbl 1022.11056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.