AFTD Auto-Formalizing Theoretical Domains

schnorr_mem_zpowers_iff_exists_zmod

theoremverified

Let G be a commutative group, q a prime, and g in G an element of order q. Any element x in the cyclic subgroup generated by g is of the form g^(k.val) for some scalar k in ZMod q.

Statement

theorem schnorr_mem_zpowers_iff_exists_zmod {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)
    (hg : orderOf g = q) (x : G) (hx : x ∈ Subgroup.zpowers g) :
    ∃ k : ZMod q, x = g ^ k.val
Source
folklore
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • schnorr_zpow_eq_pow_zmod_valLet G be a commutative group, q a prime, and g in G an element of order q. For any integer z, the integer power g^z equals g^(z.val) where…
Used by 1
  • schnorr_linear_batch_soundness_boundLet G be a commutative group, q a prime, and g in G an element of order q. Let pk, a₁, a₂ in Subgroup.zpowers g. For any challenges c₁, c₂…

Read back from the Lean

Let $G$ be a commutative group, and let $q$ be a prime natural number. Let $g \in G$ be an element whose group order is $q$. If $x \in G$ belongs to the subgroup of integer powers of $g$ ($x \in \operatorname{zpowers} g$), then there exists an element $k \in \mathbb{Z}/q\mathbb{Z}$ such that $x = g^{k.\mathrm{val}}$ (where $k.\mathrm{val} \in \mathbb{N}$ is the canonical representative of $k$ in $\{0, \dots, q-1\}$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, any element x in the cyclic subgroup generated by g is an integer power g^z for some integer z. Since g has order q, its powers depend only on the exponent modulo q; thus choosing k to be z regarded as an element of ZMod q yields x = g^(k.val).

  1. There exists an integer z such that x = g^z.

    By definition of the cyclic subgroup generated by g, any element x ∈ Subgroup.zpowers g is an integer power of g. Applying Subgroup.mem_zpowers_iff.mp unpacks this to an integer z such that x = g^z, substituting g^z for x.

    line 5

    uses Subgroup.mem_zpowers_iff.mp

      obtain ⟨z, rfl⟩ := Subgroup.mem_zpowers_iff.mp hx
  2. The element x can be expressed as g^(k.val) for k = (z : ZMod q).

    We supply k = (z : ZMod q) as the witness. By schnorr_zpow_eq_pow_zmod_val, since g has order q, the integer power g^z is equal to g^(k.val), where k is the canonical reduction of z modulo q.

    line 6

    uses schnorr_zpow_eq_pow_zmod_val

      exact ⟨(z : ZMod q), schnorr_zpow_eq_pow_zmod_val g hg z⟩
Subgroup.mem_zpowers_iff.mp
An element belongs to the cyclic subgroup generated by g if and only if it is an integer power g^z for some integer z.
schnorr_zpow_eq_pow_zmod_val
For an element g of order q and any integer z, the power g^z equals g^(k.val), where k is the image of z in ZMod q.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Every element in the cyclic subgroup generated by g is of the form g^(k.val) for some scalar k in ZMod q. -/theorem schnorr_mem_zpowers_iff_exists_zmod {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G)    (hg : orderOf g = q) (x : G) (hx : x ∈ Subgroup.zpowers g) :    ∃ k : ZMod q, x = g ^ k.val := by  obtain ⟨z, rfl⟩ := Subgroup.mem_zpowers_iff.mp hx  exact ⟨(z : ZMod q), schnorr_zpow_eq_pow_zmod_val g hg z⟩
See it in the graphDiscuss this resultChallenge it