Dixon's algorithm (Second Category Integer Factoring Integer Factoring)
Revision as of 11:38, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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, deter...")
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