First category integer factoring

Problem Description

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. For example, naive trial division is a Category 1 algorithm.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial	[- Trial division (1202)] [ Wheel factorization (1940)] Williams' p + 1 algorithm (1982) [ Special number field sieve (1940)]
Polynomial > 3	Lenstra elliptic curve factorization (1987) Fermat's factorization method (1894)
Cubic
Quadratic
nlogn
Linear
logn