🚀 go-pugleaf

In article <26250.Jul2400.28.0492@virtualnews.nyu.edu> brnstnd@nyu.edu (Dan Bernstein) writes:
>Arjen Lenstra and I are pleased to announce the record non-networked
>factorization of a difficult number (no prime factors under 40 digits).
>The number is (2^488 + 1)/257. Its prime factors are p_49 and p_97,
>...
>This computation can be seen as a substantial step towards a practical
>implementation of the general number field sieve (GNFS): it depended on
>character columns and a square root inside the algebraic number field
>rather than explicit generators of the unit group and of prime ideals of
>the field. We are investigating the practical effectiveness of GNFS.

Question: is the technique used here generally applicable to all
composite numbers or is it applicable to composites of special forms?

In article <BrwFFH.CAt@cs.psu.edu> so@fortran.cs.psu.edu (Nicol C. So) writes:

[in reply to a posting by Dan Berstein about the Number Field Sieve]

 
>Question: is the technique used here generally applicable to all
>composite numbers or is it applicable to composites of special forms?

It is applicable to all numbers,   BUT:

The reason they were able to factor a 145 digit number with the method
is because that particular number had a polynomial representation with
VERY small coefficients. The polynomial they used was x^5 + 4, i.e.
single digit coefficients. A general number of 145 digits will yield

a polynomial with coefficients around 23-24 digits --> a BIG difference.
The speed of the method strongly depends on the size of these coefficients.

My estimates show that the Number Field Sieve becomes faster than the
quadratic sieve for general integers somewhere between 135 and 140 digits.
[Although there are several optimists who think it might be slightly lower].
135 digits is currently out of reach.

Currently, NFS is better than other methods only when one can find
a polynomial representation of the number with very small coefficients.
This restricts the set of numbers that can be factored with the method
to be very small. At present this seems to be an unsurmountable obstacle
to the method. 

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

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