Part 1 数论和密码学#

整除#

定义#

如果 a 和 b 是整数 且 a ≠ 0, 那么如果存在一个整数 c， 使得 b = ac， 则称 a 整除 b， 记为 $a\ |\ b$

• 当 a 整除 b 时，我们称 a 是 b 的 因数 或 除数，并且称 b 是 a 的 倍数
• 如果 $a\ |\ b$，那么 $\frac{b}{a}$ 是一个整数
• 如果 a 不整除 b，我们记作 $a\ \nmid\ b$

例题#

判断 $3\mid7$ 和 $3\mid12$ 是否成立.

例题解答#

• $3\nmid7$ 因为 $\frac{7}{3}$ 不是整数
• $3\mid12$ 因为 $\frac{12}{3}$ 是整数

定理#

• 线性组合性 如果 $a\mid b$ 且 $a\mid c$，那么 $a\mid (b+c)$.
• 如果 $a\mid b$ ，那么对于所有的整数 c，$a\mid bc$.
• 传递性 如果 $a\mid b$ 并且 $b\mid c$ ，那么 $a\mid c$.
• 大小关系 如果 $a\mid b$ ，$b\neq 0$ ，那么 $\lvert{a}\rvert\leq\lvert{b}\rvert$.

推论#

若 $a, b, c$ 是整数，且 $a\neq 0$ ，且 $a\mid b$ 和 $a\mid c$ ，则对任意整数 $m$ 和 $n$ ，$a\mid (mb + nc)$ .

练习#

证明：如果 $c\mid(a-b)$，$c\mid (a'-b')$ ，那么 $c\mid(aa'-bb')$

除法算法#

当一个整数被一个正整数除时，会得到一个商和一个余数.这通常被称为“除法算法”（Division Algorithm），但实际上它是一个定理.

定义#

如果 $a$ 是一个整数，$b$ 是一个正整数，那么存在唯一的整数 $q$ 和 $r$，使得 $0\leq r< b$，并且 $a = bq+r$.

对于得数，我们有这样的定义：

由于相关的定理证明太过于复杂以及难懂，这里略过了.

同余关系#

定义#

如果 a 和 b 是整数，且 m 是正整数，那么当 m 整除 a-b 时，称 a 与 b 在模 m 下同余.

例题#

判断 17 是否在模 6 意义下与 5 同余，24 和 14 是否在模 6 意义下同余.

解答#

太简单了，略去

定理#

设 m 为正整数.当且仅当存在一个整数 k 使得 $a = b + km$ ，整数 a 和 b 在模 m 下同余

性质#

自反性 任何正整数都和它自身同余 $a\equiv a \pmod{m}$

对称性 $a\equiv b \pmod{m} \Rarr b\equiv a\pmod{m}$

传递性 $a\equiv b \pmod{m},b\equiv c\pmod{m}\Rarr a\equiv c\pmod{m}$

同余式的加和乘#

定理#

设 m 为正整数.如果 $a\equiv b \pmod{m}$ 且 $c\equiv d\pmod{m}$ 则 $a+c\equiv b +d\pmod{m}$ ，$ac\equiv bd \pmod{m}$ 且 $a^k\equiv b^k \pmod{m}$.其中 k 是非负整数.

备注#

这条定理主要强调了同余关系的加法和乘法具有可叠加性.从这个角度想的话这个定理就很自然，所以证明就先略过了.

同余式的代数运算#

• 将有效同余的两边同时乘以一个整数会保持其有效性.

• 将一个整数加到有效同余的两边也会保持其有效性.

• 然而，将同余两边同时除以一个整数并不总能产生有效的同余关系.

计算 mod m 函数的和与积#

定理 设 m 为正整数，a 和 b 为整数.那么

如此便可以将一个数字拆分成它的因数和一部分进行模运算再相加或相乘

二进制模幂算法#

这个算法实际上是借助了上面这个定理进行的.因为任意数的二进制展开是存在且唯一的，所以利用快速幂以及模运算的乘法可拆性就可以将幂次的二进制展开每一位对应的模幂计算出来相乘再取模.

举个例子更加直观一点

例子#

$2^{644} \bmod 645$

