Genus 1 point counting records over prime fields


July 7, 2010

The number of points on the elliptic curve E defined by the equation

      y2 = x3 + 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 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 described in Genus 1 point counting in quadratic space and essentially quartic time. A rough breakdown of the running time is given below:

TaskTotal CPU time
Compute Φfn(X,j(E)) mod p32 days
Compute Xp mod Φfn(X,j(E))995 days
Construct the Elkies kernel polynomial hn(X)3 days
Compute Yp mod hn and derive Xp mod hn326 days
Find the Frobenius eigenvalue λn using BSGS22 days

Instantiated Weber modular polynomials Φfn(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 Φfn(X,j(E)) has a root in Fp). 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 Xp 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 Xp mod hn from Yp mod hn is described in Fast 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/Fp defined by the equation

      y2 = x3 + 31415926X + 27182818

is #E(Fp) = p+1−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 in Genus 1 point counting in quadratic space and essentially quartic time. A rough breakdown of the running time is given below:

TaskTotal CPU time
Compute Φfn(X,j(E)) mod p4 days
Compute Xp mod Φfn(X, j(E))255 days
Construct the Elkies kernel polynomial hn(X)< 1 day
Compute Yp mod hn and derive Xp mod hn85 days
Find the Frobenius eigenvalue λn using BSGS8 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 Φfn(X,j(E)) has a root in Fp). 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 and here for details).

The polynomial multiplications required to compute Xp 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 Xp mod hn from Yp mod hn is described in Fast 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).