整数除法中的余数

讨论完了正整数 a 整除正整数 b 的情况，我们来看看应该如何处理正整数 a 不能整除正整数 b 的情况。前面提到过，有两种处理这一问题的方法：引入分数，或者引入余数。分数的引入已经耳熟能详了，我们来看看余数的引入会为我们带来哪些有趣的性质。

我们在日常生活中经常使用余数的概念。举个例子，假设现在的时间是 21 点。如果问从现在开始 50 个小时以后的时间（每天以 24 小时计时），我们就会自然而然地用 50 除以 24 后取余数，并把它加在当前时间上，得到 23 点这样的结果。

在第二条分支上，我们会对余数特别感兴趣，因此我们引入一个专门的记号来表示余数。令 a 和 b 为整数，m 为正整数，如果 m 可以整除 a−b，我们称 a 模 m 同余 b，并把 m 称为「模数」。这个同余关系用符号表示为 a≡b (modm)。我们可以利用时钟理解模数的概念。50 小时除以 24 小时，余数为 2 小时。这也就意味着 24 可以整除 50−2，我们称 50 模 24 同余 2，用符号表示为 50≡2(mod 24)。可以看出，模数在同余算术中起到了很大的作用。

既然负数引入的原因是加法和减法，分数引入的原因是乘法和除法，那么同余算数下是否也有加减乘除的概念呢？这个问题看起来比较简单，但深入了解后就会发现这是一个揭露质数性质的有趣问题。下面，我们根据模数的不同，分三种情况回答这个问题：模数为 2、模数为合数 n、模数为质数 p。为了论述方面，之后如无特别说明且不引起歧义，我们把同余符号≡简单地写成=，并略去 mod 符号。

当模数为 2 时，能参与运算的就剩下 0 和 1 了，这有什么可讨论的呢？既然只剩下了 0 和 1，我们干脆在模数为 2 的条件下把各种情况下的加减乘除的运算及运算结果都列出来好了。

•  0 与 0 的运算：0+0=0，0−0=0 ，0×0=0，0÷0 无意义；

•  0 与 1 的运算：0+1=1，0−1=？，0×1=1，0÷1=0；

•  1 与 0 的运算：1+0=1，1−0=1，1×0=0，1÷0 无意义；

•  1 与 1 的运算：1+1=？，1−1=0，1×1=1，1÷1=1。

我们遇到了两个有点麻烦的问题，第一个是 1+1 的结果。要说 1+1 应该等于 2，但这里是模数为 2 的同余运算，只剩下 0 和 1 这两个数，但加法运算结果超过 0 和 1 了。这怎么办？没关系，既然同余运算的定义是取余数，我们把结果除以 2 取余数就好了。2 除以 2 的余数为 0，所以我们有 1+1=0。

第二个是 0−1 的结果。要说 0−1 应该等于−1，但这里是模数为 2 的同余运算，根本没有负数的概念，怎么办？回想之前我们对负数的另一种理解：负数是与某个正数相加后结果为 0 的数。因此我们可以把 0−1 写为 0+(−1)，而所谓的 −1 就是与 1 相加后结果为 0 的数。谁与 1 相加后结果是 0 呢？就是上一段提到的 1，1+1=0。因此有 0+(−1)=0+1=1。

模数为 2 的运算就这么多，实际中有什么应用呢？模数 2 造就了计算机的诞生。

计算机到底是如何工作的？刘慈欣的著名硬科幻小说《三体》的第 17 章：三体、牛顿、冯·诺依曼、秦始皇、三日连珠[30]，就介绍了计算机的工作原理。我们先来看看冯·诺依曼为秦始皇构建的第一个部件：

「我不知道你们的名字，」冯·诺伊曼拍拍前两个士兵的肩，「你们两个负责信号输入，就叫『入 1』、『入 2』吧。」他又指指最后一名士兵，「你，负责信号输出。就叫『出』吧，」他伸手拨动三名士兵，「这样，站成一个三角形，出是顶端，入 1 和入 2 是底边。」

