Genus 1 point-counting records (original) (raw)
accessibility Genus 1 point counting over prime fields
July 7, 2010
The number of points on the elliptic curve E defined by the equation
_y_2 = _x_3 + 2718281828X + 3141592653,
modulo the prime p_=16219299585*216612 − 1 is p+1−_t, where the Frobenius trace t is the integer
−205676009405629562870723544951711978493769633522691001290342982824394579979020\
4959592275407252503375130973581475034324335091578303659602898092961951903564756\
9198933574237708567449417804544527593253489171272835036914287573195186259060507\
9378051967142239957124811271733862496681523052872100104674708907819012461473325\
1721212562552160555172655862716920841284900275128560059998430399307232130155235\
4770318037680806930569295989240725111217683349520179828098497727732803344520638\
0645027334602616814059068320663621699856598219760976692643576278752947430140491\
6595475629667874243634018488586052345598505206569111319389909915321869347167949\
3155868676978108334106790272982037127662933425771749796702645059239637511409201\
5289220525350785051281761320333589438348416068558542547465060916278320139630744\
2907319563523368372624948591596206702163789435318699775791048148955678435878742\
1897666214061826149830661747871603324711207139815142803476791860168691157478407\
2003315890189110872897596116422007228911474320208862334504162336413864836736210\
5359715444909805319838607670493175621868405897718758574258106867910177145843538\
0874391942946098290760561460645783184379042763328777066300543506565157925043754\
3611837824244725809922762112549137228504010076069580209346876604348239136238425\
8118394715018207836019464687487606402936418324093917766417210216541895677571152\
6763272193305850435146386442265129449541112284818987192814321299484336893724691\
2741334009664482781230858923491788181119189054650310889869900858629974659408913\
4428483925169564746537782964488059752941315320933387528426715619831817515485624\
4734335275132494621001952446852583583199264754496938732527393372326375034790053\
4081899583099725646921295752447566660037903173384929003015921757772295870375676\
8925317990125300911646115088717717639105382789821458209896785394362925921805561\
8911632548625725986031204760147307727593699728775128379092168271121767274773752\
5964246646239976448378614270245272134687309907284961938608669237187423020635746\
6899619292842753118560048311852205009216761760201957318038204119623750508007193\
6406702382528439958955208274496842320127279061845291668832974850434817931979782\
7570511372607343605964113472504605104937216247772767586484941749269032791114761\
4095896400156814109886322639484738661356630416026575898292621971967626230086181\
2490242979836754266268188351661135061847887688824809576465291476689413020982267\
7706160197656271121723717447557022758725420893727752776926667115368323484986502\
6489506952739429390868342254983967258910337922712336904912
This particular prime p was chosen simply because it happens to be the least prime with more than 5000 digits that appears on this list of proven primes. (Update: as kindly pointed out to me by David Broadhurst, there are many smaller proven primes with more than 5000 digits, which you can find using this handy search page). No special properties of the prime p were used in the computation.
This computation was performed on 8 computers working in parallel (3.0 GHz AMD Phenom II, 4 cores each), and took about 6 weeks (1378 CPU days). This figure includes the time required to compute all of the (instantiated) modular polynomials that were used, as initially described inGenus 1 point counting in quadratic space and essentially quartic time and published in On the evaluation of modular polynomials (please cite the paper when citing this result). A rough breakdown of the running time is given below:
| Task | Total CPU time |
|---|---|
| Compute Φf_n_(X,j(E)) mod p | 32 days |
| Compute X_p_ mod Φf_n_(X,j(E)) | 995 days |
| Construct the Elkies kernel polynomial hn(X) | 3 days |
| Compute Y_p_ mod hn and derive X_p_ mod hn | 326 days |
| Find the Frobenius eigenvalue λ_n_ using BSGS | 22 days |
Instantiated Weber modular polynomials Φf_n_(X,j(E)) were computed modulo p for each of the 1400 primes n from 5 to 11681. Exactly 700 of these n were found to be Elkies primes (meaning that Φf_n_(X,j(E)) has a root in F_p_). For each such n, the Frobenius trace tn = λ_n_ + p / λ_n_ mod n was computed, using a version of the Elkies procedure adapted for use with the Weber modular polynomials. The integer value of t was then uniquely determined via the Chinese remainder theorem.
The 700 Atkin primes were not used, and no attempt was made to compute t mod nk for higher powers of n.
The largest instantiated modular polynomial used (for _n_=11681) was under 20MB in size and took about two hours to compute from scratch (using 1 core).
The polynomial multiplications required to compute X_p_ mod Φfn(X,j(E)) were computed via the Schonhage-Strassen algorithm using A cache-friendly truncated FFT and a modified Barrett algorithm for the modular reductions, implemented by David Harvey. This approach yielded a better than 2x speedup over the straight Kronecker substitution used to set the previous record (see below).
The underlying integer multiplications were handled using version 5.0.1 of the GMP library and the FFT patch of Gaudry, Kruppa, and Zimmermann.
The algorithm used to derive X_p_ mod hn from Y_p_ mod hn is described inFast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm by Gaudry and Morain. This was implemented using the fast polynomial multiplication algorithm described above, which yielded about a 3x speedup for this step compared to the previous NTL-based implementation. The BSGS step was similarly accelerated.
May 2, 2010
p = 103000+1027
The number of points on the elliptic curve E/F_p_ defined by the equation
_y_2 = _x_3 + 31415926X + 27182818
is #E(F_p_) = p+1&minus_t_, where the Frobenius trace t is the integer
-636861388352367990904057279694713742114851094351751216695397614384659256064919\
4706647873332146870859276400901366040063084067717299735244893197291713818440988\
0225252195735996489438673067865526585373353177311715569431764360539216569679684\
4199435774318337712722689429728699130264355903514901138997635452390095405896643\
4652989297433450426414528180824155012331260231251866968429721277077105378101747\
7950166527874138403778588221473020127324633948603943548082308359569346004625953\
9620110426244390004902696773769435190232764418456652884533839819909025827062732\
4032376201868902481561175406225927385991094072000527859587366513433325024845709\
4979194964352041623104774343664438303537076826883806209815965385542416490278896\
7108477104460119875915497328735287223179882640189180034222190520568973867444111\
6975668109770040675138573141407680637785929791032577904012353697462620102383583\
6994044688057978567199858826250984211864125943909139007619238813622166173539314\
5775729948556072062060472104068489955265352667858706698835066969488907889054684\
6393526897721511387653968685227292213835640025973111636794599614354982343197803\
9221980716947758159535612291906317776150968525214250286177406994748262908708881\
4300642491364521951720983618076548410569250398714768518872603606172495255364349\
1951541525079596353362795740670402566056577892073559126871600932087279932386594\
4452623622641328635750028383398917995495668721194406971110042913523896993355813\
2440300647278797342410791325082632031315908336271706927065108028163731224113236.
This computation was performed on 8 computers working in parallel (3.0 GHz AMD Phenom II, 4 cores each), and took just over 10 days (approximately 350 CPU days). This figure includes the time required to compute all of the (instantiated) modular polynomials that were used, as described inGenus 1 point counting in quadratic space and essentially quartic time. A rough breakdown of the running time is given below:
| Task | Total CPU time |
|---|---|
| Compute Φf_n_(X,j(E)) mod p | 4 days |
| Compute X_p_ mod Φfn(X, j(E)) | 255 days |
| Construct the Elkies kernel polynomial hn(X) | < 1 day |
| Compute Y_p_ mod hn and derive X_p_ mod hn | 85 days |
| Find the Frobenius eigenvalue λ_n_ using BSGS | 8 days |
Instantiated modular polynomials Φfn(X,j(E)) were computed modulo p for each of the 901 primes n from 2 to 7001 (for p_> 3 the Weber modular polynomials were used). Exactly 450 of these n were found to be Elkies primes (meaning that Φf_n(X,j(E)) has a root in F_p_). For each Elkies prime n, the Frobenius trace tn = λ_n_ + p / λ_n_ mod n was computed, using a version of the Elkies procedure adapted for use with the Weber modular polynomials. The integer value of t was then uniquely determined via the Chinese remainder theorem.
The 451 Atkin primes were simply ignored, and no attempt was made to compute t mod nk for higher powers of n.
The largest instantiated modular polynomial used (for _n_=7001) was under 10MB in size and took less than thirty minutes to compute. The total time spent computing modular polynomials was less than 2 percent of the overall computation time, despite the fact that, asymptotically, these computations strictly dominate the complexity of the SEA algorithm. For comparison, the previous point-counting record modulo a 2500 digit prime used nearly one terabyte of precomputed modular polynomials, whose construction took substantially longer than the point-counting computation itself (see here andhere for details).
The polynomial multiplications required to compute X_p_ mod Φfn(X,j(E)) were performed, via Kronecker substitution, using large integer multiplications. These multiplications were handled using version 5.0.1 of the GMP library and the FFT patch of Gaudry, Kruppa, and Zimmermann. The algorithm used to derive X_p_ mod hn from Y_p_ mod hn is described inFast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm by Gaudry and Morain, and was implemented using version 5.5.2 of Shoup's NTL library (a faster approach based on abelian lifts was not used).