CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page
  • Introduction
  • Important Properties
  • Finite Fields
  • Lagrange Interpolation
  • Secret Sharing
  • Error Correction
  • Erasure Errors
  • General Errors

Was this helpful?

  1. Discrete Math

Polynomials

PreviousRSA CryptographyNextCountability

Last updated 4 years ago

Was this helpful?

Introduction

"I learned this in 4th grade", you say, "and I already know how to do Taylor approximations and binomial expansions and get local minima... what else is there to do?" (At least that was my first thought )

Turns out, polynomials are super useful in the world of discrete math. Here, we'll cover two applications in discrete space, which are secret sharing and error correction.

Important Properties

Gotta do some quick review first! Recall that all polynomials are in the form

adxd+ad−1xd−1+⋯+a1x+a0a_dx^d + a_{d-1}x^{d-1} + \cdots + a_1x + a_0ad​xd+ad−1​xd−1+⋯+a1​x+a0​

where dddis the degree of the polynomial (highest power) and aia_iai​are the coefficients.

Polynomials have some nice properties:

  • A nonzero polynomial of degree dddhas at most dddreal roots.

  • If we're given d+1d+1d+1distinct points (x y pairs), there is exactly one, unique polynomial of degree dddthat goes through all of those points.

Finite Fields

Like many things in discrete math, polynomials can be taken to a modulo as well! When this happens and we have p(x)(modm)p(x) \pmod{m}p(x)(modm)where p(x)p(x)p(x)is a polynomial and mmmis a prime number, we say that we're working in a Galois Field GF(m)GF(m)GF(m).

Even when working over a finite field, the two properties of polynomials still apply. Finite fields restrict the number of possible polynomials, which is actually necessary for some of the applications below.

Lagrange Interpolation

We have already established that d+1d+1d+1points only have one unique degree dddpolynomial that goes through all of them. But how do we find this one polynomial?

Lagrange Interpolation is a method to recover this polynomial given your original points. It has a lot of interesting ties to previously covered concepts like the Chinese Remainder Theorem and linear algebra (which won't be covered here, but explore it further to find out more!). Here's how it works:

First, let's find a polynomial that is degree ddd and is equal to 111at point x1x_1x1​, but 000everywhere else. This isn't too hard to do: we can use (x−x2)(x−x3)⋯(x−xd+1)(x-x_2)(x-x_3)\cdots(x-x_{d+1})(x−x2​)(x−x3​)⋯(x−xd+1​). Note here that we skipped x1x_1x1​because adding that term would make the polynomial degree d+1d+1d+1! However, this alone would result in a number other than 1 at x1x_1x1​, so we can normalize it by dividing by all (x1−xj)(x_1-x_j)(x1​−xj​):

Δ1(x)=∏j≠1(x−xj)∏j≠i(x1−xj)\Delta_1(x) = \frac{\prod_{j \ne 1} (x - x_j)}{\prod_{j \ne i} (x_1 - x_j)}Δ1​(x)=∏j=i​(x1​−xj​)∏j=1​(x−xj​)​

Why are we doing this though? Well, you can think of it like creating a basis of polynomials so that we can take a linear combination of all of them to get the original. Since Δ1(x1)=1\Delta_1(x_1) = 1Δ1​(x1​)=1, we can multiply it by y1y_1y1​ to ensure that it passes through the original point. Combining all of the delta polynomials for all d+1d+1d+1original points yields

p(x)=∑i=1d+1yiΔi(x)p(x) = \sum_{i=1}^{d+1} y_i \Delta_i(x)p(x)=i=1∑d+1​yi​Δi​(x)

Secret Sharing

Now, let's take a look at a cool application of Lagrange interpolation!

Here's the setup: let's say you're in the Super Secret Club and want to create a secret code for your Super Secret Vault™. However, you want to make sure that the Vault™ can only be opened if 30 of your 50 members agree. How would we pull this off?

Here's the solution: create a 29-degree polynomial and give each person in the club a point on that polynomial (xi,yi)(x_i, y_i)(xi​,yi​). Make sure none of the x's are 0! Then, set the secret code equal to y0y_0y0​, the y-value of the polynomial corresponding to x=0x=0x=0.

We know that a 29-degree unique polynomial can be recovered with 30 distinct points. So, if 30 members agree and get together to share their points, we can use Lagrange interpolation to recover the original polynomial! Once you have this original polynomial, it is a simple matter to recover the secret code by plugging in 0 to the polynomial.

Error Correction

Lagrange interpolation can also be used to correct errors in data (if it gets erased or corrupted). There are two main types of errors: erasure errors, when the data is simply lost, and general errors, where the data is corrupted and displays something other than the original data.

Erasure Errors

Erasure errors aren't too tough to think about once we have a good grasp of polynomial properties. Since we know that a unique polynomial of degree dddcan be recovered with d+1d+1d+1points, we could simply tack on an additional kkkpoints in order to protect the original polynomial from kkkerased points.

General Errors

General errors, on the other hand, are slightly more difficult to consider because they could throw off the result wildly if we do not identify them. So how do we figure out which points are the errors?

Let us construct an error-locator polynomial E(x)=(x−e1)(x−e2)⋯(x−ek)E(x) = (x-e_1)(x-e_2) \cdots (x-e_k)E(x)=(x−e1​)(x−e2​)⋯(x−ek​) where an error eie_iei​ represents the incorrect value given by one of the spies when in a larger group.

For any one point iii in the original polynomial P(i)P(i)P(i), we know that P(i)E(i)=riE(i)P(i)E(i) = r_iE(i)P(i)E(i)=ri​E(i) where rir_iri​ is the original location of the point of the polynomial.

If we have MMM original data points, this provides enough points for a M−1M-1M−1 degree polynomial, which we can call Q(x)Q(x)Q(x). For any particular point, though, we know that Q(i)=P(i)E(i)Q(i) = P(i)E(i)Q(i)=P(i)E(i) since the point given is either in the original polynomial, or is in the error-locator polynomial. Therefore, in order to solve for the true polynomial P(x)P(x)P(x), we can take the ratio Q(x)E(x)\frac{Q(x)}{E(x)}E(x)Q(x)​ by definition of Q(x)Q(x)Q(x). Since we do not know what each value eie_iei​ is, we need to solve a system of linear equations for each point to identify what these are. This requires M+2kM + 2kM+2k equations, because we require the polynomial Q(x)E(x)Q(x)E(x)Q(x)E(x) to perform this calculation.

😛