View Single Post
Old 2016-05-04, 14:39   #1
Apr 2014
Marlow, UK

708 Posts
Default Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve

As I understand it, in the Small Prime Variation of the Quadratic Sieve, primes less than a threshold (Pmin, say) are not used for sieving, as the cost of sieving is disproportionately high given the contribution of these primes.

Sieving with powers of primes that are themselves used in sieving is also less beneficial than sieving with other primes of size comparable to these powers (e.g. the contribution for p^2 is the same as for p).

However, it seems to me that for primes in the factor base less than Pmin it ought still to make sense to sieve with the lowest powers that are Pmin or above, as the contribution is just as high as that of similarly-sized primes (why would I sieve with the prime 257 but not 256 (28), for example)?

In the implementations I've looked at, this does not appear to be done, and I was wondering why; is the benefit outweighed by the added complexity?
mickfrancis is offline   Reply With Quote