Second category integer factoring
Jump to navigation
Jump to search
Problem Description
A general-purpose factoring algorithm, also known as a Category 2, Second Category, or Kraitchik family algorithm,[9] 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 numbers. Most general-purpose factoring algorithms are based on the congruence of squares method.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | Dixon's algorithm (1981) | |
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Rational sieve (1993) | |
| nlogn | General number field sieve (1996) | |
| Linear | ||
| logn | Shor's algorithm Quantum Implementation (1994) |