Pohlig–Hellman algorithm: Difference between revisions

Revision as of 00:42, 5 April 2017

Revision as of 10:29, 24 April 2017

Line 24:

(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)

:'''Input.''' A cyclic group <math>G</math> of order <math>n</math> with generator <math>g</math>, an element <math>h\in G</math>, and a prime factorization <math display="inline">n=\sum_prod_{i=1}^rp_i^{e_i}</math>.

:'''Output.''' The unique integer <math>x\in\{0,\dots,n-1\}</math> such that <math>g^x=h</math>.

:# For each <math>i\in\{1,\dots,r\}</math>, do: