伪素数

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

伪素数的重要性

公开密钥加密的基础是建立在大的合数，很难进行因数分解的基础上，因此素数在公开密钥加密里非常重要，而伪素数可能被误当成素数，影响公开密钥加密。

卡尔·帕梅朗斯在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）
• 强伪素数