Mashi 3la Raibi, 3la Jamila! 💓

Polynomials are functions of the form: $$ f(x) = a_0 + a_1 x + \dots + a_n x_n $$ where $n$ is any non-negative integer and $a_0,\dots,a_n$ any fixed numbers with $a_n \ne 0$. We call:

• $n$ the polynomial degree,
• $a_0,\dots,a_n$ the polynomial coefficients and
• $a_0$ the polynomial constant term.

Polynomial Interpolation

1. Suppose that $f(x)$ is a polynomial of degree 2, i.e. of the form $f(x) = a_0 + a_1 x + a_2 x^2$. Let $f(1)=2$, $f(2)=5$, and $f(4)=2$. Find $f(x)$.
2. Can you quickly write down a non-zero polynomial that vanishes at 1, 3 and 100?
3. Same problem as before, but now with the two extra conditions: $f$ must have degree $\leq 3$ and also $f(50)=1$.
4. Same problem as before, but now with the following conditions: $f$ must have degree $\leq 4$, $f(50)=1$ and $f(4)=3$.
5. Now suppose that we have $n+1$ points $(x_0,y_0), (x_1,y_1), \dots, (x_n,y_n)$ such that $f(x_i)=y_i$ for $0 \leq i \leq n$. Can you generalize the above approach to find $f(x)$?

Secret Sharing

Raibi Jamila, often referred to simply as “Raibi,” is a beloved yogurt-based drink that has become a staple in Moroccan culture. Many have tried to replicate the drink, but none have succeeded in capturing its unique flavor. The secret recipe for Raibi is known only to a few select individuals, who have sworn to keep it a secret. To prevent these individuals from sharing the secret and to ensure it is never lost, we are going to construct a scheme that allows the secret to be shared among a group of people in such a way that the secret cannot be revealed unless a minimum number of the group’s members act together to pool their knowledge.

6. Let $s$ be the secret recipe. We construct $f(x)$ a polynomial of degree $t$ such that $f(0)=s$ and $f(i)=a_i$ for $1 \leq i \leq t$, where $a_i$ are random numbers. We compute the points $y_1=f(1), y_2=f(2), \dots, y_n=f(n)$ where $n>t$ and distribute them among $n$ people. Can you explain how any $t+1$ people from $n$ people can reconstruct the secret $s$? Can any $t$ people do the same?
7. Let’s take the following example: $n=6$, $t=3$ and $y_1=13$, $y_2=29$, $y_3=61$ $y_4=115$, $y_5=197$ and $y_6=313$. What is the secret $s$?