Date:         Wed, 11 Sep 2002 16:54:29 -0400
Reply-To:     Reynald LERCIER <lercier@club-internet.fr>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <lercier@club-internet.fr>
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.