Date: Mon, 8 Mar 2010 08:16:18 -0600
From: Thorsten Kleinjung
Subject: This is a tasty factor
To: NMBRTHRY@LISTSERV.NODAK.EDU
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 176185533608779112426057212156915737261973725692777098729042794211002730969474260553528629693362630813445982221616581896014560600230501525946408962727837512415610132135965435178668094176985071980937279402238467438168204332393198436347681167033274334629858331628089772185868567968860006604487 (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 97424992175763507877707709291914998778015966147054584755896881783255837016412999374281145264013986049748696515423136622647352488174403160324612550620242636441380838851457881913863524385273540967010429382172447745964801 has 218 digits
Report your potential champion to Richard Brent
(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