椭圆曲线深入解析（第二部分）

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～

上一次，我们定义了椭圆曲线是什么，并 devised 了一种（可疑复杂的）方法来将曲线上的点相加。我们也暗示了这种操作对密码学应用的重要性。

然而，定义在实数上的曲线并不是我们所追求的构造。

密码学是一门离散精度的学科。我们希望算法能够产生一致、可重复的结果。换句话说，我们追求的是确定性，这粗略地说意味着使用相同的输入应该得到相同的输出，无论是什么情况。

在这个意义上，处理实数是相当麻烦的，因为我们通常使用浮点运算，因此总是存在舍入误差，使得操作不精确。

由于舍入误差，添加 P ⨁ Q 的结果甚至可能完全不落在曲线上（在实数上工作时）。

这需要采取不同的策略。

这将是我们今天的起点！我们将先进行一个小小的绕路，然后直接回到椭圆曲线上。

合适的领域

与实数相对，整数在操作上非常精确。因为没有小数，所以舍入误差似乎不再是问题！

尽管这对加法、减法和乘法是正确的，但看起来除法可能会有一些问题：1 除以 3 显然不会得到一个整数，我们又回到了浮点运算的领域。

我们还需要问自己，我们可以允许我们的整数有多大。毕竟，我们需要以某种方式表示它们——而当试图在计算机中存储和处理它们时，允许它们变得过大是有问题的。

所以是的，整数——更具体地说，正整数——但我们还差一步。我们需要一种方法来保持我们的值在控制范围内（有界的），同时还要弄清楚如何处理除法。

模运算

为了弥补这一点，我们将使用一个简单的工具：模运算 和模运算。

我在以前的文章中谈过这些内容，所以我假设你对此概念是熟悉的。

通过使用模运算来约束加法、减法和乘法运算的结果，我们基本上将可以操作的可能整数限制在一个有限的集合中，比如这个：

我们在这里使用符号 𝔽，因为生成的集合将是一个域（因此是 𝔽）。域只是一个加法、减法、乘法和除法都被定义良好的集合。

这样一个问题解决了（有界性）。现在我们的域是一个有限的集合，我们称之为有限域。

除法需要更多的工作——还有一个聪明的观察。

另一种视角

以5 mod 3为例。显然，结果是2。我们是如何得到这个结果的？

我们可以更严格地描述这个过程为找到这个方程的解：

并且要求 x 的值在 0 和 4 之间（𝔽₅ 的一个元素）。这将得到 k = 1 和 x = 2。

然而，很明显，其他的解是存在的。例如，k = 2 和 x = -1。正如你现在可能猜到的，我们可以找到无穷多个整数解。

实际上，所有可能的 x 的值的集合形成了一个等价类。

好的……我们为什么要关心这件事呢？结果发现，通过这样的方式来看，有什么我们可以做的关于除法的事情！

如果我们仔细想一下，某些除法 1 / a 的结果无非是一个其他的数字，满足某个特定的属性。例如，1 / 2 的结果是 0.5，而 1 / 3 的结果是 0.333(…)。这些结果都分享这个属性：

因此，与其把它看作是除法，我们不如把它看作是找到倒数数字。我们问自己：

给定我们域中的某个数字，我们能否找到另一个数字（也在该域中），使得当我们将它们相乘时，结果是1？

换句话说，我们在找这个方程的解：

而——你大概猜到了——可以转换成这个形式：

我们又回到了之前的场景！如果我们有权找到一个有效的 x 值，我们称它为 a 的模逆，并将其写作 a⁻¹。

太棒了

这一形式被称为贝祖恒等式，而我们当然只关心 x 和 k 的整数解（这是一个线性丢番图方程）。

重要的是，一种解可能并不存在。不计零，一个整数 a 的模逆存在的条件是它与域大小 p 是互质的，意味着它们没有共享任何因子——或者说它们的最大公约数（GCD）是1。

