Content deleted Content added
→Groups of prime-power order: added link |
Dscheinder (talk | contribs) |
||
Line 15:
:# For all <math>k\in\{0,\dots,e-1\}</math>, do:
:## Compute <math>h_k:=(g^{-x_k}h)^{p^{e-1-k}}</math>. By construction, the order of this element must divide <math>p</math>, hence <math>h_k\in\langle\gamma\rangle</math>.
:## Using the [[Baby-step giant-step|baby-step giant-step algorithm]], compute <math>d_k\in\{0,\dots,p-1\}</math> such that <math>\gamma^{d_k}=h_k</math>. It takes time [[Big O notation|<math>O(\sqrt p)</math>]].
:## 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>]] instead of the trivial [[Baby-step giant-step|naby-step giant-step algorithm's]] [[Big O notation|<math>O(p ^ {e/2})</math>]].
== The general algorithm ==
| |||