注：本节可参考国内《信息安全数学基础》《初等数论》《抽象代数》等相关内容（即如果学习过以上课程，下面内容可以跳过）。

模运算(Modular Arithmetic)

在计算机的一些领域（如密码学），我们通常希望处理一串范围较小的数字。这时，模运算就起到了巨大的作用，它能将数压缩到一个较小的范围，从而简化大量运算。
在生活中，最常见的模运算例子就是时钟。时钟以12小时为一循环（如果以24小时制计算则为24小时一循环），因而我们能够轻松计算当前时刻若干小时后的时刻。
用数学语言描述的话，我们可以定义，其中为除以得到的余数。即：

计算法则（加法，减法与乘法）

在计算时，我们可以先计算和，再将二者相加取模（这很容易证明）。同理，也等于。
在乘法运算上，这一法则的效果更明显：，借助这一公式，计算的规模可以大大减小。

集合表示（Set representation）

下面我们换个视角分析模运算。对于任意整数与，如果整除，则称与对同余(congruent modulo m)，即：

显然，在这个式子中，与除以得到的余数相同，故上述式子也可记为：

于是我们可以将所有对同余的数组成一个集合（如，等），一共可以组成个集合。这些集合可以覆盖所有整数，也被称为模的剩余类(residue classes mod m)。
通过建立这些集合，我们就可以理解上述模运算法则的原理。由于每个集合里的所有元素均相互同余，所以我们可以将运算的数转化到这个范围内。
下面再用数学语言将这一命题进行阐述（可以直接用定义证明，故证明过程省略）：
如果且，那么，同时。
注意到我们这里没有涉及到除法运算，这将在后面被讨论。

指数运算

在密码学中，指数运算也是一种重要的运算。那么，对于（均为自然数），如何求它对的模呢？一种朴素的方法是依次计算一直到，但这样效率太低（如果用程序实现时间复杂度可达）。
为了优化这一运算，我们可以使用下述“重复平方(repeated squaring)”技巧：
- 设计递归函数mod_exp(x,y,m)，返回值为；
- 如果，则返回1（）;
- 如果，设z=mod_exp(x,y//2,m)（）;
  - 如果为偶数，则返回；
  - 如果为奇数，则返回。
这样算法的时间复杂度就降到了（具体关于算法时间复杂度的知识可参见CS61B）。

双射(Bijecions)

在介绍除法运算前，先做一个铺垫。这里我们回顾一下高等数学中映射的概念：
- 映射(mapping)：设,是两个给定的集合，若按照某种规则，使得中的每一个元素，都可以在中找到唯一的元素与之对应，则称是集合到集合的一个映射。
- 单射(one-to-one)：设是集合到集合的一个映射，若的逆像也具有唯一性，即对中的任意两个不同元素,也满足（也可表述为），则为单射。
- 满射(onto)：如果，满足，则称为满射。
- 双射：如果既是单射又是满射，那么就是双射。
利用这些概念，我们考虑以下函数（均将集合映射到自身）：

可以发现，映射是双射（集合中的每一个，都存在唯一原像）；而映射只有当是奇数时才是双射（映射到），当为偶数时既不是单射也不是满射。
另外关于双射，有以下定理：
- 对于一个有限集合，如果映射存在对应的逆映射满足，则为双射。

逆(Inverses)

之前我们进行减法模运算时，注意到，所以加法模运算很容易拓展到减法模运算。
然而想通过乘法模运算推导出除法模运算就困难一些。在实数域上，我们知道除以等价于乘以。相应的，计算，就需要找到，使得，那么就可以将问题转化为。这里也被称为模的乘法逆(multiplicative inverse)。
那么，能否保证一定存在？又是否唯一呢？我们先举一些例子：令，则当时，，即是模的乘法逆；而当时，取，循环，无法取到，即模的乘法逆不存在。
关于模的乘法逆的存在性与唯一性，有下述定理：
- 当和满足（即与互质），则模的乘法逆存在且唯一。
证明如下：
- 考虑以下数列：。可以证明这一数列没有重复值（使用反证法：如果存在，使得，则，而与互质，故只能，但，产生矛盾）。因此数列包含中的每一个值，故一定存在，使得为模的乘法逆。
- 下面证明唯一性：如果存在满足，那么。又因为，所以。
- 当然，这一定理的逆命题同样成立（当模的乘法逆存在与互质）简单证明如下：设为模的乘法逆，则，即存在，使得。而如果，则，产生矛盾。
我们一般将模的乘法逆记为，就像一般的算术一样。下面我们将介绍如何利用最大公约数计算。

乘法逆的计算

事实上，对于最大公约数，我们可以得到以下结论（也被称为裴蜀定理）：
- 如果，那么一定存在整数，使得
基于这一结论，我们可以得出：。从而，那么对取模即为我们所求的乘法逆。

欧几里得算法（辗转相除法）

首先，我们定义。对于非零的两数，存在以下定理：
- 设，则。
- 证明很容易（直接使用模运算定义即可），故省略。
通过这一定理，可以对和反复互相取模，直到其中一项变为，则另一项即为和的最大公因数。
我们可以将这一算法用python代码实现：

def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)

