在密码学中，零知识证明(zero-knowledge proofs)或零知识协议(zero-knowledge protocols)是指一种特殊的协议。在此协议中，被称为证明者(prover)的参与方可以向被称为验证者(verifier)的参与方证明某个给定的陈述是正确的，但在此过程中不泄露除给定的陈述是正确的以外其他任何信息。本书的写作目标是为对零知识证明不熟悉的读者介绍零知识证明系统背后的数学原理及其应用。

在零知识证明协议中，所谓的零知识简洁的非交互式知识论证(zero knowledge succinct, non interactive arguments of knowledge，简写为zk-SNARKs)是特别令人感兴趣的。其令人感兴趣的原因是zk-SNARKs产生的证明远远小于为证明陈述为正确所需要的原始数据且证明者与验证者之间仅需要进行一次交互。

从实践的角度看，zk-SNARKs令人心潮澎湃的原因是zk-SNARKs具有在不泄露任何计算输入的前提下向公众证明计算是诚实的，方法是将zk-SNARKs的证明作为交易发送给公链上的实现验证者功能的智能合约。在此场景下，我们发现了一种将复杂计算外包到链下然后在公链上进行验证计算结果正确性的方法。此方法使公开可验证计算、区块链扩容和增加交易隐私性成为可能。

由于区块链和zk-SNARKs的联系，对区块链技术日益增加的兴趣也增加了人们对优秀且详细的零知识证明协议、相关应用及其标准相关资料的需求。只有充分了解zk-SNARKs的相关资料，开发者才能写出安全和高效的代码。

但是，零知识证明的细节是复杂的，更加深入的了解需要开发者熟悉数学和计算机理论学科，包括已有的计算模型和编程范式的更新。不幸的是，关于zk-SNARKs的资料散落在博客、Github 仓库和数学论文中，这使得zk-SNARKs仍旧是难以理解的，或者说是“神奇的”。资料的分散等问题阻碍了开发者探索或使用zk-SNARKs在其项目中，从而减慢了zk-SNARKs的广泛使用和向web3的过渡。

本书尝试改变这一情况。本书专门为密码学经验较少的读者设计，写作目标是尽可能缩小知识门槛并以动手进行简单的纸笔运算的方式向开发者解释抽象概念。读完并计算本书示例后，读者将掌握理解zk-SNARKs背后数学原理的所必须的概念。

本书的目标读者是希望了解zk-SNARKs基础原理以提高开发质量和安全性或希望弥补知识差距的软件工程师和智能合约工程师。本书会按照逻辑顺序依次进入各个概念，所以本书对新手或具有相关经验的读者都适用。本书假定读者对于编程具有基本的了解，并且对于逻辑思考和战略性问题解决具有热情。

你需要多少数学知识才能理解和实现零知识证明？答案是取决于你的目标的理解水平和你的应用系统所需要的安全性。在没有任何对零知识证明数学基础了解的情况下，我们也可以实现零知识证明。但是，如果要阅读基础论文、理解证明系统的内部运作或者实现一个安全且高性能的zk-SNARKs，我们需要一些数学知识。

没有扎实的数学基础，对于学习零知识证明相关概念有兴趣但没有了解过素数域(prime field)或者椭圆曲线(elliptic curve)的人可能很快就会不知所措。出现这种情况的原因不是理解所需要的数学过于复杂，而是大量的技术名词、不了解的术语和令人困惑的符号使文本难以阅读。即使是一个简单的概念，可能仍会因为上述原因而难以理解。出现这种情况容易导致读者丧失兴趣，或者是获取到一些支离破碎的知识，在最坏的情况下，这些知识会导致读者开发出不成熟且不安全的实现。

这就是为什么本书使用很大篇幅解释理解zn-SNARKs开发的基础概念所需要的数学原理。我们鼓励对基础数论和椭圆曲线不熟悉读者花费一定时间阅读相关章节，直到读者可以解决每章中的至少几个练习。读者应当重视例子中的所有细节。

本书从非常底层开始并且仅假设读者具有高中数学整数计算的基本概念。然后本书将展示乍看起来与高中数学完全不同的数字和数学结构，但在更深的层次上，实际上非常相似。这将在本书的示例中给予说明。

值得强调的是，在本书中的数学是非正式的、不完整的且经过优化以帮助读者尽可能有效的理解零知识证明相关概念。本书在设计上选择了尽可能少但必要的数学理论，侧重于丰富的数值计算。我们相信这种非正式的、示例驱动的方式使初学者在初始阶段更容易理解材料。

作为初学者，你会发现在实际开发高安全性的现实世界zk-SNARKs算法前，使用纸笔计算一个简单的zk-SNARK是有用的。

但是，为了读者可以计算这些简单的数学示例，读者需要一定的数学基础。因此，本书致力于帮助没有相关经验的读者专注于我们认为重要的概念，并附有鼓励你自行计算的练习。每节包含一系列难度逐渐提高的联系以帮助读者记忆和使用相关概念。

由于本书旨在完整介绍与初学者有关的所有主题，因此有多种方式可以阅读此书。最明显的阅读方法就是按照章节顺序线性阅读此书。如果读者几乎没有对于数学和密码学的前置知识，我们推荐这种阅读方法。我们从最基础的概念，比如自然数、素数开始，并介绍如何用不同种类的计算在这些集合中进行计算。然后，我们将继续学习代数结构，如群(group)、环(ring)、素数域(prime field)和椭圆曲线(elliptic curve)。

在本书的开始，我们开发了一个示例。随着我们学习的深入，该示例将逐渐扩展。通过这种方式，我们在成熟的密码学体系上递增构建了一些真实世界中的SNARK。这些SNARK都十分简单，我们可以通过纸笔计算以详细展示其中的每一步。

如果希望更好理解在零知识证明系统中出现的椭圆曲线，读者可以从5.6.4节快速阅读。在此节中，我们介绍了BLS6_6曲线，这是一种可以使用纸笔运算且配对友好(pairing-frendly)的椭圆曲线。在第 5 章中，我们将介绍了所有关于这条曲线的概念。开发zk-SNARKs的程序员经常面临这种情况，在进行真实实现前需要使用纸笔进行一些计算，但是这些计算通常因为加密算法使用的椭圆曲线大小而无法进行。在本书中，我们特别设计了BLS6_6曲线以实现纸笔计算。这是一条配对友好曲线，具有在没有任何计算机辅助的情况下进行基于配对的计算所需要的所有属性。这种计算有助于读者理解系统的细节。此外，我们推导出Tiny-jubjub曲线，该曲线可用于使用纸笔计算EdDSA。

如果读者对于使用纸笔从零开始构建简单zk-SNARK感兴趣，读者可以阅读所有有关三分解问题(3-factorization problem)的示例。在 示例 115 中，我们引入三分解问题作为形式语句(formal language)中的语句(statement)。如果此例子过于抽象，读者可以在 示例 124 开始，在此示例中，我们将三分解问题描述为一种代数电路(algebraic circuit)。在 示例 126 中，我们执行了此电路。在 示例 118 中。我们引入了实例(instance)和见证(witness)概念以便稍后实现各种级别的零知识证明。在 示例 120 中，我们将电路转换为关联的 Rank-1 约束系统(Rank-1 Constraint System)，并在 示例 122 中，我们计算了此问题的构造性证明(constructive proof)。在 示例 131 中，我们将约束系统(constraint system)转换为二项式算术程序(Quadratic Arithmetic Program)，并展示如何将构造性证明(constructive proof)转换为多项式整除问题(polynomial divisibility problems)。在 示例 145 中，我们使用这些示例的结果完成从三分解问题推导Groth16 zk-SNARK的过程。在 8.3 节，我们计算证明者和验证者密钥。在 示例 147 中，我们计算zk-SNARK并在 示例 148 中进行验证。在 示例 149 中，我们将展示如何模拟证明。

如果读者希望更好了解高级语言如何被编译为零知识证明系统可以接受的表示，读者可以从 第 7 章 开始阅读。在第七章中，我们推导出一种带有可以将高级语言编译为图像电路表示的brain-complier的玩具语言。像R1CS等重要的表示将在 6.2.1 中解释，构造性证明、见证和实例等核心概念将在6.1 中解释。

此节中的超链接目前均无效，但随着本书的翻译将逐渐补齐

本章主要介绍在本书中所需要的软件及其安装过程。

为了提供交互式学习体验，并允许读者亲身体验本书中所描述的抽象数学概念，我们给出了如何使用SageMath编程语言进行编程的例子。Sage是一门很好学习的语言，该语言基于Python，但对于代数对象的计算进行扩展和优化。因此，我们推荐读者在进一步深入后续章节前，下载并安装此语言。

值得注意的是，sage并不是一门轻量化语言，其下载安装将占用近 4 GB 空间。读者可以参考官网教程安装对应版本。

目前官方推荐windows用户使用WSL进行安装，实际上，官方也提供适用于windows的二进制预编译版本，读者可前往sagemath 预编译包清华镜像中下载安装包直接安装即可，请确保下载版本为 9.0 以上版本。这也是在windows下安装配置最为简单的方式。

安装完成后，读者可在命令行内键入sage，将出现以下内容:

(sage-sh):~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.3, Release Date: 2021-05-09                     │
│ Using Python 3.7.10. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘

出现此情况则证明安装成功。

为了将我们使用纸笔推导的运算转化为现实世界中的zk-SNARKs，我们给出了如何使用Circom领域专用语言来实现部分示例。Circom是一种零知识证明电路编程语言和编译器以帮助程序员设计算术电路。它使用了snarkjs作为其底层的零知识证明系统。读者可以在Circom 安装中找到其安装步骤。

译者目前尚未安装此系统，待后文需要时再行补充

本章的目标是使只掌握了基础代数水平的读者快熟掌握算术(arithmetic)。我们首先讨论基础整数算数，然后进一步讨论长除法(long division)、最大公约数和欧几里得除法(Euclidean Division)。之后，我们将介绍最为重要的使用纸笔进行的模除(modular arithmetic)技能。最后，我们将介绍多项式(ploynomial)，计算多项式对整数算术的模拟，并介绍拉格朗日插值(Largrange Interpolation)。

从某种意义上说，整数算数(integer arithmetic)是现代密码学大部分内容的核心。幸运的是，大部分读者可能仍记得在学校内学习过的整数算数。然后，重要的是，读者应自信地在本书的计算示例中使用这些概念来理解并执行运算。当然，我们会重述这些基础计算概念以实现帮助读者回忆并填补知识漏洞。

尽管在本章中讨论的术语和概念可能不会直接出现在零知识证明文献中，但了解这些名词对于阅读后续章节是必要的。

本章提出的许多观点在全球大部分学校的基础数学教育中都有所涵盖。本章所提出的大部分观点也可以在 Hongxi Wu 所编写的 Understanding numbers in elementary school mathematics¹中找到，读者也可以在 Maurice Mignotte 的 Mathematics for Computer Algebra² 中找到许多内容。与前者相比，后者更加面向计算机学科。

整数( integers 或 whole numbers )指不带小数部分的数字。\( \frac{2}{3} \), \( 1.2 \) 和 \( -1280.006 \) 等数字都不是整数。

在本书中，我们使用 \( \mathbb{Z} \) 作为整数集合的代表：

\[ \mathbb{Z} := \{\ldots, -3,-2,-1,0,1,2,3,\ldots\} \]

如果 \( a\in \mathbb{Z} \) 是一个整数，我们使用 \( |a| \) 表示 \( a \) 的绝对值( absoulte value )。绝对值指 \( a \) 的不考虑符号的非负值，如下：

\[ \begin{equation} |4|= 4 \\ |-4|= 4 \end{equation} \]

我们使用符号 \( \mathbb{N} \) 表示所有正整数，通常称之为自然数( natural numbers )。此外，我们使用 \( \mathbb{N}_{0} \) 表示所有非负整数。上述叙述说明， \( \mathbb{N} \) 不包含 \( 0 \) ，但 \( \mathbb{N}_{0} \) 包含：

\[ \begin{align*} \mathbb{N} := \{1,2,3,\ldots\} & & \mathbb{N}_{0} := \{0,1,2,3,\ldots\} \end{align*} \]

此外，我们使用符号 \( \Bbb{Q} \) 表示有所有有理数(rational numbers)构成的集合。该集合是由所有分数 \( \frac{n}{m} \) 构成的，其中 \( n \in \Bbb{Z} \) 是一个整数且 \( m \in \Bbb{N} \) 是一个自然数。

在集合 \( \Bbb{N}\)、 \( \Bbb{Z}\) 和 \( \Bbb{Q} \) 上定义了加法和乘法的概念。我们大多数人可以在大脑中进行许多整数运算，但随复杂度的增加，在大脑中进行计算变得复杂。我们通常使用Sagemath进行复杂计算(我们会在本书稍后部分定义环和域)：

sage: ZZ # Sage 对整数集合的表示
Integer Ring
sage: NN # Sage 对自然数集合的表示
Non negative integer semiring
sage: QQ # Sage 对有理数集合的表示
Rational Field
sage: ZZ(5)
5
sage: ZZ(5) + ZZ(3)
8
sage: ZZ.random_element(10**6)
455617

我们特别感兴趣的数字集合是素数(prime numbers)。素数指自然数 \( p \in \Bbb{N} \) 在满足 \(p \ge 2\) 条件下，其只能被它本身和 \(1\) 整除。除了 \(2\) 以外的所有素数被称为奇素数(odd prime numbers)。我们使用 \( \Bbb{P} \) 表示所有素数构成的集合，使用 \( \Bbb{P}_{\ge 3}\) 表示奇素数。

素数集合 \( \Bbb{P} \) 是一个无限集合且可以按照数字大小进行排序。这意味着对于任何一个素数 \( p \in \Bbb{P} \) ，都存在另一个素数 \( p' \) 使得\( p < p' \) 。结论是没有最大的素数。将所有素数按大小排序，我们写出：

\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, \ldots\]

算术基本定理(fundamental theorem of arithmetic)告诉我们，在某种意义上素数是构成其他自然数的基本组件，或者说，每一个自然数都可以通过素数彼此相乘获得。假设 \( n \in \Bbb{N} \) 且 \( n > 1 \) ，存在素数 \( p_1, p_2, \ldots, p_k \in \Bbb{P} \)，那么存在:

\[ n = p_1 \cdot p_2 \cdot \ldots \cdot p_k \ \]

除了因子的顺序，该分解对于任何自然数都是不同。我们称上述分解为 \(n\) 的质因数分解(prime factorization)

示例 1 质因数分解

为了使读者理解质因数分解概念，我们此处给出对数字 \( 504 \in \Bbb{N} \) 的分解。分解方法是使 \(504\) 依次除以从 \(2\) 开始的素数，分解结果如下：

\[504 = 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 7\]

我们可以通过Sage检查此结果，该程序提供了自然数质因数分解算法：

sage: n = NN(504)
sage: factor(n)
2^3 * 3^2 * 7

上述计算揭示了一个重要的结论：计算一个整数的质因数分解在运算上是昂贵的，因为我们必须重复除以所有小于该数的素数，直到所有因子都是素数本身。由此，出现了一个重要的问题：计算自然数质因子分解的速度到底有多快？ 这个问题就是著名的整数因子分解问题(integer factorization problem)。据我们所知，目前仍没有比将待分解的数除以按升序排列的所有素数这一朴素方法更快的分解方法。

在另一方面，计算给定集合的素数的乘积是快速的。我们发现素数相乘与其逆过程，即自然数的质因子分解在计算资源耗费上完全不同。质因子分解问题是单向函数(one-way function)的一个例子。所谓单向函数指一种在某一方向计算简单但逆向计算复杂的可逆函数(nvertible function)。

计算是否可行取决于我们拥有的计算资源。当前自然数的质因子分解没有多项式时间内实现的算法。但是，美国数学家 Peter W. Shor 在 1994 年开发了一种在量子计算机上使用的可在多项式时间内完成的自然数质因子分解算法¹。因此，当前依赖于自然数质因子分解的加密算法(如 RSA 算法)将在量子计算机出现后变得不安全。

练习 1. 计算 -123, 27 和 0 的绝对值。

练习 2. 对 30030 进行质因数分解并使用sage进行检查

练习 3. 已知如下方程：

\[ 4 \cdot x + 21 = 5\]

计算符合以下假定的 \(x\) 的所有解：

1. 方程定义在自然数集上
2. 方程定义在整数集上

练习 4. 已知以下方程：

\[2 x^3 - x^2 - 2 x = - 1\]

计算符合以下假设的所有解：

1. 方程定义在自然数集上
2. 方程定义在整数集上
3. 方程定义在有理数集上

