Xref: utzoo sci.math:3475 sci.crypt:1035
Path: utzoo!mnetor!uunet!mcvax!walter
From: walter@cwi.nl (Walter M. Lioen)
Newsgroups: sci.math,sci.crypt
Subject: New Factorization Records
Message-ID: <7535@boring.cwi.nl>
Date: 25 Apr 88 12:01:19 GMT
Organization: CWI, Amsterdam
Lines: 80
Keywords: 4,6,8,9,10,12,14,15,16,18,...
Reply-To:


New Factorization Records
=========================

by
Herman te Riele, Walter Lioen and Dik Winter
Centre for Mathematics and Computer Science Amsterdam, The Netherlands
25 April 1988

We have just factorized an 87- and a 92-digit composite number
(denoted in the sequel by c87  and  c92, respectively).
The c92 is a 'most wanted' and the c87 a 'more  wanted' number in 
Wagstaff's Update 2.1 to the Second Edition of the book: 'Factorizations
of b^n +- 1 (to appear May or June 1988).

The c87 is the number (7^122 + 1)/(2.5.5.4497653.133440673) =

     42142151862206025464266996449410193418719493951400\
     8498829323679884430081886740302539869 .

Its prime factors are:

     369232401898464835382701047039367301441
and
     1141344899459682026753500636360162456697950330909 .

The c92 is the number (6^131 - 1)/(5.263.3931.6551) =

     25590419435661766569669195465155692745666184377627\
     375121409756912567458209805153386642764777 .

Its prime factors are:

     1284827442574221936870974393373403
and
     19917397922626842334449833677404096613537638684348856178059 .

Both numbers were factorized on the NEC SX-2 of the Dutch National Aerospace
Laboratory in The Netherlands. On this machine, which is the world's fastest
known single CPU-vector computer, the c87 took about 30 CPU-hours and the
c92 about 95. We used a general purpose factoring algorithm (a variant
of the so-called quadratic sieve; the number of primes in the factor base
was 18811 for the c87 and 24334 for the c92). Attempts by others to factor
both numbers by special purpose algorithms (like the Elliptic Curve Method) 
have failed despite the use of several years of computing time on these numbers
(on a cluster of VAXes).

The factorization of the c92 means a new absolute record for general purpose
factoring algorithms. 
The previous record was established only a few weeks ago by Robert Silverman 
of the MITRE Corporation (Bedford MA, USA). He spent a total of 15,000 CPU
hours on a parallel network of 24 SUN-3 workstations (about 625 hours on each
machine) using another variant of the quadratic sieve method. This yielded the
decomposition of the 90-digit composite number (5^160 + 1)/(5^32 + 1)
into a 41- and a 49-digit prime. 

The factorized c87 and c92 are also new records for single CPU-
computers. The previous record was established
by us in December 1986, when we factorized an 82-digit composite number
on the CDC Cyber 205 vectorcomputer of the Academic Computer Centre 
Amsterdam. Computing time spent on this number was about 70 CPU-hours.
Our program on the NEC SX-2 runs about 10 times as fast as our program on the
Cyber 205.

Acknowledgements
----------------
We like to thank the Dutch National Aerospace Laboratory (NLR) for the 
provision of computer time (and memory!) on the NEC SX-2 and for the 
hospitality during the period when we converted and optimized our program
on the SX-2. In particular, we like to mention the very stimulating atmosphere 
at the NLR and the invaluable technical and operational support during 
this project.
We also acknowledge financial support by the Dutch 'Werkgroep Gebruik 
Supercomputers'.


-- 
Walter M. Lioen,
CWI, P.O. Box 4079, 1009 AB  Amsterdam, The Netherlands.
INTERNET:    walter@cwi.nl
BITNET/EARN: walter@mcvax