Date:         Thu, 5 Dec 2002 12:02:27 -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:      Elliptic Curve Point Counting, 100002 bits

Dear Number Theorists,

We would like to report that we were able to compute the number of
points of an elliptic curve defined over GF(2^100002). The total
running time was about 82 hours on a 731 MHz Alpha EV6 CPU. The
lifting phase was done in 42 hours and the norm computation, in 40
hours.

The software we used for this task is the same as the software we
developed for the previous record [LeLu02]. Briefly, it implements a
O(n^(2+epsilon)) algorithm based on Mestre and Kim et al. ideas
[Mestre01, KPC+02]. Details are available in a preprint which is
submitted for publication and which is available on request.

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

[KPC+02] Hae Young Kim, Jung Youl Park, Jung Hee Cheon, Je Hong Park,
Jae Heon Kim, and Sang Geun Hahn. Fast elliptic curve point counting
using gaussian normal basis. In Claus Fieker and David R. Kohel,
editors, Algorithmic Number Theory, 5th International Symposium,
ANTS-V, pages 292-307, Berlin, July 2002. Springer Verlag.

[LeLu02] R. Lercier and D. Lubicz, Elliptic Curve Point Counting,
65538 bits. Email to the NMBRTHRY list, november 2002.

[Mestre01] Jean-Francois Mestre. Lettre a Gaudry et Harley. Available
at http://www.math.jussieu.fr/~mestre, december 2000.

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

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

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

let E be the elliptic curve given by

 y^2 + xy = x^3 + a6,

with

 a6 = t^126 + t^125 + ... + t^3 + t^2

given in a compressed hexadecimal form as

        0x77248f38be02f90fbc3f3508053bd1bc,

then the number of points of E is equal to

 2^100002+1-c

with

   c = -0x35df8a633f173cdd4c76ee81ac28bc805ef54f6f8cc4b66d9af7fa363a4c70c\
