mersenneforum.org SIQS Problem
 Register FAQ Search Today's Posts Mark Forums Read

 2008-10-17, 02:41 #1 patrickkonsor   Oct 2008 128 Posts SIQS Problem Hello all, I'm working on a SIQS implementation in Java. While very rough, it works with one exception; I was wondering if anyone could offer me some advice to resolve my issue. The polynomials are of the form g(x) = (ax + b)^2 - n When I produce a totally new polynomial (that is, a new a and b), my calculated solutions work fine. However, when I generate the subsequent 2^(s - 1) - 1 polynomials (which have the same a and a new b), the calculated solutions are not correct (they don't produce many, if any, smooth relations). I've presented the relevant pseudo code below (don't mind the fact that it's inefficient). Hopefully someone will notice the issue. Alternatively, I could solve the issue myself if someone could provide me some sample debugging output from a working implementation. Thank you very much for your time and thought! Patrick Konsor Here is some pseudo code I'm using to generate a totally new polynomial.. Code: Let n be the number to be factored Let factorBase be an array of factors Let M be the sieving interval Let t[i] be the solution to t[i]^2 = n mod factorBase[i] int s = 0; int a = 1; int m = 1; int[] q = new int[totalPrimes]; int limit = sqrt(2 * n) / M; while (a < limit) { if (random() * 10 < 5) { a = a * factorBase[m]; q[s] = m; s++; } m++; } // Compute b int b = 0; int[] B = new int[s]; for (int i = 0; i < s; i++) { int p = factorBase[q[i]]; int g = t[q[i]] * modInverse(a / p, p); if (g > p / 2) { g = p - g; } B[i] = (a / p) * g; b += B[i]; } // Compute Solutions pSol1 = new int[totalPrimes]; pSol2 = new int[totalPrimes]; aInv = new int[totalPrimes]; BaInv2 = new int[totalPrimes][s]; for (int i = 0; i < totalPrimes; i++) { int p = factorBase[i]; if (!(a % p == 0)) { aInv[i] = modInverse(a, p); for (int j = 0; j < s; j++) { BaInv2[i][j] = 2 * B[j] * aInv[i] % p; } pSol1[i] = aInv[i] * (t[i] - b) % p; pSol2[i] = aInv[i] * (-1 * t[i] - b) % p; } } Here is the pseudo code for computing a new curve with the same a Code: // Compute v int v = 1; int iTmp = i; while ((iTmp & 0x00000001) == 0) { iTmp >>= 1; v++; } int e = (l >> v) & 0x00000001; if (e == 0) e = -1; b += 2 * e * B[v - 1] // Compute Solutions for (int i = 0; i < totalPrimes; i++) { int p = factorBase[i]; if (!(a % p == 0)) { pSol1[i] += e * BaInv2[i][v - 1] % p pSol2[i] += e * BaInv2[i][v - 1] % p } else { pSol1[i] = 0; pSol2[i] = 0; } } Finally, here is the pseudo code that distributes the approximate prime factorizations.. Code: byte[] sieveArray = new byte[2 * M + 1]; for (int i = 0; i < totalPrimes; i++) { int p = factorBase[i]; int sol1 = pSol1[i]; int sol2 = pSol2[i]; int x; for (int k = ceil((-1 * M - sol1) / p); (x = k * p + sol1 + M) < sieveArray.length; k++) { sieveArray[x] += pLog[i]; } if (p > 2) { for (int k = ceil((-1 * M - sol2) / p); (x = k * p + sol2 + M) < sieveArray.length; k++) { sieveArray[x] += pLog[i]; } } }
 2008-10-20, 02:19 #2 patrickkonsor   Oct 2008 2×5 Posts Well, to my eternal shame I've spent several days debugging to discover that the problem was simply that I added the BaInv's when I should've subtracted (and vice versa); however, this doesn't make much sense as I always did correctly calculate the new b value using the same +/-1 coefficient.
2008-10-20, 11:53   #3
jasonp
Tribal Bullet

Oct 2004

33·131 Posts

Quote:
 Originally Posted by patrickkonsor Well, to my eternal shame I've spent several days debugging to discover that the problem was simply that I added the BaInv's when I should've subtracted (and vice versa); however, this doesn't make much sense as I always did correctly calculate the new b value using the same +/-1 coefficient.
When first implementing SIQS I also realized that the signs of the mod-B coefficients had to be flipped compared to what was in Contini's thesis. I wonder if it was a typo there but I know that doing the opposite is required.

Sorry it took so long for you to figure out, but consider it the tuition for factoring school :)

 2008-10-20, 12:03 #4 alpertron     Aug 2002 Buenos Aires, Argentina 22·337 Posts I had the same problem when implementing the code for my factorization applet, because I used the same source (Contini's thesis) but I was able to fix it quickly by running it step by step in the debugger.

 Similar Threads Thread Thread Starter Forum Replies Last Post cgy606 Factoring 1 2016-10-21 13:37 Dome Factoring 14 2015-03-06 17:59 henryzz Factoring 2 2013-08-26 23:02 Hermes Factoring 24 2009-01-16 12:21 ThiloHarich Factoring 6 2007-12-03 18:48

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

Fri Apr 23 07:20:24 UTC 2021 up 15 days, 2:01, 0 users, load averages: 2.49, 2.33, 1.99

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.