正如我们在高中数学中了解的那样，对整数进行加减乘产生的结果仍属于整数。与之不同，除法产生的结果有时不属于整数，比如 \(7\) 除以 \(3\) 的结果不属于整数。但是如果使用带余除法(division with a remainder)进行除法，产生的结果属于整数。比如，\(7\) 除以 \(3\) 等于 \(2\) ，余数为 \(1\)，因为\( 7 = 2 \cdot 3 + 1\) 。

在本节内，我们将介绍整数带余除法，也被称为欧几里得除法(Euclidean Division) 。带余除法是本书中许多概念的基础技术。下面给出了一个对带余除法的精确定义：

假设存在整数 \(a \in \Bbb{Z}\) 和整数 \(b \in \Bbb{Z}\) 且 \(b \neq 0 \) ，另存在 整数 \( m \in \Bbb{Z} \) 和自然数 \(r \in \Bbb{N} \) 且 \( 0 \leq r <|b| \) 满足以下条件：

\[a = m \cdot b + r \]

上述使用 \(b\) 对 \(a\) 的分解被称为欧几里得除法。在此除法中，我们称 \(a\) 为被除数(dividend)，\(b\) 为除数(divisor)，\(m\) 为商(quotient)，而 \(r\) 被称为余数(remainder)。可以证明，只要除数不为 \(0\) ，对于一个整数进行带余除法产生的商和余数都是唯一的。

符号 1

假设数 \(a\) 、 \(b\) 、 \(m\) 和 \(r\) 符合上述公式。我们使用以下符号表示带余除法的商和余数：

\[ \begin{align*} a\ div\ b: = m && a\ mod\ b: = r \end{align*} \]

如果 \(a\ mod\ b = 0\) 成立，我们可以称整数 \(a\) 可以被另一个整数 \(b\) 整除。 在这种情况下，我们写成\(b|a\) ，并且称整数 \(a\ div\ b\) 是 \(b\) 对 \(a\) 的共因子(cofactor)。

简而言之，带余除法是一个整数除以另一个整数的产生商和非负的余数的过程。其中余数小于除数的绝对值。

示例 2

因为 \(-17 = -5 \times 4 + 3 \) 是 \(-17\) 对 \(4\) 的带余除法。使用上文定义的符号和定义， \(-17\) 是被除数，而 \(4\) 是除数。可以使用以下表示：

\[ \begin{align*} {-17}\ div\ 4 = {-5} && {-17}\ mod\ 4 = 3 \end{align*} \]

根据定义，余数是非负数。根据上述运算，我们也可以知道 \(-17\) 不能被 \(4\) 整除，因为余数不为 \(0\) 。这意味着表达式 \(4|{-17}\) 的真值为 False 。当然，\(4|12\) 的真值为True，因为 \(12\) 可以被 \(4\) 整除，即 \(12\ mod\ 4 = 0\)。我们也可以使用sage进行实现：

sage: ZZ(-17) // ZZ(4) # 整数商
-5
sage: ZZ(-17) % ZZ(4) # 余数
3
sage: ZZ(4).divides(ZZ(-17)) # 整除测试
False
sage: ZZ(4).divides(ZZ(12))
True

备注 1

在上文中，我们根据带余除法定义了 a div b 和 a mod b 符号。但是，需要注意的是在很多编程语言(如Python和Sage)以不同方式实现了 / 和 % 符号。程序员需要特别注意数学符号和编程实现的差异，这可能导致进行密码学实现时出现细微的错误。

举一个例子，考虑被除数 \(-17\) 和 除数 \(-4\) 。注意，与上文的例子不同，此处的除数为负数。根据我们的定义，有：

\[ \begin{align*} {-17}\ div\ {-4} = {5} && {-17}\ mod\ {-4} = 3 \end{align*} \]

\({-17} = 5 \times (-4) + 3\) 是 \(-17\) 除以 \(-4\) 的带余除法结果(根据定义，余数是一个非负数)。但是，在Sage中使用 / 和 % 进行计算会获得一个不同的结果：

sage: ZZ(-17) // ZZ(-4) #商
4
sage: ZZ(-17) % ZZ(-4) # 余数
-1
sage: ZZ(-17).quo_rem(ZZ(-4))
(4, -1)

计算整数带余除法的方法被称为整数除法算法(integer division algorithms)。最著名的算法被称为长除法(long division) 。很多人可能在学校内学习过此算法。简而言之，长除法算法从左到右依次循环计算出除数的每一位，在每次循环减去除数的最大可能倍数(在位数层面)。倍数成为商的位数，余数是被除数的第一位。

长除法这段翻译的比较垃圾，可能是因为直译的原因，但考虑到读者应该都学习过长除法，所以暂且不再修改。

由于长除法是进行十进制数字进行纸笔除法运算的标准方法，在本书的大量进行纸笔计算的例子中，我们会经常使用长除法，所以读者应该熟悉此方法。但是，我们没有给出长除法的标准定义而是使用提供了一系列计算示例，因为这样可以使过程更加清晰。

示例 3

举一个长除法计算的示例，我们计算 \(a = 143785\) 除以 \(b=17\) 的结果。我们希望获得带余除法的标注形式，即 \(143785 = m \cdot 17 + r\) 的形式。竖式计算过程如下：

$$ \begin{array}{r} 8457 \\ 17 {\overline{\smash{\big)} 143785} } \\ \underline{136\phantom{000} } \\ 77\phantom{00} \\ \underline{ 68 } \phantom{00}\\ 98 \phantom{0}\\ \underline{ 85 } \phantom{0} \\ 135 \\ \underline{ 119 } \\ 16 \end{array} $$

由此，我们计算得到了 \(m = 8457\) 而 \(r = 16 \)，即 \(143785 = 8457 \times 17 + 16 \)。我们可以通过Sage进行验算：

sage: ZZ(143785).quo_rem(ZZ(17))
(8457, 16)
sage: ZZ(143785) == ZZ(8457)*ZZ(17) + ZZ(16)
True

练习 5. 长除法

找到 \(m \in \Bbb{Z} \) 和 \(r \in \Bbb{N} \) ，要求 \( 0 \leq r < |b| \) 使得 \(a = m \cdot b + r \) 对以下数组成立：

• \( (a, b) = (27, 5) \)
• \( (a,b)=(27,-5) \)
• \( (a,b)=(127,0) \)
• \( (a,b)= (-1687, 11) \)
• \( (a,b)= (0, 7) \)

在哪种情况下您的结果是唯一的？

练习 6. 长除法算法

使用您熟悉的编程语言实现整数的长除法算法并正确处理边缘情况。

练习 7. 二进制表示

编写一个算法以实现计算任何非负整数的二进制表示

本书最重要的部分之一是模运算及其在素数域(prime fields)计算中的应用。前者定义在3.3，后者定义在4.3.1。为了方便进行模运算，我们需要熟悉用于计算最大公约数(greatest common divisor，简写为GCD)¹的扩展欧几里得算法(Extended Euclidean Algorithm)。

两个非零整数 \(a\) 和 \(b\) 的最大公约数被定义为可以被 \(a\) 和 \(b\) 整除的最大非零自然数 \(d\)，即在 \(d | a\) 和 \(d | b\) 都成立的情况下的最大非零自然数 \(d\) 。我们使用 \( gcd(a,b) := d \) 表示最大公约数。由于自然数 \(1\) 可被任何其他整数整除，所以 \(1\) 是任何两个非零整数的公约数，但 \(1\) 不一定是最大公约数。

一个常用来计算最大公约数的方法是欧几里得算法。但是，在本书中我们不需要此算法，我们将介绍扩展欧几里得算法。此算法可以计算两个自然数 \(a\) 和 \(b \in \Bbb{N} \) 的最大公约数，并附加有两个整数 \(s, t \in \Bbb{Z} \) 满足以下等式:

\[gcd(a,b) = s \cdot a + t \cdot b \]

以下伪代码展示了如何使用扩展欧几里得算法计算最大公约数和 \(s\) 、 \(t\) ：

由于不知道如何使用mathjax进行伪代码输入，所以此处使用了图片。

该算法非常简单，可以在纸笔计算中有效使用。我们经常将此算法的中间过程写成一个表，在表内填入\(r\)、 \(s\) 和索引 \(k\) 的值。下面的例子给出了一个简单的计算执行过程。

示例 4

为解释扩展欧几里得算法，我们假设 \(a = 12 \)、 \(b = 5\)。由于 \(12,5 \in \Bbb{N} \) 且 \(12 \ge 5 \)。算法要求均被满足，我们可以进行如下计算：

\[ \begin{array}{c|ccc|cc} k & r_k & s_k & t_k & q_k\\ \hline 0 & 12 & 1 & 0 & \\ 1 & 5 & 0 & 1 &\\ 2 & 2 & 1 & -2 & 2 \\ 3 & 1 & -2 & 5 & 2 \\ 4 & 0 & & \\ 5 & \cdot & &\\ \end{array} \]

从上述表格中，我们可以得到 \(12\) 和 \(5\) 的最大公约数为 \(gcd(12,5) = 1 \) 并且得到了 \(1 = (-2) \times 12 + 5 \times 5 \)。使用Sage检查结果：

sage: ZZ(12).xgcd(ZZ(5)) # gcd(a,b),s,t
(1, -2, 5)

练习 8. 扩展欧几里得算法

找到整数 \(s, t \in \Bbb{Z} \) 使得 \(gcd(a, b) = s \cdot a + t \cdot b \) 成立：

• \((a, b) = (45, 10) \)
• \((a, b) = (13, 11) \)
• \((a, b) = (13, 12) \)

练习 9. 走向素数域

存在 \(n \in \Bbb{N} \) 属于自然数， \(p\) 是一个素数，满足 \(n < p\) 。最大公约数 \(gcd(p,n)\) 是多少？

练习 10. 找到所有 \(k \in \Bbb{N} \) 且 \(0 \geq k \geq 100 \)，满足 \(gcd(100, k) = 5 \)

练习 11. 证明对所有 \(n,m \in \Bbb{N} \) 都存在 \(gcd(n,m)=gcd(n+m,m) \)

互素(Coprime integers，亦译为互质)指整数不存在共同的素数因子。正如我们在 3.3 节 中看到的，互素对于我们非常重要。因为在模运算中，涉及互素的计算与非互素的计算非常不同(参见 3.3.2 节)

判断两个整数是否互质的简单方法是将这两个数依次与小于其的素数相除，判断它们是否共享素因子。另一种判断互素的方法是计算两个整数的最大公约数，当最大公约数为 1 时，则互素。显然，计算最大公约数的方法更加高效。

示例 5

再次考虑 示例 4。正如我们所看到的，12 和 5 的最大公约数为 1 。这说明 12 和 5 是互素的，因为除了 1 没有其他共同的素数因子。

目前为止，我们使用的整数表示体系被称为十进制体系(decimal positional system)。在此体系中，我们将任何整数表示为由十进制数字集合 \(\{0,1,2,3,4,5,6,7,8,9\} \) 中的元素构成的序列。需要强调的是，计算机科学和密码学中存在其他整数表示方法：

所谓二进制体系(binary positional system)指任何整数都是由二进制数字(或称为位)集合 \(\{0,1\}\) 构成的元素序列表示。更加准确的说，设 \(n \in \Bbb{N}_{0} \) 是一个使用十进制表示的非负整数， \(b=b_{k-1}b_{k-2}\ldots b_{0} \) 是由位 \(b_j \in \{0,1\} \subset \Bbb{N}_0 \) 构成的序列，其长度为正整数 \(k \in \Bbb{N}\) 。如果下式成立，则 \(b\) 是 \(n\) 的二进制表示：

\[ n = \sum_{j=0}^{k-1} b_j\cdot 2^j \]

在这种情况下，我们将 \(n\) 的二进制表示记为 \(Bits(n):= b_{k-1}b_{k-2}\ldots b_{0}\) ，并称 \(n\) 是一个 \(k\) 位数(k-bit number)， \(k:= |n|_2\) 是 \(n\) 的位长(bit length)。

可以证明，如任何非负数的二进制表示都是唯一的。我们称 \(b_0\) 是最低有效位(least significant bit)，\(b_{k-1}\) 是最高有效位(most significant bit)，同时定义整数的汉明权重(Hamming weight)是其二进制表示中 \(1\) 的数量。

另一种常用的表示方法被称为十六进制系统(hexadecimal positional system)。该标识系统将每个整数表示为一组 16 个字符构成的序列。通常情况下，我们选择的字符为 \(\{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f\} \)。

如无特殊说明，在本书中，我们将使用十进制表示数字。值得注意的是，在现实世界的密码学系统中，我们经常需要处理大整数。在这种情况下，我们一般选择十六进制系统，因为十六进制相比于十进制表示一个整数的长度更短。

sage: NN(27713).str(2) # 二进制表示
'110110001000001'
sage: NN(27713).str(16) # 十六进制表示
'6c41'

如果某个进制系统选择了 \(k\) 进制，使用以下字符集 \(\{d_0,d_1,\ldots, d_{k-1}\}\) 表示一个整数的结果为 \(d_{j_h}\cdots d_{j_1} d_{j_0}\)。我们可以通过以下公式将其转化为由十进制表示的整数 \(n\) ：

\[ n = \sum_{i=0}^h j_i\cdot k^{i} \]

通过类似公式，我们可以将一个整数从当前的进制系统转化到任何其他进制系统。因此，十进制并不是特殊的，只是最常见的。为了处理进制产生的歧义，许多计算机系统使用在数字前增加前缀的方法标识当前整数所处的进制体系。常见的前缀有：

\[ \begin{array}{cc} 0x & hexadecimal \\ 0b & binary \end{array} \]

示例 6

为理解整数表达式和整数本身的不同，请将表达式 \(11\) 视为整数表达。请注意，在不声明进制的情况下，此表达式是有歧义的。它有可能表示十进制系统的整数 \(11\)，也有可能是二进制中的\(11\)，该值等同于十进制中的\(3\)。当然，\(11\) 也可能指十六进制系统内的数字，其等同于十进制中的 \(17\)。为澄清歧义，我们有必要在整数前增加前缀：

\[ \begin{array}{cc} 0x11 &= 17 \\ 0b11 &= 3 \end{array} \]

示例 7

使用上述公式将十六进制数字 \(\{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f\} \) 转化为十进制：

\[\{0_0,1_1,2_2,3_3,4_4,5_5,6_6,7_7,8_8,9_9,a_{10},b_{11},c_{12},d_{13},e_{14},f_{15}\}\]

如果你想转化 \(y=0x3f7a\) 为十进制进制，你需要将其写为 \(0x3_3f_{15}7_7a_{10}\) ，然后使用对应公式进行转化，如下：

$$ \begin{align*} n&=\sum_{i=0}^4 j_i\cdot 16^{i} \\ &=10\cdot 16^0+7\cdot 16^1+15\cdot 16^2+3\cdot 16^3 \\ &= 16250 \end{align*} $$

练习 13. 已知八进制系统，通常使用 \(\{0,1,2,3,4,5,6,7\}\) 作为表示集合。使用八进制的数字通常带有前缀 \(0o\) 。请写出 \(0o1354\) 和 \(0o777\) 的十进制表示。

模运算(Modular arithmetic)是一种特殊的整数运算体系。在模运算中，数字在到达某一特定值后会“回绕”，与在时钟上的运算类似，每当指超过 12 时就会出现回绕。比如，当前时钟显示为 11 点，那么 20 小时后是 7 点，而不是 31 点。数字 31 在显示小时的普通时钟上是没有意义的。

发生回绕的数字被称为模(modulus)。模运算将时钟上的运算推广到任何模数中，并研究在这种新的体系中的公式和现象。模运算对于理解大部分现代密码学都是极其重要的，因为模运算提供了代数系统的运算基础设施。这些代数系统提供了密码学上有用的单向函数。

尽管模运算与我们熟悉的普通整数运算非常不同，但我们鼓励读者学习示例，并进一步发现当我们熟悉模运算后，模运算并不令人望而生畏。对于模运算更加详细的介绍和在数论中的应用在 Hardy 等人编写的 An Introduction to the Theory of Numbers¹ 的第 5-8 章内找到。

在下文中，令 \(n \in \Bbb{N}\) 且 \(n \geq 2\) 是一个固定的自然数，我们称 \(n\) 为模运算体系的模(modulus)。当给定 \(n\) 后，我们可以将整数分类：当两个整数对 \(n\) 进行带余除法得到的余数相同，我们则认为两个整数属于一类。属于同一类的两个数之间的关系被称为同余(congruent)。

示例 8

在时钟计算中，模数 \(n = 12 \)。在此体系内，整数 \(-7,5,17,29\) 为同余关系，因为这些整数与 \(12\) 进行带余除法获得的余数都为 \(5\) 。假设存在一个 12 小时制的时钟，从 5 点钟开始，增加 12 小时，在表盘上显示为 5 点钟，但其也代表 17 。同理，如果我们减去 12 小时，表盘上仍显示 5 点钟，但其也代表 -7 。

