数论与群论密码学-12-素数测试

如前文所述,我们用到的许多公钥密码系统都需要我们找到大素数。而我们现在仅有的方法是反复随机生成足够大的数,并测试其是否是素数。因此我们实际上需要的是一个高效判定素数的方法。事实上,与其说我们将要给出的算法判断的是数的素性,倒不如说他们判断的是数的“合性”:因为他们都是基于通过找出待测数的非平凡因子(1 及其自身)证明其非素数的。

虽然在 2002 年提出了存在多项式时间可算的素数判定算法,然而该算法实际上十分复杂而且非常低效。

后文我们假设 \(n\) 为一正奇数。因为偶数可于常数时间内判断1,因此证明其是否为素数是平凡的。

我们需要注意到的是,除了下述的测试 0: 朴素判定以外,其余的方法都不保证通过测试的数为素数,而仅仅在概率上非常可能为素数。更详细地说,若数 \(n\) 未通过素性测试,则其必定是合数。但是若其通过一次素性测试,其仅有一定可能为素数。而若其通过多次测试,则有非常大的可能为素数。

测试 0: 朴素测试

测试是否对于某些随机的,或全部 \(m \le \sqrt{n}\),都有 \(m \not\mid n\)。若 \(n\) 不通过测试,则显然有 \(m \mid n\)\(n\) 为合数。若 \(n\) 对于所有 \(m\) 皆通过,那么 \(n\) 必定是素数。然而该方法为指数时间复杂度,因此其实并不可行。

该方法是唯一一个能保证 \(n\) 为素数的算法。对于剩下的测试,我们仅能在一定概率内确定 \(n\) 为素数。我们称通过这样测试的数为伪素数。

测试 1: 费马测试

回忆前文所给的费马定理:

\(n\) 为素数,那么对于所有 \(b\),若 \(gcd(b, n) = 1\),则一定有 \(b^{n-1} \equiv 1 \pmod n\)

一个奇合数 \(n\) 被称作以 \(b\) 为底的伪素数(\(psp_b\)),若有

\[ b^{n-1} \equiv 1 \pmod n \tag {1} \]

因此有费马测试如下:
取一随机数 \(b\) 使得 \(1 < b < n\),并判断 \(n\) 是否是 \(psp_b\)
若测试失败,则 \(n\) 必定是合数。否则 \(n\) 有可能是素数。

注意:
1. 若式 (1) 成立,则 \(gcd(b, n) = 1\)
2. 若 \(b_1 \equiv b_2 \pmod n\),则 \(psp_{b_1} \iff psp_{b_2}\)

接下来分析该算法的准确性。记 \[ \begin{aligned} \mathcal{P}_n &= \{b \pmod n \mid \text{$n$ 是 $psp_b$}\} \\ &= \{b \pmod n \mid b^{n-1} \equiv 1 \pmod n\} \\ &\subseteq (\mathbb{Z}/n\mathbb{Z})^\times \end{aligned} \]

  1. \(gcd(b, n) = 1\),则 \[\text{$n$ 是 $psp_b$} \iff b \in \mathcal{P}_n \iff ord(b) \mid n-1\]

  2. \(b_1, b_2 \in \mathcal{P}_n \implies b_1b_2, b_1b^{-2} \in \mathcal{P}_n\)
    其中 \(b^{-2}\) 定义在 \((\mathbb{Z}/n\mathbb{Z})^\times\) 中。

  3. \(n\) 对于某些 \(b \in (\mathbb{Z}/n\mathbb{Z})^\times\) 不通过测试,那么其同样不通过至少一半的 \(b \in (\mathbb{Z}/n\mathbb{Z})^\times\)\[\mathcal{P}_n \ne (\mathbb{Z}/n\mathbb{Z})^\times \implies \big| \mathcal{P}_n \big| \le \frac{1}{2} \phi(n)\]

该定理是群论中一个更广泛的结论的特殊情况:

\(\mathcal{P}_n \ne (\mathbb{Z}/n\mathbb{Z})^\times\)(存在使得 \(n\) 不通过测试的底)那么

\[ \newcommand{\prob}{\mathsf{Prob}} \prob(\text{$n$ 通过测试 $k$ 次}) \le \frac{1}{2^k} \]

或者说,若 \(n\) 通过 \(k\) 次费马测试,那么

