Conference rusure::math

For more info on this, see "Factoring Gets Easier", in the Dec 2, 1983
issue of Science, page 999.

The story as reported above is substantially correct, however.
						-- Jerry

Newsgroups: sci.math
Path: decwrl!pyramid!necntc!linus!bs
Subject: New Factorization Record
Posted: 30 Mar 88 20:18:30 GMT
Organization: The MITRE Corporation, Bedford MA
 
I am pleased to announce that I have just factored the first 90 digit
number ever to be factored by a general purpose algorithm. Special
purpose algorithms have factored larger numbers but these algorithms depend
on luck. They also depend upon the number being factored having small
prime factors. General purpose algorithms, on the other hand, run in
deterministic time depending only on the size of the number being factored
and are guaranteed to succeed regardless of the size of the factors.
Special purpose algorithms are generally useless if the number being factored
is the product of two, nearly equal, primes. The number factored had been
attempted by special purpose methods before and they all failed.
 
The number is (5^160 + 1)/(5^32 + 1)  =
 
293873587705571876992171512531077883265779802078078442040265372270345687866210937500000001
 
Its factors are:
 
46957667265666758402894952584920394200961      and
6258266324069263267587145223441885541709510944641
 
The first factor is the largest penultimate factor ever found of any number.
 
 
The factorization took about 15,000 total CPU hours, running on a parallel
network of 24 SUN-3's. Each machine therefore took about 625 hours.
Researchers at DEC's research facility (SRC) in California had already
expended about 5 years (on a cluster of machines) of CPU time trying to factor
the number using the Elliptic Curve algorithm and had failed.
 
See:
 
"The Multiple Polynomial Quadratic Sieve", Mathematics of Computation
Jan. 1987 (the issue dedicated to Dan Shanks)
 
and
 
"Parallel Implementation of the Quadratic Sieve", J. Supercomputing V1 #3, 1987
 
The algorithm runs in time L(n) = exp([1+o(1)] sqrt(ln N lnlnN))
 
Adding 3 digits roughly doubles the run time for N near 90 decimal digits.
This factor of 2 drops (very!) slowly to 1 as n --> infinity.
 
Bob Silverman

>The factorization took about 15,000 total CPU hours, running on a parallel
>network of 24 SUN-3's. Each machine therefore took about 625 hours.
>

This may imply that the author holds another record: the longest computer 
run to solve a specific problem. There is little data on this category; up 
to now the longest that I am aware of was the 180 CPU hours of Cray-I time,
over a period of three months, that Don Knuth used to solve a problem of
mine - the nonintersecting Knight's tour on an 8x8 board. Anyone else know
of any documented long successful runs? 

Lynn 

