schnorr_mem_zpowers_iff_exists_zmod
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).
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.
uses
Subgroup.mem_zpowers_iff.mpobtain ⟨z, rfl⟩ := Subgroup.mem_zpowers_iff.mp hx
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.
uses
schnorr_zpow_eq_pow_zmod_valexact ⟨(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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