# Polynomial Modulo Soundness

We want to proof a polynomial modular multiplication (PMM)

$$A_i(X) ⋅ B_i(X) = R_i(X) \mod P(X)$$

Where $A,B,R$ are low degree.

We can do this using an auxiliary low-degree polynomial $Q_i(X)$ and evaluating the following in a random point $z$

$$A_i(z) ⋅ B_i(z) = Q_i(z) ⋅ P(z) + R_i(z)$$

To verify many such PMMs we can take a linear combination in a random $α$

$$\sum_i α^i ⋅ A_i(X) ⋅ B_i(X) = P(z) ⋅ \sum_i α^i ⋅ Q_i(z) + \sum_i α^i ⋅ R_i(z)$$

Question Can the prover pre-sum the quotients? I.e. have an auxiliary low-degree polynomial $Q(X)$ and check:

$$\sum_i α^i ⋅ A_i(X) ⋅ B_i(X) = P(z) ⋅ Q(z) + \sum_i α^i ⋅ R_i(z)$$

Given $A_i, B_i, R_i, Q$ and $P$ low-degree polynomials that satisfy the above equation. We want to show the only solution is

$$Q(X) = \sum_i α^i ⋅ Q_i(X)$$

where

$$Q_i(X) = \frac{A_i(X) ⋅ B_i(X) - R_i(X)}{P(X)}$$

We know that

$$Q(X) = \frac{\sum_i α^i ⋅ (A_i(X) ⋅ B_i(X) - R_i(X) )}{P(X)}$$

So this amounts to proving

$$\frac{\sum_i α^i ⋅ (A_i(X) ⋅ B_i(X) - R_i(X) )}{P(X)} = \sum_i α^i ⋅ \frac{A_i(X) ⋅ B_i(X) - R_i(X)}{P(X)}$$

Let's assume that between $A_i(X) ⋅ B_i(X) - R_i(X)$ there are enough degrees of freedom that these can be arbitrary polynomials $D_i(X)$ of degree $2⋅d$:

$$\frac{\sum_i α^i ⋅ D_i(X)}{P(X)} = \sum_i α^i ⋅ \frac{D_i(X)}{P(X)}$$

Remco Bloemen
Math & Engineering
https://2π.com