希拉·南丁格尔

Ciara Nightingale

ZK 数学 101：二元运算符与群论

探索群论基础知识：二元运算符、单位元、逆元、结合律和交换律。理解密码学和 ZK 证明至关重要。

什么是群论

群论构成了现代密码学和零知识系统的数学支柱。 可以把它看作是学习密码学的专用语言。

密码学家使用诸如“循环加法群”和“生成器”之类的术语，因为这些精确的数学结构使得密码学算法和证明能够被创建。

如果不理解群，那么高级的密码学概念仍然是遥不可及的，就像你必须先掌握算术才能学习微积分一样。 ‍

你将学到什么

最终，你将学习群的定义。 为此，你必须首先学习：

• 二元运算符：定义群元素如何相互作用的基本运算 ‍
• 核心群属性：
  • 单位元
  • 结合律
  • 闭包性
  • 寻找逆元（加法和乘法）
  • 费马小定理及其在寻找逆元中的应用 ‍
• 群中的除法：乘法逆元如何产生除法运算 ‍
• 阿贝尔群：
  • 交换律

到本文结束时，你将理解支撑零知识证明的群结构，并能够理解未来的密码学概念。 ‍

前提条件

这是本系列文章的第三篇。 建议你在阅读本文之前阅读前两篇，它们涵盖了模运算和集合论：

• 模运算
• 集合论

‍

什么是群？

群是一个配备了满足特定属性的二元运算符的集合。 要理解这句话的含义，我们必须首先定义术语“二元运算符”。 ‍

二元运算符

术语 "二元运算符" 听起来很可怕，但实际上并非如此。

二元运算符是一种运算符，它接受两个操作数（即，集合中的两个元素）来执行计算或运算。 二元运算符对两个元素 a 和 b 进行运算以产生结果： ‍ a⋅b=c

其中⋅表示任何二元运算符。 令人困惑的是，在某些情况下，此符号也用于表示算术中的乘法（我们将在以后的文章中使用⋅来表示乘法）。

二元运算符的常见示例包括：

• 算术运算符
  • 加法：+（例如，3+4）
  • 减法：−（例如，5−2）
  • 乘法：×（例如，6×7）
  • 除法：÷（例如，8÷2）
  • 取模：modn（例如，10mod3） ‍
• 比较运算符
  • 等于：==（例如，3==3）
  • 不等于：≠（例如，4≠5）
  • 大于：>（例如，7>3）
  • 小于：<（例如，2<6）
  • 大于或等于：≥（例如，5≥5）
  • 小于或等于：≤（例如，4≤7） ‍
• 布尔运算符
  • 与（AND）
  • 或（OR）
  • 异或（XOR）
  • 非（NOT）

例如，在表达式 3+4 中，+ 运算符是一个二元运算符，它接受两个操作数 3 和 4，并执行加法以输出 7。 ‍

群的定义

群是元素 G 的集合，配备了满足特定属性的二元运算符 ⋅ 。 ‍ 当我们说“配备了二元运算符”时，我们的意思是，在该群中只能考虑指定的运算符。 例如，假设我们将一个群定义为模 p 的整数集合，并配备加法运算符。 所有其他运算符（例如，乘法等）在此上下文中都不存在。

让我们来看看我们的集合 G 加上二元运算符 ⋅ 必须满足的那些“特定属性”： ‍

1. 闭包性

集合 G 在运算下必须是“封闭的”，这意味着当你将运算应用于集合中的任意两个元素时，结果也必须是集合中的一个元素。

形式上，如果 a 和 b 是集合中的元素，则 a⋅b 也必须在集合中： a⋅b=c

其中 c∈G

例如，考虑加法运算符下的整数集合：

5+9=14

由于 14 也在整数集合中，因此加法运算符是封闭的。

或者对于乘法下的整数集合：

5×9=45

由于 45 也在整数集合中，因此乘法运算符是封闭的。 ‍

2. 单位元

集合中必须存在一个单位元 I，使得对于集合中的每个元素 a，当与单位元运算时，输出是元素本身：

a⋅I=I⋅a=a

此外，单位元必须是唯一的，这意味着每个集合只存在一个单位元。

同样，考虑加法下的整数。 这里，单位元是 0，因为

a+0=a

对于乘法下的整数，对于整数 a，单位元是 1，因为：

a×1=a ‍

3. 逆元

每个元素必须有一个逆元。 对于集合中的每个元素 a，必须存在一个元素 ainv，使得当它与该元素运算时，输出是单位元 I：

a⋅ainv=ainv⋅a=I

对于加法下的整数，逆元是元素的负数（或元素乘以 −1），例如，对于整数 5：

−5+5=0

