0
$\begingroup$

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?

1 Answers 1

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.