9.Number Theory and Cryptographic Hardness Assumptions

现代密码系统无一例外地基于某个难题的假设。例如，在第3至5章中，我们看到私钥密码学，包括加密方案和消息认证码，可以基于伪随机置换（又称分组密码）存在的假设。表面上看，伪随机置换存在的假设似乎非常强大和不自然，有理由质疑这个假设是否成立，或者是否有任何证据支持它。在第7章中，我们探讨了分组密码在实践中的构造方式。这些构造能够抵御攻击的事实表明伪随机置换的存在是合理的。然而，人们可能难以相信对现有分组密码不存在有效的区分攻击。此外，我们目前的理论状态是，我们不知道如何基于任何“更简单”或“更合理”的假设来证明任何现有实际构造的伪随机性。总的来说，这不是一个完全令人满意的情况。

相比之下，正如第3章中提到的（并在第8章中详细研究），可以基于较为温和的单向函数存在的假设来证明伪随机置换的存在。（非正式地说，如果一个函数易于计算但难以反转，则称其为单向函数；请参见第9.4.1节。）然而，除了在第8.1.2节中简要讨论外，我们还没有看到任何被认为是单向函数的具体示例。

本章的一个目标是介绍一些被认为“困难”的问题，并基于这些问题提出猜想的单向函数。从这个角度看，本章可以被视为私钥密码学的“自上而下”方法的高潮。 （见图9.1。）也就是说，在第3至5章中，我们已经展示了私钥密码学可以基于伪随机函数和置换。然后，我们已经看到后者可以通过在第7章中探讨的分组密码实际实现，或者可以根据任何单向函数构造出，正如在第8章中所示。在这里，我们进一步展示了如何基于某些困难的数学问题来构建单向函数。

我们将探讨的示例是与数论相关的，因此我们首先进行一个简短的数论介绍。由于我们还对能够高效解决的问题感兴趣（即使单向函数在一方向上必须易于计算，而且密码方案必须允许诚实参与者使用高效算法），我们还会启动对算法性数论的研究。即使对数论已经熟悉的读者，也鼓励阅读本章，因为算法方面的内容在纯粹的数学处理中通常被忽略。

本章的第二个目标是为公钥密码学的发展提供所需的材料，我们将在第11章开始研究公钥密码学。引人注目的是，在私钥环境中，存在着不需要涉及任何数论即可构建所需基元（分组密码和哈希函数）的高效方法，然而在公钥环境中，所有已知的构造都依赖于困难的数论问题。因此，本章的内容不仅作为我们对私钥密码学研究的顶点，还作为我们处理公钥密码学的基础。

9.1 预备知识和基本群论

我们开始复习素数和基本的模算术知识。即使是之前已经了解过这些内容的读者，也应该浏览一下接下来的两节，因为其中一些材料可能是新的，我们会为大部分陈述的结果提供证明。

9.1.1 素数与整除性

整数集合用$\mathbb{Z}$表示。对于$a,b\in \mathbb{Z}$，如果存在整数$c$使得$ac=b$，我们称$a$整除$b$，记作$a|b$。如果$a$不能整除$b$，则记作$a\nmid b$。（尽管定义允许其中一个或多个数为负数或零，我们主要关注所有数都为正数的情况。）一个简单的观察是，如果$a|b$且$a|c$，则对于任意$X,Y\in \mathbb{Z}$，都有$a|(Xb+Yc)$。

如果$a|b$且$a$为正数，则称$a$是$b$的因子。如果进一步有$a\notin \{1,b\}$，则称$a$为$b$的非平凡因子。大于1的正整数如果没有其他因子，则称其为素数，即它只有两个因子：1和它本身。大于1的正整数如果不是素数，则称其为合数。按照约定，数字1既不是素数也不是合数。

算术基本定理指出，大于1的每个整数都可以唯一地（忽略顺序）表示为素数的乘积。也就是说，任何大于1的正整数$N>1$都可以写成$N=\prod _i{p}_i^{e_i}$，其中$p_i$是不同的素数，$e_i\ge 1$对于所有$i$成立；此外，$p_i$（和$e_i$）在去掉顺序后是唯一确定的。

命题 9.1: 设$a$是一个整数，$b$是一个正整数。那么存在唯一的整数$q$、$r$，满足$a=qb+r$且$0\le r<b$。

此外，对于命题中的整数$a$和$b$，可以在多项式时间内计算出$q$和$r$；见附录B.1。（算法的运行时间是其输入长度的函数。在算法数论的上下文中，整数输入总是假定用二进制表示。因此，算法的运行时间是以$||N||$，即$N$的二进制表示的位数，来衡量的。注意$||N||=|\log N|+1$。）

两个整数$a$、$b$的最大公约数，记作$gcd(a,b)$，是满足$c|a$且$c|b$的最大整数$c$。（我们将$gcd(0,0)$视为未定义。）最大公约数的概念在$a$和$b$中有一个或两个为负数时也是成立的，但我们通常有$a,b\ge 1$；无论如何，$gcd(a,b)=gcd(|a|,|b|)$。注意$gcd(b,0)=gcd(0,b)=b$；此外，如果$p$是素数，则$gcd(a,p)$要么等于1，要么等于$p$。如果$gcd(a,b)=1$，我们称$a$和$b$互素。

TIP

陈述1： "如果 p 是素数，则 gcd(a, p) 要么等于 1，要么等于 p。"

• 这个陈述的意思是，如果 p 是一个素数，那么任意整数 a 和 p 的最大公约数（gcd）要么是 1，要么是 p。
• 如果 a 不是 p 的倍数（即 a % p ≠ 0），那么 gcd(a, p) = 1，因为素数 p 确保它与任何不是 p 的倍数的整数没有除了 1 以外的共因子。
• 如果 a 是 p 的倍数（即 a % p = 0），那么 gcd(a, p) = p，因为在这种情况下，p 是 a 和 p 之间唯一的共因子。

陈述2： "如果 gcd(a, b) = 1，我们称 a 和 b 互质。"

• 这个陈述同样是正确的。两个整数 a 和 b 被称为互质（或互素），如果它们的最大公约数是 1。 这两个陈述都是数论中的基本概念。

以下是一个有用的结果：

命题 9.2: 设$a$、$b$是正整数。那么存在整数$X$、$Y$，使得$Xa+Yb=gcd(a,b)$。此外，$gcd(a,b)$是能以这种方式表达的最小正整数。

这个结论被称为贝祖等式（Bézout's identity）或贝祖定理（Bézout's theorem）。它说明对于任意两个正整数$a$和$b$，存在整数$X$和$Y$，使得$Xa+Yb=gcd(a,b)$。这个等式的特殊情况是当$gcd(a,b)=1$时，即$a$和$b$互质，此时存在整数$X$和$Y$使得$Xa+Yb=1$。

此外，贝祖等式也指出$gcd(a,b)$是可以用这种方式表示的最小正整数，也就是说，不存在比$gcd(a,b)$更小的正整数可以用$a$和$b$的线性组合表示。这可以通过贝祖定理的证明来理解。

举例：

考虑$a=48$和$b=18$。它们的最大公约数是$gcd(48,18)=6$。

