拉格朗日插值法

对某个多项式函数，已知有给定的 $k+1$ 个取值点： $(x_0,y_0)\ldots(x_k,y_k)$ 。
假设任意两个不同的 $x_j$ 都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：

$\ell_0(x)=\frac{(x-x_1)(x-x_2)\cdots(x-x_k)}{(x_0-x_1)(x_0-x_2)\cdots(x_0-x_k)}y_0$

$\cdots$

$\ell_k(x)=\frac{(x-x_0)(x-x_1)\cdots(x-x_{k-1})}{(x_k-x_0)(x_k-x_1)\cdots(x_k-x_{k-1})}y_k$

$f(x)=\ell_0(x)+\ell_1(x)+\cdots+\ell_k(x)$

即可求出多项式。

已知 3 个点 $(4,10)(5,5.25)(6,1)$ 。

$\ell_0(x)=\frac{(x-5)(x-6)}{(4-5)(4-6)}\times 10$

$\ell_1(x)=\frac{(x-4)(x-6)}{(5-4)(5-6)}\times 5.25$

$\ell_2(x)=\frac{(x-4)(x-5)}{(6-4)(6-5)}\times 1$

$f(x)=\ell_0+\ell_1+\ell_2=\frac{1}{4}(x^2-28x+136)$

Shamir 秘密共享

生成