🚀 go-pugleaf

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"