From herman Tue Sep 15 14:04:42 1998
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: 186-digit SNFS factorization
Status: R

--------------------------------------------------------------------------
186-digit SNFS factorization: On to factoring a 512 bits RSA key with GNFS
--------------------------------------------------------------------------

       CWI (Centrum voor Wiskunde en Informatica) Amsterdam announces the
completion of the factorization with the Special Number Field Sieve (SNFS)
of the number N = q^41 - 1 where q = 2^15 - 135 = 32633.
This 186-digit number

        N = 11479871829350896175708878568178066783490157668510\
            74717395313897372101603192784500981496996372219763\
            23286874712940112289135951719949211771917273399032\
            116161158648055707302951416350994232

is the largest ever factored by SNFS.  The previous record was the
181-digit number 12^167 + 1, factored by the CWI factoring group
in September 1997.

        We used the polynomials

            f(X) = q^8 X - 1
            g(X) = X^5 - q

with common root m = q^(-8) (mod N).
The factor base bound was 16.7 million for f and 10.0 million for g.
Both large prime bounds were 200 million, with two large primes allowed
on each side.  We sieved over |a| <= 23.1 million and 0 < b <= 3 million.
Over this skewed rectangle, the terms  a^5  and  b^5 * q  in
b^5 * g(a/b)  have bounds about the same size, while the  q^8 * a  term
in b * f(a/b)  grows only slightly.

        The sieving was carried out on 88 SGI machines at CWI
(a mixture of O2's, Indy's and R10000's).  It started on July 27, 1998
and finished on September 6, 1998, spanning 42 calendar days.
Total sieving time was 1848 CPU days, about 5.1 CPU years.
About 18 million relations were required but the sieving continued
an extra week until about 20.5 million relations had been generated.
This sieving data occupied 700 Mb when compressed.

        This 14% extra data enabled us to experiment with the filter routine.
The filter routine discards some relations and combines other relations,
to generate an input matrix for the linear algebra step in SNFS.
It is of crucial importance that this matrix be as small as possible.
The linear algebra code uses a Block Lanczos algorithm over GF(2).
Given an  n x n  matrix with w nonzero elements,
the Block Lanczos code uses about n/63 iterations on a 64-bit machine.
Each iteration has matrix multiplies of various sizes:

                                       Cost per product
        (n x n) * (n x 64)             O(w)    (low  constant)
        (64 x n) * (n x 64)            O(n)    (high constant)
        (n x 64) * (64 x 64)           O(n)
        (64 x 64) * (64 x 64)          O(1)

The total cost becomes O(n*w) + O(n^2).

        Using our old filter code on the full 20.5 million relations,
we got a matrix with n ~= 2.5 million and w ~= 69 million.
The average density is 28 nonzero elements per row or column.
The matrix does not have any rows for prime ideals of norm below 50
-- including such primes would raise w to 81 million.
The CPU time to find linear dependencies in this matrix with the Block
Lanczos iterative algorithm was about 25 hours on the Cray C90 at the 
Academic Computing Centre Amsterdam (SARA). On a 250 MHz SGI R10000 
processor this would have taken about 2 weeks. The square root step 
found two large factors (see below) at the second dependency, after 
3.7 CPU hours on one SGI R10000 processor.

        The factored number was "missioned" to us by Warren D. Smith
of the NEC Research Institute in Princeton (New Jersey), USA,
who needed its complete factorization in order to verify the reliability
of a random number generator construction depending on this N.
Smith already knew the factors

        q - 1 = 2^3 * 4079
        12276959
        6583132529
        303771374062875780001

but the factors of the remaining 144-digit composite cofactor were unknown.

        The Special Number Field Sieve requires the input number
to be of the form b^n +- 1 for small b (or other nice polynomial form),
so the known factors do not make the number any easier for SNFS.
Of course, an alternative was to apply the quadratic sieve method
or GNFS to that 144-digit cofactor but then the sieving time
would be much larger than 5.1 CPU years (we estimate at least 100 CPU years).
We tried ECM on the cofactor (about one month of MIPS R10000 time), 
without success. Richard Brent tried ECM too.

        Although the progress of 181D to 186D for SNFS is not spectacular,
the experience which we have collected so far has helped us to improve our 
GNFS code to such an extent that we expect to start to attack a 512-bit 
RSA key at short notice. Our aim is to finish this successfully before the 
turn of the millennium, but we realize that the support of many computers
will be indispensable to reach this goal.

        The prime factors of the c144 are

p1 = 35248919056805550577302715253055133986457425596569939606656862808735117
            (71 decimal digits)
and

p2 = 4065156729013581506575981668657719473245161586950309024883650879544686723
            (73 decimal digits)

Primality of p1 and p2 was proved twice, viz. with help of the Jacobi sum 
test program of H. Cohen, A.K. Lenstra and D.T. Winter, and with help of the
cyclotomy test program of Bosma and Van der Hulst. CPU time was a few seconds.
 
Factorizations of p1-+1 and p2-+1:

p1-1=2.2.41.1787.12391.26255958569.
     369694651490973388789264004509304651895199414222703
p1+1=2.3.19.31.274228773106481.191586760095993389.
     189845691099852872604609472956295253

p2-1=2.41.119311.11106163.348643196801343332465074129.
     107309387946064797284587902392893
p2+1=2.2.3.17.31.107.347.1079779.1619119.622502477.
     15908068430855981046386706574615762707250997

        We thank the Dutch National Computing Facilities Foundation
for providing access to the Cray C90 and all those CWI workstation owners
for allowing us to use their idle evening, night and weekend cycles.

Stefania Cavallar
Peter Montgomery
Herman te Riele
{cavallar, pmontgom, herman}@cwi.nl
---------------------------------------------------------------------------