如果两个群之间存在保结构映射 (structure preserving map)，那么这两个群之间就存在同态。

假设我们有两个代数数据结构 $(A,\square)$ 和 $(B, \blacksquare)$，其中 $A$ 的二元运算符是 $\square$，$B$ 的二元运算符是 $\blacksquare$。

从 $A$ 到 $B$ 的同态存在，当且仅当存在一个函数 $\phi: A\rightarrow B$，使得：

换句话说，如果 $a_i \square a_j = a_k$，那么 $\phi(a_i) \blacksquare \phi(a_j) = \phi(a_k)$。

请注意，同态是单向的。函数 $\phi$ 接受 $A$ 中的元素并将其映射到 $B$ 中的元素。我们对“反向映射”没有任何要求。

我们将首先展示一些简单的示例，进行一些澄清说明，然后提供更复杂的示例。

同态的简单示例

加法运算下的所有整数到加法运算下的所有偶数

设 $A$ 为加法运算下的所有整数的集合，设 $B$ 为加法运算下的所有偶数的集合。很明显，$A$ 和 $B$ 都是群。

设 $\phi(x)=2x$

我们看到 $\phi$ 定义了从 $A$ 到 $B$ 的同态，因为对于任意一对整数 $a_i$ 和 $a_j$，以下等式均成立：

拼接运算下的所有字符串到加法运算下的非负整数

例如，设 $A$ 是在拼接运算下的所有字符串（包括空字符串）构成的幺半群，设 $B$ 是在加法运算下的所有非负整数构成的幺半群。

从 $A$ 到 $B$ 存在同态，因为存在一个函数 $\phi$，它将字符串映射为非负整数并保持以下性质：

在这种情况下，$\phi$ 是字符串的长度。例如：

在这里，我们有：

加法运算下的所有实数到加法运算下的所有 $n\times m$ 实数矩阵

一旦你掌握了诀窍，有些同态可能看起来相当平淡无奇。这就是这种同态的一个例子。在这种情况下，我们的函数 $\phi$ 只是将实数重复 $n\times m$ 次。例如，如果 $n=3$ 且 $m=2$，那么 $\phi(8.8)$ 将会是：

举个例子，$\phi(8.8 + 0.2)=\phi(8.8)+\phi(0.2)$，这是因为：

关于同态的澄清

• $\phi$ 必须适用于 $A$ 中的每一对可能的元素（包括相同元素的配对）。然而，它不需要“访问” $B$ 中的所有元素。例如，将 $A$ 中的每个元素映射到 $B$ 中单位元上的同态是一个有效的同态，但并非一个有用的同态。它被称为平凡同态。
• 如果我们任意选择两个带有二元运算符的集合，它们之间不一定存在同态。
• 可能存在从 $A$ 到 $B$ 的同态，但未必存在从 $B$ 到 $A$ 的同态。
• 如果存在从 $A$ 到 $B$ 的同态，也存在从 $B$ 到 $A$ 的同态，并且 $\phi$ 是从 $A$ 到 $B$ 的映射，那么 $\phi$ 的逆映射不一定是实现从 $B$ 到 $A$ 的同态的有效映射。

更多同态的示例

加法运算下的整数到乘法运算下 $b$ 的整数次幂

假设我们有群 $A=(\mathbb{Z},+)$（加法运算下的所有整数集合）和群 $B$，$B$ 是乘法运算下 $b$ 的所有整数次幂的集合，即 $B=(b^i\space:\space i\in\mathbb{Z}, \times)$。我们可以任意地设 $b=2$，以便更容易地思考这个例子。

从 $A$ 到 $B$ 存在一个同态，由 $\phi(x)=b^x$ 定义。根据代数规则：

要理解为什么这种关系成立，请考虑：

加法运算下的整数到质数取模乘法运算下 $b$ 的整数次幂

这与上面的例子非常相似，只是增加了一个模数运算。我们将“找出定义该同态的函数 $\phi$”作为练习留给读者。