根据贝祖定理，我们可以找到整数$X$和$Y$使得$Xa+Yb=gcd(48,18)=6$。一个可能的选择是$X=1$和$Y=-2$，因为$1\cdot 48+(-2)\cdot 18=6$。

根据贝祖等式，我们可以写出$Xa+Yb=d^2$，即$1\cdot 48+(-2)\cdot 18=6^2$，也就是$48-36=12$。这再次确认了$d^2=gcd(48,18)=6$。

所以，这个例子验证了贝祖定理中关于$gcd(a,b)$和$Xa+Yb$的关系。

证明：

令$d=gcd(a,b)$为$a$和$b$的最大公约数。根据贝祖定理，存在整数$X$和$Y$使得$Xa+Yb=d$。

现在，考虑任意整数$x$和$y$，使得$x=X\cdot \frac{d}{gcd(a,b)}$ 和 $y=Y\cdot \frac{d}{gcd(a,b)}$。注意到$\frac{d}{gcd(a,b)}$是一个整数，因为$d$是$gcd(a,b)$的倍数。

将$x$和$y$代入上述等式中得到：

$$xa+yb=X\cdot \frac{d}{gcd(a,b)}\cdot a+Y\cdot \frac{d}{gcd(a,b)}\cdot b=d\cdot (Xa+Yb)=d^2$$

因此，对于任意整数$x$和$y$，都有$xa+yb$是$d^2$的倍数。这意味着$d$是$xa+yb$ 的一个公约数。

另一方面，由于$d=gcd(a,b)$，$d$是$a$和$b$的一个公约数，因此$d$也是$xa+yb$的一个公约数。

综上所述，$d$是$a$和$b$以及任意$xa+yb$的公约数，这意味着$d$是$a$和$b$以及$xa+yb$的最大公约数，即$d$是$gcd(a,b)$和$xa+yb$的最大公约数。由于$d^2$是$gcd(a,b)$和$xa+yb$的一个公约数，而$d$是其最大公约数，因此$d^2\le gcd(a,b)$。

但是我们也知道$d=gcd(a,b)$，因此$d^2\ge gcd(a,b)$。结合两个不等式，我们得到$d^2=gcd(a,b)$，因此$gcd(a,b)$是$d^2$的一个因数。

由于$d$是正整数，所以$d^2$的因数只能是$d$本身或者$1$。但因为$gcd(a,b)\ge 1$，所以只有$d=gcd(a,b)$是可能的。因此，我们得出结论$gcd(a,b)=d^2$。

命题 9.3： 如果 $c|ab$ 且 $gcd(a,c)=1$，则 $c|b$。因此，如果 $p$ 是素数且 $p|ab$，则要么 $p|a$ 或 $p|b$。

例子：

假设 $a=15$，$b=7$，$c=3$。我们来验证命题 9.3 是否适用于这些值。

首先，$c|ab$，因为 $3$ 是 $105$ 的约数，即 $c|ab$ 成立。

然后，我们检查 $gcd(a,c)$ 是否为 $1$。计算 $gcd(15,3)$，得到 $3$。由于 $gcd(a,c)\ne 1$，这部分条件不满足，所以这个例子不符合命题中的要求。

因此，根据命题 9.3，我们不能得出 $c|b$，这在这个例子中是正确的，因为 $3$ 并不整除 $7$。

这个例子说明了命题 9.3 中的条件和结论的作用：即使 $c|ab$，但如果 $gcd(a,c)\ne 1$，则不能保证 $c|b$。而如果 $gcd(a,c)=1$，根据命题，我们可以确信 $c|b$。

证明： 由于 $c|ab$，我们有整数 $\gamma$ 使得 $\gamma c=ab$。如果 $gcd(a,c)=1$，则根据前一个命题，存在整数 $X$ 和 $Y$，使得 $1=Xa+Yc$。将两边都乘以 $b$，我们得到

$$b=Xab+Ycb=X\gamma c+Ycb=c\cdot (X\gamma +Yb)$$

由于 $X\gamma +Yb$ 是整数，所以 $c|b$，即 $c$ 整除 $b$。

命题的第二部分基于这样的事实：如果 $p$ 不能整除 $a$（即 $p\nmid a$），且 $p$ 是素数，则 $gcd(a,p)=1$。这是因为如果 $p$ 和 $a$ 有大于 1 的公因数，那么 $p$ 将会整除 $a$，这与我们的假设相矛盾。

综上所述，这个命题说明了如果 $c$ 整除乘积 $ab$，且 $a$ 和 $c$ 互质，那么 $c$ 也将整除 $b$。此外，如果素数 $p$ 整除乘积 $ab$，则要么它整除 $a$，要么整除 $b$（或者同时整除两者）。

命题 9.4 如果 $a|N$，$b|N$，且 $gcd(a,b)=1$，那么 $ab|N$。

例子： 假设我们有两个正整数 $a=6$ 和 $b=35$，并且我们希望证明当 $gcd(a,b)=1$ 时，$ab$ 能够整除某个正整数 $N$。

首先，计算 $gcd(a,b)$，我们有 $gcd(6,35)=1$，满足条件。然后我们可以找到整数 $X$ 和 $Y$，使得 $Xa+Yb=1$，一个可能的组合是 $X=9$ 和 $Y=-1$，因为 $9\cdot 6+(-1)\cdot 35=1$。

现在，我们将这个等式两边都乘以一个正整数 $N$，假设 $N=210$：

$$\begin{array}{rl}N& =XaN+YbN\\ 210& =9\cdot 6\cdot 210+(-1)\cdot 35\cdot 210\\ 210& =9\cdot 1260-1\cdot 735\\ 210& =11340-735\\ 210& =10605.\end{array}$$

我们可以看到，$ab=6\cdot 35=210$ 能够整除 $N=210$。因此，根据命题 9.4，当 $gcd(a,b)=1$ 时，$ab$ 能够整除某个正整数 $N$。

证明： 我们令 $ac=N$ 和 $bd=N$，并使用命题 9.2 得到 $1=Xa+Yb$，其中 $c,d,X,Y$ 都是整数。将上述方程的两边同时乘以 $N$，我们得到：

$$N=XaN+YbN=Xabd+Ybac=ab(Xd+Yc),$$

由此可见 $ab|N$。

9.1.2 模算术

设 $a$、$b$ 和 $N\in \mathbb{Z}$（整数集合），其中 $N>1$。我们使用符号 $[amodN]$ 表示 $a$ 除以 $N$ 的余数。更详细地说：根据命题 9.1，存在唯一的 $q$ 和 $r$，满足 $a=qN+r$，且 $0\le r<N$，我们定义 $[amodN]$ 等于这个 $r$。因此请注意，$0\le [amodN]<N$。我们将将 $a$ 映射到 $[amodN]$ 的过程称为模 $N$ 的约化。

如果$[amodN]=[bmodN]$，即 $a$ 除以 $N$ 的余数与 $b$ 除以 $N$ 的余数相同，我们称 $a$ 与 $b$ 模 $N$ 同余，记作 $a=b(\mathrm{mod}N)$。请注意，当且仅当 $N|(a-b)$ 时，$a=b(\mathrm{mod}N)$。在表达式中，如

$$a=b=c=\dots =z(\mathrm{mod}N)$$

