数论与群论密码学-17-椭圆曲线素因子分解

\(\newcommand{\gcd}{\mathsf{gcd}}\) \(\newcommand{\den}{\mathsf{den}}\)

除了构造密码系统,椭圆曲线还带来了新的素因子分解和素数判定的手段。本节及下一节分别讨论这两个话题。

Pollard 的 \(\rho -1\) 方法

若已知 \(n\) 是合数,若欲找到 \(n\) 的一个非平凡因数:
1. 取数 \(B\)
2. 取数 \(k\) 为尽可能多的小于 \(B\) 的数的积。理想地取 \(k = B!\)
3. 随机选择 \(a\) 使得 \(2 \le a \le n-2\)
3. 使用模幂算法计算 \(r = \mathsf{rem}(a^k, n)\)
4. 使用欧氏算法计算 \(d = (r-1, n)\)
5. 若有 \(d = 1\)\(d = n\) 则重新选取 \(a\)\(k\)。否则有 \(d \mid n\)\(d\)\(n\) 的一个不大于 \(B\) 的非平凡因数,我们称 \(d\)\(B\)-smooth 的。

\(d\)\(\frac{n}{d}\) 上重复该算法可得 \(n\) 的素因子分解。

在有些情况下,例如 \(n = 491,389 = 383 \times 1283\) 时,由于 \(n\) 的最小非平凡素因数为 \(383\),由于 \(383 - 1 = 2 \times 191\),因此一开始我们必须取 \(B \ge 191\) 才有可能得到一个非平凡的 \(d\)。然而这样一来 \(k\) 必须是一个非常大的数,从而使得在这些情况下该方法并不切实际。

变种

我们给出 Pollard 的 \(\rho -1\) 方法的一个变种。

取两数满足 \(B \le C\),计算 \(k_{B, C} = \displaystyle \prod_{l \le B} l^{\lfloor \frac{\log(C)}{\log(l)} \rfloor}\)

于是 \(k_{B, C}\) 满足:

\[ l^v \mid k_{B, C} \iff \text{$l \le B$ 且 $l^v \le C$} \tag{1} \]

注意, \(k_B := k_{B, B} = \mathsf{lam}\{n : n \le B\}\).

我们断言,对于满足 \(p \mid n\) 的素数 \(p\),有

\[ l^v \mid p-1 \implies \text{$l \le B$ 且 $l^v \le C$} \tag{$\star$} \]

因此对于任何互质与 \(n\) 的数 \(a\)\((a, n) = 1\)) 来说,记 \(k = k_{B,C}\),都有

\[ a^k \equiv q \pmod p \tag{2} \]

因此有 \(p \mid (a^{k-1}, n) = d\).

根据式 (\(\star\)) 与式 (1),有 \(l^v \mid p-1 \implies l^v \mid k_{B, C} \implies p-1 \mid k_{B, C}\)。于是根据费马定理有式 (2) 成立。

Lenstra 方法

基于 Pollard 的 \(\rho -1\) 方法的原理,Lenstra 将 \((\mathbb{Z}/p\mathbb{Z})^\times = \mathbb{F}_p^\times\) 替换为 \(E(\mathbb{F}_p)\) 得到一条合适的椭圆曲线 \(E/\mathbb{Q}\)

由于我们要求 \(p \ge 5\),首先验证有 \((n, 6) = 1\),否则可得 \(n\) 的一个因子。另外,验证不存在任何 \(r \ge 2\) 使得 \(n \ne m^r\)

接下来选定参数 \(B\), \(C\),计算

\[ k = \prod_{q \le B\\\text{$q$ 为素数}} q^{\lfloor \frac{\log C}{\log q} \rfloor} \]

随机选择 \(a, x_0, y_0 \in [0, n-1]\),因此有点 \(P = (x_0, y_0)\)

计算 \(b = y_0^2 - (x_0^3 + ax_0)\) 并得过点 \(P\) 的曲线

\[ E : y^2 = x^3 + ax + b \]

\(\Delta_E = 4a^3 + 27b^2\) 并验证有 \(g := \gcd(\Delta_E, n) = 1\)
\(g = n\),即 \(\Delta_E = n\) 则重新选取曲线与点。
\(g \ne 1, n\) 则得到一个 \(n\) 的非平凡因数。

否则有 \(g = 1\)。此时通过后述方法选择序列 \(k_1, \cdots k_r = k\),并对 \(1 \le 1 \le k\) 逐项求

\[ P_j = k_jP = (\frac{x_j}{z_j}, \frac{y_j}{z_j}) \in E(\mathbb{Q}) \]

其中 \(x_j, y_j, z_j\) 约至最简,即 \(\gcd(x_j, y_j, z_j) = 1\).

\(d_j := \gcd(z_j, n)\)
\(d_j = n\),则重新选取曲线与点。
\(d_j \ne 1, n\),则得到一个 \(n\) 的非平凡因数。

