bs@linus.UUCP (Robert D. Silverman) (08/04/87)
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
booth@vax135.UUCP (David Booth) (08/05/87)
Regarding Bob Silverman's announcement:
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
Apparently, the number that was factored should be read as
(10^94 + 1)/(101*45121). Bob: would you please use a clearer,
more conventional syntax next time? Thanks.
David Booth
UUCP: {harvard, seismo, ucbvax}!vax135!booth
Arpanet: vax135!booth@ucbvax.berkeley.edulls@mimsy.UUCP (Lauren L. Smith) (08/06/87)
In article <10489@linus.UUCP>, bs@linus.UUCP (Robert D. Silverman) writes: > I have just established two new factoring records. > > 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. 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? Although I'm sure that is an irrelevant question, because the algorithm probably would take years on a single processor.... - Lauren Smith ARPA: lls@mimsy.umd.edu
bs@linus.UUCP (Robert D. Silverman) (08/06/87)
In article <7876@mimsy.UUCP] lls@mimsy.UUCP (Lauren L. Smith) writes: ]In article <10489@linus.UUCP>, bs@linus.UUCP (Robert D. Silverman) writes: ]> I have just established two new factoring records. ]> ]> 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. ] ]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? Although ]I'm sure that is an irrelevant question, because the algorithm probably ]would take years on a single processor.... ] ]- Lauren Smith ] ]ARPA: lls@mimsy.umd.edu 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, desribing the algorithm and its implementation. Bob Silverman
jml@strath-cs.UUCP (08/10/87)
In article <1839@vax135.UUCP> booth@vax135.UUCP (David Booth) writes: >Regarding Bob Silverman's announcement: >Apparently, the number that was factored should be read as >(10^94 + 1)/(101*45121). Bob: would you please use a clearer, >more conventional syntax next time? Thanks. > >David Booth Come on. Give the man a break. The notation Bob used was as clear as day to me and hopefully most others. In fact it is more obvious and direct than the one you give, whose only advantage is conservation of space. I can't speak for anyone else, but I personally prefer the "dot" version of multiplication to the "star" version when writing a product. However I do believe that the "star" is much more preferable in a programming language. No hard feelings I hope. jml, the modern Mersenne.