20081017, 02:41  #1 
Oct 2008
2×5 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; } } 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; } } 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]; } } } 
20081020, 02:19  #2 
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.

20081020, 11:53  #3  
Tribal Bullet
Oct 2004
DD7_{16} Posts 
Quote:
Sorry it took so long for you to figure out, but consider it the tuition for factoring school :) 

20081020, 12:03  #4 
Aug 2002
Buenos Aires, Argentina
2546_{8} 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SIQS on GPU  cgy606  Factoring  1  20161021 13:37 
SIQS  problem with solving linear algebra  Dome  Factoring  14  20150306 17:59 
SIQS problems  henryzz  Factoring  2  20130826 23:02 
SIQS implemantation... help needed :(  Hermes  Factoring  24  20090116 12:21 
partial relations in SIQS  ThiloHarich  Factoring  6  20071203 18:48 