但是，如果集合仅限于正整数，则并非所有元素在该集合中都具有逆元（例如，不存在正整数 b 使得 5+b=0）。 因此，加法下的正整数集合不是一个群。

对于乘法下的整数，逆元是 a 的倒数。 例如，对于整数 5：

5×15=1

但是，15 不在整数集合中； 因此，乘法下的整数集合不是群。 ‍

4. 结合律

运算必须是结合的。 这意味着括号的位置不会影响计算的结果。 对于集合中的任意三个元素 a、b 和 c，结合律可以用数学方式定义为：

(a⋅b)⋅c=a⋅(b⋅c)

例如，加法下的整数集合：

(1+2)+3=1+(2+3)=6

对于乘法下的整数集合：

(1×2)×3=1×(2×3)=6

由于加法下的整数集合满足所有属性，因此该集合构成一个群。 但是，对于加法下的正整数集合，由于并非所有元素在该集合中都具有逆元，因此它不构成群。

要记住群的属性，请使用以下首字母缩写词：

Cyfrin Is Incredibly Awesome（闭包性、单位元、逆元、结合律） ‍

模运算中的逆元

在处理“常规数学”时，逆元是直观的。 但是，它们在模运算中的工作方式略有不同。

请记住，对于集合中的每个元素 a，逆元 ainv 使得：

a⋅ainv=ainv⋅a≡I(modn)

请注意，我们已将 modn 添加到等式中，因为我们现在正在使用模运算。 ‍

模运算中的加法逆元

在模 n 的有限整数集合中找到元素 a 的加法逆元，表示为 $\mathbb{Z}n ,meansfindinganelementa{inv}suchthatwhenitisappliedtotheelementawiththebinaryoperator+,ityieldstheidentityelement0:a+ainv≡0(modn)$**。

找到加法逆元：

1. 使用定义： a 模 n 的加法逆元是数字 b，使得和 a+b 可被 n 整除。 简而言之，b 满足： ‍
2. ainv≡−a(modn) ‍
3. 简化 −amodn：
   • 计算 −a，即 a 的负数。
   • 简化 −a(modn) 以确保 b 在 0 到 n−1 的范围内。

示例：模 7

找到 Z7 中 3 的加法逆元：

• 从 −3 开始，即 3 的负数。
• 简化 −3mod7（将 7 加到它以找到 0 到 (n−1) 范围内的全等值：
• −3+7=4
• 因此，3(mod7) 的加法逆元是 4(mod7)

一般规则 对于任何 a∈Zn（∈表示模 n 的整数集合中的任何元素 a），加法逆元是：

ainv≡n−a(modn) 如果 a≠0，如果 a=0，则 b=0。

这有效，因为将 n−a 加到 a 得到：

a+(n−a)=n≡0(modn) ‍

乘法逆元和费马小定理

让我们找到模 p 的有限整数集合的乘法逆元。 模运算中乘法逆元的定义是：

a×ainv≡1(modp)

其中运算符是乘法，用 × 表示，单位元是 1。

要找到有限集合的乘法逆元，特别是模 p 的整数，你必须首先理解费马小定理：**

费马小定理指出，当且仅当 p 是素数且 a 是不能被 p 整除的整数时（即，a≠0 模 p），则：

ap−1≡1(modp)

意思是，将 a 提升到 p−1 的幂次方得到的结果与 1 模 p 同余。**

找到乘法逆元

要找到 a 模 p 的乘法逆元，我们需要找到一个整数 ainv，使得：

a⋅ainv≡1(modp)

由于在“基本”算术中 ainv=a−1：

a⋅a−1≡1(modp)

a−1 是我们试图找到的乘法逆元，费马小定理用于找到它。 费马小定理指出，如果 a≠0(modp)，则：

ap−1≡1(modp)

然后，将此方程的两边乘以 a−1（我们试图找到的假设逆元）：

ap−1⋅a−1≡1⋅a−1(modp)

ap−2≡a−1(modp)

因此，ap−2 是 a 模 p 的乘法逆元。 换句话说：

ainv=a−1≡ap−2(modp)

因此，只要 a 不能被 p 整除，模素数 p 的整数 a 就存在乘法逆元。 意思是，如果 p 是素数且 a≠0(modp)，因为 0 没有逆元，则存在一个整数 ainv 使得 a⋅ainv≡1(modp)。

费马小定理对于理解为什么模素数 p 的整数集合（不包括零）经常在零知识证明和密码学中被选择至关重要，例如，在 Groth16中。

该集合用 Zp∗ 表示，由模 p 的所有非零元素组成，并形成一个乘法群，其中每个元素都有一个逆元。 ‍

模运算中的除法

在模运算文章中，我们提到除法在模运算中不存在，就像在“基本”算术中一样。 但是，我们可以使用乘法逆元构造除法运算。

