Date: Wed, 11 Sep 2002 16:54:29 -0400 Reply-To: Reynald LERCIER Sender: Number Theory List From: Reynald LERCIER Subject: Cardinality of a genus 2 hyperelliptic curve over GF(2^4001) As a corollary of our current understanding of some new ideas due to J.-F. Mestre to compute the cardinality of jacobians of genus 2 hyperelliptic curves defined over GF(2^n), we are pleased to report on a computation that we have done with a first implementation. The corresponding algorithm was initially presented by J.-F. Mestre at a talk that he gave in March 2002 at the university of Rennes. He generalized to higher genus his now well known method to compute cardinalities of elliptic curves over GF(2^n). A written report of this talk is in preparation and will be published on the web [Rennes]. There exists several other methods that we are aware of for this task. _ A first method was invented by J.-F. Mestre with R. Harley and P. Gaudry. It is a genus two AGM algorithm using ``bracket products'' [BostMestre88] in order to explicitly lift hyperelliptic curves with (2,2)-isogenous jacobians. Their implementation of this method yielded a 4000-bit record [ECC01] (6 days, DEC alpha). _ A second method is due to K.-S. Kedlaya [Kedlaya01]. It yields cardinalities on hyperelliptic curves of any genus over GF(p^n), p small and odd, thanks to a trace formula on the Monsky-Washnitzer cohomology. A generalization to the characteristic 2 was recently done by J. Denef and F. Vercauteren [ANTS02, CRYPTO02]. The first figures given by them seems to indicate that this method is slower than Mestre's one for the genus 2 case, although it is quite practical for cryptographic sizes. _ A last method is due to A.-G.-B Lauder and D. Wan [LauderWan]. It can be used for a large class of algebraic varieties over GF(p^n), p small. Nothing is really known about the efficiency of this method in practice, especially for hyperelliptic curves. This new method is much more closer to the elliptic curve AGM than the first one implemented by P. Gaudry and R. Harley. Basically, a genus 2 hyperelliptic curve over GF(2^n) with ordinary jacobian can be easily lifted over an unramified extension of the 2-adics as a curve of the form y^2 = (x-e1)*(x-e2)*(x-e3)*(x-e4)*(x-e5)*(x-e6) with, modulo two, e1 = e2, e3 = e4 and e5 = e6. Then, let A0 = \sqrt(a/d), B0 = \sqrt(b/d), C0 = \sqrt(c/d) and D0 = 1 with a = (e1-e3)*(e3-e5)*(e5-e1)*(e2-e4)*(e4-e6)*(e6-e2), b = (e1-e4)*(e4-e5)*(e5-e1)*(e2-e3)*(e3-e6)*(e6-e2), c = (e1-e3)*(e3-e6)*(e6-e1)*(e2-e4)*(e4-e5)*(e5-e2), d = (e1-e4)*(e4-e6)*(e6-e1)*(e2-e3)*(e3-e5)*(e5-e2), we can define a Borchardt sequence as A_(i+1) = (A_i+B_i+C_i+D_i)/4, B_(i+1) = (\sqrt(A_i*B_i)+\sqrt(C_i*D_i)) / 2, C_(i+1) = (\sqrt(A_i*C_i)+\sqrt(B_i*D_i)) / 2, D_(i+1) = (\sqrt(A_i*D_i)+\sqrt(B_i*C_i)) / 2. Then, J.-F. Mestre underlined that a formula due to Thomae-Fay leads to the equality B_d(A,B,C,D) = A_d/A_(d+n) = B_d/B_(d+n) = C_d/C_(d+n) modulo 2^d and that B_d(A,B,C,D) is equal to the product (ones chosen an embedding of the CM field of definition of the jacobian) of the two eigenvalues which are units modulo 2. For d = 3/2 n, the coefficients of the numerator of the Zeta function of the curve (and consequently, the cardinality of the jacobian) can be computed from B(A,B,C,D) modulo 2^d. We have done a first implementation of this algorithm this summer and were able to achieve easily a 4001 bits computation. Non critical parts of this implementation are magma codes [MAGMA], other parts like the Borchardt iterations are written in C. Arithmetic operations are performed with the ZEN library [ZEN] built over the GMP librarie [GMP]. This took 3 days over a network of 6 DEC alpha processors (731MHz). This implementation can be clearly improved in many ways. As explained, the computations involved are very close to the computations needed for AGM for elliptic curves. Therefore, many speedups implemented by R. Harley to achieve an elliptic curve 32003 bits record [Harley02] can be adapted to the genus 2 case. The main differences is that the accuracy needed is 3/2*n instead of n/2, that three square roots instead of one are needed in each iteration and finally, that the computation can be distributed. Details of a computation done on arbitrary curve are given at the end of this email. A preprint about the implementation and the complexity involved is in preparation [LercierLubicz] too. Finally, as pointed out by J.-F. Mestre, AGM methods for (hyper)elliptic (footnote) curves can be explained via Theta functions [Mumford84] and this will enable to extend the algorithm to the genus three case, and maybe higher... Unfortunately, the complexity increases badly with the genus. R. Lercier (lercier@celar.fr) D. Lubicz (lubicz@celar.fr) (footnote) J.-F. Mestre pointed out to us that AGM methods should work also for some classes of genus 3 non-hyperelliptic curves. References: ----------- [Rennes] http://www.maths.univ-rennes1.fr/crypto/seminaire.html [BostMestre88] J.-B. Bost and J.-F. Mestre, Moyenne arithmetico-geometrique et periodes des courbes de genre 1 et 2 Gaz. Math. No. 38, (1988), 36--64; MR 89k:14072 [ECC01] P. Gaudry, Algorithms for counting points on curves, slides of a talk at ECC 2001 available at http://www.lix.polytechnique.fr/Labo/Pierrick.Gaudry/papers.en.html [Kedlaya01] K.-S. Kedlaya, Counting Points on Hyperelliptic Curves using Monsky-Washnitzer Cohomology J. Ramanujan Math. Soc. 16 (2001), no. 4, 323--338; MR 1 877 805 [ANTS02] J. Denef and F. Vercauteren, An Extension of Kedlaya's Algorithm to Artin-Shreier Curves in Characteristic 2 in proceeding of ANTS V. [CRYPTO02] F. Vercauteren, Computing Zeta Functions of Hyperelliptic Curves over Finite Fields of Characteristic 2, Crypto 2002. [LauderWan] A.-G.-B Lauder and D. Wan Counting points on varieties over finite fields of small characteristic, preprint available at http://web.comlab.ox.ac.uk/oucl/work/alan.lauder/ [MAGMA] http://magma.math.usyd.edu.au/ [ZEN] http://www.di.ens.fr/~zen/defaultind.html [GMP] http://www.swox.com/gmp/ [Harley02] R. Harley, Elliptic Curve Point Counting: 32003 bits, email to the NMBRTHRY list [LercierLubicz] R. Lercier and D. Lubicz, Mestre's Extension of AGM Algorithm to Hyperelliptic Curves in Charateristic 2, preprint [Mumford84] D. Mumford, Tata lectures on theta. II, Birkh\"auser Boston, Boston, MA, 1984; MR 86b:14017 PS: Computational data ---------------------- Let GF(2^4001) be given as GF(2)[t]/(P(t)) with P(t) = t^4001+t^137+1, let H(x) = x^3+h2*x^2+h1*x+h0 with h2 = 0x77F30C12DA444C438BE68243930D8500A7E32FB677C4CFAF67C39F9706080F0\ BC8A58FD7F3C6CB0DD6EC1040836413A0A8D9694741331E5AD8FEA22457829BDD45F0E\ 94CDF9BA9CA860934804A486844770696B6BE399B22BFB954CA987F60FABF698C5F4F4\ 397AE15EA5E2B24170C1BACEBAA5A3757535830EB976EDE4A0C96EC721AC3E7332547E\ E1A567782ABE6145EBB81585589605BAB8E2F8332A0BB35A2A392E43EEA490C419FA0A\ 680BF111491C4EDD421464A30EC22C4E93779EC5A42058BA3E3997297F8C90C0DE4880\ 9EBFB4827069E97C95735EFD3F0DDA416D42535B56545E097A884D3F82CD04EDB5F918\ 1497B1B164C6FB3070E8DEEFE5D277AE373D796A09410AC9EF8E839FC44BBBFC523C6C\ E2A7B642649137C5BAD13335BB8035A2530C925475926B7B533225D1BABD8F21E150A8\ C0C4F1F1F89833AC698C3184C064A11DEBA3105E2D5010EC9FFA291336015DF68C0964\ 6978A96A0C32380B049BDD9068A0DE50BB13D65C344483F7DE523025146B643252E9FD\ D886300DAFAD9A62193BE9920A933176C43EC6B2D3BA3929AA85924795293FC70DCD32\ 5BB707525679B84AA054893B38FF39A8475053F83597D0AD615C08CEEAFD87015469D0\ 117F1270F42B9D1B1EE7ACF3980517007F5A0D78F663F2B08F3FED516836AB8F44D474\ 2078AA5A8CCE84F54719916F6CC, h1 = 0xF6545A582DDB1EC0CCCD2D77DB187E7CB2D9C250B44CD6D2B9DE285B8DB67D7\ 9A314E1AA2B96E73D175379863FC5EC5C684D75D4A664EC2BE3CC20D8B3834629F178D\ D5E07DAAF48B9CA0F81DAC87BF25097CA1688BF0015AB40287D1D4E9003F496C4EFF27\ 29B248EB97F2AD04CAC01A9AF83286459F74EBB325A7D89DD31C68C818AD942B7D4702\ A23F2D6300F614EB229DA6B1CF8B90EA601E3DFD88A54D8820E2AFBFED5F7420D0DC95\ 41715C2B7527B8B1E79F3F226A4197F0D83221124449BADED1707B1450E73D0B5E9C5F\ 01AE7ABB8D446C04254E4FDF89EFC420DFDB74AAE313E8369A11E161C9889107F3E225\ 2A9D9A80F733A976E0F02F74BE82F9381CB96BAAE5E4907913850E4A5C67BC0020E502\ 899B83376576D979B0AACB6437817C6F97863FAF623ADA17143F6E6568F55B08A82096\ BAFD59BAF2DEB04CA9B79CFE7EC7CB29451D8A7530D43E9CC09793CF49869D838C8F16\ 14626E6E28D696E386CE21B0C16D2340EC52B94348551E30F85B014E52F09A674815D4\ FAE8F0930F8AD1BB41A72DC2F7C4AAB4B9DC461370CFA1FB901CECEF185CE75C35064D\ A0EB6009402B1F9EA12CB8F59B008B716148561FBF39488A6D91D7B9F3D7EF6DE77D7B\ 982B2E31643C14194B5FA0C2014E6D3D1F1DD12020D56BB80DEAE371A0A2387B418973\ 861968A00E58B9FAB5CDD1F1161, h0 = 0x2532FFE07616DC69577EF6B8D987CF0736F3F0C9CA41E87E881A15F4E6A7EFE\ C8CA14E720E30E88E4016B68BCF74EF04CADD4AACC41E5E042199984C0560BE0A8085C\ B9888788C0AB9127A7DBCA244FA20A7E0B01796702EBC65E8D94360365990D5424AF84\ AB0D1FA859DAED2069C8BC5B839E19D57E62402A466D33AA718EC607BFF9F1D837C6DB\ 8D0661D85C1CD29662920AB6E1DCF64CB4687CB6885471AE79A72C03AE955C0E5FAA00\ DA643EDB3BB4985F42FF1EB39963D518F3FF0F580D1981B22B0F3F97EEB10DECC457DE\ 3DF25BD9CB3AAC4EEDB3FF73B5F8504007FD21FF1A566E20FF280A73E3C8B12407628B\ 5D0AC9D5B7125541E3BFA0D252E33C408F8C97F2FDFB68EEEA22FC79021DBAABCCC3CC\ 89D93B8E3605D5349C22FEB0DC38935AFD76B66FC633516C0F96D6497C30460ADBDB49\ 3FBA40E22548157A463AE2A5B14DD7167964B984CE69725DBE35561D008D299A1F7A4A\ C33DB65D83C64149B5DD644AE7F607C955B7BECB8EAF10FA71E2C97A6FC81AF8A4A376\ 973E10E5EA5F53274A66EF67D92F8507084590562C2D9EC726CCAF6BA77C05FB4FA970\ 11AD9E13694E0D34C0AE7664EEEDEC34E69611E31FA15C62C1D17757C0F049EDAB1630\ 43E7636431336A5BB5FD2BBF4F4CE3778756984503C9B08117F528D449F31BDC68C64B\ 233DBCB6EDDA59A38E05E09ECC9, let Q(x): = x^3+q2*x^2+q1*x+q0, with q2 = 0x73378AFABD8099009E803D56ACB6E31290B1B5A615CF78C3FBAD28DAB4F183C\ 0CEBA6BE2ADDA6CE634DFDD2EA40717CB83C0C44508E3F546480A47007B82C511A0CBB\ FF4E98DED25EA7ED768198579E9A89356979BD99CC1883929950DA119354C33F3F4DB8\ 4534AB36D6457EF698E662266164F20E66DB0ABA81270C04200E3D80E5701E7F66EB1D\ 6F7BEE7A88B0149821E995FA5CFF6689A1E460A7C671248F9782FC68E800A961A834A7\ 687F0CF32E79F70EC524A3BEDCA05DA542DF817EBC51FD5B5FE04832FF150FB657E2AB\ EC67A8FA847DBF5566A89304FFAB36ACD12F57139EBDBBB2FFD8026FB2779246F4737F\ A22995807859CB0016174DEF949085C9D29D7FF1C5AD715D503C38F08F21CBEEDE9D7D\ 293CF7BE30B1E53D5CA11B4AD97E7E598FD4FA5F2E1DC638E812DC86C8100B9C8FE4A9\ 14B5C9BEAF877985C6A44D959854D79C2F1BACC486EEC14C6D1463FB6DC671F2DAF9E5\ 4569971607D17C63B043A069630DD7EF6D7EA512AE770C502702D21368A85A51E7A44A\ FE315F0A94FCBB3334AE4D02470A8EBF43E168863937902414BBD100907333BECCD2BB\ CCB98B83C4BAB900B6CEFEA288B0A5D042AF699C1137B4519C03D74E7ED9F1D3D23350\ 7651659C75A956B6043FC05F3DB2DAE6A7EA0C1194BC84B08DB3AAD8876B79CC658243\ E69E6EE125D07470685805E93F5, q1 = 0x9BFD8300685B81FD66463B2844DB3D657A2788BFC3B40AB7BC2AC3728E8A570\ 6F708FE69D65D8CEA130AF3962D57075488BF37A09DB8FA41750B3653BD8DCC757952C\ 71E23F16A32C7B75AECF16DE3DA3C36D3FFC488D12A7DA21317D879642564CCF0E5B2E\ D0F00A2949675C2DEF86F3B0A4C25054C0CEE74DC178644DCAAA5C8B4B77727672C962\ 8D2B1273DF525A88EBACD4342C72BE58B918740F1BFDAFE86ABE653612117A9872C771\ 6F8F0053DD6B1304D6DD3F4E875326371F198AFCBB74432F603C4755F49EAB42BCBE3F\ 872C306B7AF55B6175EBFEBCF98CB50B24F7313EB870B3C46194006AAD201AADBF68F9\ 25DA635F5EEB5F86329918E830A23782C81D3B3173DEAEC61B996C801CF9060F156F22\ F5291982E7FBA74D6700021856E27946737064237145DE932C35BB53659513EE392A0B\ 3CFD3C675288F37B50B0815382A424A5135D35780E1811A350723ACDA9A446F47BEDCA\ 85524A404DE8CB0C18167318C8993F492EE5CAD6D3BA50C0C09DCC5BBFD0C2766302FB\ FC0152760AE5F67DD478D2CEC57944E5C81A7CD0954A41120A3F9E59E84D6DFF142AC7\ C7F497D4DB1B2461C9453B2AE78C26ED2183A1C0F41203A2458B44321213DA7848DA2E\ 44AD6CAF4622725036B43441CEF557AE0A7D3DE9D5168BDAC974979D52BC7906AD40BA\ 53A58AF84BCA96D5AC400D5A43F, q0 = 0x880749CCA2B9CEF7C3E6A513A661951C36F70D2BDBB61DCA9BB425EBC4590E3\ 27E2830B61FE39435BA5F3FD99F4C361D36FFC64787CC9E9E68BC30283C8282C104A4E\ 66518EE3A909796957B2A86E2E911023B08CC0AE284EE2905C902AB166E98B221598B5\ 764B9D5C27E1801CEE280A3C1801ECE21A7A0AF6A681B4F7DE7BE3760FFF1656B9F102\ 5D95E7CD3FF26D85FE076335B8379D5A42C5912CE512215172ABAAC558DB29953631CE\ 9651301D924B261426C73289000D8EA5BA2BAF94A444DB74AF10FB80158C3131159DB3\ 10807A6A7290613A6FE8E1DED8281994E819020E72EB29C36D12C91C12B2A476402222\ 629AA7F5EAAB859A09AAE4810098BD5F620FDB36F47AF1FB73BF67D95D6DF0AEF6C5C0\ 1B460B61D4B75D7F255F372159A8A55A24DAA0C54053A2735AD5876E2CFA673F33B5FC\ 1885730293840650771F53ABFF3846F5B27F6C4475F52DFA594DCC78B2CA92C6089A2C\ 32364BCCD945FC30C41B76C75B09A6D11F9E7975467FD9C601910D9F464D215EA6FC43\ 7F3141B0783D89863711E1F5728D2585F9490DED769509E62F3CC6604015A5617BCB77\ D3406888520F9229901DE5588F62E6DC3A584962E1DFFF608732219FC9BC38D4EC3238\ 3677E5D415A86D0DEF91B0D8B962F4191B36C7E6ABEC18DC21C8641ABE943D6E533E56\ 9221E379E2D129B89593B6E648D, then the Zeta Function of the genus 2 hyperelliptic curve C given by the affine equation y^2+H(x)*y+Q(x)*H(x) is equal to X^4*P(1/X)/(1-2^4001*X)*(1-X) where P(X) := X^4-a*X^3+b*X^2-a*2^4001*X+2^8002 and a = -0x289148EF8239A294E31A0F64A238D3ACA56D3D2018DFD0857194EC27B5106B3\ 4973B7ED5D389F4E21F4330C1A6D7A85B9B1E3CE532B921388474B7BFE8DC6C8FFF32F\ C9A4A387FEFBA2DD5A4F670DC606B7123A8CD9E5617F1DFBA1011BF77D355288F3D913\ 90F71D0FD77473107DD66E088DC807A0E8B031FE68AB5D7E898FDD3405A873E10A09A9\ 1BAF042144161CE456E60BEA6B3A952B642CBFDFD3834CFCD0B4EA5FEAF6C54F5FC00A\ D89ABB7CF67FFE90950FFE97D27B7DDBE1F6985CC2B9ACA2E94E54D65BB48746F952F2\ EE940D53459633CBF07DBFDDE2B31807B0255892FB2B634028C5D82AAEA08A4DFA05F6\ 3B98977B3A8F59848E, b = 0x48191E88910C2CF04A702D6AE9E272C45C38678C824C738B838646AF69A00782\ D6DE8A3442CE6617CDC4C74EADF56559FA655BD059F217F13092E6C520038CB43FEF41\ 7E025ACE0EAC22DF433CEB502B4F79F345409FA54B6A39155120B6DE82CCAB894A91BA\ BD28D751E95CB8EEDB76C0ECCAF200094854DEE0FE1FFD4DC14E21A0ADF7E7A05ECDA4\ 30F77E15A56965458E80A26D50A5C13295A3C830B3AA22440E10A25BFED0106D9E17AD\ A6B1385F169E8EB17AC84F0EA883B92D75574099DF551DFF682D401658C5D11E04AA53\ 1AD773E18117FF80E4B71FD23916B553B048AD23A417D04592FD6BD543A6AFC0D469F0\ EB906AC5C1EB20982E6962331C215FA6C28D4C6847464F94817C3336D0805491A52F91\ D94D5B1B253F5D3387F3BB253B41A7F0A76CB5144D969E064421AF2DB0A4DF6038B122\ 17F64084894175FC2F3E5DF67601C3BBA48BDFB112EA89AAD32F1772BC3CE84947DB34\ 1347A4485E02EE4693582595B399634B088CD4FB406B943F2CC70897520DF7B7E376DA\ 75FAE0B0C6CB27162380C55E2549D5CCD4980E94E150F0D34802880D59F26723F08DF7\ 1C448153092A578112798715FB6759F0D9E0BFA6C5D7B6F8A704B60EF929190088CB14\ 33B3D23B62E3C5A610391A6409DD3809C84574AF3EB39CFC9F0E5B8F387AF3D9737379\ 03CC5981AD52C6B3102539D0645. Consequently, the number of elements in the jacobian of C is P(1) = 2^8002-a*2^4001+b-a+1 and the number of points on the curve is 2^4001+1-a.