「哼，你让他们成楔形攻击队形不就行了？」秦始皇轻蔑地看着冯·诺伊曼。牛顿不知从什么地方掏出六面小旗。三白三黑，冯·诺伊曼接过来分给三名士兵，每人一白一黑，说：「白色代表 0，黑色代表 1。好，现在听我说，出，你转身看着入 1 和入 2，如果他们都举黑旗，你就举黑旗，其他的情况你都举白旗，这种情况有三种：入 1 白，入 2 黑；入 1 黑，入 2 白；入 1、入 2 都是白。」

计算机用位（bit）表示信息，每个位只有两个可能的值，即 0 或者 1。在故事中，我们把白旗看作 0，把黑旗看作 1。冯·诺依曼构建了 0 和 1 的第一种运算关系：「与」。从描述中我们可以看到，随着运算的‘入’不同，运算结果的‘出’也不同。冯·诺依曼构建的第一个运算关系的全部运算结果可以用表 2 描述：

入1

入2

出

运算关系

0

0

0

0×0=0

0

1

0

0×1=0

1

0

0

1×0=0

1

1

1

1×1=1

表 2：冯·诺依曼构建的运算关系「与」

稍微对比一下我们就可以看出，这个运算关系和模 2 下的乘法运算有异曲同工之妙！既然与运算是模 2 下的乘法，那么冯·诺依曼构建的下一个运算关系会是模 2 下的加法吗？

冯·诺伊曼转向排成三角阵的三名士兵：「我们构建下一个部件。你，出，只要看到入 1 和入 2 中有一个人举黑旗，你就举黑旗，这种情况有三种组合——黑黑、白黑、黑白，剩下的一种情况——白白，你就举白旗。明白了吗？好孩子，你真聪明，门部件的正确运行你是关键，好好干，皇帝会奖赏你的！下面开始运行：举！好，再举！再举！好极了，运行正常，陛下，这个门部件叫或门。」

冯·诺依曼所构建的第二种运算关系称为「或」，其全部运算结果可以用下表 3 描述：

入 1

入 2

出

0

0

0

0

1

1

1

0

1

1

1

1

表 3：冯·诺依曼构建的运算关系「或」

感觉和加法运算没什么关系，我们继续往后看：

然后，冯·诺伊曼又用三名士兵构建了与非门、或非门、异或门、同或门和三态门，最后只用两名士兵构建了最简单的非门，出总是举与入颜色相反的旗。

我们注意到有一个运算关系为「异或」。异或运算是指，如果两个「入」所举的旗子是同一个颜色，「出」就举白旗；如果两个「入」所举的旗子不是同一个颜色，「出」就举黑旗。异或运算的全部结果可以用表 4 描述：

入1

入2

出

运算关系

0

0

0

0+0=0

0

1

1

0+1=1

1

0

1

1+0=1

1

1

0

1+1=0

表 4：冯·诺依曼构建的运算关系「异或」

这个运算关系和模 2 下的加法运算又有异曲同工之妙！

实际上，使用与、异或和「出总是举与入颜色相反的旗」的「非」这 3 种基本运算就可以实现计算机中的所有运算关系。若把非运算看作「入 2」固定为 1 的异或运算（运算结果如表 5 所示），我们完全可以用模 2 下的加法和乘法运算表示计算机中的全部运算关系。

入1

入2（固定）

出

运算关系

0

1

1

0+1=1(mod 2)

1

1

0

1+1=0(mod 2)

表 5：运算「非」和「与」的关系

而计算机正是这些简单的运算构成的，正如冯·诺依曼之后所说：

「不需要，我们组建一千万个这样的门部件，再将这些部件组合成一个系统，这个系统就能进行我们所需要的运算，解出那些预测太阳运行的微分方程。这个系统，我们把它叫做……嗯，叫做……」

「计算机。」汪淼说。

