mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2022-05-06, 21:16   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,857 Posts
Plus FastECPP software and 50000 digit primality proof (reposted from NMBRTHRY)

Quote:
Originally Posted by Andreas Enge @inria.fr
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
Exciting development. The early preview was visible since last August:
Quote:
rank prime digits who when comment
64129 U(148091) 30949 x49 Sep 2021 Fibonacci number, ECPP
66197 (2^95369 + 1)/3 28709 x49 Aug 2021 Generalized Lucas number, Wagstaff, ECPP
Batalov is offline   Reply With Quote
Old 2022-05-06, 22:05   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

106916 Posts
Default

An amazing feat! Such parallelism and clever mathematics run on some very big hardware. I take my hat off to these provers.
paulunderwood is online now   Reply With Quote
Old 2022-05-06, 23:17   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,331 Posts
Default

So 71 years of CPU time for 51,000 digits vs 20 months * 64 cores ~ 107 years of CPU time for 49,081 digits.
But depends on how comparable those CPU core years are.

51,000 digits is supposed to take (51000/49081)^3.75 ~ 15% longer ? At least with Primo.
ATH is offline   Reply With Quote
Old 2022-05-06, 23:29   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

232018 Posts
Default

Note in their text that they say "This <<...>> 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" (!!).

They call it a pre-release. They will likely optimize it even more.

Btw, I had to "massage" their cert a little bit, but then factorDB took it. Took 3 iterations slightly reformatting the file (and to rename it into .out file)
Batalov is offline   Reply With Quote
Old 2022-05-06, 23:31   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

4,201 Posts
Default

Quote:
Originally Posted by ATH View Post
So 71 years of CPU time for 51,000 digits vs 20 months * 64 cores ~ 107 years of CPU time for 49,081 digits.
But depends on how comparable those CPU core years are.

51,000 digits is supposed to take (51000/49081)^3.75 ~ 15% longer ? At least with Primo.
It is 50,001 digits. My estimate for Primo is (50001/49081)^4 = 1.077 or 7.7% longer.

I used quad channel DDR 2400MHz for R49081's certification. I guess they were using octa channel most of the time, but that does not explain their speed fully. There is marginal gain by having fewer stage 2 steps to do.

Last fiddled with by paulunderwood on 2022-05-06 at 23:53
paulunderwood is online now   Reply With Quote
Old 2022-05-06, 23:33   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

4,201 Posts
Default

Quote:
Originally Posted by Batalov View Post
Note in their text that they say "This <<...>> 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" (!!).

They call it a pre-release. They will likely optimize it even more.

Btw, I had to "massage" their cert a little bit, but then factorDB took it. Took 3 iterations slightly reformatting the file (and to rename it into .out file)
Please email Andraes and ask him to make an UTM submission.

Last fiddled with by paulunderwood on 2022-05-06 at 23:37
paulunderwood is online now   Reply With Quote
Old 2022-05-06, 23:50   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,857 Posts
Default

I made a shorter jump and forwarded NMBRTHRY email to Caldwell. (though he is surely on the list.*)

________
* Funny story: a few years ago a ton (literally!) of porn links started coming every day via NMBRTHRY email list. It went on for quite a while. Many folks, I am afraid, unsubscribed from it at that point. Since then it has been moderated with huge delays. One curious example was when an invitation to a December conference was sent out in March.
Batalov is offline   Reply With Quote
Old 2022-05-07, 00:33   #8
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

46438 Posts
Default

This is great news for two reasons:

1. It's a new ECPP world record.
2. We finally have an open-source ECPP implementation that can compete with Primo. I'm aware that Marcel has no obligation to make Primo open source, but I do feel that closed-source software goes against the spirit of science.

Last fiddled with by ixfd64 on 2022-05-07 at 02:14
ixfd64 is offline   Reply With Quote
Old 2022-05-07, 07:31   #9
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

23×3×29 Posts
Default

Holy s**t!


Hats off and congrats to all those involved. That is some serious soft- and hardware. I wonder how big the code can go? There are so many interesting numbers from 50K to 100K digits. Just the electricity cost alone will make such a number pretty valuable
Puzzle-Peter is offline   Reply With Quote
Old 2022-05-07, 13:51   #10
mathwiz
 
Mar 2019

22×3×23 Posts
Default

Fantastic!

It would seem this page needs an update?
mathwiz is offline   Reply With Quote
Old 2022-05-07, 15:15   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

4,201 Posts
Default

Some entity should set up fastECPP for a proof-over-the-net. Clients could latch onto the main server. This way a 60k proof might be computed in a reasonable amount of time.

Last fiddled with by paulunderwood on 2022-05-07 at 15:22
paulunderwood is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
For which types of primes is GPU primality test software available? bur GPU Computing 6 2020-08-28 06:20
Fastest software for Mersenne primality test? JonathanM Information & Answers 25 2020-06-16 02:47
APR-CL as primality proof f1pokerspeed FactorDB 14 2014-01-09 21:06
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 14:58.


Sat Jun 25 14:58:01 UTC 2022 up 72 days, 12:59, 0 users, load averages: 1.13, 1.06, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