Editing Quadratic residue (section)

===Integer factorization===

In § VI of the ''Disquisitiones Arithmeticae''<ref>Gauss, DA, arts 329&ndash;334</ref> Gauss discusses two factoring algorithms that use quadratic residues and the [[law of quadratic reciprocity]].

Several modern factorization algorithms (including [[Dixon's algorithm]], the [[continued fraction factorization|continued fraction method]], the [[quadratic sieve]], and the [[General number field sieve|number field sieve]]) generate small quadratic residues (modulo the number being factorized) in an attempt to find a [[congruence of squares]] which will yield a factorization. The number field sieve is the fastest general-purpose factorization algorithm known.