SIQS Problem

[patrickkonsor]

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..

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

// 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..

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]

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.

[jasonp]

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 :)

[alpertron]

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.