本文为《离散数学及其应用》第四章的阅读笔记

一、数论

  • 整除：使用记号 a| b 表示 a 能整除 b；可以用量词表达为：$\exists c (ac = b)$

此处希望读者留意：a 整除 b 的含义是 b 是 a 的整数倍；而不是 a 是 b 的整数倍。

定理1：令 a，b，c 为整数，其中 $a \not= 0$。则

  • 如果 a | b 和 a | c，则 a | (b + c)
  • 如果 a | b，那么对所有整数 c 都有 a | bc
  • 如果 a | b，b | c，则 a| c

此处对定理1 的第二条做出解释：

定理1 存在一个实用的推论：

推论1：如果 a，b，c 是整数，其中 $a \not= 0$，使得 a | b 和 a | c，那么当 m 和 n 是整数时有 a | mb + nc。

  • 除法算法：

定理2：令 a 为整数， d 为正整数。则存在唯一的整数 q 和 r，满足 $0 \leq r < d$，使得 a = dq + r。

虽然这个定理表述得十分复杂，但原理非常简单：被除数 = 除数 $\times$ 商 + 余数。

  • 模算术：

如果 a 和 b 为整数而 m 为正整数，则当 m 整除 (a - b) 时称为 a 模 m 余 b。用记号 $a \equiv b (mod \ m)$。

我们称 $a \equiv b (mod \ m)$ 为同余式， m 为模。

定理3：令 a 和 b 为整数，并令 m 为正整数。则 a $\equiv$ b (mod m) 当且仅当 a mod m = b mod m。

定理三可以作如下理解：被除数除以除数得余数 等于 余数除以除数的余数。

定理4：令 m 为正整数。整数 a 和 b 是模 m 同余的，当且仅当存在整数 k 使得 a = b + km

定理四可以作如下理解：模相同的数同余的两数，差一定为模的整数倍。

定理5：令 m 为正整数。如果 $a \equiv b (mod \ m)$，$c \equiv d (mod \ m)$，则 $(a + c) \equiv (b + d) (mod \ m)$

定理五可由各位读者自行证明。

推论1：令 m 是正整数，令 a 和 b 是整数。则 (a + b) mod m = ((a mod m) + (b mod m)) mod m，并且 ab mod m = ((a mod m)(b mod m)) mod m。

推论一可以理解为：和的模 等于 模的和再做模运算；乘积的模 等于 模的乘积再做模运算。

对于模 m 运算，我们可以用运算符 mod m 表示。

加法的模：$a +_m b = (a + b) mod\ m$

乘法的模：$a ·_m b = (a · b) mod\ m$

运算 加法的模、乘法的模 满足如下性质：

  1. 封闭性：如果 a 和 b 属于 $Z_m$，则 $a +_m b$ 和 $a ·_m b$ 也属于 $Z_m$
  2. 结合律：如果 a 、b 和 c 属于 $Z_m$，则有 $（a +_m b） +_m c = a +_m (b +_m c)$ 和 $（a ·_m b） ·_m c = a ·_m (b ·_m c)$
  3. 交换律：如果 a 和 b 属于 $Z_m$，则有 $a +_m b = b +_m a$ 和 $a ·_m b = b ·_m a$
  4. 单位元：如果 a 属于 $Z_m$，则有 $a +_m 0 = 0 +_m a = a$ 和 $a ·_m 0 = 0 ·_m a = a$
  5. 加法逆元：如果 $a \not= 0$ 属于 $Z_m$，则 m - a 是 a 的模 m 加法逆元，则有 $a +_m (m - a) = 0$ 且 $0 +_m 0 = 0$
  6. 分配律：如果 a 、b 和 c 属于 $Z_m$，则有 $a ·_m (b +_m c) = (a ·_m b) +_m (a ·_m c)$ 和 $a +_m (b ·_m c) = (a +_m b) ·_m (a +_m c)$

以上性质均较易理解，此处不多做解释。

  • 数的表示：

定理1：令 b 是一个大于 1 的整数。则如果 n 是一个正整数，就可以唯一地表示下面的形式
$n = a_kb^k + a_{k-1}b^{k-1} + … + a_1b + a_0$
其中 k 为非负整数，$a_0$，$a_1$，…，$a_k$ 是小于 b 的非负整数，且$a_k \not= 0$

我们也将上述表达式称为 n 的 b 进制表达式。

  • 模指数运算

在密码学中能够有效的计算 $b^n mod \ m$ 非常重要，其中 b、n、m 是大整数。先计算 $b^n$ 再求余数显然是不可行的。我们将介绍一种利用指数 n 的二进制展开式的一个算法：

例如对于 $n = (a_{k-1} … a_1a_0)$，计算 $b_n$：$b^n = b^{a_{k-1}2^{k-1} +…+a_1·2+a_0} = b^{a_{k-1}2^{k-1}}…b^{a_1·2}·b^{a_0}$

因此我们需要计算 $b^{a_{k-1}2^{k-1}}，…b^{a_1·2}，b^{a_0}$ ，并依次相乘。为了提高效率，每乘一项就可以进行一次模运算。

以下为伪代码：

1
2
3
4
5
6
7
8
procedure modular exponentiation (b: 整数, n, m：正整数) {
    x := 1
    power := b mod m
    for i := 0 to k - 1
        if a_i = 1 then x := (x · power) mod m
        power := (power · power) mod m
    return x
}
  • 欧几里得算法求最大公约数

传统的方法也称辗转相除法，例如求 91 和 287 的最大公约数 gcd(a, b)。

  1. 用大数 287 除以 小数 91，得到 287 = 91 · 3 + 14
  2. 91 和 287 的任何公约数，也必定是 287 - 91 · 3 = 14 的因子；因此，求 gcd(91, 287)，转化为 gcd(91, 14)
  3. 用大数 91 除以小数 14，…

