伪素数

伪素数是有和質數相同的性質（像是通過隨機性的素性测试判定），但本身是合数的数，根据所满足的性质的不同可以划分不同种类的伪素数。其中最有名的伪素数是满足费马小定理的合数，即费马伪素数。

伪素数的重要性
公开密钥加密的基礎是建立在大的合數，很難進行因數分解的基礎上，因此質數在公开密钥加密裡非常重要，而伪素数可能被誤當成質數，影響公开密钥加密。

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

费马伪素数
费马伪素数的定义是：对自然数x和一个与其互素的自然数a，如果x整除 ax-1 - 1，则称x是一个以a为底的费马伪素数或者关于a的费马伪素数。最小的费马伪素数是341（=11×31，关于2）。如果x关于任何与其互素的数都是费马伪素数，则称x是绝对伪素数（或卡邁克爾數），来自找到第一个绝对伪素数的数学家羅伯特·丹尼·卡邁克爾）。最小的绝对伪素数是561。

参见
*
*

• 欧拉伪素数
• 欧拉-雅可比伪素数
• 费马伪素数

*
*

• 佩蘭數列

*

• 強偽質數

參考資料