🚀 go-pugleaf

In article <1992Aug24.131342.7986@linus.mitre.org> bs@gauss.mitre.org (Robert D. Silverman) writes:
> :than Adleman's ridiculous estimates a year ago. They are based on
> Ah, yes. Now he's belittling Len Adleman too. A great way to argue.

As you know, Bob, Adleman's 330-digit estimates had amazingly little
mathematical validity. This is why you're attacking me rather than
defending Adleman's arguments---there's nothing correct to defend.

Adleman stated that it was not clear whether GNFS (without homogeneous
polynomials, of course) would be faster than MPQS for 330-digit numbers.
It was, at that time, quite clear that GNFS would be much faster. It is
easy for an expert to see where Adleman's ``analysis'' departed solid
mathematics and entered the realm of wishful thinking so as to prove his
claim that GNFS was of no practical importance---but the damage has been
done. What was Adleman's motive in trying to discourage practical GNFS
research? What is your motive, Bob?

> How do you know they were suboptimal?

I know because others at the conference reported that to me.

> They might well have been, but since
> you were not at the conference where I presented them,

You're frothing, Bob.

> Furthermore,
> I asked Arjen how much speedup was obtained by the lattice sieve when you
> did 2,488+, and he said he did not know.

Correct. We simply don't have enough data. One might guess any number
between 1.5 and 2.5 for the speedup, but without a non-lattice MasPar
implementation there's no solid basis for comparison. The fact remains
that you didn't take the lattice sieve into account.

> :I defy you to make a statement of the form ``GNFS will use more than G
> :MIPS-years to factor RSA-129, while MPQS will take under M MIPS-years to
> :factor RSA-129, and G > M,'' rather than hiding behind loose comparisons
> OK, I will.
  [ ... ]
> I estimate
> that you will need to find 14 digit coefficients to equal this with GNFS.

No, Bob, you're still dodging.

You have claimed that the crossover point is 135 digits. If the
crossover point is 135 digits then GNFS should be expected to be
somewhat slower than MPQS at 129 digits. Surely you can back up this
statement by presenting your *numerical* estimates for how long GNFS
will take at 129 digits. There is obviously some breakeven point where
searching for a better polynomial won't be worthwhile; surely you can
estimate where that point will be.

> Furthermore, as you are well aware (or should be), there is a fair amount
> of variablility in the number of cycles that one obtains from a fixed number
> of relations.

Yes, indeed! This is one of the reasons that estimating GNFS yield is so
difficult---and that it's so irresponsible of you to pretend that you do
have accurate estimates.

> Rather than state that my claims
> have no validity, why don't you post some estimates of your own, based on
> your experiments, and let others decide who is right.

Because, Bob, in case you haven't been listening, my entire point is
that NOBODY HAS ACCURATE ESTIMATES.

> You and I both know that between 100 and 150 digits, PPMPQS and GNFS only
> vary in run time by a factor of 2 to 3.

No, Bob, I don't know that. That's the estimate which Buhler, Lenstra,
and Pomerance obtained by setting o(1) to 0---but they correctly point
out the inaccuracies involved. You pretend that your numbers are exact.
Why?

> :> But he still lacks data on QS. Lenstra and Manasse have
> :> done a few dozen numbers with QS. I've done in excess of 500.
> :I can't speak for either Arjen Lenstra or Mark Manasse, but it seems to
> :me that a few dozen numbers ranging up to 116 digits have far more
> :relevance to 129-digit factorizations than several hundred wimpy
> :numbers.
> Define 'wimpy' please for the rest of the audience.

Under 100 digits. You should be ashamed of having impugned the adequacy
of Lenstra and Manasse's data.

---Dan