密码学数学基础 笔记 1：从带余除法出发，讨论整除、素因数分解的存在性，以及素数的数量与筛法

整除与素数

这一部分的目标是理解算术基本定理：每个大于 $1$ 的整数都可以分解为素数的乘积，且忽略因子的排列顺序后，分解是唯一的

我们先证明分解的存在性。唯一性的证明需要最大公因数和 Bézout 等式，放到后面讨论

带余除法

整数集合 $\mathbb{Z}$ 对加法、减法和乘法封闭，但两个整数相除，结果未必是整数。因此，在整数范围内讨论除法时，需要同时考虑商和余数

带余除法定理：对任意整数 $a$ 和正整数 $b$，存在唯一的一对整数 $q,r$，使得

$$a=qb+r,\qquad 0\leq r<b$$

其中 $q$ 是商，$r$ 是最小非负余数

存在性与唯一性

取

$$q=\left\lfloor\frac{a}{b}\right\rfloor,\qquad r=a-qb$$

由取整函数的定义，

$$q\leq\frac{a}{b}<q+1$$

两边乘以 $b>0$，就得到 $0\leq r<b$，因此商和余数存在

再证明唯一性。假设

$$a=qb+r=q'b+r',\qquad 0\leq r,r'<b$$

相减得到

$$b(q-q')=r'-r$$

右侧的绝对值小于 $b$，同时又是 $b$ 的倍数，因此只能为 $0$。于是 $r=r'$，进而 $q=q'$

当被除数为负数时，余数仍按同样的范围选取，例如

$$-23=(-6)\times 4+1$$

这里的商是向下取整得到的 $-6$

最小绝对值余数

也可以允许余数为负数，以减小余数的绝对值。例如

$$23=6\times 4-1$$

一种固定的约定是

$$-\frac b2<r\leq\frac b2$$

从普通余数 $r_0\in[0,b)$ 出发：若 $r_0\leq b/2$，保持不变；若 $r_0>b/2$，则将商加 $1$，余数改为 $r_0-b$

这样总有 $|r|\leq b/2$。当 $b$ 为偶数、余数恰好落在边界时，约定保留 $b/2$，排除 $-b/2$，就能保证唯一性

整除

若存在整数 $c$ 使得

$$a=bc$$

则称 $b$ 整除 $a$，记为 $b\mid a$。此时 $b$ 是 $a$ 的因子，$a$ 是 $b$ 的倍数。不整除记为 $b\nmid a$

当 $b>0$ 时，整除等价于带余除法的余数为 $0$

一些基本性质如下，涉及的变量均为整数：

• $1\mid a$、$a\mid a$、$a\mid 0$
• 若 $a\mid b$ 且 $b\mid a$，则 $a=\pm b$
• 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$
• 若 $d\mid a$，则对任意整数 $k$，都有 $d\mid ka$
• 当 $k\neq 0$ 时，$d\mid a$ 等价于 $kd\mid ka$
• 若 $a\neq 0$ 且 $d\mid a$，则 $|d|\leq |a|$

这些性质都可以从 $a=bc$ 的定义直接推出。例如，若 $b=ma$、$c=nb$，则 $c=nma$，所以 $a\mid c$

整数线性组合

后面最常用的性质是：公因子整除任意整数线性组合

若 $d\mid a$、$d\mid b$，则对任意 $u,v\in\mathbb{Z}$，

$$d\mid ua+vb$$

证明很直接：写成 $a=md$、$b=nd$ 后，有

$$ua+vb=(um+vn)d$$

特别地，$d$ 同时整除 $a,b$ 时，也整除 $a+b$ 和 $a-b$。因此，在等式 $a+b=c$ 中，若 $d$ 整除其中任意两项，就一定整除第三项

例如，考虑整数方程

$$7x^2+11=21y$$

如果存在整数解，则 $7$ 整除 $7x^2$ 和 $21y$，于是也应整除两者之差 $11$，产生矛盾。因此方程没有整数解

素数与素因数分解

本文约定 $\mathbb{N}=\{1,2,3,\ldots\}$。正整数分为三类：

• $1$：只有一个正因子
• 素数：大于 $1$，正因子只有 $1$ 和自身
• 合数：存在满足 $1<d<n$ 的因子 $d$

最小非平凡正因子一定是素数

设 $n$ 是合数，$d$ 是它大于 $1$ 的最小正因子

如果 $d$ 也是合数，就存在 $1<e<d$，使得 $e\mid d$。由整除的传递性，$e\mid n$，这与 $d$ 的最小性矛盾。因此 $d$ 必为素数

这里用到了良序原理：任何非空的非负整数集合都有最小元素。它也保证严格递减的正整数序列不可能无限延续

分解的存在性

对任意 $n>1$：

1. 如果 $n$ 是素数，分解已经完成
2. 如果 $n$ 是合数，取其最小非平凡正因子 $p_1$，则 $p_1$ 是素数，可以写成 $n=p_1n_1$，其中 $1<n_1<n$
3. 对 $n_1$ 重复上述过程

每次剩余的正整数都严格减小，所以过程必然终止，最终得到

$$n=p_1p_2\cdots p_s,$$

其中每个 $p_i$ 都是素数。

将相同的素数合并，并按大小排列，可以写成标准分解：

$$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, \qquad p_1<p_2<\cdots<p_k,\quad \alpha_i>0$$

例如

$$10725=3\times 5^2\times 11\times 13$$

至此证明了每个 $n>1$ 都有这样的分解；不同分解过程是否会得到相同的结果，还需要证明唯一性（此处略）

素数有多少个

素数有无穷多个

假设素数只有有限个，分别为 $p_1,\ldots,p_k$，构造

$$N=p_1p_2\cdots p_k+1.$$

因为 $N>1$，由素因数分解的存在性，$N$ 至少有一个素因子 $q$。

但对每个 $p_i$，$N$ 除以 $p_i$ 都余 $1$，因此 $q$ 不在原来的素数列表中，与假设矛盾。

一个粗略的数量估计

记 $p_n$ 为第 $n$ 个素数，$\pi(x)$ 为不超过 $x$ 的素数个数。上面的构造还说明

$$p_{n+1}\leq p_1p_2\cdots p_n+1$$

由此可以归纳得到

$$p_n\leq 2^{2^{n-1}}$$

初始情形 $p_1=2$ 成立。若前 $n$ 项都满足结论，则

$$p_{n+1} \leq 2^{1+2+\cdots+2^{n-1}}+1 =2^{2^n-1}+1 \leq 2^{2^n}$$

对 $x\geq 2$，选择 $n$ 使得 $2^{2^{n-1}}\leq x<2^{2^n}$，就有

$$\pi(x)\geq n>\log_2\log_2 x$$

这个下界很粗，但它把“素数有无穷多个”变成了一个具体的数量估计

更精确的结果是素数定理：

$$\pi(x)\sim\frac{x}{\ln x}, \qquad\text{即}\qquad \lim_{x\to\infty}\frac{\pi(x)}{x/\ln x}=1$$

例如，从 $2$ 到一个很大的整数 $N$ 中均匀抽样，抽到素数的概率约为 $1/\ln N$。如果每次独立抽样，找到素数所需的期望尝试次数约为 $\ln N$；这是平均意义上的估计

试除与埃拉托斯特尼筛法

判断一个数是否为素数，只需尝试不超过 $\sqrt n$ 的素数

如果要一次找出不超过 $N$ 的所有素数，可以使用埃拉托斯特尼筛法：

1. 初始保留 $2,3,\ldots,N$
2. 从小到大取尚未被划去的数 $p$，将 $p^2,p^2+p,\ldots$ 划去
3. 处理到 $p^2>N$ 时停止，剩下的数就是素数

从 $p^2$ 开始，是因为 $2p,3p,\ldots,(p-1)p$ 都有小于 $p$ 的素因子，已经在之前被划去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

from math import isqrt


def primes_up_to(n):
    if n < 2:
        return []

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    for p in range(2, isqrt(n) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False

    return [p for p in range(2, n + 1) if is_prime[p]]

筛法适合批量生成一定范围内的素数。密码学中处理的大整数通常需要更高效的素性测试，例如 Miller–Rabin 等算法，会在后续内容中讨论