同态映射

RareSkills
发布于 2024-08-28 20:25
阅读 20

本文通过多个例子详细解释了同态映射的概念，并探讨了其在加密技术和零知识证明中的应用。文章结构清晰，分为简单和复杂例子两部分，并附有详细的数学公式和Python代码示例。

## 通过示例理解同态

如果在两个群之间存在一个_结构保持映射_，那么两个群之间就存在同态。

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

从 A 到 B 的同态存在当且仅当存在一个函数 ϕ:A→B 使得

$$ \phi(a_i \square a_j)=\phi(a_i)\blacksquare\phi(a_j)\space\space\forall a_i,a_j\in A $$

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

注意，同态是单向的。函数 ϕ 将 A 中的元素映射到 B 中的元素。我们对于“反向”映射没有要求。

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

## 同态的简单示例

### 所有整数加法映射到所有偶整数加法

设 A 为所有整数加法的集合，B 为所有偶整数加法的集合。显然，A 和 B 都是群。

设 ϕ(x)=2x

我们看到，ϕ 定义了一个从 A 到 B 的同态，因为对于任何一对整数 ai 和 aj，以下关系成立：
$$
\begin{align*}
\phi(a_i+a_j)&=\phi(a_i)+\phi(a_j)\\
2(a_i+a_j)&=2(a_i)+2(a_j)
\end{align*}
$$

### 所有字符串连接映射到所有大于等于零的整数

例如，设 A 为所有字符串（包括空字符串）的单元，在连接下操作，设 B 为所有大于等于零的整数的单元，在加法操作下。

从 A 到 B 存在一个同态，因为存在一个函数 ϕ 将字符串映射到大于等于零的整数并保持以下性质

$$
\phi(a_i+a_j)=\phi(a_i)+\phi(a_j)
$$

在这种情况下，ϕ 是字符串的_长度_。例如：

$$
\begin{align*}
\text{Rare}&\rightarrow 4\\
\text{Skills}&\rightarrow 6\\
\text{RareSkills}&\rightarrow 10\\
\end{align*}
$$

在这里，我们有

$$
\begin{align*}
\phi(\text{Rare})&=4\\
\phi(\text{Skills})&=6\\
\phi(\text{RareSkills})&=10\\
\phi(\mathsf{concat}(\text{Rare},\text{Skills}))&=\phi(\text{Rare})+\phi(\text{Skills})\\
\end{align*}
$$

#### 所有实数加法映射到所有 n×m 矩阵的加法

一些同态在你掌握这些概念后似乎相当微不足道。这是这样的一个同态的例子。在这种情况下，我们的函数 ϕ 只是将实数重复 n×m 次。例如，如果 n=3 和 m=2，则 ϕ(8.8) 为：

$$
\begin{bmatrix}
8.8&8.8\\
8.8&8.8\\
8.8&8.8
\end{bmatrix}
$$

作为示例，如果 ϕ(8.8+0.2)=ϕ(8.8)+ϕ(0.2) 因为

$$
\begin{bmatrix}
9&9\\
9&9\\
9&9\\
\end{bmatrix}=
\begin{bmatrix}
8.8&8.8\\
8.8&8.8\\
8.8&8.8
\end{bmatrix}+
\begin{bmatrix}
0.2&0.2\\
0.2&0.2\\
0.2&0.2\\
\end{bmatrix}
$$

## 关于同态的澄清

- ϕ 必须适用于 A 中每一对可能的元素（包括相同元素的对）。然而，它不需要“访问” B 中的所有元素。例如，将 A 中的每个元素映射到 B 中的单位元的同态是一个有效的同态，但并没有什么用。它被称为_平凡同态_。
- 如果我们选择两个任意集合及其二元运算，则不一定存在同态。
- 可能存在从 A 到 B 的同态，但不一定存在从 B 到 A 的同态。
- 如果存在一个从 A 到 B 的同态和一个从 B 到 A 的同态，并且 ϕ 是从 A 到 B 的映射，ϕ 的逆可能不一定是从 B 到 A 的同态的有效映射。

## 更多同态的示例

#### 整数加法映射到 b 的整数次幂的乘法

