6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What does "computational complexity" mean here? These are the same polynomials, just written differently. $\endgroup$ Jun 24, 2014 at 20:30
  • $\begingroup$ @PaŭloEbermann I meant the computational complexity of Newton interpolation. $\endgroup$
    – Kar
    Jun 25, 2014 at 4:15

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks, I improved it a bit further, to make it a bit a clearer exactly which calculations are made. $\endgroup$ Jun 25, 2014 at 11:17
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 25, 2014 at 12:35
  • $\begingroup$ @HenrickHellström Sorry, I deleted my comment a few minutes after posting, as I managed to figure it out! Thanks though! $\endgroup$
    – Kar
    Jun 25, 2014 at 12:37

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.