PR #6453: the CRT encoding computes multiplication
ProvedPr6453Encoding.crt_encodingalgebracomplexity-theoryinteger-multiplication
The CRT encoding of a product, stated explicitly. Encode a polynomial by its values at the points of a finite set S, multiply the encodings pointwise, decode by interpolation: the result is the product, provided the product's degree is below the number of points. The ingredients are that evaluation is multiplicative and additive, and that below that bound the evaluations determine a polynomial.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace Pr6453Encoding
theorem crt_encoding {R : Type*} [CommRing R] [IsDomain R] {S : Finset R} (p q r : Polynomial R)
(hpq : (p * q).natDegree < S.card) (hr : r.natDegree < S.card)
(h : ∀ x ∈ S, Polynomial.eval x r = Polynomial.eval x p * Polynomial.eval x q) :
r = p * q := by
sorry
end Pr6453EncodingSource
CrocSwap/integer-mult-bounds, PR #6453, head b1a3e525793eca35c56324aa7ffd0b714cf606d4, RESULT.json (module block).