# 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
x503 + x3 + 1 500 MHz Alpha EV6 6 minutes
x1009 + x55 + 1 500 MHz Alpha EV6 1 hour
x1511 + x278 + 1 500 MHz Alpha EV6 5 hours
x2003 + x12 + x10 + x8 + 1 500 MHz Alpha EV6 14 hours
x2503 + x316 + 1 500 MHz Alpha EV6 40 hours 531 MB
x3001 + x975 + 1 667 MHz Alpha EV6 54 hours 932 MB Paul Bourke (Swinburne University Astrophysics and Supercomputing)
x3511 + x1141 + 1 667 MHz Alpha EV6 97 hours 1.3 GB Paul Bourke (Swinburne University Astrophysics and Supercomputing)
x4001 + x137 + 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
x5003 + x18 + x16 + x8 + 1 750 MHz Alpha EV6 143 hours 4GB Rajit Manohar (Cornell Computer Systems Laboratory)
x6007 + x435 + 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
x7001 + x1631 + 1 667 MHz Alpha EV6 11 days 11.3 GB Pierrick Gaudry (Laboratoire d'informatique de l'É polytechnique)
x8009 + x3159 + 1 750 MHz Alpha EV6 13 days 16.9 GB Rajit Manohar (Cornell Computer Systems Laboratory)