人类通过模 2 这样一个最为基本的同余运算，就可以用数学方式描述计算机的计算模式了。

我们再来看看当模数为合数 n 时会发生什么。当模数为 n 时，可以参与运算的数为所有小于 n 的整数了，即：0、1、2、…、n−1，一共有 n 个数。其实，模数为 n 的情况特别复杂。为了简单起见，我们这里只考虑 n 为两个质数乘积的形式，就以 n=10=2×5 为例好了，因为 10 是 2 和 5 这两个质数的乘积，并且模 10 取余数很简单：看结果的个位即可。

首先要解决减法和负数问题。模数为 n 时的解决方法和模数为 2 的解决方法相似。对于小于 n 的任意数 a，哪个数和 a 相加的结果等于 0 呢？结果很简单，n−a。首先 n−a<n 是肯定满足的。其次，a+(n−a)≡a−a+n≡n≡0 (modn)。这样，我们就成功的解决了模数为 n 时加法的全部问题。例如，n=10 时，小于 10 的数所对应的负数如表 6 所示。

a

0

1

2

3

4

5

6

7

8

9

-a

0

9

8

7

6

5

4

3

2

1

表 6：模 n=10 下的负数表

然后要解决除法和倒数的问题。对于 0 来说很简单，任何数乘以 0 还是 0；0 除以任何数也是 0；任何数除以 0 都没有意义。但对于不是 0 的数来说，除法和倒数的问题解决起来就有那么一点复杂了。根据前面的描述，我们要对小于 n 的数 a 找到 a⁻¹，要求 a 与 a⁻¹ 相乘的结果在模 n 下等于 1，即 a×a⁻¹≡1 (modn)。

然而，很快我们就会发现，对于有些 a 来说，可以找到 a⁻¹，例如，n=10 时，对于 a=3，我们有 3×7≡21≡1 (mod 10)，因此 a⁻¹=7。但是对于有些 a 来说，我们却找不到这样的数。例如，n=10 时，对于 a=2：2×1=2，2×2=4，2×3=6，2×4=8，2×5=0，2×6=2，2×7=4，2×8=6，2×9=2，根本没有等于 1 的。这怎么办？

干脆，我们把所有能找到 a⁻¹ 的 a 都列出来，看看有没有什么规律。n=10 时， a⁻¹ 的找寻结果如表 7 所示。

a

1

2

3

4

5

6

7

8

9

a^-1

1

\

7

\

\

\

3

\

9

表 7：模 n=10 下的负数表

有什么规律吗？我们首先可以观察到：偶数都找不到。那 5 找不到又是个什么情况？等等，当 a 和模数 10 的最大公约数为 1 时，也就是 a 和 10 互质时，就能找到 a⁻¹；反之，当 a 和模数 10 不互质，就找不到 a⁻¹。实际上，数学家们已经证明：对于任意 a<n，只有当 a 与 n 互质，才能找到 a−1。给定满足与 n 互质的 a，怎么才能快速找到 a⁻¹ 呢？总不能一个一个去试吧？实际上，利用前面提到的辗转相除法，就可以快速找到 a⁻¹。

在小于 n 的所有整数中，与 n 互质的数有多少个呢？当 n=10 时，一共有 1、3、7、9 这 4 个数满足条件。实际上，当 n=p×q，其中 p 和 q 为质数时，满足条件的数共有 (p−1)(q−1) 个。例如，当 n=10=2×5 时，我们可以得到 (2−1)(5−1)=4。如果 n 有更多的质数因子，满足条件数的个数计算会变得稍微复杂一些。我们把满足小于 n，且与 n 互质的数总个数用一个函数 φ(n) 来表示。这个函数叫做「欧拉函数」（Euler Function），没错，这个欧拉就是和哥德巴赫写信的欧拉。

既然与模数 n 互质的数 a 都能找到 a⁻¹ ，这些数是不是还有什么其它的性质？我们列举这些数的两个非常重要的性质。

