From herman@cwi.nl Mon Sep 14 11:33:32 1998 From: Herman.te.Riele@cwi.nl To: wds@research.nj.nec.com Subject: factors Dear Warren, Better late than never as we say here: we have factored the number which you sent us in July 1997. Below is a draft announcement which I intend to send out on internet, but if you have any remarks/comments, please let me know. BW, Herman -------------------------------------------------------------------------- 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 linear algebra time for this matrix 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. 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. Additional information on p1 and p2: p1-1=2.2.41.1787.12391.26255958569. 369694651490973388789264004509304651895199414222703 p1+1=2.3.19.31.c67 (Note: mpqs is running at present on my workstation to factor c67=9974227237353013745699693054062007353270352460829071761928936844577) 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 ---------------------------------------------------------------------------