First category integer factoring
Jump to navigation
Jump to search
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
Error creating thumbnail: Unable to save thumbnail to destination
Step Chart
Error creating thumbnail: Unable to save thumbnail to destination
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) | |
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |