Continue(s)

Twitter:@dn0t_ GitHub:@ogrew

Rustでフェルマーテストを実装する

はじめに

前回に引き続き、整数論の勉強中に知った知識をRustで実装するシリーズです。

今回の流れは、以下の通りです。

素数の性質を示すフェルマーの小定理を紹介します。

②それを利用したシンプルな素数判定の方法(フェルマーテスト)をRustで実装します。

③しかし、このテストは絶対ではない、あくまで確率的な素数判定方式であるということを解説し、その回避方法を示して実験します。

④さらに、その回避方法を持ってしても失敗する(合成数なのに素数だと判定されてしまう)不思議な数、カーマイケル数のことを紹介します。


フェルマーの小定理

まずはじめに、今回の肝となる定理を紹介します。

素数 p と任意の自然数 a が互いに素であるとき、a^{p-1}-1p で割り切れる。

たった、これだけです。

(この定理をより一般化したものが、よくRSA暗号方式の背景として紹介されるオイラーの定理です。)

フェルマーテストの実装

我々がやりたいことは素数判定であり、それもエラトステネスの篩のような愚直なアルゴリズムでは計算量が莫大すぎてやりたくない桁数のものです。

これを実現するための判定方式の一つとしてフェルマーテストがあります。これは先ほど紹介したフェルマーの小定理対偶を使います。

フェルマーの小定理の待遇は次の様になります。

自然数 an が互いに素で a^{n-1}-1n で割り切れないとき、 p合成数である。

これを判定基準として任意の数が素数であるかどうかを見極めるアルゴリズムを実装します。

ソースコード

gist.github.com

実験

$ cargo run 71 2
...
[a = 2] 71 is probably prime number

$ cargo run 809 2
...
[a = 2] 809 is probably prime number

$ cargo run 3827 2
...
[a = 2] 3827 is composite number

$ cargo run 709507 3
...
[a = 3] 709507 is probably prime number

素数

先ほどのテストに今度は n = 341 を投げてみます。すると、素数であると判定されます。

$ cargo run 341 2
...
[a = 2] 341 is probably prime number

しかし、 341=11\times31合成数です。テストをすり抜けてしまいました。

実はフェルマーテストは完全な素数判定法ではありません。

このような合成数素数に擬態する合成数ということで"擬素数"(Pseudoprime)と呼びます。

なぜこのようなことが起きてしまうのかを整理しておくと、元の定理が「素数ならXを満たす」というものなので、その待遇は「Xを満たさないなら素数でない(=合成数である)」というものなので「素数でない(=合成数)がXを満たす」ものを検知できないのです。

この検知できない合成数、擬素数の存在は素数判定において非常に厄介ですが、実は底となる数 a の値を複数試すと正しく判定する場合もあります。

$ cargo run 341 3
...
[a = 3] 341 is composite number

カーマイケル数

それでは、今度は n = 561 という数字でテストしてみます。

$ cargo run 561 2
...
[a = 2] 561 is probably prime number

しかし、561=3\times11\times17 であり、合成数です。底の数を変えてみます。

$ cargo run 561 5
...
[a = 5] 561 is probably prime number

$ cargo run 561 7
...
[a = 7] 561 is probably prime number

むむむ、結果はやはり素数と判定されてしまいます。

実は n = 561 はどのように底の自然数をとってもフェルマーテストをパスしてしまう意地悪な擬素数なのです。

このような数のことをアメリカの数学者から名前を取ってカーマイケル数と呼びます。小さい方から順に n = 561, 1105, 1729, 2465, 2821 ... と続き、無限に存在することも証明されています。

しかし、カーマイケル数は実はそこまで数は多くなく 10^{4} 未満の数のうちだと 22 個存在しています。

おわりに

今回は確率的素数判定法の1つフェルマーテストとそれを見事にすり抜けるカーマイケル数についてを紹介しました。

フェルマーテストは絶対ではありませんが、効率よく高確率で素数かどうかをうまく判定します。さらにこれを改良した判定法にミラーラビンテストというのがありますが、私がまだ理解していないので名前のみの紹介とします。

気になる方は調べてください。

参考