commit b0fe4c9f0f85842f494701e1b0221f180a8fd0ad
parent 10dc813e1ad0c6f1e0dbe28c3745883c41a8d006
Author: oscarbenedito <oscar@obenedito.org>
Date: Sat, 29 Feb 2020 18:07:44 +0100
Corrections
Diffstat:
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/content/blog/2020-02-23-sharing-a-secret.pdc b/content/blog/2020-02-23-sharing-a-secret.pdc
@@ -29,7 +29,7 @@ where $a_i$ are random numbers, $\forall i \in \{1, \dots, k-1\}$. Now we'll eva
If we want to recover the secret from $k$ shares, we can interpolate the $k$ points $(x_i, p(x_i))$ using [Lagrange's form for the interpolation polynomial](https://en.wikipedia.org/wiki/Lagrange_polynomial)[^proof]:
-[^proof]: Let's quickly proof that the $p$ defined in Lagrange's form ($\bar{p}$ from now on) is the same as the previously defined $p$. $\bar{p}$ is clearly a polynomial of degree (at most) $k-1$, since it is the sum of polynomials of degree $k-1$, so we only need to proof that it interpolates the points given (we'll asume that the fact that there is only one polynomial of degree at most $k-1$ that interpolates $k$ points is true). That is easy to proof since $i \neq j \implies l_i(x_j) = 0$ and $l_i(x_i) = 1$, therefore having $\bar{p}(x_i) = p(x_i) l_i(x_i) = p(x_i)$.
+[^proof]: Let's quickly prove that the $p$ defined in Lagrange's form ($\bar{p}$ from now on) is the same as the previously defined $p$. $\bar{p}$ is clearly a polynomial of degree (at most) $k-1$, since it is the sum of polynomials of degree $k-1$, so we only need to prove that it interpolates the points given (we'll asume that the fact that there is only one polynomial of degree at most $k-1$ that interpolates $k$ points is true). That is easy to prove since $i \neq j \implies l_i(x_j) = 0$ and $l_i(x_i) = 1$, therefore having $\bar{p}(x_i) = p(x_i) l_i(x_i) = p(x_i)$.
<div class="mathjax-container">
$$p(x) = \sum_{i=1}^{k} p(x_i) l_i(x),$$
