Date:         Mon, 13 Jan 2003 16:00:46 -0500
Reply-To:     Reynald LERCIER <lercier@club-internet.fr>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Reynald LERCIER <lercier@club-internet.fr>
Subject:      Genus 2 hyperelliptic curve point counting, 32770 bits

We are pleased to report that we were able to compute the Zeta
function of a genus 2 hyperelliptic curve defined over GF(2^32770).
The software that we used is the same as the software we used in
December for a computation in GF(2^16420) [LeLu0a] following [Mestre].
Details will be given in [LeLu02b].

The total running time was about 8 days on a 731 MHz Alpha EV6 CPU.
The lifting phase was done in 7 days 22 hours and the norm
computation, in 6 hours.

     R. Lercier (lercier@celar.fr)
     D. Lubicz (lubicz@celar.fr)

References:
-----------

[LeLu02a] R. Lercier and D. Lubicz, Genus 2 hyperelliptic curve point
counting, 16420 bits. Email to the NMBRTHRY list, december 2002.

[LeLu02b] R. Lercier and D. Lubicz, Mestre's Extension of AGM
Algorithm to Hyperelliptic Curves in Charateristic 2, preprint.

[Mestre] Jean-Francois Mestre. Algorithmes pour compter des points en
petite caracteristique en genre 1 et 2. Available at
http://www.maths.univ-rennes1.fr/crypto/seminaire.html.

PS: Computational data
----------------------

Let GF(2^32770) be given as GF(2)[t]/(P(t)) with

     P(t) = (t^32771+1)/(t+1),

let

    H(x) =                    x^3 +
                 0x437278323b*x^2 +
            0xd996a1ea823554cd2*x +
            0x37ed3a99f22ab977006a0,

and

    Q(x) =                    x^3 +
                 0x3335313734*x^2 +
                     0x4272757a*x +
                       0x4345444558,

(where coefficients given in as hexadecimal numbers are polynomials in
t), 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^32770*X)*(1-X) where


         P(X) := X^4-a*X^3+b*X^2-a*2^32770*X+2^65540

and