解答#

首先，将幂次进行二进制展开

之后对每一个二进制位对应的数字进行计算

这里的power初始值为 2，这么写是为了最后每一行的 a 为 1 时乘以上一行对应的 power 方便

递推关系类似：

if(a[i]) {
    x[i] = x[i-1] * power[i-1];
}
else x[i] = x[i-1];
power[i] = pow(power[i-1],2);

最后的结果就是表格右下角的 x 的值

模 m 算术运算#

定义#

给定 $Z_m$ 是一个包含从 0 到 m-1 的非负整数的集合，即 $\{0,1,...,m-1\}$

• 加法 $+_m$ 被定义为 $a +_m b = (a+b)\bmod m$ 这是模 m 加法

• 乘法 $*_m$ 被定义为 $a*_m b = (a * b) \bmod m$ 这是模 m 乘法

• 进行这些运算被称为模 m 的算术运算

例题#

计算 $7+_119$ 和 $7*_{11} 9$

解答#

利用定义可简单计算.略

性质#

• 封闭性 如果 a 和 b 属于 $Z_m$ ，那么 $a+_mb$ 和 $a*_mb$ 属于 $Z_m$

• 结合律 如果 a, b 和 c 属于 $Z_m$

• 交换律 如果 a 和 b 属于 $Z_m$ ，那么 $a +_m b = b +_m a$ 以及 $a *_m b = b *_m a$

• 单位元 0 和 1 分别是模加法和模乘法的单位元

  • 如果 a 属于 $Z_m$ ，那么 $a +_m 0 = a$ 以及 $a*_m 1 = a$

• 加法逆元 如果 $a \neq 0$ 属于 $Z_m$ ，那么 m - a 是 a 的 模 m 加法逆元.0 是它自身的模 m 加法逆元.

  • $a+_m(m-a) = 0\ \And\ 0 +_m 0 = 0$

• 分配律 如果 a, b 和 c 属于 $Z_m$ 那么

  • $a*_m(b+_mc) = (a*_mb)+_m(a*_mc)$ 以及 $(a+_mb)*_mc = (a*_m c)+_m(b*_mc)$

乘法逆元在模 m 的运算中并不总是存在 例如，2 在模 6 的情况下没有乘法逆元，因为没有整数 x 使得 $2*x\equiv 1\pmod 6$

质数与最大公约数#

定义#

设 p 是大于 1 的正整数，如果 p 的正因子只有 1 和 p ，那么称 p 是质数.否则，称 p 是和数.

例子#

整数 7 是质数，因为他的正因数只有 1 和 7；但 9 是合数，因为它可以被 3 整除

算术基本定理#

定理#

每一个大于 1 的正整数都可以唯一的表示为一个素数，或者表示为两个或更多素数的和层级，其中素因数以非递减序排列.

例子#

• $641 = 641$
• $100 = 2 * 2 * 5 * 5 = 2^2 * 5^2$
• $999 = 3 * 3 * 3 * 37 = 3^3 * 37$
• $1024 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 2^{10}$

试除法#

定理#

如果 a 是合数，则 a 必有小于等于 $\sqrt a$ 的素因子

证明#

$a = b*c$，其中 $1 < b < a, 1 < c < a$ .显然，b 和 c 中必有一个小于等于 $\sqrt{a}$ .否则， $b*c > a$，矛盾.

例子#

判断 157 和 161 是否是素数.

解答#

$\sqrt{157}, \sqrt{161}$ 都小于 13， 小于 13 的素数有 2 3 4 5 11 分别相除查看是不是整除即可，答案略

剩余例子略，比较简单带过了.

埃拉托斯特尼筛法 The Sieve of Erastosthenes#

定理#

每一个大于 1 的正整数都可以唯一地表示为一个素数，或者表示为两个或更多素数的成绩，其中素因数以非递减序排列.

另一种更加形式语言的表述#

设 $a > 1$，则 $a = p_1^{r_1}p_2^{r_2}p_3^{r_3}...p_k^{r_k}$，其中 $p_i$ 是互不相通的素数， $r_i$ 是正整数，而且在不及顺序的情况下，该表示是唯一的.