理解是这个序列中的每个等号（不仅仅是最后一个）都指的是模 $N$ 同余。

注意，$a=[bmodN]$ 意味着 $a=b(\mathrm{mod}N)$，但反之不成立。例如，$36=21(\mathrm{mod}15)$，但 $36\ne [21mod15]=6$。另一方面，当且仅当 $a=b(\mathrm{mod}N)$ 时，$[amodN]=[bmodN]$。

模 $N$ 同余是一个等价关系，即它是自反的（对于所有 $a$，$a=a(\mathrm{mod}N)$）、对称的（$a=b(\mathrm{mod}N)$ 意味着 $b=a(\mathrm{mod}N)$）、以及传递的（如果 $a=b(\mathrm{mod}N)$ 且 $b=c(\mathrm{mod}N)$，则 $a=c(\mathrm{mod}N)$）。模 $N$ 同余还遵循关于加法、减法和乘法的标准算术规则。因此，例如，如果 $a=a^{{}^{\prime }}(\mathrm{mod}N)$，$b=b^{{}^{\prime }}(\mathrm{mod}N)$，则 $a+b=a^{{}^{\prime }}+b^{{}^{\prime }}(\mathrm{mod}N)$，$ab=a^{{}^{\prime }}{b}^{{}^{\prime }}(\mathrm{mod}N)$。一个结果是我们可以“先缩减再相加/相乘”，而不必“先相加/相乘再缩减”，这常常可以简化计算。

示例 9.5

让我们计算 $[1093028\cdot 190301mod100]$。由于 $1093028=28mod100$ 且 $190301=1mod100$，我们有

$$\begin{gathered} 1093028\cdot 190301=[1093028mod100]\cdot [190301mod100]mod100 \\ =28\cdot 1=28mod100. \end{gathered}$$

另一种计算答案的方法（即计算乘积 $1093028\cdot 190301$，然后对结果进行模 $100$ 的约化）不够高效。模 $N$ 同余一般情况下不保持除法。也就是说，如果 $a=a^{{}^{\prime }}modN$ 且 $b=b^{{}^{\prime }}modN$，则通常不成立 $a/b=a^{{}^{\prime }}/b^{{}^{\prime }}modN$；事实上，“$a/bmodN$” 这个表达式通常并没有明确定义。作为一个经常引起混淆的具体例子，$ab=cbmodN$ 并不一定意味着 $a=cmodN$。

示例 9.6

取 $N=24$。则 $3\cdot 2=6=15\cdot 2mod24$，但 $3^6=15mod24$。

然而，在某些情况下，我们可以定义一个有意义的除法概念。如果对于给定的整数 $b$，存在一个整数 $c$ 使得 $bc=1modN$，我们称 $b$ 在模 $N$ 下是可逆的，将 $c$ 称为 $b$ 在模 $N$ 下的（乘法）逆元。显然，$0$ 永远不可逆。也不难证明，如果 $c$ 是 $b$ 在模 $N$ 下的乘法逆元，则 $[cmodN]$ 也是 $b$ 在模 $N$ 下的乘法逆元。此外，如果 $c_0$ 是 $b$ 的另一个乘法逆元，则 $[cmodN]=[c_{0}modN]$。当 $b$ 在模 $N$ 下可逆时，我们可以简单地让 $b^{-1}$ 表示唯一的乘法逆元，该逆元位于集合 $\{1,...,N-1\}$。

当 $b$ 在模 $N$ 下可逆时，我们定义模 $N$ 下由 $b$ 除法为乘法 $b^{-1}$（即，我们定义 $[a/bmodN]\equiv [a{b}^{-1}modN]$）。我们强调，只有在 $b$ 可逆时才定义了除法。如果 $ab=cbmodN$ 并且 $b$ 是可逆的，那么我们可以将方程的每一边都除以 $b$（或者实际上是将每一边都乘以 $b^{-1}$），得到

$$(ab)\cdot b^{-1}=(cb)\cdot b^{-1}modN\Rightarrow a=cmodN.$$

我们看到，在这种情况下，除法的运算效果与预期一致。因此，模 $N$ 下的可逆整数在某种意义上更易于处理。

自然的问题是：在给定模 $N$ 的情况下，哪些整数在模 $N$ 下是可逆的？我们可以使用命题 9.2 来完全回答这个问题：

命题 9.7

设 $b$ 和 $N$ 为整数，其中 $b\ge 1$ 且 $N>1$。则 $b$ 在模 $N$ 下可逆的充要条件是 $gcd(b,N)=1$。

证明

假设 $b$ 在模 $N$ 下可逆，记 $c$ 为其逆。由于 $bc=1modN$，这意味着存在某个 $\gamma \in \mathbb{Z}$ 使得 $bc-1=\gamma N$。等价地，$bc-\gamma N=1$。由于根据命题 9.2，$gcd(b,N)$ 是能够以这种方式表示的最小正整数，并且不存在小于 $1$ 的正整数，这意味着 $gcd(b,N)=1$。

反之，如果 $gcd(b,N)=1$，则根据命题 9.2，存在整数 $X$、$Y$，使得 $Xb+YN=1$。将此方程的每一边对 $N$ 取模，得到 $Xb=1modN$，我们可以看出 $X$ 是 $b$ 的一个乘法逆元。（事实上，这提供了一个计算逆元的有效算法。）

示例 9.8

取 $b=11$ 和 $N=17$。然后有 $(-3)\cdot 11+2\cdot 17=1$，因此 $14=[-3mod17]$ 是 $11$ 的逆元。可以验证 $14\cdot 11=1mod17$。

加法、减法、乘法和逆元的计算（如果存在）模 $N$ 都可以在多项式时间内进行；请参见附录 B.2。指数运算（即计算 $[a^{b}modN]$，其中 $b>0$ 为整数）也可以在多项式时间内计算；请参见附录 B.2.3。

9.1.3 群

设 $\mathbb{G}$ 是一个集合。在 $\mathbb{G}$ 上的一个二元运算 ◦ 本质上是一个函数 ◦(·, ·)，它将 $\mathbb{G}$ 中的两个元素映射到 $\mathbb{G}$ 中的另一个元素。如果 $g,h\in \mathbb{G}$，则我们可以用简便的符号 $g◦h$ 代替繁琐的符号 ◦(g, h)。

我们现在引入群这个重要的概念。

定义 9.9 一个群是一个集合 $\mathbb{G}$，以及一个二元运算 ◦，满足以下条件：

1. 封闭性： 对于所有 $g,h\in \mathbb{G}$，有 $g◦h\in \mathbb{G}$。
2. 存在单位元： 存在一个单位元 $e\in \mathbb{G}$，使得对于所有 $g\in \mathbb{G}$，都有 $e◦g=g=g◦e$。
3. 存在逆元： 对于所有 $g\in \mathbb{G}$，存在一个元素 $h\in \mathbb{G}$，使得 $g◦h=e=h◦g$。这样的 $h$ 被称为 $g$ 的逆元。
4. 结合律： 对于所有 $g_1,g_2,g_3\in \mathbb{G}$，成立 $(g_1◦g_2)◦g_3=g_1◦(g_2◦g_3)$。

