Modular seed recovery is correct below the modulus.
ProvedCryptography.BerggrenModular.recoverMod_applyWordMaether-catalogcryptography
Modular seed recovery is correct below the modulus. If every intermediate
state along the word stays below m, the modular observer recovers the control
word exactly.
theorem Cryptography.BerggrenModular.recoverMod_applyWordM{m : ℕ} [NeZero m] (u : List Move) {v : Tri} (hv : Valid v)
(hb : ∀ s : List Move, s <:+ u → (applyWord s v).2.2 < m) :
recoverMod m u.length (redTri m (applyWord u v)) = u := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Cryptography/BerggrenModular/Modular.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Cryptography/BerggrenModular/Modular.lean import Mathlib import Definitions.Def_Cryptography_BerggrenModular_Core import Definitions.Def_Cryptography_BerggrenModular_Modular /-! # Berggren moves on `(ℤ/m)³` We push the Berggren moves through the reduction map `ℤ³ → (ℤ/m)³` and study what survives. ## Main results * `redTri_applyMove`, `redTri_applyWord` — reduction is equivariant: the modular dynamics is a genuine quotient of the integer dynamics. * `applyMoveM_bijective` — every modular move is a bijection of `(ℤ/m)³` (the state map itself loses nothing; all loss comes from wrap-around). * `lorentzM_applyMoveM` — the Lorentz form `a²+b²−c²` is still invariant mod `m`. * `whichMoveMod_redTri` — **the classifier remains sound modulo `m`**: as long as the observed state has not wrapped around (`hypotenuse < m`), the canonical lift of the residue is the true state and `whichMove` returns the true last move. * `whichMoveMod_not_sound_mod_seven` — and this hypothesis is sharp: an explicit failure at `m = 7`. * `vecOfM_iterate_applyMoveM` — iterating the move `B₂` mod `m` is exactly multiplication by the matrix power `B₂^t` over `ℤ/m`, which is what makes the seed-recovery problem for `B₂`-only words a discrete-logarithm problem. -/ open Cryptography open BerggrenModular /-! ## Reduction is equivariant -/ /-! ## The classifier modulo `m` -/
Formal statement
theorem Cryptography.BerggrenModular.recoverMod_applyWordM{m : ℕ} [NeZero m] (u : List Move) {v : Tri} (hv : Valid v)
(hb : ∀ s : List Move, s <:+ u → (applyWord s v).2.2 < m) :
recoverMod m u.length (redTri m (applyWord u v)) = u := by sorrySource