From Peter-Lawrence.Montgomery@cwi.nlTue Jul 2 19:47:26 1996 Date: Tue, 2 Jul 1996 11:27:13 -0400 From: Peter-Lawrence.Montgomery@cwi.nl To: Multiple recipients of list NMBRTHRY Subject: SNFS using quadratic and cubic polynomials Special Number Field Sieve using Quadratic and Cubic Polynomials Marije Elkenbracht-Huizing (marije@cwi.nl) Peter L. Montgomery (pmontgom@cwi.nl) Centrum voor Wiskunde en Informatica, Amsterdam 29 June 1996 We completed the factorization of 10^193 - 1, using a variant of the Special Number Field Sieve (SNFS): 10^193 - 1 = 3 * 3 * 773 * 39373 * 561470969 * 639701219449517 * 4274417556076113498947 * 26409540111952717487908689681403 * 447798287131284928051408304965265782892174953181087929 * 2010734797237741296291807480478464451813538790168907747 The factors through p15 = 639701219449517 appear in the 1988 edition of the Cunningham table. Wagstaff found the p22 by ECM in 1989. Montgomery found the p32 by ECM earlier this year, leaving the c108 cofactor n = 900403598078332057414450774519008597054323652282471624\ 134999932247510711400923528055469318913913955096285963 The usual SNFS cannot take advantage of known non-algebraic factors of a number. Our variant of SNFS used the information that n divides 10^193 - 1, as well as the small size of n. Specifically, since n divides 10^193 - 1, we know a value for cbrt(10) == 10^129 (mod n). Given m in Q(cbrt(10)) \ Q, we can choose the minimal polynomial for m over Z as our cubic, and use lattice basis reduction to find a quadratic satisfied by (m mod n). Since n is 108 digits, we expect the quadratic to have coefficients approximately 108/3 = 36 digits. We chose the two polynomials f(X) = 5 X^3 - 108 g(X) = 60835576517246011990383510078956198 X^2 - 389138363159121114815712194873126731 X + 555553034174397658278366349076513150 with common root m = 6/cbrt(10) == 6 * 10^64 (mod n). This (m, g) sieved better than other pairs we tried. The resultant of f and g is 4*n. The discriminant of g is divisible by 3 and is congruent to 1 mod 8. This discriminant is a quadratic residue modulo the primes 5, 7, 13, 17, 23, 29, 31, 41, 43, 47, 59, 61, 67, 79, 83, 89, 97 but a non-residue modulo 11, 19, 37, 53, 71, 73. We might have done better by replacing X by X + 3: the real roots of g(X) are 2.15 and 4.25, so g(X + 3) has smaller coefficients than g(X). Using about 60 SGI workstations for one week, we found 27 million relations using |a| <= 5000000 and 0 < b <= 770000. The factor base bounds were 4 million, and the large prime bounds were 30 million. Block Lanczos on the 518636 x 523271 matrix took 26 hours on an SGI Challenge. The square root took 48 minutes, and found the factorization on the first dependency. With bounds of 10^6.7 for a and 10^5.8 for b, the norms were bounded approximately by 10^48 (quadratic) and 10^21 (cubic). The usual SNFS, using f(X) = 8X^5 - 25 with m = 5 * 10^38 (without talking advantage of the known factors of 10^193 - 1) would have norm bounds approximately 10^34 (degree 5) and 10^44 (linear). Two quadratic polynomials with coefficients approximately 10^27 would give norm bounds approximately 10^40 and 10^40. Using X^4 - 10 (known root 10^145) and a cubic with 27-digit coefficients would give norm bounds approximately 10^27 (degree 4) and 10^47 (cubic). We thank the many individuals at CWI who made their workstations available for this experiment.