Wheel factorization (First Category Integer Factoring Integer Factoring)
Jump to navigation
Jump to search
Time Complexity
$O({2}^{n/2})$
Space Complexity
$O(n)$ bits
(need to keep track of what number you're currently checking, along with o(n) bits for the wheel (assuming it's small))
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM?
Year
1940