可能質數

在數論上，可能質數（probable prime，縮寫為PRP）指的是一個滿足所有質數都會滿足、但多數合成數都不會滿足的特定條件的數。不同的可能質數會有不同的條件。雖說一些可能質數會是合成數（也就所謂的偽質數），但一般會透過條件的選取讓這種狀況變得少見。

像例如一個基於費馬小定理的費馬合成數測試，其原理如次：在給定一個 $n$ 的狀況下，選取一個不是 $n$ 的倍數的數 $a$ （一般會在 $1<a<n-1$ 的範圍中選取 $a$ ），然後計算 $a^{n-1}{\pmod {n}}$ 。若結果不是1，則 $n$ 是合成數；若結果是1，那 $n$ 就有可能是質數，這種情況下，可稱 $n$ 是以 $a$ 為底的可能質數。一個以 $a$ 為底的弱可能質數指的是一個以 $a$ 為底的可能質數，但這個可能質數不是以 $a$ 為底的強可能質數。

對於固定的底 $a$ ，一個以之為底的合成數不太可能會是可能質數（也就所謂的偽質數），像例如說在不大於 $25\times 10^{9}$ 的數字中，有11,408,012,595個奇合成數，但只有21,853個以2為底的偽質數；^[1]^:1005相比之下在同樣的區間中有1,091,987,404個奇質數。

性質

質數可能性是高效質數判定演算法的基礎，而這類演算法被應用於密碼學中。這些演算法通常在本質上是隨機化的。這主意背後的想法是盡管對於任意固定的底 $a$ 而言，都有實際上是合成數的以 $a$ 為底的可能質數，因此會期望說對於任意的合成數 $n$ ，存在一個 $P<1$ ，使得在隨機選取 $a$ 時， $n$ 是以 $a$ 為底的偽質數的機率不會超過 $P$ 。在這種狀況下，假如重複類似的操作 $k$ 次，每次都選取新的 $a$ ，那麼 $n$ 是以 $a$ 為底的偽質數的機率就不會大於 $P^{k}$ 。有鑑於 $P^{k}$ 指數性遞減之故，因此只需要選取適量的 $k$ ，就能把機率壓低到可忽略地小（相對電腦硬體出現錯誤的機率等而言）的程度。

然而壞消息是，由於卡邁克爾數之故，上述的理論是對於弱可能質數而言是不成立的；不過對於諸如強可能質數（像例如由米勒-拉賓質數判定法給出的那些，其中 $P={\frac {1}{4}}$ ）或歐拉可能質數（由梭羅維-施特拉森質數測試（英语：Solovay–Strassen primality test）給出，其中 $P={\frac {1}{2}}$ ）等對質數可能性測試更精進的想法而言，上述的理論是成立的。

即使在需要使用確定性質數判定證明的狀況下，一個有用的步驟是先使用隨機化質數判定法，這可迅速（且確定）地去掉絕大多數的合成數。

有時質數判定測試會與小的偽質數表一起使用，好快速確定小於特定門檻的數字的質數性。

變體

一個以 $a$ 為底的歐拉可能質數是一個較強的理論指出的可能是質數的正整數，其中對於任意的質數 $p$ ， $a^{\frac {(p-1)}{2}}\equiv ({\tfrac {a}{p}}){\pmod {p}}$ ，其中 $({\tfrac {a}{p}})$ 是雅可比符號。

一個是合成數歐拉可能質又稱以 $a$ 為底的歐拉-雅可比偽質數。最小的以2為底的歐拉-雅可比偽質數是561。^[1]^:1004在小於 $25\times 10^{9}$ 的數字中，有11347個以2為底的歐拉-雅可比偽質數。^[1]^:1005

這測試可利用1的平方根除以p必然等於1或-1這件事實來改進。而這可藉由 $n=2^{s}\cdot d+1$ 這點（其中 $d$ 是奇數）達成。若 $n$ 滿足以下條件，則稱 $n$ 是以 $a$ 為底的強可能質數：

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

或

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在小於 $25\times 10^{9}$ 的數字中，有4842個以2為底的2強偽質數。^[1]^:1005

此外也有基於盧卡斯數列的盧卡斯可能質數（英语：Lucas pseudoprime）。盧卡斯可能質數可單獨使用。另外貝里-PSW質數判定法（英语：Baillie–PSW primality test）是混合盧卡斯測試和強可能質數測試的質數判定法。

測試是否為強可能質數的範例

以下為測試97是否是以2為底的強可能質數的步驟：

第一步：找到使得 $96=d\cdot 2^{s}$ $96=d\cdot 2^{s}$ 的 $d$ $d$ 和 $s$ $s$ ，其中 $d$ $d$ 是奇數。
- 先從 $s=0$ 開始，此時 $d$ 會是96。
- 慢慢增加 $s$ ，之後會發現說 $d=3$ 且 $s=5$ ，而這是因為 $96=3\cdot 2^{5}$ 之故。
第二步：在 $1<a<97-1$ 的範圍內選取 $a$ ，此處選取 $a=2$ 。
第三步：計算 $a^{d}{\bmod {n}}$ ，也就是計算 $2^{3}{\bmod {9}}7$ 。由於這不同餘於1之故，因此測試下一個條件。
第四步：在 $0\leq r<s$ $0\leq r<s$ 的範圍內計算 $2^{3\cdot 2^{r}}{\bmod {9}}7$ $2^{3\cdot 2^{r}}{\bmod {9}}7$ 。假若其中一個的結果與96同餘，那97是可能質數；不然97就篤定是合成數。以下是對各個 $r$ $r$ 運算的結果：
- $r=0:2^{3}\equiv 8{\pmod {97}}$
- $r=1:2^{6}\equiv 64{\pmod {97}}$
- $r=2:2^{12}\equiv 22{\pmod {97}}$
- $r=3:2^{24}\equiv 96{\pmod {97}}$
因此，97是以2為底的強可能質數，也因此是以2為底的可能質數。