 mersenneforum.org QS polynomials
 Register FAQ Search Today's Posts Mark Forums Read  2018-02-11, 17:47 #1 Till   "Tilman Neumann" Jan 2016 Germany 21516 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 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?   2018-02-12, 01:25 #2 jasonp Tribal Bullet   Oct 2004 32×5×79 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.   2018-02-12, 05:53   #3
Till

"Tilman Neumann"
Jan 2016
Germany

10258 Posts Hi Jason,

Quote:
 Originally Posted by jasonp 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).   2018-02-12, 10:35   #4
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

37×163 Posts Quote:
 Originally Posted by jasonp 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.   2018-02-12, 16:28   #5
Till

"Tilman Neumann"
Jan 2016
Germany

53310 Posts Quote:
 Originally Posted by Till 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). )   2018-02-12, 16:30   #6
Till

"Tilman Neumann"
Jan 2016
Germany

21516 Posts Quote:
 Originally Posted by henryzz 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!   2021-08-03, 21:21 #7 bsquared   "Ben" Feb 2007 E9416 Posts I finally got around to implementing Q2(x) polynomials and tuning the KS multiplier selection and I'm quite happy with the results. As one test case I generated 100 random rsa semiprimes. Of the 100, 85 used kN==1 mod 8 and were about 10% faster on average. Rarely (3 times out of 100) it seems to be a little overzealous trying to get kN == 1 mod 8 and will pick a slightly worse multiplier for 4-5% slowdown or so. But overall, quite an improvement in my view. Many thanks Till!   2021-08-04, 12:11 #8 ThiloHarich   Nov 2005 22×33 Posts When we only pick odd numbers on the left by taking q(x) = (2x+b)^2 - k*n We can expect a factor of 4 on the right i.e. q(x) = 0 mod 4, as long as k*n is odd. But kn = 1 mod 8 gives an extra factor 2 if b is odd (2x+b)^2 - k*n = (2x+b)^2 - 1 = 4x^2 + 4bx + b^2 - 1 = 4x^2 + 4bx (mod 8) Since b^2 = 1 mod 8 for odd b And such (2x+b)^2 - k*n = 4x^2 + 4bx = 4x (x + b) (mod 8) Since either x or x+b are even we know (2x+b)^2 - k*n = 0 mod 8 I remember that when playing with the QS in some cases of k and n q(x) has many 2 in its prime factors. There also was a kind of a structure in it, which works nicely with sieving. But for some n there is no k to get many 2's on the right side. I was not able to come up with some approach using this nice feature. Last fiddled with by ThiloHarich on 2021-08-04 at 12:42   2021-08-04, 13:57   #9
Till

"Tilman Neumann"
Jan 2016
Germany

13×41 Posts Quote:
 Originally Posted by bsquared I finally got around to implementing Q2(x) polynomials and tuning the KS multiplier selection and I'm quite happy with the results. As one test case I generated 100 random rsa semiprimes. Of the 100, 85 used kN==1 mod 8 and were about 10% faster on average. Rarely (3 times out of 100) it seems to be a little overzealous trying to get kN == 1 mod 8 and will pick a slightly worse multiplier for 4-5% slowdown or so. But overall, quite an improvement in my view. Many thanks Till!
Congrats!

Yes, it does not work on all numbers but on most of them. Your results look similar to mine. I estimated the "benalty" for kN == 1 (mod 8) from a scatter plot of f(k1)-f(k*) vs. runtime(k1)-runtime(k*), where k1 is the best k with kN == 1 (mod 8) and k* is the best k with kN == 3, 5, 7 (mod 8).

Do you still get convincing kN == 2 (mod 8) ? That looked like a 50-50 case to me, so I still do not consider them.

Last fiddled with by Till on 2021-08-04 at 13:58 Reason: parentheses   2021-08-04, 14:26   #10
bsquared

"Ben"
Feb 2007

22×3×311 Posts Quote:
 Originally Posted by Till Do you still get convincing kN == 2 (mod 8) ? That looked like a 50-50 case to me, so I still do not consider them.
I need more data on that, haven't re-evaluated with the new Q2 polys. I dug up two examples from recent log files:
1) a C60 where the k=2, kn==2 mod 8 case was 15% faster than kn==1 mod 8 (with k=1)
2) a C78 where the k=2, kn==6 mod 8 case was 5% slower than kn==1 mod 8 (with k=203)

In any case the k=2 multiplier is rarely used. Both of the above examples were the only ones out of 100 samples at those sizes.   2021-08-04, 15:17   #11
Till

"Tilman Neumann"
Jan 2016
Germany

10258 Posts Quote:
 Originally Posted by bsquared 2) a C78 where the k=2, kn==6 mod 8 case was 5% slower than kn==1 mod 8 (with k=203)
Monster k !     Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post paul0 Programming 6 2015-01-16 15:12 chris2be8 FactorDB 1 2012-03-10 16:49 yemsy Aliquot Sequences 1 2011-02-17 10:25 mdettweiler Factoring 15 2010-01-14 21:13 Orgasmic Troll Puzzles 4 2003-09-16 16:23

All times are UTC. The time now is 20:20.

Thu Feb 2 20:20:16 UTC 2023 up 168 days, 17:48, 1 user, load averages: 0.85, 1.18, 1.16 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