mersenneforum.org Possible improvement of quadratic sieve
 Register FAQ Search Today's Posts Mark Forums Read

 2010-02-10, 22:56 #1 Random Poster     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?
2010-02-11, 11:32   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×5×373 Posts

Quote:
 Originally Posted by Random Poster 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.
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?
You are 25 years too late with your suggestion. Read my 1987 paper:

Math. Comp. 1987

2010-02-11, 23:06   #3
Random Poster

Dec 2008

179 Posts

Quote:
 Originally Posted by R.D. Silverman You are 25 years too late with your suggestion. Read my 1987 paper: The Multiple Polynomial Quadratic Sieve Math. Comp. 1987
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.

2010-02-12, 00:16   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

746010 Posts

Quote:
 Originally Posted by Random Poster 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.
clueless

 2010-02-12, 03:09 #5 jasonp Tribal Bullet     Oct 2004 5×709 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Ilya Gazman Factoring 3 2016-02-22 11:32 Sam Kennedy Factoring 20 2013-01-09 16:50 paul0 Factoring 3 2011-09-22 17:12 ThiloHarich Factoring 47 2007-01-08 14:12 ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 23:57.

Mon Jun 27 23:57:06 UTC 2022 up 74 days, 21:58, 1 user, load averages: 1.22, 1.14, 1.19