第一，这些数在模 n 下互相之间进行乘法运算，结果仍然是这些数。一般来说，如果一些数互相之间运算后结果还在这些数之内，我们称这些数在此运算下具有「封闭性」。我们列举一下 n=10 的情况。与 10 互质的数为 1、3、7、9，我们有：

•  1 与其它数的乘法运算：1×3=3，1×7=7，1×9=9

•  3 与其它数的乘法运算：3×1=3，3×3=9，3×9=7

•  9 与其它数的乘法运算：9×1=3，9×3=7，9×9=1

第二，如果我们对这些数求「幂」，会有更有趣的结果。所谓幂运算，就是让数自己和自己相乘，把乘多少次写在右上角。例如，在自然数条件下， 3 4 =3×3×3×3=81。我们试试在模 n=10 的条件下计算这些数的「幂」，结果如表 8 所示（注意，规定 a 0 =1）。

a

1

3

7

9

a⁰

1

1

1

1

a¹

1

3

7

9

a²

1×1=1

3×3=9

7×7=9

9×9=1

a³

1×1×1=1

3×3×3=7

7×7×7=3

9×9×9=9

a⁴

1×1×1×1=1

3×3×3×3=1

7×7×7×7=1

9×9×9×9=1

表 8：模 n=10 下的幂运算结果表

观察结果后我们会发现，对于所有的 a，都有 a⁴=1。4 这个数怎么这么眼熟呢？对了！4 就是这些数的总个数。事实上，在模 n 下对所有存在倒数的数求其 φ(n) 的幂，结果都为 1。

更有意思的是，对于 3 和 7 来说，a⁰、a¹、a²、a³ 的结果能把 1、3、7、9 各得到一遍（虽然得到的顺序不太一样），到 a⁴=1 又循环回了 1。事实上，在模 n 下一定能找到一个数 g，使得 g⁰、g¹、…、g^φ(n)−1把所有与 n 互质且小于 n 的正整数各得到一遍，看起来就好像 g 把所有这些数都生成（Generate）了一遍。因此，我们把满足这种条件的数称为「生成元」（Generator）。

有关模 n 条件下的一些性质我们就讲到这里。

我们最后来看看当模数为质数 p 时会发生什么。当模数为 p 时，可以参与运算的数为 0、1、2、…、p−1 这 p 个数。我们用与 10 最近的质数 11 为例。

减法和负数问题很容易解决。对于小于 p 的任意数 a，哪个数和 a 相加的结果等于 0 呢？同样是 p−a。例如，p=11 时，每个小于 11 的数所对应的负数如表 9 所示。

a

0

1

2

3

4

5

6

7

8

9

10

-a

0

10

9

8

7

6

5

4

3

2

1

表 9：模 p=11 下的负数表

p 是质数为除法和倒数问题的解决带来了很大的便利，因为所有小于 p 的整数都与 p 互质。这样一来，所有小于 p 的整数 a 都能找到 a⁻¹ 了，欧拉函数的形式也非常简单：φ(p)=p−1。p=11 时， a⁻¹ 的结果如表 10 所示。

a

1

2

3

4

5

6

7

8

9

10

a^-1

1

6

4

3

9

2

8

7

5

10

表 10：模 p=11 下的倒数表

模数为 n 的其它性质在模数为 p 时依然满足。第一，显然这些数在乘法运算下仍具有封闭性，反正所有小于 p 的数都在里面了。第二，任意 a 求「幂」同样满足 a^φ(p)=a^p−1=1，也同样存在生成元。模 p=11 时各个数的求「幂」结果如表 11 所示。

A

1

2

3

4

5

6

7

8

9

10

a⁰

1

1

1

1

1

1

1

1

1

1

a¹

1

2

3

4

5

6

7

8

9

10

a²

1

4

9

5

3

3

5

9

4

1

a³

1

8

5

9

4

7

2

6

3

10

a⁴

1

5

4

3

9

9

3

4

5

1

