素数判定アルゴリズム - projectpn

古今東西の様々な素数判定・素因数分解アルゴリズム。
まだ作りかけです。

基本

試し割り法(trial division)

単一の数字の素数判定に向いているアルゴリズム

確率的素数判定アルゴリズム

• フェルマーテスト(Fermat primality test)
• Solovay-Strassen素数判定法(Solovay-Strassen primality test)
• ミラー・ラビン素数判定法(Miller–Rabin primality test)
• Baillie-PSW素数判定法

決定的素数判定アルゴリズム

• AKS素数判定法
• 楕円曲線素数証明

特殊な数にのみ使えるアルゴリズム

• リュカ-レーマーテスト(Lucas-Lehmer primality test)

多数の数字の素数判定に向いているアルゴリズム

• エラトステネスの篩
• アトキンの篩

素因数分解アルゴリズム

• p-1法
• p+1法
• ポラード・ロー法