Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Engineering LibreTexts

3.3: Polynomial Interpolation

( \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

Theorem 3.8

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)=(xx2)(xx3)(xxd+1)(x1x2)(x1x3)(x1xd+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 i1 leads to a term (xixi) 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)=(xx1)(xxj1)(xxj+1)(xxd+1)(xjx1)(xjxj1)(xjxj+1)(xjxd+1)

The pattern is that the numerator is "missing" the term (xxj) and the denominator is missing the term (xjxj), 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 ij

Now consider the following polynomial:

f(x)=y11(x)+y22(x)++yd+1d+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 ji, we get:

f(xi)=y11(xi)++yii(xi)++yd+1d+1(xi)=y10++yi1++yd+10=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.

Example 3.3.1

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)=(xx2)(xx3)(xx4)(x1x2)(x1x3)(x1x4)=(x4)(x5)(x2)(34)(35)(32)=x311x2+38x4022(x)=(xx1)(xx3)(xx4)(x2x1)(x2x3)(x2x4)=(x3)(x5)(x2)(43)(45)(42)=x310x2+31x3023(x)=(xx1)(xx2)(xx4)(x3x1)(x3x2)(x3x4)=(x3)(x4)(x2)(53)(54)(52)=x39x2+26x2464(x)=(xx1)(xx2)(xx3)(x4x1)(x4x2)(x4x3)=(x3)(x4)(x5)(23)(24)(25)=x312x2+47x606 As a sanity check, notice how: 1(x1)=1(3)=331132+383402=22=11(x2)=1(4)=431142+384402=02=0

It will make the next step easier if we rewrite all LaGrange polynomials to have the same denominator 6: 1(x)=3x333x2+114x12063(x)=x39x2+26x2462(x)=3x3+30x293x+9064(x)=x3+12x247x+606

Our desired polynomial is

f(x)=y11(x)+y22(x)+y33(x)+y44(x)=11(x)+12(x)+93(x)+64(x)

=16(3x312x227x+114)=x322x29x2+19

And indeed, f gives the correct values:

fig-ch01_patchfile_01.jpg
Figure 3.3.1: Copy and Paste Caption here. (Copyright; author via source)
f(x1)=f(3)=332232932+19=1=y1f(x2)=f(4)=432242942+19=1=y2f(x3)=f(5)=532252952+19=9=y3f(x4)=f(2)=232222922+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!

Theorem 3.9

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 yipf(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+1k 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.

Corollary 3.10

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.

Example \PageIndex{1}
fig-ch01_patchfile_01.jpg
Figure \PageIndex{1}: Copy and Paste Caption here. (Copyright; author via source)

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:

fig-ch01_patchfile_01.jpg
Figure \PageIndex{1}: Copy and Paste Caption here. (Copyright; author via source)

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.

 


This page titled 3.3: Polynomial Interpolation is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?