否则存在 \(\overline{x}_j \equiv \frac{x_j}{z_j} \pmod n\)\(\overline{y}_j \equiv \frac{y_j}{z_j} \pmod n\)。于是有

\[ \overline{P}_j = (\overline{x}_j, \overline{y}_j) \equiv k_jP \pmod n \]

可以直接从 \(\overline{P}_{j-1}\) 中计算得到。

选取序列的方法

方法 1 (cf. Silverman/Tate)

二进制展开 \(k\):

\[ 2^r + 2^{r-1}c_1 + \cdots + 2c_{r-1} + c_r \]

其中 \(c_i \in \{0, 1\}\)

\(k_0 = 1\), \(k_j = 2k_{j-1} + c_j\)

方法 2 (cf. Koblitz)

\(q_1 = 2, q_2 = 3, \cdots, q_r\) 为不大于 \(B\) 的素数。取

\[ k_0 = 1\\ k_{j+1} = q_i k_j \]

其中 \(A_{i-1} \le j < A_i\), \(1 \le i \le r\), \(A_0 = 1\), \(A_i = \alpha_{q_1}\cdots\alpha_{q_i}\)。因此该序列形如:

\[ 1, 2, 2^2, \cdots, \\ 2^{\alpha_2}, 3(2^{\alpha_2}), 3^2(2^{\alpha_2}), \cdots, \\ 3^{\alpha_3}2^{\alpha_2}, \cdots \\ k \]

Lenstra 方法的正确性

首先,类似于 Pollard 的方法,我们有如下事实:

若有 \(p\) 为素数且 \(p \mid n\),而 \(E/\mathbb{F}_p\) 是一条满足如下条件的椭圆曲线:

\[ \begin{aligned} l^v \mid \#E(\mathbb{F}_p) &\implies \text{$l \le B$ 且 $l^v \le C$} \\ &\stackrel{\text{式 (1)}}{\iff} l^v \mid k_{B,C} \end{aligned} \tag{\star\star} \]

那么对于每一个点 \(P \in E(\mathbb{F}_p)\) 皆有

\[ k_{B, C}P = P_\infty \tag{3} \]

根据式 (\(\star\star\)) 及式 (1) 我们有 \(\#(E(\mathbb{F}_p)) \mid k_{B, C}\).

根据 P3 有 \(ord(P) \mid \#(E(\mathbb{F}_p)) \mid k_{B, C}\).

根据 P1 有 \(k_{B, C}P = P_\infty\).

另外有如下事实:

\(p\) 为素数,设

\[ \begin{aligned} R_p &= \{x \in \mathbb{Q} : \den(x) \not\equiv 0 \pmod p\}\\ &= \{\frac{a}{b} \in \mathbb{Q} : p \not\mid b\} \end{aligned} \]

\(R_p\)\(\mathbb{Q}\) 的子环。

于是映射 \(x \to x \pmod p\) 定义了如下环同构:

\[ r_p : R_p \to \mathbb{F}_p \]

更多地,若 \(E/\mathbb{Q}\) 是一条由 \(y^2 = f(x), f(x) \in \mathbb{Z}[x]\) 定义的椭圆曲线(注意有 \(f(x)\) 的系数皆为整数),于是若有素数 \(p\), \(p \not\mid \Delta_E\),那么

\[ r_{E, p}((x, y)) = \begin{cases} (r_p(x), r_p(y)), &\text{若 $p \not\mid \den(x)$}\\ P_\infty, &\text{否则} \end{cases} \]

定义了如下群同态:

\[ r_{E, p} : E(\mathbb{Q}) \to \overline{E}(\mathbb{F}_p) \]

其中 \(\overline{E}/\mathbb{F}_p\) 是由 \(y^2 \equiv f(x) \pmod p\) 定义的椭圆曲线。

该事实证明中的难点在于证明 \(r_{E, p}\) 是同态: \(r_{E, p}(P + Q) = r_{E, p}(P) + r_{E, p}(Q)\)

\(P \in E(\mathbb{Q})\) 有无穷阶,且存在数 \(k > 0\) 使得

\[ kr_{E, p}(P) = P_\infty \]

那么有 \(p \mid \den(x)\),其中 \((x, y) = kP\).

\(kr_{E, p}(P) = P_\infty\),那么 \(r_{E, p}(kP) \stackrel{\text{同态}}{=} kr_{E, p}(P) = P_\infty\)。于是根据 \(r_{E, p}\) 的定义有 \(p \mid \den(x)\).

于是若有素数 \(p\), \(p \mid n\),且式 (\(\star\star\)) 对于 \(E/\mathbb{F}_p\) 成立(根据哈赛定理若有 \(B > p+1+2\sqrt{p} \iff B > (\sqrt{p}+1)^2 \iff \sqrt{B} > \sqrt{p}+1\)),那么有 \(p \mid \gcd(\den(\underbrace{x(k_{B, C}P)}_{\text{点 $k_{B, C}P$ 的 x坐标}}), n)\).