RE: .3
    
    Just guessing, but the complete proof (including deadends) of the
    four-color theorem may be up there (but probably wouldn't be now
    -- measuring things in CPU hours rather than some value normalized
    for processor speed is a bit bogus).
    
    					Topher

    I believe the four-color theorem proof was ~10,000 hours, but its
    a long time since I read the (Scientific American???) article.
    
    /Bevin

    As some of you may have seen on Usenet, DEC now holds the record
    for the largest number ever factored by a "general purpose" factoring
    algorithm.  In this message, I hope to explain what we did, and
    how, and solicit help for the next stage of our research.
    
    First, some trivia:
    
    7^139 + 1
    = 2^3
    * 557
    * 5312442648966139012589
    * 190705279598948669274660288301207361
    * 651666519182971782190402264651775450396158503528225547931
    
    (unless I mistyped one of them)
    
    The product of the last two numbers is a 93 digit number which starts
    12427....  The other factors were previously known.  The penultimate
    factor is 36 digits long.
    
    Last summer, we started running a distributed implemention of Hendrik
    Lenstra's elliptic curve method for integer factorization.  That
    algorithm successfully factored about half of the numbers we tried
    with it; these numbers were the 90-120 digit numbers on the most
    and more wanted lists, and a dozen or so Mersenne numbers in the
    range 2^353-1 to 2^475-1.  This summer, we have been running a
    distributed implementation of the multiple polynomial quadratic
    sieve algorithm.  ECM's running time is primarily a function of
    the size of the smallest factor to be found, and is this well-suited
    to factoring numbers taken "at random".  MPQS's running time is
    a function only of the size of the input number.  With our current
    level of technology, using ECM we expect to find factors up to 36
    digits in about a week.  Using MPQS we expect to factor 93 digit
    numbers in about a week.  One advantage of MPQS is that, for any
    size number, you're always making steady progress toward a
    factorization; at any moment you can say with confidence that the
    process is about 60% complete (which happens to be today's progress
    number on a 96 digit factorization).  With ECM all you can say is
    that with high probability, the smallest factor of the number has
    more than x digits, where x grows slowly with running time.
    
    At present, we are running these algorithms using the idle cycles
    of all of the workstations at SRC, the Systems Reseach Center, in
    Palo Alto.  We have a master program that searches for workstations
    that have been idle for at least half an hour.  When one is found,
    a driver program is started that spawns workers for different subtasks,
    and that relays output back to the master.  If the driver notices
    that the machine is too busy, it suspends the workers.  If the driver
    notices that the user has started typing keys again, it terminates
    the workers and exits.  It starts multiple workers only because
    the workstations at SRC are multiprocessors; most of them (about
    60) have five MicroVAX II's, while a few (about 20) have four CVAXes.
    Due to the nature of research that our users are engaged in, at
    any time nearly a quarter of our workstations are crashed (the mean
    operating time between failures isn't as bad as it looks; machines
    that crash at night stay crashed all night.  Moreover, most crashes
    are carefully investigated; quite often someone will spend several
    days examining a single crash).  When the machines are up, they
    are idle about three-fifths of the time.  Thus, our total VUP-power
    is about 260.  That is, over the course of an average day, we get
    the equivalent of two-thirds of a year of computing on a 780.
    
    Our project for the remainder of the summer is to greatly increase
    the size of our computing engine.  We propose to do this by using
    electronic mail as the channel for distributing tasks and reporting
    results.  Our tentative goal is to get to 2500 VUPs.  At that point,
    we expect to factor 100 digit numbers in slightly less than a week
    using MPQS, and to find 40 digits factors in slightly more than
    a week using ECM.
    
    Here's how you can help.  The easy way to help is to wait until
    we're ready, and then volunteer your local cluster of machines to
    help out.  We'll send out details soon.  The hard way to help is
    to offer to write some of the software.
    
    If you want to program, here's what we really need: VMS programs
    that implement everything except the factorization algorithms. 
    That is, we can supply C source for both ECM and MPQS (the ECM stuff
    has a specialized extended precision arithmetic library that's written
    in assembler).  We will be the global master, at least for now.
    What we're missing is: a driver, which spawns the right kind of
    worker, feeding it the right kind of input.  It needs to set an
    appropriately low priority for the worker, and to relay messages
    from the worker back to the local master.  It needs to do the best
    job it can of figuring out whether the worker should be suspended
    or terminated due to the machine being used for more important things.
    A local master, which has to make sure that all the right machines
    are running a driver; make sure that the local master is restarted
    not too long after the machine reboots; maintain the task list of
    things to hand out to workers, by reading incoming mail; and bundle
    up reports from workers into mail messages back to the global master.
    Finally, we need some sort of installation procedure that makes
    it easy for anyone who wants to help to do so; what should be involved
    should be as easy as copying over a small script and executing it.
    However, it should be easy to adapt it so that it handles the slightly
    more challengng case where someone wants to automatically have it
    create a new mailbox to which all the control messages will be sent,
    and new user accounts to run the factorization workers under.  The
    MPQS workers need a few megabytes of temporary disk space on each
    machine; there should be some way of telling them where to get that
    space.  And so on.
    
    Don't think that we're pushing all the hard work off; we're busy
    trying to put together a package that does the same thing, but which
    runs on any Unix machine, so that we can ship it out over Usenet.
    
    Please send me mail if you think you might be interested in helping
    us.
    
    Thanks,
    
    Mark Manasse (decsrc::msm)
    Arjen Lenstra
    

    Quick newsflash: Arjen and I just finished factoring a 96 digit
    factor of 11^107-1, using our distributed quadratic sieve algorithm.
    The factors were both 48 digits long.  This sets records for both
    the largest number ever factored by quadratic sieve, or any other
    general-purpose algorith--the previous record was our 93 digit
    factorization of three weeks ago--and the largest penultimate factor
    ever found.  Given that we had also previously spent 10 VUP years
    trying to factor the number by elliptic curve, and that we spent
    another 10 VUP years on it using quadratic sieve, this may well
    rank high on the list of computations using the most cycles.
    
    I'll post more details later.  We're starting in on a 100 digit
    number now, which we hope to get some help on, so stay tuned.
    
    Mark

    Re .6:
    
    For help with implementing DECnet distributed computational
    algorithims, I strongly suggest that you contact Paul S. Winalski.
    As the author of the distibuted Mandelbrot program he has been dealing
    in this for a couple of years now.
    
    
    --  Barry

