Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
Well, just do it! $$a\cdot a^{-1}=1\Longrightarrow (-a)\cdot a^{-1}=...??$$ –  DonAntonio Dec 1 '12 at 23:46
    
@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? –  ampersand Dec 1 '12 at 23:50
    
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. –  DonAntonio Dec 2 '12 at 0:03
    
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. –  ampersand Dec 2 '12 at 0:10
    
@ampersand: Thanks, misread question. –  André Nicolas Dec 2 '12 at 1:00

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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