使用带余除法，我们可以将对于同余的直觉转化为适当的数学定义。设 \(a,b \in \Bbb{Z}\) 均为整数，另存在 \(n \in \Bbb{N} \) 且满足 \(n \geq 2 \) 。那么当以下等式成立时，我们就称 \(a\) 与 \(b\) 对于模 \(n\) 同余(congruent with respect to the modulus)。

\[a\ mod\ n = b\ mod\ n\]

上述也可表示为:

\[a \equiv b\ (mod\ n)\]

练习 14. 下列那一对数在模 13 的情况下全等：

• \((5,9)\)
• \((13,0)\)
• \((-4,9)\)
• \((0,0)\)

练习 15. 找到所有满足 \(x \equiv 4\ (mod\ 6)\) 的整数

$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } $$ 在上文中，我们已经定义了同余关系，现在的问题是我们是否可以像操作等式一样操作同余关系。事实上，我们可以将等式的替换规则(substitution rule)应用于同余关系中，但与等式的替换规则不同，对于任意的非零整数 \(k \in \Z\)，只有在 \(k\) 与 \(n\) 互素时，同余式 \(a ≡ b\ ( mod\ n )\) 与 \(k \cdot a ≡ k \cdot b\ (mod\ n) \) 相等。

设整数 \(a_1,a_2,b_1,b_2, k\in\Bbb{Z}\)。以下规则适用于同余规则：

• \(a_1 ≡ b_1\ (mod\ n) \Leftrightarrow a_1+k ≡ b_1+k\ (mod\ n) \)
• \(a_1 ≡ b_1\ (mod\ n) \Rightarrow k \cdot a_1 ≡ k \cdot b_1\ (mod\ n) \)
• \(gcd(k,n)=1\) 且 \(k \cdot a_1 ≡ k \cdot b_1\ (mod\ n) \Rightarrow a_1 ≡ b_1\ (mod\ n) \)
• \(k \cdot a_1 ≡ k \cdot b_1\ (mod\ k \cdot n) \Rightarrow a_1 ≡ b_1\ (mod\ n) \)
• \(a_1 ≡ b_1\ (mod\ n)\) 且 \(a_2 ≡ b_2\ (mod\ n) \Rightarrow a_1+a_2 ≡ b_1+b_2\ (mod\ n)\)
• \(a_1 ≡ b_1\ (mod\ n)\) 且 \(a_2 ≡ b_2\ (mod\ n) \Rightarrow a_1 \cdot a_2 ≡ b_1 \cdot b_2\ (mod\ n)\)

与传统整数计算不同的是。同余关系符合费马小定理(Fermat's Littile Theorem)。简单来说，在模运算中，每个数的素数幂次与该数本身同余。更加精确的表述为，设素数 \(p \in \Bbb{P}\) ，且整数 \(k \in \Bbb{Z}\) ，满足以下公式：

\[k^p ≡ k\ (mod\ p)\]

如果 \(k\) 与 \(p\) 互素，我们可以在上述同余式两边同除 \(k\) ，得到以下等式：

\[k^{p-1} \equiv 1\ (mod\ p)\]

下列Sage代码展示了费马小定理的示例，并强调了底数 \(k\) 与 \(p\) 的互素情况(\(k=64,p=137\))和不互素的情况(\(k=1918,p=137\))：

sage: ZZ(137).gcd(ZZ(64))
1
sage: ZZ(64) ^ ZZ(137) % ZZ(137) == ZZ(64) % ZZ(137)
True
sage: ZZ(64) ^ ZZ(137 - 1) % ZZ(137) == ZZ(1) % ZZ(137)
True
sage: ZZ(1918).gcd(ZZ(137))
137
sage: ZZ(1918) ^ ZZ(137) % ZZ(137) == ZZ(1918) % ZZ(137)
True
sage: ZZ(1918) ^ ZZ(137-1) % ZZ(137) == ZZ(1) % ZZ(137)
False

以下示例包含了本节介绍的大部分概念。

示例 9

为了更好理解同余，我们对以下同余方程进行求解：

\[7\cdot(2x+21) + 11 \equiv x - 102\ (mod\ 6)\]

因为同余式与等式的变换规则有或多或少的相似，我们可以安装与求解等式方程时类似的方法进行同余方程的求解。我们对同余方程的右侧进行化简：

\[7\cdot(2x+21) + 11 = 14x + 147 + 11 = 14x + 158\]

基于上述表达式，我们可以将同余方程写为：

\[14x + 158 \equiv x - 102\ (mod\ 6)\]

在接下来的步骤中，我们希望将当前等式转化为仅有包含 \(x\) 的项在左侧，其他项在右侧的形式。 变化过程如下：

\[ \begin{multline*} 14x + 158 \equiv x - 102\ (mod\ 6) \Leftrightarrow\\ 14x - x + 158 - 158 \equiv x -x - 102 - 158\ (mod\ 6) \Leftrightarrow \\ 13x \equiv -260\ (mod\ 6) \end{multline*} \]

如果同余方程只是一个正常的整数方程，我们可以通过两边同除 13 获得 \(x=-20\) 的结果。但是，在同余方程中，我们需要保证模数和我们需要除去的数为互素关系，这可以保证除法结果与原式等价。这意味这我们需要计算 \(gcd(13,6)\) 。由于 13 是素数且 6 不是 13 的因子，我们得到 \(gcd(13,6)=1\)，所以 13 和 6 为互素关系。因此，我们可以在同余方程两侧同除 13，如下:

\[13x \equiv -260\ (mod\ 6) \Leftrightarrow x \equiv -20\ (mod\ 6)\]

我们现在的任务是找到所有的整数 \(x\) 满足 \(x\) 与 \(-20\) 在模 \(6\) 的条件下同余。换言之，我们需要找到所有满足以下等式的 \(x\)：

\[x\ (mod\ 6) = -20\ (mod\ 6)\]

因为 \(-4 \times 6 + 4 = -20\)，我们知道 \(-20\ mod\ 6 = 4\)，所以 \(x=4\) 是同余方程的一个解。但是，\(22\) 是另一个答案，因为 \(22\ (mod\ 6)=4\)。还有一个答案是 \(-20\) 。事实上，满足此方程的解构成以下集合：

\[ \{\ldots, -8,-2, 4,10, 16,\ldots\} = \{4+k\cdot 6 ;|; k\in \Bbb{Z}\} \]

总结来说，我们证明了\(7\cdot(2x+21) + 11 \equiv x - 102\ (mod\ 6)\) 的解为 \(\{x = 4+k\cdot 6 ;|; k\in \Bbb{Z}\} \) 。我们从此解集内任取两个数，\(x=4\) 和 \(x=4+12 \times 6 = 76\) 使用Sage验证：

sage: (ZZ(7)* (ZZ(2)*ZZ(4) + ZZ(21)) + ZZ(11)) % ZZ(6) == (ZZ(4) - ZZ(102)) % ZZ(6)
True
sage: (ZZ(7)* (ZZ(2)*ZZ(76) + ZZ(21)) + ZZ(11)) % ZZ(6) == (ZZ(76) - ZZ(102)) % ZZ(6)
True

如果您到现在仍不熟悉模运算，并且移位模运算看起来如此复杂而气馁，您应记住两件事。第一，在模运算中计算同余并不比在您更熟悉的数学体系(如有理数体系)中的计算复杂，这只是一个习惯问题。其次，当我们在 3.3.4 节 引入同余类表示的概念，计算会变得更加清晰和易于处理。

练习 16. 已知在模 13 的情况下，计算以下同余方程的所有解 \(x \in \Bbb{Z}\) ：

\[\kongru{5x+4}{28+2x}{13}\]

练习 17. 已知在模 23 的情况下，计算以下同余方程的所有解 \(x \in \Z\) ：

\[\kongru{69x}{5}{23}\]

练习 18. 已知在模 23 的情况下，计算以下同余方程的所有解 \(x \in \Z\) ：

\[\kongru{69x}{46}{23}\]

练习 19. 设 \(a,b,k \in \Z \)，满足 \(\kongru{a}{b}{n}\) 。证明 \(\kongru{a^k}{b^k}{n}\)

练习 20. 设 \(a,n \in \Z \)，满足 \(a\) 和 \(n\) 互不互素。对于 \(b \in \Z \)，同余方程 \(\kongru{a \cdot x}{b}{n}\) 有解 \(x\)。请说明 \(b\) 需要满足的条件及求出方程的解集。

$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } \gdef\vecshow#1#2{#1_1, \ldots #1_k \in \Bbb{#2} } $$

我们已经学习了如何求解模运算中的同余方程。在此节，我们可以学习到如何使用中国剩余定理(Chinese Remainder Theorem，亦译为孙子定理)求解不同模下的同余系统。在满足任意的 \(k \in \Z\) 及与其互素的自然数 \(\vecshow{n}{N}\)，和整数 \(\vecshow{a}{Z}\) 条件下，所谓 联立同余(simultaneous congruences)¹ 问题(见下式)会有解，并且此时同余体系所有可能的解都是同余体系中的模的乘积 \(N = n_1 \cdot \ldots \cdot n_k\)：

\[ \begin{array}{c} \kongru{x}{a_1}{n_1} \\ \kongru{x}{a_2}{n_2} \\ \cdots \\ \kongru{x}{a_k}{n_k} \\ \end{array} \]

求解方法如下：

示例 10

为了解释如何使用中国剩余定理求解联立同余问题，我们展示一个同余系统:

\[ \begin{array}{c} \kongru{x}{4}{7} \\ \kongru{x}{1}{3} \\ \kongru{x}{3}{5} \\ \kongru{x}{0}{11} \\ \end{array} \]

显然，所有的模都是互素的(因为它们都是素数)。现在我们进行如下计算：

\[ \begin{array}{l} N = 7 \cdot 3 \cdot 5 \cdot 11 = 1155\\ N_1 = 1155/7 = 165\\ N_2 = 1155/3 = 385\\ N_3 = 1155/5 = 231\\ N_4 = 1155/11 = 105\\ \end{array} \]

在上述计算的基础上，我们使用扩展欧几里得算法：

\[ \begin{array}{cccc} 1 = & 2 \cdot 165 & + & -47 \cdot 7 \\ 1 = & 1 \cdot 385 & + & -128 \cdot 3 \\ 1 = & 1 \cdot 231 & + & -46 \cdot 5 \\ 1 = & 2 \cdot 105 & + & -19 \cdot 11 \\ \end{array} \]

结果，我们得到了 \(x = 4 \cdot 2 \cdot 165 + 1 \cdot 1 \cdot 385 + 3 \cdot 1 \cdot 231 + 0 \cdot 2 \cdot 105 = 2398\) 是联立同余问题的一个解。因为 \(2398\ mod\ 1155 = 88\)，所以所有解构成的集合为 \(\{\ldots, -2222, -1067,88,1243, 2398, \ldots\} \)

我们也可以使用Sage的中国剩余定理(CRT)函数对上述求解进行检查：

sage: CRT_list([4, 1, 3, 0], [7, 3, 5, 11])
88

$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } \gdef\Zmod#1#2{#1\ \text{mod}\ #2} $$ 正如我们在上文中的各种示例见到的那样，计算同余式麻烦的，且解集通常较大。因此，找到一些方法简化模运算是有必要的。

当我们识别出某集合内的数进行模运算具有相同的余数，该集合被称为在模 \(n\) 体系中的同余类(remainder class 或 residue class)。使用同余类可以有效简化模运算。

根据带余除法的性质可以得到对于每个模 \(n\) 都有 \(n\) 个不同的同余类，对于整数的加法和乘法可以投影为同余类上的一种新的加法和乘法。

通俗的说，新的加法和乘法是通过取第一个同余类的任一元素与第二个同余类的一些元素进行正常的加法或乘法，然后判断产生的结果属于哪一个同余类。下面的例子使上述的抽象描述更加具体。

示例 11

选择模数 \(n=6\) ，此体系存在 6 个同余类。当我们使用余数标识每一个同余类，我们得到以下表示:

\[ \begin{array}{ccc} 0: = \{\ldots, -6,0,6,12, \ldots \}\\ 1: = \{\ldots, -5,1,7,13, \ldots \}\\ 2: = \{\ldots, -4,2,8,14, \ldots \} \\ 3: = \{\ldots, -3,3,9,15, \ldots \}\\ 4: = \{\ldots, -2,4,10,16, \ldots \}\\ 5: = \{\ldots, -1,5,11,17, \ldots \} \end{array} \]

假如我们需要计算 \(2+5\) 在模 6 体系内的结果，我们可以找到\(2\) 和 \(5\) 对应同余类的元素，此处我们选择 \(14\) 和 \(-1\)。对其进行正常的加法，结果为 \(14+(-1)=13\)。查找此结果对应的同余类为 \(1\)。

因此，我们得到 \(2+5=1\) 在模 6 体系内，另一种更加易读的使用同余式表示方式为 \(\kongru{2+5}{1}{6}\)

推而广之，模运算中的加法和乘法可以转化为同余类上的代表元素正常的加法和乘法。下表总结了模 6 体系内所有同余类的加法和乘法:

\[ \begin{array}{c | c c c c c c} + & 0 & 1 & 2 & 3 & 4 & 5\\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0\\ 2 & 2 & 3 & 4 & 5 & 0 & 1\\ 3 & 3 & 4 & 5 & 0 & 1 & 2\\ 4 & 4 & 5 & 0 & 1 & 2 & 3\\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \end{array} \quad \quad \quad \quad \begin{array}{c | c c c c c c} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 2 & 3 & 4 & 5\\ 2 & 0 & 2 & 4 & 0 & 2 & 4\\ 3 & 0 & 3 & 0 & 3 & 0 & 3\\ 4 & 0 & 4 & 2 & 0 & 4 & 2\\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \end{array} \]

这样，我们定义了一个新的算数体系。在此体系内仅包含 6 个数字且有子集的加法和乘法定义。我们将此算数体系称为模 6 算术(modular 6 arithmetic)，并将其关联类型(associated type)记为 \(\Z_6\) 。

要了解为什么使用同余类进行模运算是有效的且可以大幅简化同余计算，让我们重新回到 示例 9 的同余方程:

\[ \kongru{7\cdot(2x+21) + 11}{x-102}{6} \]

如 示例 9 所示，同余式的运算与正常算术不同：比如，进行除法需要检查模数和被除数是否互素，并且解通常不是唯一的。

我们可以将上述同余方程通过投影到同余类(projecting onto the remainder classes)转化到 \(\Z_6\) 体系内：由于 \(\Zmod{7}{6}= 1\)、\(\Zmod{21}{6}= 3\)、\(\Zmod{11}{6}= 5\) 和 \(\Zmod{102}{6}= 0\)，我们得到下式：

$$ \begin{align*} \kongru{7\cdot(2x+21) + 11}{x-102}{6} \text{ over } \Z \\ \Leftrightarrow & 1\cdot (2x+3) + 5 = x \text{ over } \Z_6 \end{align*} $$

我们可以利用上文给出的加法和乘法表进行方程求解，就像我们求解正常方程一样：

