Baby-step Giant-step (Discrete Logarithm Over Finite Fields Logarithm Calculations)
Jump to navigation
Jump to search
Time Complexity
$O({2}^{\sqrt{n}})$
Space Complexity
$O({2}^{\sqrt{n}})$ words
(Derived: Uses a hash table of this size)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1971