这里我们再分析一下这个程序运行的时间复杂度（递归调用的次数）。可以证明，gcd(x,y)在经过两次递归后最大项不会超过：
- 若，则在一次递归后，最大项已经不超过，故第二次递归也一定不超过；
- 若，则在两次递归后，最大项会变为。
所以最多经过次递归后，变为。故时间复杂度为。
下面我们就使用欧几里得算法求解乘法逆。

欧几里得算法的扩展

我们将上面求解最大公约数的代码进行扩展：

def extended_gcd(x,y):
  if y==0:
    return x,1,0
  else:
    d,a,b=extended_gcd(y,x%y)
    return d,b,a-(x//y)*b

这个函数输入后返回三个值，满足。可以验证，当时，即为模的乘法逆。
那么这个算法是如何设计出来的呢？我们可以尝试逆向递推：
- 当时，返回值，显然满足；
- 当时，首先通过递归调用extended_gcd(y,x%y)得到，且，然后再返回。
- 很明显即为最大公约数（和先前的方法相同），而对于和，有以下推导：

这便是$a'$和$b'$表达式的由来。

与先前的算法相比，仅仅是增加了常数倍的计算量，时间复杂度仍为。
当然，除了递归，我们还可以直接采用递推法求解。注意到且，所以一定整除由和组成的线性组合。那么基于下面两个等式：

对两个式子的右边做辗转相除（类似的操作）,左边也作出相应的运算，最后一定能得到。

除法模运算

在得到乘法逆后，我们就可以做除法模运算了。一种典型的使用场景如下：
- 已知，求。
- 为解这一方程，注意到模的乘法逆为，故。而且这是取模后的唯一解。

算术基本定理（Fundamental Theorem of Arithmetic）

在初等数论中，有一个非常重要的定理：任何一个大于的整数可分解为若干个质数的乘积。事实上，我们可以用拓展后的欧几里得算法进行证明。
首先证明一个引理：
- 设且，那么如果，则。
- 简单证明：因为，所以存在整数，满足。两边乘以得，因为，（因为），所以。
有了这个引理，既可以对算术基本定理进行证明：
- 在归纳法例4中，我们已经证明了任意大于的整数都可以表示为一个或多个质数的乘积。那么，就只需要证明这一序列在对质因子进行排序后唯一即可。（用数学语言描述即为：如果，均为质数，那么，且与仅顺序不同）
- 下面给出具体证明：
- 对于，因为，所以，又因为均为质数，所以一定等于的其中之一（设为）。于是将等式两边各除去和对应的。
- 以此类推，可以得到对应的项。最终左式除到，此时右式还剩下项。又因为质数均大于，所以只有当，即时等式成立。再由先前已经建立的与一一对应，命题得证。
这一证明体现了欧几里得算法的核心思想：除法与余数的唯一性（对于任意与，存在唯一的与，使得）

中国剩余定理（Chinese Remainder Theorem）

最后我们介绍另一个与模运算有关的定理。我们首先给出这个定理的简化形式：

对于任意满足，存在唯一的，满足：

证明如下：
- 先证明存在性：因为，由先前乘法逆的存在性定理，分别存在关于的乘法逆（记为）与关于的乘法逆（记为）。令

注意到$u\equiv 1\hspace{0.3em}(\operatorname*{mod}n)$且$u\equiv 0\hspace{0.3em}(\operatorname*{mod}m)$（类似有$v\equiv 1\hspace{0.3em}(\operatorname*{mod}m)$且$v\equiv 0\hspace{0.3em}(\operatorname*{mod}n)$），因此令$x=ua+vb$，则有$x\equiv 1\cdot a+0\cdot b\equiv a\hspace{0.3em}(\operatorname*{mod}n)$（类似有$x\equiv b\hspace{0.3em}(\operatorname*{mod}m)$），故$x$满足命题要求。

再证明唯一性：设与均满足命题要求，则有且，又因为互质，故，即存在，使得。而，所以只能等于，即。
将这一定理进行推广，就得到了下述中国剩余定理：
- 设为正整数且两两互质，那么对于任意数列，存在唯一的满足以下方程组：

且

其中$\left(\dfrac{N}{n_i}\right)_{n_i}^{-1}$表示$\dfrac{N}{n_i}$模$n_i$的乘法逆。

这里的取值只可能为（当）与（当）因此，如果将看成一个维向量（第个元素为），那么就可以看成第个元素为，其余元素均为的基向量，而为的线性组合（所以乘以任意倍数均满足方程）
证明的唯一性与上面的二元情况类似，就不再赘述了。
最后，我们注意到如果用表示（），用表示，那么就可以用表示（即可以唯一确定）。对于乘法也是类似，可以唯一表示。因此与形成了一个同构（环同构）。

CS70 Chapter 6