同态映射

通过示例理解同态

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

假设我们有两个代数数据结构 (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^{ai}=\underbrace{b\cdot b\cdot\dots\cdot b}{{a_i} \text{ times}}

$$

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

$$

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

$$ b^{a_i +aj}=\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

这个概念已经在我们关于 有限域 的文章中讲解过，但我们没有使用“同态”来描述它。

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

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

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

或者在 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 可能是复杂的数学对象，◼ 可能是复杂的数学运算，但那并不重要。

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

动机

好的，了解到群和同态的概...