• Polynomial Practice
• If f and g are non-zero real polynomials, how many roots do the following polynomials have at least? How many can they have at most? (Your answer may depend on the degrees of f and g.)
  • f +g
  • f g
  • f/g, assuming that f/g is a polynomial
• Now let f and g be polynomials over GF(p).
  • If f g = 0, is it true that either f = 0 or g = 0?
  • If deg f p, show that there exists a polynomial h with degh < p such that f(x)= h(x) for all x {0,1,,p1}.
  • How many f of degree exactly d < p are there such that f(0)= a for some fixed a {0,1,,p1}?
• Find a polynomial f over GF(5) that satisfies f(0)= 1, f(2)= 2, f(4)= How many such polynomials are there?

2 The CRT and Lagrange Interpolation

Let n₁,n_k be pairwise coprime, i.e. n_i and n_j are coprime for all i 6= j. The Chinese Remainder Theorem (CRT) tells us that there exist solutions to the following system of congruences:

and all solutions are equivalent (mod n₁n₂ n_k). For this problem, parts (a)-(c) will walk us through a proof of the Chinese Remainder Theorem. We will then use the CRT to revisit Lagrange interpolation.

• We start by proving the k = 2 case: Prove that we can always find an integer x₁ that solves (1) and (2) with a₁ = 1,a₂ = Similarly, prove that we can always find an integer x₂ that solves (1) and (2) with a₁ = 0,a₂ = 1.
• Use part (a) to prove that we can always find at least one solution to (1) and (2) for any a₁,a₂. Furthermore, prove that all possible solutions are equivalent (mod n₁n₂).
• Now we can tackle the case of arbitrary k: Use part (b) to prove that there exists a solution x to (1)-(k) and that this solution is unique (mod n₁n₂ n_k).
• For two polynomials p(x) and q(x), mimic the definition of a mod b for integers to define p(x) mod q(x). Use your definition to find p(x) mod (x1).
• Define the polynomials xa and xb to be coprime if they have no common divisor of degree 1. Assuming that the CRT still holds when replacing x,a_i and n_i with polynomials (using the definition of coprime polynomials just given), show that the system of congruences

p(x) y₁ (mod (xx₁)) (1) p(x) y₂ (mod (xx₂)) (2)

()

p(x) y_k (mod (xx_k)) (k)

has a unique solution (mod (xx₁)(xx_k)) whenever the x_i are pairwise distinct. What is the connection to Lagrange interpolation?

3 Old secrets, new secrets

In order to share a secret number s, Alice distributed the values (1,p(1)),(2,p(2)),,(n+1,p(n+1)) of a degree n polynomial p with her friends Bob₁,,Bob_n+1. As usual, she chose p such that p(0)= s. Bob₁ through Bob_n+1 now gather to jointly discover the secret. Suppose that for some reason Bob₁ already knows s, and wants to play a joke on Bob₂,,Bob_n+1, making them believe that the secret is in fact some fixed s⁰ 6= s. How can he achieve this?

4 Berlekamp-Welch for General Errors

Suppose that Hector wants to send you a length n = 3 message, m₀,m₁,m₂, with the possibility for k = 1 error. For all parts of this problem, we will work mod 11, so we can encode 11 letters as shown below:

Hector encodes the message by finding the degree 2 polynomial P(x) that passes through (0,m₀), (1,m₁), and (2,m₂), and then sends you the five packets P(0),P(1),P(2),P(3),P(4) over a noisy channel. The message you receive is

DHACK 3,7,0,2,10 = r₀,r₁,r₂,r₃,r₄

which could have up to 1 error.

• First, lets locate the error, using an error-locating polynomial E(x). Let Q(x) = P(x)E(x).

Recall that

Q(i)= P(i)E(i)= r_iE(i), for 0 i < n+2k.

What is the degree of E(x)? What is the degree of Q(x)? Using the relation above, write out the form of E(x) and Q(x) in terms of the unknown coefficients, and then a system of equations to find both these polynomials.

• Solve for Q(x) and E(x). Where is the error located?
• Finally, what is P(x)? Use P(x) to determine the original message that Hector wanted to send.

5 Error-Detecting Codes

Suppose Alice wants to transmit a message of n symbols, so that Bob is able to detect rather than correct any errors that have occured on the way. That is, Alice wants to find an encoding so that

Bob, upon receiving the code, is able to either

• tell that there are no errors and decode the message, or
• realize that the transmitted code contains at least one error, and throw away the message.

Assuming that we are guaranteed a maximum of k errors, how should Alice extend her message (i.e. by how many symbols should she extend the message, and how should she choose these symbols)? You may assume that we work in GF(p) for very large prime p. Show that your scheme works, and that adding any lesser number of symbols is not good enough.