20200820, 18:08  #1 
Feb 2016
3·5 Posts 
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 bsmooth 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 bsmooth candidates. 
20200820, 18:27  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·13·389 Posts 
Quote:
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 breakeven point was at roughly 100 digits. 

20200822, 15:57  #3  
"Tilman Neumann"
Jan 2016
Germany
417_{10} Posts 
Quote:
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. KnuthSchroeppel multiplier 3. BlockLancos or BlockWiedemann for the linear algebra 4. You should have efficient implementations of TonelliShanks, modular inverse and other basic algorithms 5. In SIQS, you need a good aparameter (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. 

20200822, 17:14  #4 
Feb 2016
17_{8} Posts 
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^2ac)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 510 percent. Check my video about it: https://www.youtube.com/watch?v=KIZG...WIxuLgm7mYksfp Last fiddled with by Ilya Gazman on 20200822 at 17:22 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Factoring in the Quadratic Sieve  ThiloHarich  Factoring  47  20070108 14:12 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 