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?

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

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.

  • $\begingroup$ Thanks, I improved it a bit further, to make it a bit a clearer exactly which calculations are made. $\endgroup$ – Henrick Hellström Jun 25 '14 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$ – Henrick Hellström Jun 25 '14 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 '14 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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