擬素数とは？わかりやすく解説

擬素数（ぎそすう、英：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
強い擬素数（英語版）

脚注

注釈

^ 対象の性質を持っている数全体を（素数も含めて）擬素数と呼ぶ場合もある。

出典

^ Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-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.
^ Weisstein, Eric W. "Fermat Pseudoprime". MathWorld (英語).

[1] 対象の性質を持っている数全体を（素数も含めて）擬素数と呼ぶ場合もある。

[2] Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-2

[3] 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.

[4] Weisstein, Eric W. "Fermat Pseudoprime". MathWorld (英語).

[注 1]

[1]

[2]

[3]

表話編歴素数の分類
生成式	フェルマー ( $2 2 n + 1$ ) メルセンヌ ( $2 p - 1$ ) 二重メルセンヌ ( $2 2 p -1 - 1$ ) ワグスタッフ ( $(2 p + 1)/3$ ) プロス ( $k \cdot2 n + 1$ ) 階乗 ( $n! \pm 1$ ) 素数階乗 ( $p n # \pm 1$ ) ユークリッド ( $p n # + 1$ ) ピタゴラス ( $4 n + 1$ ) ピアポント ( $2 u \cdot3 v + 1$ ) Quartan（英語版） ( $x 4 + y 4$ ) ソリナス（英語版） ( $2 a \pm 2 b \pm 1$ ) カレン ( $n \cdot2 n + 1$ ) ウッダル ( $n \cdot2 n - 1$ ) Cuban（英語版） ( $(x 3 - y 3)/(x - y)$ ) キャロル ( $(2 n - 1) 2 - 2$ ) Kynea ( $(2 n + 1) 2 - 2$ ) レイランド ( $x y + y x$ ) サービト（英語版） ( $3\cdot2 n - 1$ ) ミルズ ( $[A] 3 n$ )
漸化式（英語版）	フィボナッチリュカペルニューマン–シャンクス–ウィリアムズペラン分割ベルモツキン
各種の性質	ヴィーフェリッヒ（英語版） (対（英語版）) ウォール–孫–孫（英語版）ウォルステンホルムウィルソン幸運フォーチュンラマヌジャン（英語版）ピライ正則強（英語版）スターン Supersingular (楕円曲線)（英語版） Supersingular (ムーンシャイン理論)（英語版）良いスーパーヒッグス（英語版）高度コトーティエント（英語版）
基数依存	ハッピー二面（英語版）回文エマープレピュニット ( $(10 n - 1)/9$ ) 置換可能 Circular（英語版）切り捨て可能 Strobogrammatic（英語版） Minimal（英語版）弱いフルサイクルプライム Unique（英語版） Primeval（英語版）自己スマランダチェ–ウェラン（英語版）
組	互いに素双子 ( $p, p + 2$ ) Bi-twin chain ( $n - 1, n + 1, 2 n - 1, 2 n + 1, \dots$ ) 三つ子 ( $p, p + 2$ or $p + 4, p + 6$ ) 四つ子 ( $p, p + 2, p + 6, p + 8$ ) k−Tuple いとこ ( $p, p + 4$ ) セクシー ( $p, p + 6$ ) 陳ソフィー・ジェルマン ( $p, 2 p + 1$ ) カニンガム鎖 ( $p, 2 p \pm 1, \dots$ ) 安全 ( $p, (p - 1)/2$ ) 算術数列（英語版） ( $p + an; n = 0, 1, \dots$ ) 平衡 ( $p - n, p, p + n$ )
桁数	タイタニック ( $103$ 桁以上) 巨大 ( $104$ 桁以上) メガ ( $106$ 桁以上)
複素数	アイゼンシュタイン素数（英語版）ガウス素数
合成数	擬素数概素数半素数楔数 Interprime（英語版）
関連する話題	確率的素数 Industrial-grade prime（英語版）違法素数素数の公式（英語版）素数の間隔『巨大な素数の一覧』
最初の50個	$2$ $3$ $5$ $7$ $11$ $13$ $17$ $19$ $23$ $29$ $31$ $37$ $41$ $43$ $47$ $53$ $59$ $61$ $67$ $71$ $73$ $79$ $83$ $89$ $97$ $101$ $103$ $107$ $109$ $113$ $127$ $131$ $137$ $139$ $149$ $151$ $157$ $163$ $167$ $173$ $179$ $181$ $191$ $193$ $197$ $199$ $211$ $223$ $227$ $229$
素数の一覧

擬素数とは？ わかりやすく解説

擬素数

フェルマー擬素数

擬素数の例

脚注

注釈

出典

急上昇のことば

「擬素数」の関連用語

擬素数とは？わかりやすく解説