

Thread Tools 
20160504, 14:39  #1 
Apr 2014
Marlow, UK
38_{16} Posts 
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 (P_{min}, 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 P_{min} it ought still to make sense to sieve with the lowest powers that are P_{min} or above, as the contribution is just as high as that of similarlysized primes (why would I sieve with the prime 257 but not 256 (2^{8}), 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? 
20160506, 02:19  #2 
Tribal Bullet
Oct 2004
2^{2}×883 Posts 
Once the problem size gets above a fairly small threshold, the runtime needed for sieving small primes becomes insignificant compared to sieving everything else; there are only a few such, and they cache nicely, so they're done in a flash compared to the thousands of larger primes you must also sieve with.

20160506, 08:13  #3  
Apr 2014
Marlow, UK
2^{3}·7 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime Gap Length with consecutive integers divisible by small primes  carpetpool  Prime Gap Searches  45  20170930 20:51 
Nonsieving version of Quadratic Sieve  mickfrancis  Factoring  5  20160331 06:21 
Sieving polynoms in Quadratic Sieve  ThiloHarich  Factoring  13  20090104 18:19 
Small Primes  Housemouse  Math  2  20080604 05:23 
Using p=2 for sieving (Quadratic sieve algorithm)  R1zZ1  Factoring  36  20071102 15:59 