$$ \begin{align*} 1\cdot (2x+3) + 5 &= x & \text{ }\\ 2x+3 + 5 &= x & \text{\# addition table:} 3+5 = 2 \\ 2x+2 &= x & \text{\# add 4 and $-x$ on both sides} \\ 2x+2 +4 -x &= x + 4 -x & \text{\# addition table: } 2+4 = 0 \\ x &= 4 & \end{align*} $$

正如我们所见，尽管使用同余类进行加法和乘法的规则有些陌生，但使用这种方式解决同余方程与解决正常的等式方程的过程极其类似。

我们可以使用 sage 对模 6 体系内的运算进行验证:

sage: Z6 = Integers(6)
sage: Z6(2) + Z6(5)
1
sage: Z6(7) * (Z6(2) * Z6(4) + Z6(21)) + Z6(11) == Z6(4) - Z6(102)
True

备注 2

本备注主要涉及 k位模数(k-bit modulus) 问题。

在密码学论文中，我们经常可以读到类似“[...] 使用了 4096 位模数”([. . .] using a 4096-bit modulus) 。这意味着加密系统使用的模运算的模数在二进制表示中长度位 4096 位。相反，数字 6 的二进制表示为 110，因此在 示例 11中，我们描述的是 3位模数系统。

练习 13. 将 \(\Z_{13}\) 定义为类似 示例 11 的模 13 算术体系。然后将上述同余方程在 \(\Z_{13}\) 体系内重新求解。

$$ \gdef\kongru#1#2#3{ #1 \equiv #2\ (\text{mod}\ #3) } \gdef\Zdiv#1#2{#1\ \text{div}\ #2} $$ 正如我们所致，整数可以进行加法、减法和乘法预算且运算结果仍属于整数，但是对于除法，并非如此：如\(3/2\) 就不是一个整数。为了更加抽象的角度解释这一问题，我们需要首先考虑乘法逆元的定义。当我们有一个定义有乘法的集合，并且该集合中有一个对乘法表现中性的元素(其他元素与之相乘后的结果不变)，那么我们使用以下方式定义乘法逆元(multiplicative inverses):

设 \(S\) 是可以进行 \(a \cdot b\) 乘法运算且 存在中性元素(neutral element) \(1 \in S\)的集合，对任何 \(a \in S\) 都存在 \(1 \cdot a = a\) c成立。那么对元素 \(a \in S\) 的乘法逆元 \(a^{-1}\) 定义如下:

\[ a \cdot a^{-1} = 1 \]

通俗来说，乘法逆元的定义是指它抵消了原来的元素，所以两者相乘结果为 \(1\) 。

具有乘法逆元的数特别令人感兴趣，因为它们可以定义两个数的除法。事实上，如果 \(a\) 是一个数且具有乘法逆元 \(a^{-1}\) 存在，那么我们可以定义除法为与逆元相乘：

\[ \frac{b}{a}:= b\cdot a^{-1} \]

示例 12

已知有理数集合，即 \(\Bbb{Q}\) 。对于此集合，中性元素为 \(1\) ，因为 \(1 \cdot a = a\) 对任何有理数都成立。比如\(1\cdot 4=4\)、 \(1\cdot \frac{1}{4}=\frac{1}{4}\) 和 \(1\cdot 0 =0\) 。

每个有理数 \(a\neq 0 \) 都存在乘法逆元 \(\frac{1}{a}\) 。比如，\(3\) 的乘法逆元是 \(\frac{1}{3}\)，因为 \(3\cdot \frac{1}{3}=1\)。 \(\frac{5}{7}\) 的乘法逆元是 \(\frac{7}{5}\)，因为 \(\frac{5}{7}\cdot \frac{7}{5}=1\) 。

示例 13

查看整数集合 \(\Bbb{Z}\) ，我们可以发现中性元素为数字 \(1\) 。除了数字 \(1\) 和 \(-1\) 外，没有其他整数具有乘法逆元，因为对于 \(a \cdot x = 1\) 方程在 \(a \neq 1\) 及 \(a \neq -1\) 集合内没有整数解。

乘法逆元定义有一个类似的加法的定义，称为加法逆元。在整数集合内，加法运算的中性元素为 \(0\) ，因为 \(a + 0 = a\) 对于任何整数 \(a \in \Bbb{Z}\) 均成立。加法逆元总是存在的，并且由负数 \(-a\) 给出，因为 \(a + (-a) = 0 \)。

此处注意 pull requests 原仓库，原文有误

示例 14

查看 示例 11 给出的模 6 体系 \(\Bbb{Z}_6\) ，我们可以使用对应的乘法表找到乘法逆元。为此，我们需要查看每行元素并找到等于 1 的条目。如果此条目存在，这该行对应的元素存在乘法逆元，否则则不存在乘法逆元。

比如，在 \(\Bbb{Z}_6\) 中，\(5\) 的乘法逆元是 \(5\) 本身，因为 \(5 \cdot 5 = 1\) 。我们也可以发现 \(5\) 和 \(1\) 是 \(\Bbb{Z}_6\) 体系内仅有的存在乘法逆元的元素。

因为 \(5\) 存在乘法逆元，所以我们可以在 \(\Bbb{Z}_6\) 体系内进行除 5 操作。这是因为除法事实上可以被定义为与乘法逆元相乘：

\[ \frac{4}{5} = 4 \cdot 5^{-1} = 4 \cdot 5 = 2 \]

从上述例子中，我们观察到一个有趣的现象，即虽然 \(5\) 作为一个整数没有乘法逆元，但 \(5\) 在模 6 算术中存在乘法逆元。

这就提出了一个问题：在模算术体系内，哪些数字具有乘法逆元？答案是，在模 \(n\) 体系内，仅当 \(n\) 和 \(r\) 互质时，数字 \(r\) 存在乘法逆元。在这种情况下，\(gcd(n,r)=1\) ，由扩展欧几里得算法，我们可以得到 \(s\) 和 \(t\)，因此以下等式成立：

\[1 = s\cdot n + t \cdot r\]

对此等式两边同取模 \(n\)，则 \(s \cdot n\) 项消失，这说明 \(t\ \text{mod}\ n\) 是模 \(n\) 算术中 \(r\) 的乘法逆元。

示例 15

在上一个实例中，我们使用乘法表回顾了 \(\Bbb{Z}_6\) 中的乘法逆元。在现实世界中，因为模数都非常大，所以我们不可能写出乘法表。

我们尝试使用非查表的方式获得 \(2 \in \Bbb{Z}_6\) 的乘法逆元。我们观察到 \(2\) 和 \(6\) 不是互素的，因为它们存在最大公约数 \(2\) 。因此，对于 \(n=2\) 方程 \(1 = s\cdot n + t \cdot r\) 无法解出 \(s\) 和 \(t\) 。这意味着 \(2\) 在 \(\Bbb{Z}_6\) 中没有乘法逆元。

基于相同的原因， \(3\) 和 \(4\) 与 \(6\) 不互素，故也不存在乘法逆元。但是 \(5\) 是特殊的，因为 \(gcd(6,5)=1\)。为了计算 \(5\) 的乘法逆元，我们需要使用拓展欧几里得算法，计算如下：

\[ \begin{array}{c | c c l} k & r_k & s_k & t_k = \Zdiv{(r_k-s_k \cdot a)}{b} \\ \hline 0 & 6 & 1 & 0 \\ 1 & 5 & 0 & 1 \\ 2 & 1 & 1 & -1 \\ 3 & 0 & . & . \\ \end{array} \]

解得 \(s=1， t=-1\)，即 \(1 = 1\cdot 6 -1\cdot 5\) 。因此， \(-1\ \text{mod}\ 6 = 5\) 是 \(5\) 的乘法逆元。我们可以使用Sage验算：

sage: ZZ(6).xgcd(ZZ(5))
(1, 1, -1)

此时，细心的读者可能注意到模数是素数的情况是令人感兴趣的。在这种情况下，所有同余类都存在逆元，因为对于素数 \(n\) 和任何 \(r < n \)都有 \(gcd(r,n)=1)\) 成立。事实上，费马小定理也提供了一些方式在这种情况下用于计算乘法逆元，因为在素数模 \(p\) 和 \(r < p\) 条件下，我们得到：

\[ \begin{align*} \kongru{r^p}{r}{p} & \Leftrightarrow \\ \kongru{r^{p-1} }{1}{p} & \Leftrightarrow \\ \kongru{r\cdot r^{p-2} }{1}{p} \end{align*}
\]

这说明在素数模 \(p\) 体系中，同余类 \(r\) 的乘法逆元是 \(r^{p-2}\)

我们在 3.2.2 运算规则 中讨论了费马小定理，读者可返回查阅。

示例 16

为了发现素数模体系中的特殊性质，我们将重复 示例 11 中的过程，但在素数模 \(5\) 体系内。对于 \(p=5\) ，我们可以得到以下同余类：

\[ \begin{array}{ccc} 0: = \{\ldots, -5,0,5,10, \ldots \}\\ 1: = \{\ldots, -4,1,6,11, \ldots \}\\ 2: = \{\ldots, -3,2,7,12, \ldots \} \\ 3: = \{\ldots, -2,3,8,13, \ldots \}\\ 4: = \{\ldots, -1,4,9,14, \ldots \} \end{array} \]

根据上述同余类，我们可以得到如下加法和乘法表：

\[ \begin{array}{c | c c c c c} + & 0 & 1 & 2 & 3 & 4 \\\hline 0 & 0 & 1 & 2 & 3 & 4 \\ 1 & 1 & 2 & 3 & 4 & 0 \\ 2 & 2 & 3 & 4 & 0 & 1 \\ 3 & 3 & 4 & 0 & 1 & 2 \\ 4 & 4 & 0 & 1 & 2 & 3 \\ \end{array} \quad \quad \quad \quad \begin{array}{c | c c c c c} \cdot & 0 & 1 & 2 & 3 & 4 \\\hline 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 2 & 0 & 2 & 4 & 1 & 3 \\ 3 & 0 & 3 & 1 & 4 & 2 \\ 4 & 0 & 4 & 3 & 2 & 1 \\ \end{array} \]

我们可以发现 \(\Bbb{Z}_5\) 体系中的加法和乘法与 \(\Bbb{Z}_6\) 体系中有一些微小但重要的差异。特别是，我们发现在乘法表中，在任一同余类 \(r \neq 0\) 所在的行中都存在等于 1 的条目，因此这些数均具有乘法逆元。此外，若非零元素不参与运算，则乘积均不为 \(0\) 。

关于如何在乘法表内查找某个同余类是否存在乘法逆元的方法，我们亦在 示例 14 中进行了详细解释，读者可自行查阅。

基于 示例 15 中的结论，我们可以使用费马小定理对 \(\Bbb{Z}_5\) 中的元素计算乘法逆元。已知 \(3 \in \Bbb{Z}_5\) ，使用同余类计算 \(3^{5-2}=3^3=3\cdot 3\cdot 3= 4\cdot 3 = 2\) 。事实上，\(3^{-1}=2\)，因为 \(3 \cdot 2 = 1\) 在 \(\Bbb{Z}_5\) 中成立。

使用 Sage 在模 5 算术体系中进行检查：

sage: Z5 = Integers(5)
sage: Z5(3)**(5-2)
2
70sage: Z5(3)**(-1)
2
72sage: Z5(3)**(5-2) == Z5(3)**(-1)
True

示例 17

为了了解素数模体系和非素数模体系的主要区别之一，已知在 \(\Bbb{Z}_5\) 和 \(\Bbb{Z}_6\) 上定义的线性方程 \(a \cdot x + b = 0\)。因为任何非零元素在 \(\Bbb{Z}_5\) 中都存在乘法逆元，所以我们总可以在 \(\Bbb{Z}_5\) 中求解线性方程。但在 \(\Bbb{Z}_6\) 中，方程不一定有解。为证明这一点，已知方程 \(3x+3=0\) 在 \(\Bbb{Z}_5\) 中，我们有以下求解过程：