我们可以很快证明这一点。假设 a 和 p 共享某个因子 t，意味着 a = t.a' 和 p = t.p'。然后，我们可以将 t 提出来，上面的方程将变成：

无论我们使用的x 和 k 值是什么，左边的结果永远不会是1，这意味着方程将没有解。因此，如果 a 和 p 共享因子，则模逆不存在。

有一个非常简单的解决方法：选择一个质数作为 p！根据定义，任何质数只有两个因子：1和其本身——这意味着，只要有限域的大小是质数，那么它的所有元素（不包括零）都将具有模逆。

好吧，事实上，根据定义，0 的倒数是 0。

太神奇了！这意味着每个元素的除法在这个集合中是被定义的——的确是一个域。

回到椭圆曲线

有限域中元素之间的运算产生确定和定义良好的结果，这正是我们所想要的！

现在我们所需要做的就是在这些集合上定义我们的椭圆曲线，而不是在实数上。这里的算法并没有太复杂——我们在之前的讨论中已经导出了点加法和点倍的显式公式。我们唯一要做的调整是将除法替换为乘以模逆。

例如，点倍通过执行以下计算来完成：

所以，是的，没什么花哨的——除了所有这些结果都是以模 p 计算。我们也知道它们是我们有限域中的元素——这意味着生成的 R 将具有整数坐标。

这里有一个需要注意的细微之处。当我们在实数中分析情况时，我们可以保证找到第三个交点。现在不太明显的是这是否可以直接翻译到有限域设置中。幸运的是，加法和倍运算在有限域上同样表现良好！

因此，当在有限域上定义时，椭圆曲线看起来不会像“曲线”。相反，它们更像是一组被限制在边长为 p 的平方内的点，这样：

曲线 y² = x³ + x + 6 mod 7，以蓝色显示。你可以在这里尝试不同的曲线。

当然，不包括无穷远处的点！

仅仅通过观察这张图并不明显在曲线上相加任何两个点的结果是什么。然而，和以前的方程无论我们现在所用的集合如何，切线和割线规则是通过我们已经推导出的方程定义的。只不过视觉效果现在不太有帮助：

是吧……不。

如你所见，当线到达我们平方域的边界时，它们被割断——这很有意义，因为这些线也以 p 为模被定义。

现在一切都以 p 为模定义！

考虑这种更自然的方式，注意到左边和右边的边在模 p下是等价的（7 mod 7 = 0），因此如果我们能够弯曲我们的平方到三维空间，我们可以粘贴那些边缘，得到一个三维圆柱面。让我们探讨一下，只是为了好玩。

顶部和底部边界同样可以做到。这需要一些想象力，但就好像我们的椭圆曲线实际上是在饼状领域中定义的——一个环面。在这个空间中，线条将有效地是连续的！这里有一个很好的视频来帮助你想象正在发生的事情。

对于那些研究过拓扑的人来说，这将非常像商拓扑！

我们不需要关心这些变换，但努力推动我们的理解进一步发展总是一个很好的练习，因为它可能帮助我们获得新的见解。

说到这里——我们还有一个特别棘手的点到目前为止我们没有很优雅地处理：无穷远点。它感觉有点勉强——我们似乎不能把它放在任何地方。在我们小小的弯曲和饼干练习之后，让我们看看我们是否能找到一个将它放在某处的方法。

投影坐标

由于我们的曲线定义在 ℝ² 或 𝔽ₚ² 上，这并不疯狂我们将椭圆曲线想象为平面上的点（或者在我们刚刚检查的情况下的变形平面）。

这称为仿射空间（连同无穷远点），有时表示为 𝔸²。

这里有一个相当不寻常的问题：我们可以放置这个平面在哪里？我的意思是，一个平面只不过是一个平面——我们代表事物的抽象画布。试图将它放置在某个地方有意义吗？

事实上，是的！而且第一步是向上移动一个维度。

在三维空间中，一个平面实际上是由一个线性方程定义的：

