I have been reading “How to Share a Secret” in detail for the past few weeks, a revolutionary research paper by Adi Shamir. This paper applies some of the concepts of Number Theory and Algebra, one of which is polynomial interpolation, and has been used to construct a secure and reliable key management system. The theorem is simple and easy to understand, and has been applied in the best way one ever could.
Theorem: (Uniqueness of Polynomial Interpolation)
Consider n+1 unequal coordinates (x0,y0),(x1,y1),(x2,y2),…..,(xn,yn). According to the theorem of uniqueness of polynomial interpolation, there exists at most one polynomial p of degree less than or equal to n such that:
p(xi) = yi; i=0,…..,n
Remember the uniqueness for the satisfying polynomial is only for a particular degree. There can exist two polynomials of different degrees which contain all of these points.
We are going to prove this theorem by contradiction.
Let us assume that there exist two polynomials p1 and p2 of degree less than or equal to n, that satisfying
p1(xi) = p2(xi) = yi; i=0,…..,n
This implies: All the points lie on the graphs of p1 and p2. So, one can conclude that at these points, the difference between the polynomials is zero since the value is same for both of the polynomials on that point. We can generalize this as:
q(xi) = p1(xi) – p2(xi); i=0,…..,n
The degree of the polynomial q(xi) is same as that of p1 and p2 i.e. less than or equal to n. We can conclude from the above that:
q(xi) = 0; i=0,…..,n
Clearly, the polynomial has n+1 zeros. How is it possible? How can a polynomial of degree <= n have n+1 zeros? Yes, it can happen only when the polynomial q(xi) is a zero polynomial i.e. value of q is zero at all points of x in the Cartesian Plane.
Now, since q is a zero polynomial, from the above equations we have:
q(xi) = p1(xi) – p2(xi)
0 = p1(xi) – p2(xi)
p2(xi) = p1(xi); i=0,…..,n
Thus we have proved that the polynomials p2 and p1 are identical polynomials, making our assumption wrong. Hence, we have proved the theorem mentioned above by method of contradiction!