From: lenstra@BELLCORE.COM (Arjen Lenstra)
Newsgroups: sci.math.numberthy
Subject: rsa129
Date: 29 Apr 94 13:06:04 GMT

RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429357069
35245733897830597123563958705058989075147599290026879543541 (129 digits)
Factors: 3490529510847650949147849619903898133417764638493387843990820577 * 3276
9132993266709549961988190834461413177642967992942539798288533
Date: April 1994
Method: ppmpqs
Time: Approximately 5000 mips years
Name: Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul Leyland, and more than
 600 volunteers
Email: lenstra@bellcore.com
--------------------------------------------------------------------------------

encoded message:

968696137546220614771409222543558829057599911245743198746951209308162\
98225145708356931476622883989628013391990551829945157815154

public exponent:

9007

`secret' exponent:

106698614368578024442868771328920154780709906633937862801226224496631\
063125911774470873340168597462306553968544513277109053606095

decoded message:

200805001301070903002315180419000118050019172105011309190800151919090\
618010705

decoded decoded message:

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE



To find the factorization of RSA-129, we used the double large prime
variation of the multiple polynomial quadratic sieve factoring method.
The sieving step took approximately 5000 mips years, and was carried
out in 8 months by about 600 volunteers from more than 20 countries,
on all continents except Antarctica. Combining the partial relations
produced a sparse matrix of 569466 rows and 524338 columns. This matrix
was reduced to a dense matrix of 188614 rows and 188160 columns using
structured Gaussian elimination. Ordinary Gaussian elimination on this
matrix, consisting of 35489610240 bits (4.13 GigaByte), took 45 hours
on a 16K MasPar MP-1 massively parallel computer. The first three
dependencies all turned out to be `unlucky' and produced the trivial
factor RSA-129. The fourth dependency produced the above factorization.

Derek Atkins
Michael Graff
Arjen Lenstra
Paul Leyland