herman@cwi.nl (Herman te Riele) (02/11/91)
We have factorized for the first time a number of more than 100 decimal digits on a single computer. The computer is a Cray Y-MP4/464, which belongs to NWO (Netherlands Organization for the Advancement of Science) and which is governed by SARA (The Academic Computer Centre Amsterdam) and the NWO - foundation NCF (National Computing Facilities). The program was written by Herman te Riele, Walter Lioen and Dik Winter of the CWI Amsterdam (Centrum voor Wiskunde en Informatica). The method was the multiple polynomial version of the quadratic sieve of Kraitchik and Pomerance (with improvements by Montgomery and Silverman). For the MPQS-intimates: the factor base used consisted of about 50,000 primes; the time used was about 475 CPU-hours for collecting the 50,000 relations needed; the Gaussian elimination took about 0.5 CPU-hour. We used just one processor of the four-processor Cray Y-MP4. We could also have done the job in about five days by using the complete four-processor machine. The job was started on Jan. 18, 1991 and finished on Febr. 11, 1991, the day that CWI celebrated its 45-th birthday. The factorized number consists of 101 decimal digits, and can be written as (2^463+1)/(3.2356759188941953.76834966209858049526107). These three given prime factors were known already. The Cray Y-MP4 has now found the two remaining prime factors (of 35 and 66 digits, resp.): 88119307925269041107418404833666787 and 497532604551403800659718805165333685595913106186792454026995210139. The previous one-computer record was a 92-digit number, factorized by us in the spring of 1988 on a NEC SX-2 computer (in about 100 hours CPU-time). Herman, Walter and Dik CWI Kruislaan 413 1098 SJ Amsterdam The Netherlands