Dear colleagues,

I am pleased to announce the release of a new free software for creating

elliptic curve primality proofs using the fastECPP algorithm due to

Morain, Franke, Kleinjung and Wirth [1, 2]. It is available under the

GPL version 3 or later at

https://www.multiprecision.org/cm/
It relies on the approach of computing class polynomials by complex

approximations as described in [3]. Optimal class invariants are chosen

derived from Weber functions [4], simple [5] or double eta quotients [6],

including cases where it is enough to compute lower-degree subfields of

the class field [7]. The evaluation of modular functions, which is the

most important part of the class polynomial computation, is optimised

following [3, 8]. To ease the step of factoring class polynomials modulo

primes, the class fields are then represented as a tower of cyclic Galois

extensions of prime degree following [9].

The software relies on a number of libraries from the GNU project,

notably GMP [10], MPFR [11] and MPC [12], and on PARI/GP [13] for

computations with class groups and for root finding modulo a prime.

The code has been used to prove a record prime of about 50000 digits;

indeed it has shown that

10^50000+65859 is the smallest prime with

50001 digits. The certificate is available at

https://www.multiprecision.org/downl...cert-50000.bz2
in PARI/GP format [13] and at

https://www.multiprecision.org/downl...0000.primo.bz2
in Primo format [14] as converted by PARI/GP code written by

J. Asuncion, who is also the author of the fastECPP implementation in

PARI/GP. Parallelisation uses MPI.

Computations have been carried out on the PlaFRIM [15] and MCIA [16]

clusters in Bordeaux.

The first phase of the record, in which a list of discriminants and

candidate orders of points on elliptic curves is produced, has taken

about 26 days of wallclock time and 67 years of CPU time, in several

runs on clusters with 752 to 1328 cores. Of this CPU time, about 8%

has been devoted to the computation of square roots modulo a prime by

the Tonelli-Shanks algorithm, about 12% to solving quadratic equations by

Cornacchia's algorithm, about 65% to removing smooth factors from curve

cardinalities, and about 15% to internal primality tests. This imbalance

probably indicates non-optimal choices of parameters. On the other hand,

it leads to very short certificates: We reach a length of only 1645 steps,

as opposed to the 3794 steps in the recent 49000 digits record [17],

which implies that verification time is proportionally lower.

For the specialists, the parameters were as follows: Discriminants with

absolute value up to about 6.9*10^9, leading to class numbers with prime

factors up to 157 (and no bound on the class numbers themselves), and

a smoothness bound of about 5.5*10^11 for partial factorisation of point

orders.

The second phase of the record, in which complex multiplication produces

a list of elliptic curves and points of (recursively shown to be) prime

orders on them, has taken about 74 days of wallclock time and less than

4 years of CPU time on a few machines with 32 to 256 cores in total.

Depending on the largest factor of the class number, each step may take

a vastly differing amount of time. The longest step has taken close to

10 days for factoring a class polynomial for the discriminant -345992327

of class number 13112=2^3*11*149 for an intermediate prime of about

47800 digits; this would also have been the wallclock time for this phase

had it been run sufficiently in parallel. Of the total CPU time, about

96% has been devoted to finding roots of class polynomials, about 3% to

verifying point orders, and only about 1% to the construction of the class

polynomials.

Verification of the certificate takes a little over 4 hours using PARI/GP

on a machine with 128 cores.

Andreas Enge

[1] F. Morain: "Implementing the asymptotically fast version of the

elliptic curve primality proving algorithm", Mathematics of Computation

76 (257), 2007, pp. 493-505

[2] J. Franke, T. Kleinjung, F. Morain and T. Wirth: "Proving the Primality

of Very Large Numbers with fastECPP", in Duncan Buell: "Algorithmic

Number Theory - ANTS-VI", Lecture Notes in Computer Science 3076,

Springer-Verlag, Berlin 2004, pp. 194-207

[3] A. Enge: "The complexity of class polynomial computation via floating

point approximations", Mathematics of Computation 78 (266), 2009,

pp. 1089-1107

[4] R. Schertz: "Die singulären Werte der Weberschen Funktionen $f$,

$f_1$, $f_2$, $\gamma_2$, $\gamma_3$", Journal für die reine und

angewandte Mathematik 286/287, 1976, pp. 46-74

[5] A. Enge and F. Morain: "Generalised Weber Functions", Acta Arithmetica

164 (4), 2014, pp. 309-341

[6] A. Enge and R. Schertz: "Constructing elliptic curves over finite

fields using double eta-quotients", Journal de Théorie des Nombres de

Bordeaux 16, 2004, pp. 555-568

[7] A. Enge and R. Schertz: "Singular values of multiple eta-quotients

for ramified primes", LMS Journal of Computation and Mathematics 16,

2013, 407-418

[8] A. Enge, W. Hart and F. Johansson: "Short addition sequences for theta

functions", Journal of Integer Sequences 18 (2), 2018, pp. 1-34

[9] A. Enge and F. Morain: "Fast Decomposition of Polynomials with Known

Galois Group", in Marc Fossorier, Tom Høholdt and Alain Poli (editors):

"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes -

AAECC-15", Lecture Notes in Computer Science 2643, Springer-Verlag,

Berlin 2003, pp. 254-264

[10] Torbjörn Granlund et al.: "GMP - The GNU Multiple Precision Arithmetic

Library", release 6.2.1, 2020,

http://gmplib.org/
[11] Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, Paul Zimmermann

et al.: "GNU MPFR - A library for multiple-precision floating-point

computations with exact rounding", release 4.1.0, 2020,

http://www.mpfr.org/
[12] A. Enge, M. Gastineau, P. Théveny and P. Zimmermann: "GNU MPC - A

library for multiprecision complex arithmetic with exact rounding",

release 1.2.1, 2020,

https://www.multiprecision.org/mpc/
[13] PARI Group: "PARI/GP", release 2.13.4, 2022,

https://pari.math.u-bordeaux.fr/
[14] M. Martin: "Primo", release 4.3.3, 2020,

http://www.ellipsa.eu/public/primo/primo.html
[15] PlaFRIM, Plateforme Fédérative pour la Recherche en Informatique et Mathématiques,

https://www.plafrim.fr/
[16] MCIA, Mésocentre de Calcul Intensif Aquitain,

https://www.mcia.fr/
[17]

https://primes.utm.edu/primes/page.php?id=133761