数论与群论密码学-19-Schoof 算法

本节讨论前文使用到的 Schoof 算法。

考虑 \(E/\mathbb{F}_q\),其中 \(q = p^r\), \(p\) 为素数。 Schoof 算法用于计算 \(N_{E/\mathbb{F}_q} = \big| E(\mathbb{F}_q) \big|\)

如前文所述,记 \(a_{E/\mathbb{F}_q} = -N_{E/\mathbb{F}_q} + (q+1)\),有 \(\big| a_{E/\mathbb{F}_q} \big| \le 2\sqrt{q}\).

Schoof 算法将计算化简为:

  1. 依据哈赛定理,仅需计算 \(a_{E/\mathbb{F}_q} \bmod n\),对于任何 \(n > 4\sqrt{q}\).

  2. 依据 CRT,仅需计算 \(a_{E/\mathbb{F}_q} \bmod l\),对于所有小于某数 \(B\) 的素数 \(l\)。其中有 \(B\) 满足 \(\displaystyle \prod_{l \le B} l > 4\sqrt{q}\)。于是有 \(B = \Theta(\log q)\).

    例如:
    对于 \(q \le 10^8\),取 \(B = 11\).
    对于 \(q \le 2^{134}\),取 \(B = 59\).

\(\overline{\mathbb{F}}_q\)\(\mathbb{F}_q\) 的代数封闭,于是映射 \(\phi : x \mapsto x^q\)\(\overline{\mathbb{F}}_q\) 上的自同构,有 \(\phi(x) = x \iff x \in \mathbb{F}_q\).

\(E(\overline{\mathbb{F}}_q)[l] = \{P \in E(\overline{\mathbb{F}}_q) : lP = P_\infty\}\),有 \(E(\overline{\mathbb{F}}_q)[l] \simeq \mathbb{Z}/l\mathbb{Z} \times \mathbb{Z}/l\mathbb{Z}\)\(\mathbb{F}_l\) 上的二维向量集合。

于是弗罗贝尼乌斯映射(Frobenius) \(\phi_l((x, y)) = (x^l, y^l)\)\(E(\overline{\mathbb{F}}_q)\) 上的一个 \(\mathbb{F}_l\)-线性 映射。其特征多项式为

\[ \mathsf{ch}_{\phi_l}(t) = t^2 - a_{E/\mathbb{F}_q} + q \in \mathbb{F}_l[t] \]

根据 Cayley-Hamiton 定理有 \(\phi_l^2 - q\mathsf{Id}_l = t\phi_l\) 对于任何 \(t = a_E \pmod l\) 成立。其中 \(\mathsf{Id}_l\)\(\mathbb{F}_l\) 中的单位函数。

于是有 Schoof 算法如下:

逐项测试 \(t = 0, 1, \cdots, l-1\) 直到有一项 \(t\) 满足

\[ \phi_l^2 -q\mathsf{Id}_l = t\phi_l \quad \text{在 $E[l]$ 中} \tag{1} \]

测试条件 1 成立需要用到以下事实:

对于每一个奇数 \(n\),皆存在 \((n^2 - 1)/2\) 次多项式 \(\psi_n(X) \in \mathbb{F}_q[X]\) 使得

\[ (x, y) \in E[n] \iff \psi_n(x) = 0 \]

该多项式被称为 \(E\)\(n\)-次 除法多项式,其可通过递归的方法计算。

然而 \(\psi_l\) 的次随 \(l\) 二次增长。例如,若 \(q = 10^{200} \approx 2^{650}\),那么需要 \(l \approx 250\)。如此一来有 \(\mathsf{deg}(\phi_l) \approx 250^2/2 = 31,250\).

有 Elkies 和 Atkins 对 Schoof 算法的改进版本避免了使用除法多项式。他们的方法中使用的多项式的次数大约等于 \(l\).