はじめに
前回に引き続き、整数論の勉強中に知った知識をRustで実装するシリーズです。
今回の流れは、以下の通りです。
②それを利用したシンプルな素数判定の方法（フェルマーテスト）をRustで実装します。
③しかし、このテストは絶対ではない、あくまで確率的な素数判定方式であるということを解説し、その回避方法を示して実験します。
④さらに、その回避方法を持ってしても失敗する（合成数なのに素数だと判定されてしまう）不思議な数、カーマイケル数のことを紹介します。
フェルマーの小定理
まずはじめに、今回の肝となる定理を紹介します。
たった、これだけです。
（この定理をより一般化したものが、よくRSA暗号方式の背景として紹介されるオイラーの定理です。）
フェルマーテストの実装
我々がやりたいことは素数判定であり、それもエラトステネスの篩のような愚直なアルゴリズムでは計算量が莫大すぎてやりたくない桁数のものです。
これを実現するための判定方式の一つとしてフェルマーテストがあります。これは先ほど紹介したフェルマーの小定理の対偶を使います。
フェルマーの小定理の待遇は次の様になります。
これを判定基準として任意の数が素数であるかどうかを見極めるアルゴリズムを実装します。
ソースコード
実験
$ 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
擬素数
先ほどのテストに今度は を投げてみます。すると、素数であると判定されます。
$ cargo run 341 2 ... [a = 2] 341 is probably prime number
しかし、 の合成数です。テストをすり抜けてしまいました。
このような合成数を素数に擬態する合成数ということで"擬素数"(Pseudoprime)と呼びます。
なぜこのようなことが起きてしまうのかを整理しておくと、元の定理が「素数ならXを満たす」というものなので、その待遇は「Xを満たさないなら素数でない（＝合成数である）」というものなので「素数でない（＝合成数）がXを満たす」ものを検知できないのです。
この検知できない合成数、擬素数の存在は素数判定において非常に厄介ですが、実は底となる数 の値を複数試すと正しく判定する場合もあります。
$ cargo run 341 3 ... [a = 3] 341 is composite number
カーマイケル数
それでは、今度は という数字でテストしてみます。
$ cargo run 561 2 ... [a = 2] 561 is probably prime number
しかし、 であり、合成数です。底の数を変えてみます。
$ cargo run 561 5 ... [a = 5] 561 is probably prime number $ cargo run 561 7 ... [a = 7] 561 is probably prime number
むむむ、結果はやはり素数と判定されてしまいます。
実は はどのように底の自然数をとってもフェルマーテストをパスしてしまう意地悪な擬素数なのです。
このような数のことをアメリカの数学者から名前を取ってカーマイケル数と呼びます。小さい方から順に と続き、無限に存在することも証明されています。
しかし、カーマイケル数は実はそこまで数は多くなく 未満の数のうちだと
個存在しています。
おわりに
今回は確率的素数判定法の1つフェルマーテストとそれを見事にすり抜けるカーマイケル数についてを紹介しました。
フェルマーテストは絶対ではありませんが、効率よく高確率で素数かどうかをうまく判定します。さらにこれを改良した判定法にミラーラビンテストというのがありますが、私がまだ理解していないので名前のみの紹介とします。
気になる方は調べてください。
