Interpolation and Zero-Testing over domains

Exercise 12

Interpolate the value vectors and selector vectors as before, now over $\mathrm{\Omega }$ instead of $I$.

#Solve here! Hint: your previously defined interpolate function should also work here!
Ω = [ω^i for i in range(1,n+1)]
a = interpolate(Ω,list(LI.values())) #Now the points are (ω^i, LI[i]) for i in I
b = 
c = 

qL =
qR =
qM =

If computed correctly you should have obtained:

$$\begin{array}{rl}a(x)=& 16416182153879456417786784551517017277046601793284012108757927423286461067892x^3\\ +& 5472060717959818805561601436314318772137091100104008585924551046643952123905x^2\\ +& 5472060717959818804459621193740257811501762607132022234940276763289347427726x\\ +& 16416182153879456416684804308942956316411273300312025757773653139931856371714\end{array}$$

We said that one of the advantage of working with multiplicatives domains is that the verifier can now use $Z(x)=x^n-1$ as the vanishing polynomial, which can be computed in constant time, instead of $Z(x)=\prod _i^d(x-i)$ which is an $O(d)$ operation.

Exercise 13

Let $t(x)=qM\ast a\ast b+qL\ast a+qR\ast b-c$ where the polynomials $a(x),b(x),c(x)$ are obtained by Lagrange–interpolating the three witness columns over the multiplicative domain $\mathrm{\Omega }=\{\omega ,{\omega }^2,\dots ,{\omega }^4\}$. Take the domain‑vanishing polynomial $Z(x)=x^4-1$. Perform polynomial long‑division of $t(x)$ by $Z(x)$; that is, find polynomials $Q(x),R(x)\in {\mathbb{F}}_p[x]$ such that:

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

Verify that the division is exact: show that the remainder $R(x)$ is zero. Equivalently, confirm that there exists a polynomial $Q(x)\in {\mathbb{F}}_p[x]$ for which

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

#Solve here!

t = qM*a*b + qL*a+qR*b-c      
Z =  x^4 - 1                     
Quo=
Rem=

print("Quotient Q(x):\n", Quo)
print("\nRemainder R(x):\n", Rem)
print("\nIs remainder zero?  ", Rem == 0) #should be True