(forwarded from the Number Theory List [NMBRTHRY@LISTSERV.NODAK.EDU] A new record for ECM factoring, a 73 digit factor. This polished off M1181, since the cofactor is prime. --rich) ---- Thorsten Kleinjung [thorsten.kleinjung@epfl.ch] Mon 3/8/2010 7:16 AM This is a tasty factor We are pleased to announce that on the occasion of its 25th anniversary, ECM smashed through the 70-digit barrier by finding the 73-digit prime factor 1808422353177349564546512035512530001279481259854248860454348989451026887 of 2^1181-1 (thereby completing the factorization of 2^1181-1). The previous ECM record, 68 digits, stood only two months. The 40-, 50-, and 60-digit barriers were broken in 1991, 1998, and 2005, respectively. According to Richard Brent's prediction on page 7 of http://wwwmaths.anu.edu.au/~brent/pd/rpb196sp.pdf ECM is a year ahead of schedule. Some details of this computation: We used GMP-ECM with some modifications so we can run stage 1 on a cluster of PlayStation 3 game consoles (PS3) and stage 2 on a cluster of regular processors. Stage 1: We implemented arithmetic functions for PS3s for Mersenne numbers. We used a recently developed 4-way SIMD carry-less Karatsuba multiplier based on radix 2^12 signed digit representation, thereby obtaining a speed-up of approximately a factor of 2 over our previous unoptimized 4-way SIMD PS3 multiplier. Stage 1 for 24 curves in parallel and for B1=3*10^9 took less than 23 hours on one PS3, i.e., less than one hour per curve per PS3. Stage 2: we parallelized some functions, this stage with the default value of B2 of about 10^14 took about 15 minutes on 4 cores (per curve). We ran more than 30000 stage 1 (less than a week on our PS3 cluster) and 8800 stage 2 computations. The output of the lucky job: GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] Resuming ECM residue saved by jwbos@node-3-6.ps3 with GMP-ECM 5.0 on Wed Mar 3 14:03:04 2010 Input number is 1761855336087791124260572121569157372619737256927770987290427942110027309694 7426055352862969336263081344598222161658189601456060023050152594640896272783 7512415610132135965435178668094176985071980937279402238467438168204332393198 436347681167033274334629858331628089772185868567968860006604487 (291 digits) Using B1=3000000000-3000000000, B2=103971375307818, polynomial x^1, sigma=4000027779 Step 1 took 0ms Step 2********** Factor found in step 2: 1808422353177349564546512035512530001279481259854248860454348989451026887 Found probable prime factor of 73 digits: 1808422353177349564546512035512530001279481259854248860454348989451026887 Probable prime cofactor 9742499217576350787770770929191499877801596614705458475589688178325583701641 2999374281145264013986049748696515423136622647352488174403160324612550620242 636441380838851457881913863524385273540967010429382172447745964801 has 218 digits Report your potential champion to Richard Brent <champs@rpbrent.com> (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt) Paul Zimmermann kindly checked the group order: sage: FindGroupOrder(p,4000027779) 2^4 * 3^2 * 13 * 23 * 61 * 379 * 13477 * 272603 * 12331747 * 19481797 * 125550349 * 789142847 * 1923401731 * 10801302048203 Joppe Bos, Thorsten Kleinjung, Arjen Lenstra (EPFL LACAL) Peter Montgomery (Microsoft Research) http://www.youtube.com/watch?v=ecc0nbg9m-8&feature=related