View Single Post
Old 2006-03-14, 10:25   #1
ThiloHarich's Avatar
Nov 2005

9910 Posts
Default Simple Idea for SIQS

I have a simple Idea, which is so simple that somebody else might have worked around with it:

Y^2 = X^2 – N -> Y^2 = X^2 - N mod p

I see two applications:

We consider the possible x mod p:

X_p = {x| y^2 = x^2 – N mod p, 0<=x<=p}

Then we know Y^2 = x^2 - N -> x mod p \in X_p.

But since |{y^2mod p|0<=y<p}| < (p+1)/2 it holds: |X_p| <= (p+1)/2 (if N mod p != 0 ). So we only have to consider half of the possible x. If we have a relation y^2 = x^2 – N we have a divisor x+y of N via fermats method.

Example N = 55 = 5*11, p = 3, N mod 3 = 2
Y^2 = {0,1} -> X_3 = {0,2}
We start with x = sqrt (N) = 6:
0 (6mod 3) is in X_3 and 6^2 – 55 is no square.
1 (7mod 3) is not in X_3 and so we switch to 8:
2 (8mod 3) is in X_3 and 8^2 – 55 = 3^2 So we found the divisor 8+3 = 11.

We can easily build X_p*q out of X_p and X_q. |X_p*q| <= (p+1)*(q+1)/4 if q and p were primes. So in every step we can sieve half of the numbers.

The problem is that the set for X is getting very huge. If we have a memory effective way to represent the set we might have a fast factoring algorithm. I thought of representing the set by BDD’s, but I have not much faith in this idea, and have not tried it.

Another idea (this is why I tried to implement the SIQS) is the following:

If we have a leading coefficient a = p_1 * p_2 * … * p_s (p_i of the factor base). Then we look for numbers a*d, which factor over the factor base. If we focus on d = y^2 mod p, we can again half the numbers we are searching for, for each p.

I think I made a mistake, because this simple idea will fasten the SIQS reasonable.

Last fiddled with by ThiloHarich on 2006-03-14 at 10:27
ThiloHarich is offline   Reply With Quote