Quadratic Sieve optimizations

[Ilya Gazman]

Please share the quadratic sieve optimizations you know, and remember, there is no optimization to small if it makes the code run faster ;)

Here are some examples to get you started:

1. Big primes - If you found a relation with all its primes in the primes base except one big prime, then keep it. If you find another one, you can multiply them together to get a b-smooth value.

2. Ignore small primes - Sieving the value 3 requires more time than 11, 13, 17, 19, and 23 combined, instead, we can just adjust the threshold to capture them during the trial division of the b-smooth candidates.

[xilman]

Originally Posted by Ilya Gazman

Please share the quadratic sieve optimizations you know, and remember, there is no optimization to small if it makes the code run faster ;)

Establish where it is quicker to use QS and where to use NFS.

No point making a program 10% faster if another program is 1000% faster.

Purely within QS, we found that three large primes can make abig improvement, but only when factoring large enough integers. In those days (roughly 20 years ago) the break-even point was at roughly 100 digits.

[Till]

Originally Posted by Ilya Gazman

Please share the quadratic sieve optimizations you know, and remember, there is no optimization to small if it makes the code run faster ;)

Here are some examples to get you started:

1. Big primes - If you found a relation with all its primes in the primes base except one big prime, then keep it. If you find another one, you can multiply them together to get a b-smooth value.

2. Ignore small primes - Sieving the value 3 requires more time than 11, 13, 17, 19, and 23 combined, instead, we can just adjust the threshold to capture them during the trial division of the b-smooth candidates.

Apart from the 2- (or even 3-) large primes variant and the small primes variant I would like to mention:

1. It should be SIQS
2. Knuth-Schroeppel multiplier
3. Block-Lancos or Block-Wiedemann for the linear algebra
4. You should have efficient implementations of Tonelli-Shanks, modular inverse and other basic algorithms
5. In SIQS, you need a good a-parameter (refering to Contini) generator, both for speed and stability to factor small N

Another point I found to improve performance at bit:
6. Use the polynomial Q(x) = (2ax+b)^2 - kN for kN == 1 (mod 8), Q(x) = (ax+b)^2 - kN for kN != 1 (mod 8)

Furthermore, in C it seems to be pretty good to use a segmented sieve, and a bucket sieve for large primes.
Using Java, I could not get any performance improvement from that, but maybe that was my failure.

Sieving with powers seems to be quite useless except for small N where it brings a small performance improvement.

[Ilya Gazman]

Those are excellent points! I also sow your Java implementation, it's about 15 times faster then what I got so far ;)

Here are a few other ideas:

1. Select the the sieving bound `m` to be the multiplication of the first primes in the prime base, then create a sieving array of that size. Now you only need to sieve on those first primes once and keep resetting the array to those values instead of 0. This optimization is more efficient for the QS but can work with multi polynomials as well. You just need to be clever in selecting the optimal m and the array size. You can get more choices by multiplying N with a small integer k
2. In both MPQS and SIQS there is a rounding error when selecting the `a` coefficient based on the `m` sieving size. To fix it, calculate the minimum and adjust the sieving starting position accordingly. So if we are sieving on a(ax^2+2b + c) then the sieve should start from (sqr(b^2-ac)-b)/a -m/2
3. For linear algebra, I made a new algorithm(new as far as I know) that is very fast for processing relations one by one. I run it simultaneously to sieving. It allows me to collect the minimalistic amount of relations before terminating. In practice, it reduces the required relations by 5-10 percent. Check my video about it: https://www.youtube.com/watch?v=KIZG...WIxuLgm7mYksfp