# How come Shamir Secret Sharing uses Lagrange interpolation?

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?

• What does "computational complexity" mean here? These are the same polynomials, just written differently. – Paŭlo Ebermann Jun 24 '14 at 20:30
• @PaŭloEbermann I meant the computational complexity of Newton interpolation. – 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.
• 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 '14 at 12:35