🚀 go-pugleaf

         Robert Silverman posted:
:The problem I have is that one must add the time you spent looking for
:good polynomials to the total run time. However, looking for good
:polynomials is non-deterministic. We do not know of a deterministic
:method which, if you spend time t, you will succeed in reducing the
:coefficients by size F(t). Thus, you cannot predict AT all how long
:a factorization will take. On the other hand, using the base M method,
:while sub-optimal, is deterministic.
:
:If you estimate sieve time is T, and you spend (say) .2T looking
:for a better polynomial, there is no guarantee of finding one, and
:you will have increased total time by 20% for no good reason. Nor do
:you have assurances that spending the extra time will reduce the sieve time
:by more than the time you spent searching.

         I don't understand what you are saying here.  Suppose we use a
brute force technique (trying a bunch of different m values) to search
for good polynomials.  We can certainly estimate what measure we will
obtain as a function of the number of m values that we try.  We can then
predict how long the total factorization will take as a function of the
number of trials.  Minimizing this function will tell us how many m
values we should test in order to minimize the expected running time
(this assumes we fix this number in advance, actually we should quit
early if we are lucky, try more if we are unlucky, this is a detail).
It is true this does not give a worst case running time, however is it
not the case that we do not have worst case guaranteed bounds for any
competitive factoring method?  Do you not choose the number of primes
in your factor base by similar reasoning?
                          James B. Shearer