除法运算： 在模运算中，除法 —或者更确切地说是逆乘法，可以通过乘以分母的逆元来构造。 例如：

ab→(a⋅binv)modp**

除法示例： 如果 p=7 且 a=3，则根据费马小定理：

37−1≡36≡1(mod7)

要找到逆元，计算 37−2：

35≡243≡5(mod7)

因此，3 模 7 的逆元是 5，因为：

3⋅5≡15≡1(mod7) ‍

阿贝尔群

阿贝尔群是一个集合和一个二元运算符，具有上述群的四个属性，外加运算符必须是可交换的。 交换律： 运算时操作数的顺序无关紧要。

a⋅b=b⋅a

阿贝尔群只是我们将在本系列后面描述配备二元运算符的集合的另一种方式，因此你应该习惯理解这意味着什么：运算符是可交换的！

要记住阿贝尔群的定义，这里有另一个厚颜无耻的助记符： Clearly : 交换律 Cyfrin: 闭包性 Is: 单位元 Incredibly: 逆元 Awesome: 结合律 ‍

群的例子

现在让我们来看一些例子，以习惯于确定集合加上特定运算符组合是否是一个群（以及该群是否是阿贝尔群）。 ‍

示例 1：加法下的整数集合

我们有 4 个属性要检查群，另外一个属性来确定它是否是阿贝尔群：

它是否具有结合性？

是的！ 整数的加法具有结合性：

(a+b)+c=a+(b+c)**

它是否是封闭的？

是的！ 对于任何整数 a 和 b，a+b 也是一个整数。**

是否存在单位元？

是的！ 加法单位元是 0，因为：

a+0=a**

所有元素是否都有逆元？

是的！ 整数 a 的加法逆元是 −a，并且：

a+(−a)=0**

为了检查它是否是阿贝尔群，它是否是可交换的？**

是的，加法是可交换的：

a+b=b+a

属性	结果
结合律	✅
闭包性	✅
单位元	✅
逆元	✅
交换律	✅

由于所有属性都满足，因此加法下的整数集合是一个阿贝尔群！ ‍

示例 2：模 p 加法下的整数集合

让我们以模 7 的整数为例：{0,1,2,3,4,5,6}。**

它是否具有结合性？

是的！ 让我们检查一下：

(((3+5)mod7)+6)mod7=0

(3+((5+6)mod7))mod7=0

我们可以进一步编写一个数学证明来证明这在所有情况下都成立，但这超出了本文的范围。**

它是否是封闭的？

是的！ 由于我们使用模 7，因此任何加法的结果始终在 0 和 6 之间，因此它仍然在集合中：

(1+5)mod7=6**

是否存在单位元？

是的！ 加法单位元是 0。**

所有元素是否都有逆元？

是的！ 要找到 a 模 p 的加法逆元，我们需要一个元素 ainv 使得：

a+ainv≡0(modp)

对于 p=7，4 的逆元是 3，因为：

4+3≡0(mod7)

通常，a 的逆元是 p−a。 ‍ 属性	结果
结合律	✅
闭包性	✅
单位元	✅
逆元	✅

它是否是阿贝尔群？

是的，模 p 加法是可交换的：

a+b≡b+a(modp)

模 p 加法下的整数集合是一个阿贝尔群！ ‍

示例 3：乘法下的模 n 整数

让我们取模 6 的整数集合：{0,1,2,3,4,5}。**

它是否具有结合性？

是的！ 让我们检查一下：

(((3⋅4)mod6)⋅2)mod6=0

(3⋅((4⋅2)mod6))mod6=0**

它是否是封闭的？

是的！ 由于运算是模 6，因此任何乘法的结果始终在集合中：

(2⋅3)mod6=0**

是否存在单位元？

是的！ 在乘法下，单位元是 1：

(3⋅1)mod6=3**

所有元素是否都有逆元？

在模运算中查找逆元更为复杂。 对于元素 a，乘法逆元 ainv 使得：

(a⋅ainv)modn=1

例如，对于 n=6：

• 对于 a=1：inverse(1)=1
• 对于 a=2：没有逆元，因为 (2⋅x)mod6=1 在集合中没有解。

因此，并非此集合的所有元素都具有逆元，因此它不是一个群。

回想一下，如果 n 是素数，则由于费马小定理，每个元素（0 除外）都具有逆元。 意思是，对于任何非零整数 a 模素数 p，都存在一个乘法逆元。 该定理提供了一种计算此逆元的实用方法 ap−2，确保 (Zp,×) 的结构形成一个群。 ‍ 属性	结果
结合律	✅
闭包性	✅
单位元	✅
逆元	❌

由于它不是群，因此无需检查此群是否是阿贝尔群。 ‍

