# How do I construct a recursive polynomial as required in PLONK?

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s

At around 19 minutes, he gets to the Prod Check Gadget.

Background:

$$\omega \in F_p$$ is the primitive $$k$$th root of unity (i.e. $$\omega^{k} = 1$$)

$$\Omega = \{1, \omega, \omega^{2}, ..., \omega^{k-1}\}$$

Then he sets $$t \in {F_p}^{(\le k)}[X]$$ to be the degree-$$k$$ polynomial such that

$$t(1) = f(1)$$ and $$t(\omega^s) = \prod_{i=0}^s f(\omega^i)$$ for $$s = 1, ..., k-1$$.

So $$t(\omega) = f(1)\cdot f(\omega)$$

$$t(\omega^2) = f(1)\cdot f(\omega)\cdot f(\omega^2)$$

$$\dots$$

$$t(\omega^{k-1})= f(1)\cdot f(\omega)\cdot f(\omega^2)\dots f(\omega^{k-2})\cdot f(\omega^{k-1})$$

In the next slide, he says that the Prover should construct the polynomial $$t(X) \in {F_p}^{(\le k)}$$ & he will use this polynomial $$t(X)$$ for the proof.

I am confused as to how do I construct a recursive polynomial like $$t(X)$$.

I know how to calculate the value of $$t(X)$$ for any value of $$X \in \Omega$$ - that's pretty simple.

i.e. if I want to calculate $$t(\omega^3)$$, it can be calculated as

$$t(\omega^3) = f(1) \cdot f(\omega) \cdot f(\omega^2) \cdot f(\omega^3)$$

However, how do I construct a univariate polynomial $$t$$ in a way that the Prover can send a commitment of this polynomial to the Verifier?

Let's say my $$f$$ polynomial is

$$f(X) = 3X^2 + 4X + 7$$

How do I go from here to constructing $$t(X)$$?

To construct $$t(X)$$, you can use the Lagrange interpolation method.

Suppose $$F=GF(17)$$ and $$w=4$$ is an $$4^{th}$$ roots of unity in $$F$$. (I'm taking your example from this post )

Now $$f(X)=3X^2+4X+7$$ and $$\Omega=\{1,4,16,13\}$$.

Then $$t(X)$$ will be $$6X^3 + 13X^2 + 11X + 1$$.

Here is the sage code for this:

sage:F=GF(17)
sage:w=F(4)
sage:R.<x>=PolynomialRing(F,'x')
sage:f=3*x^2+4*x+7
sage:points=[(w^0,f(w^0)),(w,f(w^0)*f(w)),(w^2,f(w^0)*f(w)*f(w^2)),(w^3,f(w^0)*f(w)*f(w^2)*f(w^3))]
sage:t=R.lagrange_polynomial(points)
sage:t



output:

6*x^3 + 13*x^2 + 11*x + 1

• Thank you very much for the answer. If you get time, could you also look at this question of mine - crypto.stackexchange.com/questions/105901/… - my question was only about $\prod_{a \in \Omega} f(a) = 1$ & the answer seems satisfactory however, in the comments, I have also discussed $\prod_{a \in \Omega} f(a) = m$ - I am not so convinced about the answer for that. If you have any thoughts, do let me know. Let me know if I should ask a separate question for $\prod_{a \in \Omega} f(a) = m$? Apr 8, 2023 at 8:40