当集合 $\mathbb{G}$ 的元素有有限个时，我们称 $\mathbb{G}$ 是有限群，记 $|\mathbb{G}|$ 为群的阶（即 $\mathbb{G}$ 中元素的数量）。

当群 $\mathbb{G}$ 的操作满足交换性时，我们称其为阿贝尔群，满足条件为：

• 交换性： 对于所有 $g,h\in \mathbb{G}$，成立 $g◦h=h◦g$。

当二元运算清楚时，我们可以简单地称集合 $\mathbb{G}$ 为群。我们将始终处理有限的阿贝尔群。然而，当某个结果需要这些假设时，我们将会仔细指明。

结合律意味着在写长表达式时，我们不需要添加括号；也就是说，表示 $g_1◦g_2◦\dots ◦g_n$ 是无歧义的，因为我们对操作 ◦ 的求值顺序不影响结果。

可以证明群 $\mathbb{G}$ 中的单位元是唯一的，因此我们可以称其为群的单位元。同样，可以证明群 $\mathbb{G}$ 中的每个元素都有唯一的逆元。参见练习 9.1。

如果 $\mathbb{G}$ 是一个群，$\mathbb{H}\subseteq \mathbb{G}$ 是 $\mathbb{G}$ 的子集，且 $\mathbb{H}$ 在与 $\mathbb{G}$ 相同的运算下也构成一个群，我们称 $\mathbb{H}$ 是 $\mathbb{G}$ 的子群。要验证 $\mathbb{H}$ 是子群，我们需要根据定义 9.9 验证封闭性、存在单位元和逆元，以及结合律。（事实上，如果 $\mathbb{G}$ 是阿贝尔群，那么结合性和交换性都会自动继承自 $\mathbb{G}$。）每个群 $\mathbb{G}$ 总是有平凡子群 $\mathbb{G}$ 和 $\{1\}$。如果 $\mathbb{H}\ne \mathbb{G}$，我们称 $\mathbb{H}$ 是 $\mathbb{G}$ 的真子群。

一般情况下，我们不会使用 ◦ 符号来表示群的运算。相反，我们根据讨论的群的性质使用加法或乘法符号。这并不意味着群的运算对应于整数的加法或乘法；这只是一个方便的记号。使用加法记号时，群的运算应用于元素 $g$ 和 $h$ 时表示为 $g+h$；单位元记为 $0$；元素 $g$ 的逆元记为 $-g$；我们用 $h-g$ 代替 $h+(-g)$。使用乘法记号时，群的运算应用于 $g$ 和 $h$ 时表示为 $g\cdot h$ 或简写为 $gh$；单位元

记为 $1$；元素 $g$ 的逆元记为 $g^{-1}$；有时我们用 $h/g$ 代替 $h{g}^{-1}$。

在这一点上，看一些例子可能会有帮助。

示例 9.10

一个集合在一个运算下可能是一个群，但在另一个运算下可能不是。例如，整数集合 $\mathbb{Z}$ 在加法下是一个阿贝尔群：单位元是元素 $0$，并且每个整数 $g$ 都有逆元 $-g$。然而，在乘法下它不是一个群，因为例如整数 $2$ 在整数集合中没有乘法逆元。

示例 9.11

实数集合 $\mathbb{R}$ 在乘法下不是一个群，因为 $0$ 没有乘法逆元。然而，非零实数集合是一个阿贝尔群，其乘法运算下的单位元为 $1$。

以下示例引入了我们经常使用的群 ${\mathbb{Z}}_N$。

示例 9.12

设 $N>1$ 为一个整数。集合 $\{0,\dots ,N-1\}$ 关于模 $N$ 的加法（即 $a+b\stackrel{\mathrm{def}}{=}[a+bmodN]$）构成一个阿贝尔群，群的阶为 $N$。封闭性显然成立；结合性和交换性来自于整数的这些性质；单位元为 $0$；由于 $a+(N-a)=0modN$，任何元素 $a$ 的逆元为 $[(N-a)modN]$。我们用 ${\mathbb{Z}}_N$ 表示这个群。（有时我们也会用 ${\mathbb{Z}}_N$ 表示集合 $\{0,\dots ,N-1\}$，而不考虑任何特定的群运算。）

我们在本节中结束之前，给出一个简单的引理，正式化了群的“消去律”。

引理 9.13

设 $\mathbb{G}$ 是一个群，$a,b,c\in \mathbb{G}$。特别地，如果 $ac=c$，则 $a$ 是 $\mathbb{G}$ 中的单位元。如果 $ac=bc$，则 $a=b$。

证明 我们知道 $ac=bc$。将两边同时乘以元素 $c$ 的唯一逆元 $c^{-1}$，我们得到 $a=b$。详细地说：

$$ac=bc\Rightarrow (ac)c^{-1}=(bc)\cdot c^{-1}\Rightarrow a(c\cdot c^{-1})=b(c\cdot c^{-1})\Rightarrow a\cdot 1=b\cdot 1,\text{即}a=b.$$

将上述证明与（在引理 9.7 之前的讨论中）关于模 $N$ 除法的消去律进行比较。正如相似性所示，模 $N$ 中可逆元素在模 $N$ 的乘法下构成一个群。我们稍后会详细讨论这个示例。

注： 引理 9.13 说明了群中元素的唯一性和乘法消去律的特性。这些性质在群论中起着关键作用，使得我们能够从一些简单的条件中推导出更多复杂的结果。

抱歉我之前的翻译有误。以下是经过修正的翻译：

群指数运算

在群中，我们常常需要描述将群操作应用于固定元素 $g$ 的 $m$ 次操作，其中 $m$ 是一个正整数。使用加法符号，我们可以表示为 $m\cdot g$ 或 $mg$，即：

$$mg=m\cdot g\stackrel{\text{def}}{=}\underset{m\mathrm{times}}{\underbrace{g+\cdots +g}}.$$

需要注意的是，$m$ 是一个整数，而 $g$ 是群中的元素。因此，$mg$ 不表示对 $m$ 和 $g$ 进行群操作（实际上，我们是在一个群中，其群操作用加法表示）。然而，幸运的是，“符号的行为是正确的”；例如，如果 $g\in \mathbb{G}$，$m$ 和 $m^{\prime }$ 是整数，那么 $(mg)+(m^{\prime }g)=(m+m^{\prime })g$，$m(m^{\prime }g)=(m{m}^{\prime })g$，以及 $1\cdot g=g$。在阿贝尔群 $\mathbb{G}$ 中，对于 $g,h\in \mathbb{G}$，有 $(mg)+(mh)=m(g+h)$。

使用乘法符号时，我们将群操作应用于元素 $g$ 的 $m$ 次操作表示为 $g^m$，即：

$$g^m\stackrel{\text{def}}{=}\underset{m\mathrm{times}}{\underbrace{g\cdots g}}.$$

指数运算的熟知规则成立：$g^m\cdot g^{m^{\prime }}=g^{m+m^{\prime }}$，$(g^m{)}^{m^{\prime }}=g^{m{m}^{\prime }}$，以及 $g^1=g$。此外，在阿贝尔群中，对于 $g,h\in \mathbb{G}$，有 $g^m\cdot h^m=(gh{)}^m$。所有这些只是将前面段落中的结果从加法符号转化为乘法符号。

