可能質數

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

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

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

性質

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

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

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

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

變體

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

一個是合成數歐拉可能質又稱以Template:Math為底的歐拉-雅可比偽質數。最小的以2為底的歐拉-雅可比偽質數是561。Template:R在小於$25\times 10^9$的數字中，有11347個以2為底的歐拉-雅可比偽質數。Template:R

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

$a^d\equiv 1(\mathrm{mod}n),$

或

$a^{d\cdot 2^r}\equiv -1(\mathrm{mod}n)\text{ for some }0\le r\le s-1.$

一個實際上是合成數的以Template:Math為底的強可能質數又稱為以Template:Math為底的強偽質數。所有以Template:Math為底的強偽質數也都是在相同底下的歐拉可能質數，但反過來不盡然成立。

最小的以2為底的2強偽質數是2047。Template:R在小於$25\times 10^9$的數字中，有4842個以2為底的2強偽質數。Template:R

此外也有基於盧卡斯數列的Template:Link-en。盧卡斯可能質數可單獨使用。另外Template:Link-en是混合盧卡斯測試和強可能質數測試的質數判定法。

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

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

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

參見

• Template:Link-en
• Template:Link-en
• 歐拉-雅可比偽質數
• Template:Link-en
• 米勒-拉賓質數判定法
• 佩蘭質數判定法
• 卡邁克爾數

外部連結

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