5.4.5 素数检验

下面将给出两个随机性素数检验方法, 它们对于检验大数的素数性质是有用的, 而且出错的概率足够小. 应用这些检验方法有可能在不知道素因子的情形下证明一个数不是素数.

1. 费马素数检验

设自然数 $n$ 是一个奇数,而 $a$ 是一个满足 $gcd\left(a,n\right)=1$ 以及 $a^{n-1}\equiv 1\left(\mathrm{mod}n\right)$ 的整数. 那么 $n$ 称为对于基 $a$ 的伪素数.

$◼\mathbf{A}$: 341 是对于基 2 的伪素数; 341 不是对于基 3 的伪素数.

检验 设给定奇数 $n>1$ . 选取 $a\in {\mathbb{Z}}_n\setminus \{0\}$ .

• 如果 $gcd\left(a,n\right)>1$ ,那么 $n$ 不是素数.

• 如果 $gcd\left(a,n\right)=1$ ,并且 $\left\{\begin{array}{l}{a}^{n-1}\equiv 1\left(\mathrm{mod}n\right)\\ a^{n-1}\not\equiv 1\left(\mathrm{mod}n\right)\end{array}\right\}$ ,那么 $n\left\{\begin{array}{l}\text{ 通过 }\\ \text{ 不通过 }\end{array}\right\}$ 对于基 $a$ 的检验. 如果 $n$ 不通过检验,那么 $n$ 不是素数. 如果 $n$ 通过检验,那么它可能是一个素数,但还必须对其他基进行检验,即对于 $a$ 的其他值进行检验.

$◼\mathbf{B}$: $n=15$ : 对于 $a=4$ 检验给出 $4^{14}\equiv 1\left(\mathrm{mod}15\right)$ . 对于 $a=7$ 检验给出 $7^{14}\equiv 4\not\equiv 1\left(\mathrm{mod}15\right)$ . 因此 15 不是素数.

$◼\mathbf{C}$: $n=561$ : 对于任意的 $a\in {\mathbb{Z}}_{561}\setminus \{0\}$ 并且 $gcd\left(a,561\right)=1$ 检验得到 $a^{560}\equiv 1\left(\mathrm{mod}561\right)$ . 但 $561=3\cdot 11\cdot 17$ 不是素数.

注 对于所有 $a\in {\mathbb{Z}}_n\setminus \{0\}$ 满足 $a^{n-1}\equiv 1\left(\mathrm{mod}n\right)$ ,并且 $gcd\left(a,n\right)=1$ 的合数 $n$ 称为卡迈克尔 (Carmichael) 数.

如果 $n$ 不是素数并且不是卡迈克尔数,那么我们可以证明第一种应用 $k$ 个满足 $gcd\left(a,n\right)=1$ 的数获得错误结果的误差水平至多是 $1/2^k$ . 至少对于 ${\mathbb{Z}}_n\setminus \{0\}$ 中满足 $gcd\left(a,n\right)=1$ 的数中的一半关系式 $a^{n-1}\not\equiv 1\left(\mathrm{mod}n\right)$ 成立.

2. 拉滨-米勒素数检验

拉滨-米勒 (Rabin-Miller) 素性检验以下列命题 (*) 为基础:

设 $n>2$ 是素数, $n-1=2^{t}u\left(u\text{是奇数}\right),gcd\left(a,n\right)=1$ . 那么

对于某个 $j\in \{0,1,\cdots ,t-1\},a^u\equiv 1\left(\mathrm{mod}n\right)$ 或 $a^{2^{j}u}\equiv -1\left(\mathrm{mod}n\right)$ .(*)

每个奇自然数 $n>1$ 可以用下列方法检验其素性:

检验 选取 $a\in {\mathbb{Z}}_n\setminus \{0\}$ ,并且求出表达式 $n-2=2^{t}u(u$ 是奇数).

• 如果 $gcd\left(a,n\right)>1$ ,那么 $n$ 不是素数.