我们可以在三维中表示出无数不同的平面。现在“放置”一个平面在某处确实有意义——我们所需要做的只是选择三维空间中无数的平面之一。

我们实际上不需要任何花哨的东西。我们可以选择位于 z = 1 的水平（x-y）平面。想象一下我们在这个平面上画我们的椭圆曲线。

这里变得有趣的是：对于曲线上的每个点 P=(x,y)，如果我们画一条通过原点 (0,0,0) 和 (x,y,1) 的直线，那么该直线将恰好在 z=1 的平面上相交于一个点：P。所以这些直线和它们本身是等价的！

通过原点穿过的直线在 z=1 平面上每条直线的单一交点。

这被称为投影空间，表示为 ℙ²。为了使事情更清楚，让我们把这些三维空间中的点表示为 (X,Y,Z)。

现在，任何这些直线上的点保持比率 X:Y:Z。也就是说，如果我们检查由 P=(x,y,1) 定义的直线，那么点 (2x,2y,2) 将同样在这条直线上，点 (3x, 3y, 3) 也是，或者通常说，任何类型的形态 (tx, ty, t)。这通常通过不等式 (X:Y:Z) 表示，以反映这种比率的概念。

因为我们选择了 z = 1，我们可以通过以下公式恢复原始的 x 和 y 值：

这些表达式可以代入我们椭圆曲线方程中，得到这个表达式：

去掉分母后得到：

让我们休息一下。我必须承认：这感觉像是不必要的复杂性。

但有时，这些看似不必要的复杂性往往能揭示出让我们的生活变得更容易的新见解。

有一个很好的视频完美地说明了这个想法。它与椭圆曲线的关系不大，但我觉得它真是太惊人了！

经过仔细的观察，确实发生了一些神奇的事情。

你看，曲线上每一个位于 z = 1 平面上的点都具有(X,Y,1)的形式。然而，“曲线上的点”实际上是满足方程 e 的任何点。没有什么实质性的理由限制我们只能在这里的平面进行工作。

然而，我们正通过这些投影坐标进行操作——每条以原点开始的直线都是一个等价类。在这种情况下恰好存在另一个满足方程的点：点 (0,1,0)。你可以自己检查一下——这好像正在奏效！

这条线完全平行于平面 z = 1——所以从不与之相交。它满足该方程，但在我们的仿射空间（平面）中却没有代表点。

听起来耳熟吗？

猜猜看——这就是我们所寻找的无穷远点，但我们现在实际上可以表示它！显示这个事实需要一些努力。然而，为了不使事情变得过于复杂，我们将避免深入探讨这条路径。

有用性

投影坐标为无穷远点提供了这种新视角。自然地，我们可能会想知道那是否是它们唯一的用途，或者这仅仅是一个极其人为的产物，用以获得一些额外的理解。

事实上，投影坐标相当有用！当我们计算点加法和乘法的公式时，发生了一些有趣的事情：我们能够避免一些模逆！

这又有什么好处呢……？

模逆的计算是相当昂贵的。计算它们的标准算法是扩展欧几里得算法。

我们在这里将不覆盖这部分以简洁起见，但你可以在这里了解它是如何工作的。

可以肯定的是，这要比简单的乘法努力得多。因此，使用投影坐标将导致更快速的椭圆曲线操作！

在密码学中，我们需要进行数千或数百万次这样的运算，任何一点都有意义。

总结

今天我们已经覆盖了相当多的内容！我们从实数转到有限域，看到我们的曲线在这个新环境中的变化，甚至找到一种合适的方式来表示我们的无穷远点。

当然，这远非故事的结束。

我们还没有讨论为什么椭圆曲线在密码学中是有用的。但是现在，既然我们在这种有界环境中工作，确实发生了一些显著的事情：椭圆曲线表现得像群。这为它们赋予了密码学的超能力。

下次，我们将探讨这种群结构，看看它为什么有用，并最终到达椭圆曲线在现代密码学中如此重要工具的核心。

等到那时见！