Uniqueness of the discrete logarithm below the order
ProvedECDLP.dlog_uniquecryptographygroup-theorynumber-theory
Let be an additive commutative group and an element of order . If are natural numbers with and and
then . In other words, the discrete logarithm in the cyclic subgroup is unique in the range ; applied to the challenge base point, this shows that the benchmark's secret with and is the unique such integer.
Formalization Note. The order is Mathlib's addOrderOf, and a • P is the additive-monoid scalar multiplication (-fold addition). The statement is for arbitrary additive commutative groups, so it is reusable beyond the challenge instance.
Preamble
import Mathlib
Formal statement
namespace ECDLP
theorem dlog_unique {G : Type*} [AddCommGroup G] {P : G} {n : ℕ}
(hP : addOrderOf P = n) {a b : ℕ} (ha : a < n) (hb : b < n)
(h : a • P = b • P) : a = b := by sorry
end ECDLPSource
Well-definedness of the discrete logarithm in a cyclic subgroup; implicit in the Epoch AI problem statement ('the integer x with 1 <= x < n such that Q = xP'), https://epoch.ai/frontiermath/open-problems/elliptic-curve-discrete-logarithm; standard treatment: Washington, Elliptic Curves: Number Theory and Cryptography, 2nd ed., Chapman & Hall/CRC 2008, Chapter 5.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.