数论与群论密码学-18-椭圆曲线素数测试

\(\newcommand{\gcd}{\mathbb{gcd}}\)

本节介绍一种使用椭圆曲线的素性测试。该测试基于以下方法。

Pocklington 素性测试

\(n > 1\) 为一个整数,并且存在整数 \(a, q\) 满足:
1. \(q\) 是素数,且 \(q > \sqrt{n} - 1\), \(q \mid n-1\).
2. \(\gcd(a^{\frac{n-1}{q}} - 1, n) = 1\)\(q^{n-1} \equiv 1 \pmod n\).
那么 \(n\) 为素数

\(n\) 不为素数,那么存在素数 \(p \le \sqrt{n}\), \(p \mid n\).

由于有 \(q > \sqrt{n} - 1\)\(q\) 为素数,那么 \(\gcd(q, p-1) = 1\).

因此根据拓展欧氏算法可知,存在 \(x, y \in \mathbb{Z}\) 使得

\[xq +y(p-1) = 1\]

又因为 \(a^{n-1} \equiv 1 \pmod n\) 我们有

\[ b := a^{\frac{n-1}{q}} \equiv b^{xq}b^{y(p-1)} \equiv a^{(n-1)x}b^{y(p-1)} \equiv b^{y(p-1)} \pmod n \]

然而这是不可能的。

注意:

  1. 使用此方法需要找到满足条件 1 的数 \(q\),包括证明 \(q\) 为素数。然而对于某些素数 \(n\),这样的 \(q\) 并不一定存在。例如对于所有不大于 \(10,000\) 的奇素数来说,其中仅有 \(57.8\%\) 的数有这样的 \(q\).

  2. 若存在满足条件 1 的数,这样的数是唯一的。即若有 \(q_1, q_2\) 满足条件 1,并且不失一般性地假设 \(q_2 > q_1\),那么有 \(q_1q_2 > (\sqrt{n}-1)(\sqrt{n}+1) = n -1\)。然而有 \(q_1q_2 \mid n-1\),因此不可能有 \(q_2 \ne q_1\).

  3. \(n\) 为素数且存在满足条件 1 的 \(q\),那么每一个 \(a \in [1, n)\) 皆满足 \(a^{n-1} \equiv 1 \pmod n\)。因此对于 \(a\) 来说,条件 2 的成立等价于 \(\mathsf{ord}(a) \not\mid \frac{n-1}{q}\)。因此随机选取的数 \(a\) 极有可能可以满足条件 2。特别地,每一个模 \(n\) 的生成元都满足条件 2.

Goldwasser/Kilian 椭圆曲线素性测试

基于与上述 Pocklington 素性测试类似的原理,有 Goldwasser/Kilian 椭圆曲线素性测试如下:

定义如下在 \(\mathbb{Z}/n\mathbb{Z}\) 上的 “椭圆曲线”(因为如果 \(n\) 为素数,则 \(\mathbb{Z}/n\mathbb{Z} = (\mathbb{Z}/n\mathbb{Z})^\times = \mathbb{F}_n\)):

\[ E_n := \{(x, y): y^2 \equiv x^3 + ax + b\} \cup \{P_\infty\} \]

\(n\) 不为素数,则 \(E_n\) 不一定是群。

于是假设 \(n\) 为素数,若有满足以下条件的 \(P = (x, y) \in E_n\)\(m \in \mathbb{N}\), \(q\)
1. \(q\) 是素数且 \(q > (n^\frac{1}{4} + 1)^2\)\(q \mid m\)
2. \(mP = P_\infty\)\(\frac{m}{q}P\) 可计算但是 \(\frac{m}{q}P \ne P_\infty\).
那么 \(n\) 为素数。

\(n\) 不为素数,那么存在素数 \(p \le \sqrt{n}\), \(p \mid n\)

\(\overline{E}/\mathbb{F}_p\) 为由 \(y^2 \equiv x^3 + ax + b \pmod p\) 定义的椭圆曲线,其中 \(\gcd(\Delta_E, n) = 1\).

\(N = \big| \overline{E}(\mathbb{F}_p) \big|\)。根据哈赛定理有 \(N \le p+2+2\sqrt{p} \le (n^\frac{1}{4} + 1)^2 \stackrel{条件 1}{<} q\)。于是 \(N < q\).

由于 \(q\) 为素数且 \(\gcd(N, q) = 1\),那么存在 \(x, y \in \mathbb{Z}\)使得 \(xN + yq = 1\).

\(\overline{P} = P \pmod p\),此时条件 2 表述为

\[ \text{$m\overline{P} = P_\infty$ 且 $\frac{m}{q}\overline{P} \ne P_\infty$} \tag{$2'$} \]

那么因为 \(\overline{E}(\mathbb{F}_p)\) 为群,有 \(N\overline{P} = P_\infty\).

于是 \(\frac{m}{q}\overline{P} = \frac{m}{q}(xN + yq)\overline{P} = \frac{m}{q}x\underbrace{N\overline{P}}_{P_\infty} + y\underbrace{m\overline{P}}_{P_\infty} = P_\infty + P_\infty = P_\infty\),与条件 (\(2'\)) 冲突。

因此 \(n\) 为素数。

于是有 Goldwasser/Kilian 素性测试方法如下:

  1. 随机选择整数 \(a, x_0, y_0 \pmod n\),于是有点 \(P = (x_0, y_0)\) 及过点 \(P\) 的曲线 \(E : y^2 = x^3 + ax + b\),其中 \(b = y_0^2 - (x_0^3 + ax_0)\).

  2. 计算并验证有 \(g := \gcd(\Delta_E, n) = 1\),其中 \(\Delta_E = 4a^3 + 27b^2\)

    \(g = n\),即 \(\Delta_E = n\) 则重新选取曲线与点。

    \(g \ne 1, n\) 则得到一个 \(n\) 的非平凡因数。

以上与 Lenstra 因式分解方法的前半部分一样。

  1. 假设 \(n\) 为素数并使用 SChoof 算法计算 \(m = \#E(\mathbb{F}_n)\)

    若 Schoof 算法失败,则说明可以轻易地找到 \(n\) 的一个因数。

  2. 尝试将 \(m\) 写为 \(m = kq\),其中 \(k \ge 2\) 是一个合适小的数且 \(q\) 可能是个素数,即 \(q\) 可以通过一些合适的素性测试。若无这样的 \(k\)\(q\) 则重新选取点和曲线。

  3. 此时有 \(m = kq\),其中 \(k \ge 2\) 是一个合适小的数且 \(q\) 可能是个素数,且 q > (n^ + 1)$。计算 \(mP\)\(kP\).

    \(mP \ne P_\infty\) 则根据拉格朗日定理有 \(n\) 为合数。

    \(kP = P_\infty\) 则重新选取点和曲线。

  4. 此时有 \(m = kq\), \(mP = P_\infty\), \(kP \ne P_\infty\)。于是有 \(n\) 为素数当 \(q\) 为素数。我们可以用相同的方法证明 \(q_1 := q\) 为素数,该步骤同样需要证明另一个数 \(q_2\) 也为素数。

    由于 \(q_{i+1} \le \frac{q_i - 1}{2}\),我们最多仅需考虑 \(t = \log_2n\) 个这样的数。而若我们能确信其中任何一项 \(p_i\) 为素数,那么必然有 \(q_{i-1}, \cdots, q_1 = q\) 以及 \(n\)为素数。