Zero-equality testing via polynomial division

Now, remember we want to build a protocol that is more efficient than recomputing the original function. In the checks above, we were looping through the values of $I$ to check for zero equality. We can take advantage of the algebraic properties of the interpolated polynomials to do this in a different way, which will lead to a more efficient algorithm for arbitrary circuits.

In fact, since we are working on a field, we know that if $t(x)=0$ for every index $i\in I$, then the polynomial $(x-i)$ divides $t(x)$, and therefore the polynomial $Z(x)=\prod _{i\in I}(x-i)$ divides $t(x)$. Equivalently, there must exist a quotient polynomial $Q(x)\in \mathbb{F}[x]$ such that:

$$t(x)=Q(x)\cdot Z(x)$$

Checking this relation for the right "vanishing" polynomial Z replaces the need for looping over all indexes.

Exercise 4

Compute $Z(x)$ and quotient $Q(x)$ for $t(x)$. Also compute $Z^{\prime }(x)$ for $I^{\prime }=I\setminus \{3,4\}$ and the corresponding $Q_1(x)$ and $Q_2(x)$ for the recursive constraint polynomials $f_1$ and $f_2$.

#Solve here!

Z = R(1)  # Start with the constant polynomial 1
for i in I:
    Z *= (x - i)
Q = 
Z1 = 
Q1 = 
Q2 =

If computed correctly you should get:

$$\begin{array}{rl}Q(x)=& 304003373219989933642311190906351042896505061116889365884697280369108451328x^5\\ +& 18240202393199396018538671454381062573790303667013361953081836822146507079681x^4\\ +& 15504172034219486615757870736223903187721758116961357660119561298824531017728x^3\\ +& 12160134928799597345692447636254041715860202444675574635387891214764338053122x^2\\ +& 7296080957279758407415468581752425029516121466805344781232734728858602831871x\\ +& 7296080957279758407415468581752425029516121466805344781232734728858602831873\end{array}$$

We can also do the sanity check of recovering $t$ from $Q$ and $Z$.

print("Is t(x) = Q(x) * Z(x)?", t == Q*Z)
show("Q=",Q)
print("Is f1(x) = Q1(x) * Z1(x)?", f1 == Q1*Z1)
show("Q1=",Q1)
print("Is f2(x) = Q2(x) * Z1(x)?", f2 == Q2*Z1)
show("Q2=",Q2)