First category integer factoring
Revision as of 11:56, 10 October 2022 by Admin (talk | contribs) (Created page with "== 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 == 1050px == St...")
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) | |
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |