アルゴリズム論特論（塩田）第9回 (1) フェルマ・テスト
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
フェルマの小定理を用いた合成数判定
まずは復習から。
Th.1（フェルマの小定理） $p$ が素数、$b$ が $p$ で割り切れない整数ならば
$b^{\,p-1} \equiv 1 \pmod{p}$
この対偶を取ると
Cor.2（合成数判定） $n$ で割り切れない整数 $b$ が
$b^{\,n-1} \not\equiv 1 \pmod{n}$
を満たすならば $n$ は素数ではない。
Ex.3 $n=1357$, $b=3$ とします。もちろん $3$ は $1357$ では割り切れず、
$b^{\,n-1} = 3^{1356} \equiv 487 \not\equiv 1 \pmod{1357}$
となるので $n=1357$
は素数ではない ことがわかります。
実際 $1357 = 23 \times 59$ です。
間違えていけないのは
「$b^{\,n-1} \equiv 1 \pmod{n}$ ならば $n$ は素数である」
とは必ずしも言えない、ということです。
ここ大事！
Ex.4 $n=341$, $b=2$ とします。$2$ は $341$ では割り切れず、
$b^{\,n-1} = 2^{340} \equiv 1 \pmod{341}$
が成り立ちます。しかし $341 = 11 \times 31$ ですから $341$ は素数ではありません。
（このように、合成数 $n$ と、$n$ で割り切れない整数 $b$ が
$b^{\,n-1} \equiv 1 \pmod{n}$
を満たすとき、「$n$ は $b$ を底とする 擬素数 である」と言います。）
とは言え、
Cor.2 は合成数をはじくことには使えますので、
不完全ながら次のような素数判定法が考えられます。
フェルマ・テスト
Algorithm 5 (フェルマ・テスト)
- 入力：大きな自然数 $n$
- 出力：False ⇒ $n$ は確実に合成数, True ⇒ $n$ は素数かもしれない
def FermatTest($n$):
for $b$ in [2, 3, 5, 7, 11]:
if $b^{n-1}\, \% \, n \neq 1$ :
return False
return True
$b=2,3,5,7,11$ の 5 つの底に対して
$b^{\,n-1} \equiv 1 \pmod{n}$
が成り立てばさすがに $n$ は素数なんじゃないの、というアイデアです。
実際、
Alg.5 で True となる合成数は 100万以下で 15 個、1 億以下で 143 個しかありません。
用いる底を $b=2,3,5,7,11,13,17,19,23,29$ の 10 個に増やすと、1 億以下で誤判定される合成数は 75 個に減ります。
- $b$ をランダムに選ぶ version もあります。
- 実装の際には $b^{\,n-1}\,\%\,n$ の計算には前回勉強した高速べき乗法を用います。