ミラー-ラビン素数判定法は、与えられた数が素数であるかを確率的に判定するアルゴリズムです。確定的な素数判定法ではありませんが、高速であり、実用上十分な精度で素数判定を行うことができます。特に大きな数の素数判定に有効です。 前提知識：フェルマーの小定理 ミラー-ラビン素数判定法の仕組み なぜこれで素数判定ができるのか 具体例：n = 561 (合成数) の場合 まとめ 前提知識：フェルマーの小定理 ミラー-ラビン素数判定法の理解には、フェルマーの小定理が基礎となります。 フェルマーの小定理 p が素数であり、a が p と互いに素な整数であるとき、以下の式が成り立ちます。 a(p - 1) ≡ …
ja.wikipedia.org