加法运算下的 $n\times m$ 矩阵到加法运算下的整数

在这种情况下，$\phi$ 只是将矩阵中的所有元素相加。至于为什么这样成立，也留给读者作为练习。

乘法运算下的 $2\times2$ 整数矩阵到乘法运算下的整数

从第一个幺半群到第二个幺半群之间存在同态，因为 $\phi$ 是矩阵的行列式，并且以下规则成立：

其中 $X,Y,Z$ 是 $2\times2$ 的整数矩阵。为什么这两个代数数据结构是幺半群而不是群，留给读者作为练习。

有理数群（不包括分母为 $p$ 的倍数的有理数）到模 $p$ 加法群

这个概念已经在我们关于 finite fields 的文章中讲授过了，但当时我们并没有使用“同态”这个词来描述它。

设 $A$ 为在加法运算下分母不为 $p$ 的倍数的所有有理数构成的群。设 $B$ 为模 $p$ 的有限域。

从群 $A$ 到群 $B$ 存在一个同态。$\phi$ 是：

或者在 Python 中：

Copy
p = 11
def phi(num, den):
    return num * pow(den, -1, p) % p

例如：

• $1/3 + 3/5 = 14/15$
• $1/3$ 同余于 $6 \pmod {17}$
• $3/5$ 同余于 $4 \pmod {17}$
• $4 + 6\equiv10 \pmod {17}$
• $14/15\equiv 10 \pmod {17}$

说 $1/3$ 同余于 $6 \pmod {17}$，等同于声明 $\phi(1/3)=6$。

有理数幺半群（不包括分母为 $p$ 的倍数的有理数）到模 $p$ 乘法群（不包括零）

让我们使用与上面相同的示例，但改为乘法。函数 $\phi$ 保持不变。

• $1/3 * 3/5 = 1/5$
• $1/3$ 同余于 $6 \pmod {17}$
• $3/5$ 同余于 $4 \pmod {17}$
• $4 \times 6\equiv7 \pmod {17}$
• $1/5\equiv 7 \pmod {17}$

留给读者的练习

寻找以下代数数据结构对的同态。如果你卡住了（或者只是不想解决这个问题），你可以通过 Google 搜索答案或向聊天机器人咨询。

1. 加法运算下的实数到加法运算下的实系数多项式。
2. 实系数多项式到加法运算下的实数。提示：尽管这看起来与问题 1 相似，但函数 $\phi$ 将与前一个问题的答案完全无关。
3. 乘法运算下大于零的正实数到加法运算下的所有实数。

同态加密

如果 $\phi$ 在计算上很难求逆，那么 $\phi$ 就对 $A$ 的元素进行了同态加密。

设 $A$ 为加法运算下的所有整数，设 $B$ 为目标群，$\blacksquare$ 为 $B$ 的二元运算符。

零知识加法，示例 1

假设我们希望向验证者证明我们计算了 $2 + 3=5$。我们会向验证者提供 $(x, y, 5)$，其中 $x=\phi(2), y= \phi(3)$，验证者将检查：

请注意，同态加密意味着验证者知道函数 $\phi$。

零知识加法，示例 2

证明者声明：“我有两个数字 $a$ 和 $b$，并且 $b$ 是 $a$ 的五倍。”证明者将 $\phi(a)$ 和 $\phi(b)$ 发送给验证者，验证者检查以下等式：

请记住，这里的“乘法”不是二元运算符，它只是重复加法的简写。

请注意，在这些示例中，我们没有提到 $B$ 的元素是什么，也没有提到 $\blacksquare$ 是什么。$B$ 可以是令人生畏的数学对象，$\blacksquare$ 也可以是令人生畏的数学运算符，但这都不重要。

这就是抽象代数的魅力所在：我们不需要知道。只要它具有我们关心的属性，即使我们对其具体实现一无所知，也能推断出它的行为。

动机

好的，很酷；我们理解了群和同态，但这如何帮助我们呢？我之所以费尽心思解释这一切，是因为我希望你能理解以下陈述：

