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

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

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

密码学中的同余运算 II

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

模的乘法运算

模的乘法(modular multiplication)运算为

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

我们假设  。若上式成立,等式左边等于  ,
等式右边为
 。
因此,从实际计算中我们可以看出等式成立,下面我们不妨从实际图例中观察一下,这个运算是怎样运作的呢?
图 1
若我们将  看作围绕圆逆时针转  次,步长为  的转动,那么我们可以得到上图中的图(1)。与加减法时相同,模运算中围绕圆的完整环不影响终点的位置。因此,从上图中(2),(3)可以看出,加粗部分为对终点有实际影响的移动。图(3)中帮助我们省去了步长多余的移动;由于此题中若次数为 3 的整数倍,无论步长为几,最终模  的结果均为  ,因此,图(2)帮我们省去了多余的移动次数。

模的幂运算

因为模的幂运算(modular exponentiation)实际上是重复的乘法运算,因此我们有
在平时我们计算的过程中, 常常会得到非常大的数,例如下面两个例子:
这就会在我们的计算过程,以及计算机的工作过程造成很大的工作量。即便我们算出了答案,也很难直接计算它的模。
那么怎样减少计算量呢?接下来就要靠模的幂运算发挥作用了。
假设我们现在要计算  , 如果我们先将  算出来,想要计算其余数则必须要完整精确的数字,但是我们的计算器只能最大显示到  的完整数字。这个时候我们需要做一个小拆分,即  进而再利用模的乘法运算问题就可以解决啦,
在第二个问题中,对于  次幂的数字,普通计算器上只能完整显示  ,那我们怎样用计算器计算出  呢?显然,将  拆分成  个  和 1 个 ,并不是很高效。
其实,对于模的幂运算还有另外一种表达方法。即为,
对于任意的正整数  ,若 ,则  。
而这种表达方式,则可以帮助我们更快速的解决问题。
我们先通过举例的方法观察一下对  进行幂运算时前几项余数的规律,
在表格的最后两行我们发现,所得结果为  和  ,当我们把其放入原式当中,就会得到我们想要的结果,以  为例(带入  同理),即为

(模的幂运算)

(模的乘法运算)

因此,我们可以利用  和  这样特殊的数字,来帮助我们简化模的幂运算计算,但是在我们计算的过程中会发现,并不是所有的运算最终都会得到  或  ,比如这道题目:计算 。和上一道题目一样观察一下对  进行幂运算时前几项余数的规律,
从上面的计算我们可以看出,虽然没有得到  或 ,但结果是四组一循环的,因此我们有
因此,在实际运算中,我们往往根据不同的题目选择以上三种方法进行计算。

模的除法运算

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

模的逆运算

说到逆运算,我们不妨回忆一下,什么样的数字才称为(inverse).
一个数字乘它的逆等于  。从一些基础的运算我们知道:
  • 数字  的逆为  ,因为 。(例如,  的逆为  )
  • 除  以外的所有实数都有逆。
  • 一个数字乘  的逆就相当于除以  。(例如,  与  相同)
虽然在模的运算中不存在除法运算,但我们仍然有逆运算,类比数的逆运算,我们可以得到:
  • 的逆为
  • 或者说
  • 当  时, 才有  的逆 。
在了解了模的逆后,怎样找到逆成为我们现在的主要问题。一种比较天真的办法来找到  为:
  1. 把  中的  ,从  到  依次带入来计算。
  2. 当  时,所得  即为所求
在这里要注意, 只存在于整  到  中,因此测试时给予  更大的值是没有必要的。

一个示例

求整数  对同余  的模逆元素 ,
上述方程可变换为  在整数范围  内,
按照上面的方法可以找到满足该同余等式的  值为 4,如下式所示,
并且,在整数范围  内不存在其他满足此同余等式的值。故整数 3 对同余 11 的模逆元素为 4。
一旦在整数范围  内找到 3 的模逆元素,其他在整数范围  内满足此同余等式的模逆元素值便可很容易地写出——只需加上  的倍数便可。
综上,所有整数 3 对同余 11 的模逆元素 x 可表示为 ,即
(0)

相关推荐