Here's what we just posted to sci.math:

Since our last report we found the following factorization:

11^107 - 1 =
  2
* 5
* 1276033068038437
* 304971297664201988898688683700564748747693245597
* 690075192242979172401950662719273770411957106853

The number we factored was the product of the last two factors, which is a
96 digit number which starts 21045... As should be evident, the factors we found
both contain 48 digits. We expected the penultimate factor to be large,
since we had previously run our distributed elliptic curve implementation
on this number for 10 CPU years, without success. We didn't expect it
to be quite that large, however.

This factorization establishes records for both the largest number
ever factored using a `general purpose' factoring algorithm (the
multiple polynomial quadratic sieve algorithm), and the largest 
penultimate factor ever found by a factoring algorithm. The previous
records were Herman te Riele's 92 digit factorization, our 93 digit
factorization, and Bob Silverman's 43 digit penultimate factor of
an 89 digit number.

The number we factored was the next-to-last unfactored number from
the 1925 Cunningham tables of factorizations of numbers of the form
y^n +/- 1 for y = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers (n).
We are currently working on the last unfactored number, a 93 digit
composite factor of 10^109 + 1.

The elapsed time for the factorization was 23 days. We used about 65
Firefly workstations here at DEC's Systems Research Center in Palo Alto,
each of which contains 5 MicroVAX II processors, or 4 CVAX processors.
In addition, we used electronic mail to receive assistance from a pair
of Titans at our sister research facility DEC's Western Research
Laboratory, and from various other machines at the University of
California at Berkeley (a VAX 750), the University of Chicago (a Sun 4
and a Sun 3), and at the Katholieke Universiteit Nijmegen (a Sun 4)
in The Netherlands. We also attempted to use a Cray at Apple, but we
were unsuccessful. We would like to take this opportunity to thank
the people at SRC for allowing us to use their idle cycles and their
virtual memory, and Chris Kent and Joel McCormack at WRL, Hendrik Lenstra
at Berkeley, Mike O'Donnell at Chicago, Andries Lenstra and Ron Sommeling
at Nijmegen, and Malcolm Slaney at Apple for their assistance.

Factoring this number required 10 CPU years from SRC, two CPU weeks
on the Titans (at 10 MIPs each), and 4 CPU days on the Sun 4 in
Chicago. We don't know how much time the other machines provided, but
it was approximately one week each. The external machines furnished
about 5 percent of the relations we needed. As last time, the final 
matrix reduction was done on a VAX 8800. The matrix was 37901 elements
square, and we needed approximately one CPU day to reduce it.

After we complete the factorization of the 93 digit number, we plan 
to factor a 100 digit composite factor of 11^104 + 1. This will be
much easier with your help. We expect to post a program to 
comp.sources which will let you participate in our next factorization.
For now, you can help us out simply by sending us a mail message
indicating your willingness and the approximate number of machines
and system type that you can contribute. Please send your mail to
msm@src.dec.com or ...!decwrl!msm. In addition to posting the program,
we will also send it directly to anybody who expresses interest.


Arjen Lenstra, University of Chicago & DEC SRC
Mark Manasse, DEC SRC

     The results mentioned in 30.6-30.9 seem to use the method
     mentioned in note 259.0.
     
     Dan

'Fraid not.  We do use Hendrik's elliptic curve algorithm to
make sure that the number doesn't have any easy factors, but
then we switch over to a variant of Pomerance's quadratic
sieve algorithm.  At present, the tradeoff seems to be that for
numbers whose smallest factor is around the cube root (or a
little larger) that elliptic curve is the way to go, while
numbers with smallest factor closer to the square root,
quadratic sieve works better.  Asymptotically, they're the same,
but that means little for the size of constant factor these
things carry around.

One thing in favor of elliptic curve is that it scales much
better.  Quadratic sieve needs more and more memory (rapidly)
as the number to be factored grows.  ECM is relatively stable.

Thus, if you could only get your hands on diskless PC's (but you
could get as many as you wanted), ECM is to be preferred.  Sadly,
for the range of numbers we're looking at these days (slightly
in excess of 100 digits) you would need *a lot* of PC's to ever
get a result with, say, 45 digits; as a rough guess, I'd say
it would take about 150 years of VAX 780 time, as opposed to
the 12 years or so it takes using quadratic sieve.

Mark

     Thanks for clearing that up.
     
     Dan

From:	RDVAX::MACHEFSKY "EXTERNAL RESEARCH PROGRAM, WEST COAST 415-723-4339
        06-Apr-1990 2127"  6-APR-1990 23:08:37.16
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---
 

Path: shlump.nac.dec.com!decuac!haven!aplcen!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!usc!cs.utexas.edu!texbell!bellcore!flash!lenstra
From: lenstra@flash.bellcore.com (Arjen Lenstra)
Newsgroups: sci.math
Subject: An attempt to factor the ninth Fermat number 2^512 + 1
Message-ID: <21840@bellcore.bellcore.com>
Date: 6 Apr 90 17:42:53 GMT
Sender: news@bellcore.bellcore.com
Reply-To: lenstra@flash.UUCP (Arjen Lenstra)
Distribution: sci
Organization: Bellcore, Morristown, NJ
Lines: 96
 
A few weeks ago we began our first serious attempt to find the complete 
factorization of the ninth Fermat number F9 = 2^512 + 1. The seven 
digit factor 2424833 has been known for a long time, but the remaining 
148 digit cofactor is still unfactored (although known to be 
composite). Attempts to factor this 148 digit cofactor using the 
elliptic curve method have all failed.
 
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 may be able to factor 
it using the special version of our new factoring algorithm, the 
number field sieve.
 
Currently we are working on F9 using the network of firefly 
workstations at Digital Equipment Corporation's Systems Research 
Center in Palo Alto, and using some 40 workstations (both DEC 3100's 
and Sparc's) at Bell Communications Research in Morristown.  These 
forces will soon be joined by 10 Sparcs's at Oregon State University
(Robert Robson and Russell Ruby, and Joe Buhler from Reed College)
6 Sparc's at Mitre Corporation (Bob Silverman), and 2 Sparc's at the
University of Bordeaux (Henri Cohen).  If we just keep going as we
are doing right now, then we will be done in a few months.
 
We thought it would be a nice idea to offer more people the opportunity 
to help with the factorization of F9. If you (i.e., your university, 
company, institute, or whatever) have some workstations that are 
idle for a significant amount of their time (as is the case for most 
workstations), and if you are willing to spend a few easy minutes 
to install our program, then here is what to do:
 
Send mail to factor@src.dec.com containing the following two lines, 
without leading spaces:
 
	f9program#
	path# a-mail-path-from-src-back-to-you
 
where you should replace a-mail-path-from-src-back-to-you by something 
that probably works to get email to you from DEC SRC. Upon receipt 
of your message, factor@src.dec.com will send you everything you 
need to help with F9, except input. To get input, we suggest that 
you first try and see if the whole thing works at your site. If you 
still like it after having seen what it is all about, and if you 
indeed want to help, then contact one of us personally, either by 
phone or by email, describing your machines and how many cycles you 
think they will be able to contribute (1 415 853 2221 = 
msm@src.dec.com, or 1 201 829 4878 or 1 415 643 6036 = 
lenstra@flash.bellcore.com).  We will accept collect calls.
 
Unlike our email-mpqs factorizations we cannot freely distribute 
inputs, because we only have a limited number of them. So, if you 
contact us, we assume that we can count on your contribution.  We 
are still running our mpqs factorizations, by the way; if you don't 
think you'll be able to live up to our expectations, but want to help, 
we suggest that you mail for our mpqs package, by sending mail to 
factor@src.dec.com with contents: 
 
	program#
	path# a-mail-path-from-src-back-to-you
 
If you decide to help us with F9, you can expect that your message 
will elicit a response from the daemon that reads factor@src.dec.com's 
mail.  You will receive various C-programs, and scripts to run them. 
Installation takes a few minutes, initialization of some auxiliary 
files takes about five minutes (on a DEC 3100 or a Sparc workstation), 
and after you got your inputs you almost don't have to look at it 
again. You do have to make sure every now and then that your machines 
have still inputs to work on; if everything is installed correctly, 
it will send you mail when it runs out. We tried to make the program 
as friendly for its environment as we could. This means, among other 
things, that
 
- it automatically mails its results to us;
- it automatically comes back after a reboot or a crash;
- it pauses as soon as it notices keyboard activity;
- it pauses as soon as the load (not including factoring) becomes too high;
- if pausing is not enough (because it's still in the swap-space), 
  then it can easily be killed for a fixed period of time, after 
  which it automically comes back;
- and finally, a feature that isn't useful for us at all, it can be
  killed forever.
 
Contributors to our email-mpqs factorization might consider switching 
to F9. The whole set-up is very similar, except for the way in which 
we handle tasks.
 
We should add that by sending those two lines to factor@src.dec.com, 
you won't get some dirty virus or anything like that. You get the 
source code of the same things we are using, and you can inspect 
those sources before compiling them.  If you don't like them you 
can change them in whatever way you like as long as we get output 
that is the same as the output of the unchanged program.  The code 
you receive is free of any restrictions on its use and modification, 
except that we'll get very mad if you use it to factor F9 before we 
do.  It's also free of any warranty; although we don't think it will 
do anything bad to your computers, we know that it may annoy other 
users, and that's your problem, not ours.

    .re. .13
    No wait a minute,
    
    >> Thanks to Maple, this is:
    >>
    >>134078079299425970995740249982058461274793658205923933777235614437217640300735\
    >>46976801874298166903427690031858186486050853753882811946569946433649006084097
    
    Maple is not the only one who can do large number computations.
    The BU(x) function in calreal computes (2^x) for large numbers.
    (i.e. 2^512 can be computed as follows:
    
    CALREAL> set noincremental print;
    CALREAL> bu( 512);
    
        BU ( 2 ^ 512 ) = 1340780792994259709957402499820584612747936582059239337772356144372
    1764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
    CALREAL>
    
    BTW: remember to add the +1 at the end in order to get the F9)
    /k