mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-03-14, 10:25   #1
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 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
Old 2006-03-14, 12:23   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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<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.
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-03-14, 12:33   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

244128 Posts
Default

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
xilman is online now   Reply With Quote
Old 2006-03-15, 08:09   #4
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2006-03-15, 11:48   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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.
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-03-16, 08:22   #6
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

9910 Posts
Default

I have already programmed a mpqs algorithm which runs half as fast as the Dario Alpern SIQS Applet.
Thank you for the constructive advice.
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Windows 10 in Ubuntu, good idea, bad idea, or...? jasong jasong 8 2017-04-07 00:23
A simple idea for factoring numbers ThiloHarich Factoring 15 2017-03-06 11:23
SIQS on GPU cgy606 Factoring 1 2016-10-21 13:37
SIQS problems henryzz Factoring 2 2013-08-26 23:02
SIQS Problem 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

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.