Source: https://rareskills.io/zh-cn/post/python-lagrange-interpolation
Lagrange 插值是一种计算穿过一组 n 个点的多项式的技术。
<aside> 💡 💡 一句话理解：插值就是『连点成线』。给你几个散落的点，找一条平滑曲线（多项式）正好穿过它们全部。就像在坐标纸上点了几个图钉，再用一根有弹性的尺子把它们顺滑地串起来。后面会看到，这条曲线的具体长相（系数）由这些点唯一决定。
</aside>
设想如果我们有两个点，可以通过一条直线对它们进行插值。例如，给定 $(1, 1)$ 和 $(2, 2)$ ，我们可以画一条穿过这两个点的直线，它将是一个次数为 $1$ 的多项式 $y = x$ 。
现在设想如果我们只有一个点，我们可以用一个次数为 0 的多项式画一条穿过该点的直线。例如，如果这个点是 $(3, 5)$ ，我们可以画一条穿过它的直线 $y = 5$ （这是一个次数为 $0$ 的多项式）。
我们可以用一个（最高）次数为 $n - 1$ 的多项式“画一个多项式穿过” $n$ 个点的规律适用于任何数量的点。例如，点 $(0, 0), (1, 1), (2, 4)$ 可以用 $y = x^2$ 进行插值。如果这些点恰好在一条直线上，例如 $(0, 0), (1, 1), (2, 2)$ ，那么我们可以用次数为 1 的多项式 $y = x$ 画一条穿过 $(1, 1)$ 和 $(2, 2)$ 的直线，但通常情况下，三个点不会共线，因此我们需要一个次数为 2 的多项式来穿过所有点。
<aside> 💡 💡 为什么是 $n-1$ 次：因为一个 $n-1$ 次多项式恰好有 $n$ 个可调的旋钮（系数），刚好够用来满足 $n$ 个点的要求——不多不少。$2$ 个点定一条直线（$1$ 次，$2$ 个旋钮）；$3$ 个点定一条抛物线（$2$ 次，$3$ 个旋钮）。点越多，曲线就能拐越多的弯。
</aside>
就我们的目的而言，了解如何计算这个多项式并不重要，因为有数学库可以替我们完成计算。最常用的算法是 Lagrange 插值 ，下面我们将展示如何在 Python 中实现它。
我们可以使用 Lagrange 插值计算一个穿过点 $(1,4), (2,8), (3,2), (4,1)$ 的多项式 $p(x)$ 。
from scipy.interpolate import lagrange
x_values = [1, 2, 3, 4]
y_values = [4, 8, 2, 1]
print(lagrange(x_values, y_values))
# 3 2
# 2.5 x - 20 x + 46.5 x - 25
让我们使用与之前相同的多项式，但这次我们将使用有限域 $\mathbb{F}_{17}$ 而不是浮点数。
<aside> 💡 💡 这里最绕的是『有限域』：把所有运算都改成『钟表算术』。普通时钟到 $12$ 就绕回 $1$；这里是到 $17$ 就绕回 $0$，也就是任何数都先除以 $17$ 取余数。比如 $20$ 在 $\mathbb{F}_{17}$ 里就是 $3$（$20-17$）。神奇的是，插值这套连点成曲线的玩法，在这种『绕圈数字』里照样成立，而且密码学正需要这种没有小数、不会越算越大的整洁世界。
</aside>