擬素数

擬素数（ぎそすう、英：pseudoprime）とは、ほとんどの合成数が満たさない何らかの性質を持っている（確率的素数）が、実際には素数でないものである^{[注 1]}。注目している性質によって、フェルマー擬素数（英語版）、オイラー擬素数（英語版）、カタラン擬素数、リュカ擬素数など様々な種類の擬素数が存在する。

擬素数は、大きな数を素因数分解することの難しさを利用する公開鍵暗号において最も重要である。カール・ポメランスは1988年に144桁の数字を因数分解するのに1000万ドル、200桁の数を因数分解するのに1000億ドルかかると見積もっていた（今日ではこれよりずっと安くなっているが、それでも法外に高額である）^[1][2]。しかし、これを用いるのに必要な2つの大きな素数を見つけるのにも費用がかかるため、様々な確率的素数判定が用いられ、まれに素数ではなく合成数が不適切に素数と判定される場合もある。一方でAKS素数判定法などの決定的素数判定法では偽陽性が生じることはなく、擬素数はない。

フェルマー擬素数

フェルマーの小定理は、pが素数でありaとpが互いに素である場合、a^p−1 − 1 はpで割り切れるという内容である。整数a > 1で合成数の整数xが a^x−1 − 1を割り切れる場合、xはaを底とするフェルマー擬素数（英語版）と呼ばれる。xが底aのフェルマー擬素数である場合、xはaと互いに素となる。この定義とは異なる定義を用いるものもある。例えば、それを用いると奇数のみを擬素数にすることができる^[3]。

xと互いに素である全ての値をとるaに対してフェルマー擬素数である整数xはカーマイケル数と呼ばれる。

擬素数の例

• カタラン擬素数
• 楕円擬素数
• オイラー擬素数（英語版）
• オイラー・ヤコビ擬素数（英語版）
• フェルマー擬素数（英語版）
• フロベニウス擬素数（英語版）
• リュカ擬素数
• ペリン擬素数
• en:Somer–Lucas pseudoprime
• 強い擬素数（英語版）