pohlig-hellman

Work in Progress

Concept

Pohlig-Hellman

Correctness claim (Pohlig—Hellman reconstruction). The residues uniquely recover .

  • layman explanation: prime-power logarithms are digits of one exponent and crt glues them together.

Proof. If and , put and . Then

because . Thus each size- logarithm supplies the next digit; induction gives each prime-power residue, and chinese remainder theorem combines them.
If , recover one base- digit at a time and combine the results with the chinese remainder theorem. The cost is governed by the largest prime factor, so cryptographic groups use a large prime-order subgroup.