首页 趣味数学故事正文

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

xiawuyouke 趣味数学故事 2022-02-13 21:57:54 54 0 同余

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

密码学中的同余运算

密码学已经有数千年的历史,无论是在战争中,还是现在的全球互联网都起着重要的作用。密码学的神奇故事包含着两大古老的领域——数论和概率论。

对于本文所讨论的主题——同余运算就属于数论中的一个重要概念。从孙子问题到凯撒密码,再到 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)。

我们还可以观察到,在这个等价类中数与数之间相差的都是 5 的整数倍。就是说,如果我们要把所有整数模 C,那么将会得到 C 个袋子,每一个袋子中的数都差 C 的整数倍。

在数学上,我们就用 A ≡ B(mod C) 来表示在这个情况,并读作 A 同余于Bmod C。在这个表达中,我们要注意:

1. ≡ 是一个表示相同的、等价的符号。即 A 和 B 在一个等价类中。

2. (mod C)告诉我们 A 和 B 要除的数。

3. 当以上两种情况都满足时,我们称“≡”为模 C 的同余

等价关系

从上面模 5 的例子可以看出,我们把所有的整数看成一个圆饼,通过模运算将其切成了五份,分为了五个等价类,对于这种告诉我们如何分出等价类的方法,我们称为等价关系(Equivalence relation)。

等价关系有三种性质:

- 自反性(Reflexivity):A 与 A 有关。

- 对称性(Symmetry):若 A 与 B 有关,那么 B 与 A 有关。

- 传递性(ransitivity):若 A 与 B 有关,B 与 C 有关,则 A 与 C 有关。

由于同余运算也是等价关系,所以也就满足这三条性质,比如:

- 3 ≡ 3(mod 5) (自反性)

- 若 3 ≡ 8(mod 5),那么 8 ≡ 3(mod 5) (对称性)

- 若 3 ≡ 8(mod 5),且 8 ≡ 18(mod 5),那么 3 ≡ 18(mod 5) (传递性)

利用这三条性质,可以帮助我们完成很多模的运算。

模的加减运算

数与数之间存在加减法运算,那么模与模之间是否存在类似的呢?如果存在,这将更方便于我们的计算。

我们不妨假设模之间的运算是这样的过程:

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

我们先来尝试用一个例子来验证下,假设 A=12,B=9,C=7。

那么我们得到,等式的左边 (12+9)mod 7=0,等式的右边 (12mod 7+9mod 7)mod 7=0。

因此,从这个例子来看,这个等式是成立的。

但是,这个等式为什么成立,它又是怎样运作的呢?我们在图形上更直观的角度来观察一下

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

从上图我们可以看出,只要是围绕圆的完整环就不影响终点的位置,通过先计算 mod 7 可以帮助我们忽略围绕圆的完整步数。通过加法运算,使得他们从 0 开始,顺时针移动。

对于减法运算,我们只需要将 B 取为负数,直观上,相减就视为逆时针地移动,公式如下:

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


免费下载:微信扫码关注网站官方公众号【中小学趣味数学 qwshuxue
趣味数学二维码
1、回复 “101”免费领取《【小学奥数】学er思内部题库word可打印
2、回复 “102”免费领取《【记忆力教程】快速高效学习教程
3、回复 “103”免费领取《一分钟速算教程
4、回复 “104”免费领取《Top 32经典英文启蒙绘本PDF+MP3
5、回复 “105”免费领取《儿童英语绘本195本【PDF版】
6、回复 “106、107、108”免费领取《更多神秘礼物……
版权说明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

本文链接:http://www.zxxedu.cn/38521.html

发表评论

评论列表(0人评论 , 54人围观)
☹还没有评论,来说两句吧...