AFTD Auto-Formalizing Theoretical Domains

schnorr_zpow_eq_pow_zmod_val

theoremverified

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.

  1. 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`.

    line 5

    uses pow_orderOf_eq_one

      have h_pow : g ^ q = 1 := by rw [← hg, pow_orderOf_eq_one]
  2. 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.

    line 6

    uses zpow_eq_zpow_emod', ZMod.val_intCast, zpow_natCast

      rw [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.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it