数论与群论密码学-11-$\mathbb{F}_p^\times$ 的生成元

前文所提到的几种离散对数密码系统都需要我们找到一个 \(\mathbb{F}_p^\times\) 的生成元,或者至少一个具有足够高的阶的元素。本章所考虑的就是寻找(或者说是判断)生成元的方法。

随机选取并测试

随机选中生成元的概率

前文给出过,若 \(p\) 是一个素数,则 \(\mathbb{F}_p := \mathbb{Z}/p\mathbb{Z}\) 是一个有 \(p\) 个元素的域(因此 \(\mathbb{F}_p\) 是一个有限域)。另外根据定理 2.3,\(\mathbb{F}_p^\times\) 是一定有生成元的。

因为 \(\mathbb{F}_p^\times\) 是一个阶为 \(p-1\) 的循环群,因此其有 \(\phi(p-1)\) 个生成元。

事实上,上述定理对于任何有限域 \(F\) 都成立:\(F^\times\) 是一个循环群并且有 \(\phi(q-1)\) 个生成元,其中 \(q = \big| F \big|\)\(F\) 中元素的数量。

由于 \(\mathbb{F}_p^\times\)\(\phi(p-1)\) 个生成群,因此对于随机选取的元素 \(a \in \mathbb{F}_p^\times\) 来说其为生成元的概率为

\[ P = \frac{\phi(p-1)}{p-1} = \prod_{q \mid (p-1)} (1 - \frac{1}{q}) \]

因此如果设计时我们应避免选取使得 \(p-1\) 有太多个的素因数 \(q\) 的素数 \(p\)。因为那样的话将有

\[ \prod_{q \mid (p-1)} (1 - \frac{1}{r}) \to 0 \]

特别地,若 \(p = 2q+1\),其中 \(q\) 是素数,那么有前述概率 \(P = \frac{1}{2}(1-\frac{1}{q}) \approx \frac{1}{2}\) 由于这样的素数 \(p\) 对于 SPH 攻击来说是安全的,因此称其为 "safe prime"。另外可以证明,对于这样的 "safe prime" 来说 \(-4\) 总是生成元。

判断元素是否为生成元

那么,给定 \(a \in \mathbb{F}_p^\times\),我们如何判断其是不是生成元?

方法 1

一个很朴素的方法是,对于所有整数 \(n\), \(1 \le n < p-1\),测试是否在 \(\mathbb{F}_p^\times\) 中有 \(a^n \ne 1\)。即使我们利用了 \(a^n = a^{n-1} \cdot a\) 的方式迭代,该方法的时间复杂度也为 \(\Theta(p\log^2p)\),即指数复杂度。

方法 2

更好的方法是,对于所有素数 \(q \mid (p-1)\),测试是否有 \(a^{(p-1)/q} \ne 1\)

\(G = \mathbb{F}_p^\times\) 是一个 \(n\) 阶循环群,那么 \(x \in G\) 是一个生成元,当且仅当 对所有素数 \(q \mid (p-1)\), 皆有 \(x^{n/q} \ne 1\).

(\(\Rightarrow\)) 若 \(x\) 是一个生成元,那么 \(ord(x) = n\)。于是有 \(x^{n/q} \ne 1\).

(\(\Leftarrow\)) 因为对所有素数 \(q \mid (p-1)\), 皆有 \(x^{n/q} \ne 1\), 设 $d = ord(x),那么根据 P3 有 \(d \mid n = dk, k \in \mathbb{Z}\)。假设 \(k \ne 1\),那么 \(\exists q \mid k\) 并且有 \(\frac{n}{q} = d \frac{k}{q}\)。于是 \(x^{n/q} = x^{\frac{dk}{q}} = 1\)。那么则不可能有 \(k \ne 1\)。因此 \(d = 1 \implies x \text{ 是生成元}\)

计算 \(a^{(p-1)/q}\) 的复杂度为 \(\Theta(\log(\frac{p-1}{q}\log^2p)) = \Theta(\log^3p\)。而 \(p-1\) 的素因数的个数 \(\#\{q \mid (p-1)\} \le \log_2p\),由于 \[ p-1 = p_1^{e_1} \cdots p_r^{e_r} \ge p_1 \cdots p_r \ge 2^r \] 其中找到 \(q \mid (p-1)\) 的时间复杂度为 \[ \Theta(f(p-1)) := \Theta(\exp(\sqrt{(1+\epsilon) \log p \log \log p})) \] 因此判断 \(a\) 是否为生成元的复杂度为 \[ \Theta(r(f(p-1)+\log^3p)) \] 注意这是一个次指数复杂度。

另外该方法也可推广用作计算任何元素的阶。

另一种方法

逐次考察 \(2, 3, 5, 6, 7, \cdots\)(略过平方数),并使用 GRH (广义黎曼猜想)测试元素是否为生成元。该方法可在对数时间内找到生成元。