20100210, 22:56  #1 
Dec 2008
179 Posts 
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?

20100211, 11:32  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
described the algorithm as it was implemented in 1982 by J. Gervers. It has not been implemented this way since 1984. Quote:
The Multiple Polynomial Quadratic Sieve Math. Comp. 1987 

20100211, 23:06  #3 
Dec 2008
179_{10} Posts 
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.

20100212, 00:16  #4 
Nov 2003
2^{2}×5×373 Posts 

20100212, 03:09  #5 
Tribal Bullet
Oct 2004
2·3·19·31 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Factoring in the Quadratic Sieve  ThiloHarich  Factoring  47  20070108 14:12 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 