擬素数

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

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