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?

[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 
[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. 
[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 
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 11:32. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.