可能质数

在数论上，可能质数（probable prime，缩写为PRP）指的是一个满足所有质数都会满足、但多数合成数都不会满足的特定条件的数。不同的可能质数会有不同的条件。虽说一些可能质数会是合成数（也就所谓的伪质数），但一般会透过条件的选取让这种状况变得少见。

像例如一个基于费马小定理的费马合成数测试，其原理如次：在给定一个n的状况下，选取一个不是n的倍数的数a（一般会在${\displaystyle 1<a<n-1}$的范围中选取a），然后计算${\displaystyle a^{n-1}{\pmod {n}}}$。若结果不是1，则n是合成数；若结果是1，那n就有可能是质数，这种情况下，可称n是以a为底的可能质数。一个以a为底的弱可能质数指的是一个以a为底的可能质数，但这个可能质数不是以a为底的强可能质数。

对于固定的底a，一个以之为底的合成数不太可能会是可能质数（也就所谓的伪质数），像例如说在不大于${\displaystyle 25\times 10^{9}}$的数字中，有11,408,012,595个奇合成数，但只有21,853个以2为底的伪质数；^[1]:1005相比之下在同样的区间中有1,091,987,404个奇质数。

性质

质数可能性是高效质数判定算法的基础，而这类算法被应用于密码学中。这些算法通常在本质上是随机化的。这主意背后的想法是尽管对于任意固定的底a而言，都有实际上是合成数的以a为底的可能质数，因此会期望说对于任意的合成数n，存在一个${\displaystyle P<1}$，使得在随机选取a时，n是以a为底的伪质数的几率不会超过P。在这种状况下，假如重复类似的操作k次，每次都选取新的a，那么n是以a为底的伪质数的几率就不会大于${\displaystyle P^{k}}$。有鉴于${\displaystyle P^{k}}$指数性递减之故，因此只需要选取适量的k，就能把几率压低到可忽略地小（相对电脑硬件出现错误的几率等而言）的程度。

然而坏消息是，由于卡迈克尔数之故，上述的理论是对于弱可能质数而言是不成立的；不过对于诸如强可能质数（像例如由米勒-拉宾质数判定法给出的那些，其中${\displaystyle P={\frac {1}{4}}}$）或欧拉可能质数（由梭罗维-施特拉森质数测试（英语：Solovay–Strassen primality test）给出，其中${\displaystyle P={\frac {1}{2}}}$）等对质数可能性测试更精进的想法而言，上述的理论是成立的。

即使在需要使用确定性质数判定证明的状况下，一个有用的步骤是先使用随机化质数判定法，这可迅速（且确定）地去掉绝大多数的合成数。

有时质数判定测试会与小的伪质数表一起使用，好快速确定小于特定门槛的数字的质数性。

变体

一个以a为底的欧拉可能质数是一个较强的理论指出的可能是质数的正整数，其中对于任意的质数p，${\displaystyle a^{\frac {(p-1)}{2}}\equiv ({\tfrac {a}{p}}){\pmod {p}}}$，其中${\displaystyle ({\tfrac {a}{p}})}$是雅可比符号。

一个是合成数欧拉可能质又称以a为底的欧拉-雅可比伪质数。最小的以2为底的欧拉-雅可比伪质数是561。^[1]:1004在小于${\displaystyle 25\times 10^{9}}$的数字中，有11347个以2为底的欧拉-雅可比伪质数。^[1]:1005

这测试可利用1的平方根除以p必然等于1或-1这件事实来改进。而这可借由${\displaystyle n=2^{s}\cdot d+1}$这点（其中d是奇数）达成。若n满足以下条件，则称n是以a为底的强可能质数：

${\displaystyle a^{d}\equiv 1{\pmod {n}},\;}$

或

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ for some }}0\leq r\leq s-1.\,}$

一个实际上是合成数的以a为底的强可能质数又称为以a为底的强伪质数。所有以a为底的强伪质数也都是在相同底下的欧拉可能质数，但反过来不尽然成立。

最小的以2为底的2强伪质数是2047。^[1]:1004在小于${\displaystyle 25\times 10^{9}}$的数字中，有4842个以2为底的2强伪质数。^[1]:1005

此外也有基于卢卡斯数列的卢卡斯可能质数（英语：Lucas pseudoprime）。卢卡斯可能质数可单独使用。另外贝里-PSW质数判定法（英语：Baillie–PSW primality test）是混合卢卡斯测试和强可能质数测试的质数判定法。

测试是否为强可能质数的范例

以下为测试97是否是以2为底的强可能质数的步骤：

• 第一步：找到使得${\displaystyle 96=d\cdot 2^{s}}$的${\displaystyle d}$和${\displaystyle s}$，其中${\displaystyle d}$是奇数。
  • 先从${\displaystyle s=0}$开始，此时${\displaystyle d}$会是96。
  • 慢慢增加${\displaystyle s}$，之后会发现说${\displaystyle d=3}$且${\displaystyle s=5}$，而这是因为${\displaystyle 96=3\cdot 2^{5}}$之故。
• 第二步：在${\displaystyle 1<a<97-1}$的范围内选取${\displaystyle a}$，此处选取${\displaystyle a=2}$。
• 第三步：计算${\displaystyle a^{d}{\bmod {n}}}$，也就是计算${\displaystyle 2^{3}{\bmod {9}}7}$。由于这不同余于1之故，因此测试下一个条件。
• 第四步：在${\displaystyle 0\leq r<s}$的范围内计算${\displaystyle 2^{3\cdot 2^{r}}{\bmod {9}}7}$。假若其中一个的结果与96同余，那97是可能质数；不然97就笃定是合成数。以下是对各个${\displaystyle r}$运算的结果：
  • ${\displaystyle r=0:2^{3}\equiv 8{\pmod {97}}}$
  • ${\displaystyle r=1:2^{6}\equiv 64{\pmod {97}}}$
  • ${\displaystyle r=2:2^{12}\equiv 22{\pmod {97}}}$
  • ${\displaystyle r=3:2^{24}\equiv 96{\pmod {97}}}$
• 因此，97是以2为底的强可能质数，也因此是以2为底的可能质数。

参见

• 可证明质数（英语：Provable prime）
• 贝里-PSW质数判定法（英语：Baillie–PSW primality test）
• 欧拉-雅可比伪质数
• 卢卡斯伪质数（英语：Lucas pseudoprime）
• 米勒-拉宾质数判定法
• 佩兰质数判定法
• 卡迈克尔数

外部链接

• The prime glossary – Probable prime
• The PRP Top 10000 (the largest known probable primes)

参考资料

1. Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. The pseudoprimes to 25·10⁹ (PDF). Mathematics of Computation. July 1980, 35 (151): 1003–1026. JSTOR 2006210. doi:10.1090/S0025-5718-1980-0572872-7 .