Pohlig–Hellman algorithm: Difference between revisions

Revision as of 09:28, 20 May 2019

Revision as of 15:34, 22 May 2019

Line 18:

:## Set <math>x_{k+1}:=x_k+p^kd_k</math>.

:# Return <math>x_e</math>.

Assuming <math>e</math> is much smaller than <math>p</math>, the algorithm computes discrete logarithms in time complexity [[Big O notation|<math>O(e\sqrt p))</math>]], insteadfar ofbetter thethan trivialthe [[Baby-step giant-step|naby-step giant-step algorithm's]] [[Big O notation|<math>O(p ^ {e/2})</math>]].

== The general algorithm ==