Card words
ProvedCryptography.BerggrenModular.card_wordsaether-catalogcryptography
Formal statement of Cryptography.BerggrenModular.card_words from the Aether Catalog (Cryptography). The mathematical content is given by the Lean statement below; a human-readable write-up is pending.
theorem Cryptography.BerggrenModular.card_words(k : ℕ) : Fintype.card (Fin k → Move) = 3 ^ k := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Cryptography/BerggrenModular/Hardness.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/Hardness.lean
import Mathlib
import Definitions.Def_Cryptography_BerggrenModular_Core
import Definitions.Def_Cryptography_BerggrenModular_Hardness
import Definitions.Def_Cryptography_BerggrenModular_Modular
/-!
# Seed recovery: easy over `ℤ`, information-theoretically hard over `ℤ/m`
Fix the Berggren root `(3,4,5)` and a *control word* `u ∈ {B₁,B₂,B₃}^k`. The
*seed-recovery problem* asks: from the single observed state `applyWord u root`,
reconstruct `u`.
* Over `ℤ` this is **easy**: `recoverFrom` solves it with `k` comparisons and `k`
linear maps (`intSeedRecoverable`). This is a corollary of the exactness of the
classifier `whichMove` together with the freeness of the Berggren monoid.
* Over `ℤ/m` the same problem becomes **impossible** once `k` is large compared to
the modulus, and quantitatively ambiguous long before that:
- `mod_ambiguity_lower_bound` : for every `n` with `m³·n < 3^k` there is an
observed modular state with more than `n` consistent control words. Taking
`n = ⌈3^k/m³⌉ − 1` this is the promised `Ω(3^k / poly(m))` bound: the
modulus is polynomial-size, the ambiguity is exponential.
- `not_modSeedRecoverable_of_card` : if `m³ < 3^k` no recovery function exists.
- `not_modSeedRecoverable_of_dl` : recovery for *all* words of length `≤ k`
would in particular solve the discrete-logarithm problem for the matrix `B₂`
modulo `m`; and that problem is already unsolvable for `k ≥ m³` because the
`B₂`-orbit has collided by then. This is the precise sense of
"hard unless the `B₂` discrete logarithm mod `m` is easy".
## Main results
* `intSeedRecoverable`
* `mod_ambiguity_lower_bound`
* `not_modSeedRecoverable_of_card`
* `dlEasy_of_modSeedRecoverable`
* `not_dlEasy_of_large`
* `berggren_modulus_separation` — the combined statement.
-/
open Cryptography
open BerggrenModular
/-! ## Integer seed recovery is easy -/
/-! ## The modular observation -/
/-! ## Counting: `3^k` control words versus `m³` states -/Formal statement
theorem Cryptography.BerggrenModular.card_words(k : ℕ) : Fintype.card (Fin k → Move) = 3 ^ k := by sorry
Source