Simple Idea for SIQS

[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.

[R.D. Silverman]

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.

[xilman]

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

[ThiloHarich]

(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.

[R.D. Silverman]

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.

[ThiloHarich]

I have already programmed a mpqs algorithm which runs half as fast as the Dario Alpern SIQS Applet.
Thank you for the constructive advice.