a = 0x3c8199b9a22477da89524c6f2a12ac36fb916bb1ae87aa519f8c5267ff7e2b7\
9479f1fc3a75e30b0e7a665702fd8bf52c386e680070aba2a9a93ab8d3dd6e7be8b63\
f1148372b021e9732eb72721b97e8b0938c2de35dc800130cd163fd4a6dcada997f22\
6ed1fbf9254d307ec4e4bf7208db040b6e15f8afdf8b631d9429a53e2b246e8717cb4\
176b2aebd44f642ebb4fe2f77ddab5cd2bac6382cb2b20f82702d9cfe08a6328ece90\
6d7e5a33159eb0f92b28c064ac1b0f72604f1b5fe705d4910017db517484b8e2e1f5a\
05920f74f3faff56929390d2bf1f463ed4575054c4a59b8dddcd9a5e614190cd10ecd\
c0f2fb7c595d29d8343d9ba796d6f51e9c7f47f301cb149532558f593a96b33f60ccd\
6f7ee0b9b08126fb8960850bc5cb014d7b5176758e026d136fc15249e2a2201288198\
abe434af235d980dc428c74480c0ccc801c11033bbc32b810a01d7b6d6a884b369976\
f24c6f437ac3d1c907cddc8680662111d02dc2ef5d76379d0f94f72882971715ca21e\
160b3dfe9195b8bf8afc4a7d8cc0eb78ccdb054391b74eb010e679488824e082e12bf\
4ba90dc50fbe7c7f48ed1c2a655582bb65b1a9b8d6d400a54153a054a74d9fb752482\
8ce08570978ea2ffd58afa677ac55a532510b8f042c0dc2f3578a4fb04be2ac311de3\
7ab2d134051de49728a9d1becd78a462c13d23eb3c4481fcbd8d4e39c38ee59c5ce7c\
92d572bacce51d4fd8632de4b15ba2334b955f7fa6f5a7a24dc0c88b392068c0b2352\
85092e0e3aae65c50b7b514215b775f956854715e5c33586d206500ce364993c43c26\
d152cc322f973d26c424bead42c0207f5867b019007a4e5f6dec9d58fae7766b8bea0\
7aaf6515eb00767a75838fdccecdde242b18e677567b2c64e8b09341e6f46f141bd2e\
a81e2fa4ec622b9b1024229aa28a4602011a269c2f7f21798c2c3542f7f37497ccf50\
f138769c34f38872ebd4265b0465e714d59f902a9a55b74ec1c8ad2d81720355edc0b\
30a9d83eeb7f6ef82020a409bffed312b742efe6a6346ab0fb578a8e09a075b3914ce\
0a75febcd52d73ffc0f13c96d43a4fe7ffda47759ac6c240037e1ea0da5eac8d63df6\
5eb81ed740528c373854f7dd4bd4127d58a01f95a4b8a309ef097b603a208d6b5bca4\
0399b678bdd2fbe5fd0d546f406ae7f1dcfc604ddd5b6b7ad868152d8bf885286e280\
f872f29256d9a6bb3ff98a5ce9c87491fcca80b03f0ed380f9a6c6a58656526bb2d2a\
07510ba843869e041b3fee497140bf6a2f451b5f83f4204eb85b373c64e42e1dc0ccd\
1bc9e7ecb24da24fdbe0ae5618b74e705325070936189986afb54990a626fa8a6f93e\
88e1f186974b37fc0c9da718b21b888b8a6ac8fe657bbf893b55969a507baa089280f\
88175dc25535ea2e6841137555a7ea37cd4a79e97178e2dad55f73fc416608898f96f\
13581d09b30d0d2838b443a7a840ab9a5b8602890ef7ca7eb156414ce6e8d76e11353\
935c991b3ee417b0f0662e42e1a061e5e9eb04f4d9fd166b915198bcee332b5dec343\
8f3c25f99e5331a9c8ae3639ed050de59c3a14f0a31a469504571c0c06afa7cfbd923\
6267f0c01b028fe08e83a34543268ae5b2b8e9c145876a74c5180babfd65621bfa1de\
8acc2e3c19a3b7a674c33d2576df8437e4e90ddbcb06a427e8210396df7583914ad5b\
f617cdd3a00d670153a192c58bed51660b74e112534dab3b2aef6e6bd68e84b143c9e\
10acafa17131800452a70924dd009964db28db2fdce61cab1614bd08a6ee1de2747bf\
fe03edc917de92e2414a519170173dcaf07cfb3642b77eb0235fe9c29debafd5010a2\
e0347c24a79c60fa6833e3a690083da7a1274b294778970d48d772a348ddf69cac806\
f8496471e573d01eafc4737d179f25267a915220d4c7da444ba1038abed85ee7d55d0\
341c4c5d95620d6241c9cc86a9bbe1401b14d107b69bb91983a421ffd8a1595733e52\
86ea9ffcdeffae0e7b36b79fe87eebc50276e12aea83837fc03a056bf1ad5acdae6b2\
4cd61d57fb53e59022aa6c8fd484fec28d36d913fe0c2fb262f899089f787ce1248f4\
24b8938bc113438826d43c1e032bed960a5ca8273a9df8ff1bb3b6a831d53e43b457b\
3dec791db75c7bc891727279ca4b26d12a0fe04d073b319d910142335059e83757056\
300cbfa26db341b446d03539e249ac89747ef5c1e014d1cd514d1e4af98663058ffd2\
b3f66563144c23b69e66563a11e329b41e0820b23ac8aa198f621fbdcd138ea4be127\
0abd524e3c1cf0f152a5d722690c7cd4557d46b5c4b87328634e7a2eee1c8b7a91f37\
b590baa7365544527045890e1048a56e430c1d4f1d7f695d69e108e9137001120aac0\
0099e3b4f55ff8022d0e55dbb42c4a65d9aa2a99be63f168de23acd5c2c1095696d1b\
b1a93e1a036996544e7014e6e7e184da286ecdb32962ee5f54689e6bb1cb9af5367e6\
310c148882c4102c4b28d4b5359a71bdd22e5086579bf5df9f2c2391d9ce39f438c82\
374cc137243935294d8341e1d2b5ea05ef0d66a6a051e0760bf42b4d14f8d9be4d103\
822e5ab06c86d884fffc32c7dd066b01b36a63f1eb28e265c026542150670598b2088\
baf969f8d679b365a897b8d2e151e13f5052dfc8ce19883c64dec43667e7d89ab005a\
52c5a85c28b94682784671d6cdf1697cc93b36a106870bbbd0b8862629128c39d4a59\
6f88c3974f148b74f854a55a8f9f5ff5a12871bd8df4c90cf50b11eb20e05d74bd79b\
df18c9f7ee82f4b7083de40385641d1e7b76d9a999d7b0db77af37532a6ce50a3bd2b\
2d70d18348203d53370e711ec7390f9b08c08c1a70c6cc7a1a3ff01bab008c196036d\
a68de7205f1f3f29168bd11e276d8e0a,

