mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-10-17, 02:41   #1
patrickkonsor
 
Oct 2008

128 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
Old 2008-10-20, 02:19   #2
patrickkonsor
 
Oct 2008

2×5 Posts
Default

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.
patrickkonsor is offline   Reply With Quote
Old 2008-10-20, 11:53   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

Quote:
Originally Posted by patrickkonsor View Post
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 :)
jasonp is offline   Reply With Quote
Old 2008-10-20, 12:03   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·337 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIQS on GPU cgy606 Factoring 1 2016-10-21 13:37
SIQS - problem with solving linear algebra Dome Factoring 14 2015-03-06 17:59
SIQS problems henryzz Factoring 2 2013-08-26 23:02
SIQS implemantation... help needed :( Hermes Factoring 24 2009-01-16 12:21
partial relations in SIQS 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.