2020.1.15 修订文章几处错误, 感谢@Terminator, @Kuuki, @糖糖, @杨春的指正.
一枚数学系的大学生，喜欢数学文化的小视频，翻译中如有问题，请多指正~
密码学中的同余运算 II
在上一篇文章中我们主要介绍了同余运算的来源，以及模的加减法。在实数运算中，乘法与除法运算也扮演者十分重要的角色。在这篇文章中，我们将介绍模的乘除法运算，乘方运算，以及模的逆。
模的乘法运算
模的乘法(modular multiplication)运算为
同样的，我们通过一个实际的例子来理解。
我们假设 。若上式成立，等式左边等于
,
等式右边为
。因此，从实际计算中我们可以看出等式成立，下面我们不妨从图例 1 中观察一下，这个运算是怎样运作的呢？若我们将 看作围绕圆顺时针转 次，步长为 的转动，那么我们可以得到上图中的图（1）。与加减法时相同，模运算中围绕圆的完整环不影响终点的位置。因此，从上图中（2），（3）可以看出，加粗部分为对终点有实际影响的移动。图（3）中帮助我们省去了步长多余的移动；由于此题中若次数为 3 的整数倍，无论步长为几，最终模 的结果均为 ，因此，图（2）帮我们省去了多余的移动次数。
模的幂运算
因为模的幂运算(modular exponentiation)实际上是重复的乘法运算，因此我们有在平时我们计算的过程中， 常常会得到非常大的数，例如下面两个例子：这就会在我们的计算过程，以及计算机的工作过程造成很大的工作量。即便我们算出了答案，也很难直接计算它的模。那么怎样减少计算量呢？接下来就要靠模的幂运算发挥作用了。假设我们现在要计算 , 如果我们先将 算出来，想要计算其余数则必须要完整精确的数字，但是我们的计算器只能最大显示到 的完整数字。这个时候我们需要做一个小拆分，即 进而再利用模的乘法运算问题就可以解决啦，在第二个问题中，对于 次幂的数字，普通计算器上只能完整显示 ，那我们怎样用计算器计算出 呢？显然，将 拆分成 个 和 个 ，并不是很高效。我们先通过举例的方法观察一下对 进行幂运算时前几项余数的规律，
在表格的最后两行我们发现，所得结果为 和 ，当我们把其放入原式当中，就会得到我们想要的结果，以 为例（带入 同理），即为因此，我们可以利用 和 这样特殊的数字，来帮助我们简化模的幂运算计算，但是在我们计算的过程中会发现，并不是所有的运算最终都会得到 或 ，比如这道题目：计算 。和上一道题目一样观察一下对 进行幂运算时前几项余数的规律，
从上面的计算我们可以看出，虽然没有得到 或 ，但结果是四组一循环的，因此我们有因此，在实际运算中，我们往往根据不同的题目选择以上三种方法进行计算。
模的除法运算
我们考虑 ，因为 ，所以我们不能直接简单的在等式两边都除 。这就说明，一般情况下模的除法运算是不成立的。但是，如果我们增加一个条件，存在 与 互质，那么模的除法运算(modular division)就成立,如下式：
模的逆运算
说到逆运算，我们不妨回忆一下，什么样的数字才称为逆(inverse).一个数字乘它的逆等于 。从一些基础的运算我们知道：
- 一个数字乘 的逆就相当于除以 。（例如， 与 相同）
虽然在模的运算中不存在除法运算，但我们仍然有逆运算，类比数的逆运算，我们可以得到:
在了解了模的逆后，怎样找到逆成为我们现在的主要问题。一种比较天真的办法来找到 为：
在这里要注意， 只存在于整 到 中，因此测试时给予 更大的值是没有必要的。来看下面的一个示例：在整数范围 内，按照上面的方法可以找到满足该同余等式的 值为 4，如下式所示，并且，在整数范围 内不存在其他满足此同余等式的值。故整数 3 对同余 11 的模逆元素为 4。一旦在整数范围 内找到 3 的模逆元素，其他在整数范围 内满足此同余等式的模逆元素值便可很容易地写出——只需加上 的倍数便可。综上，所有整数 3 对同余 11 的模逆元素 x 可表示为 ，即
