Editing Integer factorization (section)

=== 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]]