Conference rusure::math

1221.0. "Fermats Ninth Number" by STAR::BUDA (Putsing along...) Fri Apr 13 1990 12:41

    A notes file has been created called VMSZOO::FACTOR.  Please feel free
    to ask questions and/or leave comments.
    
    Type KP7 to add the conference to your note book.
    
    	- mark
    
    
From:	STAR::GOLDSTEIN "Andy Goldstein  12-Apr-1990 1922" 12-APR-1990 19:35:15.74
To:	@DISTLIST:VMSENG
CC:	
Subj:	Distributed Factoring - Put those VUPs to work to help beat out SUN!

From:	RDVAX::MACHEFSKY "EXTERNAL RESEARCH PROGRAM, WEST COAST 415-723-4339  06-Apr-1990 2127"  6-APR-1990 21:40:59.63
To:	@SUN,@WTD
CC:	DECSRC::MSM,MACHEFSKY
Subj:	Beat back SUN...Advance science!

 
Help advance the cause of science and stop SUN from planting its flag
in Fermat's ninth number. 
 
Mark Manasse of Digital's System Research Center (SRC) in Palo Alto is
engaged in a race to be the first to factor Fermat's ninth number,
1+2^2^9. On the dark side is Bob Silverman of Mitre who has the full
might of SUN's 10,000 workstation internal network behind him. Silverman
has promised to lay the laurels of glory on SUN's brow in exchange for
the use of their systems.
 
How can you help? Large numbers of workstations, working in parallel, are
required to factor Fermat's ninth number. If you are willing to put your
workstation or local cluster of workstations to the task, you can help.
The software Mark has written is very polite, runs in the background when
you aren't, and can even be made to go away if you don't want it around
for a while. However, BE WARNED - TO PARTICIPATE YOU MUST BE SERIOUS.
EVERY WORKSTATION THAT VOLUNTEERS TO DO A PART OF THE FACTORIZATION MUST
COMPLETE ITS TASK OR THE PROJECT WILL FAIL.
 
Here is how to participate:
 
Individuals who have either VMS or Ultrix workstations can run the 
quadratic sieve program.  While this will not help directly with 
the factorization of the ninth Fermat number, it will allow us to 
reallocate some of our other resources to that task. To receive this 
software, together with instructions on how to run it, send a mail 
message to BIGTOP::FACTOR. In the body of your message include the 
following line, formatted exactly as below, first letter flush left 
against the margin, where Nodename is the node where you receive 
Email and Userid is your userid on that system:

 
Path# Nodename::Userid
Program#

 
If you control, or can be respsonsible for, a collection of Ultrix/RISC 
workstations that total 100 MIPS or more, you can run the number field
sieve program, which is much more powerful than the above quadratic
seive program. To run this program you will have to contact Mark Manasse,
DECSRC::MSM, to get a tasklist. Because it requires some direct supervision
to run, Mark beleives that the biggest payback for the effort can be had
from a workstation cluster. However, individuals with Ultrix/RISC workstations
may still run this program, if they desire.
 
To get a copy of the software, together with instructions on how to run it,
send a mail message to BIGTOP::FACTOR. In the body of your message include
the following line, formatted exactly as below, first letter flush left
against the margin, where Nodename is the node where you receive Email and
Userid is your userid on that system:

 
Path# Nodename::Userid
F9Program#

 
To run this program, you will have to contact Mark for a tasklist.  In
the case of both of the above programs, results are reported via Email
and do not require you to collect any information.
 
By next week Mark expects to have about 300 workstations working on this
problem, most inside Digital but some at universities on the internet.
He needs to have 600-700 workstations working on the problem to produce
the factors by the end of the month and secure the crown of glory for
DEC's brow.
 
Mark can be reached via Email at DECSRC::MSM, or via phone at DTN 543-2221,
non-DTN 415-853-2221.
 
Help! and, as Mark puts it,  "Glow with pride as DEC and our allies beat
back the forces at Sun which seek to eclipse us."
 
regards,
Ira
P.S. Please forward this message to anyone who may be able to help.
 
---------------------------Attachment------------------------------------------
 
Here is Mark Manasse in his own words on factoring Fermat's ninth number:
 
   "The factoring project now stands on a major threshold: the first 
   factorization of a >= 512 bit number with no special properties to 
   the factors.  The number in question is F9, the ninth Fermat number, 
   which is 1 + 2^2^9.  Thanks to Maple, this is:
 
134078079299425970995740249982058461274793658205923933777235614437217640300735\
46976801874298166903427690031858186486050853753882811946569946433649006084097
 
   which has a single known small factor of 2424833, and a remaining 
   known-to-be-composite portion which has 148 digits.
 
   Factoring difficult 148 digit composites is still far too difficult 
   for any of the general purpose factoring methods we currently know 
   of. F9 however has a very special form, and we can factor it using 
   the special version of a new factoring algorithm, the number field 
   sieve, invented by J.M. Pollard, Hendrik and Arjen Lenstra, and me.
 
   We've been working at F9 for a few weeks on the Fireflies at SRC, 
   and on a modest number of SPARCstations, Sun-3's, Sun-4's, and PMAXes 
   at Bellcore (where Arjen works).  But it's time to get serious now: 
   Bob Silverman of Mitre has struck a deal with Sun to use their internal 
   engineering network of ~10,000 Sun-3's and Sun-4's to produce some 
   factorizations that Sun can trumpet about.  He doesn't have his own 
   number field sieve program yet, but we've explained how it works in 
   several lectures, so it's just a matter of time.  And that's what 
   we're working against: time.  If we continue with the number of 
   workstations we have, it will take us about three months to collect 
   all the data we need.  If we can get more workstations, we can reduce 
   this time.
 
   The new software tries to be reasonably polite about getting out of 
   the way; it should never bother you for more than about five minutes.  
   If you type at a tty (xterm, DECterm, rlogin, whatever), it will stop.  
   If your load average exceeds .5 (excluding factoring), it will stop.  
   If you want it to not even use virtual memory for a while, that too 
   can be arranged: just go to the directory for running factorization, 
   and touch shortkill.`hostname`; that kills it for four hours.  If 
   you want to get out altogether, touch stop.`hostname`."
 
				---The End---