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.