Pohlig–Hellman algorithm: Difference between revisions

Revision as of 04:21, 30 January 2018

Revision as of 04:22, 30 January 2018

Line 20:

== The general algorithm ==

In this section, we presentadddpresent the general case of the Pohlig-Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and the [[Chinese remainder theorem]] (to combine these to a logarithm in the full group).

(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.)