What is the largest number factored by a general purpose algorithm, and how was it done?
arithmetic/factoring.record New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
What is the largest number factored by a general purpose algorithm, and how was it done? [ Editor: problem statement reconstructed from the postings (Robert Silverman's announcement of a factoring record, with a follow-up question). ]
Show solution
I have just established two new factoring records. I just finished factoring the following 88 digit number: 94 10 + 1 --------- 101.45121 It was factored by a parallel version of the Multiple Polynomial Quadratic Sieve (MPQS) and is the largest number ever factored by a general purpose algorithm. It also represents the first time a 40 digit penultimate factor of a number has been found. The factorization is: 2144906157509411684424913774078958939881 times 1023037643093214557651333120422980213172396059301 -- Bob Silverman <bs@linus.UUCP> In article <7876@mimsy.UUCP>, lls@mimsy.UUCP (Lauren L. Smith) writes: > Impressive. I'm interested in parallel algorithms and am wondering > about a couple of things - How long did the factoring take? What > parallel machine did you run? Did the algorithm exploit fine-grained > parallelism or large-grained or both? Do you have any idea of the > speedup? The algorithm was implemented on a network of 24 SUN-3 microcomputers. The algorithm was designed and written in such a way that N machines do, in practice and in theory yield an N-fold speedup. The total number of CPU hours, summed over all 24 machines was 11,400 hours or about 475 hours/machine. I have a paper, to appear in Volume I, #3 of the Journal of Supercomputing, describing the algorithm and its implementation. -- Bob Silverman <bs@linus.UUCP> [ Editor: the announcement mentions two records but describes only one. ]