§1 example 2: discrete logarithm from a rank-two stabilizer
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.discrete_log_reductionLet be prime, let generate the unit group modulo , and let be a unit. Suppose an integer basis is supplied for
One classical procedure, polynomial in the binary input length and chosen before , returns an integer such that
For , the representative is necessarily zero. This identifies the exact information extracted from a stabilizer basis.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
noncomputable section
open scoped Matrix ComplexConjugate Kronecker
namespace QAlgorithms.Papers.Independent.Intakethird100.P03
open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)
attribute [local instance] Classical.propDecidable
/-- PDF p.4, example 2: one classical polynomial-time procedure extracts m modulo q-1
from a basis of P, with (m,-1) in P and zeta^m=g. q=2 returns the representative zero. -/
theorem discrete_log_reduction :
∃ extract : List Bool → List Bool, QAlgorithms.Complexity.PolyTimeComputable extract ∧
∀ (q : ℕ), Nat.Prime q → ∀ (zeta g : (ZMod q)ˣ), orderOf zeta = q - 1 →
∀ B : Matrix (Fin 2) (Fin 2) ℤ, IsLatticeBasis B →
(∀ v : Fin 2 → ℤ, v ∈ columnLattice B ↔ zeta ^ (v 0) * g ^ (v 1) = 1) →
∃ m : ℕ, m < q - 1 ∧
extract (discreteLogInput q zeta g B) = encodeNatural m ∧
(![((m : ℕ) : ℤ), -1] : Fin 2 → ℤ) ∈ columnLattice B ∧ zeta ^ m = g := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a function from finite Boolean lists to finite Boolean lists that is Turing-machine computable in polynomial time with identity input and output encodings, such that for every prime natural number , every pair of units of with of multiplicative order , and every integer matrix whose multiplication map on is injective, the following implication holds: if, for every , membership in is equivalent to , then there exists a natural number such that applied to the encoded input returns the natural-number encoding of , the integer vector belongs to , and . Negative exponents in the hypothesis are taken in the unit group. The encoded input concatenates natural-number encodings of and the representatives of in , then the natural-number encoding of and signed encodings of . A natural number is encoded by the least-significant-first binary digits of , prefixed by their length in true bits and one false bit; an integer is encoded by the bit indicating followed by the natural-number encoding of . The hypotheses allow and exclude ; no behavior is specified on inputs failing the hypotheses.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.