CS70-Homework 6 Solved

(a)    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.)

(i)         f +g

(ii)       f ·g

(iii)      f/g, assuming that f/g is a polynomial

(b)   Now let f and g be polynomials over GF(p).

(i)         If f ·g = 0, is it true that either f = 0 or g = 0?

(ii)       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,...,p−1}.

(iii)      How many f of degree exactly d < p are there such that f(0)= a for some fixed a ∈ {0,1,...,p−1}?

(c)    Find a polynomial f over GF(5) that satisfies f(0)= 1, f(2)= 2, f(4)= 0. How many such polynomials are there?

2        The CRT and Lagrange Interpolation
Let n1,...nk be pairwise coprime, i.e. ni and nj are coprime for all i 6= j. The Chinese Remainder Theorem (CRT) tells us that there exist solutions to the following system of congruences:

x ≡ a1 (mod n1)
(1)
x ≡ a2 (mod n2)
(2)
...
.

(..)
x ≡ ak (mod nk)
(k)
and all solutions are equivalent (mod n1n2 ···nk). 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.

(a)    We start by proving the k = 2 case: Prove that we can always find an integer x1 that solves (1) and (2) with a1 = 1,a2 = 0. Similarly, prove that we can always find an integer x2 that solves (1) and (2) with a1 = 0,a2 = 1.

(b)   Use part (a) to prove that we can always find at least one solution to (1) and (2) for any a1,a2. Furthermore, prove that all possible solutions are equivalent (mod n1n2).

(c)    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 n1n2 ···nk).

(d)   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 (x−1).

(e)    Define the polynomials x−a and x−b to be coprime if they have no common divisor of degree 1. Assuming that the CRT still holds when replacing x,ai and ni with polynomials (using the definition of coprime polynomials just given), show that the system of congruences

p(x) ≡ y1 (mod (x−x1))   (1’) p(x) ≡ y2 (mod (x−x2))    (2’)

                                                                                  ...                                                                (...)

                                                                               p(x) ≡ yk (mod (x−xk))                                          (k’)

has a unique solution (mod (x−x1)···(x−xk)) whenever the xi 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 Bob1,...,Bobn+1. As usual, she chose p such that p(0)= s. Bob1 through Bobn+1 now gather to jointly discover the secret. Suppose that for some reason Bob1 already knows s, and wants to play a joke on Bob2,...,Bobn+1, making them believe that the secret is in fact some fixed s0 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, m0,m1,m2, 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:

A
B
C
D
E
F
G
H
I
J
K
0
1
2
3
4
5
6
7
8
9
10
Hector encodes the message by finding the degree ≤ 2 polynomial P(x) that passes through (0,m0), (1,m1), and (2,m2), 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 = r0,r1,r2,r3,r4

which could have up to 1 error.

(a)    First, let’s 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)= riE(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.

(b)   Solve for Q(x) and E(x). Where is the error located?

(c)    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

(I)      tell that there are no errors and decode the message, or

(II)     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.