以此类推。下面介绍欧几里得算法：

引理：令 a = bq + r，其中 a，b，q 和 r 均为整数。则 gcd(a, b) = gcd(b, r)。

假定 a 和 b 为正整数，且 $b \leq a$。令 $r_0 = a$ 和 $r_1 = b$。当连续运用整除运算时。可得：

  • $r_0 = r_1q_1 + r_2$ ($0 \leq r_2 < r_1$)

  • $r_1 = r_2q_2 + r_3$ ($0 \leq r_3 < r_2$)

  • ……

  • $r_{n-2} = r_{n-1}q_{n-1} + r_n$ ($0 \leq r_n < r_{n-1}$)

  • $r_{n-1} = r_nq_n$

最终在这一连续相除序列中出现余数 0，因为在余数序列 $a = r_0 > r_1 > r_2 > … \geq 0$ 中至多包含 a 项。由引理可推出：

gcd(a, b) = gcd($r_0$, $r_1$) = gcd($r_1$, $r_2$) = … = gcd($r_{n-2}$, $r_{n-1}$) = gcd($r_{n-1}$, $r_{n}$) = gcd($r_n$, 0) = $r_n$

因此，最大公约数是除法序列中最后一个非零余数。

  • 线性同余方程

形如：$ax \equiv b(mod \ m)$，其中 m 为正整数，a 和 b 为整数，而 x 为变量，称为线性同余方程。

如何求解线性同余方程？即如何找出所有满足同余方程的整数解。我们将介绍一种方法，利用使得 $\overline aa \equiv 1(mod \ m)$ 成立的整数 $\overline a$。如果这样的整数存在，我们也称 $\overline a$ 为 a 模 m 的逆。当 a 和 m 互素时，a 模 m 的逆一定存在。

不知各位读者是否发现，线性同余方程组可以用来解决我们熟悉的“中国剩余定理”：有物不知其数，三分之余二，五分之余三，七分之余二，此物为几何？我们可以用线性同余方程来重新表述：$x \equiv 2(mod \ 3)$；$x \equiv 3(mod \ 5)$；$x \equiv 2(mod \ 7)$。

  • 费马小定理

如果 p 为素数，a 时一个不能被 p 整除的整数，则 $a^{p-1} \equiv 1(mod \ p)$。再者，对每一个整数 a 都有：$a^p \equiv a(mod \ p)$

费马小定理告诉我们：如果 $a \in Z_p$，则 $a^{p-1} = 1$ 也在 $Z_p$ 中。

二、密码学

数论在密码学（将信息作转换使得在没有特殊知识的情况下不能很容易恢复出来）中起到关键的作用。

最早使用密码学的人之一是尤利乌斯 · 恺撒。它通过把字母表众多的每个字母正向移动三位来加密消息。用数学表达式表达就是：$f(p) = (p + 3) mod \ 26$ 。当然我们也可以对恺撒密码进行扩展：$f(p) = (p + k) mod \ 26$，此处 k 可被称为密钥。

  • 私钥密码学：

古典密码，包括移位密码和放射密码，都是私钥密码系统的实例。在私钥密码系统中，一旦你知道加密密钥，你就能很快找到解密密钥。当采用私钥密码系统时，通信的双方必须共享一个密钥。由于知道该密钥的仍和人都可以轻易地为消息加密和解密，所以通信地双方就需要安全地交换密钥。

许多现代私钥密码系统却不然。特别是，现在私钥密码学的美国政府标准，高级加密标准（AES），非常复杂并被认为时能很好地抵御密码分析。但是它仍然具有共享安全通信密钥地特性。

  • 公钥密码：

为了避免每对希望安全通信地双方都需要共享密钥，20 世纪 70 年代密码学家引入了公钥密码系统的概念。当使用这种系统的时候，知道怎样发送加密消息的人并不能揭秘消息。在这样的系统中，每个人都可以由一个众所周知的加密密钥，但只有解密密钥时保密的，而且只有消息的预期接收人能解密消息。

  • RSA 密码系统 · 公钥密码系统

为了使用特定的密钥 (n, e) 对消息加密。

  1. 首先将明文消息 M 翻译成整数序列。为此，可以先将每个明文字母翻译成两位数，并将这些两位数连接起来构成字符串。
  2. 接下来，将这个串分成 2N 位数字登场的分组，这里 2N 是一个大偶数使得 2N 位数字的整数不超过 n
  3. 接下来进行加密。加密过程是将每个分组 $m_i$ 转换成密文分组 $c_i$。由函数 $C = M^e \ mod \ n$

当已知解密密钥 d 就是 e 模 (p - 1)(q - 1) 的逆时，就可以很快地对密文解密：$C^d \equiv (M^e)^{d} \equiv M^{de} \equiv M^{1+k(p-1)(q-1)}(mod \ n)$

为什么 RSA 密码系统适合作为公钥密码系统呢？

  1. 公钥构造简单：

    首先，通过需按照两个各有 200 多位地大素数 p 和 q，再寻找一个与 (p - 1)(q - 1) 互素的整数 e，就可以迅速构造一个公钥。

  2. 解密可行：

    当知道模数 n 的因子分解，即知道素数 p 和 q 时，我们可以迅速找到 e 模 (p - 1)(q - 1) 的逆 d。（可以利用欧几里得算法寻找 d 和 (p-1)(q-1) 的贝族系数 s 和 t）

参考书籍：《离散数学及其应用》Kenneth H. Rosen 著