| Title: | The Digital way of working |
| Moderator: | QUARK::LIONEL ON |
| Created: | Fri Feb 14 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 5321 |
| Total number of notes: | 139771 |
A notes file has been created to follow this subject, answer questiosn
etc... It is VMSZOO::FACTOR. VMS engineering is getting involved
quite heavily.
- 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---
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1080.1 | This round of FACTORING is done. | STAR::BUDA | Putsing along... | Mon Jun 18 1990 13:28 | 125 |
<<< VMSZOO::FOLKD$:[NOTES$LIBRARY]FACTOR.NOTE;1 >>>
-< Factoring Notes File >-
================================================================================
Note 34.0 Complete factorization of F9 No replies
BIGTOP::msm 119 lines 15-JUN-1990 22:05
--------------------------------------------------------------------------------
1990 Jun 15 11:15 am PDT (the date order that Arjen prefers, since
it's fully big-endian), Palo Alto:
We have just completed the factorization of the ninth Fermat number,
2^512+1. We used the specialized version of the number field sieve,
which is appropriate for numbers of the form a^b+c, for small a and
c. This algorithm is based on an algorithm of John Pollard, as refined
by Hendrik Lenstra, Jr. Arjen Lenstra and I worked on the
implementation of the algorithm, and tried to chip in minor
improvements where we could.
We began collecting data for this factorization in early April, using
hundreds of workstations around the world. Results were sent back
to Palo Alto using electronic mail. We completed collection in
mid-May, and then constructed a large system of linear equations
to solve. We then ran a structured Gaussian elimination algorithm
to reduce our sparse system of 200,000+ equations to a dense system
of 72,000+ equations, using a variant of an algorithm due to Andrew
Odlyzko and Carl Pomerance. We then started Gaussian elimination on
the dense system here at SRC, a process which we expected to take
six weeks on a single workstation, and sent a box of tapes to the
Supercomputer Computation Research Institute at Florida State
University, where Jim Hudgens and George Marsaglia graciously arranged
some time for us on their very large Connection Machine. Mike McKenna
and Roger Frye wrote and ran the Gaussian elimination program for the
Connection Machine, which ran in only three hours, and shipped a
file of dependencies back out to California this morning. I then
turned the dependencies back into dependencies of the sparse matrix,
and computed the necessary exponents. Finally, we multiplied all
the prime powers together to arrive at an equation of the form x^2
== y^2 (mod F9). The first one we found had x = -y, but an hour
later we produced the factorization on the second try.
Enough suspense:
2 ^ 512 + 1 =
134078079299425970995740249982058461274793658205923933777235614437217640\
30073546976801874298166903427690031858186486050853753882811946569946\
433649006084097 =
2424833
* 7455602825647884208337395736200454918783366342657
* 7416400626275308015247871419019374740599407810975190239058213161444157\
59504705008092818711693940737
The last two factors have 49 and 99 digits, respectively. Both have
been proved prime by Andrew Odlyzko, using the Jacobi sum algorithm
implemented by Arjen. Our numerological team observes that both factors
begin and end with sevens and 49 is seven squared. Think about it.
We'd like to thank everyone who contributed computing cycles to this
project, but I can't: we only have records of the person at each
site who installed and managed the code. If you helped us, we'd
be delighted to hear from you; please send us your name as you would
like it to appear in the final version of the paper. I'm sure this
list is incomplete; please help us out. The first list has individuals
whose names we do know, the second list has computer addresses we
haven't resolved to individuals.
Dean Alvis, Thomas G. Arnold, Bob Ayers, Pete Balkus, Joel Bartlett,
David M. Bernardo, Anita Borg, Wieb Bosma, Patrick Boyle, Richard
P. Brent, John Brownie, Bruce Bullis, Jerome Chailloux, Chran-Ham
Chang, Henri Cohen, Leisa Condie, Bob Devine, Jeff Dike, John Dillon,
Jeremy Dion, Mike Doody, Alan Eustace, Mike Ferrara, John Forecast,
Hania Gajewska, Stephen Gildea, Andy Goldstein, Tim Greenwood, Ramsey
Haddad, Gary Harding, B. J. Herbison, Jim Horning, Felix S Hsu, Scott
Huddleston, Peter Ilieve, Jeff Janock, Mike Johnson, Kevin Jones,
Bill Kalsow, Irving Kaplansky, Harsh Kapoor, Bill Katz, Christopher
A. Kent, Alan Kirby, Manfred Koethe, Ted Lemon, Walter Lioen, Todd
Little, Joseph A. Martin, Murray S. Mazer, James T. McCartney, Joel
McCormack, Steven Miller, Jeffrey Mogul, Francois Morain, David
Mostardi, A. E. Mossberg, Jeff E. Nelson, Marc Nozell, Tom Patterson,
Nigel Poole, Eric D. Postpischil, Dennis Racca, Jon Reeves, Brian
Reid, Herman te Riele, John Riley, John Robinson, Eduardo Santiago,
Richard Schedler, Michael Sclafani, Mark Shand, Bob Silverman, Al
Simons, Kiran Somalwar, Bill Sommerfeld, Bob Souza, Alan Stanier,
John T. Stapleton, Jorge Stolfi, Geof Stone, Richard Swan, Ed Taranto,
Bob Thomas, Gary Thomas, Dennis Ting, Win Treese, Percy Tzelnic,
Brick Verser, Paul Vixie, David Wall, Dick Wilkins, Dik Winter, Ted
Wobber, Frank M. Woodall, Jr.
21.158::guest@gill, 21.158::stapes@hans, 63.404::[email protected],
63.491::[email protected], RYN::[email protected],
RYN::postmaster@hans3, RYN::postmaster@jogger, RYN::postmaster@karma,
RYN::postmaster@mroact, [email protected], [email protected],
catcsm::[email protected], [email protected], [email protected],
[email protected], dscad::[email protected], dscipl::[email protected],
[email protected], [email protected], [email protected], [email protected],
[email protected], [email protected], [email protected], [email protected],
[email protected], [email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected], konark::[email protected],
marla::[email protected], marla::[email protected], may18::[email protected],
may37::[email protected], may37::[email protected], may39::[email protected],
may39::[email protected], [email protected], [email protected],
np::[email protected], [email protected], pmax01::[email protected],
pmax02::[email protected], [email protected],
[email protected], [email protected],
ptools::[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], segny::[email protected], shell::[email protected],
sk8r::[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected],
[email protected], [email protected]
If you're interested in participating in our ongoing factorization
efforts, please send mail to [email protected]. Your message should
contain the (appropriately modified) lines:
program#
path# [email protected]
Thanks again to all our contributors.
Mark Manasse
| |||||