Lagrange interpolation seems to be affected by the so-called Runge phenomenon wh

Question

Lagrange interpolation seems to be affected by the so-called Runge phenomenon when one tries to interpolate polynomials of high degree from a set of equidistant points.

Lagrange interpolation is used in some secret sharing schemes like Shamir's secret sharing, in which the polynomial being interpolated is not continuous but defined over a finite field.

Does any of you know whether this Runge phenomenon also exists or could also affect the accuracy of the interpolation done in Shamir's secret sharing scheme?

Explanation / Answer

No, the Runge phenomenon is known not to affect Shamir's scheme.

Remember, the point of Shamir's scheme is not actually to form an approximation over an interval; instead, it's to encode a secret in a randomly chosen polynomial, and then divide up clues to that polynomial so that, with enough clues (shares), someone can reconstruct the entire polynomial (and hence recover the secret).

(Now, in practice, we don't bother reconstructing the entire polynomial; instead, we just recover the coefficient that is the secret. However, that's just a detail; we could, if we wanted to, recover the entire polynomial).

So, in terms of accuracy, the question is "do we recover the polynomial with sufficient accuracy so that we can uniquely identify the secret". And, the answer to that is, yes, we can (because computation in Finite Fields are done precisely, with no rounding errors).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.