\[ \begin{align*} 3x+3 &= 0 & \text{\# add 2 and on both sides} \\ 3x+3+2 &= 2 & \text{\# addition-table: } 2+3 = 0 \\ 3x &= 2 & \text{\# divide by } 3 \text{ (which equals multiplication by 2)}\\ 2\cdot(3x) &= 2\cdot 2 & \text{\# multiplication-table: } 2\cdot 2=4 \\ x &= 4 & \end{align*} \]

在素数模体系中，我们得到了唯一解 \(x=4\) 。现在，我们考虑 \(\Bbb{Z}_6\) 中的求解过程：

\[ \begin{align*} 3x+3 &= 0 & \text{\# add 3 and on both sides} \\ 3x+3+3 &= 3 & \text{\# addition-table: } 3+3 = 0 \\ 3x &= 3 & \text{\# division not possible (no multiplicative inverse of 3 exists)} \end{align*} \]

由于 \(3\) 在 \(\Bbb{Z}_6\) 中没有乘法逆元，所以我们不能通过两边同除 \(3\) 以进行方程求解。事实上，当我们观察 \(\Bbb{Z}_6\) 的乘法表时，我们可以发现解集为 \(x \in \{1,3,5\}\) 。这些解都满足 \(3x + 3 = 0\) 。

练习 22. 考虑模数 \(n=24\) 。对于整数 \(7,1,0,805,-4255\) ，哪些数在模 24 体系内存在逆元？如果存在，请计算乘法逆元。

练习 23. 求出同余方程 \(\kongru{17(2x+5)-4}{2x+4}{5}\) 的解集。

练习 24. 求出同余方程 \(\kongru{17(2x+5)-4}{2x+4}{6}\) 的解集。

多项式是由变量(variables)和系数(coefficients)组成的，但仅包含加法、减法和乘法运算的表达式。多项式内的所有系数必须具有相同的类型，比如系数均为整数或均为有理数等。¹

更加准确的说，单变量多项式(univariate polynomial)是以下表达式:

\[ P(x) := \sum _{j = 0} ^{m}{a} _{j}{x} ^{j} ={a} _{m}x^m +{a} _{m-1} x^{m-1} + \dots + a_1 x + a_0 \]

在上式中， \(x\) 被称为变量，而 \(a\) 则被称为系数。如果 \(R\) 是系数的类型，则 \(R\) 中所有单变量多项式的集合记为 \(R[x]\) 。单变量多项式通常简称为多项式，记为 \(P(x) \in R[x]\)。常数项 \(a_0\) 也可记为 \(P(0)\)

如果多项式内所有系数均为 0，则该多项式被称为零多项式(zero polynomial)。如果多项式的常数项为 \(1\) 且其他系数均为零，则该对象是被称为单多项式(one polynomial)

给定一个非零多项式 \(P(x)=\sum_{j=0}^m a_jx^j\)，我们乘非负整数 \(deg(p) := m\) 为多项式的次数(degree)。同时，我们将零多项式的次数记为 \(-\infty\)，其中 \(-\infty\) 为一个符号，其性质为 \(-\infty + m = -\infty\) 且对于所有非负整数 \(m \in \Bbb{N}_0\)，都存在 \(-\infty < m\)。

此外，我们将多项式中具有最高次数项的系数记为首项系数(leading coefficient)，记为：

\[Lc(P):=a_m\]

译者翻译到此才发现全国科学技术名词审定委员会管理的 术语在线 网站，后文名词会尽可能选择此网站翻译。前文名词将会在将来在进行审定。

我们可以将通过指定多项式最高次数来限制多项式集合 \(R[x]\) 的范围。如果 \(m\) 是指定的最高次数，所有低于或等于 \(m\) 的多项式集合记为 \(R_{\leq m}[x]\)

示例 18

正如上文所述，多项式的系数必须具有相同的类型。以整数为系数的多项式集合记为 \(\Bbb{Z}[x]\) 。其中的一些多项式如下：

\[ \begin{align*} P_1(x) &= 2x^2 -4x +17 & \text{ \# with } deg(P_1)=2 \text{ and } Lc(P_1)=2\\ P_2(x) &= x^{23} & \text{ \# with } deg(P_2)=23 \text{ and } Lc(P_2)=1\\ P_3(x) &= x & \text{ \# with } deg(P_3)=1 \text{ and } Lc(P_3)=1\\ P_4(x) &= 174 & \text{ \# with } deg(P_4)=0 \text{ and } Lc(P_4)=174\\ P_5(x) &= 1 & \text{ \# with } deg(P_5)=0 \text{ and } Lc(P_5)=1\\ P_6(x) &= 0 & \text{ \# with } deg(P_6)=-\infty \text{ and } Lc(P_6)=0\\ P_7(x) &= (x-2)(x+3)(x-5) \end{align*} \]

每个整数都可以视为零次整数多项式。\(P_7\) 也是多项式，因为我们可以将其拆成 \(P_7(x)=x^3 - 4 x^2 - 11 x + 30\)，该多项式的次数为 \(3\) 且首项系数为 \(1\)

以下表达式不是整数多项式：

\[ \begin{align*} Q_1(x) &= 2x^2 + 4 + 3x^{-2}\\ Q_2(x) &= 0.5x^4 -2x\\ Q_3(x) &=2^x \end{align*} \]

\(Q_1\) 不是整数多项式，因为 \(x^{-2}\) 具有负指数。\(Q_2\) 是因为系数 \(0.5\) 不属于整数。\(Q_3\) 则因为变量出现在系数的指数位上。

我们可以使用 Sage 进行多项式的运算。为此，我们必须指定变量的符号和整数的类型

sage: Zx = ZZ['x'] # 使用 x 表示变量的整数多项式
sage: Zt.<t> = ZZ[] # 使用 t 表示变量的整数多项式
sage: Zx
Univariate Polynomial Ring in x over Integer Ring
sage: Zt
Univariate Polynomial Ring in t over Integer Ring
sage: p1 = Zx([17, -4, 2])
sage: p1
2*x^2 - 4*x + 17
sage: p1.degree()
2
sage: p1.leading_coefficient()
2
sage: p2=Zt(t^23)
sage: p2
t^23
sage: p6 = Zx([0])
sage: p6.degree()
-1

示例 19

回想在 示例 11 中定义到模 6 算术体系 \(\Bbb{Z}_6\)。使用 \(x\) 表示变量且系数均位于 \(\Bbb{Z}_6\) 中的多项式集合记为 \(\Bbb{Z}_6[x]\)。一些属于 \(\Bbb{Z}_6[x]\) 的多项式如下：

\[ \begin{align*} P_1(x) &= 2x^2 -4x +5 & \text{ \# with } deg(P_1)=2 \text{ and } Lc(P_1)=2\\ P_2(x) &= x^{23} & \text{ \# with } deg(P_2)=23 \text{ and } Lc(P_2)=1\\ P_3(x) &= x & \text{ \# with } deg(P_3)=1 \text{ and } Lc(P_3)=1\\ P_4(x) &= 3 & \text{ \# with } deg(P_4)=0 \text{ and } Lc(P_4)=3\\ P_5(x) &= 1 & \text{ \# with } deg(P_5)=0 \text{ and } Lc(P_5)=1\\ P_6(x) &= 0 & \text{ \# with } deg(P_5)=-\infty \text{ and } Lc(P_6)=0\\ P_7(x) &= (x-2)(x+3)(x-5) \end{align*} \]

与上一个例子相同， \(P_7\) 是一个多项式。但是，因为我们将系数定义在 \(\Bbb{Z}_6[x]\) 中，表达式 \(P_7\) 的运算有所不同，因为我们需要使用 \(\Bbb{Z}_6[x]\) 中的加法和乘法：

\[ \begin{align*} (x-2)(x+3)(x-5) &= (x+4)(x+3)(x+1) & \text{\# additive inverses in } \Z_6 \\ &= (x^2+4x+3x+3\cdot 4)(x+1) & \text{\# bracket expansion} \\ &= (x^2+1x+0)(x+1) & \text{\# computation in } \Z_6 \\ &= x^3+x^2+x^2+x & \text{\# bracket expansion}\\ &= x^3+2x^2+x \end{align*} \]

同样，我们可以使用 Sage 进行系数定义在 \(\Z_6\) 的多项式进行运算。如下：

sage: Z6 = Integers(6)
sage: Z6x = Z6['x']
sage: Z6x
Univariate Polynomial Ring in x over Ring of integers modulo 6
sage: p1 = Z6x([5, -4, 2])
sage: p1
2*x^2 + 2*x + 5
sage: p1 = Z6x([17, -4, 2])
sage: p1
2*x^2 + 2*x + 5
sage: Z6x(x-2) * Z6x(x+3) * Z6x(x-5) == Z6x(x^3 + 2*x^2 + x)
True

给定一些相同类型的元素作为多项式的系数，我们可以计算得到对应的多项式。更准确的说，设 \(P \in R[x]\) 且 \(P(x)=\sum_{j=0}^m a_j x^j\) 是一个系数属于 \(R\) 的多项式，另设 \(b \in R\) 。我们可以计算对应的多项式如下：

\[ P(b) = \sum_{j=0}^m a_j b^j \]

简单来说，就是代入求值，原文使用了 the evaluation of P at b 的表述，即将 \(b\) 代入 \(x\) 进行求值。

示例 20

再次考虑 示例 18 中的整数多项式。我们可以代入计算给定数值的结果，代入计算如下：

\[ \begin{align*} &P_1(2) = 2\cdot 2^2 -4\cdot 2 +17 = 17 \\ &P_2(3) = 3^{23}=94143178827 \\ &P_3(-4) = -4 = -4\\ &P_4(15) = 174 \\ &P_5(0) = 1 \\ &P_6(1274) =0 \\ &P_7(-6) = (-6-2)(-6+3)(-6-5) = -264 \\ \end{align*} \]

注意，不是所有的数都可以代入多项式求值，比如 \(P_1(0.5)\) 不是严格正确的，因为 \(0.5\) 不是整数。我们可以使用Sage验证代入计算的结果：

sage: Zx = ZZ['x']
sage: p1 = Zx([17,-4,2])
sage: p7 = Zx(x-2)*Zx(x+3)*Zx(x-5)
sage: p1(ZZ(2))
17
sage: p7(ZZ(-6)) == ZZ(-264)
True

示例 21

再次考虑 示例 19 给出的 \(\Z_6\) 系数多项式。我们也可以代入计算多项式的值，如下：

\[ \begin{align*} & P_1(2)= 2\cdot 2^2 -4\cdot 2 +5 = 2 - 2 + 5 = 5\\ &P_2(3)= 3^{23}=3\\ &P_3(-4)= P_3(2) = 2\\ &P_5(0)= 1\\ &P_6(4)=0 \end{align*} \]

使用sage验算如下：

sage: Z6 = Integers(6)
sage: Z6x = Z6['x']
sage: p1 = Z6x([5,-4,2])
sage: p1(Z6(2)) == Z6(5)
True

多项式在很多方面与整数类似。特别是，多项式也可以进行加法、减法和乘法。此外，多项式也有自己的带余除法(欧几里得除法)定义。通俗地说，我们可以通过将对应项系数相加的方法实现两个多项式加法，并且我们可以通过使用乘法分配律实现多项式的乘法。

设 \( \sum _{n = 0} ^{m_1}{a} _{n}{x} ^{n} \) 和 \( \sum _{n = 0} ^{m_2}{b} _{n}{x^n} \) 均是定义在 \(R[x]\) 上的多项式。那么，多项式的和(sum) 和 乘积(product) 定义如下：

\[ \sum _{n = 0} ^{m_1}{a} _{n}{x} ^{n} + \sum _{n = 0} ^{m_2}{b} _{n}{x } ^{n} = \sum _{n = 0} ^{max({m_1,m_2})}{({a} _{n} +{b} _{n})}{x} ^{n} \]

\[ \bigg (\sum _{n = 0} ^{m_1}{a} _{n}{x} ^{n} \bigg) \cdot \bigg (\sum _{n = 0} ^{m_2 }{b} _{n}{x} ^{n} \bigg) = \sum _{n = 0} ^{m_1+m_2} \sum _{i = 0} ^{n}{a} _{i }{ {b} _{n-i} }{x} ^{n} \]

多项式减法的规则可以从加法和乘法中推导出来，即减数多项式与 \(-1\) 相乘后于被减数相加。

已知多项式次数的定义，我们发现和的次数总是两个被加数的最大值，而乘积的次数总是因子次数的和。因为我们已经定义了 \(-\infty + m= - \infty\) ，所以即使在多项式乘法的因子中出现了零多项式，乘积的次数为因子次数的和的定理依然成立。

示例 22

为了举例说明多项式运算的工作原理，已知以下两个整数多项式 \(P,Q\in \Z[x]\) 且 \(P(x)= 5x^2 -4x +2 , Q(x)=x^3-2x^2 +5\)。两个多项式的和是将多项式对应次数项的系数相加，如下：

\[ \begin{align*} (P+Q)(x) & = (0+1)x^3 + (5-2)x^2 + (-4 +0) x +(2+5) \\ & = x^3 +3x^2 -4x +7 \end{align*} \]

多项式的乘积通过将第一个多项式中的每一项于第二个多项式中的每一项相乘计算得到的：

\[ \begin{align*} (P\cdot Q)(x) & = (5x^2 -4x +2)\cdot (x^3-2x^2 +5) \\ & = (5 x^5 -10 x^4 +25 x^2)+ (-4x^4 +8 x^3 -20x) + (2x^3 -4x^2+10) \\ & = 5 x^5 -14x^4 +10x^3+21x^2-20x +10 \end{align*} \]

使用 Sage 检验如下：

sage: Zx = ZZ['x']
sage: P = Zx([2,-4,5])
sage: Q = Zx([5,0,-2,1])
sage: P+Q == Zx(x^3 +3*x^2 -4*x +7)
True
sage: P*Q == Zx(5*x^5 -14*x^4 +10*x^3+21*x^2-20*x +10)
True

示例 23

已知 示例 22 中给出的多项式，但已知系数属于模 6 算术体系的情况，即 \(P,Q\in \Z_6[x]\)。运算如下：

\[ \begin{align*} (P+Q)(x) & = (0+1)x^3 + (5-2)x^2 + (-4 +0) x +(2+5) \\ & = (0+1)x^3 + (5+4)x^2 + (2 +0) x +(2+5) \\ & = x^3 +3x^2 +2x +1\\ \\ (P\cdot Q)(x) & = (5x^2 -4x +2)\cdot (x^3-2x^2 +5) \\ & = (5x^2 +2x +2)\cdot (x^3+4x^2 +5) \\ & = (5 x^5 +2 x^4 +1x^2)+ (2x^4 +2x^3 +4x) + (2x^3 +2x^2+4) \\ & = 5 x^5 +4x^4 +4x^3+3x^2+4x +4 \end{align*} \]

使用 Sage 检验如下：

sage: Z6x = Integers(6)['x']
sage: P = Z6x([2,-4,5])
sage: Q = Z6x([5,0,-2,1])
sage: P+Q == Z6x(x^3 +3*x^2 +2*x +1)
True
sage: P*Q == Z6x(5*x^5 +4*x^4 +4*x^3+3*x^2+4*x +4)
True

练习 26. 比较 示例 22 和 示例 23 中的多项式和 \(P + Q\) 和多项式乘积 \(P \cdot Q\) ，并已知 示例 11 中给出 \(\Z_6\) 的定义。如何通过 \(\Z[x]\) 体系下的运算结果推导出 \(\Z_6[x]\) 体系下的运算结果。

$$ \gdef\Zdiv#1#2{#1\ \text{div}\ #2} \gdef\Zmod#1#2{#1\ \text{mod}\ #2} $$

多项式运算与整数运算共享了许多性质。因此，欧几里得除法的概念和长除法算法也存在多项式定义。回忆 欧几里得除法 一节，我们知道，给定两个整数 \(a, b \neq 0\) ，总是存在另一个整数 \(m\) 和自然数 \(r\) 且 \(r < |b|\) 使得 \(a = m \cdot b + r\) 成立。

当被除数多项式的首项系数具有乘法逆元的概念，我们就可以将整数的欧几里得除法推广到多项式中。事实上，给定两个定义在 \(R[x]\) 上的多项式 \(A, B \neq 0\) 且 \({Lc(B)}^{-1}\) 在 \(R\) 中存在，那么就有多项式 \(Q\)(the quotient 商) 和 \(P\)(the remainder 余数) 且 \(deg(P) < deg(B)\) 使得：

\[A = Q \cdot B + P\]

与整数欧几里得除法类似，\(Q\) 和 \(P\) 都是唯一的。

符号 2

假设多项式 \(A,B,Q,P\) 满足上式。我们通常使用一些符号表示欧几里得除法中的商和余数：

\[ \begin{array}{lcr} \Zdiv{A}{B}: = Q, & & \Zmod{A}{B}: = P \end{array} \]

如果 \(\Zmod{A}{B}=0\) 成立，我们乘多项式 \(A\) 可以被 \(B\) 整除。在这种情况下，我们也可以记为 \(B|A\) 并称 \(B\) 是 \(A\) 的一个因子。

类似整数，计算多项式欧几里得除法的方法被称为多项式除法算法(polynomial division algorithms)。最著名的算法可能是所谓的多项式长除法(polynomial long division)。如下所示：

该算法只有存在 \(B\) 的首项系数存在乘法逆元时才有效。它可以被推广，但我们在下面的内容中仅需要这个较为简单的算法。

示例 24

在本示例中，我们将讨论多项式长除法。

为了举例说明长除法时证明工作的，给出 \(A(x)=x^5+2x^3-9\in \Z[x]\) 除以 \(B(x)=x^2+4x-1\in\Z[x]\) 。因为 \(B\) 不是零多项式，且 \(B\) 的首项系数是 \(1\) ，该系数是可逆的，所以我们可以使用多项式长除法。我们的目标是找到 商 \(Q \in \Z[x]\) 和余数 \(P \in \Z[x]\) 使得 \(x^5+2x^3-9 = Q(x)\cdot (x^2+4x-1) + P(x)\) 成立。使用主要国家的长除法运算过程表示方法，我们运算过程如下：

$$ \begin{array}{rll} X^3 - 4X^2 + 19X - 80 \\ X^2+4X-1 {\overline{\smash{\big)} X^5\phantom{-4X^4} + 2 X^3\phantom{- 4X^2 + 19X }-9})}\\ \underline{X^5+4X^4-X^3\phantom{- 4X^2 + 19X - 80} } \\ -4X^4+3X^3\phantom{- 4X^2 + 19X - 80}\\ \underline{ -4X^4-16X^3+4X^2 } \phantom{+ 19X - 80}\\ 19X^3-4X^2 \phantom{+ 19X - 80}\\ \underline{ 19X^3+76X^2-19X } \phantom{-9} \\ -80X^2+19X-9\\ \underline{ -80X^2-320X+80 } \\ 339X-89 \end{array} $$

上述长除法是经过译者本土化后的(读者应在高考期间学习过此内容)，所以与原文不太相同，但考虑到教育背景的差异，译者使用的竖式可能与读者熟悉的不同。

示例 25

在上一个例子中，多项式除法给出了非平凡(非零的)的余数。没有余数的除法是令人感兴趣的。在这种情况下，除数被称为被除数的因子(factors of the dividend)。

比如，回顾 示例 18 中给出的整数多项式 \(P_7\) 。 \(P_7\) 既可以写成 \(x^3 - 4 x^2 - 11 x + 30\) 也可以写成 \((x-2)(x + 3)(x-5)\) 。由此可知，多项式 \(F_1(x)=(x-2), F_2(x)=(x+3), F_3(x)=(x-5)\) 都是 \(x^3 - 4 x^2 - 11 x + 30\) 的因子。

练习 27. 已知多项式 \(A(x):=-3x^4+4x^3+2x^2+4\) 和 \(B(x) := x^2-4x+2\) 。在以下类型限制下计算 \(A\) 除以 \(B\) 的结果：

1. \(A,B \in \Z[x]\)
2. \(A,B \in \Z_6[x]\)
3. \(A,B \in \Z_5[x]\)

对比 \(\Z[x]\) 和 \(\Z_6[x]\) 下的结果，考虑如何根据 \(\Z[x]\) 下的结果推出 \(\Z_6[x]\) 下的结果。

练习 28. 证明 \(B(x)= 2x^4-3x+4\in \Z_5[x]\) 是 \(A(x)=x^7 + 4x^6 + 4x^5 + x^3 + 2x^2 + 2x + 3\in\Z_5[x]\) 的因子，即 \(B|A\)，并计算 \(\Zdiv{B}{A}\) .

回忆 算术基本定理 告诉我们任何自然数都可以写成素数的乘积。在本节中，我们会发现类似的定理也适用于单变量多项式。

在多项式内也存在类似素数的概念，被称为 不可约多项式(irreducible polynomial)。不可约多项式指不能使用欧几里得除法分解为两个非常数多项式乘积的多项式。不可约多项式之于多项式与素数之于整数：它们都是构建其他所有多项式的基本构件。

为更加清楚的说明，设 \(P \in \R[x]\) 是任一多项式，那么存在不可约多项式 \(F_1, F_2, \ldots, F_k \in R[x]\) 使得下式成立：

\[P = F_1 \cdot F_2 \cdot \ldots \cdot F_k\]

除因子排列顺序不同外，这种分解是唯一的，被称为 \(P\) 的素因子分解(prime factorization)。此外，每一个因子 \(F_i\) 则被称为 \(P\) 的素因子(prime factor)

示例 26

已知多项式 \(P = x^2-3\)。当我们认为 \(P\) 是一个整数多项式时(\(P \in \Bbb{Z}[x]\))，我们发现该多项式为一不可约多项式，因为除 \(1 \cdot (x^2-3)\) 之外的任一分解都形如 \((x-a)(x+a)\) 形式，但对于整数 \(a\) 而言 \(a^2=3\) 无解。

sage: Zx = ZZ['x']
sage: p = Zx(x^2-3)
sage: p.factor()
x^2 - 3

另一方面，如果我们认为 \(P\) 是一个多项式 \(P \in \Bbb{Z}_6\) ，我们发现 \(P\) 存在两个因子 \(F_1=(x-3)\) 和 \(F_1=(x+3)\) ，因为 \((x-3)(x+3)= x^2 -3x +3x -3\cdot 3= x^2-3\)

使多项式求值为 \(0\) 的 \(x\) 点被称为多项式的根(roots)。更加准确的说，设 \(P \in R[x]\) 为一多项式，那么根 \(x_0\ \in R\) 满足 \(P(x_0)=0\)，且 \(P\) 的所有根的集合如下：

\[R_0(P):=\{x_0\in R| P(x_0)=0\}\]

多项式的根因在质因子分解中具有重要意义。可以证明，对于 \(P\) 的任一给定的根 \(x_0\) 都存在 \(F(x)=(x-x_0)\) 是 \(P\) 的素因子。

求多项式的根的过程有时被称为解多项式(solving the polynomial)。这是一个难题，在历史上有大量的研究。

可以证明，如果 \(m\) 是多项式 \(P\) 的次数，那么 \(P\) 不会有超过 \(m\) 个根。但是，一般来说，多项式的根数量会小于 \(m\) 。

示例 27

回顾 示例 18 中给出的整数多项式 \(P_7(x) = x^3 - 4x^2 - 11x + 30\) ，我们可以计算出它的根是 \(R_0(P_7)=\{-3,2,5\}\).

另一方面，我们知道 示例 26 中给出的 \(x^2-3\) 是不可约多项式，因此它没有根。因为只要多项式存在一个根，那么其必然可以继续分解，这与不可约多项式的定义冲突(反证法)。

示例 28

给出另一个例子，已知整数多项式 \(P=x^7 + 3 x^6 + 3 x^5 + x^4 - x^3 - 3 x^2 - 3 x - 1\) 。我们可以使用 Sage 计算此多项式的根：

sage: Zx = ZZ['x']
sage: p = Zx(x^7 + 3*x^6 + 3*x^5 + x^4 - x^3 - 3*x^2 - 3*x - 1)
sage: p.roots()
[(1, 1), (-1, 4)]
sage: p.factor()
(x - 1) * (x + 1)^4 * (x^2 + 1)

我们发现 \(P\) 存在根 \(1\) ，并且素因子 \((x-1)\) 在 \(P\) 中出现了一次。我们也发现 \(P\) 存在根 \(-1\)，其关联的素因子 \((x+1)\) 在 \(P\) 中出现了四次。因此，我们得到了如下素因子分解：

\[P=(x - 1) * (x + 1)^4 * (x^2 + 1)\]

上述出现几次存在一种更加数学的表述，即多重根(multiple root)。译者注。

练习 29. 证明：若多项式 \(P \in R[x]\) 且其次数为 \(deg(P)=m\) 存在至多 \(m\) 个根，则该多项式必存在一个素因子 \(F\) 且 \(deg(F)>1\)

练习 30. 给出多项式 \(P=x^7 + 3 x^6 + 3 x^5 + x^4 - x^3 - 3 x^2 - 3 x - 1\in \Bbb{Z}_6[x]\) ，计算该多项式的所有根 \(R_0(P)\) ，然后计算 \(P\) 的素因数分解

多项式一个极其有用的特性是 m 次多项式可以使用 \(m+1\) 个数值点推导出来。这意味着我们可以从集合 \(S\) 中唯一地导出 m 次多项式：

\[S= \{(x_0,y_0), (x_1,y_1),\ldots,(x_m,y_m) | x_i\neq x_j\text{ for all indices i and j}\}\]

因此，多项式具有这样的性质：\(m+1\) 个满足 \(x_i \neq x_j\) 条件的 \((x_i,y_i)\) 点可以确定所有 \(x \in R\) 的 \((x, P(x))\) 的集合。这种 少决定多 的性质在多项式内广泛的使用，包括在 SNARKs 中。因此，我们需要知道使用一组点计算多项式的方法。

如果我们想要计算得到的多项式的系数存在乘法逆元，则可以使用拉格朗日插值(Lagrange Interpolation)法进行求解。给定一个点集 \(S\) ，使用以下算法可以求解出 \(m\) 次多项式 \(P\)：

示例 29

给定集合 \(S=\{(0,4),(-2,1),(2,3)\}\) 。我们的任务是求出一个位于 \(\Bbb{Q}[x]\) 内的二次多项式，即系数均属于有理数的二次多项式。因为 \(\Bbb{Q}\) 内的元素均具有乘法逆元，我们可以使用拉格朗日插值算法，计算如下：

\[ \begin{align*} l_0(x) & = \frac{x-x_1}{x_0-x_1}\cdot\frac{x-x_2}{x_0-x_2} = \frac{x+2}{0+2}\cdot\frac{x-2}{0-2} = -\frac{(x+2)(x-2)}{4}\\ & = -\frac{1}{4}(x^2-4)\\ l_1(x) & = \frac{x-x_0}{x_1-x_0}\cdot\frac{x-x_2}{x_1-x_2} = \frac{x-0}{-2-0}\cdot \frac{x-2}{-2-2} = \frac{x(x-2)}{8}\\ & = \frac{1}{8}(x^2-2x)\\ l_2(x) & = \frac{x-x_0}{x_2-x_0}\cdot\frac{x-x_1}{x_2-x_1} = \frac{x-0}{2-0}\cdot\frac{x+2}{2+2} = \frac{x(x+2)}{8}\\ & = \frac{1}{8}(x^2+2x)\\ P(x) & = 4\cdot (-\frac{1}{4}(x^2-4)) + 1\cdot \frac{1}{8}(x^2-2x) + 3\cdot \frac{1}{8}(x^2+2x)\\ & = -x^2+4 + \frac{1}{8}x^2-\frac{1}{4} x + \frac{3}{8}x^2+\frac{3}{4} x \\ & = -\frac{1}{2} x^2 +\frac{1}{2} x + 4 \end{align*} \]

事实上，通过 \(P(0)=4, P(-2)=1, P(2)=3\) ，可以使用 Sage 进行求解，如下：

sage: Qx = QQ['x']
sage: S = [(0, 4), (-2, 1), (2, 3)]
sage: Qx.lagrange_polynomial(S)
-1/2*x^2 + 1/2*x + 4

示例 30

为给出与本书主题更加相关的另一个示例，让我们重新考虑集合 \(S=\{(0,4),(-2,1),(2,3)\}\) 。这一次，我们使用这些点计算多项式 \(P \in \Bbb{Z}_5[x]\) 。因为我们在 示例 16 已经知道 \(\Bbb{Z}_5\) 内的元素均存在逆元，所以我们可以使用拉格朗日插值法求解出属于 \(\Bbb{Z}_5\) 的二次多项式。计算过程如下：

\[ \begin{align*} l_0(x) & = \frac{x-x_1}{x_0-x_1}\cdot\frac{x-x_2}{x_0-x_2} = \frac{x+2}{0+2}\cdot\frac{x-2}{0-2} = \frac{(x+2)(x-2)}{-4} = \frac{(x+2)(x+3)}{1}\\ & = x^2+1\\ l_1(x) & = \frac{x-x_0}{x_1-x_0}\cdot\frac{x-x_2}{x_1-x_2} = \frac{x-0}{-2-0}\cdot \frac{x-2}{-2-2} = \frac{x}{3}\cdot \frac{x+3}{1} = 2(x^2+3x)\\ & = 2x^2+x\\ l_2(x) & = \frac{x-x_0}{x_2-x_0}\cdot\frac{x-x_1}{x_2-x_1} = \frac{x-0}{2-0}\cdot\frac{x+2}{2+2} = \frac{x(x+2)}{3} = 2(x^2+2x)\\ & = 2x^2+4x\\ P(x) & = 4\cdot (x^2+1) + 1\cdot (2x^2+x) + 3\cdot (2x^2+4x) \\ & = 4x^2+4 + 2x^2 +x + x^2+2x\\ & = 2x^2 +3x +4 \end{align*} \]

使用 Sage 计算如下：

sage: F5 = GF(5)
sage: F5x = F5['x']
sage: S = [(0, 4), (-2, 1), (2, 3)]
sage: F5x.lagrange_polynomial(S)
2*x^2 + 3*x + 4

练习 31. 已知 示例 16 中给出的模 5 算术体系，给定集合 \(S=\{(0,0),(1,1),(2,2),(3,2)\}\) ，求解符合上述点集的多项式 \(P \in \Bbb{Z}_5[x]\)

练习 32. 已知上一个例子中给出的集合 \(S\)。为什么我们不能使用拉格朗日插值算法在 \(\Bbb{Z}_6\) 内求解符合 \(S\) 的多项式？

在上一章内，我们介绍了进行纸笔计算 SNARKs 的基础计算工具。在本章内，我们将对群(groups)、环(rings)和域(fields)等更加抽象但与 SNARKs 相关的数学概念进行介绍。

有关密码学的科学文献机场包含此类术语，所以我们需要对这些抽象术语有一定了解以帮助我们理解文献。

$$\gdef\G{\Bbb{G}}$$

交换群(Commutative Groups)是对数学现象的本质抽象，如加法和减法或乘法和除法。¹

为了理解交换群，让我们回想当我们在学校学习整数加法和减法的时候。我们已经知道每当两个整数相加那么结果必然是一个整数。我们还了解到当我们对任一整数增加零，那么产生的结果与最初的加数相同。此外，我们还了解到两个(或更多)整数相加的顺序对加法结果没有影响，并且括号对于加法结果没有影响。对于任意整数，总存在另一个整数(负数)使其相加后结果为 0

这些条件是交换群的定义属性，数学家认识到完全相同的规则集可以在不同的数学结构内找到。因此，给出一个抽象的、形式化的且与任何具体的例子分离的群定义是有意义的。这使我们可以灵活地处理来自不同数学领域的实体，同时保留抽象代数等领域的基本结构部分。

将这些规则提炼为最小的独立属性列表并将其抽象化，我们得到了如下交换群的定义：

一个交换群 \((\G,\cdot)\) 由集合 \(\G\) 和映射 \(\cdot:\G \times \G \to \G\) 构成。该映射被称为群法则(group law)，该映射将集合内两个元素运算为第三个元素，使得以下属性成立：

1. 交换性(Commutativity)：对于任意的 \(g_1, g_2 \in \G\)，等式 \(g_1 \cdot g_2 = g_2 \cdot g_1\) 成立
2. 结合性(Associativity)：任选 \(g_1,g_2,g_3 \in \G\) ，等式 \(g_1 \cdot (g_2 \cdot g_3) = (g_1 \cdot g_2) \cdot g_3\) 成立
3. 存在幺元(Existence of a neutral element)：对于任一 \(g \in \G\)，存在 \(e \in \G\) 使得 \(e \cdot g = g\)
4. 存在逆(Existence of an inverse)：对于任一 \(g \in \G\) ，存在 \(g^{-1} \in \G\) 使得 \(g \cdot g^{-1} = e\)

如果 \((\G, \cdot)\) 是一个群，并且 \(\G'\subset\G\) 是 \(\G\) 的子集且映射关系依旧封闭，即 \(\cdot:\G' \times \G' \to \G'\) 成立，那么我们称 \((\G', \cdot)\) 是 \((\G, \cdot)\) 的子群(subgroup)

通俗地说，群是我们可以以类似整数相加的方式进行运算的一类结构。具体来说，这意味着我们可以以一种可逆的方式将两个元素结合成一个新的元素，且最终结果与结合的顺序无关。

符号 3

因为我们在本书中仅关注交换群，所以我们直接称交换群为群。

如果不会引起歧义(即已知群法则)的情况下，我们通常删除 \(\cdot\) 符号而直接使用 \(\G\) 表示一个群。

符号 4

对于交换群 \((G, \cdot)\)，我们有时使用所谓的加法记号(additive notation) \((G, +)\) ，即使用 \(+\) 而不是 \(\cdot\) 代表群法则，幺元记为 \(0\) ，且 \(g \in \G\) 的逆元为 \(-g := g^{-1}\)

在后文中，群会在密码学和 SNARKs 中大量使用。但是先让我看一些熟悉的例子。

示例 31

具有整数加法的整数集 \((\Bbb{Z}, +)\) 是典型的交换群，其中群法则使用 加法记号书写。

为了将整数加法与交换群的抽象公理进行比较，我们首先注意到整数的加法是符合交换律和结合律的。整数加法的幺元 \(e\) 是 \(0\) ，此外整数的逆元是其相反数。 这意味着整数与加法是符合抽象意义上的交换群的。

举一个整数子群的例子，已知包含 \(0\) 的偶数集：

\[\Bbb{Z}_{even}:=\{\ldots,-4,-2,0,2,4,\ldots\}\]

我们可以发现此集合是 \((\Bbb{Z}, +)\) 的子集，因为满足以下条件：

1. 偶数的和仍为偶数，说明映射关系封闭
2. 存在幺元 \(0\)
3. 存在逆元

示例 32

交换群最基本的例子是只有一个元素 \(\{\bullet\}\) 且映射关系为 \(\bullet\cdot \bullet=\bullet\) 的群。我们称这种群为平凡群(trivial group)

平凡群是任何群的子群。为证明这一点，设 \((G, \cdot)\) 是一个具有幺元 \(e \in \G\) 的群，那么 \(e \cdot e = e\) 和 \(e^{-1}=e\) 都成立。因此，集合 \(\{e\}\) 是 \(\G\) 的子群。事实上， \(\{0\}\) 是 \((\Bbb{Z}, +)\) 的子群，因为 \(0 + 0 = 0\) 成立。

示例 33

已知模 6 算术体系 \((\Bbb{Z}_6, +)\)中的加法，如 示例 11 中的定义。显然，同余类 \(0\) 是模 6 体系中的幺元，同余类 \(r\) 的逆元为 \(6-r\) ，因为 \(r + (6-r) = 6\) ，其中 \(6\) 与 \(0\) 同余。此外，\(r_1 + r_2 = r_2 + r_1\) 及 \((r_1+r_2)+r_3=r_1+(r_2+r_3)\) 继承自整数加法。因此，我们认为 \((\Bbb{Z}_6,+)\) 是一个群。

上一个示例(即示例 33)中的交换群在本书中是一个重要的示例。从这个例子中，我们可以抽象得到以下结论：对于任意模数 \(n\) 的 \((\Bbb{Z}_n, +)\) ，可以证明 \((\Bbb{Z}_n, +)\) 为一个交换群，且幺元为 \(0\) ，任何元素 \(r \in \Bbb{Z}_n\)都存在加法逆元 \(n-r\)。我们称这样的群为关于模 n 的同余类群(remainder class group)

练习 33. 已知 示例 16，设 \(\Bbb{Z}_5^{*}\) 是 \(\Bbb{Z}_5\) 中除同余类 0 以外的所有同余类的集合，即 \(\Bbb{Z}^{ * }_5 = \{1,2,3,4\}\) ，证明 \((\Bbb{Z}_5^*, \cdot)\) 为交换群。

练习 34. 推广上一个练习的，已知对一般的模数 \(n\)，设 \(\Bbb{Z}_n^*\) 是 \(\Bbb{Z}_n\) 中除同余类 \(0\) 以外的元素构成的集合，即 \(\Bbb{Z}_n^*=\{1,2,\cdots,n-1\}\)。举一个反例证明 \((\Bbb{Z}_n^*, \cdot)\) 不是一般的群。

找到一个条件使得 \((\Bbb{Z}_n^*, \cdot)\) 是一个交换群，并计算幺元，给出任何元素的逆元表达式并证明交换群公理。

$$\gdef\G{\Bbb{G}}$$

正如我们在前面的示例所见，群可以包含无限多个元素(如整数)，也可以包含有限多个元素(如同余类群\((\Bbb{Z}_n,+)\))。为进行分类，我们将包含有限个元素的群称为有限群(finite group)。在这种情况下，构成群的元素的个数被称为群的阶(order)

符号 5

设 \(\G\) 是一个有限群。我们将 \(\G\) 的阶记为 \(|\G|\) 或 \(ord(G)\)

示例 34

已知同余类群 \((\Z_6, +)\) 、 \((\Z_5,+)\) 和 \((\Z_5^*, \cdot)\) 。显然，\((\Z_6,+)\) 的阶为 \(6\) ，\((\Z_5, +)\) 的阶为 \(5\)，而 \((\Z_5^*, \cdot)\) 的阶为 \(4\)

事实上， $\Z_5^* = \{1,2,3,4\}$ ，故其阶数为 4

练习 35. 设 \(n \in \Bbb{N}\) 且 \(n > 2\) 为一模数，计算同余类群 \((\Z_n,+)\) 的阶。

列出一个群内所有的元素可能是复杂的，而且如何计算给定群的元素不总是那么简单。因此，从实践的角度出发，我们需要群拥有一个生成集(generator set)。这是群的一个小子集，但其他所有元素都可以由生成集及其逆元使用群法则计算出来。

当然，每一个群都有生成集，因为我们可以将群内所有元素都视为生成集的部分。让我们感兴趣的问题是寻找给定群的最小生成集。在此问题上，更令我们感兴趣的是寻找仅包含一个元素的生成集。在这种情况下，存在一个(不一定是唯一的)元素 \(g \in \Bbb{G}\) 使得 \(\Bbb{G}\) 内所有其他元素都可以通过 \(g\) 和 \(g^{-1}\) 的组合计算得到。

具有单个、不一定唯一的生成元的群的称为循环群(cyclic group) ，任何能够生产 \(\Bbb{G}\) 的元素被称为生成元。

示例 35

循环群最基本的例子是整数加法群 \((\Bbb{Z}, +)\)。\(1\) 是整数加法群的生成元，因为显然所有整数都可以由 \(1\) 和它的逆元 \(-1\) 通过加法构成。比如 \(-4 = -1 + (-1) + (-1) + (-1)\) 。与之对应，\(-1\) 也可以作为 \(\Bbb{Z}\) 的生成元。

示例 36

已知群 \((\Bbb{Z}_5^*, \cdot)\) ,因为 \(2^1=2, 2^2=4, 2^3=3, 2^4=1\)，所以 \(2\) 是 \((\Bbb{Z}_5^*, \cdot)\) 的生成元。

此外，由于 \(3^1=3, 3^2=4, 3^3=2, 3^4=1\) ，\(3\) 是 \((\Bbb{Z}_5^*, \cdot)\) 的生成元。由此可知，循环群的生成元可能多于 1 个。

\(4^1=4, 4^2=1, 4^3=4\)，事实上，\(4^k\) 符合:

\[ 4^k = \begin{cases} 4 &\text{if k is odd}\\ 1 &\text{if k is even} \end{cases} \]

因此，\(4^k\) 不是 \((\Bbb{Z}_5^*, \cdot)\) 的生成元。由此可见，有限循环群内的每个元素不一定都是生成元。

示例 37

已知模 n 算术体系内的同余类群 \((\Bbb{Z}_n, +)\)，该群是一个循环群，其生成元是 \(1\)。因为该群内的任何其他元素都可以通过 \(1\) 自身累加得到。由于 \(\Bbb{Z}_n\) 是有限集合，所以 \((\Bbb{Z}_n, +)\) 的阶数为 \(n\)

练习 36. 已知群 \((\Bbb{Z}_6,+)\) ，证明 \(5 \in \Bbb{Z}_6\) 是群的生成元，但 \(2 \in \Bbb{Z}_6\) 不是生成元

练习 37. 设 \(p \in \Bbb{P}\) 是一个素数，且 \((\Bbb{Z}_p^*, \cdot)\) 是一个有限群，证明 \((\Bbb{Z}_p^*, \cdot)\) 是一个循环群。

观察到，当 $\Bbb{G}$ 是一个 $n$ 阶循环群且 $g \in \Bbb{G}$ 是 $\Bbb{G}$ 的生成元时，存在所谓的 指数映射(exponential map)。该映射关系将余数类 $(\Z_n, +)$ 的加法运算映射到 $\Bbb{G}$ 的运算上。指数映射可以使用以下式子形式化(其中 $g^x$ 表示“将 $g$ 乘以自己 $x$ 次”，$g^0=e_{\Bbb{G}}$):

$$g^{(\cdot)}: \Z_n \to \Bbb{G}; x \mapsto g^x$$

要了解指数映射的工作原理，我们首先观察到，由于 $g^0=e_\Bbb{G}$ 的定义，$\Z_n$ 的幺元被映射为 $\Bbb{G}$ 的幺元。此外，由于 $g^{x+y}=g^x \cdot g^y$ ，所以该映射符合群法则。

符号 6

如果群 $(\Bbb{G}, +)$ 写成 加法记号 ，那么指数映射通常被称为 标量乘法(scalar multiplication) ，记法如下:

$$(\cdot)\cdot g: \Z_n \to \Bbb{G}; x \mapsto x\cdot g$$

在此记号中，符号 $x \cdot g$ 被定义为“将生成元 $g$ 与其自身相加 $x$ 次”，而符号 $0 \cdot g$ 被定义为 $\Bbb{G}$ 中的幺元。

密码学应用通常使用阶数 $n$ 相当大的有限循环群，这意味着对于非常大的余数类，使用生成元自乘的方法计算指数映射是不可行的。但 平方和算法(square and multiply) 可以通过 $k$ 步计算指数映射，其中 $k$ 为指数的位长度。该算法使计算大余数类的指数映射称为可能。

由于指数映射遵循群法则，所以先在或后在 $\Z_n$ 中进行加法计算并不重要：两种情况下的结果都是相同的。前一种方法(即先进行加法运算)通常被称为在指数中进行计算。在密码学中，特别是在 SNARK 开发中，我们经常在生成元的指数中进行计算。

示例 38

已知乘法群 $(\Z^*_5, \cdot)$ 是一个 4 阶循环群，且元素 $3 \in \Z_5^*$ 使其生成元。这意味着以下映射既遵循 $\Z_4$ 中的加法群法则，也遵循 $\Z^*_5$ 的乘法群法则:

$$3^{(\cdot)}: \Z_4 \to \Z_5^* ; x \mapsto 3^x$$

为了给出一个在指数中计算的示例，让我们在生成元 $3$ 的指数中执行 $1+2+3$ 计算:

$$ \begin{align} 3^{1+3+2} &=3^{2}\\ & = 4 \end{align} $$

在上式 $(1)$ 中，我们首先在余数类群 $(\Z_4, +)$ 中计算 $1+2+3$ ，然后在 $(2)$ 中计算指数映射 $3^{(\cdot)}$ 的值。

然后，由于指数映射遵循群法则，我们也可以对加法映射到 $(\Z_5^*, +)$ 中，然后使用 $(\Z_5^*, +)$ 的群律。结果相同:

$$ \begin{align*} 3^1 \cdot 3^3 \cdot 3^{2} & = 3\cdot 2 \cdot 4\\ & = 1\cdot 4\\ & = 4 \end{align*} $$

因为指数映射是遵循群法则的一对一映射，可以证明该映射具有以 $g$ 为底的逆，称为以 g 为底的离散对数映射(base g discrete logarithm map):

$$log_g(\cdot): \Bbb{G} \to \Z_n; x \mapsto log_g(x)$$

离散对数在密码学中极其重要，因为对于有限循环群，指数映射及其逆(即离散对数映射)被认为是单向函数。这意味着计算指数映射是高效快速的，但计算对数映射是缓慢的。

示例 39

考虑 示例 38 中给出的指数映射 $3^{(\cdot)}$ ，其逆元可以使用以 3 为底的离散对数表示，如下:

$$log_3(\cdot): \Z_5^* \to \Z_4; x \mapsto log_3(x)$$

与计算 $3^{(\cdot)}$ 不同，我们没有任何方法计算出此映射的值，只能通过尝试该群内的任一元素直到找到正确的元素。比如，为计算 $log_3(4)$ ，我们不得不尝试任一 $x \in \Z_4$ 使其满足 $3^x=4$ ，我们所能做的只有重复测试直到满足条件。为做到这一点，我们只能写下所有的 $3^{(\cdot)}$:

$$ \begin{array}{cccc} 3^0 = 1, & 3^1 = 3, & 3^2 = 4, & 3^3 = 2 \end{array} $$

因为离散对数 $log_3(\cdot)$ 定义为指数映射的反函数，我们可以计算得到:

$$ \begin{array}{ccccc} log_3(1) = 0, & log_3(2) = 3, & log_3(3) = 1, & log_3(4) = 2 \end{array} $$

请注意，上述方法之所以可行，因为我们可以写出所有的指数映射。但是，在现实世界中，由于群是极其庞大的，所以上述方法并不可行。

练习 38. Let $(\Bbb{G},+)$ be a finite cyclic group of order $n$. Consider algorithm \ref{alg_square-and-mul} and define its analog for groups in additive notation.

此练习不知道如何翻译，暂且保留英语

由算术基本定理可知，每个自然数 $n$ 都是素数因子的乘积。

若 $\Bbb{G}$ 是 n 阶有限循环群，则 $\Bbb{G}$ 的每个子群 $\Bbb{G}'$ 都是有限循环群且 $\Bbb{G}'$ 的阶数为 $n$ 的因数，此外，对于 $n$ 的每个因子 $k$ ，$\Bbb{G}$ 都存在一个对应的 $k$ 阶子群。这被称为 有限循环群的基本定理(fundamental theorem of finite cyclic groups)。

符号 7

如果 $\Bbb{G}$ 是一个 n 阶有限循环群，且 k 是 n 的因子，那么对于每一个有限循环群，将其记为 $\Bbb{G}[k]$ ，称其为 $\Bbb{G}$ 的 商群(factor group)

如果给定的有限循环群的阶是素数，就会出现一个有趣的情况。正如我们所知，素数仅存在两个因子: 数字 1 和素数本身。根据有限循环群的基本定理，我们可知阶数为素数的有限循环群的商群仅有平凡群和本身。

密码学协议通常假设存在有限的素数阶循环群。但是，这些协议在现实世界中的一些实现没有定义在素数阶群上，而是定义在具有特殊阶数的群上。此特殊阶数可以分解为一个大素数和一个小的共因子。在这种情况下，我们需要使用一种被称为 共因子清除(cofactor clearing) 的方法以确保计算不在该群本身进行，而是在其（大）质数阶子群中进行。

为详细理解共因子清除的细节，设 $\Bbb{G}$ 是一个 n 阶有限循环群，且 $k$ 为 $n$ 的一个因子，具有与之对应的商群 $\Bbb{G}[k]$ 。我们将任何元素 $g \in \Bbb{G}[k]$ 通过自乘 $k$ 次映射到 $\Bbb{G}$ 的幺元 $e$ 上:

$$g^k=e$$

因此，如果 $c := n\ \text{div}\ k$ 是 k 与 n 的共因子，那么任何元素 $g \in \Bbb{G}$ 都可以通过 $g$ 与其自身相乘 $c$ 次映射到因子群 $\Bbb{G}[k]$ 中。这定义了以下映射，在密码学文献中通常称为共因子清除:

$$(\cdot)^c: \Bbb{G} \to \Bbb{G} [k] : g \mapsto g^c$$

示例 40

已知有限循环群 $(\Z^*_5, \cdot)$ ，其阶数为 4 (参见 示例 34)，且 4 有 1、2 和 4 三个因子，因此根据有限循环群基本定理，$\Z^*_5$ 存在三个不同的子群。事实上， 1 阶唯一子群 $\Z^*_5[1]$ 是由仅包含乘法幺元的 $1$ 的平凡群 $\{1\}$ 组成的。 4 阶子群 $\Z^*_5[4]$ 是 $\Z^*_5$ 本身，根据定义，每个群都是其自身的平凡子群。2 阶子群 $\Z^*_5[2]$ 是有趣的，由集合 $\Z^*_5[2]=\{1,4\}$ 给出。

由于 $\Z^*_5$ 不是素数阶群，并且由于 4 的唯一素数因子是 2 ，因此 $\Z^*_5$ 的最大素数阶子群是 $\Z^*_5[2]$ 。此外，由于 2 和 4 的共因子是 2 (共因子概念请参考 符号-1) ，我们得到了共因子清除映射 $(\cdot)^2:\Z^*_5 \to \Z^*_5[2]$ 。当我们对 $\Z^*_5$ 的所有元素使用此映射，我们分析 $\Z^*_5$ 的所有元素都被映射到 $\Z^*_5[2]$ 中:

$$1^2 = 1\quad{} 2^2 = 4\quad{} 3^2 = 4\quad{} 4^2 = 1$$

因此，我们可以使用此映射对任何来自 $\Z^*_5$ 的元素进行共因子清除。共因子清除的结果是元素被映射到大素数阶子群 $\Z^*_5[2]$ 中。

练习 39. 已知 示例 40 ，证明 $\Z^*_5[2]$ 是一个 交换群

练习 40. 已知模 6 加法的有限循环群 $(\Z_6, +)$ ，描述此群的所有子群。识别 $\Z_6$ 的大素数阶子群，定义共因子清除映射并将其对 $\Z_6$ 的所有元素使用。

练习 41. 已知 $(\Z^*_p, \cdot)$ 是一个循环群，证明对于 $p \geq 5$ ，并不是所有元素 $x \in \Bbb{F}^*_p$ 是 $\Bbb{F}^*_p$ 的生成元。

对于 SNARKs 发展特别重要的概念是 配对映射(pairing maps)，定义如下:

设 $\Bbb{G}_1$，$\Bbb{G}_2$ 和 $\Bbb{G}_3$ 是三个交换群，那么配对映射是一个函数:

$$e(\cdot,\cdot): \Bbb{G}_1 \times \Bbb{G}_2 \to \Bbb{G}_3$$

此函数使用 $\Bbb{G}_1$ 和 $\Bbb{G}_2$ 中的元素对 $(g_1,g_2)$ ，并将其映射为 $\Bbb{G}_3$ 中的元素，在此过程中满足 双线性(bilinearity) 。双线性的含义是对于所有的 $g_1, g_1' \in \Bbb{G}_1$ 和 $g_2, g_2' \in \Bbb{G}_2$ 都满足以下等式:

$$ \begin{array}{lcr} e(g_1 \cdot g_1',g_2)= e(g_1,g_2)\cdot e(g_1',g_2) &\text{and}& e(g_1,g_2 \cdot g_2')= e(g_1,g_2)\cdot e(g_1,g_2')\ \end{array} $$

通俗地说，双线性是指在先执行群法则再进行映射，或先进行映射再在 $\Bbb{G}_3$ 中执行群法则的结果相同。

如果配对结果是 $\Bbb{G}_3$ 中的幺元，并且其中一个输入是 $\Bbb{G}_1$ 或 $\Bbb{G}_2$ 中的幺元，那么我们称配对映射是 非退化(non-degenerate) 的。更加精确的表述是，如 $e(g_1, g_2) = e_{\Bbb{G}_2}$ 成立，则必有 $g_1 = e_{\Bbb{G}_1}$ 或 $g_2 = e_{\Bbb{G}_2}$

示例 41

一个非退化配对的最基本的示例是 $\Bbb{G}_1$，$\Bbb{G}_2$ 和 $\Bbb{G}_3$ 均为具有加法的整数群 $(\Z, +)$ 。在这种情况下，以下映射是非退化配对映射:

$$ e(\cdot,\cdot): \Z \times \Z \to \Z ; (a,b)\mapsto a\cdot b $$

请注意，通过整数分配律可以推出双线性。设 $a, b, c \in \Z$ ，根据乘法分配律，等式 $e(a+b,c)=(a+b)\cdot c = a\cdot c + b\cdot c = e(a,c)+ e(b,c)$ 成立。

为证明 $e(\cdot,\cdot)$ 是非退化的，假设 $e(a, b) = 0$ 成立，那么必然可以推出 $a$ 或 $b$ 为 0

练习 42. (配对映射的算术定理)

设 $\Bbb{G}_1$，$\Bbb{G}_2$ 和 $\Bbb{G}_3$ 是同阶的有限循环群，其阶数均为 $n$ ，且存在 $e(\cdot, \cdot): \Bbb{G}_1 \times \Bbb{G}_2 \to \Bbb{G}_3$ 是一个配对映射。证明，对于给定的 $g_1 \in \Bbb{G}_1$ 和 $g_2 \in \Bbb{G}_2$ 和任意的 $a, b \in \Z_n$ ，以下等式均成立:

$$e(g_1^a, g_2^b) = e(g_1,g_2)^{a\cdot b}$$

练习 43. 对于某模数 $n$ ，已知同余类群 $(\Z_n, +)$ ，证明以下映射是一个配对映射:

$$ e(\cdot,\cdot): \Z_n \times \Z_n \to \Z_n ; (a,b)\mapsto a\cdot b $$

为什么此配对通常不是非退化的，必须对 $n$ 施加什么条件才能使配对具有非退化的性质？

在本节中，我们将研究被认为满足某些 计算难度假设(computational hardness assumptions)的群。这些群无法在多项式时间内完成计算。

示例 42

举一个众所周知的满足计算难度假设的例子，即因式分解问题，如计算合数的质因子(参见 示例 1)。如果质因数非常大，计算质因子是不可能的，并且预计在未来仍不可能、我们可以假定质因数分解问题是计算困难的或计算不可行的。

注意，在 示例 42 中，计算不可行的前提是质因子足够大。理所当然，该表述在密码学标准模型中会更加精确。在密码学标准模型中，我们会给出一个安全参数，并描述为“存在一个安全参数使得计算问题的解不可行”。在以下示例中，安全参数与所介绍的群的顺序大致相关。在本书中，我们不会给出安全参数的定义，因为我们的目标是提供对密码学假设的直观理解，而不是教授严格的密码学安全性证明。

此外，请理解这些仅是假设。长期以来，学术界一直探索高效的质因子分解算法，并且随着计算机速度的加快，质因子分解算法的表现逐渐变好，但总有一个更高的安全参数是质因子分解问题无法使用现有算法求解。

在下文中，我们描述了在密码学群概念下的一些问题，这些问题均被认为满足计算难度假设。在本书中，我们将多次引用这些满足计算难度假设的问题。

所谓的 离散对数问题(Discrete Logarithm Problem, DLP) ，亦被称为 离散对数假设(Discrete Logarithm Assumption) 是密码学中最重要的假设。

设 $\Bbb{G}$ 是一个 $r$ 阶有限循环群，且生成元为 $g$ 。已知存在指数映射 $g^{(\cdot)}: \Z_r \to \Bbb{G} ; x\mapsto g^x$ ，该映射将 模 r 算术中的剩余类 1 : 1 的映射到对应的群中。离散对数问题的任务就是找到该映射的逆，即对于给定的 $h,g \in \Bbb{G}$ ，可以找到解 $x \in \Z_r$ 满足等式:

$$ h = g^x$$

在某些群内， DLP 被假设为无法求解，但在另一些群内可以求解。我们称前者为 DL 安全群(DL-secure)

重述前定义，在 DL 安全群内，存在足够大的阶 $n$ ，使得对于给定的 $h$ 和 $g$ 无法对 $h = g^x$ 求解获得 $x$。此处的 $n$ 就是上文讨论的安全参数。

示例 43

DL 安全群应用最基础的示例之一是在公钥密码学中。参与公钥密码学的各方都认可 $(\Bbb{G}, g)$ ，其中 $\Bbb{G}$ 是一个具有合适阶数 $n$ 的有限群且满足 DL 安全群的定义， $g$ 是 $\Bbb{G}$ 的生成元。

在此设定中，密钥是某个数 $sk \in \Z_r$ ，对应的公钥 $pk$ 是一个群元素 $pk = g^{sk}$。因为离散对数算法被假定为无法执行，所以攻击者无法通过公钥计算出对应的私钥，因为求解私钥涉及以下方程的解:

$$pk = g^x$$

如示例 43 所述，识别 DL 安全群是一个重要的实际问题。不幸的是，假设所有的有限循环群中的离散对数计算都是困难的是没有意义的，我们可以很容易通过反例推翻这一假设。

设 $\Bbb{G}$ 是 n 阶有限循环群且生成元为 $g$ 。决策性 Diffie-Hellman(decisional Diffie–Hellm, DDH) 问题是对于均匀随机值 $a,b,c \in \Z_r$ ，可以区分 $(g^a, g^b, g^{ab})$ 与三元组 $(g^a, g^b, g^c)$ 区分开来。

如果我们认为 DDH 问题在 $\Bbb{G}$ 求解不可行，我们称为 $\Bbb{G}$ 是 DDH 安全群(DDH-secure group)

DDH 安全群是比 DLP 安全群更严格的假设，因为如果 DDH 问题不可行，那么 DLP 也不可行，但反之则不一定成立。

要证明以上结论，我们假设离散对数假设不成立。在这种情况下，给定一个生成元 $g$ 和一个群元素 $h$ ，我们容易计算出 $x \in \Z_p$ 满足 $h = g^x$ 。那么，决策性 Diffie-Hellman 假设也不成立，因为对于给定的三元组 $(g^a, g^b, z)$ ，我们可以首先计算出 $b$ ，然后计算 $g^{ab} = (g^a)^b$ 并确定 $z = g^{ab}$ 是否成立。

另一方面，以下示例展示了离散对数假设成立但决策性 Diffie-Hellman 假设不成立的群。

示例 44

设 $\Bbb{G}$ 是一个有限循环且生成元为 $g$ 的 $r$ 阶 DL安全群，另有 $\Bbb{G}_T$ 使得存在一个有效的可高效计算的配对映射 $e(\cdot,\cdot): \Bbb{G} \times \Bbb{G} \to \Bbb{G}_T$ ，且此配对映射是双线性和非退化的。

在这样的设定下，很容易证明 DDH 是可行的，因为对于给定的三元组 $(g^a, g^b, z)$ ，可以通过以下配对检查 $z = g^{ab}$ 是否成立:

$$ e(g^a,g^b) \overset{?}{=} e(g,z) $$

由于 $e(\cdot, \cdot)$ 具有双线性，这意味着 $e(g^a, g^b) = e(g, g)^{ab} = e(g, g^{ab})$ 并且通过 $e(g,y) = e(g, y')$ 可以推出 $y=y'$ 。由于非退化性，等式意味着 $z = g^{ab}$

由此可见， DDH 假设确实强于离散对数假设，且具有有效配对的群不可能是 DDH 安全群。

设 $\Bbb{G}$ 是 n 阶有限循环群且生成元为 $g$ 。计算性 Diffie-Hellman 假设规定，对于给定独立随机元素 $a, b \in \Z_r$ ，如果仅知道 $g, g^a, g^b$ (但是不知道 $a,b$ 的值) ，无法计算 $g^{ab}$ 。如果 $\Bbb{G}$ 符合这一假设，那么我们称 $\Bbb{G}$ 为 CDH安全(CDH-secure)群

一般来说，我们不知道 CDH 安全假设是否比 DL安全假设更加严格，或者这两个假设是否等效。我们知道 DL 假设对 CDH 假设 是必要的，但是另一个方向目前还不是很清楚。特别是，目前没有已知的 DL 安全群不符合 CDH 安全假设。

要了解离散对数假设对 CDH 假设是必要的，我们可以首先假设该结论不成立，使用反证法。那么，给定生成元 $g$ 和一个群元素 $h$ ，很容易计算出某元素 $x \in \Z_p$ 符合 $h = g^x$ 。在这种情况下，计算性 Diffie-Hellman 假设不成立，因为给定 $g, g^a, g^b$ ，可以有效计算出 $b$ ，这意味着 $g^{ab} = (g^a)^b$ 可以这个数据中计算出来。

计算性 Diffie-Hellman 假设是一个比 决策性 Diffie-Hellman 更弱的假设。这意味着存在 CDH 成立但 DDH 不成立的群，但不存在 DDH 成立而 CDH 不成立的群。为证明此结论，假设可以有效地使用 $g, g^a, g^b$ 计算得到 $g^{ab}$ 。那么，给定 $(g^a, g^b, z)$ 很容易判断 $z = g^{ab}$ 是否成立。

存在几种 CDH 存在的变体和特殊情况。比如，平方计算 Diffie-Hellman 假设(square Computational Diffie-Hellman Assumption) 假设，给定 $g, g^x$ ，计算 $g^{x^2}$ 是困难的。逆计算 Diffie-Hellman 假设(inverse Computational Diffie–Hellman Assumption) 假设对于给定 $g, g^x$，计算 $g^{-1}$ 是困难的。

哈希到群

一般来说，哈希函数是可用于将任意长度的数据映射到定长数据的任何函数。由于任意长度的二进制字符串通常是表示数据的一种方式，我们可以将哈希函数理解为以下映射:

$$H: \{0,1\}^* \to \{0,1\}^k$$

其中 $\{0,1\}^*$ 表示任意但有限长度的所有二进制字符串的集合，$\{0,1\}^k$ 表示看到长度恰好为 $k$ 位的二进制字符串的集合。

$H$ 的像(images) ，即哈希函数 $H$ 的返回值，被称为 哈希值(hash value)、摘要(digests) 或简称为 哈希(hashes)

符号 8

在下文中，我们称元素 $b \in \{0, 1\}$ 为 1 bit 。如果 $s \in \{0,1\}^*$ 是二进制字符串，我们称 $|s| = k$ 是其长度，即 $s$ 的位数。我们使用 $<>$ 表示空字符串，使用 $s=<b_1,b_2,\ldots,b_k>$ 表示 k 位长的二进制字符串。

如果给定两个二进制字符串 $s=<b_1,b_2,\ldots,b_k>$ 和 $s'=<b'_1,b'_2,\ldots,b'_l>$ ，我们使用 $s||s'$ 表示字符串 拼接(concatenation)，即 $s||s'=<b_1,b_2,\ldots,b_k,b'_1,b'_2,\ldots,b'_l>$

如果 $H$ 是一个哈希函数，将任意长度的二进制字符串 $s \in \{0, 1\}^*$映射到长度为 $k$ 的二进制字符串，我们记 $H(s)_j$ 是像 $H(s)$ 的第 $j$ 位。

示例 45

最基本的哈希函数 $H_k:\{0,1\}^*\to \{0,1\}^k$ 是通过简单的截断或填充实现哈希。设存在二进制字符串 $s$ ，如果 $|s| > k$，那么我们直接阶段大于 $|s|$ 的字段; 如果 $|s| < k$，那么我们通过填充 $0$ 以实现长度。为了使该哈希函数具有确定性，我们定义截断和填充都应该发生在左侧。

比如，如果参数 $k = 3$，使用此哈希函数处理 $s_1=<0,0,0,0,1,0,1,0,1,1,1,0>$ 和 $s_2=1$ ，那么哈希后的结果位 $H_3(s_1)=<1,1,0>$ 和 $H_3(s_2)=<0,0,1>$

哈希函数的一个理想属性是 均匀性(uniformity)，这意味着哈希函数应尽可能将输入值均匀的映射到输出空间。使用数学术语表示，任意来自 $\{0, 1\}^k$ 长度为 $k$ 的字符串都应该以大致相同的概率生成输出结果。

特别令人感兴趣的是密码学哈希函数，该函数是一个单向函数。这实质上意味着给定来自 $\{0,1\}^k$ 的字符串 $y$ ，不可能找到一个字符串 $x \in \{0, 1\}^*$ 使得 $H(x)=y$ 成立。该属性通常被称为 抗原象形(preimage-resistanc)

此外，如果给定一个字符串 $x_1 \in \{0,1\}^*$ 那么找到另一个字符串 $x_2 \in \{0,1\}^*$ 使其满足 $H(x_1)=H(x_2)$ 是不可能的。

另外，要找到两个字符串 $x_1, x_2 \in \{0,1\}^*$ 使其满足 $H(x_1)=H_(x_2)$ 是不可行的，称为 抗碰撞性(collision resistance)。需要注意的是，碰撞总是存在的，因为函数 $H: \{0,1\}^* \to \{0,1\}^k$ 的输入是无限多的，不可避免的产生碰撞。事实上，对于任何产生长度为 $k$ 的哈希函数，找到给定摘要的原象总是需要 $2^k$ 的暴力搜索。计算这些值实际上是不可能的，也不太可能偶然产生具有相同哈希值。

密码学哈希函数的第三个属性是输入的微小变化(如更改单个位)应该生成看起来完全不同的哈希值。这被称为 扩散(diffusion) 或雪崩效应。

由于密码学哈希函数将输入的微小变化映射位输出值的较大变化，因此通过将输出与预期输出进行比较，我们较为容易发现哈希函数实现的错误。因此，密码学哈希函数的定义通常包含一些常见输出和预期输出的哈希值的测试向量。由于空字符串 $<>$ 是唯一长度为 0 的字符串，因此常见的测试向量都包含空字符串的哈希值。

示例 46

考虑 示例 45 中的 k 截断哈希函数。由于空字符串的长度为 0 ，因此空字符串的哈希是长度为 $k$ 且仅包含 0 的字符串:

$$H_k(<>)= <0,0,\ldots, 0,0>$$

从 $H_k$ 的定义可以明显看出，这个简单的哈希函数不符合密码学哈希函数的定义。特别的是，每个哈希值都是自己的原象，因为对于长度为 $k$ 的字符串， $H_k(y)=y$。因此我们很容易找到原象，所以抗原象性的性质不成立。

此外，很容易构造碰撞，因为所有长度 $|s| > k$ 且右侧 k 位相同的字符串均对应相同的哈希值。这意味着该哈希函数不是抗碰撞的。

最后，该哈希函数没有太多的扩散，因为如果不改变最右边 k 位的数据根本不会改变哈希值。

使用纸笔计算密码学安全级别的哈希函数是可能的，但是很乏味。幸运的是， Sage 提供了 hashlib 库。该库提供了一系列的函数帮助用户使用 Python 编写可靠和稳定的包含哈希函数的代码。以下示例展示了如何在 Sage 中使用 hashlib

示例 47

一个用于被认为可以生产密码学安全的哈希函数是 SHA256 哈希函数。正如上文讨论的概念，该函数可以将任意长度的二进制字符串映射为长度为 256 位的二进制字符串:

$$ \text{SHA256}: \{0, 1\}^* \to \{0, 1\}^{256}$$

为了评估 SHA256 哈希函数的正确实现，对于空字符串的哈希结果如下:

$$ \text{SHA256}(<>) = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 $$

为了具有更好的人类可读性，通常的做法是使用 16 进制而不是 2 进制形式展示哈希结果。我们可以使用 Sage 计算哈希结果，并将其自由地在二进制、十六进制和十进制之间转化。为此，我们导入 hashlib 的 SHA256 实现:

sage: import hashlib
sage: test = 'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'
sage: empty_string = ""
sage: binary_string = empty_string.encode()
sage: hasher = hashlib.sha256(binary_string)
sage: result = hasher.hexdigest()
sage: type(result)
<class 'str'>
sage: d = ZZ('0x' + result)
sage: d.str(16) == test
True
sage: d.str(16)
'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'
sage: d.str(2)
'1110001110110000110001000100001010011000111111000001110000010100100110101111101111110100110010001001100101101111101110010010010000100111101011100100000111100100011001001001101110010011010011001010010010010101100110010001101101111000010100101011100001010101'
sage: d.str(10)
'102987336249554097029535212322581322789799900648198034993379397001115665086549'

正如我们在上一节所看到的，一般哈希函数将任意长度的二进制字符串映射到固定长度。但是，在各种密码学原语中，最好不要简单的认为哈希函数的结果是固定长度的字符串，而是认为哈希函数产生了类似群一样的代数结构，同时保持了哈希函数的一些特性，比如抗原象形和抗碰撞性。

这样的哈希函数可以定义在不同的代数结构上，但从某种意义上来说，最基本的哈希函数是映射到群的哈希函数，因为这样的哈希函数可以很容易地拓展到其他代数结构中，如环或域。

下面给出更加精确的定义，设 $\Bbb{G}$ 是一个群，$\{0, 1\}^*$ 是所有有限的二进制字符串构成的集合，那么哈希到群(hash-to-group)函数是确定性的映射:

$$ H: \{0,1\}^* \to \Bbb{G}$$

如以下示例所示，哈希函数函数可以通过舍弃一些属性实现哈希结果为有限循环群。

示例 48

设 $\Bbb{G}$ 是一个 n 阶有限循环群，如果我们想实现一个哈希到群的函数，一个直接方法是可以基于以下观察结果: 大小为 k 的二进制字符串都可以解释为一个整数 $z \in \Z$ 且范围为 $0\leq z < 2^k$ 。

更加准确地说，设 $H: \{0,1\}^* \to \{0,1\}^k$ 是一个由参数 $k$ 定义的哈希函数，$g$ 是 $\Bbb{G}$ 的生成元，而 $s \in \{0,1\}^*$ 是一个二进制字符串。我们可以使用以下等式表示哈希结果:

$$z_{H(s)}= H(s)_0\cdot 2^0 + H(s)_1\cdot 2^1 + \ldots + H(s)_k \cdot 2^k$$

哈希到群 $\Bbb{G}$ 函数可以被定义为指数映射和 $H(s)$ 整数表示的组合:

$$H_{g} : {0,1}^* \to \Bbb{G}: s \mapsto g^{z_{H(s)}}$$

构造这样的哈希到群函数是简单的，且对于部分应用已经足够好了。然而在密码学应用中，该函数是没有足够安全保证的，我们可以在离散值 $H_g(s)$ 和 $H_g(t)$ 中构造离散对数关系，无论 $\Bbb{G}$ 是否是 DL 安全群。

更加准确的说，群元素 $H_g(s)$ 和 $H_g(t)$ 之间的离散关系是对于任何 $x \in \Z_n$ 都有 $H_g(s) = h_g(t)^x$ 成立。要了解如何构造满足此条件的 $x$ ，设 $z_{H(s)}$ 在 $\Z_n$ 中存在乘法逆元。在这种条件下，元素 $x=z_{H(t)}\cdot z_{H(s)}^{-1}$ 是 $H_g(s)$ 和 $H_g(t)$ 存在离散对数关系:

$$ \begin{align*} g^{z_{H(t)}} & = g^{z_{H(t)}} & \Leftrightarrow\\ g^{z_{H(t)}} & = g^{z_{H(t)}\cdot z_{H(s)}\cdot z_{H(s)}^{-1}} & \Leftrightarrow \\ g^{z_{H(t)}} & = g^{z_{H(s)}\cdot x} & \Leftrightarrow \\ H_g(t) & = (H_g(s))^x \end{align*} $$

因此，在哈希值之间存在离散对数关系的应用是不受欢迎的，我们需要一些其他方法构造哈希到群函数，这些方法始于在模 $r$ 的 $\Z_r$ 算术体系内进行哈希计算。