• 如果 $gcd\left(a,n\right)=1$ ,那么计算序列 $a^u\left(\mathrm{mod}n\right),a^{2u}\left(\mathrm{mod}n\right),\cdots ,a^{2^{t-1}u}\left(\mathrm{mod}n\right)$ , 直到找到满足 $(\ast )$ 的值为止. 序列的元素可以通过重复实施模 $n$ 平方算出. 如果不存在这样的值,那么 $n$ 不是素数. 不然 $n$ 通过对于基 $a$ 的检验.

$◼\mathbf{A}$: $n=561$ ,并且要用 $a$ 的不同值检验: $n-1=2^4\cdot 35,a=2$ :

$$2^{35}\equiv 263\not\equiv \pm 1\left(\mathrm{mod}561\right),$$$$2^{70}\equiv 166\not\equiv -1\left(\mathrm{mod}561\right),$$$$2^{140}\equiv 67\not\equiv -1\left(\mathrm{mod}561\right),$$$$2^{280}\equiv 421\not\equiv -1\left(\mathrm{mod}561\right).$$

因此 561 不是素数.

如果随机且独立地选取 $k$ 个不同的值,并且 $n$ 对基 $a$ 的每个值通过检验,那么 $n$ 不是素数的第一类误差率 $\le 1/4^k$ . 在实用中取 $k=25$ .

$◼\mathbf{B}$: 仅有一个数 $\le 2.5\cdot {10}^{10}$ ,通过对于基 $a=2,3,5,7$ 的检验,但它不是素数.

3. AKS 素数检验

AKS 素性检验基于确定一个数是素数还是合数的多项式算法. 它是Agrawal, Kayal 和Saxena 于 2002 年发表, 同时它显然可以有效地检验任何自然数的素性.

这个检验方法基于下列命题:

如果 $n>1$ 是自然数,而 $r$ 是一个素数,满足下列假设:

• $n$ 不被 $\le r$ 的素数整除;

• 当 $i=1,2,\cdots ,\lfloor {\left({\log }_{2}n\right)}^2\rfloor$ 时, $r^i\not\equiv 1\left(\mathrm{mod}n\right)$ (符号 $\lfloor x\rfloor$ 表示 “ $\le x$ 的最大整数”);

• 对于每个 $1\le a\le \sqrt{r}\log n,{(x+a)}^n\equiv x^n+a\left(\mathrm{mod}{x}^r-1,n\right)$ ,

那么 $n$ 是一个素数幂.

设 $n>1$ 是一个奇自然数,要检验它的素性,并设 $m\text{:=}\lfloor {\left({\log }_{2}n\right)}^5\rfloor$ . 如果 $n<5690034$ ,那么可以通过将它与已知素数的表相比较检验它是否素数. 对于 $n>$ 5690034,令 $n>m$ :

检验

• 核验 $n$ 是否能被区间 $\left[3,m\right]$ 中的自然数整除. 如果是,那么 $n$ 不是素数.

• 不然,取素数 $r<n$ ,使得 $r^i\not\equiv 1\left(\mathrm{mod}n\right)\left(i=1,2,\cdots ,\lfloor {\left({\log }_{2}n\right)}^2\rfloor \right)$ .(可以证明这样的素数 $r$ 存在.)

• 核验当 $a=1,2,\cdots ,\lfloor \sqrt{r}{\log }_{2}n\rfloor$ 时,同余式 ${(x+a)}^n\equiv x^n+a\left(\mathrm{mod}{x}^r-1,n\right)$ 是否成立. 若不成立,则 $n$ 不是素数. 若成立,则 $n$ 是一个素数幂. 在这种情形要检验是否存在自然数 $q$ 和 $k>1$ ,使得 $n=q^k$ . 若不存在,则 $n$ 是一个素数.

与已知的算法及有效性随机性算法不同, 这个检验的结果是可信的, 甚至没有可忽略的小的错误概率误差. 但在密码学中拉滨-米勒素数检验更合适.