Pohlig–Hellman reduction to prime-power-order subgroups
ProvedECDLP.pohlig_hellmanLet be an additive commutative group, an element of finite order , and for some natural number . Let be a positive divisor of . Then the Pohlig–Hellman projection satisfies:
- the point has order exactly ;
- the projected target satisfies .
Thus the discrete logarithm of to the base , reduced modulo , is the discrete logarithm of to the base in the subgroup of order . Taking to run over the prime-power factors of and recombining by the Chinese remainder theorem is the Pohlig–Hellman algorithm (1978); when is prime, as in the challenge instance, the reduction is trivial.
Formalization Note. n / m and x % m are natural-number division and remainder; • is additive scalar multiplication. The hypothesis 0 < n excludes the infinite-order case, where the statement would be false.
import Mathlib
namespace ECDLP
theorem pohlig_hellman {G : Type*} [AddCommGroup G] {P Q : G} {n : ℕ} (hn : 0 < n)
(hP : addOrderOf P = n) {x : ℕ} (hQ : Q = x • P) {m : ℕ} (hm : m ∣ n) :
addOrderOf ((n / m) • P) = m ∧ (n / m) • Q = (x % m) • ((n / m) • P) := by sorry
end ECDLPConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.