这个表达式称作 整数 a 的素因子分解

例子#

$7007 = 7^2 * 11 * 13$

推论#

设 $a = p_1^{r_1}p_2^{r_2}p_3^{r_3}...p_k^{r_k}$，其中 $p_i$ 是互不相通的素数，$r_i$ 是正整数，则正整数 d 为 a 的因子的充份必要条件是 $d = p_1^{s_1}p_2^{s_2}...p_k^{s_k}$，其中 $0 \leq s_i \leq r_i, i = 1,2,...,k$

例子 1#

21560 有多少个正因子？

解答 1#

$21560 = 2^3 * 5 * 7^2 * 11$，因此 21560 的正因子的个数为 $4 * 2 * 3 * 2 = 48$.

例子 2#

$10!$ 的二进制表示中从最低为暑期有多少个连续的 0？

解答 2#

故 10! 的二进制表示中从最低位数起有 8 个连续的 0

无穷素数#

定理#

存在无限多个素数.

证明#

假设素数的数量是有限的: $p_i, i = 1,2,...,n$ 令 $q = p_1p_2...p_n + 1$. 对于 q （或者说任意一个数），它是素数或者能用算数基本定理表示. 但是没有任何一个 p 能够整除 q，而 q 又不是素数，矛盾 因此素数有无限个.

素数的函数表示#

梅森素数 定义#

形如 $2^p - 1$，其中 p 是素数，被称为梅森素数

部分非梅森素数 特点#

当 p 是合数时，$2^p - 1$ 一定是合数 相关证明可以将 p 拆开然后进行一个非常常见的因式分解，因为比较简单所以这里先略过了.

素数定理#

不超过 x 的素数个数与 $\frac{x}{lnx}$ 的比率随着 x 的增大而趋近于 1.

由该定理得知，随机选择一个小于 n 的正整数是素数的概率大约是 $\frac{\frac{n}{\ln n}}{n} = \frac{1}{\ln n}$

生成素数#

一般地说，没有一个具有整数稀疏的多项式 f(n) 使得其对所有正整数 n 都为素数.

关于素数的猜想#

哥德巴赫猜想，孪生素数猜想等

最大公约数 GCD#

定义 1#

1. 设 a 和 b 为整数，且不全为零.嫩狗同时整除 a 和 b 的最大整数 d 称为 a 和 b 的最大公约数，记作 gcd(a,b)

2. 如果两个整数 a 和 b 的最大公约数为 1，则称 a 和 b 是互素的

3. 整数 $a_i, i = 1,2,...,n$ 是两两互素的，如果当 $1 \leq i < j \leq n$ 时有 $gcd(a_i,a_j) = 1$

例子#

1. gcd(24,36) = 12

2. 17 与 22 互素

用素因子分解式找最大公约数#

假设 a 和 b 的素因数分解式

其中每个质数都是非负整数，且两个素因数分解式中出现的所有素数都包含在两者中，那么：

这个公式右边的整数可以同时整除 a 和 b，并且没有比它更大的整数能够同时整除 a 和 b.但是这个算法并不高效

最小公倍数 LCM#

定义#

正整数 a 和 b 的最小公倍数是同时被 a 和 b 整除的最小正整数，记作 lcm(a,b)

最小公倍数也可以通过素因数分解来计算

这个数字可以被 a 和 b 同时整除，并且没有更小的数字可以同时被 a 和 b 整除

定理#

a, b 为正整数，那么 ab = gcd(a,b) * lcm(a,b)

欧几里得算法 Euclidean Algorithm#

算法过程#

procedure gcd(a,b: positive integers)
x:=a y:=b
while y != 0
	r:= x mod y
	x:= y
	y:= r
return x{gcd(a,b) is x}

证明#

假设 a 和 b 是正整数 且 a ≥ b. 设 $r_0 = a, r_1 = b$.通过连续应用除法算法啊，我们得到如下结果：

最终，余数为零会出现在序列中： $a = r_0 > r_1 > r_2 > ... \geq 0$.这个序列中最多不能包含超过 a 项 根据引理 1 可证.

最大公约数表示成一个线性组合#

