Editing Integer factorization (section)

== Factoring algorithms <!-- This section is linked from [[Factorization]] --> ==

=== Special-purpose ===
A special-purpose factoring algorithm's running time depends on the properties of the number to be factored or on one of its unknown factors: size, special form, etc. The parameters which determine the running time vary among algorithms.

An important subclass of special-purpose factoring algorithms is the ''Category 1'' or ''First Category'' algorithms, whose running time depends on the size of smallest prime factor. Given an integer of unknown form, these methods are usually applied before general-purpose methods to remove small factors.<ref name="Bressoud and Wagon">
{{cite book
 | author = [[David Bressoud]] and [[Stan Wagon]]
 | year = 2000
 | title = A Course in Computational Number Theory
 | publisher = Key College Publishing/Springer
 | isbn = 978-1-930190-10-8
 | pages = [https://archive.org/details/courseincomputat0000bres/page/168 168–69]
 | url-access = registration
 | url = https://archive.org/details/courseincomputat0000bres/page/168
}}</ref> For example, naive [[trial division]] is a Category 1 algorithm.

* [[Trial division]]
* [[Wheel factorization]]
* [[Pollard's rho algorithm]], which has two common flavors to [[Cycle detection|identify group cycles]]: one by Floyd and one by Brent.
* [[Algebraic-group factorisation algorithms|Algebraic-group factorization algorithms]], among which are [[Pollard's p − 1 algorithm|Pollard's {{math|''p'' − 1}} algorithm]], [[Williams' p + 1 algorithm|Williams' {{math|''p'' + 1}} algorithm]], and [[Lenstra elliptic curve factorization]]
* [[Fermat's factorization method]]
* [[Euler's factorization method]]
* [[Special number field sieve]]
* [[Difference of two squares]]

=== General-purpose ===
A general-purpose factoring algorithm, also known as a ''Category 2'', ''Second Category'', or [[Maurice Kraitchik|''Kraitchik'']] ''family'' algorithm,<ref name="Bressoud and Wagon"/> has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor [[RSA number]]s. Most general-purpose factoring algorithms are based on the [[congruence of squares]] method.

* [[Dixon's factorization method]]
* [[Continued fraction factorization]] (CFRAC)
* [[Quadratic sieve]]
* [[Rational sieve]]
* [[General number field sieve]]
* [[Shanks's square forms factorization]] (SQUFOF)

=== Other notable algorithms ===
* [[Shor's algorithm]], for quantum computers