UpdateTime 2021-10-06

整数 关于整数的严格定义,参见 皮亚诺公理体系 良序性质:每个非空的正整数集合都有一个最小元 定义:如果存在整数 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}

UpdateTime 2021-10-03

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

UpdateTime 2021-10-03

基础运算 定理一:设 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,

UpdateTime 2021-10-03

有关 欧几里得算法,参考 辗转相除法 定理 如果 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

UpdateTime 2021-10-02

辗转相除法 又称为 欧几里得算法 一些定义 整除:如果 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,如果我

UpdateTime 2021-09-21

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 =

UpdateTime 2021-04-28

数论 素数定理 一个小于任意数 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;否则的