Definitions of ShoupCoefficients: Coefficient interface to Shoup's construction The field consumers use the lower coefficients of the monic polynomial
DefinitionMIPRE_Foundations_LowDegree_ShoupCoefficientsThe definitions of the module MIPRE.Foundations.LowDegree.ShoupCoefficients of the MIP* = RE formalization (commit 70cbf1c of vidick/MIPRE-formalization). Coefficient interface to Shoup's construction. The field consumers use the lower coefficients of the monic polynomial. Keeping this adapter separate lets generic arithmetic and the future constructor use the same coefficient algorithms without importing the Shoup interface.
Definitions (1): MIPRE.LowDegree.BinaryPolynomial.shoupLowerCoeffs (Shoup's output normalized to the k lower coefficients; the leading monic coefficient is implicit.).
Formalization Note The bundle is the module MIPRE.Foundations.LowDegree.ShoupCoefficients (MIPRE/Foundations/LowDegree/ShoupCoefficients.lean) with every declaration not listed removed, imports rewritten to the bundles of the module's import closure; the declarations keep their names, statements and bodies; the source module is split over 71 imported bundle(s).
/- Copyright (c) 2026 MIPRE contributors. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. -/ /- Generated for Prove2Me from vidick/MIPRE-formalization@70cbf1c, MIPRE/Foundations/LowDegree/ShoupCoefficients.lean (definition bundle: declarations the uploaded statements rest on); produced mechanically by prove2me/tools/gen.py, never edited by hand. -/ import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.CharP.Algebra import Mathlib.Algebra.CharP.Two import Mathlib.Algebra.Field.ZMod import Mathlib.Algebra.MonoidAlgebra.Basic import Mathlib.Algebra.MvPolynomial.CommRing import Mathlib.Algebra.MvPolynomial.Degrees import Mathlib.Algebra.Polynomial.Degree.SmallDegree import Mathlib.Algebra.Polynomial.Div import Mathlib.Algebra.Polynomial.Eval.Defs import Mathlib.Algebra.Polynomial.FieldDivision import Mathlib.Algebra.Polynomial.Monic import Mathlib.Algebra.Polynomial.SpecificDegree import Mathlib.Algebra.Squarefree.Basic import Mathlib.Data.List.Basic import Mathlib.Data.List.OfFn import Mathlib.Data.List.Rotate import Mathlib.Data.Matrix.Mul import Mathlib.Data.Nat.Bits import Mathlib.Data.Nat.Factorization.Basic import Mathlib.Data.Nat.Notation import Mathlib.Data.Nat.Size import Mathlib.Data.ZMod.Basic import Mathlib.FieldTheory.Finite.Basic import Mathlib.FieldTheory.Finite.Extension import Mathlib.FieldTheory.IsAlgClosed.AlgebraicClosure import Mathlib.FieldTheory.KummerExtension import Mathlib.FieldTheory.Minpoly.Finite import Mathlib.LinearAlgebra.FiniteDimensional.Lemmas import Mathlib.LinearAlgebra.LinearIndependent.Lemmas import Mathlib.LinearAlgebra.Matrix.Circulant import Mathlib.LinearAlgebra.Matrix.ToLin import Mathlib.RingTheory.AdjoinRoot import Mathlib.RingTheory.Coprime.Lemmas import Mathlib.RingTheory.Polynomial.Content import Mathlib.RingTheory.Polynomial.Cyclotomic.Factorization import Mathlib.RingTheory.RootsOfUnity.PrimitiveRoots import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring import Definitions.Def_MIPRE_Foundations_Cost_Basic_B import Definitions.Def_MIPRE_Foundations_Cost_Encoding_B import Definitions.Def_MIPRE_Foundations_SAT_Circuit import Definitions.Def_MIPRE_Foundations_Cost_PolyTime import Definitions.Def_MIPRE_Foundations_Cost_Closure import Definitions.Def_MIPRE_Foundations_Cost_Loops_B import Definitions.Def_MIPRE_Foundations_Cost_Fold import Definitions.Def_MIPRE_Foundations_Cost_Unary import Definitions.Def_MIPRE_Foundations_Cost_Numeric_B import Definitions.Def_MIPRE_Foundations_LowDegree_Encoding import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryRepresentation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryConstants import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotient import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNormalize import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDivision import Definitions.Def_MIPRE_Foundations_Cost_Binary import Definitions.Def_MIPRE_Foundations_SAT_Formula import Definitions.Def_MIPRE_Foundations_SAT_FmlLib import Definitions.Def_MIPRE_Foundations_SAT_Flatten import Definitions.Def_MIPRE_Foundations_Cost_Reader import Definitions.Def_MIPRE_Foundations_SAT_FmlProg import Definitions.Def_MIPRE_Foundations_SAT_ArrayProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryLinear import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryElimination import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasisProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryEchelon import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryBasis import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySolve import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryMatrixSolve import Definitions.Def_MIPRE_Foundations_Cost_Iterates import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCirculantProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryKernel import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGroupAlgebra import Definitions.Def_MIPRE_Foundations_LowDegree_FiniteReducedComponents import Definitions.Def_MIPRE_Foundations_LowDegree_IdempotentSplit import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponents import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComponentsProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientFrobenius import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientComponents import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientFactors import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryGCD import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryFactorization import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCyclotomicSeed import Definitions.Def_MIPRE_Foundations_LowDegree_BinarySubstitution import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNonresidueLoop import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryNonresidueCorrectness import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientOrbit import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryTraceBits import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOrbitPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOrbitDescent import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryQuotientTranslation import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryCoprimeDegree import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComposedSumPolynomial import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryComposedSumProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryOddPrimeProgram import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPrimePowerTrace import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreier import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierProg import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierTower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryArtinSchreierLoop import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryDegreeArithmetic import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryPrimality import Definitions.Def_MIPRE_Foundations_LowDegree_UnaryPrimePower import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDegreeFactors import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryDegreeDecomposition import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryPrimePowerDispatch import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryIrreducibleAssembly import Definitions.Def_MIPRE_Foundations_LowDegree_BinaryIrreducibleConstructor import Definitions.Def_MIPRE_Foundations_LowDegree_Shoup /-! # Coefficient interface to Shoup's construction The field consumers use the lower coefficients of the monic polynomial. Keeping this adapter separate lets generic arithmetic and the future constructor use the same coefficient algorithms without importing the Shoup interface. -/ namespace MIPRE.LowDegree.BinaryPolynomial open Cost /-- Shoup's output normalized to the `k` lower coefficients; the leading monic coefficient is implicit. This construction retains Shoup's unary input bound. -/ noncomputable def shoupLowerCoeffs : PolyTimeFun Unary BitStr := takeBitsProg.comp ((PolyTimeFun.id _).pair shoupIrreducible) end MIPRE.LowDegree.BinaryPolynomial