View Single Post
Old 2011-09-21, 14:09   #3
R.D. Silverman
R.D. Silverman's Avatar
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts

Originally Posted by jasonp View Post
o(1) means 'this can't be zero, but we expect it to drop to zero much faster than all the other terms grow'. The temptation to make it zero and keep going is overwhelming.

Incidentally, in practice the asymptotic bound on the factor base size is extremely conservative; you would be better off actually forcing the bound to a given size and choosing that size to optimize the actual runtime of your program. Don't be surprised if the best B goes down as the sieving speed increases.
It is (as implied but not stated by your answer) also implementation
and machine dependent. Note also that the asymptotic bound does
not use the large-prime variation. It assumes that all useful relations
factor entirely over the factor base.

The optimal B is also dependent on the large prime bound and whether you
use one or two large primes.

Experiment. Do (say) 1/10% of the estimated sieving using different B's.
R.D. Silverman is offline   Reply With Quote