a⁵

1

10

1

1

1

10

10

10

1

10

a⁶

1

9

3

4

5

5

4

3

9

1

a⁷

1

7

9

5

3

8

6

2

4

10

a⁸

1

3

5

9

4

4

9

5

3

1

a⁹

1

6

4

3

9

2

8

7

5

10

a¹⁰

1

1

1

1

1

1

1

1

1

1

表 11：模 p=11 下的幂运算结果表

从表 11 的计算结果也可以看出，2、6、7、8 通过幂运算可以把所有小于 11 的数各得到一遍。这些数就是模 11 下的生成元了。

同余和模数的引入使得质数包含了有趣的性质，而且似乎也挺好理解的，有什么比较难的问题吗？下面我们就来看看与质数相关的两个非常重要的困难问题：整数分解问题与离散对数问题。

数学家们很早就意识到，质数是构造正整数的积木。如果哥德巴赫猜想是对的，那么所有大于 2 的偶数都可以表示为 2 个质数的和；所有大于 5 的奇数都可以表示为 3 个质数的和。然而，还可以通过另一种方法用质数表示正整数。这个方法描述起来似乎有点麻烦，但是证明比较简单，它叫做「算术基本定理」。

算术基本定理：每个大于 1 的正整数或者为质数，或者可唯一地写为两个或多个质数的乘积。

虽然小学老师没有详细讲过这个定理，但这个定理确实挺好理解的，简单来说就是每个正整数都可以分解成质数因子相乘的形式。来看几个例子：

•  100 是一个合数，可以写为：100=2×2×5×5=2²×5²；

•  999 是一个合数，可以写为：999=3×3×3×37=3³×37；

•  1024 是一个合数，可以写为：1024=2×2×2×2×2×2×2×2×2×2=2¹⁰。

然而，算术基本定理只是告诉数学家们合数可以写为两个或多个质数的乘积形式，但是没有具体告诉数学家们具体怎么进行合数的质数分解。对于比较小的合数，我们可以尝试用它除以各个正整数，通过看是否能够整除来找到质因子。但是如果合数太大，这种方法的效率就会变得非常低。这个问题到现在为止依然困扰着数学家们。这个问题被称为「整数分解问题」（Integer Factorization Problem）[31]。

整数分解问题虽然没有被解决，但因为一直以来也一直没有找到应用方法，所以数学家们对解决这个问题动力也有所不足。然而，「现代密码学」诞生的标志之一，「公钥密码学」的出现，特别是 Rivest，Shamir 和 Adleman 提出了「RSA 算法」之后（我们后面就会详细讲解 RSA 算法），使得整数分解问题重新站到了历史的舞台上，这是因为 RSA 算法安全的原因正是由于整数分解问题是一个很困难的问题。

为了确定人类可以解决整数分解问题的难度，也为了衡量 RSA 算法的安全性，Rivest，Shamir 和Adleman 组建的「RSA 实验室」[32]于 1991 年 3 月 18 日发起了「RSA分解挑战」项目[33]，号召全世界的研究者们研究整数分解问题。他们的具体做法是：公开一系列不同长度的，由两个大质数相乘得到的合数，并邀请全世界的研究者们分解这些合数。合数的大小从 100 位十进制长一直到 617 位十进制长（依次称为 RSA-100, …, RSA-2048）。如果分解成功，RSA实验室将会支付一笔数额不菲的奖金。成功分解 RSA-2048 所对应的奖金达到 200000 美元！这些合数被称为「RSA 数」。RSA 分解挑战项目极大地激发了全世界研究者对于整数分解问题的探究。

在 RSA 分解挑战项目开始后不到 2 周，RSA-100 就在 1991 年 4 月 1 日被分解出来了。分解出 RSA-100 的学者是 Lenstra，他因此也获得了 1000 美元的奖金。一年以后的 1992 年 4 月 14 日，Lenstra 和 Manasse 分解出第二个RSA数：RSA-110，奖金为 4429 美元。后来，更大的 RSA 数被成功分解。到 2005 年，来自德国波恩大学的Franke 等人成功分解了RSA-640，获得了 20000 美元的奖金。