565c0302a2ed25ac3ef4175f31815a3a58bf8f599e6e70a20fb538a1573d3ed7944dfac11\
94da217d7eae2de5e6ff54540b9f6e321a6b4f0b29d978bb7b69a9408d540bad085dd9503\
a31814f9db98642cca3780af11fed65658d5ef6bde55adbe9e50137158cce37e1eb344cf0\
43e8d0ce8020ee093de11b7dc40f9e04e149b9650316e6e1fdb06fedf2874fad670a2d1b6\
3cb6e52828775319a5bec803d44aaf2cf869e83f20ae6ca0f8a36a9cca2f204be3d254256\
011169163f84a02c6ad0437d78fd43d90de411a6aca2842e27a6ad7acbdf793f5d5ae26f5\
a45c99b8a463f647fa468bffcf20fcb1cc3fefbabce95b8167ac12de0fc3a92fd8e81caf5\
246e267a4a32ae75016d492d020eb76b0ce5c23c053f8b56a31b48e2380c2fc4b178d300b\
ee19d9677b9b61a6b072104db2f3562e9ddafb2cd0cd10894619ba6c86252cd0335f4a8cd\
82877fed2d723b42bd89726b46cb3887d3d855a625b218469d0a1747950063f604392b05d\
b24ce0dabdcefe5178d0d04ba70ab93b36806d4e2deebb82d4fddcd8abe91c9bf89931620\
e7aa685d41ba922b7ce4438168da7280dae84b521ba3b5e64ca5716a48286c7d448260d67\
1984afa97180a6323c2be102d63e1c484758bde6dc5aff31e35ad4e5f596cba070d13e67c\
a15addf9187bdefb8ba5db8c6443257c31bc3311cc7867a937a3b3ff526067ff8da279b82\
ae79b5d3e8abeba0102440b4f5a031be55da5a60f41d859cf627eecf03e032818516fe200\
03c0d0d7bbc18d80067ac5ad713bfbd87dab06f74dbc45946ea101eb76129073465e39068\
70804038822795f662caf88988b78e11c92e92e19972055d7bd535f5f31672b09c801be2c\
f719fbff02d321a7c36d77a316be429bd9434d1e8fcc9f30a61d65cd526f928774f2c8deb\
26d81b01a3cca66b08231bd05b5fed031b163dda240d2b0cc65d1e269f6895d4411376a01\
8a039c7ea33a3a6169bf4ddb77ba34d579136e0b13d4cb6588f1614006a0e634d4f7bc6fa\
641fa36814c60984c6cbda88f9b997637689d18d2b85d36431dedc102f6d5daaa88387096\
de632d77cc70cfd2d4e8a999c1cd3ac959cc34dc7c204b4f1b3ecbda584f8157348170698\
86558e188d7e9c23e4de71f14f339887c1e1729728ece0bc9bf67ad8f715eba8ebe31918d\
f4200cc5d297581133aacb9d0058cf0c56ca41e24c35d1484044fd2b913ba02b05cd84980\
0417d31e9b72d140408f1841eb732af24ab10670d7646bfa8c5c1d2606f68be9bafc11272\
379db7be40084526ec41172443966ac0a6a871f8c8ae8584b92ad753bb054c386cf27a3ee\
4556770e3d1ebece11284082fe11fa26c59eb39d26621edf3c631f63b933dd1ea067d9ae5\
4a17fd4e5d747c3a79a22b7b76c9331d219c3d0d648995dd7fe582ece0d467ba45b315803\
57ee993d83c6e6652afdc890422f9a7bd27597a67bcaf39f8f90d662d4cc810e4bbe56372\
d9a6b51b25bfe17ef21d968772def911de1731017879ca517fc8b4a0b181d886470ab17bc\
2ebb8293e6b408919b395c7ebfe102228f22eb4aee28c14a349f4067de185ad7349605675\
bd85c7e9a7a546ea4700a547bd82e4e204a05e3b3afdbff8f51e70ccae725ca2cb9313ed2\
105c53f2a5916739fd7ed9633b99939c1815a270b174efb3e37c0317637c327463f371d89\
b0910d2e150381b04aec0240347655ef9ea14445cd7b754dea322fc711d6d99e57537617d\
1d7ad3df466854d942fcc3d182be02f2979df5963235e15cea8f9fbba98f9b26725da21af\
fead641d9b3fc09a80f13c909583241a76146c5fc8189f7144db08217d239bd217184f869\
84584e479da15a9b6e216e37806b99520c1cf3acbdc0b93c9f5f0c16ceba809ef74d2c313\
d63f5ad591345bb0344409c7b902a1286b7d67f75ca1dbb37948a1166d6b34c5fa6c6099b\
4415cc8069b5937a5ebf88ca16072b77c8d765d807961e262b7535b9b2f514e009ad20ac5\
5088c98a7a1096c8ae4ba4e739d486471e3b41045d9aeb9704db72d0409f17621ac12cbdc\
144c29bfe31e37af56c1554d06a6a764800fa1228964001a6bed34fc3665c8bb5d24106aa\
c08f1171d1d3abc248fd5645fa2007730b6f0d5bd0f3358933e062efa003f93a3543f1eab\
8ac9f0aaf3923b92e94c7d9d273767b1f9c345e436d2b6376f91278f35ac8699bb7964da6\
8ba7fdde04703b2203cb686390fd7365bedec442507d622992fe6b50610441eab273ba312\
71a7e555a285e0c27e398a7be60c64dcca5eccd7c5f344d457fc5f44fc35024a721b90853\
27e4ef085eebf36678cc63eabf6a447f426f7e5a9f8a5909b3f6f8beeb4e5cb8762f99a04\
215e06d1d3e2b6f83a03e19788f011cb9e875aba860edb21233f04e9f006473be117c0fef\
c5c54a35ce5bb5578ad259afe6bf9097f4cb624e2d2af8b2f22cd5e38fa6037f9a6711c3a\
d90c1964b24d679e07afcc24ec938f4ca169a190e4ab7b04ebf3b09e839b9c52afeb47f45\
1431242f9dc4e536ec42d25f73517b361945e5074daf89bad158a8d8694152b003eadee96\
b8907b463f9dac0c592aee40d818c829f755d35fd3a640b2239e50242392e223f986c897a\
28efb7629bb18ef4bd27ceda8484cebe1a29d6d29cbb86559b96815dead11f136f1b0f41c\
89cb1be2f1fe6ab7bf19aa53f22112821cfe2165362e3ba72cd27a197837866bf98a84e81\
8a436e7cecacd16039ff331e4edcea9bf8e25f8c0f2dd31c1957aba468c66046896c674f5\
57f1e768ec7f98e21cbc5bdb088593e65d56d74639547194f6c9f0981397040dd0910247d\
eb1e7dddd03881fc9b97295831e1fcba365a2d18e7e4580f4355dfdbc39534abb461aa5ac\
fcb5c3fe8a605582f1e3d9de405d92fd01712717a0c80cbaf96d93d068b4368a00167eb78\
657f4340626d24c6a58a39f5499fb15629e85fe3431d28cfce1141eb657b2f2eba79a3b19\
afa95ac1fba79319985bf826f7f01939a4d8abe1536563c44b7d1442bb4c8f7b8f0bd5b8d\
39529fb9c5889027e43a8c309002d7cf78e97922db6331eb8bb545764ab6ca2296f579ac8\
f59f64458030445242e6f142e63efd071475f1a9f831ff9b65bfb46f6e3d150ea9ca607df\
84d096592c3b2af53fccf3b25e6c1004201e43406d12eb7caa339fcdf28946f6122992a3f\
d5064ce3f4b8ea0e85eae3440c7f7c05e9e5eb0c72d7e31407c3d015d48267f15873f5a6a\
00c4bc1061c725d8eaaf7f8b9c9fa012759a95e1ed6ad76dd88f7bd1d4da295d615615abd\
fdda82e2dbb441e67a1a97a3f16c7bff320c5c56683eb3aa3d17fff87fdc2611772930b78\
ec59b020883c1aa1f858fc7155909fadcadd5f30240fcb5d446f2aeb16b65074ad9be3e59\
bb4aad722c6c6460aaa995c35aa9921d0c55593a88328d70b0c56be3c04043218f418a994\
ccd752a27b4e9233f55ae22b1245541cce4c74a7b355c6cb1bc001165b99cb2a0eed0b3e6\
14ad0f03474df2d73e1e14f07d46ad566ef35ed6b09413b4bb9c79294ed5d894c72f06e84\
5b747ab5e10d73cf9202d84adfa09662c53cc4792abe9bcdf4d822daa76bf32a8a04f22dc\
8859e429923465fea5c5c91f4a7602c0e3064bd9dc47498468c670f49ade15b0165474cc4\
44b58b6ffeb50e725ad0201d0b05750772661e090eeaeec00f19606f579783cb7a52f4053\
315942ac3a65ae2c4bb56fee8126279157fd5c560969e71365830a4b37f5d1cae46ff4885\
16dbe6482cf0face705d1ea44cbd54063bcbeb6ca85102408b20267fa4489769434599bde\
545c66d445298160b4445a608dca10ea063066624f31c5619cc2a86112461be33875a0bad\
b7745e5eb0106eb9a112e638f9a2e126abf66df575907fef0a4a3c38e8acebbbb22ce119a\
188916ce1d7619f90826ee097105bccd9ad0628631d819f2638a87ebe39524a668a6ad473\
44a1ef56abd962c6cb81c2ea1cea1628e86091e199298541ab5953943e16182945745e72e\
c13d481fd85ea348043fbd274ec66d2772bd973426a39f93f8f201b32153d67534ea090cd\
83aaec1a8ac550880ce5b5aa0973291d4a1cddb5254fdf35db207d9b61d519f14ddc96557\
1a21da2f0a2d988e3f093c7043d4175d422fe7cad7b7f79a7faa2d7780af48ed86ca19a47\
3b6d9d948d1a507ea55f5bdcad06518beceae413f934d1336e70db7eebe0a43762547963a\
95245f392547c8bfba9d9358ed6941fae589655b327a486e1b2e130e5d7222ffcffd3e130\
47de84cb783091ffee28b9480f86d225f62f822f8b3b700fcb734c0c86b3bc19b3f4d89cc\
ae0922f9b169d1cce808649f413f6471da1ac1cb162930a4635c5f9d5f780cd0454b4a031\
59b086f87046cb4e81f8815b6d18085d238c869ec342aaae480650210e020bba85b11a50d\
23f2966594b0da71a38b3ffccfca165fc59f6156f22d6669b60c1c59892520a714487ec1a\
97d243307d24e8e1efd8dac6534819a9bf93760d9a06d116ee381aca5f2a52bd229d56d71\
9da5ac6c032c9bb3f4466e8c02b21065a80424f0574d2af1d97615c56b4ca53f7c03a0746\
f280552d66dccdab4106360f367182b326e2cf9c3b35ca493a6f12c66b2ea8bc322432921\
656494c41b2a3b6c723aaeaf20ceb56e5bd17b9c3c8de961d7588c6430463cacedf3f1264\
683e2df5a0bd026d7e7e0b5608fef26a8b621671825126914163ea11a8459f28656a968b5\
a686380aeacaff0bcd11fd2863e8b75f8084f8e345556f69b86557a6983819c8e190d0afb\
dba4795e8f53b94c3c80329cb3bdecc4750c1d4dbb5fcb5d5cfa2950a3b2b823f90e43c07\
751ff256ece70326a2773a9386e47b4924efed5438cdef86330c4a9cf49c04896bee0ab15\
3651e520d92e5bf18ecdf8a1ca97f1cf33d9fbd7c934b6eeb768e832f97669e0f19f331dd\
852d2540d3e531d78ed9d69dda309f87461631e927c564169a1cc080017fdc5fa2cc3ede3\
c555c130b8e9a827131c54206c739cf04b697fd74d4bfb82d681b7c41a38542546cdc96c9\
ea42dd37fb368db4212bd922ab13725bd05da129b4862a6ff3ecd292dd478e4c03d458833\
94298f0c34575acccfb906d558f578d661b11387a5fb81807f4e97266b393d42541b9b599\
ae965117b859d90bb2dba7cb67419f75112b960f473f806a5a2b73a63402014d0079a0247\
1aba7cc34128298690fb257ed372549c0566515b1248f170f0e76ec16277a7a55bca09b99\
bb31474d37f3c95ddc04003e997ba349bc6bfe5ba2ff667cec8d2fb2a4be2ba971b7bf6d3\
2b06cabab9ffad68561d3b3b5e7009d48438fcc07e99a1476222c1cf8f8992040391037e7\
8b697120bff712a80899d94c0532c35f512631d695d04b812f8d7d9ca2414d67b3cb4600f\
4979fc5acb5ab396c13fc32d665902cea8822e324538a265961800a405e4b0be233bce71f\
79623477dc6e1f01b6e0ccc084915ce6a10012d7b1a54defe24041d7f93a7bc6de47ab575\
955812f5359c586a3dd007cec0767457029fc4a7c8e7881b005cb0c6663ca9cc3901f9b75\
a63580ba92129d26c336fd57f511d49c8404976f570eb7c58ea6da4df17c2306dc9091292\
f2adbba3c6ccc06ff49f64700ba63535cdfafc51e98ae8d9ad05a62a6b699a17729899a4a\
bf35b7fcd0f9cdf57b3859faab55c87d08e6a5deb8dfa2a17437b021fe162f49d2b8b3bc8\
2dd7376f2bcd4b3f70285ace7c9b60636039b89c6b1f679bbb6a6f24bbd62035ccc2cf716\
b34cc25dbd6e3a649cba496bef58cd4c6d23aa9b656d69845c493f91574c4e9a0d965363b\
37038a0ed126f01706cab7bf362ba72f711f33ffeb22ad01d85e6cbfe249dad2b2f781b4c\
c3ef140f6affb7002a0ee9fa199b6b77872c495d3fd6aeabd273cd08c636adc53bf8a6f06\
cfd8edacac867fb76bdc3b2bb90b2517a1c05723ed5322f5cdadaaf9e906026a24fe674fe\
291c291fe4b8b0fe9ea955269b32133d024d6e9e20e23315983e7c79c59174aee303d3d50\
d0db94dbe4471008e2fd42d2fa55added4eff6627517f1988408f561830103f4a913d4923\
a15d0ea44ca91ac06acd6031de4a081b0dc17045ce596d1c44a9da11e94a129f451c72326\
d3726bf545f26fe5950531abbeedf2c8a658b3a76aee2ee6cdb7be0b2c06321c5afeaabdd\
00cbcfb3dbebc43e0b97663794c5a2c3f86492933b46a8a3084f5c4db53f3c5007a27b8ff\
682d0ef806f8f7d02f49ad0e1beb55bc6bd22c9cc92e60f1bc26cd10c3b765af08e3b6f1e\
29ce85483b288b59a6c3487b4f61479f7b19d1e35b3d83c2353ad792c3c9a604de3db7fb4\
bcec342d46995618ebfb96693bee7fda56188a73185b90a275387ee65d35982ca34c3e7cf\
2ab0ea748a511ee4dac615ad97d5cf84f481b5e7c93626d6547af284f59ce98eaf39d5ca6\
a68f0a977b55d9779c861edb0233800bd4e8e2d9e16f7832abaf6020ed3f26392bba8a308\
d96c542121b575d5efbab51e06c889ffce08233f5185b88bddaca2a1072b1b70de0c2ef97\
d7f6bd7d91ba8c9776e17f4b7633f82bef91429a1020a50e053ddfc1aa3b767d21a8c9018\
8904776dc37377e58c71d3d0397eaef6f981aca5218b214af6d471d1eb29f5ab02f61bf2e\
c64afa54bf527aaeb02ea0d4f03f81572612a1d930df08255fa3170a5518ba0d6e13d011b\
263161a18e0dcad30d2a00f002cbd18ff74bc89cc1d708d599d20355b41b9dad59a7d4575\
e5ee2e90f3f95986eb09626b4914b5c550f3b058b1385ec0c9c1d3c33ba7b0a89721399c4\
af25e65c00dfb8fd85f19d6838c517ef4e149e15791f0ddd94ba853e45031d69b8e865522\
c6a5c02d2d2f88b08c8102b22a38af1aef782a40dee42f363ad4e35f5245d2c15f232df7f\
7c0f5d70919c3452caec3d9e53a5c493770ca92af603bd08d11097336fc6e0f4019a6e076\
756019ef8c4bb95d24dbef67084d32bf23f441a7e77e048f6dda1e37377a15f9538edfec3\
51f453505867785b28e66079258cfcde4b0c8ed0b88126c0cb9286bd77d36b4020508dde8\
179be78053340ebd1d45618d25d0900ab29fcbdb26c2cfe24abacaf843a39832012812045\
1b79f7e40296057772ce2803044608723c211f1b9ba68d112bf2b7e563d61895cad83712b\
2c86b0464e09d9b9d1d0332b43a4517e17f8495e62f9b7575efb121da8319a11192efee0c\
dd4d048a5df2397cc0ea5bd81b551b45c300b034fc47bf4df1f31eda5e2aad1faf8e8ef98\
c9497dd10a0d959f92f844e14e69fb59e452644282c6898b3da3260e5c1c3495854256dea\
463b4b581542c5844a4308aaf37ba55a67fd692963d98fc21a8f2856dad75b293376c5fc8\
5a2468ea3208369118d1ab4aae6c1e1b0818167e671e45e830205b94ba1a0372fbd5cefb3\
2cdf9ce80a030920a4cacc636ac765abe484e398687b69bb3985d88d7814befec694a9c67\
8e4173eca2c88b32544b1fd06b33c186c4ab0bcdaa5f8e1125cdc2e8cfa4ae598fd14190f\
f206a2293ff0113b0eda16cb40196a0058f6830b5b09e5ac2703fe4cb2bfb13d08dd4340b\
e5c310589cf7e1281c044704f8ac6aa195082eaceeb53359de108630fc5560fc64b6db4f1\
2c764b245bbaef666291bd83aa14cb06e157d4a53427b47a2d7b954eca5a2eef7220914c1\
050f5ed9d3753fa1f3100d9166c9382e01029e6c5a8cd7f5b07decc6dd47b40f7a928d75c\
f883b3c12903e293ad8360960c068f9f20945d76cfe9f28f5ab38b5ebe882f8e01bca6b3e\
454337dfa021259619e06950c3d0563da1ac88ca031a711bbb73589c1106a60f6699346b8\
71e607d3d47b8658f16694ad9bd7245d082eb09ec2ad2a479787a7e6a87bd37fefd5a2bf9\
1274023e72ef92a8085223d120b5a98b4281efc6d7ef36d753e3df1806011e955fd1b803e\
bf820fcbdd81e5fcb80f012a60f4c6d72b417512211f31ee6f41bb4107ebdabc27be7c046\
cd55c0fe24b6c3c941e48da4cd6598c5fb5212d491c3bcdf3581b243777e55408abbeadee\
9148b88a740f6849a275a9b0868235db749597def1ac960b312fb82e2f235307624a37c80\
b7ce2d4b00c9e9f6b0899101dbcf6f099a46c6627ef52a80759ab8835b3af8843ae6e3ea3\
62e3d89c41b317912622d692b686582892586fa68c80f2cb36187083c96900e0030610670\
77fbe66d807c2b605d0856538a33422077babd362a5fe0a90b38ce5cfa08d7f1291e3ed53\
b3d55e4306157d72f4586a20ee382eb563b3a2681e680e86aede99763918d49b559df344a\
7647a9d0b3bf80676038d4cef83a3d57c2e58c06832c434abb269fbda283465753e18b3e7\
5a706f7ec1b97147409ba010dd1c38330ffac9f13ffa0d7cd44756b1ecb080522f365a521\
6e66f09a12f91a90a2810aae226b8ab17d06024175c12309bcef3a484b792923954b6e9c8\
ecdef874a7ea85d4c7153ae4091fc4e10f5f354feae8f0fdf6081dafece006d4acd36a8ac\
e88a959cb4d21631b4e37d6ebff1fde0154aa347c6a52973b4f049ed6d1ee41a6ab87b98f\
5fd932cb8209b9ad3f90889ffa0bc9b5198ea3bf321d46cb199651c03a7bb28af4bdcb3a0\
2dd13247abfeab0d7792177e62a22a0a7f7f70252f2137365c885a81bcc7861104f3bc1f1\
39dfebd75fe4eedab2127eaa38764045ed7808c23d98cf295b2f254a18cfd297e95c5dae9\
c5409849978202cddcf729cd65833b6858b5ebb3ed157d3ed0f0617fb1f5621f32cd2c569\
202dd4ce6c224375954487bcbfd3.