[intro]

Polynomials

Examples of polynomials in one variable over the reals:

:`P(x) = 3x^2 + 7x – 2`

:`Q(x) = x^123 – ½ x^25 + 19 x^3 – 1`

:`R(y) = 2y + √2`

:`S(z) = z^2 – z - 1`

:`T(x) = 0`

:`W(x) = π`

=Coefficients=

A degree-`d` polynomial is represented by its `(d+1)` coefficients:

::`P(x) = a_d x^d + a_(d-1) x^(d-1) + ... + a_1 x^1 + a_0`

The numbers `a_d, a_(d-1), . . ., a_0` are the coefficients.

''Example'': In `P(x) = 3x^4 – 7x^2 + 12x – 19`, the coefficients are `3, 0, -7, 12, and -19`.

We could work over any '''field'''; that is, a set with addition, multiplication, and division defined (see chapter 15). For example, we could work with the rationals or the reals. Or with `ZZ_p`, the integers mod prime `p`. In this chapter, we will work with `ZZ_p`.

Let us take a closer look at the set `ZZ_p` for prime `p`.

:`ZZ_p = {0, 1, 2, . . . , p-1}`

:`ZZ_p** = {1, 2, 3, . . ., p-1}`

=Some Facts about Polynomials=

Given `P(x) = a_d x^d + a_(d-1) x^(d-1) + . . . + a_1 x^1 + a_0`. Let `P(x), Q(x)` be two polynomials.

The sum `P(x)+Q(x)` is also a polynomial. In other words, polynomials are "closed under addition."

Their product `P(x)Q(x)` is also a polynomial. In other words, polynomials are "closed under multiplication."

However, `P(x)`/`Q(x)` is not necessarily a polynomial.

Multiplying polynomials:

''Example'': `(x^2+2x-1)(3x^3+7x)`
:: `= 3x^5 + 7x^3 + 6x^4 + 14x^2 – 3x^3 – 7x`
:: `= 3x^5 + 6x^4 + 4x^3 + 14x^2 – 7x`

Evaluating polynomials:

''Examples'': Given `P(x) = 3x^4 – 7x^2 + 12x – 19`
::`P(5) = 3×5^4 – 7×5^2 + 12×5 – 19`
::`P(-1) = 3×(-1)^4 – 7×(-1)^2 + 12×(-1)- 19`
::`P(0) = -19`

Roots of a polynomial:

''Definition'': `r` is a "root" of `P(x)` if `P(r)` = 0.

''Examples'':

:`P(x) = 3x + 7`
::root = -(7/3).

:`P(x) = x^2 – 2x + 1`
::roots = 1, 1.

:`P(x) = 3x^3 -10x^2 + 10x – 2`
::roots = 1/3, 1, 2.

Linear Polynomials

`P(x) = ax + b`
e.g., `P(x) = 7x – 9` (over `ZZ_11`)

One root: `P(x) = ax + b = 0 => x = -b/a`
e.g., root = (- (-9)/7) = 9 * 7^{-1}
= 9 * 8 = 72
= 6 (mod 11).

Check: P(6) = 7*6 – 9 = 42 – 9 = 33 = 0 (mod 11)

The Single Most Important Fact About Low-degree Polynomials: A non-zero degree-`d` polynomial `P(x)` has at most `d` roots.

If you give me pairs `(x_1, y_1), . . . , (x_(d+1), y_(d+1))` then there is at most one degree-`d` polynomial `P(x)` such that `P(x_k) = y_k` for all `k`.

Why?

Assume `P(x)` and `Q(x)` have degree at most `d`. Suppose `x_1, x_2, . . . , x_(d+1)` are `d+1` points such that `P(x_k) = Q(x_k)` for all `k = 1,2, . . . ,d+1`. Then `P(x) = Q(x)` for all values of `x`.

Proof: Define `R(x) = P(x) – Q(x)`. `R(x)` has degree `d`. `R(x` has `d+1` roots, so it must be the zero polynomial.

Lagrange Interpolation

Given any `(d+1)` pairs `(x_1, y_1), (x_2, y_2), ... , (x_(d+1), y_(d+1))`, then there is exactly one degree-`d` polynomial `P(x)` such that `P(x_k) = y_k` for all `k`.

`k`-th "Switch" polynomial

