[遇见数学] 核心成员: 蘑菇长颈鹿

一枚数学系的大学生，喜欢数学文化的小视频，翻译中如有问题，请多指正~

密码学中的同余运算 II

在上一篇文章中我们主要介绍了同余运算的来源，以及模的加减法。在实数运算中，乘法与除法运算也扮演者十分重要的角色。在这篇文章中，我们将介绍模的乘除法运算，乘方运算，以及模的逆。

模的乘法运算

模的乘法(modular multiplication)运算为

同样的，我们通过一个实际的例子来理解。

我们假设。若上式成立，等式左边等于 ,
等式右边为
。

因此，从实际计算中我们可以看出等式成立，下面我们不妨从实际图例中观察一下，这个运算是怎样运作的呢？

图 1

若我们将看作围绕圆逆时针转次，步长为的转动，那么我们可以得到上图中的图（1）。与加减法时相同，模运算中围绕圆的完整环不影响终点的位置。因此，从上图中（2），（3）可以看出，加粗部分为对终点有实际影响的移动。图（3）中帮助我们省去了步长多余的移动；由于此题中若次数为 3 的整数倍，无论步长为几，最终模的结果均为，因此，图（2）帮我们省去了多余的移动次数。

模的幂运算

因为模的幂运算(modular exponentiation)实际上是重复的乘法运算，因此我们有

在平时我们计算的过程中，常常会得到非常大的数，例如下面两个例子：

这就会在我们的计算过程，以及计算机的工作过程造成很大的工作量。即便我们算出了答案，也很难直接计算它的模。

那么怎样减少计算量呢？接下来就要靠模的幂运算发挥作用了。

假设我们现在要计算 , 如果我们先将算出来，想要计算其余数则必须要完整精确的数字，但是我们的计算器只能最大显示到的完整数字。这个时候我们需要做一个小拆分，即进而再利用模的乘法运算问题就可以解决啦，

在第二个问题中，对于次幂的数字，普通计算器上只能完整显示，那我们怎样用计算器计算出呢？显然，将拆分成个和 1 个，并不是很高效。

其实，对于模的幂运算还有另外一种表达方法。即为，

对于任意的正整数，若，则。

而这种表达方式，则可以帮助我们更快速的解决问题。

我们先通过举例的方法观察一下对进行幂运算时前几项余数的规律，

在表格的最后两行我们发现，所得结果为和，当我们把其放入原式当中，就会得到我们想要的结果，以为例（带入同理），即为

(模的幂运算)

(模的乘法运算)

因此，我们可以利用和这样特殊的数字，来帮助我们简化模的幂运算计算，但是在我们计算的过程中会发现，并不是所有的运算最终都会得到或，比如这道题目：计算。和上一道题目一样观察一下对进行幂运算时前几项余数的规律，

从上面的计算我们可以看出，虽然没有得到或，但结果是四组一循环的，因此我们有

因此，在实际运算中，我们往往根据不同的题目选择以上三种方法进行计算。

模的除法运算

我们考虑，因为，所以我们不能直接简单的在等式两边都除。这就说明，一般情况下模的除法运算是不成立的。但是，如果我们增加一个条件，存在与互质，那么模的除法运算(modular division)就成立,如下式：

若 , 并且 , 那么我们有。

模的逆运算

说到逆运算，我们不妨回忆一下，什么样的数字才称为逆(inverse).

一个数字乘它的逆等于。从一些基础的运算我们知道：

数字的逆为，因为。（例如，的逆为）
除以外的所有实数都有逆。
一个数字乘的逆就相当于除以。（例如，与相同）

虽然在模的运算中不存在除法运算，但我们仍然有逆运算，类比数的逆运算，我们可以得到:

的逆为
或者说
当时，才有的逆。

在了解了模的逆后，怎样找到逆成为我们现在的主要问题。一种比较天真的办法来找到为：

把中的，从到依次带入来计算。
当时，所得即为所求

在这里要注意，只存在于整到中，因此测试时给予更大的值是没有必要的。

一个示例

求整数对同余的模逆元素，

即

上述方程可变换为在整数范围内，

按照上面的方法可以找到满足该同余等式的值为 4，如下式所示，

并且，在整数范围内不存在其他满足此同余等式的值。故整数 3 对同余 11 的模逆元素为 4。

一旦在整数范围内找到 3 的模逆元素，其他在整数范围内满足此同余等式的模逆元素值便可很容易地写出——只需加上的倍数便可。

综上，所有整数 3 对同余 11 的模逆元素 x 可表示为，即

揭开密码的神秘面纱——同余运算 Part II