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

mickfrancis · 2016-05-04, 14:39

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 similarly-sized primes (why would I sieve with the prime 257 but not 256 (2⁸), 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?

jasonp · 2016-05-06, 02:19

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.

mickfrancis · 2016-05-06, 08:13

Quote:

Originally Posted by jasonp

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.

Makes sense - thanks Jason.

2016-05-04, 14:39	#1
mickfrancis Apr 2014 Marlow, UK 2³×7 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 similarly-sized primes (why would I sieve with the prime 257 but not 256 (2⁸), 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime Gap Length with consecutive integers divisible by small primes	carpetpool	Prime Gap Searches	47	2022-11-15 18:53
Non-sieving version of Quadratic Sieve	mickfrancis	Factoring	5	2016-03-31 06:21
Sieving polynoms in Quadratic Sieve	ThiloHarich	Factoring	13	2009-01-04 18:19
Small Primes	Housemouse	Math	2	2008-06-04 05:23
Using p=2 for sieving (Quadratic sieve algorithm)	R1zZ1	Factoring	36	2007-11-02 15:59

2016-05-06, 02:19	#2
jasonp Tribal Bullet Oct 2004 3·1,193 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.