Open survived opened 4 months ago
Sometimes we have the same fixed set of polynomial points $\vec x$ and index $j$, and we're computing lagrange coefs $\text{coef}(j, x, \vec x)$ for different $x$. Recall that lagrange coef is computes as:
$$\text{coef}(j, x, \vec x) = \frac{\prod_{m \ne j} x - \vec xm}{\prod{m \ne j} \vec x_j - \vec x_m}$$
Note that denominator is independent of $x$. We can compute
$$\text{denom}_{j, \vec x} = (\prod_{m \ne j} \vec x_j - \vec x_m)^{-1}$$
then we can compute lagrange coef without doing modular inversion:
$$\text{coef}'(x, \text{denom}) = \text{denom} \cdot \prod_{m \ne j} x - \vec x_m$$
Computing lagrange coef code:
https://github.com/dfns/generic-ec/blob/924bc18fc39996ee8f8886391cc95e6e4256fc78/generic-ec-zkp/src/polynomial.rs#L341-L363
survived
commented
4 months ago
Sometimes we have the same fixed set of polynomial points $\vec x$ and index $j$, and we're computing lagrange coefs $\text{coef}(j, x, \vec x)$ for different $x$. Recall that lagrange coef is computes as:
$$\text{coef}(j, x, \vec x) = \frac{\prod_{m \ne j} x - \vec xm}{\prod{m \ne j} \vec x_j - \vec x_m}$$
Note that denominator is independent of $x$. We can compute
$$\text{denom}_{j, \vec x} = (\prod_{m \ne j} \vec x_j - \vec x_m)^{-1}$$
then we can compute lagrange coef without doing modular inversion:
$$\text{coef}'(x, \text{denom}) = \text{denom} \cdot \prod_{m \ne j} x - \vec x_m$$