Miller-Rabin法という確率的に素数かどうかを判定するアルゴリズムをRubyの
みで実装してみました。

 モジュール
 http://blue.h2np.net/sd/mathh.rb

 テスト用のプログラム
 http://blue.h2np.net/sd/mathh-test.rb


使っているアルゴリズムは、ごくごく普通の方法です(*1)が、さらに処理量を
少なくする実装上の工夫も施しています。

 (*1)参考 URL
 http://www.cs.albany.edu/~berg/csi445/Assignments/pa4.html


拡張ユーグリッド互除法を使って有限体上での逆数を求める a^-1 (= 1 mod m )
も入っています。

興味があれば、どうぞ。あとバグがあれば教えてください。

-- 
鈴 木 裕 信 (Hironobu SUZUKI)
E-Mail: hironobu / h2np.net
URL: http://h2np.net