Counting points on elliptic curves

One of the topics of my PhD research is point counting on elliptic curves using the new algorithm due to Takakazu Satoh. My colleagues Robert Harley, Pierrick Gaudry and François Morain and I have recently established new records for point counting in characteristic 2.

A copy of the announcement of our 3001-bit record can be found here.

A copy of the announcement of our 5003-bit record can be found here.

A copy of the announcement of our 8009-bit record can be found here.

You can also find a copy of the paper we wrote about this algorithm and its implementation here.

Let E be the curve:

y² + x y = x³ + a6

over GF(2^n). We represent the field as GF(2)[x]/(f(x)) where f is an irreducible polynomial of degree n. The coefficient a6 we chose is:

0x3F6576EA7220656A20F96F20736973616F276C207361702075742D7365274E

which comes from the ASCII encoding (ISO-8859-1) of the following line by Charles Baudelaire:

N'es-tu pas l'oasis où je rêve?

The results we obtained are 2^n + 1 - t where:

n = 503: t = -31238564670483795450312817872056405257868594699 6895244046021516482348307823
n = 1009: t = 807681026366028357085789135197617870605796659019 3619461368476677480469591352799642771094940451853932 890400847591814162158144318875981111691524778491953
n = 1511: t = -28400768556934958867743240430395694772857313718 3174931164376525122133145696760065734797075994572274 4436002311432801469936220522431939811307386594671349 2268002522029011799755284843163047617227197214936862 312112549121674571407231
n = 2003: t = -54257716382449163322217965867619130414983986889 0313935049509502740235675679159500503004838979580842 6890271717025960174927513282968711946410138504333337 2481793555545941317422170070614774973636138071957047 8245753475439861130956866532988058132481864878669071 30906901144504392836677514330977449181534276415
n = 2503: t = 375456780359377839428248525231477119570486033306 7628328951966689662892109817840199550959116531867993 2461375963686964255539300728445502594675789848832832 0162311375995573731186740440056586812194900866384065 2608555937835996837283114403351313056490579252442982 6674016543346828824344556746021336343745844527355696 0009793176441482990625000205658498151356480370740824 97972064755848961
n = 3001: t = -14403755582543872125177435497927178175213015805 7330496539872194988218278834360214740333856828611760 2964047438283887869997035112384448200530762524045217 1264059724504453800904987662332361279038091579114406 7887012079308031639424036856757184619455646737341540 5698362683566256213909170495298430198451525068385277 0257821546361523788958213844228786765379249813464301 8889266258841404146263311221589953400487995392882642 07591609255397089053805723638945016394751
n = 3511: t = 414328759607065317343606376361429657475308002212 5091696296623693442797874276129740063597782252458606 8814736164075230349572369999190460049671701908447990 5922177477328995615981656795970483234944879187691674 0980101576296914957073812728577672245395882907545677 4727747853201232221381887710903829739783516892674388 3902964447496714616419717920371808701558303985760751 2623495843343241343802212384834381406845863306448053 0654146750761222570481519428607157892447678643099620 6305648858228090017428047604695858956328254277135814 0538943424065
n = 4001: t = 801772519193752131932619560339947365971034799872 8587921312677922999812464563599735071344322180149412 4679597962879601353149563605304969090722905778013218 3804551592528156093941834305018840923437158548976538 1206596837899816779581833266977502547124291858807646 1110217915069806929966345724756739313913921549649218 3045119394738925071301039529553197801862674884789589 0991631639943661205261576802575080499543739658458057 3502734408159103335730844509915511939253762122166415 9110835745949179265910696816538335435288141851236856 0625315600699619760433075028073624496162971045493847 0970967466942969118418184438560705

The polynomials f(x) and the run-times were:

`f(x)`	CPU	Time	Memory used	CPU time provided by
`x⁵⁰³ + x³ + 1`	500 MHz Alpha EV6	6 minutes
`x¹⁰⁰⁹ + x⁵⁵ + 1`	500 MHz Alpha EV6	1 hour
`x¹⁵¹¹ + x²⁷⁸ + 1`	500 MHz Alpha EV6	5 hours
`x²⁰⁰³ + x¹² + x¹⁰ + x⁸ + 1`	500 MHz Alpha EV6	14 hours
`x²⁵⁰³ + x³¹⁶ + 1`	500 MHz Alpha EV6	40 hours	531 MB
`x³⁰⁰¹ + x⁹⁷⁵ + 1`	667 MHz Alpha EV6	54 hours	932 MB	Paul Bourke (Swinburne University Astrophysics and Supercomputing)
`x³⁵¹¹ + x¹¹⁴¹ + 1`	667 MHz Alpha EV6	97 hours	1.3 GB	Paul Bourke (Swinburne University Astrophysics and Supercomputing)
`x⁴⁰⁰¹ + x¹³⁷ + 1`	750 MHz Alpha UP2000	132 hours	1.9 GB	Tom Morris (Alpha Processor Inc)

Let E be the curve:

y² + x y = x³ + a6

over GF(2^n). We represent the field as GF(2)[x]/(f(x)) where f is an irreducible polynomial of degree n. The coefficient a6 we chose is:

0x3F2065737365727669276C20746961206E6F27757120757672756F70202C 6E6F63616C6620656C206574726F706D69277551203F20657373657274EE 616D20616C206574726F706D69277571202C746E696F7020646E61726720 656C207473652072656D6941202E6C69656C6F732075612065697620616C 2074652072756F6D61276C202C74756F74207473652072756F6D61274C

