mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-08-20, 18:08   #1
Ilya Gazman
 
Feb 2016

3·5 Posts
w00t Quadratic Sieve optimizations

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.
Ilya Gazman is offline   Reply With Quote
Old 2020-08-20, 18:27   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·13·389 Posts
Default

Quote:
Originally Posted by Ilya Gazman View Post
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.
xilman is offline   Reply With Quote
Old 2020-08-22, 15:57   #3
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

41710 Posts
Default

Quote:
Originally Posted by Ilya Gazman View Post
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.
Till is offline   Reply With Quote
Old 2020-08-22, 17:14   #4
Ilya Gazman
 
Feb 2016

178 Posts
Default

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

Last fiddled with by Ilya Gazman on 2020-08-22 at 17:22
Ilya Gazman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Factoring in the Quadratic Sieve ThiloHarich Factoring 47 2007-01-08 14:12
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 10:06.

Thu Oct 22 10:06:58 UTC 2020 up 42 days, 7:17, 0 users, load averages: 1.43, 1.35, 1.39

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.