Thread: SIQS Problem
View Single Post
Old 2008-10-17, 02:41   #1
patrickkonsor
 
Oct 2008

2×5 Posts
Default 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];
        }
    }
}
patrickkonsor is offline   Reply With Quote