2
$\begingroup$

In javascript, I am implementing Lagrange interpolation over a finite field $GF_p$ for some prime $p$. I only need to compute the value of the $y$-intercept of the Lagrange interpolation polynomial $L(x)$ (this is for Shamir's threshold secret sharing scheme, which stores the secret in the constant term). Given points on a polynomial $(x_0,y_0),...,(x_k,y_k)$, I am using the following formula for the Lagrange interpolation polynomial $L(x)$ evaluated at $x=0$:

$L(0) = \sum\limits_{i=0}^{k} y_i \prod\limits_{j=0, j\neq i}^{k} \frac{x_j}{(x_j-x_i)}$ mod $p$

I notice that the negative of some $(x_j-x_i)$ terms will appear in some of the product terms. Because computing the multiplicative inverse of $(x_j-x_i)$ is computationally expensive, I don't want to repeat calculations that can be simplified. Therefore, how can I compute the multiplicative inverse of $(x_i-x_j)$ from an already-computed multiplicative inverse of$(x_j-x_i)$? Are they equal, or is the former the negation of the latter?

  • 5
    Well, just do it! $$a\cdot a^{-1}=1\Longrightarrow (-a)\cdot a^{-1}=...??$$2012-12-01
  • 0
    @DonAntonio, thank you for the assignment, I'm sure. I can see that it's the negative. However, I'm new to modular arithmetic so not sure if it is just the negation or if they would be *equal*?2012-12-01
  • 0
    Well, you're welcome...and if you see it then what is the problem, whether you're new or not to modular arithmetic? All you need to know is that we have here $\,(-a)b=a(-b)=-(ab)\,$ . This comes from general ring theory considerations, but you don't need to know ring theory for that *here*.2012-12-02
  • 0
    I meant that I see it's the negative in the problem you presented, not in the one I presented. But ok, I'll just use the negative of the MI of $(x_j-x_i)$ for the MI of $(x_i-x_j)$. Thank you.2012-12-02
  • 0
    @ampersand: Thanks, misread question.2012-12-02

1 Answers 1

1

$(x_i-x_j)^{-1} = -(x_j-x_i)^{-1}$ is valid.