Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Factorization of a 116 digit number
Posted:
Jun 18, 1996 11:42 AM


On Saturday, July 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:
95354559032083752574945877446569580720031903863975472825454205845036702088404124447972746088891967876336741550386837
which is divisible by the following two primes (36 digits, 81 digits):
258190389365279446113985999067417377
and
369318777768986567474423605441467763425794698617365769175220216931933959983220981
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 semismooths). 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. 163174; 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), 7282.
[4] C. Pomerance, "Analysis and comparison on some integer factoring algorithms," pp. 89139; 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. 387403.



