Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've read that Newton polynomials have better computational complexity, but Shamir's uses Lagrange polynomials instead. Does anyone know if there are particular reason why Newton polynomials aren't used instead?

share|improve this question
    
What does "computational complexity" mean here? These are the same polynomials, just written differently. –  Paŭlo Ebermann Jun 24 at 20:30
    
@PaŭloEbermann I meant the computational complexity of Newton interpolation. –  Kate Jun 25 at 4:15

1 Answer 1

up vote 5 down vote accepted

The purpose of the reconstruction of the polynomial $P(x)$, is just to calculate the value of $P(0)$, which equals the shared secret value.

If Lagrange polynomials are used, a trivial optimization which cuts the number of multiplication nearly in half is $$P(0) = (\prod_{i=0}^{n-1}{-x_i})\sum_{i=0}^{n-1}{{\frac{y_i}{-x_i (\prod_{j=0,j\neq i}^{n-1}{(x_i-x_j)})}}}.$$

If Newton polynomials are used, there is no trivial optimization because you only want to calculate $P(0)$, simply because the formula is already optimized to half of $n^2$. This means that the overhead of the recursion might outweigh the general benefits compare to the Lagrange formula.

If you had had to represent the polynomial $P(x)$ in order to calculate other values than just $P(0)$, Newton polynomials would in general have been more efficient.

share|improve this answer
    
Thanks, I improved it a bit further, to make it a bit a clearer exactly which calculations are made. –  Henrick Hellström Jun 25 at 11:17
1  
Technically, your question captures that $O(n^2) = O(kn^2 + r)$ for constant parameters $k, r$. The formula in my answer requires only about half as many multiplications, as if you were to calculate the coefficients of $P(x)$ instead of the the value of $P(0)$ directly. Newton's formula calculates the coefficients faster than Lagrange's formula, but it doesn't necessarily calculate the value of $P(0)$ faster. –  Henrick Hellström Jun 25 at 12:35
    
@HenrickHellström Sorry, I deleted my comment a few minutes after posting, as I managed to figure it out! Thanks though! –  Kate Jun 25 at 12:37

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.