現在は 試し割り法 フェルマー・テスト ミラー・ラビン素数判定法 の3つの種類があります。
背景は動かんよ Trial Division 1→試し割り法(決定的アルゴリズム) Trial Division 2→Trial Divisionを効率化したもの(決定的アルゴリズム) Fermat test1→互除法を使用して互いに素を確認し、互いに素であればフェルマーテスト、互いに素でなければその場でCompositeと返す決定的アルゴリズム。 Fermat test2→なんでもいいからフェルマーテストを使う決定的アルゴリズム。 Fermat test3→フェルマーテストかつ高速(ただしカーマイケル数をProbably Primeとしてしまう確率が高い。)(確率的アルゴリズム) Miller-Rabin test1→すべての自然数に対して行うミラーラビン素数判定法(決定的アルゴリズム) Miller-Rabin test2→乱数を使用したミラーラビン素数判定法(確率的アルゴリズム)(誤判定される確率は約4⁻¹⁰⁰%)
