mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2018-02-11, 17:47   #1
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default 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 Knuth-Schroeppel 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 5-10%.

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?
Till is offline   Reply With Quote
Old 2018-02-12, 01:25   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

25·109 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2018-02-12, 05:53   #3
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1A116 Posts
Default

Hi Jason,

Quote:
Originally Posted by jasonp View Post
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 understood. The factors of the a-parameter I have in PSIQS are somewhat middle-sized and I do not use them anymore for sieving. The case distinctions saved this way more than make up for their contribution, at least for large N.

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 a-parameter 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 b-parameter must be odd

We can still use Q2(x) if these conditions are not met, but then its "1-2 bit advantage" is gone.

My performance test result was that Q2(x) is indeed faster than Q(x) if and only if the Knuth-Schroeppel algorithm (following Pomerance "The Quadratic Sieve Factoring Algorithm") gives us some k with kN == 1 (mod 8). If the Knuth-Schroeppel 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).
Till is offline   Reply With Quote
Old 2018-02-12, 10:35   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

11×521 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
I assume sieving over the different B values is basically picking a different selection of the two roots for each of the different factors of A.
henryzz is offline   Reply With Quote
Old 2018-02-12, 16:28   #5
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3×139 Posts
Default

Quote:
Originally Posted by Till View Post
My performance test result was that Q2(x) is indeed faster than Q(x) if and only if the Knuth-Schroeppel algorithm (following Pomerance "The Quadratic Sieve Factoring Algorithm") gives us some k with kN == 1 (mod 8). If the Knuth-Schroeppel 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).
I did more tests and admit that it is just a statistical relation. Nevertheless I think it is quite strong. The corrected version reads:

On average, using Q2(x) is faster than Q(x) if the Knuth-Schroeppel algorithm (following Pomerance "The Quadratic Sieve Factoring Algorithm") gives us some k with kN == 1 (mod 8). If the Knuth-Schroeppel 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). )
Till is offline   Reply With Quote
Old 2018-02-12, 16:30   #6
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3×139 Posts
Thumbs up

Quote:
Originally Posted by henryzz View Post
I assume sieving over the different B values is basically picking a different selection of the two roots for each of the different factors of A.
Sounds like a very good question to me!
Till is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GCD of Polynomials over a finite field for NFS paul0 Programming 6 2015-01-16 15:12
SNFS polynomials. chris2be8 FactorDB 1 2012-03-10 16:49
orthogonal polynomials yemsy Aliquot Sequences 1 2011-02-17 10:25
SNFS polynomials for k*b^n+-1 mdettweiler Factoring 15 2010-01-14 21:13
Polynomials and Probability Orgasmic Troll Puzzles 4 2003-09-16 16:23

All times are UTC. The time now is 05:42.

Wed Oct 21 05:42:52 UTC 2020 up 41 days, 2:53, 0 users, load averages: 0.83, 1.25, 1.36

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.