20180211, 17:47  #1 
"Tilman Neumann"
Jan 2016
Germany
3·139 Posts 
QS polynomials
Hi,
reading http://www.karlin.mff.cuni.cz/~krypt.../main_file.pdf let me investigate using the polynomial Q2(x) = (2ax + b)^2  kN instead of the usual Q(x) = (ax + b)^2  kN for SIQS. Regarding performance, I found that the output of the KnuthSchroeppel algorithm is decisive: If it finds some k with kN == 1 (mod 8) then Q2(x) is faster; otherwise Q(x) is the better choice. The difference in each case may be about 510%. Are there more papers looking at Q2(x)? Is or was anybody else using case distinctions on kN (mod 8) that improve SIQS (or maybe MPQS) performance? 
20180212, 01:25  #2 
Tribal Bullet
Oct 2004
2^{5}·109 Posts 
Every prime factor that is in the A value of a chosen QA polynomial yields one sieving root, whereas primes in the factor base always have two sieving roots. So sieving will be faster if the factors of A are not very small.
That's separate from the choice of multiplier k. Some implementations force kN==1 mod 8 but ultimately the factor base will have many primes, and luck of the draw could point to a different as better. My small SIQS code here sorts the choice of multipliers by the value of kN mod {8,3,5} to reduce the number of multipliers to try while still maximizing the chance of picking an optimal one. 
20180212, 05:53  #3  
"Tilman Neumann"
Jan 2016
Germany
1A1_{16} Posts 
Hi Jason,
Quote:
Maybe you didn't spot the little subtlety with the 2 in Q2(x) = (2ax+b)^2  kN ? The point here is that under certain conditions, Q2(x) is divisible by 4a "by design", while Q(x) = (ax+b)^2  kN is only divisible by a. Although the aparameter of Q2(x) must be chosen 1 bit smaller than in Q(x) to get polynomial values in the same bounds, the part of polynomial values that must be checked for smoothness, Q2(x)/(4a) vs. Q(x)/a, is one bit smaller in Q2(x). Furthermore Q2 has 2 bit more that can be removed very fast in trial division / resieving. The conditions that guarantee that Q2(x) is divisible by 4a are: * we need k with kN == 1 (mod 8) * the bparameter must be odd We can still use Q2(x) if these conditions are not met, but then its "12 bit advantage" is gone. My performance test result was that Q2(x) is indeed faster than Q(x) if and only if the KnuthSchroeppel algorithm (following Pomerance "The Quadratic Sieve Factoring Algorithm") gives us some k with kN == 1 (mod 8). If the KnuthSchroeppel algorithm gives us some k with kN == 3, 5, 7 (mod 8), then using Q2(x) will be slower, no matter if we use that k or the "best" k with kN == 1 (mod 8). 

20180212, 10:35  #4  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
11×521 Posts 
Quote:


20180212, 16:28  #5  
"Tilman Neumann"
Jan 2016
Germany
3×139 Posts 
Quote:
On average, using Q2(x) is faster than Q(x) if the KnuthSchroeppel algorithm (following Pomerance "The Quadratic Sieve Factoring Algorithm") gives us some k with kN == 1 (mod 8). If the KnuthSchroeppel algorithm gives us some k with kN == 3, 5, 7 (mod 8), then using Q2(x) will usually be slower, (no matter if we use that k or the "best" k with kN == 1 (mod 8). ) 

20180212, 16:30  #6 
"Tilman Neumann"
Jan 2016
Germany
3×139 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GCD of Polynomials over a finite field for NFS  paul0  Programming  6  20150116 15:12 
SNFS polynomials.  chris2be8  FactorDB  1  20120310 16:49 
orthogonal polynomials  yemsy  Aliquot Sequences  1  20110217 10:25 
SNFS polynomials for k*b^n+1  mdettweiler  Factoring  15  20100114 21:13 
Polynomials and Probability  Orgasmic Troll  Puzzles  4  20030916 16:23 