假设我们有群 A=(Z,+)（所有整数加法的集合）和群 B，即所有 b 的整数次幂在乘法下的集合，i.e., B=(bi:i∈Z,×)。我们可以随意设置 b=2，使这个例子更容易理解。

存在一个从 A 到 B 的同态，定义为 ϕ(x)=bx。根据代数的规则，

$$
\begin{align*}
\phi(a_i+a_j)&=\phi(a_i)\times\phi(a_j)\\
b^{a_i + a_j}&=b^{a_i}b^{a_j}
\end{align*}
$$

要理解为什么这个关系成立，可以考虑：

b^{a_i}=\underbrace{b\cdot b\cdot\dots\cdot b}_{{a_i} \text{ times}}

$$
b^{a_j}=\underbrace{b\cdot b\cdot\dots\cdot b}_{{a_j} \text{ times}}

$$
b^{a_i + a_j}=\underbrace{b\cdot b\cdot\dots\cdot b}_{{a_i} \text{ times}} \cdot \underbrace{b \cdot b \cdot \dots \cdot b}_{a_j \text{ times}}
$$

$$
b^{a_i +a_j}=\underbrace{b\cdot b\cdot\dots\cdot b\cdot b\cdot b\dots\cdot b}_{{a_i+a_j} \text{ times}}
$$

### 整数加法映射到质数的 b 的整数次幂的乘法模

### n×m 矩阵加法映射到整数加法

在这种情况下，ϕ 只是将矩阵中的所有元素相加。为什么有效留给读者自己思考。

### 整数的 2×2 矩阵乘法映射到整数乘法

从第一个单元到第二个单元存在一个同态，因为 ϕ 是矩阵的_行列式_，并且以下规则成立：

$$XY=Z→det(X)det(Y)=det(Z)$$

其中 X,Y,Z 是 2×2 整数矩阵。为什么这些是代数数据结构而不是群留给读者思考。

#### 排除分母为 p 的有理数的群到加法模 p

