mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Possible improvement of quadratic sieve (https://www.mersenneforum.org/showthread.php?t=13079)

Random Poster 2010-02-10 22:56

Possible improvement of quadratic sieve
 
As most readers probably know, the quadratic sieve factors a number n by finding values of x such that P(x) = x^2 - n is a product of small factors. This could be also done with multiples of n; more precisely, let m range from 1 to M and sieve for P(x) = x^2 - mn with x near sqrt(mn). Regardless of m, P(x) is congruent to x^2 modulo n, so the rest of the algorithm works as before. The advantages seem clear; first, we can get the same amount of relations with less sieving, and second, since the values of P(x) are on average smaller, we can use a smaller smoothness limit and so don't even need as many relations. The only problem I can see is that if there is p such that p^2 divides m and p divides x, then the relation from the pair (m, x) is essentially the same as from the pair (m/p^2, x/p) and should be avoided, but such x are easy to remove while sieving. (Note that if a prime p divides m only once, then it's quite fine for p to also divide x.) Any thoughts?

R.D. Silverman 2010-02-11 11:32

[QUOTE=Random Poster;205252]As most readers probably know, the quadratic sieve factors a number n by finding values of x such that P(x) = x^2 - n is a product of small factors.
[/QUOTE]

May I suggest that you read about the algorithm? Your description
described the algorithm as it was implemented in 1982 by J. Gervers.
It has not been implemented this way since 1984.

[QUOTE]
This could be also done with multiples of n; more precisely, let m range from 1 to M and sieve for P(x) = x^2 - mn with x near sqrt(mn). Any thoughts?[/QUOTE]

You are 25 years too late with your suggestion. Read my 1987 paper:

The Multiple Polynomial Quadratic Sieve
Math. Comp. 1987

Random Poster 2010-02-11 23:06

[quote=R.D. Silverman;205339]You are 25 years too late with your suggestion. Read my 1987 paper:

The Multiple Polynomial Quadratic Sieve
Math. Comp. 1987[/quote]
I thought MPQS uses P(x) = (Ax + B)^2 - n, which is very different from what I suggested. Although I don't see why even MPQS might not be improved by using multiples of n in its polynomials.

R.D. Silverman 2010-02-12 00:16

[QUOTE=Random Poster;205410]I thought MPQS uses P(x) = (Ax + B)^2 - n, which is very different from what I suggested. Although I don't see why even MPQS might not be improved by using multiples of n in its polynomials.[/QUOTE]

clueless

jasonp 2010-02-12 03:09

When you apply m > 1 you are factoring a larger number than the original, and the relation yield you get will drop very fast. MPQS doesn't have that problem, and you're not going to run out of (A,B) pairs, so there's no reason to compromise the relation yield by sieving more than one version of n simultaneously.


All times are UTC. The time now is 21:38.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.