// Verification.magma // Version 1.1 // 25 March 2014 // Reinier Bröker, Everett W. Howe, Kristin E. Lauter, and Peter Stevenhagen. /* ======================================================================== This Magma file contains code that verifies the examples found in Section 7 of the paper [BHLS]. If this file is loaded into Magma, and all of the "assert" statements run without complaint, then the examples we give in the paper are correct. Further details and explanations are found in the comments incorporated into the file, below. NOTE: We are waiting for a certificate of the primality of the integer 10^2014 + 9703. Without that certificate, our final example is not yet proven to be correct. ======================================================================== REFERENCES: [BHLS] Reinier Bröker, Everett W. Howe, Kristin E. Lauter, and Peter Stevenhagen: Genus-2 curves and Jacobians with a given number of points, in preparation. ======================================================================== VERSION HISTORY: 1.0 20 March 2014 First official version of file. 1.1 25 March 2014 Corrected a typographical error in the final print statement, and edited some comments. */ /* ======================================================================== First off, we give an example of a genus-2 curve with 10^2013 points. Let us produce the base field first. */ Q:=QuadraticField(-1); nu := 2^1006 * (1 + i) * 5^164 * (2 + i)^1685; assert Norm(nu) eq 10^2013; pi := 1 - nu; p := Integers()!Norm(pi); assert IsProbablePrime(p); /* We claim that p is in fact prime. We prove this by producing an elliptic curve over Z/pZ with a point of order 2^2013 * 5^1848. All of the factors of p must be larger than half this number, and that's enough to show that p is prime. */ K := GF(p); /* (Note that Magma will let us write GF(p) even though p is not yet proven to be a prime. But calculations will run more smoothly if we pretend that p is prime, for the moment.) */ c4 := K! 2193362041724376562767453199194901105793802139712514008683442\ 7513862320949233050187008496802024358728753741371019201447366\ 5371188552088372208754201173976908524800263376459654451889275\ 7707153545905476762438858670026924217804381906896068078010960\ 7033673924816155220115406262377704019054549578781898105182352\ 0673160959157179648485460273795270424312567182885446210359323\ 2427193787031316030265312461768934999663807643609929939754424\ 0485533137067768295941563416111486368117718193945023177719568\ 4710217212014754256997491610774725725649534878872728784678133\ 1750782061094362829145994498395076286867145752581913094534142\ 9026131461205630680821981038727726312155154272694778678723747\ 3076798570070507704677282654737182870196878448266401224103826\ 9487780995050782234649493413707389769440815977118076585196784\ 2512620025279404249566108051933718841872861305110310388916030\ 8810721202259762579732804417310299679011400929488444999242832\ 7586260725655738395320434349111337829757586312213288384883872\ 9686495559180727886295693062174759472583078476454142997978335\ 5246746603951029421037610527461194723925249496635105040860030\ 6126663337807047277455358742625192460320655129861888987095590\ 7677642062032663016194073971054447937730222904300284101956038\ 4425436442689142238961178572683003079321175629094029600302445\ 8820957601537360769167142642294330457324518011562201299686014\ 4042650835351521423178908309407960249382885433028259568829334\ 0420897256733801052497661336557130524285412478697279432756589\ 5435589804776383115926180350185341268597746879620027903468578\ 3930733019314160739207837849034079716521787087435044694909312\ 1056389404850825102639404946707207301507174006497892817658558\ 5508855183269944490894093151754121645875972713805088462359902\ 3243215061187306441189924177945748673326069042313751980170756\ 2087894040394891887139668544566924019701662382806460407253868\ 2482697491277116219830764697646634398748209230792674878502707\ 3665150061576479635987854747643572775474832082916544117587873\ 6334572458890369418760375674610236568288482641594404198732218; c2 := K! 2736554243657317496968613551116974304030944495730630072930785\ 5815321877554406496268244995957666852297423740274643569761958\ 0323385185838706584312379707771341367392235499552028020265362\ 5725485166871343505501136424811660305879729184009138643760264\ 4339511276037931744145481826896188814289026466048706845317875\ 5573542244328621865452348148916988827840675019603476348680107\ 1759246182667492640678692150606254498464236379720759473820807\ 3117087942287398606455202811832285183483925135193472356852667\ 0109983011246458206401688374061519627294074537057823572185058\ 3543593508412862182230007270491857848027823510825680350277258\ 3754358718838691565228104676888401561934427141390968173201543\ 5995089255696241533291009125077048127761242332117458440730530\ 4215439117376867163187276866702344992010837562245443171038586\ 8505374219731988560186544543781869406525143273767275781147732\ 8415483241883572828460575774410395392441239600660881225593873\ 7655195418520270967947104163594329161742606158737126685157899\ 3213330557984910537073847544192244286450092025237416675782801\ 2426298488450665651762126747155107167023697361270922953093144\ 6233288836896270283473840140808811629071858098251277055494554\ 8673779099084813822892168427682178115482633034739925861232754\ 9717051381429704638642988647468424494043656928823178726119297\ 9569446190361959738446064458231338272372332189495185626554900\ 6899434965382257506286938523192221256635688260895806675091991\ 8602536071223610915670106057265972077941542609183563050308452\ 7050664992912788406047745960457401721468868322284302358149687\ 2035748749788010568633505993308754709005770873593184738248769\ 1516785750139512313661393792269804508981762598915967071124284\ 1693278012577649278527665822951618192431230616284408180046623\ 1320598576731125752126112180001035131320400577934274953847719\ 6672857390692131583630349319747213692557997896405576311657961\ 6091958162773916744187436592723124679438069126553254936692580\ 2572332184788527631947562572430061699933188659281849652149992\ 1393943290583408914426766957790370588645965137274384943168300; R:=PolynomialRing(K); E2 := EllipticCurve(x^3 + c2*x^2 + c4*x + 1); P2 := E2![0,1]; order := 2^2013 * 5^1848; assert order*P2 eq Identity(E2); assert (order div 2)*P2 ne Identity(E2); assert (order div 5)*P2 ne Identity(E2); assert order gt 4*Sqrt(p); /* So now we know that p is prime, and GF(p) is honestly a field. We claim that the curve C over GF(p) defined by y^2 = x^6 + c4*x^4 + c2*x^2 + 1 has 10^2013 points. As explained in the paper, to prove this, it suffices to show that C has a map to an elliptic curve with 10^2013 points and to an elliptic curve of trace 0. Our C clearly has degree-2 maps to our E2 above and to the curve E1: */ E1 := EllipticCurve(x^3 + c4*x^2 + c2*x + 1); /* We claim E1 has order p+1 and E2 has order 10^2013. How do we verify the orders of these curves? For E1, we simply show that the curve is supersingular. We prove this by showing that it has CM by the quadratic order of discriminant -19, and by showing that p is inert in that order. */ j1 := jInvariant(E1); assert 0 eq Evaluate(HilbertClassPolynomial(-19), j1); assert not IsSquare(GF(p)!-19); /* To prove that E2 has order 10^2013, we exhibit a point of a known large order, and then prove that 10^2013 is the only multiple of that order that lies in the Weil interval for F_p. We've already done most of this work in the course of proving that p is prime. The point P2, used above, has order 2^2013 * 5^1848, as we have seen. To show that 10^2013 is the only multiple of this number in the Weil interval for p, we just need to check two things: First, that 10^2013 actually lies in the Weil interval: */ assert p - 10^2013 gt 0; assert p - 10^2013 lt 2*Sqrt(p); /* ... and second, that 2^2013 * 5^1848 is greater than the length 4*Sqrt(p) of the Weil interval. But we already checked this, above. Therefore, C has 10^2013 points. */ /* ======================================================================== Next, we give a second example of a genus-2 curve with 10^2013 points. (Actually, three examples, because the curve depends on the choice of a root of a cubic.) These curves can be written down succinctly. */ Q:=QuadraticField(-31); omega := (-1+s)/2; nu := 2 * (omega - 1) * 5^322 * (4*omega + 1)^456 * (omega + 1)^670; assert Norm(nu) eq 10^2013; pi := 1 - nu; p := Integers()!Norm(pi); assert IsProbablePrime(p); K := GF(p); /* Again, we don't know yet that p is prime, but it's helpful to let Magma think that p is prime. */ R:=PolynomialRing(K); /* We will produce an elliptic curve E2 over K with a point of large order... larger than 4*Sqrt(p), in particular. This will show that p is prime. */ us := [r[1] : r in Roots(x^3 + x + 1)]; u := us[1]; case (Integers()!u) mod 1000: when 889: x0 := K!0; order := 2^2010 * 5^1691; when 781: x0 := K!2; order := 2^2012 * 5^1691; when 581: x0 := K!2; order := 2^2009 * 5^1691;; else print "Error!"; end case; f2 := (u - 1) * (1 + 8*x) * (1 + 16 * x + u^24 * x^2); c2 := Coefficient(f2,3); E2 := EllipticCurve(Evaluate(f2,c2*x)/c2^4); // order 10^2013 P2 := Points(E2,x0)[1]; assert order*P2 eq Identity(E2); assert (order div 2)*P2 ne Identity(E2); assert (order div 5)*P2 ne Identity(E2); assert order gt 4*Sqrt(p); /* So now we know that p is prime. Now we turn to showing that the three curves given in our paper have order 10^2013. The curves depend on the choice of a root of x^3 + x + 1 in K. We will show that each choice gives rise to an example. */ for u in us do /* Our curve is y^2 = (u - 1) * (x^2 + 8) * (x^4 + 16 * x^2 + u^24). This clearly has maps to y^2 = (u - 1) * (x + 8) * (x^2 + 16 * x + u^24) and to y^2 = (u - 1) * (1 + 8*x) * (1 + 16 * x + u^24 * x^2) We take these equations and scale them to get monic cubic polynomials. */ f1 := (u - 1) * (x + 8) * (x^2 + 16 * x + u^24); c1 := Coefficient(f1,3); E1 := EllipticCurve(Evaluate(f1,c1*x)/c1^4); // order p+1 f2 := (u - 1) * (1 + 8*x) * (1 + 16 * x + u^24 * x^2); c2 := Coefficient(f2,3); E2 := EllipticCurve(Evaluate(f2,c2*x)/c2^4); // order 10^2013 /* To prove that E1 has order p+1, we show that it is supersingular. We accomplish this by showing that it has CM by the quadratic order of discriminant -4, and by showing that p is inert in that order... that is, we show that E1 has j-invariant 1728, and that p is 3 mod 4. */ assert jInvariant(E1) eq 1728; assert 3 eq p mod 4; /* To prove that E2 has order 10^2013, we exhibit a point of a known large order, and then prove that 10^2013 is the only multiple of that order that lies in the Weil interval for F_p. The choice of point depends on which of the three values of u we are working with. We distinguish the values of u by their lifts to the interval [0..p-1], reduced mod 1000. */ case (Integers()!u) mod 1000: when 889: x0 := K!0; order := 2^2010 * 5^1691; when 781: x0 := K!2; order := 2^2012 * 5^1691; when 581: x0 := K!2; order := 2^2009 * 5^1691;; else print "Error!"; end case; P2 := Points(E2,x0)[1]; assert order*P2 eq Identity(E2); assert (order div 2)*P2 ne Identity(E2); assert (order div 5)*P2 ne Identity(E2); assert order gt 4*Sqrt(p); assert p - 10^2013 gt 0; assert p - 10^2013 lt 2*Sqrt(p); end for; /* As in the preceding example, these computations show that each curve C has 10^2013 points. */ /* ======================================================================== Finally, we give an example of a genus-2 curve C over a finite field F_p such that #C(F_p) is the prime N = 10^2014 + 9703. The curve C will be of the form y^2 = (x^3 + 3*a*x + 2*b) * (2*d*x^3 + 3*c*x^2 + 1) for constants a, b, c, d. As is shown in the Appendix to [BHLS], such a curve has Jacobian isogenous to the product of two elliptic curves. We will write down these two curves, and verify that one of them has N points, and the other has p+1 points. This will show that C has N points. */ N := 10^2014 + 9703; assert IsProbablePrime(N); /* NOTE: The correctness of this example depends on N being prime, but as of this writing, we only know that N is a *probable* prime. We are running ECPP in order to come up with a certificate for the primality of N. Until we have this certificate, we will just go ahead under the assumption that N is indeed prime. */ p := 10^2014 + 187797362797318979657122088720867057979130075182226379535243167432462173\ 071891214845638107407668103057031358419803267001410559719070272690948312\ 932655938105701264070764783812217051528674539217364952686885135638310871\ 685760555811876429053835392755311904199009974393575102861368805455886869\ 689595303431609276366993677880234822366084355616428104067237315241580266\ 640501052042703788860977173830866036443692412082906621702466271188437625\ 021821436193847263144976834583099877400812392777876947927021997528036336\ 045346041684761034551589553736515248420068965947867524885951023287722789\ 821137940384715073479084125754122106581972390916615782190594697421397125\ 731611242969939240415729168442296336712443527859130877897732242288379056\ 062588586451273725073209188142849690092879039371961703335376699840844105\ 094837102583436686374340460007320895775383284627182882449381575152387880\ 650850869318637915116927621179661955184855494658359088591718088030919371\ 031826812964809143071948384558863157816489383116846514805548584263354873; assert IsProbablePrime(p); /* As in the previous examples, once we know that N is prime (and so know its complete factorization), we will have a proof that p is prime. */ K := GF(p); a := K! 95300092314873761810395468351335848483743650607088157\ 20609640512269125539892593004816989681385927467847982\ 67868414228691524076944277610365069194936478650188607\ 48194400934254720271348060657433030748690563756260541\ 35005274608132818723231946708392486081698655554365465\ 49690863804796555463478851712716134069783517532960744\ 67104566292653124933596242978568229458181987481029788\ 78077636227944888854446264872112997475712139962017966\ 18607438278675574814681950300088855984506442378811646\ 33808213364047270039298421412725033432390637992152732\ 36798379624586008935782132565302316322085314514743920\ 87793319547919414178087743065536422871079455665588903\ 58762106272378899038026825748030892763176966023794931\ 03612054508770750059534701828319849636475932697297695\ 12019422579557145846783311733525588147486092765588283\ 97841749185440541020217260723079513502922685843608770\ 74910418262421787902477131173465203935270945410352487\ 47077311865834481149006657485521135062309976092880210\ 12996034659500769271537723374956794691147305110255135\ 04931807589078839433006597748910042530694493260450020\ 59093982242046037605066463646088645703154074351978375\ 86386582383754762539144367934487244030454963439778332\ 53313461014552414910513628498236312797943373699188486\ 07403176186625386932741728471028474250101671363852667\ 79218726732163551974549915493731551915412970247337505\ 47195738172676789480859310643089299400407241531098846\ 68020405633354901683856396627586530195027742633388983\ 06498648064284383618310150327384687558762863904627049\ 42548159765608024120399109727985597656241158050723661\ 26702309238500265771315247221416522915299103806700149\ 47819082340366313755938508003632351753125374865358191\ 30852123951604983315905464882223543567708233599597664\ 07232788561041743052175237406111818263023582457002251\ 27817470043929613435092191965331319851068617099472702\ 16214011737164235531492635060702593625068529043373239\ 97471235786765261435134322946389972514522326935943735\ 31792942796979805188144198995025435565297486892310676\ 27870638450772543290677844286620057738090927339582213; b := a; c := K! 70932721765356215477859145823206778720671479384531334\ 01050585551222983198070948721371574279337508105686060\ 39804813835158215316574435621757268194209021092790776\ 10934496405025945356665693074096722713947362270291661\ 04423619997709760894237772097040558034756125766194431\ 58520482431320387739532254242223465184894554900157913\ 16048531081690353343150287802278679319171082480187738\ 26933201902420412365539228101690842017215933066291111\ 37460192172339480699553391833713830653194855098411578\ 31374372075052732270273387706028598058034216113262840\ 86260172075697809203994383188669186183338422397259210\ 58574592144298292050870986375678901020261839170673185\ 79341667451164711698676957734565567403492510764267758\ 64909505200231405581742761227959859022319337315622040\ 84964498019120253181518316333294440041545297197131546\ 11668385089993738400263043975196326688268526001238750\ 79035661676833380323670063572342614923213634757887874\ 26163235454948194269000039371874170295095751392990691\ 83726117065119105238711621479544902877303612168093081\ 41503675753526369889997123002235517375733396078936911\ 19054576014264351163448461368625102735585194641772769\ 22450821249926596344024479105824193297795749967494576\ 07219058274748127994564184520997040063938225957876517\ 78990331558075142892809514099706833985965997140465235\ 15885890558034300503568461293907850164092348547089916\ 96998102716091394883470845782910923495607995245414439\ 14986840087238471433558348951207230270384217862871480\ 87295297353967258678886902202459886498695774987992417\ 65043681873580635054046442451608452257000513538951584\ 92771040558189567287208244347199283075936288071325963\ 04759807040791234505682138067558411413658213682669199\ 63608200375829436117878909996596701407185259966097729\ 02347618627799944024049700201248317160434797647365912\ 02634275161576258450040107066241908331747412997802264\ 16216562834976326833364397460987753859346869239600509\ 98127299342685944908164961121877173102217649402488256\ 43400566197725758039780480705978073757142146956808451\ 30201848605972585232955285552231735157101596548148005; d := K! 47861424321589483436040042462883354259815691465089360\ 84864943379863568860381065565220996223842176186440243\ 38887856666101472913103154357160816637981421600995890\ 78741018279852490702360713493621805990800997904531364\ 80413520533546416203386707059574969315987857294899861\ 93059142578830985835862663621266681230832536964431933\ 35000759653550838891586034656825233753571547177510464\ 52194570665995632151562984066286204319485152941386400\ 06549339279187319162362441752606164297158733750788190\ 98935356505319757719102665094840954672696906532533708\ 41834524958022606351619578372274433201199345504245597\ 23494582189122843474235994819945946421145815180133779\ 89207646863559381569038742344753490295305131051668393\ 29492286423912811046329690281685580912423816184366055\ 99702131142699289918231447581574351705068765922925541\ 76084434701293137218098687617530652918244899386340791\ 64265525865917934536089226819959354755599826269832007\ 18456510951584946676541340212830675662627673875220699\ 81978859360987061648802042823024039664857147965394657\ 06530075966970333183305105588723345355192844010122604\ 43005043774742565202862847202694018893850696574738561\ 07316722492680841366590523752092884973941564262286672\ 64407637322638683711978259013744091378032480057421206\ 63619868665497089018605462334777326725791599663316879\ 23627372110323520502056559137321121339042013140499218\ 45602944669452807299488797175111747717019833231619335\ 25257659105919452602848850981284640154596380277317962\ 22803990866049451848281210898491749426032113480906416\ 70473925878459087532220976436396673727111437437932774\ 59126389334960360993802673265979093584316964617694303\ 69527846111016681490891641967923052760875605074253603\ 54802814684004313296919276257342719636514872357304383\ 80937017158478463093086293630275920934818180058182197\ 27360141896486195516458229971061321025353236435141986\ 35335750505429310404511927924689726553292139920492576\ 00912668592572776204243374572970569706641205589977029\ 86120918438712932852494687493506647337918379583974894\ 32618072122074832744885079569280853340637692001686397; Delta1 := a^3 + b^2; Delta2 := c^3 + d^2; R:=PolynomialRing(K); /* Here are the two elliptic curves that the curve C maps to: */ f1 := x^3 + 12 *( 2 *a^2 *d - b *c) *x^2 + 12 *(16 *a *d^2 + 3 *c^2) *Delta1 * x + 512 *Delta1^2* d^3; f2 := x^3 + 12 *( 2 *b *c^2 - a *d) *x^2 + 12 *(16* b^2* c + 3 *a^2) *Delta2 *x + 512 *Delta2^2 *b^3; E1 := EllipticCurve(f1); // order N E2 := EllipticCurve(f2); // order p+1 /* To prove that E1 has prime order N, we exhibit a point of order N. */ P1 := Points(E1,1)[1]; assert N*P1 eq Identity(E1); /* So, given that N is prime, p must be prime too. */ /* To prove that E2 has order p+1, we show that it is supersingular. We accomplish this by showing that it has CM by the quadratic order of discriminant -7, and by showing that p is inert in that order... This simply means showing that j(E2) = -3375, and that -7 is not a square in K. By quadratic reciprocity, the latter condition is equivalent to p not being a square modulo 7. */ assert jInvariant(E2) eq -3375; assert 6 eq p mod 7; /* Thus, modulo the assumption that 10^2014 + 9703 is prime, we have constructed a curve with 10^2014 + 9703 points. */ print "The examples have been verified, subject to the assumption that 10^2014 + 9703 is prime.";