上述符号自然地扩展到当 $m$ 是零或负整数的情况。在使用加法符号时，我们定义 $0\cdot g\text{def}0$（需要注意，左边的 $0$ 是整数 $0$，而右边的 $0$ 是群的单位元），并定义 $(-m)\cdot g\text{def}m\cdot (-g)$，其中 $m$ 是正整数。注意，$-g$ 是 $g$ 的逆元，正如预期的那样，$(-m)\cdot g=-(mg)$。在使用乘法符号时，$g^0\text{def}1$，$g^{-m}\text{def}(g^{-1}{)}^m$。同样，$g^{-1}$ 是 $g$ 的逆元，我们有 $g^{-m}=(g^m{)}^{-1}$。

假设 $g\in \mathbb{G}$ 且 $b\ge 0$ 是一个整数。那么指数运算 $g^b$ 可以使用多项式次数的群操作在 $\mathbb{G}$ 中进行计算。因此，如果群运算可以在多项式时间内计算，则指数运算也可以。有关详细讨论，请参见附录 B.2.3。

我们现在已经掌握足够的知识来证明以下令人瞩目的结果：

定理 9.14

设 $\mathbb{G}$ 是一个有限群，$m=|\mathbb{G}|$ 是群的阶，对于任何 $\mathbb{G}$ 中的元素 $g$，有 $g^m=1$。

证明：我们只证明在 $\mathbb{G}$ 是交换群（阿贝尔群）的情况下（尽管该定理对任何有限群都成立）。固定任意 $g\in \mathbb{G}$，并令 $g_1,\dots ,g_m$ 为 $\mathbb{G}$ 的元素。我们声称：

$$g_1\cdot g_2\cdot \dots \cdot g_m=(g\cdot g_1)\cdot (g\cdot g_2)\cdot \dots \cdot (g\cdot g_m).$$

为了理解这一点，注意到 $g\cdot g_i=g\cdot g_j$ 意味着由引理 9.13，$g_i=g_j$。因此，右侧括号内的每个元素都是不同的。因为 $\mathbb{G}$ 中恰好有 $m$ 个元素，右侧要相乘的这 $m$ 个元素实际上只是 $\mathbb{G}$ 中的所有元素以某种排列顺序。由于 $\mathbb{G}$ 是交换群，元素相乘的顺序不影响结果，因此右侧等于左侧。

再次利用 $\mathbb{G}$ 是交换群这一事实，我们可以将所有的 $g$ 提取出来，得到：

$$g_1\cdot g_2\cdot \dots \cdot g_m=(g\cdot g_1)\cdot (g\cdot g_2)\cdot \dots \cdot (g\cdot g_m)=g^m\cdot (g_1\cdot g_2\cdot \dots \cdot g_m).$$

再次应用引理 9.13，我们得到 $g^m=1$。

上述结果的一个重要推论是，我们可以在指数中“对群的阶取模”：

推论 9.15

设 $\mathbb{G}$ 是一个有限群，$m=|\mathbb{G}|>1$ 是群的阶。对于任何 $\mathbb{G}$ 中的元素 $g$ 和任意整数 $x$，我们有 $g^x=g^{[x\mathrm{mod}m]}$。

证明：假设 $x=qm+r$，其中 $q,r$ 是整数，且 $r=[x\mathrm{mod}m]$。然后：

$$g^x=g^{qm+r}=g^{qm}\cdot g^r=(g^m{)}^q\cdot g^r=1^q\cdot g^r=g^r$$

（使用定理 9.14），即所证明的结论。

推论 9.15

以加法表示，上述推论表明如果 $g$ 是一个阶为 $m$ 的群中的元素，则 $x\cdot g=[x\mathrm{mod}m]\cdot g$。作为示例，考虑阶为 $m=15$ 的群 ${\mathbb{Z}}_{15}$，取 $g=11$。推论表明：

$$15\cdot 11=[15\mathrm{mod}15]\cdot 11=0\cdot 11=0+11=11=7\mathrm{mod}15.$$

上述结果与事实一致（参见示例 9.5），即我们可以“先进行取模再相乘”，而不必“先相乘再取模”。

另一个在密码学应用中非常有用的推论如下：

推论 9.17

设 $\mathbb{G}$ 是一个有限群，$m=|\mathbb{G}|>1$ 是群的阶。令 $e>0$ 是一个整数，定义函数 $f_e:\mathbb{G}\to \mathbb{G}$，其中 $f_e(g)=g^e$。如果 $\text{gcd}(e,m)=1$，那么 $f_e$ 是一个置换（双射）。此外，如果 $d=e^{-1}\mathrm{mod}m$，那么 $f_d$ 是 $f_e$ 的逆函数。（注意，由命题 9.7，$\text{gcd}(e,m)=1$ 意味着 $e$ 在模 $m$ 下可逆。）

证明：因为 $\mathbb{G}$ 是有限群，论述的第二部分暗示了第一部分；因此，我们只需证明 $f_d$ 是 $f_e$ 的逆函数。这是因为对于任何 $\mathbb{G}$ 中的元素 $g$，有：

$$f_d(f_e(g))=f_d(g^e)=(g^e{)}^d=g^{ed}=g^{[ed\mathrm{mod}m]}=g^1=g,$$

其中第四个等式来自推论 9.15。

9.1.4 乘法群：欧拉函数

正如在示例 9.12 中所讨论的，集合 ${\mathbb{Z}}_N=\{0,\dots ,N-1\}$ 是一个关于模 $N$ 的加法群。我们能否定义一个关于模 $N$ 的乘法群呢？在这样做的过程中，我们将不得不排除那些不可逆的 ${\mathbb{Z}}_N$ 中的元素，例如，我们将不得不排除 0，因为它没有乘法逆元。非零元素也可能不可逆（参见命题 9.7）。在集合 $\{1,\dots ,N-1\}$ 中，哪些元素 $b$ 在模 $N$ 下可逆？命题 9.7 表明这些恰好是满足 $\text{gcd}(b,N)=1$ 的元素 $b$。我们也在第 9.1.2 节中看到，每当 $b$ 可逆时，它的逆元落在集合 $\{1,\dots ,N-1\}$ 中。这引导我们定义，对于任何 $N>1$，集合

$${\mathbb{Z}}_N^{\ast }\stackrel{\text{def}}{=}\{b\in \{1,\dots ,N-1\}\mid gcd(b,N)=1\};$$

即，${\mathbb{Z}}_N^{\ast }$ 由集合 $\{1,\dots ,N-1\}$ 中与 $N$ 互质的整数组成。群的运算是模 $N$ 下的乘法，即$ab\stackrel{\mathrm{def}}{=}[abmodN]$。我们声称 ${\mathbb{Z}}_N^{\ast }$ 是关于此运算的一个阿贝尔群。

由于 $1$ 总是在 ${\mathbb{Z}}_N^{\ast }$ 中，因此集合显然包含一个单位元素。上述讨论表明 ${\mathbb{Z}}_N^{\ast }$ 中的每个元素在相同的集合中都有一个乘法逆元。交换律和结合律来自于整数上这些性质的事实。为了证明封闭性成立，设 $a,b\in {\mathbb{Z}}_N^{\ast }$；则 $[ab\mathrm{mod}N]$ 的逆元为 $[b^{-1}{a}^{-1}\mathrm{mod}N]$，这意味着 $\text{gcd}([ab\mathrm{mod}N],N)=1$，因此 $ab\in {\mathbb{Z}}_N^{\ast }$。总结：

