View Single Post
Old 2016-03-30, 14:40   #2
Tribal Bullet
jasonp's Avatar
Oct 2004

3×1,181 Posts

The expected performance of this is worse than that of CFRAC with the same optimizations, since at least in that case the numbers being batch factored are all of size near sqrt(N), whereas with QS the candidates grow in size.

'Early abort' is helpful in both these algorithms, since we expect a lot of small factors in relations but only a few large factors, so it would make sense to do a little sieving and reject sieve values unless only a little of the sieve value is unfactored. In that sense batch cofactorization can be seen as a memory-efficient method for avoiding having to sieve most of the traditional factor base. Making a small sieve run fast is quite easy, using a large sieve much less so.

Bernstein wrote around 2004 that it was a myth that sieving was always optimal; needless to say it was a bit controversial :)
jasonp is offline   Reply With Quote