Skip to content

MillerRabin

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

MillerRabin

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
miller_rabin.php
miller_rabin.php
 
 
miller_rabin.py
miller_rabin.py
 
 

README.md

ミラー・ラビン素数判定法とは？

ミラー・ラビン法は、ある整数 $N$ が素数かどうかを高速かつ高確率で判定できる確率的アルゴリズムです。

1. 素数の性質を利用

フェルマーの小定理によると、 素数 $p$ と $1 \le a < p$ のとき

$$ a^{p-1} \equiv 1 \pmod{p} $$

が成り立ちます。

しかしこれだけだと「フェルマー擬似素数」という例外もあり、完全判定できません。

2. ミラー・ラビン法の仕組み

ミラー・ラビン法は、次のように $N-1$ を $2^r \times d$ の形に分解します（$d$ は奇数）。

$$ N-1 = 2^r \times d $$

3. 判定の流れ（図解）

以下の図で判定の流れを説明します。

N - 1 = 2^r * d   (dは奇数)

Choose a base 'a' (2 ≤ a ≤ N-2)

Compute x = a^d mod N

+-------------------------+
|                         |
|       x == 1 or x == N-1?  <-- Yes --> "Probably prime" for this base
|                         |
+-----------+-------------+
            |
            No
            |
            v
Repeat r-1 times:
   x = x^2 mod N
   If x == N-1 --> "Probably prime"
   Else continue

If none is N-1 --> "Composite"

4. 図にするとこんな感じです

Start:
   Compute x = a^d mod N

+------------------+
|  x == 1 or N-1 ? |-- Yes --> probably prime (test next base or finish)
+------------------+
         |
         No
         |
         v
Loop (r-1) times:
    x = x^2 mod N
    +------------------+
    |  x == N-1 ?      |-- Yes --> probably prime (break loop)
    +------------------+
            |
            No
            |
Loop continues

If loop ends without x == N-1:
    return Composite

5. なぜこの判定で良いのか？

  • 素数ならば、上の条件を必ず満たします。
  • 合成数は「強擬似素数」と呼ばれるもの以外は、このテストで検出されます。
  • 複数の異なる基数 $a$ を試すことで誤判定の確率を限りなく下げられます。

6. 例：$N = 561$（カルマイケル数）

$N = 561$ はフェルマー法では素数判定される場合がありますが、ミラー・ラビン法では判定されやすいです。

7. まとめ

ステップ 内容
1 $N-1$ を $2^r \times d$ に分解
2 基数 $a$ を選び、 $x = a^d \mod N$ を計算
3 $x = 1$ または $N-1$ なら合格
4 そうでなければ、$r-1$ 回繰り返し $x = x^2 \mod N$ を計算し、$N-1$ なら合格
5 それ以外は合成数と判定