命题 9.18 设 $N>1$ 是一个整数。那么 ${\mathbb{Z}}_N^{\ast }$ 是关于模 $N$ 的乘法运算的一个阿贝尔群。

定义 $\varphi (N)\stackrel{\mathrm{def}}{=}|{\mathbb{Z}}_N^{\ast }|$，即群 ${\mathbb{Z}}_N^{\ast }$ 的阶数。$\varphi (N)$ 被称为欧拉函数。$\varphi (N)$ 的值是多少呢？首先考虑当 $N=p$ 是素数的情况。那么集合 $\{1,\dots ,p-1\}$ 中的所有元素都与 $p$ 互质，因此 $\varphi (p)=|{\mathbb{Z}}_p^{\ast }|=p-1$。接下来考虑 $N=pq$ 的情况，其中 $p,q$ 是不同的素数。如果整数 $a\in \{1,\dots ,N-1\}$ 与 $N$ 不互质，那么 $p|a$ 或者 $q|a$（$a$ 不能同时被 $p$ 和 $q$ 整除，因为这将意味着 $pq|a$ 但是 $a<N=pq$）。集合 $\{1,\dots ,N-1\}$ 中能够被 $p$ 整除的元素正是 $(q-1)$ 个元素 $p,2p,3p,\dots ,(q-1)p$，能够被 $q$ 整除的元素正是 $(p-1)$ 个元素 $q,2q,\dots ,(p-1)q$。剩余的元素的数量为

$$(N-1)-(q-1)-(p-1)=pq-p-q+1=(p-1)(q-1).$$

因此，我们证明了当 $

N$ 是两个不同的素数 $p$ 和 $q$ 的乘积时，$\varphi (N)=(p-1)(q-1)$。

你被要求在习题 9.4 中证明以下一般结果（本书的其余部分很少使用）：

定理 9.19 设 $N=\prod _i{p}_i^{e_i}$，其中 $\{p_i\}$ 是不同的素数，$e_i\ge 1$。那么 $\varphi (N)=\prod _i{p}_i^{e_i-1}(p_i-1)$。

示例 9.20 取 $N=15=5\cdot 3$。那么 ${\mathbb{Z}}_{15}^{\ast }=\{1,2,4,7,8,11,13,14\}$ 且 $|{\mathbb{Z}}_{15}^{\ast }|=8=4\cdot 2=\varphi (15)$。在 ${\mathbb{Z}}_{15}^{\ast }$ 中，8 的逆元是 2，因为 $8\cdot 2=16=1\mathrm{mod}15$。

我们已经证明了 ${\mathbb{Z}}_N^{\ast }$ 是阶数为 $\varphi (N)$ 的群。下面是定理 9.14 和推论 9.17 的简单推论：

推论 9.21 取任意的整数 $N>1$ 和 $a\in {\mathbb{Z}}_N^{\ast }$。那么 $a^{\varphi (N)}=1\mathrm{mod}N$。

对于特定情况 $N=p$ 是素数，以及 $a\in \{1,\dots ,p-1\}$，我们有 $a^{p-1}=1\mathrm{mod}p$。

推论 9.22 固定 $N>1$。对于整数 $e>0$，定义 $f_e:{\mathbb{Z}}_N^{\ast }\to {\mathbb{Z}}_N^{\ast }$ 为 $f_e(x)=[x^e\mathrm{mod}N]$。如果 $e$ 与 $\varphi (N)$ 互质，则 $f_e$ 是一个双射。此外，如果 $d=e^{-1}\mathrm{mod}\varphi (N)$，则 $f_d$ 是 $f_e$ 的逆映射。

9.1.5 *同构与中国剩余定理

两个群同构表示它们具有相同的结构。从数学角度来看，群 $\mathbb{G}$ 到 $\mathbb{H}$ 的同构提供了关于 $\mathbb{G}$ 的一种替代但等价的思考方式。从计算的角度来看，同构提供了一种不同的表示方法，通常会对算法效率产生重要影响。

定义 9.23 设 $\mathbb{G}$ 和 $\mathbb{H}$ 是分别关于操作 ${\ast }_{\mathbb{G}}$ 和 ${\ast }_{\mathbb{H}}$ 的群。如果满足以下条件，则函数 $f:\mathbb{G}\to \mathbb{H}$ 是从 $\mathbb{G}$ 到 $\mathbb{H}$ 的同构：

1. $f$ 是双射（一一对应）；
2. 对于所有的 $g_1,g_2\in \mathbb{G}$，有 $f(g_1{\ast }_{\mathbb{G}}{g}_2)=f(g_1){\ast }_{\mathbb{H}}f(g_2)$。

如果存在从 $\mathbb{G}$ 到 $\mathbb{H}$ 的同构，则称这两个群是同构的，记作 $\mathbb{G}\cong \mathbb{H}$。

本质上，从 $\mathbb{G}$ 到 $\mathbb{H}$ 的同构就是将 $\mathbb{G}$ 的元素重新命名为 $\mathbb{H}$ 的元素。注意，如果 $\mathbb{G}$ 是有限的且 $\mathbb{G}\cong \mathbb{H}$，那么 $\mathbb{H}$ 必须也是有限的，并且大小与 $\mathbb{G}$ 相同。此外，如果存在从 $\mathbb{G}$ 到 $\mathbb{H}$ 的同构 $f$，那么 $f^{-1}$ 是从 $\mathbb{H}$ 到 $\mathbb{G}$ 的同构。然而，可能存在这样的情况，即 $f$ 可以高效计算，但 $f^{-1}$ 不行（或反之）。

本节的目标是利用同构的语言来更好地理解当 $N=pq$ 为两个不同素数的乘积时，群 ${\mathbb{Z}}_N$ 和 ${\mathbb{Z}}_N^{\ast }$ 的群结构。首先，我们需要引入群的直积的概念。给定群 $\mathbb{G}$ 和 $\mathbb{H}$，其分别关于群操作 ${\ast }_{\mathbb{G}}$ 和 ${\ast }_{\mathbb{H}}$，我们定义新的群 $\mathbb{G}\times \mathbb{H}$（$\mathbb{G}$ 和 $\mathbb{H}$ 的直积）如下。$\mathbb{G}\times \mathbb{H}$ 的元素是有序对 $(g,h)$，其中 $g\in \mathbb{G}$ 且 $h\in \mathbb{H}$；因此，如果 $\mathbb{G}$ 有 n 个元素，$\mathbb{H}$ 有 $n_0$ 个元素，则 $\mathbb{G}\times \mathbb{H}$ 有 $n\cdot n_0$ 个元素。$\mathbb{G}\times \mathbb{H}$ 上的群操作 ${\ast }_{\mathbb{G}\times \mathbb{H}}$ 是逐分量应用的，即：

$$(g,h){\ast }_{\mathbb{G}\times \mathbb{H}}(g^{{}^{\prime }},h^{{}^{\prime }})=(g{\ast }_{\mathbb{G}}{g}^{{}^{\prime }},h{\ast }_{\mathbb{H}}{h}^{{}^{\prime }}).$$

