walter@cwi.nl (Walter M. Lioen) (04/25/88)
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@mcvaxschoen@phoenix.Princeton.EDU (Eric R Schoenberg) (04/26/88)
I have a question about how you rate the algorithms for factoring large numbers. Is it chance that your program factored in such a relatively short time? Or can you gurantee a solution after a certain (reasonable) amount of time. Can you provide an average amount of time for factoring numbers of length n? I am asking because you say that you used general purpose algorithms and I'm not sure what you mean by general. Thank you. Randy Schoenberg
walter@cwi.nl (Walter M. Lioen) (04/26/88)
In article <2675@phoenix.Princeton.EDU> schoen@phoenix.Princeton.EDU (Randy Schoenberg) asks: > Is it chance that your program factored in such a relatively short time? > Or can you gurantee a solution after a certain (reasonable) amount of time. See the explanation of "general purpose algorithm" below. > Can you provide an average amount of time for factoring numbers of length n? Adding 3 digits roughly doubles the run time for n near 90 decimal digits. This factor of 2 drops (very!) slowly as n tends to infinity. > I am asking because you say that you used general purpose algorithms and I'm > not sure what you mean by general. General purpose algorithms, 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. The method we used is known as the "Multiple Polynomial Quadratic Sieve" method (MPQS). Special purpose algorithms depend on luck but, on the other hand, have factored larger numbers. They also depend upon the number being factored having small prime factors, and are generally useless if the number being factored is the product of two, nearly equal, primes. The well known "Elliptic Curve Method" (ECM) is an example of such a probabilistic method. -- Walter M. Lioen, CWI, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands. INTERNET: walter@cwi.nl BITNET/EARN: walter@mcvax
schoen@phoenix.Princeton.EDU (Eric R Schoenberg) (04/27/88)
In article <7537@boring.cwi.nl> walter@cwi.nl (Walter M. Lioen) writes: >The method we used is known as the "Multiple Polynomial Quadratic Sieve" >method (MPQS). > Thanks very much for the explanantion. Is there a good book or article you could recommend for an introduction to the subject of factorization of large numbers? I haven't studied the subject at all, but have always had a passing interest in it. (I am about to finish my undergraduate degree in math at Princeton, and have taken two semesters of Algebra -- just so you can suggest something for my level.) Does your MPQS method have anything to do with something I "discovered" while doodling in class a few years ago: I observed that the two polynomials x^2 + x + 1 and x^2 + x - 1 produce an awful lot of prime numbers, and that for the second one I think, any non-prime number which is produced by plugging in an integer for x has a common factor with some other number produced by plugging in a smaller integer. It has been a while since I looked into this, so I'm not sure how far I checked it or if there were any exceptions. Is there some theory behind this? x x^2 + x - 1 1 1 2 5 3 11 4 19 5 29 6 41 7 55 = 5 * 11 8 71 9 89 10 109 11 131 12 155 = 5 * 31 13 181 14 209 = 11 * 19 ... Not all the numbers have factors which are actually numbers produced by the polynomial. For example 43 1891 = 31 * 61 But notice that 31 has already been a factor of one of the numbers (x=12). I know that it has been proven that x^2 + x + 41 will produce the longest consecutive string of primes, but is there some general theorem about the factors of non-primes generated by a polynomial? My hunch is that there must be, otherwise you wouldn't be having such success at factoring those large numbers. As I said, I am a novice at this and any helpful hints would be appreciated. Thanks, Randy Schoenberg
walter@cwi.nl (Walter M. Lioen) (04/28/88)
In article <2687@phoenix.Princeton.EDU> schoen@phoenix.Princeton.EDU (Randy Schoenberg) writes: > Thanks very much for the explanantion. Is there a good book or article > you could recommend for an introduction to the subject of factorization of > large numbers? ... A good book and full of references itself: %A H. Riesel %T Prime Numbers and Computer Methods for Factorization %I Birkhauser %D 1985 > Does your MPQS method have anything to do with something I "discovered" > while doodling in class a few years ago: > ... no > ... > ... deleted stuff about polynomials (sometimes:-) `generating' primes ... > ... > I know that it has been proven that x^2 + x + 41 will produce the longest > consecutive string of primes, but is there some general theorem about the > factors of non-primes generated by a polynomial? My hunch is that there must > be, otherwise you wouldn't be having such success at factoring those large > numbers. ... I am not familiar with such a theorem. Also there is no relation (at least that I know of) with your observation and MPQS' success of factoring large numbers. For an algorithmic description of MPQS and other references on (MP)QS see: %A R.D. Silverman %T The Multiple Polynomial Quadratic Sieve %J Mathematics of Computation %V 48 %N 177 %P 329-339 %D January 1987 %K MPQS Perhaps we should move an eventual further discussion into a private e-mail combat? Greetings, -- Walter M. Lioen, CWI, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands. INTERNET: walter@cwi.nl BITNET/EARN: walter@mcvax
randall@ncr-sd.SanDiego.NCR.COM (Randall Rathbun) (04/29/88)
"Computational Methods for Factoring Large Integers" by Marvin C. Wunderlich
in the winter issue of ABACUS vol 5 #2, pgs 19-33 is an excellent article on
current methods of factoring large numbers, including the MPQS, with 17 listed
references at the end.
Hope this helps...
--
Randall L. Rathbun tele: 619-485-2999/or 2358/or 3272
NCR E&M-S.D. Dept 2861 domain: Randall.Rathbun@SanDiego.NCR.COM
16550 W Bernardo Dr route: {sdcsvax,cbosgd,nosc.arpa,ihnp4}!
San Diego, CA 92127 ncr-sd!randall.rathbuntmk@bentley.UUCP (TM Ko) (04/29/88)
In article <2687@phoenix.Princeton.EDU> schoen@phoenix.Princeton.EDU (Eric R Schoenberg) writes: > >I know that it has been proven that x^2 + x + 41 will produce the longest ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >consecutive string of primes, but is there some general theorem about the ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > >Randy Schoenberg Are you considering quadratics only? Even for the quadratic case, would someone show me how to prove this or refer me to any reference which contains a proof. I believe I have seen other polynomials that produce "?more than 100?" consecutive string of primes. (may be I am wrong) ****************************************************************************** Tsz-Mei Ko ARPA: bentley!tmk@att.ARPA AT&T Bell Labs UUCP: tmk@bentley.UUCP LC 3S-D20 184 Liberty Corner Road {att-ih,decwrl,amdahl,linus}!ihnp4!bentley!tmk Warren, NJ 07060-0908 *******************************************************************************
schoen@phoenix.Princeton.EDU (Eric R Schoenberg) (04/29/88)
In article <1147@bentley.UUCP> tmk@bentley.UUCP (59481-TM Ko) writes: >In article <2687@phoenix.Princeton.EDU> schoen@phoenix.Princeton.EDU (Eric R Schoenberg) writes: >> >>I know that it has been proven that x^2 + x + 41 will produce the longest ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >>consecutive string of primes, but is there some general theorem about the > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >Are you considering quadratics only? >Even for the quadratic case, >would someone show me how to prove this or refer me to any reference which >contains a proof. >I believe I have seen other polynomials that produce "?more than 100?" >consecutive string of primes. (may be I am wrong) >Tsz-Mei Ko Thanks to all who sent me e-mail with references and comments. I appreciate it very much. As to this question, I seem to remember John Conway mentioning in our Junior seminar that this was proved for quadratics. It was 18 months ago, so I'm not sure. I could ask him again. Randy