Given `(d+1)` pairs `(x_1, y_1), (x_2, y_2), . . ., (x_(d+1), y_(d+1))`.
`g_k(x) = (x-x_1)(x-x_2). . .(x-x_(k-1))(x-x_(k+1)) . . . (x-x(d+1))
Degree of g_k(x) is `d`.
`g_k(x)` has `d` roots: `x~1,...,x_(k-1),x(k+1),. . .,x_(d+1)`
`g_k(x_k) = (x_k-x_1)(x_k-x_2)…(x_k-x_(k-1))(x_k-x_(k+1))...(x_k-x_(d+1))`
For all `i ≠ k, g_k(x_i) = 0`.

. . .

The Lagrange Polynomial

. . .

Example

Two different perspectives

`P(x) = a_d x^d + a_(d-1) x^(d-1) + ... + a_1 x^1 + a_0` can be represented by either

`d+1` coefficients: `a_d, a_(d-1), ..., a_2, a_1, a_0`

or

Its value at any `d+1` points: `P(x_1), P(x_2), ..., P(x_d), P(x_(d+1))

::For example, `P(0), P(1), P(2), ..., P(d+1).`

To convert between the two representations

Coefficients to Evaluation: Evaluate `P(x)` at `d+1` points.

Evaluation to Coefficients: Use Lagrange Interpolation.

How do the representations differ?

When adding two polynomials, both representations are equally good, since in both cases the new polynomial can be represented by the sum of the representations.

When multiplying two polynomials, the first requires `(d+1)^2` multiplications. The second representation just requires just `2d+1` multiplications (if the two polynomials are already evaluated at the same points).

When evaluating the polynomial at some point, it is easy with the first representation. It requires Lagrange interpolation with the second representation.

Error Detection

Note that the value-representation is tolerant of "erasures." Suppose that we want to send you a polynomial `P(x)` of degree `d` and your mailer corrupts our e-mails once in a while.

Suppose that I wanted to send you a message "hello." I could write it as "8 5 12 12 15" and, hence, as `8x^4 + 5x^3 + 12x^2 + 12x + 15`. I could evaluate `P(x)` at (say) `n > d+1` points and send `<k, P(k)>` to you for all `k = 1, 2,...,d, ...,n`. As long you get at least `(d+1)` of these, choose any `(d+1)` of the ones you got, and reconstruct `P(x)`.

But is it tolerant to "corruption"? For example, suppose `P(x) = 2x^2 + 1`, and I chose `n = 4`.I evaluated `P(0) = 1, P(1) = 3, P(2) = 9, P(3) = 19`. So I sent you `<0,1>, <1,3>, <2,9>, <3,19>`.But the corrupted e-mail says `<0,1>, <1,2>, <2, 9>, <3, 19>`. You choose `<0,1>, <1,2>, <2,9>` and get `Q(x) = `.

The above scheme does detect errors! If we send the value of degree-`d` polynomial `P(x)` at `n ≥ d+1` different points, `<x_1, P(x_1)>, <x_2, P(x_2)>, ... , <x_n, P(x_n)>`, then we can detect corruptions as long as there fewer than `(n-d)` of them. Why? If there are only `n-d-1` corruptions, then we have `d+1` correct points!

We also have error correction. As long as we have fewer than `(n-d)/2` corruptions, then we can get back the original polynomial `P(x)`. And we don’t need to know which ones are corrupted. We need to know just that there are fewer than `(n-d)/2` corruptions.

[Berlekamp-Welch decoding]

Secret Sharing

Polynomials are amazing in other ways as well. We can apply their remarkable properties to the problem of sharing secrets. [Adi Shamir]

A missile has a random secret number `S` encoded into its hardware. It will not arm without being given `S`. `n` officers have memorized a private, individual "share." Any `k` out of `n` of them should be able to assemble their shares so as to obtain `S`. Any `≤ k-1` of them should not be able to jointly determine ''any'' information about `S`.

Let `S` be a random "secret" from `ZZ_p`. We want to give shares `ZZ_1, ZZ_2, . . . , ZZ_n` to the `n` officers such that:

:(a) if we have `k` of the `ZZ_i`'s, then we can find out `S`.

:(b) if we have `k-1 ZZ_i`'s, then any secret `S` is equally likely to have produced this set of `ZZ_i`'s.

Here is how we can do it. Let `S` be a random "secret" from `ZZ_p`. Pick `k-1` random coefficients `R_1, R_2, ..., R_(k-1)` from `ZZ_p`. Let `P(x) = R_(k-1) x^(k-1) + R_(k-2) x^(k-2) + ... + R_1 x^1 + S`. For any `j` in `{1,2,...,n}`, officer `j`'s share is `ZZ_j = P(j)`.

`P(0)` = where `P` hits the `y`-axis = `S`. `P(x)` chosen to be a random degree `k-1` polynomial given that `f` hits the `y`-axis at `S`. Since `S` is random, each such polynomial is equally likely to be chosen.

If `k` officers get together, they can figure out `P(x)` and then evaluate `P(0) = S`.

If `k-1` officers get together, they know `P(x)` at `k-1` different points. For each value of `S`', we can get a unique polynomial `P`' passing through their points, and `P'(0) = S'`. And so each `S`' is equally likely.

Exercises

[TK]