which comes from the ASCII encoding (ISO-8859-1) of the following line by Alfred de Musset:

L'amour est tout, l'amour et la vie au soleil.
Aimer est le grand point, qu'importe la maîtresse ?
Qu'importe le flacon, pourvu qu'on ait l'ivresse ?

The results we obtained are 2^n + 1 - t where:

n = 5003: t=-127341829230648002523018943832226937252103694652076799408922 477612855289377203332779688306682831493273269764054770424297 006136035981001881534370915908800378671831329239996811497697 148968483482544588860921652059893323901220603619128807017820 139267622096926839017765077031279609851645981284832206631534 133807288001526847890199213216628817376092472825902831868662 870338188025136323147277677664022022418918458550932834294111 993858888706282080207793141360407739444174188695573930660771 520813411370625917808763097521316149794711148167469373259091 359932614020803204802726666535109183001470735906486026091062 940240471300907998678966329023873891104882857514851544063170 582653334908271416860233735585623607368617405745505045156736 1750612709555407613790732067510175
n = 6007: t=3442061241831053996615832184729488073173960929415596873391624 0735074054386750995324726283712152853544174238412851376047070 8833119398328600011413068657966809197790402083599786447073895 7670892097869488100734744373625776913457011893379913446989775 9948146328306300644690018473496352595361381815087410129216348 6800454753434344865483117887437584475911403340275618360633469 6231378804501610228673410052580840098862304791612864276178562 3465183932446927985141947695864308965365832079922890622252441 3938585461377617126175689088978662090720513871209911870612646 2898948834053845355104577980983069522949252022515872310857412 6245720627861504154908945603509369314367877612679565045855007 9217430955154845364558025542982307460071763907044624173653064 9068697258585375195516895157040281805394439187185481758711498 9420593138961727685731114071309572168891196530781166053344563 9938870064211270693767042897900149946085199206561

The polynomials f(x) and the run-times were:

`f(x)`	CPU	Time	Memory used	CPU time provided by
`x⁵⁰⁰³ + x¹⁸ + x¹⁶ + x⁸ + 1`	750 MHz Alpha EV6	143 hours	4GB	Rajit Manohar (Cornell Computer Systems Laboratory)
`x⁶⁰⁰⁷ + x⁴³⁵ + 1`	750 MHz Alpha EV6	9 days	7.1 GB	Rajit Manohar (Cornell Computer Systems Laboratory)

Let E be the curve:

y² + x y = x³ + a6

over GF(2^n). We represent the field as GF(2)[x]/(f(x)) where f is an irreducible polynomial of degree n. The coefficient a6 we chose is:

0x3F636F64207075207327746168570

which comes from the ASCII encoding (ISO-8859-1) of Bugs Bunny's phrase:

What's up doc?

The results we obtained are 2^n + 1 - t where:

n = 7001: t=-581371373310534460112778003571913522920537044570507812766 071825066212473879209453924332740583385692865452499160811904 242698205872414186057729147273319201074753165378947550871485 673730967996250474412965784188133088012505743059546142132542 704250162993266626355516734802204804726729418784708763515549 609163420151142995403094233561277231153107257231371302254453 872229039207995763431245365186806999267459314058281699973113 019652643268708794118572021571532669324535389906079992115131 890454044735048448151995993910920507321990283570867852464235 050741381904965739448692663452746610614491278508031681354575 958619186277522674034228696819176368577661460451124436403404 953468525792487079397978160405949913563255747401978856499908 460632990544455441529706877442091824052857209486661754851767 965943320080307707967102257123456554143172682273759504390371 729788374896636018230902404170775216453565402229236693232193 425256689309240574509695883291712065992422967344009813656715 459973153166333791111238516612328972388151658382349396571949 2507357848397233571808377373646960699
n = 8009: t=-173781496855947505026635002869635953808229335381570056464 621193940895056863504783294021995065119636064037744458121824 706256101375092227785899279859382375508813512228452707543448 804227830350453630318289993429955048544858271431235554925925 218016021462976522604806199992629607633615399045665748120403 497295724818612705811737001932873239713976031333307121192031 140124936716110261344299992343462618094707883381239575692354 062675177743128084928704789927053902757527426178584350294618 098340414692085330411964582201095084463986891949680756772569 455776175298098419627580620230881405697016837843911732490034 219592736044382123314677929838172853537747054427942739774461 484712209985999476777494287080574838937079674483708654377667 748782232512309071885437433718460626024619545730229857335859 452961591499827794731180323396776774693997980749628390806053 785208509477197767399825222359144733258976844620499589156331 646085956322156871493279308734719611148013330484292242206852 555894563150429003330357185835857959827198598539336567401817 103005203941979959470708629753376721197597388299770441615351 946293827847496574699722624775864568852009210270915236395433 004819982461492543540766219587259634877029770317456234950616 362600955

The polynomial f(x) and the run-time were:

`f(x)`	CPU	Time	Memory used	CPU time provided by
`x⁷⁰⁰¹ + x¹⁶³¹ + 1`	667 MHz Alpha EV6	11 days	11.3 GB	Pierrick Gaudry (Laboratoire d'informatique de l'É polytechnique)
`x⁸⁰⁰⁹ + x³¹⁵⁹ + 1`	750 MHz Alpha EV6	13 days	16.9 GB	Rajit Manohar (Cornell Computer Systems Laboratory)