multipolynomial quadratic sieve

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, where k = 1, 2, ... and ⌊x⌋ is the floor function. We are then looking for factors p such that n congruent r^2 (mod p), which means that only numbers with Legendre symbol (n/p) = 1 (less than N = π(d) for trial divisor d, where π(d) is the prime counting function) need be considered. The set of primes for which this is true is known as the factor base.

number field sieve | prime factorization algorithms | quadratic | smooth number