擬素数

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

擬素数(ぎそすう、英:pseudoprime)は、実際には素数ではない確率的素数(en:probable prime、全ての素数に共通の性質を持つ整数)。擬素数は、それが満たす素数の特性により分類される。

擬素数という用語を全ての概素数(合成数と本当に素数である数の両方)とするものもある。

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

フェルマー擬素数[ソースを編集]

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

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

分類[ソースを編集]

脚注[ソースを編集]

  1. ^ Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-2. 
  2. ^ Cipra, Barry Arthur (December 23, 1988). “PCs Factor a 'Most Wanted' Number”. Science 242: 1634–1635. doi:10.1126/science.242.4886.1634. PMID 17730568. 
  3. ^ Weisstein, Eric W. "Fermat Pseudoprime". MathWorld(英語).