On Saturday, June 15, 1996, we completed the factorization
of a 116 digit divisor of 2^481 + 2^241 + 1.  This number
was on the Most Wanted List for the Cunningham project [2].
This was done with the self initializing quadratic
sieve (siqs) [5,1,4].

The number we factored was:

953545590320837525749458774465695807200319038639754728254542058450367\
02088404124447972746088891967876336741550386837

which is divisible by the following two primes (36 digits, 81 digits):

258190389365279446113985999067417377

and 

369318777768986567474423605441467763425794698617365769175220216931933\
959983220981


This set the record for the largest quadratic sieve factorization
for the Cunningham project.

There have been three other 116 digit quadratic sieve factorizations
for the Cunningham project, but ours has the highest most significant
digits.  However, due to the poor factor base, we had to use
a multiplier of 29, which means that we were actually sieving
upon a 118 digit number.  Compared to other factorizations, we
had a relatively small amount of computing power.  We also
did NOT use the double large prime variation [3] (requires too
much disk space).

The factorization took approximately 11 workstations and 10
months real time of sieving.  Eight of these workstations were
Sun SPARC 5's.  These each had a 85 Mhz MicroSPARC processor,
64 Kbyte on board cache, and 32 Mbytes of RAM.  The other
three workstations were a SPARC 2, a SPARCstation 1000, and a
SPARC 20.  However, these three had other heavy jobs to
run (the first two of these were being used as servers),
which prevented them from performing better than many of
the SPARC 5's.  The SPARC 5's were also being used by other
graduate students and professors for their research.  The
most productive computers got an average of about 300 smooths
relations per week, and a total of about 90000 smooths were
needed (the total factor base size was 196701.  The rest of the
relations came from semi-smooths).  For comparison purposes, here
are some benchmarks on our Sparc 5's done with the nsieve program,
available via anonymous ftp from ftp.nosc.mil in  directory
'pub/aburto' (note: we used the compiler cc rather than gcc):

 
   Sieve of Eratosthenes (Scaled to 10 Iterations)
   Version 1.2b, 26 Sep 1992
 ...
   Relative to 10 Iterations and the 8191 Array Size:
   Average RunTime =    0.050 (sec)
   High  MIPS      =     39.0
   Low   MIPS      =     30.6
 

There are ways which the sieving stage could have been made faster,
but I never had any free time to program these improvements.
For example, after using the multiplier of 29, the number was congruent
to 1 mod 8.  It follows that whenever a residue is divisible by 2,
it is also divisible by 2^3.  Perhaps a significant increase in
speed could have been obtained by only sieving on these residues
(ie not sieving on those which are not divisible by 2).  Also
according to [3], the double large prime variation may increase
the speed by a factor of 2.5 for numbers this large.

Many of the computers used came from Andrew Granville's Presidential
Faculty Fellows grant.  Also, Red Alford, David Benson, and
Carl Pomerance have generously allowed us to use their computers.
Carl Pomerance and Red Alford have suggested many ideas to increase
the speed of sieving, including the remark above about only sieving on
residues which are divisible by 2^3.  Acknowledgements are also due to
our system administrators, Shaheed Bacchus and Ron Rouhani, who were
very helpful and also tolerant of the factoring programs.

			Scott Contini

			Dept Of Mathematics
			University of Georgia


[1] W. R. Alford, Carl Pomerance, "Implementing the self initializing
	quadratic sieve on a distributed network," pp. 163-174; in:
	A.J. van der Poorten, I. Shparlinski, and H.G. Zimmer (eds),
	"Number theoretic and algebraic methods in computer science",
	World Scientific, 1995.

[2] "Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high
	powers," by John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant
	Tuckerman, and S. S. Wagstaff, Jr., American Mathematics Society,
	Providence, Rhode Island, 1988.

[3] A. K. Lenstra, M. S. Manasse, "Factoring with two large primes," Advances
	in Cryptology, Eurocrypt '90, Lecture Notes in Computer Sci. 473
	(1991), 72-82.

[4] C. Pomerance, "Analysis and comparison on some integer factoring
	algorithms," pp. 89-139; in: H.W. Lenstra , Jr., R. Tijdeman (eds),
	"Computational methods in number theory", Mathematical Centre Tracts
	154, 155, Mathematisch Centrum, Amsterdam, 1982.

[5] C. Pomerance, J. W. Smith, R. Tuler, "A pipeline architecture for factoring
	large integers with the quadratic sieve algorithm,"  SIAM J. Comput.,
	v. 17, 1988, pp. 387-403.