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


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

文章插图

密码学中的同余运算密码学已经有数千年的历史,无论是在战争中,还是现在的全球互联网都起着重要的作用 。密码学的神奇故事包含着两大古老的领域——数论和概率论 。
对于本文所讨论的主题——同余运算就属于数论中的一个重要概念 。从孙子问题到凯撒密码,再到 RSA 密钥,同余运算在这些经典的密码问题中也发挥着至关重要的作用 。
什么是同余运算当我们把两个整数 A, B 相除时(B ≠ 0),往往会得到下列等式

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

文章插图

这里 A 为被除数(dividend),B 为除数(divisor),Q 为商(quotient),R 为余数(remainder) 。
有时,当我们在做 A 除 B 的运算时,我们只关心余数 R 的取值情况(当余数为 0 时,被称为整除) 。人们定义计算余数的计算为为取模运算(modulo operator),称为模(记为 mod),这样我们就得到了等式:

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

文章插图

这个时候,我们说 A 模 B 与 R 相等,B 被称作模数(modulus) 。
例如:

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

文章插图

为了更清楚地看到模是怎样运算的,我们取 [0,11] 这个区间内的整数,并将它们都除以 3,观察余数的变化情况:

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

文章插图

我们可以看到余数从 0 开始,每次增长 1,直到接近除数为止 。所以,在这个过程当中,余数是循环的 。我们不妨把所有余数围成一个圆,随着被除数的不断增长,其余数则是在这个圆里循环 。

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

文章插图

图 1
这个过程和我们钟表的原理是一样的,人们将一天分为二个以十二小时计算的单位 。在 12 点时就会归为 0,即钟表实际上是由模数为 12 的模算数 。从表盘读取时间其实就是同余运算的过程 。例如,我们在说 18 点时,很容易就可以想到是下午 6 点,因为这个时候时针从 0 点开始走过了 18 个数字,那么我们可以从图上看到,指针最后停到了 6 点 。

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

文章插图
【你所想知道密码背后的数学——同余运算】
图 2
如果用数学公式来表达这一过程,那就是
18 ÷ 12 = 1... 6
由于此时我们只关心余数的取值,所以利用‘模’这个式子同样也可以写为18mod 12=6
因此,当我们计算 Amod B 时,可以遵循以下步骤:
  1. 将钟表的结构调整为 B 个数字
  2. 从 0 开始,移动 A 个数字
  3. 最后我们所在的地方就是我们的答案: 余数 R
当然,如果 A 是正数我们就按顺时针方向移动,如果是负数,则按逆时针方向移动 。
试想,如果我们以 B 的整数倍来增大 A,那么我们的终点将会是相同的 。即对于任意的 K 有

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

文章插图

例如,
- 3 mod 10=3
- 13 mod 10=3
- 23 mod 10=3
- 33 mod 10=3

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

文章插图

图 3
同余如果 A 与 B 除以 C 有相同的余数,那么我们可以表达为

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

文章插图

这个时候,我们可以称 A 与 Bmod C 是同余(congruence modulo) 。为了更好的了解同余的这一概念,我们先来看一下所有整数模 5 的情况:

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

文章插图


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

文章插图

从上图我们可以看到,我们把整数分为 5 个区域,分别标注为 0,1,2,3,4 。而后,根据同余运算把所有的整数都放入 5 个区域当中 。
我们可以把这些区域想象成装着一堆数字的袋子,举个例子,26 应该是在标注为 1 的袋子中,因为 26mod 5=1 。
从上图中我们可以看到,1、6、11、16、21 同样也在这个袋子里 。我们把这些在一个袋子里的数字称作是一个等价类(Equivalence class) 。