schnorr_zpow_eq_pow_zmod_val
Let 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 z is viewed in ZMod q via its canonical lift to Nat.
Statement
theorem schnorr_zpow_eq_pow_zmod_val {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G) (hg : orderOf g = q) (z : ℤ) : g ^ z = g ^ (z : ZMod q).val
- Source
- folklore
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- 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₂…
- schnorr_mem_zpowers_iff_exists_zmodLet 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…
Read back from the Lean
For any commutative group $G$, any prime natural number $q$, any element $g \in G$ whose order in $G$ is equal to $q$, and any integer $z \in \mathbb{Z}$, the integer power $g^z$ is equal to the natural power $g^{(z : \mathbb{Z}/q\mathbb{Z}).\mathrm{val}}$, where $(z : \mathbb{Z}/q\mathbb{Z}).\mathrm{val} \in \mathbb{N}$ is the canonical representative of $z \pmod q$ 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
Because g has order q, g ^ q equals 1. Any integer power g ^ z therefore depends only on the exponent modulo q, reducing g ^ z to g ^ (z % q). By definition, the canonical representative (z : ZMod q).val is precisely z % q, so the integer power coincides with the natural power g ^ (z : ZMod q).val.
g ^ q = 1
Since g has order q by assumption (hg), substituting q with the order of g shows that g ^ q is the identity by `pow_orderOf_eq_one`.
uses
pow_orderOf_eq_onehave h_pow : g ^ q = 1 := by rw [← hg, pow_orderOf_eq_one]
g ^ z = g ^ (z : ZMod q).val
Because g ^ q = 1, integer powers of g depend only on the exponent modulo q, allowing g ^ z to be rewritten as g ^ (z % q) using `zpow_eq_zpow_emod'`. By `ZMod.val_intCast`, the integer remainder z % q is equal to the canonical representative (z : ZMod q).val viewed as an integer. Finally, `zpow_natCast` converts this integer power into the natural-number power g ^ (z : ZMod q).val, completing the equality.
uses
zpow_eq_zpow_emod',ZMod.val_intCast,zpow_natCastrw [zpow_eq_zpow_emod' z h_pow, ← ZMod.val_intCast z, zpow_natCast]
pow_orderOf_eq_one- An element of a monoid raised to the power of its order equals the identity element.
zpow_eq_zpow_emod'- If an element x in a group satisfies x ^ n = 1 for a natural number n, then any integer power x ^ m equals x ^ (m % n).
ZMod.val_intCast- For any integer a and non-zero natural n, the integer remainder a % n equals the canonical representative (a : ZMod n).val coerced to an integer.
zpow_natCast- Raising an element to an integer exponent that is a coerced natural number n equals raising it to the natural power n.
- Lean distinguishes between the integer power operation `g ^ (z : ℤ)` and the natural-number power `g ^ (n : ℕ)`. The proof explicitly bridges them via `zpow_natCast` after identifying the integer remainder `z % q` with the canonical lift `(z : ZMod q).val` coerced to `ℤ`.
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.
/-- In a cyclic subgroup of prime order q, integer powers equal powers of the canonical ZMod q representative. -/theorem schnorr_zpow_eq_pow_zmod_val {G : Type*} [CommGroup G] {q : ℕ} [Fact q.Prime] (g : G) (hg : orderOf g = q) (z : ℤ) : g ^ z = g ^ (z : ZMod q).val := by have h_pow : g ^ q = 1 := by rw [← hg, pow_orderOf_eq_one] rw [zpow_eq_zpow_emod' z h_pow, ← ZMod.val_intCast z, zpow_natCast]