偽質數

偽質數是有和質數相同的性質（像是通過隨機性的素性測試判定），但本身是合數的數，根據所滿足的性質的不同可以劃分不同種類的偽質數。其中最有名的偽質數是滿足費馬小定理的合數，即費馬偽質數。

偽質數的重要性

公開密鑰加密的基礎是建立在大的合數，很難進行因數分解的基礎上，因此質數在公開密鑰加密裏非常重要，而偽質數可能被誤當成質數，影響公開密鑰加密。

卡爾·帕梅朗斯在1988年估計要將144位數的數字進行因數分解，其成本約為一千萬美元，若要分解200位數的數字，成本則是一億美元（現今的成本都比當年低很多，但仍然非常高）^[1][2]。公開密鑰加密會需要找到二個很大的質數，相乘成為很難因數分解的合數，而找到二個這類質數的成本也很高。因此出現了許多概率性的素性測試，可能有較低成本判斷是否是質數。這類的素性測試會有偽陽性，偶爾會有合數以此測試判定為質數，這類的素性測試就會有對應的偽質數。另一方面，確定性素性測試（像是AKS質數測試）不會有偽陽性，不會有任何合數以此測試判定為質數，也不會有對應的偽質數。

費馬偽質數

主條目：費馬偽質數

費馬偽質數的定義是：對自然數${\displaystyle x}$和一個與其互質的自然數a，如果${\displaystyle x}$整除 a^x-1 - 1，則稱${\displaystyle x}$是一個以a為底的費馬偽質數或者關於a的費馬偽質數。最小的費馬偽質數是341（=11×31，關於2）。如果${\displaystyle x}$關於任何與其互質的數都是費馬偽質數，則稱${\displaystyle x}$是絕對偽質數（或卡邁克爾數），來自找到第一個絕對偽質數的數學家羅伯特·丹尼·卡邁克爾）。最小的絕對偽質數是561。

參見

• 卡塔蘭偽質數（英語：Catalan pseudoprime）
• 橢圓偽質數（英語：Elliptic pseudoprime）
• 歐拉偽質數
• 歐拉-雅可比偽質數
• 費馬偽質數
• 弗羅貝尼烏斯偽質數（英語：Frobenius pseudoprime）
• 盧卡斯偽質數（英語：Lucas pseudoprime）
• 佩蘭數列
• Somer–盧卡斯偽質數（英語：Somer–Lucas pseudoprime）
• 強偽質數