はじめに（Introduction）
閾値（しきいち：threshold）に使うので、ラグランジュ補間公式について記します。
ラグランジュ補間公式
$(n+1)\ $点$\ (x_0,y_0),\ldots ,(x_n,y_n)\ $（ただし、$x_k\ 0\le k\le n$は互いに異なる）が与えられたら、
$n$次関数は一意に定まり次の式で表す事ができる。
\begin{align*}
& \ell_k(x) := \prod_{\substack{j = 0 \\ j\ne k}}^{n}\frac{x-x_j}{x_k-x_j} \\
& L(x) := \sum_{k=0}^{n} y_k \ell_k(x)
\end{align*}
まとめて、一つの式にすると
\begin{align*}
L(x) := \sum_{k=0}^{n}\left(y_k \prod_{\substack{j=0 \\ j\ne k}}^{n}\frac{x-x_j}{x_k-x_j} \right)
\end{align*}
例
3点$(1,20),(2,22),(3,32)$から2次関数を求めてみます。
\begin{align*}
L(x)&=20\frac{(x-2)(x-3)}{(1-2)(1-3)}+22\frac{(x-1)(x-3)}{(2-1)(2-3)}+32\frac{(x-1)(x-2)}{(3-1)(3-2)} \\
&=20\frac{(x-2)(x-3)}{2}+22\frac{(x-1)(x-3)}{-1}+32\frac{(x-1)(x-2)}{2} \\
&=10(x-2)(x-3)-22(x-1)(x-3)+16(x-1)(x-2) \\
&=10(x^2-5x+6)-22(x^2-4x+3)+16(x^2-3x+2) \\
&=(10-22+16)x^2+(10\cdot-5+-22\cdot-4+16\cdot-3)x + 10\cdot6-22\cdot3+16\cdot2 \\
&=4x^2-10x+26
\end{align*}
直感的に
$x$が互いに異なる3点$(x_0,y_0),(x_1,y_1),(x_2,y_2)$から2次関数を求める式をみてみます。
\begin{align*}
L(x)&=y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \\
\end{align*}
最初の項$\ y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$をみると、$x_0$を$x$に代入すると、分母と分子が同じになり$y_0$だけが残ります。また、$x_1,x_2$を代入すると分子が$0$となりこの項は$0$となります。
他の項も同じになるので、3点を満たす（通る）関数を導く事ができます。
$x$は互いに異なるので、分母が$0$になることはありません。
証明
式が求められることは直感的にわかりましたが一意に定まることが必要です。
因数定理
多項式$f(x)$が$(x-a)$を因数にもつ$\iff f(a)=0$
因数定理の証明
多項式$f(x)$を$(x-a)$で割った商を$g(x)$、あまりを$r$としたとき、$f(x)=(x-a)g(x)+r$となります。
$x$に$a$を代入すると、$f(a)=r$となり、$f(x)$が$(x-a)\ $を因数（$\ f(x)=(x-a)g(x)\ $）にもつ場合$\ r=0$が必要十分条件となります。
一意の証明
$(n+1)\ $点$\ (x_0,y_0),\ldots ,(x_n,y_n)\ $（ただし、$x_k\ 0\le k\le n$は互いに異なる）
を満たす（通る）$n$次式の関数$f(x),g(x)$を考えます。
$h(x)=f(x)-g(x)$とすると、$h(x_k)=0\ (0\le k\le n)$となります。
したがって、因数定理より$\ f(x)-g(x)=a(x-x_0)\cdots (x-x_n)\ $となります。
（各点は、$f(x)-g(x)$の因数となるためです。）
$(x-x_0)\cdots (x-x_n)\ $は$(n+1)$次関数となるなるので、$a=0$でなければなりません。
したがって、$f(x)-g(x)=0$となり、$f(x)=g(x)$となります。
これにより、一意となることがわかります。
さいごに
直感的にわかりやすい公式だと思います。
これを使って、閾値（しきいち）署名に適用していこうと思います。