b = 0x8b08cfa791ead84f519006083dbaff771df2543d7db6b0f1f7c8a16ce0e9d21\
f95602e8897e71cda08317299f730c64e3d695004a0c37e1f94b17bb6e80b9c40f665\
468ada6f28709b2d4702bddd6293dbda5ce8d58df3b751c59941757deee0ec843c533\
2a0b4a19cf957144377f668cf211f8d20f70edcf235226c4a99e0d4a2df8b15e798c9\
49576d5f485161dd6078bdea6ed745074b314954508eef7c29cb89b267c8b220ccaf0\
39f6fa766de944d1ff96411a31a65a27ae8c770356c3b1b449fd3d49c6c79a85a0021\
2858899fd4ee581c4089a190105df4cdac30eaffe1624a3771a153b86a3a8d0049f75\
18f11c3892dc9db6fc52d23f06a5c57999a8b37d4e4890f7c4c7156e02e36ed924d00\
cd022a691ecdb2a22eda92a9105b55e18662602c033b4f18328569e7c383c0e8e65d0\
4d4690de52a050eaf0f2c57df8cfd32eef3e52afd1aafa2fd7ec0cf5c03df673f763d\
45ec00f84c5d4552cfd89846699379461c356ee00076558b9dc03c0f2d9b8a5d2dc8d\
94a82f6aa62d769f096bf8b709a7bda99e7a3cb3950a6e7219f86ccf281c30bff4e84\
fd680eddadd63f1f86d09c8da0c5f622e810f6d308aeaf42355a2754e6779bb2550d9\
bdbedec7e64e51fcd671266bf745bcae7c81c1ae85a281434966d3145481fdee0dc97\
531b14259b46a0124328cf2b3d11cfd7c6a38891cbfdc38dadad51a06fa5663340188\
8cbbc1d6025ba131851d78a733a491e360e8dad9466327830beb83a98c6fc5f8c9a77\
21364cffcaf94b530fd5e26f70ee73d7be0329c60746dac2331e920dc27cec2fc33ed\
33fef131f14900ad2ffb231845fb255becc5e10e5f0fdc6b4c0a584dc4db000bb5431\
ecc26c1c8ff018b3720a5e9006c8e82a31d75753415dc5b9dd07a2419396bb8ffe9bd\
9d4470662503c3ed97c935179c71c8abdea2d2596007840c2a0f0ae9bdb34c8262619\
b5c6a10dcb5c0e102992258a35f516862eb63b7a5fd6ee17ed9d24e939763269eccfa\
ce54afb0d383a22361c9e3f351d8c76664be1a2ed511da5932c2434ba5e392788f94c\
6b6c875795d041f47740fa4da6b7aea60b77d09af59e9728000529db9d13b237e9c91\
5a32c6d70cdaf0cee19013479c3af1b00b0f2725f7742aecc4efb40c52e1a5e928296\
5ff9a92a426d81dfaa8414b0b574be8e0a961e976d92124fa424dd947a87a2f2a1bc1\
f6147fed28d00519ec7c6884725a2a60549dc59e0ce86af22955336b78521e2144398\
39eccc457754db6fa6926c6fb6b77e8abe848feeaf1796de620938cff558f0607accf\
7d34201bfb55b7f20b606b9dfd5e3a7e52cc93559ba19dc7289271817920b17fa7961\
c5395ad1d526c46dfe234a37de5f6dfa088d3875a83217adc2d97caa9772d94eb6b00\
5a26b74208fd87d2d421d52ea7d7c82dc143e7ef2359cc01ae30dc2f247424afd0f9c\
cd2daf5ae68aeb560757cb25eb63a4d63cd59c2958c87d8bbd92ad87446d8e01a8dc1\
c0cd7c7980a2b4364df63563208ac9afa2270b09f47bb19472b2d4460f371ff2c65b1\
cc020201fa0f50f6cc6b720267dd7b9d1e9a3dcb23139f3faedfbfa103d520368091a\
c522988972e88cd6b08680e33e03f76cd76ca6ad9955a917b0aa3c7c86d8391bf4bd6\
b2f3630af5bad3dbea47e3daa1cc696295d323e7202f15edd46699593537826676d38\
891bb2db3ac79568d7784cee37d84af0e2f33cbe15acd6edc63a5db71782de031d6ce\
591f6cfb89d25e081e86f73a2df02cc1c8763804d9864f21179d14027bf147dc3764c\
891dacccbf5db217032b0f3f269d393363898a6b76307fee7d91089fad0e5cb6ae8af\
ca3d61d978b3c5f1c5454fca2ff34c4d63e2e3e25b8f50f7711a64e31eddeb31f63c1\
0ad8d4e94556011cf2882609f2f44b5bb59af433cbbc60eec3a9e9a67838b2c27c08e\
b5b5dd3c3d630c386d5712eda317ac49bd7336c3c151ad9072f60668ac6ce0b2574ae\
dd75d3d1489c14b907b9cc56be0e303e83787083a3a73f4ac82420f0a33750743b143\
098a1e0e7cd2f0ac0b96c14a30e7b3ce1218f211308e77bcf623346bae4e1c8e058c0\
49369b46710acbb43e3b2472cad8f65462e92cf235bfc3cac9723e2bf02da25179668\
07bd0f0b8d3b0b7361b0f3b6462436f6350ca8a14fc365d542e8667500a1e37303420\
f79c380ea21c0fb087a016430f5577bda553afd37d410d0117e8c84b35d9d26c04748\
b70ce982d210183c844755fdc36b217ad32c28daefd1beac0a3c4c4b4ebb5a4ef07ce\
795edd02b8fa338a545e91bc5f79864e7052895317f0e4e02dd29f07021db43702fb6\
8131a9d5e9eefd294ceae5d4f48d5ad12a3065a79c0d2b943d78f520107669b1c07d3\
49581b61e6f297bb93aeec477761f302338eb887463992ef227d327605ad4e55c80fc\
f45dea0c93a6ff8f1caf5054ab18b5f83cab8deb6f42a5300c51828cd17805000febb\
22492ab0a8820367fe3dcf0b93d44d10703a13e64c524982d789f6c1b2cd5cd0b8a18\
a477770ca29a9f4a3a874b7c0490a057e41e9b36de380fdb7e2639f8f12755ec802c3\
66e7396e2084536b9d3bafac815600383b9c8e8314c75d3a9bf3959988b5452263e9f\
d40a9b0ac0893f83a8931b149fa873c5035a9e04f38d46b1699ec6f403a3e616ed12f\
38c72aa8933a47d2a50c59d56e3c6010833db2278d978facb348cf39ac68b5b403f5d\
5fef4f56699dbbbf744ce0dcac42b3263a580524994d3d15df7d7e3140db0dac36f67\
5b04f12056b6aaffa7c764ea5c6fb8a9e435bc295e751c779feb1b5809077daf2a624\
f5c10c6444e70b2b32a5a5555649af5cb35d7f4b35aef04fb6a1456e8e4c57b997fe8\
a11f294b42ad66a5e962cd2106504905886978324653e370795ab8fe072f74c82be80\
e382ea950bb592b3964c9ee2ba1aa850a27e03253f9898f157e7e4e517acdc116bb9a\
c5239727aced834dacfbae70d66ef58f57ea3607548013d6f3e82647a072d741985e5\
06c0d50254f6e4b6fcd7f4601007b3f3f0445c0693c1f568ed588ddbcee1bcd835cba\
b4ae6445cc0714af8c0756d1f35ab1f1e27e726766dbafa8319e82ac710b3f1a4af76\
be54a5f54c49bb29aa3a2271d37f29346025ea9a9c57d9438fd835b15640242aaa260\
afb9e9ff796a1b177ed98dd1f4db97bb0dc9c35f05f479f35d2bcf1e6f47bbef08637\
2712d2945e37b289d5e38667db612e17900df5bd7f55e379631d743ad43dbf9bcb86d\
95938facd0efcdf2bf2a81a4ea6d40689e5c9dd382d9f776b378c73d1024876794a5f\
fa3ed650b72de9b5d6fa8d3625767541278d5e05686b8c7555644f425cd51f3149d83\
0607ffe28033ecf9a65ecd49079c7f632f173b76f66534ed32354fbbc2040f95b6625\
abbe36e24156fe3207f00fec7cb2cbb226f4ee2bbdfcb2fca94edf80aa316bcf53648\
639ff6fde97cb25e48f31d696541acb43746d654b4e831a584c905b5810a97b07ff89\
280235d0ac3fe91831c1bd921c24d2d6627c59093fc9408838844e3042af50fed6d84\
12d479bd820b406854bb5c8c15fe54263089214fe2e41346900d27bef0186cfab8fd5\
4658e3ca133f03fb10724d35c1f809e882e9728b226f1a5f98d20febf277526bd6e40\
d1cf749a207304251bd8c02da0122e1a8947bb8bb49db54869c9f30ed314ab0e62f11\
31352b587b00d34b3af4154b6692a6871aa934c9393aedec42e2329bed6e64d0cda8d\
c0c5afcf32d95c40676f544b524668b41e94c13fa500e86120486ba2fceca86c6f7e1\
7e98899793988d1a98ba151faaadc65bb6822d376abeb4d19a05959a4b3daa85b9be1\
1055d314a78a956ec72ba0ed5c66948fda38bb14faacbbcdd871fe69cf36e4cc03d23\
32812bb6ceae3d354e0fa8627cf6e687cca77fd64d3ad5b8f24a5b03fc0eaa2f59bf7\
1a51e2568ce1fc6594fbb2b8d50558566b2072de593e289127c60bdc3f64ff892d1a6\
2303079c1f083ba2b6c8666c3dd3209f26725e1a8a7b47246b14ebed95859e63a675d\
1f42f9da76ade740a55392943bb7d4d3819b2b23ea0c2c3fb1949d5317eb4e29c4b83\
9024fe11ebaff431d223e361c5ce0bac4a368f96da57b4cf728087826e17e2b3ee046\
e13df8fc2a7c2ceab4c3090729b28fb33dcb841a035b3b53daf20b22ff672ee5bf8c2\
3521925a93ccf3e48f44b7c2fa7d8cb5e1ce59938ca08f71999c770edefa89e826328\
8c84ea6f20be9d72f0a6d2b17f1e26ea853690e7bfb645ce743299b532a56ec7fee01\
5cf44c92a292bb44d44e0987b673f855c7fb26f6ac8b2a585066829bae4e411624a74\
280893347e38fea8fb13cbed27d750af2ba3dcfbc0c447feb0aea56d637b1e92241aa\
8488a67ab13d22d6f4f25fd911d792bb4e4ccf14766a46eb9851e09edc126e65aaef5\
4345ec67a1ff2fbc690c5bf04effabd2fbd6a0fc3f3e588625c10c4c9d999aa428721\
eedaa56c6598673cf8b34e693bf60dd5727fe7f739e90144dec7f3505f3575f88e094\
6486a25205052138e6f51a5ba57260b34ba4f5efaac62d8e92767be292921513a2e3d\
0ffff4fc5a2cb1547c74774ffe644c2d9468ca512e43173bb59c17da0cdb80bfebbca\
a8a0010d1bc9a7559046a6966d4825a2305e43b39d53ffca38708954bcb16d13adabd\
a42ac998c537df11815afaf2755c4e7fc693fbe6d2a66fc4d472c1add0bd55e42482f\
d734a186d259efe330e9ddbefd83e51e29443b345d1eda515a93195ac251ed163f953\
bb652c2df51b9714bbcd1d4be9d5328666406f613956b0bb78eace5877cb43dd7a346\
77becf29fefa779e2e828605fa2f535958b4fafbebc82f807e36d7adcd9413f54d509\
772f9ee0caa3e86b3cccf3af4fc908ca35f9ed3ebaba7825f1c2b4071a75817b6f124\
5380299b2c94c4a73b4a1806e6f46afe9e23e8e8e8ee20aaa5d70ba7e0e9ad0a42540\
8c0012048b698c316c8fc4c7e396531bba6c7144a39ec1efbb0b58b300e58d2b32780\
ae8f7ef4c630ebb736c9cfb4e3aa72924cbb373ec40f5eed2067e39ebb06988bbdf0e\
3424ec0cd45830c68a5430232bfa06824ceba8b11ad614e74028b27554943a1422b72\
c2e6e543fa2e06f1eeb959b6dc0cc047d7ba3e396edd196255f65d6017f87e378dcd8\
63667594761ea48d2706fc2a77609a8c9c96537b6d3996e469031ba3d012aee2ac963\
0b86cfc15e859c93efccf089840a6b4bbe84f6a86d5f8c39f80759d6b177d57526f77\
88d44f211f70adac5582a20be41e9b519889779027f97804eb11550cd9e18e0fda506\
18746d9d00304c622ab14c6cfb81e1741cdd1ead8b765f2cbbe57d9ca14940da26ef1\
a010e0cb641e41e6b700bbc34a2fb30f013b67d0b81398258f49c24002eb35d5d088b\
4976ef81e2fc660e8176f889021c1fabdd1306c7b2dbecf3ca97964ce33f21acf6b89\
1e936759093fcdd7ec5e5952e2d66779fd3c6e2bcc234df66fda6aeb659f38bb9629a\
0c45ac3582cf72823324a26af6a6cccb4500142f03571a884f31b2e6095192e2639e5\
b8e501f9565339d78b8d8d18160269641a831f812d15a36a76d7097fa4411a12aa00a\
79680ae996ceea5fb4d4c1d88b125fda310d1ce0ffc0bbeba393c824e7299fd25e91e\
f5fe4f943a4120e6bf26be5c2c04552f5a5c12cf1facbabc452a7020dc88438829719\
fd77a48040f03a61237c430b9e3affb669835b2ae5363984bcc82c48142c7ace3e7de\
ed908ef20767f902d3b5b67a652e7160f87a460e46b06dfc19a7fb54d.

Consequently, the number of elements in the jacobian of C is

 P(1) = 2^65540-a*2^32770+b-a+1

and the number of points on the curve is

 2^32770+1-a.