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

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

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

密码学中的同余运算

密码学已经有数千年的历史，无论是在战争中，还是现在的全球互联网都起着重要的作用。密码学的神奇故事包含着两大古老的领域——数论和概率论。
对于本文所讨论的主题——同余运算就属于数论中的一个重要概念。从孙子定理到凯撒密码，再到 RSA 密钥，同余运算在这些经典的密码问题中也发挥着至关重要的作用。

什么是同余运算

当我们把两个整数  相除时()，往往会得到下列等式
或
这里  为被除数(dividend)， 为除数(divisor)， 为商(quotient)， 为余数(remainder)。
有时，当我们在做  除  的运算时，我们只关心余数  的取值情况(当余数为 0 时，被称为整除)。人们定义计算余数的计算为取模运算(modulo operator)，称为模（记为 ），这样我们就得到了等式
这个时候，我们说  模  与  相等， 被称作模数(modulus)。
例如：
  • ，可以写作 .
  • ，可以写作 .
为了更清楚地看到模是怎样运算的，我们取  这个区间内的整数，并将它们都除以 3，观察余数的变化情况
我们可以看到余数从 0 开始，每次增长 1，直到接近除数为止。所以，在这个过程当中，余数是循环的。我们不妨把所有余数围成一个圆，随着被除数的不断增长，其余数则是在这个圆里循环。
图 1
这个过程和我们钟表的原理是一样的，人们将一天分为二个以十二小时计算的单位。在 12 点时就会归为 0 ，即钟表实际上是由模数为 12 的模算数。从表盘读取时间其实就是同余运算的过程。例如，我们在说 18 点时，很容易就可以想到是下午 6 点，因为这个时候时针从 0 点开始走过了 18 个数字，那么我们可以从图上看到，指针最后停到了 6 点。
图 2
如果用数学公式来表达这一过程，那就是
由于此时我们只关心余数的取值，所以利用‘模’这个式子同样也可以写为 因此，当我们计算  时，可以遵循以下步骤
  1. 将钟表的结构调整为  个数字
  2. 从 0 开始，移动  个数字
  3. 最后我们所在的地方就是我们的答案: 余数
当然，如果  是正数我们就按顺时针方向移动，如果是负数，则按逆时针方向移动。试想，如果我们以  的整数倍来增大 ，那么我们的终点将会是相同的。即对于任意的
例如，
图 3

同余

如果  与  除以  有相同的余数，那么我们可以表达为
这个时候，我们可以称  与  是同余(congruence modulo)。为了更好的了解同余的这一概念，我们先来看一下所有整数模 5 的情况
从上图我们可以看到，我们把整数分为 5 个区域，分别标注为 0，1，2，3，4。而后，根据同余运算把所有的整数都放入 5 个区域当中。
我们可以把这些区域想象成装着一堆数字的袋子，举个例子，26 应该是在标注为 1 的袋子中，因为 。
从上图中我们可以看到，1、6、11、16、21 同样也在这个袋子里。我们把这些在一个袋子里的数字称作是一个等价类(Equivalence class)。
我们还可以观察到，在这个等价类中数与数之间相差的都是 5 的整数倍。就是说，如果我们要把所有整数模 ，那么将会得到  个袋子，每一个袋子中的数都差  的整数倍。
在数学上，我们就用  来表示在这个情况，并读作  同余于。在这个表达中，我们要注意：
  1. 是一个表示相同的、等价的符号。即  和  在一个等价类中。
  2. 告诉我们 和  要除的数。
  3. 当以上两种情况都满足时，我们称“”为模  的同余

等价关系

从上面模 5 的例子可以看出，我们把所有的整数看成一个圆饼，通过模运算将其切成了五份，分为了五个等价类，对于这种告诉我们如何分出等价类的方法，我们称为等价关系(Equivalence relation)。
等价关系有三种性质：
  • 自反性(Reflexivity)： 与  有关。
  • 对称性(Symmetry)：若  与  有关，那么  与  有关。
  • 传递性(ransitivity)：若  与  有关， 与  有关,则  与  有关。
由于同余运算也是等价关系，所以也就满足这三条性质，比如：
  • (自反性)
  • 若 ，那么  (对称性)
  • 若 ，且 ，那么  (传递性)
利用这三条性质，可以帮助我们完成很多模的运算。

模的加减运算

数与数之间存在加减法运算，那么模与模之间是否存在类似的呢？如果存在，这将更方便于我们的计算。我们不妨假设模之间的运算是这样的过程：
我们先来尝试用一个例子来验证下，假设 。那么我们得到，等式的左边 ，等式的右边 。
因此，从这个例子来看，这个等式是成立的。
但是，这个等式为什么成立，它又是怎样运作的呢？我们在图形上更直观的角度来观察一下。
从上图我们可以看出，只要是围绕圆的完整环就不影响终点的位置，通过先计算 mod 7 可以帮助我们忽略围绕圆的完整步数。通过加法运算，使得他们从 0 开始，顺时针移动。对于减法运算，我们只需要将 B 取为负数，直观上，相减就视为逆时针地移动，公式如下：
(未完待续)
参考: khanacademy.org, 维基百科
赞 (0)

相关推荐