示例 4：乘法下的模 p 整数

我们将证明，如果 p 是素数，则集合 {1,2,…,p−1} 在乘法下是一个群。 请注意，在此示例中，我们选择从集合中删除 0，因为我们可以按照我们选择的方式定义集合，并且我们希望定义一个没有元素等于 0 的集合。 具体来说，因为 0 没有逆元，因此该集合在乘法运算符下不形成群。**

它是否具有结合性？

是的！ 乘法具有结合性：

((a⋅b)⋅c)=(a⋅(b⋅c))**

它是否是封闭的？

是的！ 将任何两个非零元素模 p 相乘会导致另一个非零元素模 p。**

是否存在单位元？

是的！ 乘法单位元是 1：

(a⋅1)modp=a**

所有元素是否都有逆元？

是的！ 对于素数 p，每个非零元素都有一个逆元：

(a⋅ainv)≡1(modp)

例如，4 模 7 的逆元是 2，因为：

(4⋅2)mod7=1 ‍ 属性	结果
结合律	✅
闭包性	✅
单位元	✅
逆元	✅

a≠0 模 p 的整数集合在乘法下是一个群！**

它是否是阿贝尔群？

是的，模 p 乘法是可交换的：

a⋅b≡b⋅a(modp)

模 p 乘法下的整数集合是一个阿贝尔群！

请记住之前，模素数 p 的有限整数集合通常用于密码学，这是因为它们在加法和乘法下都形成一个阿贝尔群！ ‍

标量乘法和指数运算

在我们继续之前，让我们介绍一个加法群中的标量乘法和乘法群中的标量指数运算的概念。 乍一看，当我们之前说我们只能执行加法运算时，我们可以在加法群中进行 ”乘法” 似乎违反直觉（同样，对于乘法群中的 ”指数运算” ），但事实并非如此......**

加法群中的标量乘法意味着将群元素多次加到自身。 如果 G 是一个群元素，k 是一个整数（表示为“标量”），则：

k⋅G=G+G+⋯+G⏟k 次

例如，G=3，群是加法下的整数，则：

4⋅G=3+3+3+3=12 ‍ 加法群中的标量乘法只是重复加法。**

乘法群中的指数运算意味着将群元素多次乘以自身。 如果 g 是一个群元素，k 是一个标量，则：

gk=g⋅g⋅⋯⋅g⏟k 次

例如，在整数模 7 的乘法群中，如果 g=3，则：

34mod7=81mod7=4

乘法群中的标量指数运算只是重复乘法。

另请注意，当在模 p 的有限整数集合中工作时，标量 k 不必在集合中。

这两个运算（标量乘法和指数运算）经常出现在密码学中。 特别是，它们在一个称为循环群的特殊群类中起着关键作用，我们将在以后的文章中进行探讨。 ‍

接下来是什么？

在本系列的下一部分中，我们将探索环和域——其他类型的数学结构，这些结构可以帮助我们为密码学系统（如有限域、椭圆曲线和多项式承诺）构建基础。 理解这些结构对于理解算术电路、zk-SNARK 和其他零知识协议如何在底层工作是必要的。 ‍

总结

在本文中，我们介绍了：

• 二元运算符是数学运算的基本构建块。 ‍
• 群结构由四个关键属性定义（“Cyfrin Is Incredibly Awesome”属性）： ‍
  • 闭包性：运算总是产生集合中的结果。
  • 单位元：存在一个元素，该元素在组合时保留其他元素。
  • 逆元：每个元素都有一个产生单位元的对应元素。
  • 结合律：运算顺序不影响结果。 ‍
• 阿贝尔群增加了交换律以创建更有用的数学结构 ‍
• 群中的模运算，包括：
  • 查找加法和乘法逆元。
  • 了解为什么在密码学中首选素数模数。
  • 使用费马小定理有效地计算乘法逆元。
  • 构造除法运算符。

这些数学结构不仅仅是要理解的抽象概念。 它们是必不可少的必要构建块，可用于构建现实世界的密码系统和应用程序。 保护信息并在不泄露秘密的情况下证明知识的应用程序。 在下一篇文章中，我们将以这些群论基础为基础来探索环和域。 ‍

参考文献

更喜欢通过视频学习？ 查看有关群的此 YouTube 视频： ‍ ‍ 以及有关费马小定理的这一段： ‍ ‍ 资源：

• 证明模 p 的非零整数集合在乘法下形成一个群
• 模 p 整数集合在加法下形成一个群的证明
• RareSkills 的 ZK Book
• Victor Shoup - 计算数论和代数导论
• LeastAuthority 的 ZK Moon Math Manual
• 牛津群、环和域导论

• 原文链接： cyfrin.io/blog/zk-math-1...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～