Quadratic Sieve Factorization Method
A procedure used in conjunction with Dixon's Factorization Method to factor large numbers. The 
s are chosen as
 | (1) |
, 2, ... and 
is the Floor Function. We are then looking for factors 
such that | (2) |
(less than 
for trial divisor 
) need beconsidered. The set of Primes for which this is true is known as the Factor Base. Next, theCongruences | (3) |
in the Factor Base. Finally, a sieve is applied to find values of 
whichcan be factored completely using only the Factor Base. Gaussian Elimination is then used as in Dixon's Factorization Method in order to find a product of the 
s, yielding a Perfect Square.The method requires about 
steps, improving on the Continued Fraction FactorizationAlgorithm by removing the 2 under the Square Root (Pomerance 1996). The use of multiplePolynomials gives a better chance of factorization, requires a shorter sieve interval, and iswell-suited to parallel processing.
References
Alford, W. R. and Pomerance, C. ``Implementing the Self Initializing Quadratic Sieve on a Distributed Network.'' In Number Theoretic and Algebraic Methods in Computer Science, Proc. Internat. Moscow Conf., June-July 1993 (Ed. A. J. van der Poorten, I. Shparlinksi, and H. G. Zimer). World Scientific, pp. 163-174, 1995.
Brent, R. P. ``Parallel Algorithms for Integer Factorisation.'' In Number Theory and Cryptography (Ed. J. H. Loxton). New York: Cambridge University Press, 26-37, 1990. ftp://nimbus.anu.edu.au/pub/Brent/rpb115.dvi.Z.
Bressoud, D. M. Ch. 8 in Factorization and Prime Testing. New York: Springer-Verlag, 1989.
Gerver, J. ``Factoring Large Numbers with a Quadratic Sieve.'' Math. Comput. 41, 287-294, 1983.
Lenstra, A. K. and Manasse, M. S. ``Factoring by Electronic Mail.'' In Advances in Cryptology--Eurocrypt '89 (Ed. J.-J. Quisquarter and J. Vandewalle). Berlin: Springer-Verlag, pp. 355-371, 1990.
Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.
Pomerance, C.; Smith, J. W.; and Tuler, R. ``A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Method.'' SIAM J. Comput. 17, 387-403, 1988.
- Line of Curvature
- Line Segment
- Line Space
- L(infinity)-Norm
- Link
- Linkage
- Link Diagram
- Linking Number
- Links Curve
- Linnik's Constant
- Linnik's Theorem
- Lin's Method
- Liouville Function
- Liouville Measure
- Liouville Number
- Liouville Polynomial Identity
- Liouville-Roth Constant
- Liouville's Boundedness Theorem
- Liouville's Conformality Theorem
- Liouville's Conic Theorem
- Liouville's Constant
- Liouville's Elliptic Function Theorem
- Liouville Space
- Liouville's Phase Space Theorem
- Liouville's Rational Approximation Theorem