留给练习 9.8 验证 $\mathbb{G}\times \mathbb{H}$ 确实是一个群。上述表示法可以自然地推广到多于两个群的直积，尽管我们不会在接下来的内容中用到这一点。

现在，我们可以陈述并证明中国剩余定理。

定理 9.24（中国剩余定理） 设 $N=pq$，其中 $p,q>1$ 互质。那么：

1. ${\mathbb{Z}}_N\cong {\mathbb{Z}}_p\times {\mathbb{Z}}_q$，以及
2. ${\mathbb{Z}}_N^{\ast }\cong {\mathbb{Z}}_p^{\ast }\times {\mathbb{Z}}_q^{\ast }$。

此外，定义函数 $f$，将集合 $\{0,\dots ,N-1\}$ 中的元素 $x$ 映射为对 $(x_p,x_q)$，其中 $x_p\in \{0,\dots ,p-1\}$ 且 $x_q\in \{0,\dots ,q-1\}$，定义如下：

$$f(x)\stackrel{\text{def}}{=}([xmodp],[xmodq]).$$

那么：

1. $f$ 是从 ${\mathbb{Z}}_N$ 到 ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的同构；
2. $f$ 在 ${\mathbb{Z}}_N^{\ast }$ 上的限制是从 ${\mathbb{Z}}_N^{\ast }$ 到 ${\mathbb{Z}}_p^{\ast }\times {\mathbb{Z}}_q^{\ast }$ 的同构。

证明 对于任意 $x\in {\mathbb{Z}}_N$，函数 $f(x)$ 给出了一个由元素 $(x_p,x_q)$ 构成的对，其中 $x_p\in {\mathbb{Z}}_p$ 且 $x_q\in {\mathbb{Z}}_q$。我们要证明的是，如果 $x\in {\mathbb{Z}}_N^{\ast }$，那么 $(x_p,x_q)\in {\mathbb{Z}}_p^{\ast }\times {\mathbb{Z}}_q^{\ast }$。实际上，如果 $x_p\notin {\mathbb{Z}}_p^{\ast }$，这意味着 $[x\mathrm{mod}p],p$ 不互质。但是，这将导致 $x,p$ 不互质。这又暗示 $x,N$ 不互质，与 $x\in {\mathbb{Z}}_N^{\ast }$ 的假设相矛盾（类似的论证适用于 $x_q\notin {\mathbb{Z}}_q^{\ast }$ 的情况）。

接下来，我们将证明 $f$ 是从 ${\mathbb{Z}}_N$ 到 ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的同构。要证明它是从 ${\mathbb{Z}}_N^{\ast }$ 到 ${\mathbb{Z}}_p^{\ast }\times {\mathbb{Z}}_q^{\ast }$ 的同构的证明类似。我们首先证明 $f$ 是单射。假设 $f(x)=(x_p,x_q)=f(x_0)$，则 $x=x_p=x_0\mathrm{mod}p$ 且 $x=x_q=x_0\mathrm{mod}q$。这进一步意味着 $(x-x_0)$ 可以同时被 $p$ 和 $q$ 整除。由于 $p$ 和 $q$ 互质，命题 9.4 表明 $pq=N$ 可以整除 $(x-x_0)$。但是，这意味着 $x=x_0\mathrm{mod}N$。对于 $x,x_0\in {\mathbb{Z}}_N$，这意味着 $x=x_0$，因此 $f$ 是单射。由于 $|{\mathbb{Z}}_N|=N=p\cdot q=|{\mathbb{Z}}_p|\cdot |{\mathbb{Z}}_q|$，两个集合的大小相同，结合 $f$ 是单射可知 $f$ 是双射。

在以下段落中，用 $+N$ 表示模 $N$ 的加法，用 ${+}_{\ast }$ 表示 ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 中的群操作（即在第一个分量中进行模 $p$ 的加法，在第二个分量中进行模 $q$ 的加法）。为了完成从 ${\mathbb{Z}}_N$ 到 ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的同构的证明，我们需要证明对于所有 $a,b\in {\mathbb{Z}}_N$，有 $f(a+Nb)=f(a){+}_{\ast }f(b)$。

注意到

$$f(a+Nb)=[(a+Nb)\mathrm{mod}p],[(a+Nb)\mathrm{mod}q]$$$$=[(a+b)\mathrm{mod}p],[(a+b)\mathrm{mod}q]$$$$=\left[a\mathrm{mod}p\right],\left[a\mathrm{mod}q\right]{+}_{\ast }\left[b\mathrm{mod}p\right],\left[b\mathrm{mod}q\right]$$$$=f(a){+}_{\ast }f(b).$$

至此，我们已经完成了从 ${\mathbb{Z}}_N$ 到 ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$ 的同构的证明。关于 ${\mathbb{Z}}_N^{\ast }$ 到 ${\mathbb{Z}}_p^{\ast }\times {\mathbb{Z}}_q^{\ast }$ 的同构的证明类似。

通过一种记号，假设 $N$ 已知且 $x\in \{0,1,\dots ,N-1\}$，我们将 $x\leftrightarrow (x_p,x_q)$ 表示为 $x_p=[x\mathrm{mod}p]$ 且 $x_q=[x\mathrm{mod}q]$。也就是说，当且仅当 $f(x)=(x_p,x_q)$ 时，$x\leftrightarrow (x_p,x_q)$，其中 $f$ 如定理中所示。当涉及 $x\in {\mathbb{Z}}_N^{\ast }$ 时，也使用相同的记号。

例子 9.25 考虑 $15=5\cdot 3$，以及 ${\mathbb{Z}}_{15}^{\ast }=\{1,2,4,7,8,11,13,14\}$。中国剩余定理说明该群同构于 ${\mathbb{Z}}_5^{\ast }\times {\mathbb{Z}}_5^{\ast }$。我们可以计算：

$$1\leftrightarrow (1,1)2\leftrightarrow (2,2)4\leftrightarrow (4,1)7\leftrightarrow (2,1)$$$$8\leftrightarrow (3,2)11\leftrightarrow (1,2)13\leftrightarrow (3,1)14\leftrightarrow (4,2),$$

其中每个对 $(a,b)$，其中 $a\in {\mathbb{Z}}_5^{\ast }$ 且 $b\in {\mathbb{Z}}_3^{\ast }$，都恰好出现一次。

利用中国剩余定理

如果两个群同构，则它们都表示相同的底层“代数结构”。然而，选择使用哪种表示法可能会影响群操作的计算效率。我们先从抽象的角度讨论，然后再具体讨论 ${\mathbb{Z}}_N$ 和 ${\mathbb{Z}}_N^{\ast }$ 的情况。

设 $\mathbb{G},\mathbb{H}$ 分别是具有操作 ${\circ }_{\mathbb{G}},{\circ }_{\mathbb{H}}$ 的群，假设 $f$ 是从 $\mathbb{G}$ 到 $\mathbb{H}$ 的同构，其中 $f$ 和 $f^{-1}$ 都可以高效地计算。那么对于 $g_1,g_2\in \mathbb{G}$，我们可以通过以下两种方式计算 $g=g_1{\circ }_{\mathbb{G}}{g}_2$：直接计算 $\mathbb{G}$ 中的群操作，或通过以下步骤计算：

