|
素数生成ソフト 「CKPrime」 |
| 「CKPrime」開発の経緯 |
以前、インターネット等で広く使用されているRSA暗号について調べたことがあります。
RSA暗号で使用される公開鍵には巨大素数の積が利用されますが、これは現実的な時間範囲内でその積を素数に分解しなおすことが難しいことに基づいています。
C#言語を使い、手持ちのパソコンで巨大素数を取り扱うソフトウエアが作れないかと考えてみたのですが、100桁を超えるような桁数の多い整数を取り扱うデータ型がありませんでした。
2010年5月にリリースされたVisual C# 2010に新しくBigIntegerクラスが追加され、桁数に制限のない整数が利用できるようになったことを知り、BigIntegerを使う練習として、このソフトウエアを作ってみました。
| 「CKPrime」の概要 |
このソフトウエアは、素数に関する以下の操作を行うものです。
① 原始的方法による素数の判定
② Miller-Rabin法
による素数候補の抽出
③ Miller-Rabin法による素数の詳細チェック
④ 素数リスト作成
| ソフトウエアの動作環境 |
対応ＯＳ：Windows XP(SP3), Windows Vista(SP1以降), Windows 7
.NET Framework 4 が必要です。
| 評価テストに使用したパソコンのハードとソフト |
CPU：Intel Core2 CPU, 2.4GHz
RAM：2GB
OS：Windows7 Professional(32bit)
| ソフトウエアの画面構成と使い方 |
①［原始的方法による素数の判定］画面
素数判定のアルゴリズム
2、3、判定対象数の平方根以下で3の倍数でない正の奇数を除数として、判定対象数を除算します。判定対象数がどの数でも割り切れない場合に、これを素数と判定します。
この方法によって素数の正確な判定ができますが、対象数の桁数が大きくなると判定に莫大な時間がかかります。
画面の操作
判定対象数を入力してから[判定]ボタンをクリックすると、素数の判定が行われ、結果が表示されます。
評価テスト結果
素数「46116646144580591」(17桁)の判定時間 33秒
素数「4611664614458057389」(19桁)の判定時間 5分24秒
素数「46116646144580573897」(20桁)の判定時間 26分19秒
素数「461166461445805738999」(21桁)の判定時間 108分27秒
②［素数候補の抽出］画面
素数候補抽出のアルゴリズム
この画面ではMiller-Rabin判定法を用いて、素数の可能性が高い数を抽出します。
Miller-Rabin判定法で使用される底の数値は、判定対象数と互いに素であることが必要です。そこで、この画面では100以下の全ての素数(25個)を底として判定を行います。
画面に入力された出発数値を判定対象数として判定を開始します。判定対象数が合成数と判定された場合には、3の倍数ではない次の奇数を判定対象数として判定を行い、合成数と判定されない数(素数候補)が得られるまで判定対象数を変更して判定操作を続けます。
Miller-Rabin判定法では素数であることの確定はできません。この画面の操作で得られた素数候補が素数である確率は、以下のようになります。
(1 - (1/4)^25) Ｘ 100 = 99.999999999999911 ％
画面の操作
出発数値を入力してから、[抽出]ボタンをクリックすると、出発数値以上で、合成数と判定されない最小の整数が抽出・表示されます。
評価テスト結果
174桁の整数
1881988129206079638386972394616504398071635633794173827007633564229888
5971523466548531906060650474304531738801130339671619969232120573403187
9550656996221305168759307650257059
を出発数値として、素数候補
1881988129206079638386972394616504398071635633794173827007633564229888
5971523466548531906060650474304531738801130339671619969232120573403187
9550656996221305168759307650257581
を得るまでの所要時間 2386ミリ秒
③［素数の詳細チェック］画面
素数チェックのアルゴリズム
Miller-Rabin判定法を用い、使用する底の数を増やして、確率の高い素数判定を行います。
画面の操作
対象数値と底の下限値、上限値を入力してから、[開始]ボタンをクリックすると、下限値と上限値の間の素数を底としたMiller-Rabin判定法による素数チェックが行われ、結果が表示されます。
評価テスト結果
底の上限値を20000として、次の174桁整数の詳細チェックを実施
1881988129206079638386972394616504398071635633794173827007633564229888
5971523466548531906060650474304531738801130339671619969232120573403187
9550656996221305168759307650257581
判定結果
判定に使用した底の数：2262
判定所要時間：18秒
対象数が素数でない確率：1.4×(10のマイナス1362乗)
④［素数リスト作成］画面
素数リスト作成のアルゴリズム
この画面では、2、3、5と、7以上で、入力された最大数までの3の倍数でない正の奇数を、①の原始的素数判定方法と同様の方法で判定し、素数と判定されたものをリストアップします。
画面の操作
最大数を入力してから、[取得]ボタンをクリックすると、素数リストが作成されます。
素数リストをファイルに書き込み、これを読取り専用の隠しファイルとして保存します。
最大数には、long型の最大値 9223372036854775807 (19桁)までしか入力できません。
評価テスト結果
最大数 10000000, 作成所要時間 9秒, リストのファイルサイズ 5.7MB
最大数 100000000, 作成所要時間 3分42秒, リストのファイルサイズ 55.5MB
最大数 1000000000, 作成所要時間 81分22秒, リストのファイルサイズ 539.8MB
| ダウンロード |
| ご質問・ご意見・ご感想 |
ご質問、ご意見、ご感想、バグ等のご連絡は、
こちらへ