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² = x³ + 2718281828X + 3141592653,

modulo the prime p=16219299585*2¹⁶⁶¹² − 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 in Genus 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 Φfn(X,j(E)) mod p	32 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 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 t_n = λ_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 n^k 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 Φ^f_n(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 h_n from Y^p mod h_n 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 = 10³⁰⁰⁰+1027

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

      y² = x³ + 31415926X + 27182818

is #E(F_p) = p+1&minust, 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:

Task	Total CPU time
Compute Φfn(X,j(E)) mod p	4 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 hn	85 days
Find the Frobenius eigenvalue λn using BSGS	8 days

Instantiated modular polynomials Φ^f_n(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 t_n = λ_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 n^k 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 X^p mod Φ^f_n(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 h_n from Y^p mod h_n 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).