Palaiseau, 030606 [Corrected version 1.2] The elliptic curve primality proving algorithm (ECPP) is one of the most used algorithms for determining the primality of large numbers, with several thousands of decimal digits. ECPP is a randomized algorithm making use of the reduction of elliptic curves with complex multiplication. Its running time is rather difficult to analyze, and no rigorous proof known. However, it is possible to give convincing arguments that it runs in time O~((log N)^5), where O~ means that we use fast multiplication techniques. This line is followed in [LeLe90] and it is also sketched that a version running in O~((log N)^4) (and attributed to J. O. Shallit) exists. I realized recently that this version had to be tried, notably after some stimulating private communication with D. Bernstein, and with the aim to challenge the users of the PRIMO program of Marcel Martin (http://www.ellipsa.net/). For testing this, I proved the primality of 2177^580+580^2177 a 6016 decimal digit number taken from the tables of Paul Leyland. Using a cluster of 12 Xeon at 2.66 GHz and the help of both GMP and the mpich implementation of MPI, it took 164 days of total CPU time to do the proof (wall clock time was superior by 20%, which clearly means that more work is to be done). The computation started on 030513 and ended on 030604. This settles a new record for ECPP and primality proving of "ordinary" numbers. It is my opinion that with a better choice of parameters, the time could have been much smaller. Generalizing somewhat the short certificates of the mythic book of the Cunningham project, I give below a list of the discriminants used, followed by the sign of the trace used (special coding for D=3, 4 is required). A paper describing this faster version of ECPP will be available soon on my web page: http://www.lix.polytechnique.fr/Labo/Francois.Morain which already contains many papers on ECPP and related algorithms, and the complete certificate for the number in question. The time for checking the certificate is 25 hours on a single Xeon processor. F. Morain ---------------------------------------------------------------------- [LeLe90] A. K. Lenstra and H. W. {Lenstra, Jr.}, Algorithms in number theory, Chapter 12 in Handbook of Theoretical Computer Science, vol. A: Algorithms and Complexity, J. van Leeuwen (Ed), 1990, pp. 674--715. 5254099+1514287-395179+37016-898747+6131+1460299-14251+4295+9892+2209348+ 2819483-147367+54759-15443+248+874067+17491+5695567+700351-78856-51479+ 145747-939-691963-103947+21847-437963-378647-381971+643967+130888-7048187- 22867-31715+6491-402019+8971+14179-6702491+841784-6227251-6920932+276631- 3408995+5958712-902203-96856+8839+35572+3128827-19115+424+4121368+34184+ 10943+14251+7963-2346499-28459+4339+4864312+116251+353791-577891+22927- 174179-1898851+84763-25768+7327807+1365263-15907+981347-45316-772-182419+ 529339-17124-76408+395187+6668491-9467+469027+1831+15307+1227+2008-64324+ 554408-294607-4045519+11-91+10515+40307+4214467-185451+9208-15432-7239811- 3647311-3368-22867-364807+70931-2733139+34663+777067-500419+154776+3079019- 4488223-78103-6603643-910999+273491+49483-37495+7308107+518923+30959-3558616- 355+84031-19156-13432+3917443-410107+11819-292312-3093067+24643+2811243- 6387-107731+11812-472267+6827-1147+3647443-2984264-239647+9739-173951- 6188543+3163-3084824+46303+2979112+115+192868+3a11971+2198611-1917067- 5627-491467-3898399-728227-378031-183892-180643-1576-166699+529351+5996947- 2696-233951+44628-77251+259139+1816+3755+4174447+4b125359+244-17131+69339+ 297668+1003+4447-3028+2415316-4954856+233731-912776-2207+202651+25699- 114488-7907+7403-11383+1103-1636-563-2627+3226667+3886703+50212-404+65411- 3067-1912-1859839+14267-426776-107188+4483-2152-46039-273839-109003-1076+ 1336+10763+48676-1432+371-307156+7+25663+505415-92819-6067+43+458923-690499- 3243571-163451+842459-58648+523067-12751+5328299+4099-62831+493019+19336- 2328-646068-731-40+77827+1630099+11+32971+46259+10307-448036-3635-14567- 7+127891+318459+104+11-79787-5135656+452+3652328-3508+642883+926291-200747+ 11091+3236-3448-2093723+13971-719+59323-1907+5107-3404248+691-339-3078811- 959107+291-1592+1588+1519043+23699-68323-187-1422451+56104+25199+356+85195+ 8552+413059+9556+38131-5683-5647+1003+16251+451+35704+4747+164167-515- 1485863-1421192+4324763+4555-388-151819+4b983207+43-742523+32632-407+1166824- 3656963+53027-837547+187723+447091-44743-42488-7353847-427171+1636+703723- 40571-2815907+1255+84379+4852+6499+19+52243-355-499-709867-184-1+28207+ 521099+2879-318947+26359-306343+291-66719+432739-3c284043+16552+15415+ 2707-289128+392603+211+2047-300907-3028-9771+1600523+20371-1274467-283- 212116+2267-355+52-53571+2667-295739+91012-1068359-13268+111379-4279+103+ 999847-388+498455-127427+424-7-667+1208-7483+427003-7003-9304+5924+46324- 608183-55-700852+35467+331-107512+233368+31483+45172-46087+19-1-46363- 1367+19171+1+97483-776-120-2335+691-14068-25624-99899-463-20783-561779+ 87371-36227+2318227-19147+4843-2395-632+632+2923+835+7409683+647+1763+ 5907-68-3547-19-13603+7528-631-1513063+31043+491287+3079-1050527+2271+ 78943-8159-84839-8891-8-6187+25828+3f5331+328+668152-6847-36292-1651+268276- 139-1411-93659+103+8507-24331+1010455+107+413972+4712-113599-3b2779+12439+ 9496+13956-19+2215-91+307387-163+33239+429272+2792983-4a65956-88051-482932- 131107+643+366987+156931-57403-3563048+347+248107-220331+7749263-9304+ 167+20819+1192-34063+4072-445127-13435+3867-7608-6359272+24+69227+30792+ 797959+5163-25507-643-117823-764851+238219+13684-4843-1843-4659-2872+1027+ 2324323+544283+15256-1011+88267-21967+153415+1864+427+2787-5332+235-6103+ 607-2404-1797923+40760+17587+707347-322467+1+4372+19524-1348+1333492+2683+ 116887+12632+96632+5188-1409179+4195-2916923-1526331+144251+88-67-635704- 262099-8-811+11-356-1-907-12388+10603+899+87259-53755+408904+18232+155803- 6340+7-3147-14383+485908+66331+1283-30760-1959+13987+7783-8584-143-5315- 135992+8-307-11-20+244-16808-18868+4072+20584-4c1038403-452+21995-2419+ 1592728+4d3811+2373155+3535+51643-75587-24559+2827+295+3412+223-3d188059+ 61924+4d427-47683+443+52+1255+8952+7588-1+4744-328-14491-70283+344-7051+ 52-62452-855827+9563+115+1207768-9299+787-43-3f1019+643-388-1051-25027+ 1115-110783+50072+319304+2152-69583+116+167+51+12179+1051+3d163-6712+1355- 17368+211+24523+291931-183+904+463-1-788-232-190499+163+787+5608+3336- 3992-1203-5707-8+40-19-779527-259+347+163-43+7231+4771-1232047-8072-1528+ 504067-23-1123+219-422843-3c4c163-1099+93507+26179-8+3736+7363-8-1192- 7+11203+31783-126187+2047+7240+179+331+8+5371+10264+707+4b67+183-1087- 328583+67+451+163+571-261871-879787+155+31+439-19+1-323+19-19-3b1047-163+ 67-4372+3b4b1+955-4b15780-4c372+20+1547+259-4888+4a532+235+3a3d52+523- 4b11+4a8+4b3b123+3a3d1+1+1-1-91+19+1+3b3a3d3c1-1-1-1-1-1-1-1-1-