mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-02-10, 22:56   #1
Random Poster
 
Random Poster's Avatar
 
Dec 2008

24·11 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
Old 2010-02-11, 11:32   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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

The Multiple Polynomial Quadratic Sieve
Math. Comp. 1987
R.D. Silverman is offline   Reply With Quote
Old 2010-02-11, 23:06   #3
Random Poster
 
Random Poster's Avatar
 
Dec 2008

24×11 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-02-12, 00:16   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Random Poster View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2010-02-12, 03:09   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

25·109 Posts
Default

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.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Factoring in the Quadratic Sieve ThiloHarich Factoring 47 2007-01-08 14:12
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 07:22.

Wed Oct 21 07:22:10 UTC 2020 up 41 days, 4:33, 0 users, load averages: 1.66, 1.43, 1.36

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.