\[ \prob(\mathcal{P}_n = (\mathbb{Z}/n\mathbb{Z})^\times) \ge 1 - \frac{1}{2^k} \]

那么,当什么时候会有 \(\mathcal{P}_n = (\mathbb{Z}/n\mathbb{Z})^\times\) 呢?

注意,根据费马定理,若 \(n\) 为素数,则确实有上述结果。
然而,存在其他符合此性质的数。

卡迈克尔数(Carmichale numbers)为使得 \(\mathcal{P}_n = (\mathbb{Z}/n\mathbb{Z})^\times\) 的合数。

因此,费马测试并不实际,因为我们还需要储存一个包括所有卡迈克尔数的列表。而有证明表示,存在无限个卡迈克尔数。

插曲:子群及拉格朗日定理

\(H \subset G\)\(G\) 为群,那么如果有 \(1 \in H\)

\[h_1, h_2 \in H \implies h_1h_2^{-1} \in H\]

那么 \(H\) 为群,且称 \(H\)\(G\) 的子群。

注意,若 \(H\)\(G\) 的子群,根据以上弱化的定义,必然也有

\[h_1, h_2 \in H \implies h1^{-1} \in H \text{ 且 } h_1h_2 \in H\]

即上述定义足够保证 \(H\) 对于乘法和逆封闭。

\(x \in G\),那么 \(<x>\)\(G\) 的子群。因为有 \[x^n, x^m \in <x>, x^n\cdot(x^m)^{-1} = x^{n-m} \in <x>\]

\(G\) 为阿贝尔群且 \(m \ge 1\),那么 \[G[m] := \{x \in G \text{ 且 } x^m=1\}\]\(G\) 的子群。

因为有 \(1^m = 1\),因此 \(1 \in G[m]\)。于是若 \(x_1, x_2 \in G[m]\),那么根据定义有 \(x_1^m = 1 = x_2^m\)。于是

\[(x_1x_2^{-1})^m \stackrel{阿贝尔}{=} x_1^m(x_2^{-1})^m = 1 \cdot 1^{-1} = 1\]

因此

\[x_1x_2^{-1} \in G[m]\]

注意,若 \(G = (\mathbb{Z}/n\mathbb{Z})^\times\),则 \[\mathcal{P}_n \stackrel{定义}{=} \{b \in G : b^{n-1} = 1\} \stackrel{定义}{=} G[n-1]\]

\(H\) 是有限群 \(G\) 的有限子群,那么 \[\#H \mid \#G\]

a). 性质 P1 适用于 \(b \in G = (\mathbb{Z}/n\mathbb{Z})^\times\)

b). 因为 \(\mathcal{P}_n = G[n-1]\) 而后者是 \(G\) 的子群,因此符合性质。

c). 依前所述定义有 \(\big| G \big| = \phi(n)\)。因此根据定理 2 以及 b),因为 \(\mathcal{P}_n\)\(G\) 的子群,而两群基数可除,于是有

\[K := \frac{\big| G \big|}{\big| \mathcal{P}_n \big|} \in \mathbb{N}^+\]

于是若有 \(\mathcal{P}_n \ne (\mathbb{Z}/n\mathbb{Z})^\times\),那么 \(k \ne 1\)。因此 \(k \ge 2\)。所以有 \(\big| \mathcal{P}_n \big| = \frac{| G |}{k} \le \frac{| G |}{2} = \frac{\phi(n)}{2}\).

