🚀 go-pugleaf

In article <1992Jul25.004256.4641@linus.mitre.org> bs@faron.mitre.org (Robert D. Silverman) writes:
> The reason they were able to factor a 145 digit number

(2^488 + 1)/257 had 146 digits, last I counted.

> A general number of 145 digits will yield
> a polynomial with coefficients around 23-24 digits --> a BIG difference.

Take any 150-digit number n. Now try to find positive integers m and m',
together with six coefficients c_0 through c_5, such that n = c_0 m'^5 +
c_1 m'^4 m + ... + c_5 m^5. We could of course choose m around 25
digits, and m' = 1, and write n in base m, giving coefficients around 25
digits. This is where Bob gets his estimates.

If you choose all eight of these parameters up to 25 digits then you get
about 200 digits to play with---and n has only 150 digits. So we should
in theory (modulo some plausible heuristics) be able to chop those extra
50 digits out of the c's, ending up with 25 - 50/6 < 17 digits per c for
some pair (m,m').

Exercise for the reader (yes, kids, you can try this at home!): Can you
compute m and m' for RSA-150 so that the c_i are smaller than ``23-24
digits''? Can you beat Bob's best polynomial? Hint: Brute force.

Now can you compute m and m' so that the c_i are under 20 digits?

> The speed of the method strongly depends on the size of these coefficients.

This is true.

> My estimates show that the Number Field Sieve becomes faster than the
> quadratic sieve for general integers somewhere between 135 and 140 digits.

Ah, yes, and didn't Adleman's estimates a year ago ``show'' that GNFS
would probably be slower than MPQS around 330 digits?

---Dan