In this lab we will introduce you to working with polynomials. In the following graph, we have in blue a degree 3 polynomial, interpolated from 4 points, A, B, C and D. The red dashed lines are the delta polynomials from the intermediate steps of interpolation after they are scaled by the y-coordinate of the point (one of A, B, C, D) it passes through. Play around with this visualization and answer the questions below.
Now I have a chosen a random secret \(-5 < s < 5\), and encoded it with a degree 3 real polynomial \(P(x)\) such that \(P(0) = s\). You have obtained 4 points on the polynomial, and wish to recover the secret.
The points given are , , , :
Compute the 4 delta polynomials that passes the 4 points given, then click "Plot" to plot them, as well as \( P(x) = y_1\Delta_{x_1} + y_2\Delta_{x_2} + y_3\Delta_{x_3} + y_4\Delta_{x_4} \), which should be a polynomial passing through all 4 points given. You can type in expressions such as \( (x + 10) * (x - 12) / (-3) \) into the text boxes.
Now read off the secret, which is the value of the polynomial at \(x = 0\).
Recall that when we want to share a secret using a polynomial of degree \(d\), we choose \(d\) other random points each with different \(x\) values and find a polynomial passing through these points and \((0, \text{secret})\). \(d+1\) points of the polynomial are then needed to recover the secret. In this question we investigate what happens when we do secret sharing over the reals, but we have one less point needed to recover the secret. Suppose that in this case besides the secrets, the other points at \( x=-4, -2, 2, 4 \) forming the polynomial are chosen randomly from -5 to 5, and you only have 3 points at \(x=-4, -2, 2 \) whereas 4 points are needed to reconstruct the polynomial.
In error-correcting codes, one usually encodes an original message in a polynomial (either in the coefficients, or by interpolation), and then sends over the values of that polynomial at several different points. If enough redundant information is sent, one can recover from errors.
Here you will have some exercise with decoding a corrupted message. We are going to work in the field of numbers modulo 11. The original message that was sent to us was a polynomial P(x) of degree at most 3. With such a polynomial one can encode 4 numbers; thus the length of the original message is 4. In order to be able to recover from one error, one has to send two more redundant values. So let's assume that [ P({{i}}) ] is sent as the message.
In order to decode and recover from the error, one has to introduce an error-locating polynomial E(x). This polynomial has degree 1 (the number of errors we can tolerate), and its highest term has coefficient 1. So we can write it as E(x) = x + b0. If b0 is chosen appropriately, then E(x) will have a root at exactly the error. Then we have to introduce a new polynomial Q(x) = E(x)P(x). This polynomial will be of degree at most 4 and thus we can write it as Q(x) = a{{i}}x{{i}} + a1x + a0.
Notice that for each x, and in particular for x = 1, 2, 3, 4, 5, 6, we have Q(x) = E(x)P(x). Now if we replace P(x) by the actual message received, this equation still holds. Because if x was not an error point, then the actual message received was just P(x), and if x was an error point, then E(x) would be zero, and so no matter what we place there, the equation holds because both sides are zero.
If we represent the message received by Rx for x = 1, 2, 3, 4, 5, 6, then our equations become Q(x) = E(x)Rx for x = 1, 2, 3, 4, 5, 6. These are linear equations in terms of b0 and a{{i}}{{i>0?', ':''}}.
Fortunately you do not have to solve these equations, we have written a solver for you. All you need to do is to write down what these equations are.
Now let us try to do this again, this time with a new message. We have already copied the linear equations you have provided in the first part here, for your convenience. As you can see most of the entries are still green here. You need to correct the entries that are not correct.
Why do you think most entries are green when you start?