你所想知道密码背后的数学——同余运算 Part II

本文作者[遇见数学创作小组]：蘑菇长颈鹿

在上一篇文章《你所想知道密码背后的数学——同余运算》中我们主要介绍了同余运算的来源，以及模的加减法。在实数运算中，乘法与除法运算也扮演者十分重要的角色。在这篇文章中，我们将介绍模的乘除法运算，乘方运算，以及模的逆。

模的乘法运算

模的乘法(modular multiplication)运算为

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

我们假设 A=4, B=5, C=3。若上式成立，等式左边等于 (4*5)mod 3 = 20 mod 3 =2，等式右边为
((4 mod 3)*(5 mod 3))=(1*2) mod 3=2 mod 3。

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

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

模的幂运算

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

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

• 2^{90}=1237940039285380274899124224
• 7^{256}=221359540004604815545018861547494593...
• 
  

这就会在我们的计算过程，以及计算机的工作过程造成很大的工作量。即便我们算出了答案，也很难直接计算它的模。那么怎样减少计算量呢？接下来就要靠模的幂运算发挥作用了。

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

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

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

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

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

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

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

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

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

模的除法运算

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

模的逆运算

说到逆运算，我们不妨回忆一下，什么样的数字才称为逆(inverse)。一个数字乘它的逆等于 1。从一些基础的运算我们知道：

1. 1. 数字 A 的逆为 1/A ，因为 A(1/A)=1。（例如， 5 的逆为 1/5 ）

2. 2. 除 0 以外的所有实数都有逆。

3. 3. 一个数字乘 A 的逆就相当于除以 A 。（例如， 10/5 与 101/5 相同）

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

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

1. 1. 把 AB mod C 中的 B ，从 0 到 C1 依次带入来计算。

2. 2. 当 AB mod C=1 时，所得 B 即为所求。

在这里要注意，B mod C 只存在于整 0 到 C 中，因此测试时给予 B 更大的值是没有必要的。来看下面的一个示例：