Quadratic Sieve -- from Wolfram MathWorld

A sieving procedure that can be used in conjunction with Dixon's factorization method to factor large numbers n. Pick values of r given by r=|_sqrt(n)_|+k, (1) where k=1, 2, ... and |_x_| is the floor function. We are then looking for factors p such that n=r^2 (mod p), (2) which means that only numbers with Legendre symbol (n/p)=1 (less than N=pi(d) for trial divisor d, where pi(d) is the prime counting function) need be considered. The set of primes for which this is true is known...