如果 a 和 b 是任意整数，且不全为 0,那么 gcd(a,b) 是集合 $\{ax+by: x,y\in \Z \}$ 中的最小正整数元素.

证明#

设 s 是 a 和 b 的最小线性组合.

设 q 是 a 除以 s 的商.那么 $a \bmod s = a - qs = - q (ax+by) = a(1-qx) + b(-qy)$

因此，a mod s 是 a 和 b 的线性组合.

由于 s 是所有线性组合中的最小整数，并且 a ≤ a mod s < s,

a mod s 不能是正数，因此 a mod s = 0.

这意味着 s 是 a 的因子，同样 s 也是 b 的因子.因此 s 是 a 和 b 的公约数，gcd(a,b) ≥ s.

由于 gcd(a,b) 同时整除 a 和 b，且 s 是 a 和 b 的线性组合，我们有 gcd(a,b) | s. 但是 gcd(a,b) | s 并且 s > 0 意味着 gcd(a,b) ≤ s.

推论#

对于整数 a 和 b，如果 d | a 并且 d | b，那么 d | gcd(a,b).

贝祖定理 Bézout’s Theorem#

定理#

如果 a 和 b 是正整数，那么存在整数 s 和 t 使得 gcd(a,b) = sa + tb. 这里的整数 s 和 t 被称为贝祖系数.

根据贝祖定理，整数 a 和 b 的最大公约数可以表示为 sa + tb，其中 s 和 t 是整数. 这是 a 和 b 的一个线性组合，其系数为整数.

• gcd(6,14) = (-2) * 6 + 1 * 14

例子 - 求贝祖系数#

将 gcd(252,198) = 18 表示为 252 和 198 的线性组合.

首先使用欧几里得算法证明 gcd(252,198) = 18

1. 252 = 1 * 198 + 54

2. 198 = 3 * 54 + 36

3. 54 = 1 * 36 + 18

4. 36 = 2 * 18

• 现在从上面第 3 个式子和第 1 个式子反向推导

  • 18 = 54 - 1 * 36

  • 36 = 198 - 3 * 54

• 将第 2 个方程带入第 1 个方程中

  • 18 = 54 - 1 * (198 - 3 * 54) = 4 * 54 - 1 * 198

• 接着将 54 = 252 - 1 * 198 代入上式：

  • 18 = 4 * 252 - 5 * 198

这个方法展示了“两步法”，先使用欧几里得算法找到最大公约数，然后通 过回代的方式将最大公约数表示为原始两个整数的线性组合.

扩展欧几里得算法#

还有一种称为扩展欧几里得算法的“单步法”，可以在进行欧几里得算法的同时贝祖系数，将最大公约数直接表示为线性组合.

算法过程#

简单地说，这个算法的过程就是在使用原数字对进行欧几里得算法结束后又代入了两个自己假设的数组，这个数组开头被设计为 0 和 1,接着将这两个系数数组像原先的数字一样进行欧几里得算法，最后算出来的就是一个贝祖系数对.

首先，进行一个完整的欧几里得算法：

之后定义两个数列 s 和 t.它们有以下的属性：

则因为 $as_n + bt_n = r_n = gcd(a,b)$

所以 s 和 t 就是 a 和 b 的贝祖系数.

例子#

将 gcd(100,35) 表示为 100 和 35 的线性组合.

由 $r_0 = 100, r_1 = 35$ 可进行欧几里得算法：

• 100 = 35 * 2 + 30

• 35 = 30 * 1 + 5

• 30 = 5 * 6

接着构建 s 和 t 数列，有如下过程：

计算有 $s_3 = -1, t_3 = 3$

则

将同余式两边同时除去整数#

将有效同余式的两边同时除以一个整数，并不总是能得到一个有效的同余式。

但如果这个整数与模数互素，则可以得到一个有效的同余式:

定理#

设 m 为正整数，a, b 和 c 为整数. 如果 $ac \equiv bc \pmod{m}$ 并且 gcd(c,m) = 1,那么 $a \equiv b \pmod{m}$

证明#

因为

那么

又由于 gcd(c,m) = 1, 所以 m | a - b.

因此：

定理得证.