ミラー・ラビン素数判定法の手順とは？初期化からステップkまでをわかりやすく解説

ミラー・ラビン（Miller-Rabin）素数性テストは、フェルマーテストと平方根テストを組み合わせて強い擬素数を見つけ出すための古典的な手法です。このテストでは、まず n − 1 を「奇数 m」と「2 の冪」の積として表現します。

$$\mathrm{n-1 = m \times 2^{k}}$$

底 a を用いたフェルマーテストは、次のように変形できます。

$$\mathrm{a^{n-1} = a^{m \times 2^{k}} = \left[ a^{m} \right]^{2^{k}}}$$

つまり、aⁿ⁻¹ (mod n) を一括で計算するのではなく、k+1 段階に分けて計算できるのです。段階を分ける最大の利点は、各段階ごとに平方根テストを実施できる点にあります。平方根テストに失敗した時点で処理を打ち切り、その場で n を合成数と宣言できるため、無駄な計算を省略できます。

各段階では、フェルマーテストを満たしているかどうかに加えて、「隣接する段階の間で平方根テストが成立しているか」（つまり結果が 1 になるか）を確認します。

初期化（Initialization）

• 底 a を選び、T = a^m を計算します。ここで m = (n−1)/2^k です。

• T が +1 または −1 の場合、n は強い擬素数であると宣言して終了します。T が ±1 であれば、次の段階で T は 1 となり、以降も 1 のまま推移してフェルマーテストを通過するためです。さらに、T は平方根テストも満たしています。次の段階で T が 1 になれば、1 の平方根は ±1 だからです。

• T がそれ以外の値の場合、n が素数なのか合成数なのかはまだ判断できません。次の段階へ進みます。

ステップ1

T を二乗します。

• 結果が +1 の場合：以降の段階でも T は 1 のまま推移するため、フェルマーテストは確実に合格します。しかし、この段階で T が 1 であり、直前の段階で ±1 以外だったということは、平方根テストに不合格です。ここで n を合成数と宣言して停止します。

• 結果が −1 の場合：T はこの段階で −1 であり、次の段階で 1 になるため、フェルマーテストと平方根テストの両方を最終的に満たすことが分かります。n を強い擬素数と宣言して停止します。

• それ以外の場合：素数かどうかの判断はまだできません。次の段階へ進みます。

ステップ2〜ステップ k−1

これらの段階では、ステップ1とまったく同じ手順を繰り返し適用していきます。

ステップ k

この段階は実行する必要がありません。ここまで到達しても決定に至っていない場合、この段階は判定に役立つ情報を何ら提供しないためです。仮にこの段階の結果が 1 であっても、フェルマーテスト自体は満たすものの、直前の段階の結果が ±1 ではないため、平方根テストには不合格となります。ステップ k−1 を実行しても停止しなかった場合は、そこで n を合成数と宣言します。ミラー・ラビンテストは、ステップ0からステップ k−1 までの実行だけで十分です。

判定フローのまとめ

• 初期化時に T = ±1 → 強い擬素数（素数の可能性あり）として終了
• 二乗の結果が −1 → 強い擬素数（素数の可能性あり）として終了
• 二乗の結果が +1 かつ直前の値が ±1 以外 → 合成数として終了
• ステップ k−1 まで決定が出ない → 合成数と判定