Pohlig–Hellman algorithm: Difference between revisions

Revision as of 00:34, 3 April 2017

Revision as of 00:42, 5 April 2017

Line 29:

:## Compute <math>g_i:=g^{n/p_i^{e_i}}</math>. By [[Lagrange's theorem (group theory)|Lagrange's theorem]], this element has order <math>p_i^{e_i}</math>.

:## Compute <math>h_i:=h^{n/p_i^{e_i}}</math>. By construction, <math>h_i\in\langle g_i\rangle</math>.

:## Using the algorithm above in the group <math>\langle g_i\rangle</math>, compute <math>x_i\in\{0,\dots,p_i^{e_i}-1\}</math> such that <math>g_i^{x_i}=h_i</math>.

:# Solve the simultaneous congruence <math display="block">x\equiv x_i\pmod{p_i^{e_i}}

\quad\forall i\in\{1,\dots,r\}

\text{.}</math>The Chinese remainder theorem guarantees there exists a unique solution <math>x\in\{0,\dots,n-1\}</math>.

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

The correctness of this algorithm can be verified via the [[Abelian group#Classification|classification of finite abelian groups]]: Raising <math>g</math> and <math>h</math> to the power of <math>n/p_i^{e_i}</math> can be understood as the projection intoto the factor group of order <math>p_i^{e_i}</math>.

==Complexity==