数论与群论密码学-15-有限域上的椭圆曲线

\[\newcommand{\GF}[1]{\mathbb{F}_{ #1 }}\]

接前文所述,本章讨论当取 \(K = \GF{p}\),其中 \(p\) 为素数且 \(p \ne 2, 3\) 时的椭圆曲线 \(E(\GF{p})\)。其中 \(E: y^2 = f(x)\), \(f(x)\) 是立方的。虽然我们使用 \(\GF{p}\) 来论证,然而不难证明,本章给出的所有事实对于任意的有限域 \(\mathbb{F}_q\),其中 \(q = p^n\) 都成立。注意 \(\GF{q} \ne \mathbb{Z}/p^n\mathbb{Z}\),后者当 \(n > 1\) 时不构成域。

性质

\(\big| E(\GF{p}) \big|\)

依据定义,有 \(E(\GF{p}) \subset \GF{p} \times \GF{p} \cup \{P_\infty\}\)。因此首先有 \(\big| E(\GF{p}) \big| \le p^2 + 1\).

更进一步地,由于有 \(E: y^2 = f(x)\),给定 \(x \in \GF{p}\),记

\(\newcommand{\J}[2]{\left(\frac{ #1 }{ #2 }\right)}\)

\[ \chi_p(x) = L\J{x}{p} \]

其中 \(L\J{\cdot}{\cdot}\) 表示这里使用的是勒让德记号。后文不再强调。有

\[ \#\{y: y^2 = f(x)\} = \begin{cases} 1, &f(x) = 0\\ 2, &f(x) \in (\GF{p}^\times)^2\\ 0, &f(x) \not \in (\GF{p}^\times)^2 \end{cases} = \begin{cases} 1, &\chi_p(f(x)) = 0\\ 2, &\chi_p(f(x)) = 1\\ 0, &\chi_p(f(x)) = -1 \end{cases} \quad\quad = \chi_p(f(x)) + 1 \]

因此有

\[ \#\{(x, y) : y^2 = f(x)\} \ = \sum_{x \in \GF{p}} (\chi_p(f(x)) + 1) \ = p + \sum_{x \in \GF{p}} \chi_p(f(x)) \]

\[ \big| E(\GF{p}) \big| = p + 1 + \sum_{x \in \GF{p}} \chi_p(f(x)) \]

\(N_{E/F} := \big| E(\GF{p}) \big|\), \(a_{E/F} = \sum_{x \in \GF{p}} \chi_p(f(x))\),其中 \(F = \GF{p}\),于是有 \(N_{E/F} = p + 1 - a_{E/F}\).

\(p \mid a_{E/F}\),则称椭圆曲线 \(E/F\) 为超奇异的。

哈赛定理(Hasse's Theorem)

\[ \big| N_{E/F} - (p+1) \big| \le 2 \sqrt{p} \]

\[ \lim_{p \to \infty} N_{E/F} = p + 1 \]

因此有 \(p+1 - 2\sqrt{p} \le N_{E/F} \le p+1 + 2\sqrt{p}\).

\(E(\GF{p})\) 的结构

\(N := N_{E/F}\), \(G := E(\GF{p})\),有

\[ G \stackrel{P3}{=} G[N] \stackrel{\text{property in part d}}{\le} \mathbb{Z}/N\mathbb{Z} \times \mathbb{Z}/N\mathbb{Z} \]

其中 \(\le\) 表示子群。

Type

\(G \le \mathbb{Z}/N\mathbb{Z} \times \mathbb{Z}/N\mathbb{Z}\),则存在整数 \(A, B \ge 1\) 使得 \(B \mid A\)

\[ G \simeq \mathbb{Z}/A\mathbb{Z} \times \mathbb{Z}/B\mathbb{Z} \tag{1} \]

我们称二元组 \((A, B)\)\(G\) 的 Type.

\(G = \GF{p}\) 时,有 \(B \mid p−1\).

接下来我们讨论怎样求 \(G = E(\GF{p})\) 的 type。首先注意到若我们进行素因数分解,记 \(N = \displaystyle \prod_{l \mid N} l^{n_l}\),其中 \(l\) 皆为素数,则有

\[ A = \prod_{l \mid A} l^{\alpha_l} = \prod_{l \mid N} l^{\alpha_l} \\ B = \prod_{l \mid B} l^{\beta_l} = \prod_{l \mid N} l^{\beta_l} \tag{2} \]

其中 \(\alpha_l \ge \beta_l \ge 0\)\(n_l = \alpha_l + \beta_l\).

因为有 \(N \stackrel{\text{式 1}}{=} AB\)\(B \mid A\).

其次注意到式 1 意味着有

\[ G[l^{n_l}] \simeq \mathbb{Z}/l^{\alpha_l}\mathbb{Z} \times \mathbb{Z}/l^{\beta_l}\mathbb{Z} \tag{3} \]

\[ \begin{aligned} G[l^{n_l}] &\stackrel{\text{式 1}}{=} ((\mathbb{Z}/A\mathbb{Z}) \times (\mathbb{Z}/B\mathbb{Z}))[l^{n_l}]\\ &\simeq (\mathbb{Z}/A\mathbb{Z})[l^{n_l}] \times (\mathbb{Z}/B\mathbb{Z})[l^{n_l}]\\ &= (\mathbb{Z}/A\mathbb{Z})[l^{\alpha_l}] \times (\mathbb{Z}/B\mathbb{Z})[l^{\beta_l}]\\ \end{aligned} \]

其中有

\[ gcd(A, l^{n_l}) = l^{\alpha_l}\\ gcd(B, l^{n_l}) = l^{\beta_l}\\ \]

又因为 \(\big| G \big| = n\),于是 \(G[m] = G[gcd(m, n)]\).

可证若 \(H\)\(n\)阶 循环群,且 \(m \mid n\),那么 \(H[m]\)\(m\)阶 循环群,那么 \(H[m] \cong \mathbb{Z}/m\mathbb{Z}\).

于是有 \((\mathbb{Z}/A\mathbb{Z})[l^{\alpha_l}] \cong \mathbb{Z}/l^{\alpha_l}\mathbb{Z} \quad (l^{\alpha_l} \mid A)\).

最后注意到,若式 3 成立,则取 \(k \ge 1\),有

\[ \big| G[l^k] \big| = \begin{cases} l^{2k}, & 1 \le k \le beta_l \\ l^{\beta_l+k}, & \beta_l \le k \le \alpha_l \\ l^{\alpha_l + \beta_l}, & k \ge \alpha_l \end{cases} \tag{4} \]

因此,我们可以通过以下方式求得 \(A\):

对于每个 \(l \mid N\),求 \(\big| G[l^k] \big|\), \(k = 1, \cdots\)。根据式 4 求 \((\alpha_l, \beta_l)\),则可得 \(G\) 的 type / 结构常数 \(\{(\alpha_l, \beta_l)\}_{l \mid N}\)。于是 \(A = \prod l^{\alpha_l}\), \(B = \prod l^{\beta_l}\).

\(E: y^2 = x^3 - x\), \(p = 71\),求 \(E(\GF{p})\) 的结构。

首先计算 \(N = \big| E(\GF{71}) \big|\)。后文记 \(F := \GF{71}\).

\[-a_{E/F} = \Sigma_{x \in \GF{71}}\]

注意到 \(f(-x) = (-x)^3 - (-x) = -f(x)\)。于是有

\[ \J{f(-x)}{p} = \J{-f(x)}{p} = \J{-1}{p}\J{f(x)}{p} \stackrel{71 \bmod 4 = 3}{=} -\J{f(x)}{p} \]

于是

\[ -a_{E/F} = \Sigma_{x \in \GF{71}} \J{f(x)}{p} = \Sigma_{x \in \GF{71}} \J{-f(x)}{p} = -\Sigma\J{f(-x)}{p} \]

因此有 \(a_{E/F} = 0\)。因此 \(N = \big| E(\GF{71}) \big| = 71 + 1 = 72\).

接下来有 \(72 = 2^3 \cdot 3^2\)。于是有

\[ l=2: \quad \alpha_2 + \beta_2 = 3 = n_2, \quad \alpha_2 \ge \beta_2 \ge 0 \quad (\alpha_2, \beta_2) = (3, 0), (2, 1) \\ l=3: \quad \alpha_3 + \beta_3 = 2 = n_3, \quad \alpha_3 \ge \beta_3 \ge 0 \quad (\alpha_3, \beta_3) = (2, 0), (1, 1) \]

对于 \(l = 2\),通过在 \(\GF{71}\) 里解 \(x^3 - x = 0\),有

\[ \begin{aligned} G[2] &= \{(x, 0): f(x) = 0\} \cup \{P_\infty\}\\ &= \{(0, 0), (1, 0), (-1, 0)\} \cup \{P_\infty\} \end{aligned} \]

因此 \(\big| G[2] \big| = 4\).

于是根据式 4,由于 \(\beta_2 \ge 1 = k\),有 \((\alpha_2, \beta_2) = (2, 1)\).

对于 \(l = 3\),我们有取巧的手段。由于有 \(B \mid p-1 = 70 = 2 \cdot 5 \cdot 7\),且 \(3 \mid p-1\),因此必然得有 \(\beta_3 = 0\)\(l^{\beta_l} \mid B \mid p-1\))。于是 \((\alpha_3, \beta_3) = (2, 0)\).

因此,所求结构为 \(\{(2, 1)_2, (2, 0)_3\}\),且

\[ \begin{aligned} A = 2^{\alpha_2} \cdot 3^{\alpha_3} = 2^2 \cdot 3^2 = 36 \\ B = 2^{\beta_2} \cdot 3^{\beta_3} = 2^1 \cdot 3^0 = 2 \end{aligned} \implies \text{$E(\GF{71})$ 的 Type 为 $(36, 2)$} \]

因此 \(E(\GF{71}) \simeq \mathbb{Z}/36\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}\)。由此可知 \(E(\GF{71})\) 中元素阶最高为 \(36\),并且一定存在这样的元素。