1. 计算 $h_1=f(g_1)$ 和 $h_2=f(g_2)$；
2. 使用 $\mathbb{H}$ 中的群操作计算 $h=h_1{\circ }_{\mathbb{H}}{h}_2$；
3. 计算 $g=f^{-1}(h)$。

当我们想在 $\mathbb{G}$ 中计算多个群操作时（例如计算 $g^x$），哪种方法更好取决于在每个群中计算群操作的相对效率，以及计算 $f$ 和 $f^{-1}$ 的效率。

现在我们转向具体的情况，即在模 $N$ 下的计算，其中 $N=pq$ 是不同的素数的乘积。中国剩余定理表明模 $N$ 的加法、乘法或指数运算（即重复乘法）可以“转化”为模 $p$ 和 $q$ 下的类似运算。借鉴例子 9.25，我们以 $N=15$ 的一些简单例子来展示。

好的，我会为您添加公式和符号，以及使用美元符号 $$ \ldots $$ 将它们包裹起来。请查看下面的修订版本：

Example 9.26 假设我们想要计算$14\cdot 13(\mathrm{mod}15)$即在 ${\mathbb{Z}}_{15}^{\ast }$ 中）。例子 9.25 表明 $14\leftrightarrow (4,2)$ 和 $13\leftrightarrow (3,1)$。在 ${\mathbb{Z}}_5^{\ast }\times {\mathbb{Z}}_3^{\ast }$ 中，我们有

$$(4,2)\cdot (3,1)=([4\cdot 3(\mathrm{mod}5)],[2\cdot 1(\mathrm{mod}3)])=(2,2)$$

注意到 $(2,2)\leftrightarrow 2$，这是正确的答案，因为 $14\cdot 13=2(\mathrm{mod}15)$。

Example 9.27 假设我们想要计算 $1153(\mathrm{mod}15)$。例子 9.25 表明 $11\leftrightarrow (1,2)$。注意到 $2=-1(\mathrm{mod}3)$，因此

$$(1,2{)}^{53}=([153(\mathrm{mod}5)],[(-1{)}^{53}(\mathrm{mod}3)])=(1,[-1(\mathrm{mod}3)])=(1,2)$$

因此，$1153(\mathrm{mod}15)=11$。

Example 9.28 假设我们想要计算 $[29100(\mathrm{mod}35)]$。我们首先计算对应关系 $29\leftrightarrow ([29(\mathrm{mod}5)],[29(\mathrm{mod}7)])=([-1(\mathrm{mod}5)],1)$。使用中国剩余定理，我们有

$${([-1(\mathrm{mod}5)],1)}^{100}=([-1^{100}(\mathrm{mod}5)],[1^{100}(\mathrm{mod}7)])=(1,1)$$

并且我们可以立即看出 $(1,1)\leftrightarrow 1$。因此，$[29100(\mathrm{mod}35)]=1$。

Example 9.29 假设我们想要计算 $[1825(\mathrm{mod}35)]$。我们有 $18\leftrightarrow (3,4)$，所以

$$1825(\mathrm{mod}35)\leftrightarrow (3,4{)}^{25}=([3^{25}(\mathrm{mod}5)],[4^{25}(\mathrm{mod}7)]).$$

由于 ${\mathbb{Z}}_5^{\ast }$ 是阶为 4 的群，我们可以在指数上“工作模 4”（参见推论 9.15）并且得到

$$3^{25}=3^{[25(\mathrm{mod}4)]}=3^1=3(\mathrm{mod}5).$$

类似地，$4^{25}=4^{[25(\mathrm{mod}6)]}=4^1=4(\mathrm{mod}7)$。 因此，$([3^{25}(\mathrm{mod}5)],[4^{25}(\mathrm{mod}7)])=(3,4)\leftrightarrow 18$，所以 $[1825(\mathrm{mod}35)]=18$。

我们还没有讨论如何在模 $N$ 和模 $p$、$q$ 之间进行转换。在已知 $N$ 的因数分解的情况下，可以高效地进行转换。假设已知 $p$ 和 $q$，那么可以很容易地将模 $N$ 下的元素转换为其在模 $p$ 和 $q$ 下的表示：

元素 $x$ 对应于 $([x(\mathrm{mod}p)],[x(\mathrm{mod}q)])$，两个模数规约都可以高效地进行（参见附录 B.2）。 对于另一个方向，我们使用以下观察：具有表示 $(xp,xq)$ 的元素可以写成

$$(xp,xq)=xp\cdot (1,0)+xq\cdot (0,1).$$

因此，如果我们可以找到 $1p,1q\in \{0,\dots ,N-1\}$ 使得 $1p\leftrightarrow (1,0)$ 和 $1q\leftrightarrow (0,1)$，那么（利用中国剩余定理）我们知道 $(xp,xq)\leftrightarrow [((xp\cdot 1p+xq\cdot 1q)(\mathrm{mod}N))]$。 由于 $p$ 和 $q$ 是不同的素数，$gcd(p,q)=1$。我们可以使用扩展欧几里得算法（参见附录 B.1.2）找到整数 $X,Y$，使得

$$Xp+Yq=1.$$

注意到 $Yq=0(\mathrm{mod}q)$ 并且 $Yq=1-Xp=1(\mathrm{mod}p)$。这意味着 $[Yq(\mathrm{mod}N)]\leftrightarrow (1,0)$；即，$[Yq(\mathrm{mod}N)]=1p$。类似地，$[Xp(\mathrm{mod}N)]=1q$。 总之，我们可以按照以下方式将表示为 $(xp,xq)$ 的元素转换为其在模 $N$ 下的表示（假设已知 $p$ 和 $q$）：

1. 计算 $X,Y$，使得 $Xp+Yq=1$。
2. 设定 $1p:=[Yq(\mathrm{mod}N)]$ 和 $1q:=[Xp(\mathrm{mod}N)]$。
3. 计算 $x:=[((xp\cdot 1p+xq\cdot 1q)(\mathrm{mod}N))]$。 如果需要执行多次这样的转换，则可以

在预处理阶段一次性计算 $1p,1q$。

Example 9.30 取 $p=5$，$q=7$，$N=5\cdot 7=35$。假设我们已知表示 $(4,3)$ 并且想要将其转换为 ${\mathbb{Z}}_{35}$ 中的对应元素。使用扩展欧几里得算法，我们计算

$$3\cdot 5-2\cdot 7=1.$$

因此，$1p=[-2\cdot 7(\mathrm{mod}35)]=21$ 并且 $1q=[3\cdot 5(\mathrm{mod}35)]=15$。 （我们可以验证这些值是否正确：例如，对于 $1p=21$，我们可以验证 $[21(\mathrm{mod}5)]=1$ 和 $[21(\mathrm{mod}7)]=0$）。使用这些值，我们可以然后计算 $(4,3)=4\cdot (1,0)+3\cdot (0,1)\leftrightarrow [4\cdot 1p+3\cdot 1q(\mathrm{mod}35)]=[4\cdot 21+3\cdot 15(\mathrm{mod}35)]=24$。 由于 $24=4(\mathrm{mod}5)$ 且 $24=3(\mathrm{mod}7)$，这确实是正确的结果。