注意,若 \(H = <x>\),那么依据定理 2,有 \(\#H = ord(x)\)。因此拉格朗日定理可推广至 P2.

插曲:二次剩余

下一个素性测试需要使用关系到所谓二次剩余的欧拉定理。二次剩余与下列问题有关:

Q. 怎样判断给定 \(a \in \mathbb{Z}\) 平方数(\(\!\!\!\mod p\)),即判断是否有事实 \(a \in (\mathbb{F}_o^\times)^2\).

A1. 我们先给出结论。若 \(p > 2\) 为素数,由于有 \(gcd(2, p-1) = 2\),那么 \[a \in (\mathbb{F}_p^\times)^2 \iff ord(a) \mid \frac{p-1}{2}\]

A1 是以下定理的直接推论:

\(p\) 为素数,且有数 \(a\) 满足 \((a, p) = 1\),那么对于任何 \(n \ge 1\) 来说,方程 \(x^n \equiv a \pmod p\) 有解,当且仅当 \(ord_p(a) \mid \frac{p-1}{(n, p-1)}\)。其中 \(ord_p(a)\)\(\mathbb{F}_p^\times\)\([a]\) 的阶。

为了证明该定理,我们需要以下引理。

\(G = <x>\) 是一个阶为 \(n\) 的循环群,且有 \(m \mid n\),那么 \(x^k\) 的阶为 \(m\) 当且仅当 \(k = \frac{n}{m}k'\),其中 \(k' \in \mathbb{Z}\)\(gcd(k'm) = 1\).

根据 P2,有 \(ord(x^k) = m \iff \frac{n}{(k, n)} = m \iff \frac{n}{m} = (k, n)\)

一方面若有 \(k = \frac{n}{m}k'\)\((k', m) = 1\),那么 $(k, n) = (k', m) = .

另一方面若 \(\frac{n}{m} = (k, n)\),那么 \(\frac{n}{m} \mid k\)。因此存在 \(k' \in \mathbb{Z}\) 使得 \(k = \frac{n}{m}k'\)。于是 \(\frac{n}{m} = (k, n) = (\frac{n}{m}k', n) = \frac{n}{m}(k', m)\)。因此有 \((k', m) = 1\)

根据定理 3,有 \(\mathbb{F}_p^\times = <g>\)

首先设 \(x^n = a\)\(F_p^\times\) 中有解,于是有 \(i\) 使得 \(x = g^k\)。因此 \(a = g^{kn}\)。因为有 \(ord(g) = p-1\),根据 P2 可得知 \[ord(a) = \frac{p-1}{(nk, p-1)} \mid \frac{p-1}{(n , p-1)}\]

另一方面,若有 \(m := ord(a) \mid \frac{p-1}{(n, p-1)}\),那么存在 \(k \in \mathbb{Z}\) 使得 \(km = \frac{p-1}{(n, p-1)}\),或者说 \(p-1 = km(n, p-1)\)

根据前述引理,\(ord(a) = \frac{\frac{p-1}{(n, p-1)}}{k}\) 当且仅当 $k =

于是 \(a = g^{\frac{p-1}{m}k'}\),其中 \((k', m) = 1\).

A1 给出的方法并不实际,因为除非 \(p-1\) 的因式分解已知,求 \(ord(a)\) 需要指数级别的时间。

然而,根据欧拉定理我们确实有另一种在多项式时间内判定此问题的方法。而该方法使用了所谓的雅可比符号。

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

记号:若 \(p > 2\) 为一奇素数,\(a \in \mathbb{Z}\),那么勒让德符号 \(\J{a}{p}\) 定义为

\[ \J{a}{p} = \begin{cases} 0, & \text{if $p \mid a$}\\ 1, & \text{if $a \bmod p \in (\mathbb{F}_p^\times)^2$ 为一非零平方}\\ -1, & \text{除上述以外} \end{cases} \]

那么,我们的问题等价于判定是否有 \(\J{a}{p} = 1\).

\[ \J{a}{p} \equiv a^{\frac{p-1}{2}} \pmod p \]

注意,该定理说明了 \(\J{a}{p}\) 可在多项式时间内求得:

\[ \begin{aligned} \text{Time}(\text{计算 $\J{a}{p}$}) &= \Theta(\log(\frac{p-1}{2})\log^2(p)) \\ &= \Theta(\log^2(p)) \end{aligned} \]

\(p \mid a\),那么 \(a \equiv 0 \pmod p\)。于是等式两边皆为 0。

否则若 \(p \not\mid a\),那么 \(a \in \mathbb{F}_p^\times = G\)

我们有以下两项引理:

\[ G[2] = \{ x^2 = 1, x \in G\} = {1, -1} \]

我们给出大致的证明。由于有 \(G\) 为循环群且 \(\big| G[2] \big| = 2\) ,因为 \(\{1, -1\} \subseteq G[2]\),因此 \(G[2] = \{1, -1\}\).

\[ G^{\frac{p-1}{2}} \in \{1, -1\} \]

因为 \((a^{\frac{p-1}{2}})^2 = a^{p-1} \stackrel{P3}{=} = 1\), 因此 \(a^{\frac{p-1}{2}} \in G[2] \stackrel{Lem1}{=} \{1, -1\}\)

根据引理 2,我们仅需证 \(\J{a}{p} = 1 \iff a^{\frac{p-1}{2}} \equiv 1 \pmod p\).

于是

\[ \begin{aligned} \J{a}{p} = 1 & \stackrel{定义}{\iff} a \in (\mathbb{F}_p^\times)^2 \\ & \stackrel{略}{\iff} ord(a) \mid \frac{p-1}{2} \\ & \stackrel{P1}{\iff} a^{\frac{p-1}{2}} = 1 \text{ (在 $G$ 中)} \end{aligned} \]

我们有如下性质:
L0 (欧拉) \(\J{a}{p} \equiv a^{\frac{p-1}{2}} \pmod p\).
L1 \(\J{a}{p} = \J{b}{p}\),若 \(a \equiv b \pmod p\).
L2 \(\J{ab}{p} = \J{a}{p}\J{b}{p}\).
L3 \(\J{ab^2}{p} = \J{a}{p}\)\(p \not\mid p\).
L4 \(\J{-1}{p} = 1 \iff p \mod 1 \pmod 4\).
L5 \(\J{2}{p} = (-1)^{\frac{p^2-1}{2}} = \begin{cases} 1, &\text{若 $p \equiv \pm 1 \pmod 8$} \\ -1, &\text{若 $p \equiv \pm 3 \pmod 8$} \end{cases}\).
L6 (高斯二次互反律) 若 \(p, q\) 为奇素数,那么

\[ \J{q}{p} = (-1)^{\frac{(p-1)(q-1)}{4}}\J{p}{q} = \begin{cases} -\J{p}{q}, &\text{若 $p \equiv q \equiv 3 \pmod 4$}\\ \J{p}{q}, &\text{除此之外} \end{cases} \]

判断 11 是否是同余 13 的平方:

\[ \J{11}{13} \stackrel{L6}{=} \J{13}{11} \stackrel{L5}{=} -1 \]

因此 11 不是同余 13 的平方。

判断 21 是否是同余 43 的平方:

\[ \J{21}{43} \stackrel{L2}{=} \J{3}{43}\J{7}{43} \stackrel{L6}{=} (-\J{43}{3})(-\J{43}{7}) \stackrel{L1}{=} \J{1}{3}\J{1}{7} = 1 \]

因此 21 是同余 43 的平方。

注意,上述例子中我们对 21 进行了素因数分解。由于素因数分解算法为次指数复杂度,实际运用勒让德记号时除少数情况应避免使用 L2。所指少数情况包括在二进制下可轻易判断 \(p\) 是否有因子 2。

进一步地,所谓的雅可比符号避免了进行素因数分解的需要。

\(n\) 为一正奇数,那么定义

\[ \J{a}{n} := \J{a}{p_1}^{e_1} \times \cdots \times \J{a}{p_r}^{e_r} \]

其中 \(n = p_1^{e_1} \times \cdots \times p_r^{e_r}\).

雅可比符号满足以下条件:
J1 \(\J{a}{n} = \J{b}{n}\)\(a \equiv \pmod n\).
J2 \(\J{ab}{n} = \J{a}{n}\J{b}{n}\).
J3 \(\J{a}{nm} = \J{a}{n}\J{a}{m}\)\(m\) 也是一个正奇数。
J4 \(\J{-1}{n} = (-1)^\frac{n-1}{2} = \begin{cases}1, &\text{若 $n \equiv 1 \pmod 4$}\\-1, &\text{若 $n \equiv 3 \pmod 4$}\end{cases}\).
J5 J6 (高斯二次互反律) 若 \(m, n\) 为正奇数,那么 \[ \J{m}{n} = (-1)^{\frac{(n-1)(m-1)}{4}}\J{n}{m} = \begin{cases} -\J{n}{m}, &\text{若 $n \equiv m \equiv 3 \pmod 4$}\\ \J{n}{m}, &\text{除此以外} \end{cases} \]

判断 21 是否是同余 43 的平方,使用雅可比符号:

\[ \J{21}{43} \stackrel{J6}{=} \J{43}{21} \stackrel{J1}{=} \J{1}{21} = 1 \]

注意:
1. 欧拉定理 (L0) 与雅可比符号间有相似之处。这与随后给出的欧拉素性测试有关。
2. \(\J{a}{n} = 1\) 不一定表明 \(a\) 为同余 \(n\) 的平方,除非 \(n\) 为素数。
3. 使用雅克布符号计算 \(\J{a}{p}\) 的复杂度和计算欧几里得算法相当。

因为若有 \(r_1, \cdots, r_k\) 为欧几里得算法中计算 \((a, p)\) 时产生的余数,那么有 \(\J{a}{p} = \pm\J{p}{a} = \pm\J{r_1}{a} = \pm\J{a}{r_1} = \pm\J{r_2}{r_1} = \cdots\)。而若其中任何一项 \(r_i\) 为偶数,我们可首先从中尽可能多地提取因数 2.

不进行因数分解计算 \(\J{33}{43}\):

\[ \J{33}{43} \stackrel{J6}{=} \J{43}{33} \stackrel{J1}{=} \J{10}{33} \stackrel{J2}{=} \J{2}{33}\J{5}{33} \stackrel{J5}{=} 1 \times \J{5}{33} \stackrel{J6}{=} \J{33}{5} \stackrel{J1}{=} \J{3}{5} \stackrel{J6}{=} \J{5}{3} = \J{2}{3} \stackrel{J5}{=} -1 \]

欧拉素性测试(Solovay–Strassen 方法)

一个奇合数 \(n\) 被称作以 \(b\) 为底的欧拉伪素数,若有

\[ b^\frac{n-1}{2} \equiv \J{b}{n} \pmod n \tag {$\star$} \]

其中 \(\J{b}{n}\) 指的是雅可比符号。

根据欧拉定理(定理 3),若 \(n\) 为素数,则对于任何满足 \(gdb(b, n) = 1\)\(b\) 来说,皆有 \(n\) 为以 \(b\) 为底的欧拉伪素数。

\[\mathcal{E}_n = \{b \in (\mathbb{Z}/n\mathbb{Z})^\times : \text{式 $(\star)$ 成立}\} \subseteq (\mathbb{Z}/n\mathbb{Z})^\times\]

  1. \(\mathcal{E}_n\)\((\mathbb{Z}/n\mathbb{Z})^\times\) 的子群。
  2. \(\mathcal{E}_n \subseteq \mathcal{P}_n\),即以 \(b\) 为底的欧拉为素数一定是以 \(b\) 为底的伪素数。
  3. \(n\) 为合数,则 \(\mathcal{E}_n \ne (\mathbb{Z}/n\mathbb{Z})^\times\)。因此没有类似卡尔迈克尔数的存在。另外,有 \(\big| \mathcal{E}_n \big| \le \frac{1}{2}\phi(n)\).
  1. \((\star)\) 两边在 \(b\) 下都是乘法的。

  2. \(b \in \mathcal{E}_n\),则有

    \[ \begin{aligned} b^\frac{n-1}{2} &\equiv \J{b}{n} \pmod n\\ b^{n-1} &\equiv \J{b}{n}^2 \pmod n\\ &\equiv 1 \pmod n \end{aligned} \implies b \in \mathcal{P}_n \]

  3. 我们需要用到以下定理:

每一个卡尔迈克尔数都是 square-free 的。

\(b \in (\mathbb{Z}/n\mathbb{Z})^\times\), \(\J{b}{n} = -1\) (雅克布符号),且对于任何整除 \(n\) 的素数来说都有 \(b \equiv 1 \pmod \frac{n}{p}\),那么 \(b \not\in \mathcal{E}_n\).

假设 \(b \in \mathcal{E}_n\),那么

\[b^\frac{n-1}{2} \equiv \J{b}{n} \equiv -1 \pmod n\]

所以

\[b^\frac{n-1}{2} \equiv -1 \pmod \frac{n}{p}\]

然而

\[b \equiv 1 \pmod {n}{p}\]

那么

\[b^\frac{n-1}{2} \equiv 1^\frac{n-1}{2} \pmod \frac{n}{p}\]

所以

\[-1 \equiv 1 \pmod \frac{n}{p}\]

但是这是不可能的。因为 \(n\) 为奇数且为合数,因此 \(\frac{n}{p} > 2\).

\(p \mid\mid n\)\(gcd(n/p, p) = 1\)), 那么存在 \(b \in (\mathbb{Z}/n\mathbb{Z})^\times\) 使得 \(\J{b}{n} = -1\)\(b \equiv \pmod {\frac{n}{p}}\).

\(n' = \frac{n}{p}\),取满足 \(\J{r}{p} = -1\)\(r \in \mathbb{Z}\)

构造并观察如下集合的势:

\[\#\{a : \text{在 $(\mathbb{Z}/p\mathbb{Z})^\times$ 中 $\J{a}{p} = -1$}\} = \frac{p-1}{2}\]

因为 \(gcd(n', p) = 1\),存在 \(k\) 使得 \(kn' = r-1 \pmod p\),存在 \(b = kn' + r \equiv 1 \pmod p\) 使得

\[\J{b}{n} = \J{b}{p}\J{b}{n'}= \J{r}{p}\J{1}{n'} = -1\]

\(b' \equiv 1 \pmod {\frac{n}{p}}\).

于是假设定理 6.c 为假,即 \(\mathcal{E}_n = (\mathbb{Z}/n\mathbb{Z})^\times\).

那么根据 (a) 有 \(\mathcal{P}_n = (\mathbb{Z}/n\mathbb{Z})^\times\)。 即 \(n\) 为卡尔迈克尔数。

根据定理 7,\(n\) 是 square-free 的,即存在满足 \(p \mid\mid n\) 的素数 \(p\)。于是根据 claim 2&1,存在 \(b \not\in \mathcal{E}_n\).

那么 \(\mathcal{E}_n \ne (\mathbb{Z}/n\mathbb{Z})^\times\)。因为 \(\mathcal{E}_n\)\((\mathbb{Z}/n\mathbb{Z})^\times\) 的子群,有 \(\frac{\phi(n)}{\big| \mathcal{E}_n \big|} = k \ge 2\).

假设定理 7 为假,那么存在 满足 \(p^2 \mid n\) 的素数 \(p\),其中 \(n\) 为奇数。

那么可证明 \(G = (\mathbb{Z}/n\mathbb{Z})^\times\) 中有一元素 \(b\) 使得 \(ord(b) = \phi(p^2)\).

选择这样的 \(b\),于是由于 \(n\) 为卡尔迈克尔数,有 \(b^{n-1} \equiv 1 \pmod n\)。那么根据 P1,有 \(ord(b) = \phi(p) = p(p-1) \mid n-1\)。于是有 \(p \mid n-1\).

然而 \(p \mid n\),所以假设不可能成立,于是 \(n\) 是 square-free 的。

因此有欧拉测试如下:
取一随机数 \(b\) 使得 \(1 < b < n\)
\(gcd(b, n) \ne 1\),则 \(n\) 必然为合数。判断 \(n\) 是否是 \(Epsp_b\),即在 \(\mathbb{Z}/n\mathbb{Z}\) 中计算 \(b^\frac{n-1}{2}\)\(\J{b}{n}\)
若上两式不相等,则 \(n\) 必定是合数。否则 \(n\) 有可能是素数。

注意:
1. 若 \(n\) 通过 \(k\) 次测试,则 \[\prob(\text{$n$ 为合数}) \le \frac{1}{2^k}\] 2. 每一轮欧拉测试需要进行 \(\Theta(\log^3(n))\) 次位运算。

Miller-Rabin 素性测试

给定奇合数 \(n\),将 \(n-1\) 记作 \(2^\alpha s\),其中 \(s\) 为奇数。另选择满足 \(gcd(b, n) = 1\) 的数 \(b\)\(n\) 被称作以 \(b\) 为底的强伪素数,即 \(Spsp_b\),若以下之一成立:

  1. \(b^s \equiv 1 \pmod n\)
  2. 对于某些 \(r\), \(0 \le r \le \alpha\),有 \(b^{2^r s} \equiv -1 \pmod n\)

其中使用到了若 \(n\) 为素数,那么 \(ord(b) = 2 \implies b = \pm 1 \pmod n\),而其对于非素数幂的合数来说不成立的事实。

\[\mathcal{S}_n = \{b \in (\mathbb{Z}/n\mathbb{Z})^\times : \text{$n$ 为 $Spsp_b$} \subseteq (\mathbb{Z}/n\mathbb{Z})^\times\]

  1. \(\mathcal{S}_n \subseteq \mathcal{E}_n\)。(而我们之前有 \(\mathcal{E}_n \subseteq \mathcal{P}_n\)
  2. \(n \equiv 3 \pmod 4\),那么 \(\mathcal{S}_n = \mathcal{E}_n\).
  3. \(n\) 为素数,则 \(\mathcal{S}_n = (\mathbb{Z}/n\mathbb{Z})^\times\).
  4. \(n\) 为合数,则 \(\big| \mathcal{S}_n \big| \frac{1}{4}(n-1)\).
  1. \(n \equiv 3 \pmod 4\),那么有 \(\alpha = 1\), \(n - 1 = 2s\),则 \(s = \frac{n-1}{2}\) 为奇数。

    在这样的情况下, \(b \in \mathcal{S}_n \iff b^s \equiv \pm 1 \pmod n\).

    \(b \in \mathcal{E}_n\),则

    \[ \begin{aligned} b^\frac{n-1}{2} &\equiv \J{b}{n} \pmod n\\ b^s &\equiv \pm 1 \pmod n \end{aligned} \]

    所以 \(b \in \mathcal{S}_n\)\(\mathcal{E}_n \subseteq \mathcal{S}_n\)。而根据 a,有 \(\mathcal{S}_n \subseteq \mathcal{E}_n\)。因此 \(\mathcal{S}_n = \mathcal{E}_n\).

  2. \(n\) 为素数,\(b \in G = (\mathcal{Z}/n\mathcal{Z})^\times\)。那么 \(k := ord(b) \mid \phi(n) = n - 1 = 2^\alpha s\). 于是 \(k = 2^\beta s'\),其中 \(0 \le \beta \le \alpha\), \(s' \mid s\).

    \(\beta = 0\),则 \(k = s'\)。那么 \(b^{s'} \equiv 1 \pmod n\),并且 \((b^{s'})^\frac{s}{s'} = b^s \equiv 1 \pmod n\)。因此条件 1 成立而 \(b \in \mathcal{S}_n\).

    \(\beta > 0\),则 \(k\) 为偶数且 \(ord(b^\frac{k}{2}) = 2\) (P2)。因为 \(G\) 是循环群,所以 \(b^\frac{k}{2} \equiv -1 \pmod n\)。因此 \((b^\frac{k}{2})^\frac{s'}{s} \equiv (-1)^\frac{s}{s'} = 2^{\beta - 1}\) s$。因此条件 2 成立,其中有 \(r = \beta - 1 (0 \le r < \alpha)\)。因此 \(b \in \mathcal{S}_n\)\(G \subseteq \mathcal{S}_n\).

    于是有 \(G = \mathcal{S}_n\).

因此有 Miller-Rabin 测试如下:
\(n-1 = 2^\alpha s\), 其中 \(s\) 为奇数。

取一随机数 \(b\) 使得 \(1 < b < n-1\)
\(gcd(b, n) \ne 1\),则 \(n\) 必然为合数。

计算 \(b_0 \equiv b^s \pmod n\),并检查 \(b_0 \equiv \pm1 \pmod n\)。若有,则 \(n\) 通过测试。否则,依下式逐次计算 \(b_1, b_2, \cdots, b_{\alpha - 1}\)\[b_k \equiv b^2_{k-1} \pmod n, (1 \le k \le \alpha-1\]

若对于每一项皆有 \(b_k \equiv -1 \pmod n\),那么 \(n\) 通过相对于此 \(b\) 的测试。

\(n\) 通过 \(k\) 次 Miller-Rabin 测试,则

\[\prob(\text{$n$ 为合数}) \le \frac{1}{4^k}\]

假设广义黎曼猜想成立,Adleman, Pomerance, Rumely (1983) 和 Bach(1985) 证明了

\[\text{$n$ 为合数} \implies \text{$\exists b < 2\log^2(n)$ 使得 $b \not \in \mathcal{S}_n$}\]

若如此,则有另一种素性测试:与其随机选择 \(b\),我们可以逐次取整数 \(b = 2, 3, 5, \cdots\)。注意我们仅需取素数,由于有 \(<\mathcal{S}_n> \le \mathcal{E}_n \ne (\mathbb{Z}/n\mathbb{Z})^\times\).

事实上,在小于 \(25 \times 10^9\) 的范围内,仅有 13 个合数满足 \(2, 3, 5 \in \mathcal{S}_n\),而没有任何合数满足 \(2, 3, 5, 7, 11, 13 \in \mathcal{S}_n\).

工程计算软件 Maple 中的 isprime(n) 函数交替使用 Miller-Rabin 测试和 Lucas 测试。根据 Maple 的文档,没有已知的合数能通过测试。


  1. 假设我们用二进制编码整数↩︎