擬なずらえ素数そすう

擬なずらえ素数そすう（ぎそすう、英えい：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はカーマイケル数すうと呼よばれる。

擬なずらえ素数そすうの例れい[編集へんしゅう]

脚注きゃくちゅう[編集へんしゅう]

注釈ちゅうしゃく[編集へんしゅう]

^ 対象たいしょうの性質せいしつを持もっている数すう全体ぜんたいを（素数そすうも含ふくめて）擬なずらえ素数そすうと呼よぶ場合ばあいもある。

出典しゅってん[編集へんしゅう]

^ 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.wolfram.com (英語えいご).

[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.wolfram.com (英語えいご).

[注ちゅう 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$
素数そすうの一覧いちらん