“在加法运算下的有限域中的椭圆曲线点是一个有限循环群，且加法运算下的整数同态于该群。”

你可能不知道椭圆曲线点是什么，也不知道对它们进行加法运算意味着什么，但你确实知道：

1. 椭圆曲线点集合在加法运算下会生成另一个椭圆曲线点。
2. 接受两个椭圆曲线点并返回另一个椭圆曲线点的二元运算符是结合的。
3. 椭圆曲线点的集合包含一个单位元。
4. 椭圆曲线群有一个单位元，且该单位元是唯一的。
5. 每个椭圆曲线点都有一个逆元，将一个点与其逆元相加会生成单位元。
6. 因为该群是循环的，每一个椭圆曲线点都可以通过对某个生成元不断应用二元运算符来生成。
7. 因为椭圆曲线点构成的群是循环群，所以它也是一个阿贝尔群。
8. 因为它是一个有限群，所以它的阶数是有限的。
9. 因为同态的存在，我们对椭圆曲线点的二元运算符的行为方式有了深刻的认识。在某种意义上，我们可以利用椭圆曲线点的二元运算符来“执行整数加法”。

尽管你不知道椭圆曲线点到底是什么，但你已经知道了关于它们的 9 件事！

因此，不管“椭圆曲线点”这些奇怪的对象是什么，你都知道它行为表现如何，并且具有我们上面讨论过的群的相同属性。

信不信由你，你已经完成了理解椭圆曲线 90% 的道路。通过理解椭圆曲线与其他熟悉结构的相似性来弄懂它们，远比试图从零开始去理解其复杂的数学原理要容易得多。

这就类似于我告诉你 Ethereum 使用“Patricia Merkle trees”来存储状态。你可能不知道“Patricia tree”或“Merkle tree”是什么，但你确实知道：

• 它有一个根节点。
• 你可能可以在对数时间内访问元素，或者至少它的意图是这样。
• 叶子节点存储了某些有用的东西。
• 存在某种算法可以遍历该树并访问你关心的叶子节点。

所以，当我告诉你加法运算下的椭圆曲线点构成一个群时，你早就应该知道在学习该主题时需要注意什么了。

同样，群不需要是神秘的“月亮数学”。作为一名程序员，你早已凭直觉使用过群。现在你有了一个具体的词来描述这种反复出现的现象。

说“群”比说“这是一个具有可以结合元素的集合，并且这些元素都有这这这、那那那……”要高效得多。

我知道这可能看起来像是一个巨大的偏题，但请相信我，理解“同态”能让我们简洁地描述一个我们将经常看到的概念。当我们讨论 Quadratic Arithmetic Programs 时，它也将再次派上用场。同态在 ZK 领域中频繁出现。

想象一下在没有“根”或“叶子”这两个词汇的情况下去尝试讨论树这种数据结构。那将会极其令人沮丧。

总结

从 $A$ 到 $B$ 的同态存在，当且仅当存在一个函数 $\phi$，它接受 $A$ 中的一个元素并返回 $B$ 中的一个元素，且对于 $A$ 中的所有 $a_i$ 和 $a_j$，都有 $\phi(a_i \square a_j)=\phi(a_i)\blacksquare\phi(a_j)$，其中 $\square$ 是 $A$ 的二元运算符，$\blacksquare$ 是 $B$ 的二元运算符。$\phi$ 的存在对于同态的成立是充分的。

同态不一定是双向的。它们只被要求在一个方向上起作用，即从 $A$ 到 $B$。

如果 $\phi: A \rightarrow B$ 在计算上难以求逆，那么 $\phi$ 就对 $A$ 中的元素进行了同态加密。这意味着我们可以使用 $B$ 中的元素来验证关于 $A$ 中计算的声明。

好消息是，我们已经完成了对抽象代数的探讨，现在我们拥有了坚实的基础，可以继续探索 椭圆曲线 了。