Trial Multiplication (Discrete Logarithm Over Finite Fields Logarithm Calculations)

Time Complexity

$O({2}^n)$

Space Complexity

$O({1})$ words

(Derived: Each power $k$ that you try in the brute force search is size $O(\log n)$, which is $O(1)$ when considering $O(\log n)$ size words. Only need to keep track of one at a time.)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1940

Reference

NA