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.

因此：

定理得证.

算术基本定理的唯一性证明#

引理#

1. 如果 $a, b, c$ 为正整数，$\gcd(a,b)=1$ 且 $a \mid bc$，则 $a \mid c$.
2. 如果素数 $p \mid a_1a_2\cdots a_n$，则对于某个 $i$，有 $p \mid a_i$.

证明思路（反证法）#

假设存在两种不同的素因数分解。 $n = p_1p_2\cdots p_s = q_1q_2\cdots q_t$ 其中 $p_i$ and $q_j$ 均为素数且非降序排列。 消去公共因子后，利用引理 2 可导出矛盾（左边素数整除右边，但右边是不含左边素数的乘积），从而得证唯一性。

线性同余方程 (Linear Congruences)#

定义#

形如 $ax \equiv b \pmod m$ 的同余式，其中 $m$ 为正整数，$a, b$ 是整数，$x$ 是变量，称为线性同余式。

逆元 (Inverse)#

如果整数 $\bar{a}$ 满足 $\bar{a}a \equiv 1 \pmod m$，称 $\bar{a}$ 为 $a$ 的模 $m$ 的逆元。

定理：如果 $a$ 和 $m$ 互素（$\gcd(a,m)=1$）且 $m>1$，那么 $a$ 在模 $m$ 下有逆元，且该逆元在模 $m$ 下是唯一的。

求解逆元#

利用扩展欧几里得算法求出贝祖系数 $s, t$ 使得 $sa + tm = 1$。 则 $sa + tm \equiv 1 \pmod m \Rightarrow sa \equiv 1 \pmod m$。 因此，$s$ 即为 $a$ 的逆元。

例子：求 101 在模 4620 下的逆元。

1. 使用欧几里得算法确认 $\gcd(101, 4620)=1$。
2. 回代求贝祖系数，得到 $1 = -35 \cdot 4620 + 1601 \cdot 101$。
3. 逆元为 1601。

用逆元求解线性同余式#

求解 $ax \equiv b \pmod m$。

1. 求出 $a$ 的逆元 $\bar{a}$。
2. 方程两边同时乘以 $\bar{a}$： $\bar{a}ax \equiv \bar{a}b \pmod m \Rightarrow x \equiv \bar{a}b \pmod m$

中国剩余定理 (Chinese Remainder Theorem)#

问题背景#

“有物不知其数，三分之余二，五分之余三，七分之余二，此物几何？” 即求解方程组：

定理#

设 $m_1, m_2, \dots, m_n$ 是两两互素的大于 1 的正整数，则对任意整数 $a_1, a_2, \dots, a_n$，同余方程组：

在模 $m = m_1m_2\cdots m_n$ 下有唯一解。

构造解法#

1. 令 $m = m_1m_2\cdots m_n$。
2. 令 $M_k = m / m_k$。
3. 求 $y_k$，使得 $M_k y_k \equiv 1 \pmod {m_k}$（即 $y_k$ 是 $M_k$ 模 $m_k$ 的逆元）。
4. 通解为： $x = \sum_{k=1}^{n} a_k M_k y_k \pmod m$

例子#

求解孙子算经问题：

• $m = 3 \times 5 \times 7 = 105$
• $M_1=35, M_2=21, M_3=15$
• 逆元：$y_1=2, y_2=1, y_3=1$
• $x = 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 = 140 + 63 + 30 = 233$
• $233 \equiv 23 \pmod {105}$。最小正整数解为 23。

反向替换法 (Back Substitution)#

另一种求解方法。将第一个同余式写成 $x = m_1t + a_1$，代入第二个同余式求解 $t$，依此类推。

数论重要定理#

威尔逊定理 (Wilson’s Theorem)#

$p$ 是素数当且仅当 $(p-1)! \equiv -1 \pmod p$。

欧拉定理与欧拉函数#

欧拉函数 $\phi(n)$：小于 $n$ 且与 $n$ 互素的正整数的个数。

• 若 $p$ 是素数，$\phi(p) = p-1$。
• 若 $n = pq$ 且 $p, q$ 互素，$\phi(n) = (p-1)(q-1)$。

欧拉定理：如果 $\gcd(a,n)=1$，则 $a^{\phi(n)} \equiv 1 \pmod n$。

推论：用于简化幂运算。 若 $\gcd(a,n)=1$，则 $a^x \equiv a^{x \bmod \phi(n)} \pmod n$。

费马小定理 (Fermat’s Little Theorem)#

如果 $p$ 是素数且 $p \nmid a$，则： $a^{p-1} \equiv 1 \pmod p$ 或者对于任意整数 $a$： $a^p \equiv a \pmod p$

应用：计算大次幂的模。例如 $7^{222} \bmod 11$。

伪素数与原根#

伪素数 (Pseudoprimes)#

如果 $n$ 是合数，但满足 $b^{n-1} \equiv 1 \pmod n$，则称 $n$ 为以 $b$ 为基数的伪素数。

卡米切尔数 (Carmichael Numbers)：一个合数 $n$，如果对所有满足 $\gcd(b,n)=1$ 的正整数 $b$ 都满足 $b^{n-1} \equiv 1 \pmod n$，则称 $n$ 为卡米切尔数（如 561）。

原根 (Primitive Roots)#

