Dixon's algorithm (Second Category Integer Factoring Integer Factoring)
Jump to navigation
Jump to search
Time Complexity
$O(e^{({2} \sqrt({2}) \sqrt(n*logn))}){4}
Space Complexity
$O(n+(B/logB)$^{2})? bits
(There are pi(B) = O(B/log B) primes in the factor base; need pi(B)+1=O(B/log B) relations involving an integer (which doesn't need to be kept track of) and a pi(B)-bit string of exponents. Also need O(n) bits to perform other computations. Rest is irrelevant asymptotically)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM?
Year
1981
Reference
https://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981-0595059-1/home.html