由于人类对于密码学理解的不断深入，RSA实验室认为没有必要继续进行 RSA 分解挑战项目了。因此，RSA 分解挑战项目于 2007 年终止[34]。然而，全世界的研究者们至今还在致力于解决 RSA 分解挑战。截止目前，被分解的最大 RSA 数为 Kleinjung 等人于 2009 年 12 月 12 日成功分解的 RSA-768，不过这里的 768 指的是此合数的二进制长度，其对应的十进制长度为 232 位。

另一个困难问题理解起来就不像整数分解问题那样直观了。我们前面讲到，对于与模数 n 互质且小于 n 的所有整数中，存在一个生成元 g，使得 g⁰、g¹、…、g^φ(n)−1 会把所有小于 n 的数各得到一遍。在模 n 条件下，给定生成元 g 和某个小于 n 的正整数 a，可以通过一个称为「同余幂」的算法快速得到 b=g^a。由于生成元的特殊性，数学家们也知道对于任意一个小于 n 的正整数 b，一定存在一个小于 n 的正整数 a，使得 b=g^a 。但我们会发现，得到的顺序并没有什么规律。例如，当 n 为质数 p=11，g=2 时，得到的顺序如表 12 所示，感觉毫无规律。

2⁰

2¹

2²

2³

2⁴

2⁵

2⁶

2⁷

2⁸

2⁹

2¹⁰

1

2

4

8

5

10

9

7

3

6

1

表 12：模 p=11 下的倒数表

是否存在一种方法能快速得到满足条件的 a 呢？这个问题和实数上的求对数很像：如果在实数上，我们知道 a=log g^b ，而且用计算器就可以很快得到结果。但这个问题在模 n 条件下就变得特别困难。这个问题被称为「离散对数问题」（Discrete Logarithm Problem）[35]。

我们了解到，人类现在已经成功分解了 232 位的 RSA 数，那么离散对数问题有没有对应的记录呢？也是有的，我们这里仅介绍模数为质数 p 的情况。2005 年 6 月 18 日，Joux 和 Lercier 宣布，它们应用了一个主频为 1.15GHz，具有 16 核的 HP AlphaServer 计算机，花费了 3 周的时间，使用筛法解决了十进制 130 位长强质数下的某一个数的离散对数问题[36]。2007 年 2 月 5 日，Kleinjung 宣布，它应用并行计算技术，通过多种计算机进行并行处理，最终使用筛法解决了十进制 160 位长安全质数下某一个数的离散对数问题[37]。2014 年 6 月 11 日，Bouvier、Gaudry、Imbert、Jeljeli 和 Thomé 同样使用筛法解决了十进制 180 位长安全质数下某一个数的离散对数问题[38]。模数为质数 p 的离散对数问题计算最新进展于 2016 年 6 月 16 日公布，Kleinjung、Diem、Lenstra、Priplata、Stahlke 宣布，它们从 2015 年 2 月开始，经过 1 年 4 个月的计算，应用了 6600 个主频为 2.2GHz 的 Intel Xeon E5-2660 处理器，最终成功应用筛法得到了十进制 232 位长安全质数下某一个数的离散对数问题。注意，以上所有的成果只是找到了某一个数的离散对数。要是求解所有数的离散对数，即使使用现在最先进的计算机处理器，所花费的时间估计也是个天文数字。

有关同余和模数的性质我们就介绍到这里。既然模数为 2 解决了计算机的计算过程描述问题，那么模数为 n 和模数为 p 能为我们带来什么呢？特别是整数分解问题和离散对数问题，真的只能作为一个困难问题困扰数学家吗？1976 至 1977 年，人类终于找到了困难问题的使用方法。而人类找到使用方法的日子，就是现代密码学诞生的日子。