3.3: Polynomial Interpolation
- Last updated
- Dec 13, 2022
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
You are probably familiar with the fact that two points determine a line (in Euclidean geometry). It is also true that 3 points determine a parabola, and so on. The next secretsharing scheme we discuss is based on the following principle: d+1 points determine a unique degree- d polynomial. A note on terminology: If f is a polynomial that can be written as f(x)=∑di=0fixi, then we say that f is a degree-d polynomial. It would be more technically correct to say that the degree of f is at most d since we allow the leading coefficient fd to be zero. For convenience, we’ll stick to saying "degree-d " to mean "degree at most d "
Polynomials Over the Reals
Let {(x1,y1),…,(xd+1,yd+1)}⊆R2 be a set of points whose xi values are all distinct. Then (Poly Interpolation) there is a unique degree-d polynomial f with real coefficients that satisfies yi=f(xi) for all i.
Proof
To start, consider the following polynomial: ℓ1(x)=(x−x2)(x−x3)⋯(x−xd+1)(x1−x2)(x1−x3)⋯(x1−xd+1) The notation is potentially confusing. ℓ1 is a polynomial with formal variable x (written in bold). The non-bold xi values are just plain numbers (scalars), given in the theorem statement. Therefore the numerator in ℓ1 is a degree- d polynomial in x. The denominator is just a scalar, and since all of the xi ’s are distinct, we are not dividing by zero. Overall, ℓ1 is a degree- d polynomial.
What happens when we evaluate ℓ1 at one of the special xi values?
- Evaluating ℓ1(x1) makes the numerator and denominator the same, so ℓ1(x1)=1.
- Evaluating ℓ1(xi) for i≠1 leads to a term (xi−xi) in the numerator, so ℓ1(xi)=0.
Of course, ℓ1 can be evaluated at any point (not just the special points x1,…,xd+1 ), but we don’t care about what happens in those cases.
We can similarly define other polynomials ℓj :
ℓj(x)=(x−x1)⋯(x−xj−1)(x−xj+1)⋯(x−xd+1)(xj−x1)⋯(xj−xj−1)(xj−xj+1)⋯(xj−xd+1)
The pattern is that the numerator is "missing" the term (x−xj) and the denominator is missing the term (xj−xj), because we don’t want a zero in the denominator. Polynomials of this kind are called LaGrange polynomials. They are each degree-d polynomials, and they satisfy the property: ℓj(xi)={1 if i=j0 if i≠j
Now consider the following polynomial:
f(x)=y1ℓ1(x)+y2ℓ2(x)+⋯+yd+1ℓd+1(x)
Note that f is a degree- d polynomial since it is the sum of degree-d polynomials (again, the yi values are just scalars)
What happens when we evaluate f on one of the special xi values? Since ℓi(xi)=1 and ℓj(xi)=0 for j≠i, we get:
f(xi)=y1ℓ1(xi)+⋯+yiℓi(xi)+⋯+yd+1ℓd+1(xi)=y1⋅0+⋯+yi⋅1+⋯+yd+1⋅0=yi
So f(xi)=yi for every xi, which is what we wanted. This shows that there is some degree- d polynomial with this property.
Now let’s argue that this f is unique. Suppose there are two degree- d polynomials f and f′ such that f(xi)=f′(xi)=yi for i∈{1,…,d+1}. Then the polynomial g(x)=f(x)−f′(x) also is degree- d, and it satisfies g(xi)=0 for all i. In other words, each xi is a root of g, so g has at least d+1 roots. But the only degree-d polynomial with d+1 roots is the identically-zero polynomial g(x)=0. If g(x)=0 then f=f′. In other words, any degree- d polynomial f′ that satisfies f′(xi)=yi must be equal to f. So f is the unique polynomial with this property.
Let’s figure out the degree-3 polynomial that passes through the points (3,1),(4,1),(5,9),(2,6)
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| xi | 3 | 4 | 5 | 2 |
| yi | 1 | 1 | 9 | 6 |
First, let’s construct the appropriate LaGrange polynomials:
ℓ1(x)=(x−x2)(x−x3)(x−x4)(x1−x2)(x1−x3)(x1−x4)=(x−4)(x−5)(x−2)(3−4)(3−5)(3−2)=x3−11x2+38x−402ℓ2(x)=(x−x1)(x−x3)(x−x4)(x2−x1)(x2−x3)(x2−x4)=(x−3)(x−5)(x−2)(4−3)(4−5)(4−2)=x3−10x2+31x−30−2ℓ3(x)=(x−x1)(x−x2)(x−x4)(x3−x1)(x3−x2)(x3−x4)=(x−3)(x−4)(x−2)(5−3)(5−4)(5−2)=x3−9x2+26x−246ℓ4(x)=(x−x1)(x−x2)(x−x3)(x4−x1)(x4−x2)(x4−x3)=(x−3)(x−4)(x−5)(2−3)(2−4)(2−5)=x3−12x2+47x−60−6 As a sanity check, notice how: ℓ1(x1)=ℓ1(3)=33−11⋅32+38⋅3−402=22=1ℓ1(x2)=ℓ1(4)=43−11⋅42+38⋅4−402=02=0
It will make the next step easier if we rewrite all LaGrange polynomials to have the same denominator 6: ℓ1(x)=3x3−33x2+114x−1206ℓ3(x)=x3−9x2+26x−246ℓ2(x)=−3x3+30x2−93x+906ℓ4(x)=−x3+12x2−47x+606
Our desired polynomial is
f(x)=y1⋅ℓ1(x)+y2⋅ℓ2(x)+y3⋅ℓ3(x)+y4⋅ℓ4(x)=1⋅ℓ1(x)+1⋅ℓ2(x)+9⋅ℓ3(x)+6⋅ℓ4(x)
=16(3x3−12x2−27x+114)=x32−2x2−9x2+19
And indeed, f gives the correct values:
|
f(x1)=f(3)=332−2⋅32−9⋅32+19=1=y1f(x2)=f(4)=432−2⋅42−9⋅42+19=1=y2f(x3)=f(5)=532−2⋅52−9⋅52+19=9=y3f(x4)=f(2)=232−2⋅22−9⋅22+19=6=y4 |
Polynomials modp
We will see a secret-sharing scheme based on polynomials, whose Share algorithm must choose a polynomial with uniformly random coefficients. Since we cannot have a uniform distribution over the real numbers, we must instead consider polynomials with coefficients in Zp
It is still true that d+1 points determine a unique degree-d polynomial when working modulo p, if p is a prime!
Let p be a prime, and let {(x1,y1),…,(xd+1,yd+1)}⊆(Zp)2 be a set of points whose xi val( Interp modp) ues are all distinct. Then there is a unique degree-d polynomial f with coefficients from Zp that satisfies yi≡pf(xi) for all i.
The proof is the same as the one for Theorem 3.8, if you interpret all arithmetic modulo p. Addition, subtraction, and multiplication mod p are straight forward; the only nontrivial question is how to interpret "division mod p " which is necessary in the definition of the ℓj polynomials. For now, just accept that you can always "divide" mod p (except by zero) when p is a prime. If you are interested in how division mod p works, look ahead to Chapter 13.
We can also generalize the observation that d+1 points uniquely determine a degree- d polynomial. It turns out that:
For any k points, there are exactly pd+1−k polynomials of degree- d that hit those points, modp.
Note how when k=d+1, the statement says that there is just a single polynomial hitting the points.
Let P={(x1,y1),…,(xk,yk)}⊆(Zp)2 be a set of points whose xi values are distinct. Letd (# of polys) satisfy k⩽ and p>d. Then the number of degree-d polynomials f with coefficients in \mathbb{Z}_{p} that satisfy the condition y_{i} \equiv_{p} f\left(x_{i}\right) for all i is exactly p^{d+1-k}.
Proof The proof is by induction on the value d+1-k. The base case is when d+1-k=0. Then we have k=d+1 distinct points, and Theorem 3.9 says that there is a unique polynomial satisfying the condition. Since p^{d+1-k}=p^{0}=1, the base case is true.
For the inductive case, we have k \leqslant d points in \mathcal{P}. Let x^{*} \in \mathbb{Z}_{p} be a value that does not appear as one of the x_{i} ’s. Every polynomial must give some value when evaluated at x^{*} . \mathrm{So} \begin{aligned} &\text { [# of degree- } d \text { polynomials passing through points in } \mathcal{P}] \\ &\qquad=\sum_{y^{*} \in \mathbb{Z}_{p}}\left[\# \text { of degree- } d \text { polynomials passing through points in } \mathcal{P} \cup\left\{\left(x^{*}, y^{*}\right)\right\}\right] \\ &\stackrel{(\star)}{=} \sum_{y^{*} \in \mathbb{Z}_{p}} p^{d+1-(k+1)} \\ &\quad=p \cdot\left(p^{d+1-k-1}\right)=p^{d+1-k} \end{aligned} The equality marked (\star) follows from the inductive hypothesis, since each of the terms involves a polynomial passing through a specified set of k+1 points with distinct x coordinates.
|
|
What does a "polynomial mod p" look like? Consider an example degree-2 polynomial: f\left ( \boldsymbol{x} \right)=\boldsymbol{x}^{2}+4\boldsymbol{x}+7 When we plot this polynomial over the real numbers (the picture on the left), we get a familiar parabola. Let’s see what this polynomial "looks like" modulo 11 (i.e., in \mathbb{Z}_{11} ). Working mod 11 means to "wrap around" every time the polynomial crosses over a multiple of 11 along the y-axis. This results in the blue plot below:
This is a picture of a mod-11 parabola. In fact, since we care only about \mathbb{Z}_{11} inputs to f, you could rightfully say that just the 11 highlighted points alone (not the blue curve) are a picture of a mod-11 parabola. |
