mersenneforum.org Simple Idea for SIQS
 Register FAQ Search Today's Posts Mark Forums Read

 2006-03-14, 10:25 #1 ThiloHarich     Nov 2005 32×11 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
2006-03-14, 12:23   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by ThiloHarich 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.
What you have posted is

(1) Not useful for QS
(2) Not really applicable to QS. All you have done is rediscover difference
of squares with exclusion moduli.

2006-03-14, 12:33   #3
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

244128 Posts

Quote:
 Originally Posted by R.D. Silverman What you have posted is (1) Not useful for QS (2) Not really applicable to QS. All you have done is rediscover difference of squares with exclusion moduli.
I suspect that most everyone who starts thinking about factorization algorithms other than trial division rediscovers this algorithm relatively early on. I certainly did, back when I was aged 14 or so.

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

2006-03-15, 08:09   #4
ThiloHarich

Nov 2005

32×11 Posts

Quote:
 (1) Not useful for QS (2) Not really applicable to QS.
We have x - N = (ax + b)^2 - N = a *(ax^2 + 2bx + c) | b^2 - N = a*c
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.

2006-03-15, 11:48   #5
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by ThiloHarich We have x - N = (ax + b)^2 - N = a *(ax^2 + 2bx + c) | b^2 - N = a*c 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.
I already told you that the idea was not useful.
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.

 2006-03-16, 08:22 #6 ThiloHarich     Nov 2005 9910 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 8 2017-04-07 00:23 ThiloHarich Factoring 15 2017-03-06 11:23 cgy606 Factoring 1 2016-10-21 13:37 henryzz Factoring 2 2013-08-26 23:02 patrickkonsor Factoring 3 2008-10-20 12:03

All times are UTC. The time now is 09:50.

Fri Jan 22 09:50:08 UTC 2021 up 50 days, 6:01, 0 users, load averages: 2.31, 2.32, 2.41