数论 素数定理 一个小于任意数 NN 的素数大约有 \displaystyle\frac{N}{\ln N}\displaystyle\frac{N}{\ln N} 个，而且随着 NN 的增大，近似程度越来越好。 贝祖引理 对于任意两个不都为零的整数 aa 和 bb，我们可以找到整数 uu 和 vv，使得 au + bv = 1au + bv = 1 的解的充要条件是 aa 和 bb 互素。 贝祖引理的证明： 我们当然知道，aa 和 bb 只有互素时，才能满足 au+bv=1au+bv=1；否则的

整数 关于整数的严格定义，参见 皮亚诺公理体系 良序性质：每个非空的正整数集合都有一个最小元 定义：如果存在整数 pp 和 q \neq 0q \neq 0，使得 r = p/qr = p/q，则称实数 rr 是 有理数，如果 rr 不是有理数，则称 rr 为 无理数； 定理 1.1：\sqrt{2}\sqrt{2} 是无理数； 证法一：用反证法 假设 \sqrt{2}\sqrt{2} 是有理数，那么存在互素的正整数 a, ba, b 使得 \displaystyle {a \over b}

一点历史 1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字的首字母命名，叫做 RSA 算法。从那时直到现在，RSA 算法一直是最广为使用的 非对称加密算法。毫不夸张地说，只要有计算机网络的地方，就有 RSA 算法。 互质关系 如果两个正整数，除了 11 以外，没有其他公因子，我们就称这两个数是 互质 关系，或者 互素 关系。 关于互质关系，不难得到以下结论: 任意两个质数构成互质关系，比如 1313 和 6161

基础运算 定理一：设 a, b \in \mathbb{Z}a, b \in \mathbb{Z}, n \in \mathbb{N^+}n \in \mathbb{N^+}，则有： (a \cdot b) \bmod n = [(a \bmod n) \cdot b] \bmod n (a \cdot b) \bmod n = [(a \bmod n) \cdot b] \bmod n 证明：设 a \bmod n = da \bmod n = d，则有 a = kn + da = kn + d，

有关 欧几里得算法，参考 辗转相除法 定理 如果 a, b \in \mathbb{N^+}a, b \in \mathbb{N^+}，那么 (a, b) = s_na + t_n b(a, b) = s_na + t_n b 其中，s_n, t_ns_n, t_n 是下面定义的递归序列的第 nn 项 \begin{aligned} s_0 = 1, t_0 = 0, \\ s_1 = 0, t_1 = 1, \\ \end{aligned} \begin{aligned} s_0 = 1, t_0

辗转相除法 又称为 欧几里得算法 一些定义 整除：如果 aa 整除 bb，记为 a\mid ba\mid b，如果 aa 不能整除 bb，记为 a \nmid ba \nmid b 最大公因子：两个不同时为零的整数 a, ba, b 的最大公因子是指能同时整除 a, ba, b 的最大的整数，记为 (a, b)(a, b) 欧几里得算法 定理：整数 a \geqslant b > 0a \geqslant b > 0，令 r_0 = a, r_1 = br_0 = a, r_1 = b，如果我

DSA 的主要参数 全局公开密钥分量 pp：素数，要求 2^{L-1}<p<2^L2^{L-1}<p<2^L，且 LL 为 6464 的倍数 取 p = 127p = 127 qq：(p - 1)(p - 1) 的素因子，2^{159} < q < 2^{160}2^{159} < q < 2^{160}，即比特长度为 160160 位 则 p - 1 = 126 = 2 \times 3^2 \times 7p - 1 = 126 = 2 \times 3^2 \times 7，故取 q =