View Single Post
Old 2010-02-10, 22:56   #1
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default 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?
Random Poster is offline   Reply With Quote