查看“︁可能質數”︁的源代码

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

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

對於固定的底{{math|a}}，一個以之為底的合成數不太可能會是可能質數（也就所謂的[[偽質數]]），像例如說在不大於<math>25 \times 10^9</math>的數字中，有11,408,012,595個奇合成數，但只有21,853個以2為底的偽質數；<ref name="PSW">{{cite journal |author1 = Carl Pomerance |author-link1 = Carl Pomerance |author2 = John L. Selfridge |author-link2 = John L. Selfridge |author3 = Samuel S. Wagstaff, Jr. |author-link3 = Samuel S. Wagstaff, Jr. |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |date=July 1980 |volume=35 |issue=151 |pages=1003–1026 |url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf |jstor=2006210 |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free }}</ref>{{rp|1005}}相比之下在同樣的區間中有1,091,987,404個奇質數。

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

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

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

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

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

一個是合成數歐拉可能質又稱以{{math|a}}為底的[[歐拉-雅可比偽質數]]。最小的以2為底的歐拉-雅可比偽質數是561。{{r|PSW|p=1004}}在小於<math>25 \times 10^9</math>的數字中，有11347個以2為底的歐拉-雅可比偽質數。{{r|PSW|p=1005}}

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

: <math>a^d\equiv 1\pmod n,\;</math>
或
: <math>a^{d\cdot 2^r}\equiv -1\pmod n\text{ for some }0\leq r\leq s-1. \, </math>

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

最小的以2為底的2強偽質數是2047。{{r|PSW|p=1004}}在小於<math>25 \times 10^9</math>的數字中，有4842個以2為底的2強偽質數。{{r|PSW|p=1005}}

此外也有基於[[盧卡斯數列]]的{{link-en|盧卡斯偽質數|Lucas pseudoprime|盧卡斯可能質數}}。盧卡斯可能質數可單獨使用。另外{{link-en|貝里-PSW質數判定法|Baillie–PSW primality test}}是混合盧卡斯測試和強可能質數測試的質數判定法。

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

==參見==
* {{link-en|可證明質數|Provable prime}}
* {{link-en|貝里-PSW質數判定法|Baillie–PSW primality test}}
* [[歐拉-雅可比偽質數]]
* {{link-en|盧卡斯偽質數|Lucas pseudoprime}}
* [[米勒-拉賓質數判定法]]
* [[佩蘭數列#佩蘭偽質數|佩蘭質數判定法]]
* [[卡邁克爾數]]

==外部連結==
* [http://primes.utm.edu/glossary/page.php?sort=PRP The prime glossary &ndash; Probable prime]
* [http://www.primenumbers.net/prptop/ The PRP Top 10000 (the largest known probable primes)]

==參考資料==
{{reflist}}

{{質數}}

[[Category:偽素數]]