Revision as of 01:11, 27 June 2019 edit Daspeks (talk \| contribs) 55 edits →Complexity ← Previous edit		Revision as of 03:57, 16 August 2019 edit undo Daspeks (talk \| contribs) 55 edits →Groups of prime-power order Next edit →
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>]], far better than the [[Baby-step giant-step\|baby-step giant-step algorithm's]] [[Big O notation\|<math>O(\sqrt{p ^ {e/2})</math>]]. == The general algorithm ==

Pohlig–Hellman algorithm: Difference between revisions