Chapter 6 数论和密码学困难性假设¶
1 预备知识和基本群论¶
1. 1 素数与可除性¶
- 令 \(a\) 为整数，\(b\) 为正整数，则存在唯一的整数 \(q, r\) 满足 \(a = qb + r\)，其中 \(0≤r < b\)
- 设 \(a, b\) 为正整数，则存在整数 \(X, Y\) 满足 \(Xa + Yb = \gcd(a,b)\)，且 \(\gcd(a,b)\) 是可用这种方式表示的最小正整数
- 如果 \(c|ab\) 且 \(\gcd(a,c)=1\)，则 \(c|b\)，特别地，如果 \(p\) 为素数且 \(p|ab\)，则可得 \(p|a\)，或 \(p|b\)
证明
由于 \(c | ab\)，对于某些整数 \(\gamma\) 可以写为 \(\gamma c = ab\)
由 \(\gcd(a,c)=1\) 得，存在两个整数 \(X,Y\) 满足 \(1 = Xa + Yc\)
两边同时乘以 \(b\) 得： \(b = Xab + Ycb = X\gamma c + Ycb = c \cdot (X\gamma + Yb)\)
由于 \(X\gamma + Yb\) 是一个整数，可以得到 \(c | b\)
如果 \(p \nmid a\)，则 \(\gcd(a,p)=1\)，由此可以证明命题的第二部分
- 如果 \(p | N\)， \(q | N\)，且 \(\gcd(p,q)=1\)，则 \(pq | N\)
证明
设 \(pa = N,qb = N\)，并且 \(1 = Xp + Yq\)，其中 \(a,b,X,Y\) 都是整数
方程两边同时乘以 \(N\) 得：\(N = XpN + YqN = Xpqb + Yqpa = pq(Xb + Ya)\)，故 \(pq | N\)得证
1. 2 模算术¶
- 对 \(N\) 同余的关系是一个等价关系，具有自反性、对称性和传递性
- 对 \(N\) 的同余关系也服从标准的加、减、乘法算术规则，但不满足除法规则
- 如果给定一个整数 \(b\)，存在一个整数 \(b^{-1}\) 满足 \(bb^{-1}=1\mod N\)，则称 \(b^{-1}\) 为 \(b\) 关于模 \(N\) 的（乘法）逆元，并称 \(b\) 模 \(N\) 可逆
- 如果 \(\beta\) 是 \(b\) 的模 \(N\) 乘法逆元，则 \([\beta\mod N]\) 也是；如果 \(\beta'\) 是 \(b\) 模 \(N\) 的另一个逆元，则有 \([\beta\mod N]=[\beta'\mod N]\)。当 \(b\) 可逆时，可以简单地用 \(b^{-1}\) 表示 \(b\) 在 \(\{1,\cdots,N-1\}\) 范围内的唯一乘法逆元
- 如果 \(ab=cb\mod N\) 并且 \(b\) 可逆，则有 \((ab)\cdot b^{-1}=(cb)\cdot b^{-1}\mod N\implies a=c\mod N\)
- 设 \(a,N\) 为整数， \(N > 1\) ，则当且仅当 \(\gcd(a,N) = 1\) 时 \(a\) 关于模 \(N\) 可逆。
证明
假设 \(a\) 关于模 \(N\) 可逆，用 \(b\) 表示其逆元
注意到 \(0·b = 0 \mod N\) 无论 \(b\) 为何值都成立，所以 \(a ≠ 0\)
由 \(ab = 1 \mod N\) 得对某些 \(c ∈ ℤ\) ，有 \(ab − 1 = cN\) ，相当于 \(ba − cN = 1\)
因为 \(\gcd(a,N)\) 是可以用这种方式表达的最小正整数，而此时并没有比 \(1\) 小的整数，故 \(\gcd(a,N) = 1\) 。
反过来，如果 \(\gcd(a,N) = 1\) ，则存在整数 \(X,Y\) 满足 \(Xa + YN = 1\)，方程两边同时对 \(N\) 取模得到 \(Xa = 1 \mod N\) ，并且发现 \([X \mod N]\) 是 \(a\) 的一个乘法逆元素
1. 3 群¶
- 群是一个集合 \(G\) 和其上的二元运算 \(\circ\)，满足下列条件：
- （Closure:）对任意 \(g,h \in G\)，\(g \circ h \in G\)
- （Existence of an identity:）存在一个单位元 \(e \in G\)，对所有 \(g \in G\)，满足 \(e \circ g = g = g \circ e\)
- （Existence ofinverses:）对任意 \(g \in G\)，存在一个元素 \(h \in G\) 满足 \(g \circ h = e = h \circ g\)，这样的元素 \(h\) 称为 \(g\) 的逆元
- （Commutativity:）对任意的 \(g_1,g_2,g_3 \in G\)，恒有 \((g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3)\)
| 含义 | |
|---|---|
| 有限群 | \(G\) 中元素有限时，用 \(\lvert G \rvert\) 表示群的阶（\(G\) 中元素的个数） |
| 阿尔贝群 | \(G\) 在 \(\circ\) 运算上满足交换律（对任意 \(g,h \in G\)， \(g \circ h = h \circ g\)） |
- 群 \(G\) 中的单位元是唯一的，称为群的单位元，群中的每一个元素有唯一的逆元
- 设 \(\mathbb{G}\) 为群，且 \(a,b,c \in \mathbb{G}\)，如果 \(ac = bc\)，则 \(a = b\)，特别地，如果 \(ac = c\)，则 \(a\) 是 \(\mathbb{G}\) 的单位元。
证明
由于 \(ac = bc\) ，在其两边同时乘以 \(c\) 的唯一逆元 \(c^{-1}\) 可得 \(a = b\)
| 群运算符号 | 加法符号 | 乘法符号 |
|---|---|---|
| 群幂定义 | \(mg = m \cdot g \stackrel{\text{def}}{=} \underbrace{g + \cdots + g}_{m\ \text{times}}\) | \(g^m \stackrel{\text{def}}{=} \underbrace{g \cdots g}_{m\ \text{times}}\) |
- 群幂运算满足普通幂运算的所有性质，即：\(g^m \cdot g^{m'} = g^{m+m'}\)，\((g^m)^{m'} = g^{mm'}\)，\(g^1 = g\)
- 设 \(\mathbb{G}\) 是一个有限群，其阶 \(m = |\mathbb{G}|\)，则对任意元素 \(g \in \mathbb{G}\)，有 \(g^m = 1\)。
证明（只对 \(\mathbb{G}\) 为阿贝尔群的情形进行证明）
因为 \(G\) 是有限群，任取 \(g \in G\)，定义映射 \(f: G \to G,\quad f(x) = gx\)
根据有限群的左乘双射性得 \(\{gg_1, gg_2, \dots, gg_m\}\) 其实就是 \(G\) 的全部元素，由阿贝尔群的交换律得：
故 \(g^m = 1\)
- 令 \(\mathbb{G}\) 是一个有限群，其阶 \(m = |\mathbb{G}| > 1\)。则对任意 \(g \in \mathbb{G}\)及任意整数 \(i\)，可以得出 \(g^i = g^{[i \mod m]}\)
证明
令 \(i = qm + r\)，其中 \(q, r\) 为整数，并且 \(r = [i \mod m]\)，则：
- 令 \(G\) 是一个有限群，\(m = |G| > 1\)，令 \(e > 0\) 是一个整数，并通过 \(f_e(g) = g^e\) 定义函数 \(f_e\)：\(G \to G\)
- 如果 \(\gcd(e,m) = 1\)，则 \(f_e\) 是一个置换（也就是双射）
- 此外，如果 \(d = [e^{-1} \mod m]\)，则 \(f_d\) 是 \(f_e\) 的逆元素
证明
由 \(\gcd(e,m) = 1\) 知 \(e\) 是关于模 \(m\) 的逆元，此时 \(d\) 是 \(e\) 关于模 \(m\) 的乘法逆元
对任意 \(g \in G\)，有 \(f_d(f_e(g)) = f_d(g^e) = (g^e)^d = g^{ed} = g^{[ed \mod m]} = g^1 = g\)
1. 4 \(\mathbb{Z}_N^*\) 群¶
-
\(\mathbb{Z}_N^* \stackrel{\text{def}}{=} \left\{ a \in \{1,\cdots,N - 1\} \mid \gcd(a,N) = 1 \right\}\) 是由集合 \(\{0,\cdots,N - 1\}\) 中与 \(N\) 互素的整数组成的阿尔贝群，群运算为关于模 \(N\) 乘，即：\(ab \stackrel{\text{def}}{=} [ab \mod N]\)
-
定义 \(\phi(N) \stackrel{\text{def}}{=} |\mathbb{Z}_N^*|\) 为群 \(\mathbb{Z}_N^*\) 的阶（\(\phi\) 称为欧拉函数）
- 当 \(N = p\) 是素数时，\(\phi(p) = |\mathbb{Z}_p^*| = p - 1\)
- 当 \(N = pq\) 时，\(\phi(N) = (p - 1)(q - 1)\)
-
设 \(N = \prod_i p_i^{e_i}\)，其中 \(\{p_i\}\) 为互不相同的素数，且 \(e_i \geqslant 1\)，则 \(\phi(N) = \prod_i p_i^{e_i - 1}(p_i - 1)\)
-
任意选取 \(N > 1\)，\(a \in \mathbb{Z}_N^*\)，则
\[ a^{\phi(N)} = 1 \mod N \]对于 \(N = p\) 是素数并且 \(a \in \{0,\cdots,p - 1\}\) 的具体情况，可得
\[ a^{p - 1} = 1 \mod p \] -
选取 \(N > 1\)，对于整数 \(e > 1\)，通过 \(f_e(x) = [x^e \mod N]\) 定义 \(f_e: \mathbb{Z}_N^* \to \mathbb{Z}_N^*\)
- 如果 \(e\) 与 \(\phi(N)\) 互素则 \(f_e\) 是一个置换
- 此外，如果 \(d = [e^{-1} \mod \phi(N)]\)，则 \(f_d\) 是 \(f_e\) 的逆