这个概念已经在我们关于 [有限域](https://learnblockchain.cn/article/11315) 的文章中讲解过，但我们没有使用“同态”来描述它。

设 A 为所有分母不是 p 的倍数的有理数的群，操作为加法。设 B 为模 p 的有限域。

存在一个从群 A 到群 B 的同态。 ϕ 定义为

$$
\phi(x) = \mathsf{numerator}(x)\times\mathsf{modular\_inverse}(\mathsf{denominator}(x)) \pmod p
$$

或者在 Python 中：

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

例如：

- 1/3+3/5=14/15
- 1/3 ≡ 6(mod17)
- 3/5 ≡ 4(mod17)
- 4+6 ≡ 10(mod17)
- 14/15 ≡ 10(mod17)

说 1/3 ≡ 6(mod17) 等价于陈述 ϕ(1/3)=6。

### 排除分母为 p 的有理数的单元到模 p 的乘法（不包括零）

让我们以上述相同的例子，但进行乘法。函数 ϕ 保持不变。

- 1/3∗3/5=1/5
- 1/3 ≡ 6(mod17)
- 3/5 ≡ 4(mod17)
- 4×6 ≡ 7(mod17)
- 1/5 ≡ 7(mod17)

## 留给读者的练习

为以下代数数据结构对找到一个同态。如果遇到困难（或只是想要解决问题），可以通过谷歌查找答案或咨询聊天机器人。

1. 实数加法到带实系数多项式的加法。
2. 带实系数的多项式到实数加法。提示：尽管这与问题1相似，但函数 ϕ 完全不相关于前一个问题的答案。
3. 大于零的正实数乘法到所有实数加法。

### 同态加密

如果 ϕ 计算上难以反转，则 ϕ _同态加密_ 了 A 的元素。

设 A 为所有整数加法，B 为目标群，◼ 为 B 的二元运算。

#### 零知识加法，示例 1

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

$$ x◼y=?ϕ(5) $$

注意，同态加密意味着验证者知道函数 ϕ。

#### 零知识加法，示例 2

一个证明者声称：“我有两个数字 a 和 b，b 是 a 的五倍。”证明者将 ϕ(a) 和 ϕ(b) 发送给验证者，验证者检查：

$$ ϕ(a)+ϕ(a)+ϕ(a)+ϕ(a)+ϕ(a)=ϕ(b) $$

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

在这些示例中，请注意我们没有提到 B 中的元素是什么，◼ 是什么。B 可能是复杂的数学对象，◼ 可能是复杂的数学运算，但_那并不重要_。

这就是抽象代数的美：_我们不需要知道_。只要它具有我们所关心的属性，我们就可以推理它的行为，即使我们对实现一无所知。

### 动机

好的，了解到群和同态的概念后，这对我们有什么帮助？我这样做的原因是希望你理解下面这个声明：

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

你可能不知道椭圆曲线点是什么，或其加法的意义，但你已经知道：

1. 椭圆曲线下加法的点集带来另一个椭圆曲线点。
2. 将两个椭圆曲线点作为输入并返回另一个椭圆曲线点的二元运算是结合的。
3. 椭圆曲线点集包含一个单位元素。
4. 椭圆曲线群有一个唯一的单位元素。
5. 每个椭圆曲线点都有一个逆元，使得加上一个点及其逆元的结果为单位元素。
6. 因为群是循环的，每个椭圆曲线点可以通过对某个生成元素重复应用二元运算生成。
7. 因为椭圆曲线点的群是循环的，它也是阿贝尔群。
8. 由于它是一个有限群，阶数是有限的。
9. 由于同态的性质，我们很清楚椭圆曲线点的二元运算的行为。我们可以使用椭圆曲线的点二元运算以某种意义“添加整数”。

即使你不知道椭圆曲线点是什么，你已经知道关于它们的九个事实！

所以无论这些奇怪的对象“椭圆曲线点”是什么，你都知道它的行为以及与我们之前讨论的群拥有相同的属性。

信不信由你，你已经走了90%理解椭圆曲线的路。通过理解它们与其他熟悉结构的相似性，比从零开始理解它们奇怪的数学更容易得多。

这类似于我告诉你以太坊使用“Patricia Merkle 树”来存储状态。你可能不知道“Patricia 树”或“Merkle 树”是什么，但你知道：

- 它有一个根。
- 你可能以对数时间访问元素，或者至少这是它的意图。
- 叶子中存储着一些有用的东西。
- 有一个算法可以遍历树并访问你关心的叶子。

所以当我告诉你在加法下椭圆曲线点形成一个群时，你应该已经知道这一学科有哪些需要留意的地方。

再次强调，群不必是神秘的月球数学。作为程序员，你已经直观地使用过群。现在，你有了一个具体的词来描述这种反复出现的现象。

说“群”要远比“这是一个组合元素的方式是结合的，元素具备 blah blah blah”来得高效得多。

我知道这似乎是一个很大的偏离，但相信我，理解“同态”使我们能够简洁地描述一个我们将经常看到的概念。当我们讨论[二次算术程序](https://learnblockchain.cn/article/11314) 时，它也将再次派上用场。同态在零知识世界中频繁出现。

想象一下，试图讨论树数据结构而没有“根”或“叶子”的词汇。这将是极具挑战性的。

### 总结

从 A 到 B 的同态存在**当且仅当**存在一个函数 ϕ，它从 A 中取出一个元素并返回 B 中的一个元素，并且满足 ϕ(ai◻aj)=ϕ(ai)◼ϕ(aj)，对所有 ai 和 aj ∈ A，其中 ◻ 是 A 的二元运算，◼ 是 B 的二元运算。**ϕ 的存在是同态存在的充分条件。**

同态不一定是双向的。它们只需在一个方向上有效，从 A 到 B。

如果 ϕ:A→B 在计算上难以反转，则 ϕ 同态加密了 A 的元素。这意味着我们可以使用 B 中的元素来验证关于 A 中计算的声明。

好消息是，我们的抽象代数话题已经结束，我们现在有了坚实的基础，可以继续学习 [椭圆曲线](https://learnblockchain.cn/article/11323)。

>- 原文链接： [rareskills.io/post/homom...](https://www.rareskills.io/post/homomorphisms)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

通过示例理解同态

如果在两个群之间存在一个结构保持映射，那么两个群之间就存在同态。

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

从 A 到 B 的同态存在当且仅当存在一个函数 ϕ:A→B 使得

$$ \phi(a_i \square a_j)=\phi(a_i)\blacksquare\phi(a_j)\space\space\forall a_i,a_j\in A $$

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

注意，同态是单向的。函数 ϕ 将 A 中的元素映射到 B 中的元素。我们对于“反向”映射没有要求。

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

同态的简单示例

所有整数加法映射到所有偶整数加法

设 A 为所有整数加法的集合，B 为所有偶整数加法的集合。显然，A 和 B 都是群。

设 ϕ(x)=2x

我们看到，ϕ 定义了一个从 A 到 B 的同态，因为对于任何一对整数 ai 和 aj，以下关系成立： $$ \begin{align} \phi(a_i+a_j)&=\phi(a_i)+\phi(a_j)\ 2(a_i+a_j)&=2(a_i)+2(a_j) \end{align} $$

所有字符串连接映射到所有大于等于零的整数

例如，设 A 为所有字符串（包括空字符串）的单元，在连接下操作，设 B 为所有大于等于零的整数的单元，在加法操作下。

从 A 到 B 存在一个同态，因为存在一个函数 ϕ 将字符串映射到大于等于零的整数并保持以下性质

$$ \phi(a_i+a_j)=\phi(a_i)+\phi(a_j) $$

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

$$ \begin{align} \text{Rare}&\rightarrow 4\ \text{Skills}&\rightarrow 6\ \text{RareSkills}&\rightarrow 10\ \end{align} $$

在这里，我们有

$$ \begin{align} \phi(\text{Rare})&=4\ \phi(\text{Skills})&=6\ \phi(\text{RareSkills})&=10\ \phi(\mathsf{concat}(\text{Rare},\text{Skills}))&=\phi(\text{Rare})+\phi(\text{Skills})\ \end{align} $$

所有实数加法映射到所有 n×m 矩阵的加法

$$ \begin{bmatrix} 8.8&8.8\ 8.8&8.8\ 8.8&8.8 \end{bmatrix} $$

作为示例，如果 ϕ(8.8+0.2)=ϕ(8.8)+ϕ(0.2) 因为

$$ \begin{bmatrix} 9&9\ 9&9\ 9&9\ \end{bmatrix}= \begin{bmatrix} 8.8&8.8\ 8.8&8.8\ 8.8&8.8 \end{bmatrix}+ \begin{bmatrix} 0.2&0.2\ 0.2&0.2\ 0.2&0.2\ \end{bmatrix} $$

关于同态的澄清

ϕ 必须适用于 A 中每一对可能的元素（包括相同元素的对）。然而，它不需要“访问” B 中的所有元素。例如，将 A 中的每个元素映射到 B 中的单位元的同态是一个有效的同态，但并没有什么用。它被称为平凡同态。
如果我们选择两个任意集合及其二元运算，则不一定存在同态。
可能存在从 A 到 B 的同态，但不一定存在从 B 到 A 的同态。
如果存在一个从 A 到 B 的同态和一个从 B 到 A 的同态，并且 ϕ 是从 A 到 B 的映射，ϕ 的逆可能不一定是从 B 到 A 的同态的有效映射。

留给读者的练习

为以下代数数据结构对找到一个同态。如果遇到困难（或只是想要解决问题），可以通过谷歌查找答案或咨询聊天机器人。

实数加法到带实系数多项式的加法。
带实系数的多项式到实数加法。提示：尽管这与问题1相似，但函数 ϕ 完全不相关于前一个问题的答案。
大于零的正实数乘法到所有实数加法。

同态加密

如果 ϕ 计算上难以反转，则 ϕ 同态加密 了 A 的元素。

设 A 为所有整数加法，B 为目标群，◼ 为 B 的二元运算。

零知识加法，示例 1

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

$$ x◼y=?ϕ(5) $$

注意，同态加密意味着验证者知道函数 ϕ。

零知识加法，示例 2

一个证明者声称：“我有两个数字 a 和 b，b 是 a 的五倍。”证明者将 ϕ(a) 和 ϕ(b) 发送给验证者，验证者检查：

$$ ϕ(a)+ϕ(a)+ϕ(a)+ϕ(a)+ϕ(a)=ϕ(b) $$

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

在这些示例中，请注意我们没有提到 B 中的元素是什么，◼ 是什么。B 可能是复杂的数学对象，◼ 可能是复杂的数学运算，但那并不重要。

这就是抽象代数的美：我们不需要知道。只要它具有我们所关心的属性，我们就可以推理它的行为，即使我们对实现一无所知。

动机

好的，了解到群和同态的概念后，这对我们有什么帮助？我这样做的原因是希望你理解下面这个声明：

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

你可能不知道椭圆曲线点是什么，或其加法的意义，但你已经知道：

椭圆曲线下加法的点集带来另一个椭圆曲线点。
将两个椭圆曲线点作为输入并返回另一个椭圆曲线点的二元运算是结合的。
椭圆曲线点集包含一个单位元素。
椭圆曲线群有一个唯一的单位元素。
每个椭圆曲线点都有一个逆元，使得加上一个点及其逆元的结果为单位元素。
因为群是循环的，每个椭圆曲线点可以通过对某个生成元素重复应用二元运算生成。
因为椭圆曲线点的群是循环的，它也是阿贝尔群。
由于它是一个有限群，阶数是有限的。
由于同态的性质，我们很清楚椭圆曲线点的二元运算的行为。我们可以使用椭圆曲线的点二元运算以某种意义“添加整数”。

即使你不知道椭圆曲线点是什么，你已经知道关于它们的九个事实！

所以无论这些奇怪的对象“椭圆曲线点”是什么，你都知道它的行为以及与我们之前讨论的群拥有相同的属性。

信不信由你，你已经走了90%理解椭圆曲线的路。通过理解它们与其他熟悉结构的相似性，比从零开始理解它们奇怪的数学更容易得多。

这类似于我告诉你以太坊使用“Patricia Merkle 树”来存储状态。你可能不知道“Patricia 树”或“Merkle 树”是什么，但你知道：

它有一个根。
你可能以对数时间访问元素，或者至少这是它的意图。
叶子中存储着一些有用的东西。
有一个算法可以遍历树并访问你关心的叶子。

所以当我告诉你在加法下椭圆曲线点形成一个群时，你应该已经知道这一学科有哪些需要留意的地方。

再次强调，群不必是神秘的月球数学。作为程序员，你已经直观地使用过群。现在，你有了一个具体的词来描述这种反复出现的现象。

说“群”要远比“这是一个组合元素的方式是结合的，元素具备 blah blah blah”来得高效得多。

我知道这似乎是一个很大的偏离，但相信我，理解“同态”使我们能够简洁地描述一个我们将经常看到的概念。当我们讨论二次算术程序时，它也将再次派上用场。同态在零知识世界中频繁出现。

想象一下，试图讨论树数据结构而没有“根”或“叶子”的词汇。这将是极具挑战性的。

总结

从 A 到 B 的同态存在当且仅当存在一个函数 ϕ，它从 A 中取出一个元素并返回 B 中的一个元素，并且满足 ϕ(ai◻aj)=ϕ(ai)◼ϕ(aj)，对所有 ai 和 aj ∈ A，其中 ◻ 是 A 的二元运算，◼ 是 B 的二元运算。ϕ 的存在是同态存在的充分条件。

同态不一定是双向的。它们只需在一个方向上有效，从 A 到 B。

如果 ϕ:A→B 在计算上难以反转，则 ϕ 同态加密了 A 的元素。这意味着我们可以使用 B 中的元素来验证关于 A 中计算的声明。

好消息是，我们的抽象代数话题已经结束，我们现在有了坚实的基础，可以继续学习椭圆曲线。

原文链接： rareskills.io/post/homom...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

同态映射

通过示例理解同态

同态的简单示例

所有整数加法映射到所有偶整数加法

所有字符串连接映射到所有大于等于零的整数

所有实数加法映射到所有 n×m 矩阵的加法

关于同态的澄清

更多同态的示例

整数加法映射到 b 的整数次幂的乘法

整数加法映射到质数的 b 的整数次幂的乘法模

n×m 矩阵加法映射到整数加法

整数的 2×2 矩阵乘法映射到整数乘法

排除分母为 p 的有理数的群到加法模 p

排除分母为 p 的有理数的单元到模 p 的乘法（不包括零）

留给读者的练习

同态加密

零知识加法，示例 1

零知识加法，示例 2

动机

总结

0 条评论

文章目录