Thread: Simple Idea for SIQS View Single Post
 2006-03-14, 10:25 #1 ThiloHarich     Nov 2005 9910 Posts 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 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