I'm not talking about the size of the factor base, but which primes are candidates (only half are). Isn't there some easy way to test a prime to see if it can be?
In the QS method of integer factoring, how does one know what number can be in the factor base?
0
$\begingroup$
number-theory
1 Answers
1
When using the quadratic sieve to factor $n$, the only primes you need in the factor base are the ones for which $n$ is a quadratic residue. Testing whether $n$ is a quadratic residue for a given prime modulus $p$ is easy (if $p$ is not too big) by using quadratic reciprocity and other properties of quadratic residues, which can be found in intro Number Theory texts.