模素数 $p$ 的原根是 $\mathbb{Z}_p$ 中的整数 $r$，使得 $\mathbb{Z}_p$ 中的每一个非零元素都是 $r$ 的某个幂次。 即 $r^1, r^2, \dots, r^{p-1} \bmod p$ 生成了 $1$ 到 $p-1$ 的所有整数。

离散对数 (Discrete Logarithms)#

设 $g$ 是模 $p$ 的原根。如果 $g^x \equiv a \pmod p$，则称 $x$ 为以 $g$ 为底 $a$ 模 $p$ 的离散对数。 记作 $\log_g a = x$。 注意：计算离散对数在计算上是非常困难的（Discrete Logarithm Problem），这是许多密码学算法的基础。

同余式的应用#

哈希函数 (Hashing Functions)#

常用函数：$h(k) = k \bmod m$。

• 冲突解决：线性探测 $h(k, i) = (h(k) + i) \bmod m$。

伪随机数 (Pseudorandom Numbers)#

线性同余法： $x_{n+1} = (ax_n + c) \bmod m$ 需要选择合适的模数 $m$、乘数 $a$、增量 $c$ 和种子 $x_0$。

校验位 (Check Digits)#

• UPC (通用产品代码)：12位，利用模 10 同余检测错误。 $3x_1 + x_2 + 3x_3 + \dots + x_{12} \equiv 0 \pmod{10}$
• ISBN-10：利用模 11 同余。 $\sum_{i=1}^{10} ix_i \equiv 0 \pmod{11}$ (其中 X 代表 10)。

密码学 (Cryptography)#

古典密码#

1. 凯撒密码 (Caesar Cipher)：移位 $k=3$。 加密：$f(p) = (p+3) \bmod 26$。
2. 移位密码 (Shift Cipher)：任意 $k$。 加密：$f(p) = (p+k) \bmod 26$。 解密：$f^{-1}(p) = (p-k) \bmod 26$。
3. 仿射密码 (Affine Cipher)： 加密：$f(p) = (ap+b) \bmod 26$，其中 $\gcd(a, 26)=1$。
4. 分组密码 (Block Cipher)： 将字符分组，通过置换映射到另一组字符。例如换位密码。

密码系统 (Cryptosystems)#

五元组 $(P, C, K, E, D)$：明文、密文、密钥空间、加密函数集、解密函数集。

公钥密码学 (Public Key Cryptography)#

• 私钥密码：双方共享同一个密钥（对称）。
• 公钥密码：每个人有一对密钥（公钥加密，私钥解密）。解决了密钥分发问题。

RSA 密码系统#

最常用的公钥密码系统，基于大整数分解的困难性。

算法过程#

1. 密钥生成：

   • 选择两个大素数 $p, q$。
   • 计算 $n = pq$ 和 $\phi(n) = (p-1)(q-1)$。
   • 选择整数 $e$，使得 $\gcd(e, \phi(n)) = 1$。
   • 计算 $d$，使得 $de \equiv 1 \pmod{\phi(n)}$（即 $d$ 是 $e$ 的逆元）。
   • 公钥：$(n, e)$。私钥：$d$。

2. 加密： 将明文 $M$ 转换为整数（分组），计算密文 $C$： $C = M^e \bmod n$

3. 解密： 利用私钥 $d$ 恢复明文 $M$： $M = C^d \bmod n$

正确性#

基于 $M^{ed} \equiv M \pmod n$（欧拉定理推论）。

加密协议#

迪菲-赫尔曼密钥交换 (Diffie-Hellman Key Exchange)#

允许双方在不安全信道上协商共享密钥。基于离散对数难题。

1. 公开参数：大素数 $p$ 和原根 $g$。
2. Alice 选私钥 $a$，发送 $A = g^a \bmod p$。
3. Bob 选私钥 $b$，发送 $B = g^b \bmod p$。
4. 双方计算共享密钥：$K = B^a \bmod p = (g^b)^a = g^{ab} \bmod p = A^b \bmod p$。

数字签名 (Digital Signatures)#

用于验证消息来源和完整性。

• 发送方用私钥对消息（或其哈希）进行“解密”操作：$S = M^d \bmod n$。
• 接收方用发送方的公钥进行“加密”操作验证：$M' = S^e \bmod n$。若 $M'=M$，则签名有效。

同态加密 (Homomorphic Encryption)#

允许在密文上直接进行计算。RSA 具有乘法同态特性： $E(m_1) \cdot E(m_2) \equiv m_1^e \cdot m_2^e \equiv (m_1m_2)^e \equiv E(m_1m_2) \pmod n$

零知识证明 (Zero Knowledge Proof)#

证明者向验证者证明某个命题为真，而不泄露任何额外信息。

• 属性：完备性、可靠性、零知识。
• 例子：Schnorr 协议（证明知道离散对数而不泄露该数值）。

处理大整数#

余数系统 (Residue Number System, RNS)#

利用中国剩余定理，将大整数表示为一组较小模数的余数元组。

• $x = (x_1, x_2, \dots, x_k)$，其中 $x_i = x \bmod P_i$，$P_i$ 两两互质。
• 优点：加法和乘法可以并行地在每个分量上独立进行，大大提高了计算大整数运算的效率。
• $x+y \leftrightarrow (x_1+y_1, \dots, x_k+y_k)$
• $x\cdot y \leftrightarrow (x_1\cdot y_1, \dots, x_k\cdot y_k)$