Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!rutgers!ucla-cs!zen!ucbvax!decvax!ima!necntc!linus!bs
From: bs@linus.UUCP (Robert D. Silverman)
Newsgroups: sci.math,sci.crypt
Subject: Re: New Factoring Record
Message-ID: <10604@linus.UUCP>
Date: Thu, 6-Aug-87 14:11:23 EDT
Article-I.D.: linus.10604
Posted: Thu Aug  6 14:11:23 1987
Date-Received: Sat, 8-Aug-87 14:14:45 EDT
References: <10489@linus.UUCP] <7876@mimsy.UUCP>
Reply-To: bs@gauss.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 29
Xref: mnetor sci.math:1770 sci.crypt:514

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