20060314, 10:25  #1 
Nov 2005
101 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 p0<=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 20060314 at 10:27 
20060314, 12:23  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
(1) Not useful for QS (2) Not really applicable to QS. All you have done is rediscover difference of squares with exclusion moduli. 

20060314, 12:33  #3  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
3·3,557 Posts 
Quote:
I believe Fermat was the first person to systematize the idea and to use it to speed up his eponymous factoring algorithm. So the idea has been examined for at least 350 years. Paul 

20060315, 08:09  #4  
Nov 2005
101 Posts 
Quote:
and we will look for smooth a * (ax^2 + 2bx + c) . If p is a prime not in the factor base (and n has a quadratic residue mod p) and ax^2 + 2bx + c != y^2 mod p, then a (ax^2 + 2bx + c) can not be smooth. So the idea can be used for reducing the possible x in the QS. 

20060315, 11:48  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:
But you had to argue. Why? What compels you? Especially since it is clear that you do not understand the algorithm. Explain *in detail* how the idea reduces the amount of sieving. Or (equivalently) reduces the number of candidate relations. The polynomials in QS are *already* constructed in such a way that EVERY value is a square. I think you fail to understand how QS works. Go study it. Then maybe you might have something intelligent to say about it. 

20060316, 08:22  #6 
Nov 2005
101 Posts 
I have already programmed a mpqs algorithm which runs half as fast as the Dario Alpern SIQS Applet.
Thank you for the constructive advice. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Windows 10 in Ubuntu, good idea, bad idea, or...?  jasong  jasong  8  20170407 00:23 
A simple idea for factoring numbers  ThiloHarich  Factoring  15  20170306 11:23 
SIQS on GPU  cgy606  Factoring  1  20161021 13:37 
SIQS problems  henryzz  Factoring  2  20130826 23:02 
SIQS Problem  patrickkonsor  Factoring  3  20081020 12:03 