Question

4 Error-Correcting Polynomials (a) Alice has a length 8 message to Bob. There are 2 communication channels available. When n packets are fed through channel A, the channel will only deliver 5 packets (picked at random). Similarity, channel B will only deliver 5 packets (picked at random), but it will also corrupt (change the value) of one of the delivered packets. All channels can only work if at least 10 packets are sent through it. Using the 2 channels, how can Alice send the message to Bob? (b) Alice wishes to send a message to Bob as the coefficients of a degree 2 polynomial P. For a message [mi,m2,m3], she creates polynomial P- mix^ m2x +m3 and sends 5 packets: (0,P(0)), (1,P(1)), (2,P(2)), (3, P(3)), (4, P(4). However, Eve interferes and changes one of the values of a packet before it reaches Bob. If Bob receives and knows Alice's encoding scheme and that Eve changed one of the packets, can he still figure out what the original message was? If so find it as well as the x-value of the packet that Eve changed, if not, explain why he can not. (Work in mod 1 l.) (c) Alice decides that putting the message as the coefficients of a polynomial is too inefficient for long messages because the degree of the polvnomial grows quite large. Instead, she

Answer 1

($m_{1}$, $m_{2}$, $m_{3}$) = (3, -6, 3)

Explanation:

Given data,

$p=m_{1} x^{2}+m_{2} x+m_{3}$

5 packets are delivered by channel, which was randomly taken.

0(P(0)), 1(P(1)), 2(P(2)), 3(P(3)), 4(P(4))

Bob receives are

(0,3) (1,0) (2,3) (3,0) (4,3)

P(0) = 3

P(1) = 0

P(2) = 3

P(3) = 0

P(4) = 3

The given equation is

$p=m_{1} x^{2}+m_{2} x+m_{3}$

Solution:

$p(0)=m_{1}(0)+m_{2}(0)+m_{3}$ = 3

$m_{3}$ = 3

$p(1)=m_{1}+m_{2}+m_{3}=0$

$m_{1} + m_{2}$ = - 3

$m_{2} = -3 -m_{1}$

$p(2)=4 m_{1}+2 m_{2}+m_{3}$ = 3

$4 m_{1}+2 m_{2}$ = 0

$2 m_{1}+m_{2}=0$

$P(3)=9 m_{1}+3 m_{2}+m_{3}$  = 0

$3 m_{1}+m_{2}+3=0$

$P(4)=16 m_{1}+4 m_{2}+m_{3}$ = 3

$4 m_{1}+m_{2}$ = 0

From P(1) and P(2)

$m_{2} = -3 -m_{1}$

$2 m_{1}+m_{2}=0$

$2 m_{1}-3-m_{1}=0$

-3 + $m_{1}$  = 0

$m_{1}$ = 3

$m_{2}$ = -6

($m_{1}$, $m_{2}$, $m_{3}$) = (3, -6, 3)