In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget

$\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$)

$H = \{1, \omega, \omega^2, ..., \omega^{k-1}\} \subseteq F_p$

Prod Check Gadget is used to prove that $\prod_{a \in H} f(a) = c$

I was trying to construct a polynomial $f(x)$ which there is true.

I used $p=17$ i.e $f \in F_{17}$

$\omega = 4$ is the primitive $4$th root of unity in $F_{17}$.

So $H = \{1, 4, 16, 13\}$

Let $c = 5$

Now, I try to find a polynomial $f$ such that $f(a) = 5$ for all $a \in H$ using Lagrange Polynomial Interpolation.

sage: F17 = GF(17)
sage: R17.<x> = PolynomialRing(F17)
sage: w = F17(4)
sage: c = F17(5)
sage: points = [(w^0, c), (w, c), (w^2, c), (w^3, c)]
sage: R17.lagrange_polynomial(points)

So Lagrange Interpolation gives returns $f$ as the trivial polynomial $f(x) = 5$

Any value of $c$ returns the polynomial as $f(x) = c$

So I am unable figure what is the point of this gadget?

Or am I doing something wrong in my toy example?


1 Answer 1


ProdCheck gadget is used for checking the product of values of the polynomial over a multiplicative subgroup of the field is equal to some constant or not.

In your toy example, you want to find a polynomial $f$ such that $f(a)=5$ for all $a\in H$. But Prodcheck gadget is for checking $\prod\limits_{a\in H}f(a)=c$ or not.

For the Lagrange polynomial computation over $F_{17}$ , sage outputs $5$ because I think it will be the constant polynomial $f(x)=5$

  • $\begingroup$ You are right. Brain fade moment for me! However, Is there a way, I can create a polynomial where $\prod\limits_{a\in H}f(a)=c$ in $F_{17}$ with $w$ as the primitive 4th root of unity $\endgroup$
    – user93353
    Apr 6, 2023 at 11:41
  • $\begingroup$ You can construct a polynomial $f$ like this: choose $c_0,c_1,c_2,c_3$ such that $c=c_0c_1c_2c_3$ and construct $f$ using Lagrange interpolation such that $f(w^i)=c_i.$ $\endgroup$
    – Manas Jana
    Apr 6, 2023 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.