密码学、区块链和零知识证明的数学：模运算

Ciara Nightingale

ZK 数学 101：模运算

学习模运算和同余，密码学、区块链和零知识证明（如 Groth16 和 PLONK）背后的关键数学概念。 本文是解释理解区块链密码学和零知识系统（如Groth16和PLONK）所需的数学先决条件的系列文章的第一篇。

密码学在很大程度上依赖于有限域、模运算和群论等概念。 学习这些基础知识将使你能够了解零知识密码系统是如何实际工作的。

例如，请考虑 Groth16 论文 中的这段摘录： ‍

“令 G1 和 G2 为两个素数阶 q 的群，令 G3 为一个素数阶 q 的群。 该系统使用这些群之间的同态，其主要思想是构造一个证明，证明一个群中已提交的值对应于另一个群中的另一个值，而不揭示这些值本身。”

为了理解这一点，我们需要理解群、生成器点、同态和有限集（涉及模运算）。

可以将本系列文章视为密码学的“数学语言”指南，帮助你理解在研究论文或代码库中遇到的这些术语。 ‍

本系列文章并非旨在作为研究概述的数学主题的独立、结论性的资源。 相反，它是一个概述，用于分享理解零知识证明和密码学所需的高级概念。 有关更详细的细分，可以在每篇文章末尾的参考部分找到链接。 此外，请注意，为简单起见，已省略定理和定义的数学证明。 如果你有兴趣，我鼓励你使用链接的资源或你最喜欢的 AI 助手来了解如何从第一原理推导出这些概念。 ‍ 有了这些，让我们开始吧！ ‍

什么是模数？

模数是一个二元运算符，表示除法后的余数。 二元运算符接受两个操作数（输入）并对它们执行运算（例如，加法运算，但暂时不要太担心，当我们在另一篇关于群论的文章中正式介绍二元运算符时，将再次介绍它）。

以下符号用于表示模运算：

modn

其中 n 是一个整数。

请注意，在编程中，使用 % 符号代替。 ‍

示例 1：正整数

让我们看一个例子， 7(mod5): 7÷5=1 余数为 2。 因此，7mod5=2

以下是一些更多示例：

• 7(mod5)=2
• 5(mod2)=1
• 12(mod6)=0 ‍

示例 2：负整数

让我们来看一个负整数的例子，这可能会有点棘手。

考虑：

−7(mod5)

步骤 1：除法并找到余数** ‍ 如果我们用 5 除 −7，我们会得到：

−7÷5=−1 余数为 −2

但是 −2 不是 (mod5) 的有效余数，因为余数通常取自集合：

{0,1,2,3,4}

步骤 2：调整余数 为了使余数进入正确的范围，我们加 5**：

−2+5=3

所以：

−7(mod5)=3

考虑模运算的另一种方法是以以下形式重写数字：

−7=(−2×5)+3

这清楚地表明余数为 3。 ‍

模运算

模运算是整数的算术系统，其中数字在达到某个值（模数）时“环绕”。 术语“模”指的是所有算术运算都是相对于模数执行的事实。 ‍ 在模拟时钟上报时，模运算经常在日常生活中使用！ 没有“100 点钟”，因为小时会环绕。 每次时针到达 12 时，时间参考就会重新开始（假设你不使用 24 小时制时钟）。 ‍

某整数 n 的整数模集表示为 Zn，包含 n 个元素，表示为：

{0,1,2,…,n−1}

执行运算（例如加法）后，结果取模某个数字 n：

• 加法： (a+b)modn
  • 示例：(5+7)mod11=1 ‍
• 减法： (a−b)modn
  • 示例：(15−2)mod11=2 ‍
• 乘法： (a×b)modn
  • 示例：(15×2)mod11=8 ‍

其中 n 是模数，结果取模 n。 这意味着，初始运算的结果除以 n。 这总是导致 0 到 n−1 之间的值。 由于此模运算，自然会发生“环绕”！**

在密码学和零知识证明的上下文中，模数 n 通常选择为素数**，因此表示为 p。 随着本系列的进展，使用素数模数的原因将变得清晰。

从技术上讲，除法在通常意义上的模运算中不存在。 但是，可以使用乘法逆元定义一个“类似除法”的运算，这将在后面的群论文章中解释。 ‍

同余

如果两个整数 a 和 b 除以 n 时具有相同的余数，则称它们模 n 同余。 这写作：

a≡b(modn)

如果 a 和 b 之间的差是 n 的倍数，则 a 和 b 模 n 同余。

符号 ≡ 用于表示同余（该符号也用于等价）。 ‍

同余示例

考虑 n=5 和整数 a=17 和 b=2。 在此示例中，17 与 2 模 5 同余，因为 17 和 2 在除以 5 时都留下余数 2：

17÷5=3 余数 2

2÷5=0 余数 2

因此，

17≡2(mod5)

进一步扩展，

17≡12≡7≡2(mod5)

等等…… ‍

同余和等价类

理解同余不仅仅对于识别两个数字在除以给定模数后是否留下相同的余数有用。 在定义模运算中的等价类时，该概念是必需的，这对于理解密码学和许多其他数学领域至关重要。

在模数 n 下，等价类将所有模 n 相互同余的整数分组在一起。

如果两个整数 a 和 b 的差 (a−b) 可被 n 整除，即 a≡b(modn)，则它们模 n 位于同一个等价类中。

例如，对于模数 5，整数 2、7、12 和 −3 都属于同一个等价类，因为它们在除以 5 时都留下余数 2。

我们可以将其写为：

[2]5={…,−8,−3,2,7,12,17,…}

其中花括号表示法非正式地表示称为集合的元素集合（集合将在我们下一篇关于集合论的文章中正式介绍）。

每个等价类对应于除以 n 时可能的余数之一。 在这种情况下，2 模 5 的等价类包括所有形式为 5k+2 的整数，其中 k 是任何整数。

{[0]n,[1]n,…,[n−1]n} 的所有此类等价类的集合形成了数学家称之为模 n 的剩余系或商集。 ‍

接下来是什么？

在本系列的下一部分中，我们将研究集合论以及模运算如何适应这些代数结构，特别是有限域，它们是椭圆曲线密码学和 ZK 证明的核心。 ‍

模运算总结

• 模运算是一个系统，其中数字在达到某个值（模数）后“环绕” ‍
• 模运算给出除法后的余数（例如，7(mod5)=2） ‍
• 常用符号：a(modn)，或在编程语言中：a % n ‍
• 模运算中的基本运算：
  • 加法：(a+b)(modn)
  • 减法：(a−b)(modn)
  • 乘法：(a×b)(modn) ‍
• 结果始终介于 0 和 n−1 之间，从而产生“环绕”效果 ‍
• 同余：如果两个数字在除以 n 时留下相同的余数，则它们模 n 同余
  • 写为：a≡b(modn)
  • 示例：17≡2(mod5) 因为两者都留下余数 2 ‍
• 等价类将所有相互同余的整数分组在一起
  • 示例：₅[2]₅={...,−8,−3,2,7,12,17,...} ‍
• 等价类的完整集合构成剩余系统 ‍
• 在密码学中，模数通常选择为素数 ‍
• 理解模运算是密码学和零知识证明的基础，因为我们处理的数字系统使用模运算而不是“基础”算术。 ‍

参考资料和学习资源

更喜欢通过视频学习？ 查看此 YouTube 视频！ ‍

其他资源：

• 关于模运算的教科书章节
• 模运算的简短视频介绍
• RareSkills ZK 书

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