Baby-step giant-step: existence of a match below
ProvedECDLP.bsgscryptographygroup-theorynumber-theory
Let be an additive commutative group, of order , and with . Put . Then there exist natural numbers such that
This is the correctness core of Shanks's baby-step giant-step method: writing with , the baby step matches the giant step , so a collision search over two lists of length recovers . For the challenge instance , which is why the method is infeasible there.
Formalization Note. Nat.sqrt is the integer square root; the bound ensures , so the quotient and remainder of by are both .
Preamble
import Mathlib
Formal statement
namespace ECDLP
theorem bsgs {G : Type*} [AddCommGroup G] {P Q : G} {n x : ℕ} (hn : 0 < n)
(hP : addOrderOf P = n) (hx : x < n) (hQ : Q = x • P) :
let m := Nat.sqrt n + 1
∃ i j : ℕ, i < m ∧ j < m ∧ j • P = Q - i • (m • P) := by sorry
end ECDLPSource
Shanks, baby-step giant-step method (1971, unpublished); Washington, Elliptic Curves: Number Theory and Cryptography, 2nd ed., Chapman & Hall/CRC 2008, §5.2.1, https://doi.org/10.1201/9781420071474.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.