About: 擬素数

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