擬素数

擬素数（ぎそすう、英：pseudoprime）は、実際には素数ではない確率的素数（全ての素数に共通の性質を持つ整数）。擬素数は、それが満たす素数の特性により分類される。
擬素数という用語を全ての概素数（合成数と本当に素数である数の両方）とするものもある。
擬素数は、大きな数を素因数分解することの難しさを利用する公開鍵暗号において最も重要である。カール・ポメランスは1988年に144桁の数字を因数分解するのに1000万ドル、200桁の数を因数分解するのに1000億ドルかかると見積もっていた（今日ではこれよりずっと安くなっているが、それでも法外に高額である）。しかし、これを用いるのに必要な2つの大きな素数を見つけるのにも費用がかかるため、様々な確率的素数判定が用いられ、まれに素数ではなく合成数が不適切に素数と判定される場合もある。一方でAKS素数判定法などの決定的素数判定法では偽陽性が生じることはなく、擬素数はない。
フェルマー擬素数.
フェルマーの小定理は、"p"が素数であり"a"と"p"が互いに素である場合、"a""p"−1 − 1 は"p"で割り切れるという内容である。整数"a" > 1で合成数の整数"x"が "a""x"−1 − 1を割り切れる場合、"x"は"aを底とする"と呼ばれる。"x"が底"a"のフェルマー擬素数である場合、"x"は"a"と互いに素となる。この定義とは異なる定義を用いるものもある。例えば、それを用いると奇数のみを擬素数にすることができる。
"x"と互いに素である全ての値をとる"a"に対してフェルマー擬素数である整数"x"はカーマイケル数と呼ばれる。