C言語で多倍長整数計算 GMPライブラリを使ってみた -002-

 GMPライブラリを使ってC言語フェルマーテスト(合成数判定関数)を実装した。

素数判定と言えば、まずはこんな形を思いつく。

まあずいぶんと適当だが、始めに 2 と 2 の倍数を処理して、後は奇数について √n 以下の整数で割った剰余を求め、それが 0 なら合成数(素数でない2以上の整数)と判定する。

欠点は、素数以外で割っているのが無駄であること。nが巨大な自然数のとき、演算数が膨大になること(当然このままの形ではそんな整数は扱えないが)。「合成数は合成数であると見抜ける式でないと(素数判定は)難しい」 そこで、フェルマーテストを実装してみることにした。名前が、かっこいいでしょう?

[参考] フェルマーの小定理 – Wikipedia #フェルマーテスト

フェルマーテストは、素因数分解をすることなく、合成数なら合成数だと分かるテストである。素数なら素数と分かるテストではない。したがって、これだけでは厳密な素数の判定はできないことに注意されたい。詳しくはフェルマーテストでググれば(ry

まず、変数の初期化処理が面倒なので一行で書けるような関数を組んだ。

[my_gmp.h]

フェルマーの小定理は、互いに素である底と乗数について成り立つので、二つの整数が互いに素であるかどうかを判定する関数を組んだ。ユークリッドの互助法を用いてもよかったが、最大公約数を求める関数がGMPにあるのでそれを利用した。

[参考] 互いに素 – Wikipedia

続いて、フェルマーテストの実装。フェルマーの小定理自体、式が1つなので、実装も至ってシンプルである。

まず coprime関数 で 底a と n が互いに素かどうかをみて、互いに素であればフェルマーテストを行う。フェルマーテストを通った自然数は、素数の可能性が高い。一方、フェルマーテストに落ちた自然数は合成数である。したがって、フェルマーテストを通った自然数(擬素数)は別のテストを行って素数かどうかを判定する必要がある。

ちなみに、フェルマーテストは単純なだけに欠点が多く、このままだと実用的かどうか怪しい感じらしい。これを改善したものにミラー-ラビン素数判定法というものがあるが、実はこれを利用した確率的素数判定関数がGMPで実装されている

[参考] ミラー-ラビン素数判定法 – Wikipedia
[参考] Number Theoretic Functions – GNU MP 5.0.1

例えば、((2^61)-1)^2 = 5,316,911,983,139,663,487,003,542,222,693,990,401 なんていう数は、冒頭で示したような Brute Force アルゴリズムではかなり辛いものがあるが、これは合成数なのでフェルマーテストを使うと一瞬で合成数だと見抜ける。素晴らしい。

C言語で多倍長整数計算 GMPライブラリを使ってみた -001-

C99では long long int なる64bitの整数型も登場し、unsigned long long int であれば 0 から (2^64)-1 = 18,446,744,073,709,551,615 までの整数が扱える。10進数で19桁は扱えることになる。

[参考] long long int 型 – seclan のほえほえルーム

ところが、math.hライブラリを使わずに sqrt(2) を求めてみようだとか、10番目のメルセンヌ素数を求めてみたいだとか、そういう段になるととてもじゃないが long long int では太刀打ちできない。

こういった、いわゆる「多倍長整数」を扱うには、それなりの仕組みが必要だ。unsigined int を基本として自分で実装してもよいが、C言語には GMP という多倍長演算のためのライブラリがあるので、それを利用するとよい。

[参考] The GNU MP Bignum Library (本家)

[参考] GNU Multi-Precision Library – Wikipedia

今回私はCygwinから利用したので、その記録をまとめておく。

Cygwinのインストール時に、Mathをすべてinstallにしておくと、GMPも含まれる。Math系は何かと利用頻度が高くなるので全部インストールしておこう(笑)。ただし、Cygwinのインストールで同時にインストールできるGMPはバージョンが最新でないので、最新版がいい人は本家サイトからダウンロードしてソースからmakeする。Cygwin上でmakeコマンドが見つからなくてできない!というひとは、インストール時にDevelをすべてinstallにしておこう。Devel系は何かと利用頻度が高くなるので全部(ry

[参考] GMPの使い方 (Cygwin上での最新版GMPのインストール方法がある)

CでGMPを利用するのに必要なのは、<gmp.h>のインクルードと、コンパイル時の -lgmp オプションだ。以下に簡単なサンプルを掲載する。

つまり、r に 2 の 100乗を代入し、それを表示するコードだ。

コンパイルおよび実行は以下のように行う。

計算結果が疑わしいと思う人は、ぜひ筆算で検算してみて欲しい。コンピュータのありがたみがよくわかる。(ぇ

本家Webサイトの上部にあるマニュアル(Documentation)のリンクをたどると、他にどんな関数が用意されているかが分かる。ジャンル別に分類されているので分かりやすいと思う。演算の種類は結構豊富なので、普通の計算をするだけならまず困ることはないだろう。中にはGCD(最大公約数)を求める関数まで用意されている。なんかもう普段から使いたくなってくるくらい便利だ。

[参考] GNU MP 4.3.2

[参考] GNU MP 5.0.1