Description

1 Polynomial Practice
(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) We say a polynomial f = 0 if ∀x, f(x)= 0. If f ·g = 0, is it true that either f = 0 or g = 0?
(ii) 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 Rational Root Theorem
The rational root theorem states that for a polynomial
P(x)= anxn+an−1xn−1 +···+a0,
a0,··· ,an ∈ Z, if a0,an 6= 0, then for each rational solution qp such that gcd(p,q)= 1, p|a0 and q|an. Prove the rational root theorem.
3 Secret Sharing Practice
Consider the following secret sharing schemes and solve for asked variables.
(a) Suppose there is a bag of candy locked with a passcode between 0 and an integer n. Create a scheme for 5 trick-or-treaters such that they can only open the bag of candy if 3 of them agree to open it.
(b) Create a scheme for the following situation: There are 4 cats and 3 dogs in the neighborhood, and you want them to only be able to get the treats if the majority of the animals of each type are hungry. The treats are locked by a passcode between 0 and an integer n.
4 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 could he achieve this? In other words, what value should he report in order to make the others believe that the secret is s0?