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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.