View source for Pohlig-Hellman (Discrete Logarithm Over Finite Fields Logarithm Calculations)

== Time Complexity == 

$O({2}^{\sqrt{n}})$, only for primes; does much better for composites

== Space Complexity == 

$O({2}^{\sqrt{n}})$ (though only for primes) words

(A step in the algorithm involves using baby-steps giant-steps to compute discrete logs; the rest of the algorithm (including CRT and repeated powers) isn't as intensive)

== Description == 



== Approximate? == 

Exact

== Randomized? == 

No, deterministic

== Model of Computation == 

Word RAM

== Year == 

1978

== Reference == 

https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=2269283