C++ で巨大素数を判定・生成する

Python を使った最も基本的なプログラムとして、画面（ターミナル）にメッセージを表示するプログラムを作る。1行メッセージを表示するものと、プログラムが得意とする繰り返し処理を使った複数行のメッセージを表示する、2つのプログラムを作っていく。

「PHPで巨大素数の生成と判定」をC++に移植した。同じGMPライブラリを使用し、コマンドライン・プログラムなので、Windowsだけではなく、他のOSでも動作するソース・プログラムになっている。

（2024年11月3日）使用ライブラリ更新
（2024年7月7日）使用ライブラリ更新
（2024年2月17日）英語表記追加(-eオプション)，使用ライブラリ等を更新

サンプル・プログラム
使用ライブラリ
ビルド
解説：ミラー・ラビン素数判定プログラム
解説：指定した桁数の巨大素数を求める
解説：コマンドラインオプションの定義と取得
解説：指定した文字列が整数かどうかを判定する
参考サイト

サンプル・プログラム

ダウンロード

圧縮ファイルの内容
bigprime.exe	実行プログラム本体（CUI版）
bigprime.cpp	ソース・プログラム
makefile	ビルドファイル

bigprime.cpp 更新履歴
バージョン	更新日	内容
1.1.2	2024/11/03	使用ライブラリ更新
1.1.1	2024/07/07	使用ライブラリ更新
1.1.0	2024/02/17	英語表記追加(-eオプション)，使用ライブラリ等を更新
1.0.2	2023/10/08	使用ライブラリ更新
1.0.1	2023/05/28	使用ライブラリ更新

使用ライブラリ

多倍長整数演算するためにライブラリ GMP が必要になる。
コマンドライン・オプションを操作する場合などに、オープンソースのライブラリ Boost C++ライブラリが必要になる。
各々の導入方法等については、「C++ 開発環境の準備」をご覧いただきたい。

ビルド

ビルドするには同梱の "makefile" を利用してほしい。

解説：ミラー・ラビン素数判定プログラム

bigprime.cpp

159: /**
160:  * べき剰余を求める．
161:  * @param  mpz_class base 基数
162:  * @param  mpz_class exp  指数
163:  * @param  mpz_class mod  除数
164:  * @return mpz_class べき剰余
165: */
166: mpz_class modpow(mpz_class base, mpz_class exp, mpz_class mod) {
167:     mpz_class res = 1;
168:     while (exp > 0) {
169:         if ((exp & 1) == 1) {
170:             res = (res * base) % mod;
171:         }
172:         base = (base * base) % mod;
173:         exp >>= 1;
174:     }
175:     return res;
176: }

bigprime.cpp

178: /**
179:  * 指定した整数をミラー・ラビン判定法を使って素数かどうかを判定する．
180:  * @param   mpz_class n  判定したい整数
181:  * @return  bool true:素数である／false:素数でない
182: */
183: bool millerRabinPrimalityTest(mpz_class n) {
184:     if (n <= 1)      return false;
185:     if (n == 2)     return true;
186:     if (n % 2 == 0) return false;
187:     vector<mpz_class> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
188:     mpz_class s = 0, d = n - 1;
189:     while (d % 2 == 0) {
190:         s++;
191:         d >>= 1;
192:     }
193:     for (auto a : A) {
194:         if (a % n == 0) return true;
195:         mpz_class t, x = modpow(a, d, n);
196:         if (x != 1) {
197:             for (t = 0; t < s; ++t) {
198:                 if (x == n - 1)     break;
199:                 x = x * x % n;
200:             }
201:             if (t == s) return false;
202:         }
203:     }
204:     return true;
205: }

ミラー・ラビン素数判定については、「PHPとPythonで巨大素数を扱う」をご覧いただきたい。

mpz_classはGMPの多倍長整数のC++によるラッパークラスで、四則演算など、多倍長整数計算をintとほぼ同じように取り扱うことができる。

解説：指定した桁数の巨大素数を求める

bigprime.cpp

207: /**
208:  * 指定した桁数の巨大素数を求める．
209:  * @param   mpz_class *prime 素数を格納する
210:  * @param   long num 桁数
211:  * @return  なし
212: */
213: void getBigPrime(mpz_class *prime, unsigned long num) {
214:     bool ret;
215:
216:     //多倍長整数構造体を初期化する．
217:     mpz_t a;
218:     mpz_init(a);
219:     mpz_t n;
220:     mpz_init(n);
221:     mpz_t b;
222:     mpz_init_set_ui(b, 10);
223:     mpz_pow_ui(n, b, num);
224:
225:     //メルセンヌ・ツイスタ法で疑似乱数生成器のステート構造体を初期化する．
226:     gmp_randstate_t state;
227:     gmp_randinit_default(state);
228:     //時間をseedにする．
229:     time_t rtime;
230:     time(&rtime);
231:     gmp_randseed_ui(state, rtime);
232:
233:     //10万回まで乱数を発生させ，素数だったら戻り値にする．
234:     for (unsigned i = 0; i < 100000; i++) {
235:         //乱数を求める
236:         mpz_urandomm(a, state, n);
237:         *prime = (mpz_class)a;
238:         //素数かどうか判定する
239:         ret = millerRabinPrimalityTest(*prime);
240:         if (ret)    break;
241:     }
242:
243:     //後処理
244:     mpz_clear(a);
245:     gmp_randclear(state);
246: }

ユーザー関数 getBigPrime は、指定した桁数の多倍長整数の乱数を発生させ、それを前述のmillerRabinPrimalityTestに渡して素数かどうかを判定する。素数だったら、それを戻り値にする。

解説：コマンドラインオプションの定義と取得

bigprime.cpp

254:     //コマンドライン・オプションの定義
255:     options_description options("コマンドライン・オプション");
256:     options.add_options()
257:         ("number,n", value<unsigned long>(), "桁数")
258:         ("time,t",    "計算時間表\示")
259:         ("en,e",      "英語表\示")
260:         ("help,h",    "ヘルプ")
261:         ("version,v", "バージョン情報")
262:         ;
263:     //コマンドライン・オプションの取得
264:     variables_map vm;
265:     try {
266:         store(parse_command_line(argc, argv, options), vm);
267:     } catch(const boost::program_options::error_with_option_name& e) {
268:         ErrorMessage =  e.what();
269:         cerr << ErrorMessage << endl;
270:         return 1;
271:     }
272:     notify(vm);

コマンドラインオプションの定義と取得を行うのに、Boost C++ Librariesの Boost Program Options Libraryを利用した。
オプションの定義は、options_description型によって行う。
parse_command_line関数が、options_description の定義にしたがってコマンドライン引数を解析し、その結果を variables_map オブジェクトに格納するよう指示する。notify関数を実行することで、はじめて variables_mapオブジェクトに解析結果が格納される。

bigprime.cpp

274:     //英語表示
275:     if (vm.count("en")) {
276:         flagEnglish = true;
277:     }
278:     //ヘルプ情報を表示する．
279:     if (vm.count("help")) {
280:         dispHelp(flagEnglish);
281:     //バージョン情報
282:     } else if (vm.count("version")) {
283:         dispVersion(flagEnglish);

コマインドラインオプションが指定されているかどうかは、cout関数を用いて判定する。
オプションの後に指定された値は、vm["オプション"].as<データ型>() のようにして取り出すことができる。

bigprime.cpp

284:     //素数判定または生成
285:     } else {
286:         //計算時間表示
287:         if (vm.count("time")) {
288:             flagTime = true;
289:         }
290:         //計算開始時刻
291:         clock_t t0 = clock();
292:         //素数生成
293:         if (vm.count("number")) {
294:             unsigned long num = (unsigned long)vm["number"].as<unsigned long>();
295:             if (num <= 0) {
296:                 num = 100;
297:             }
298:             getBigPrime(&prime, num);
299:             cout << prime;
300:         //素数判定
301:         } else if (argc > 1) {
302:             bool flagJudge = false;
303:             for (int i = 1; i < argc; i++) {
304:                 if (isInteger((string)argv[i])) {
305:                     mpz_class num = (mpz_class)argv[i];
306:                     bool ret = millerRabinPrimalityTest(num);
307:                     if (! flagEnglish) {
308:                         if (ret) {
309:                             cout << "素数です";
310:                         } else {
311:                             cout << "素数ではありません";
312:                         }
313:                     } else {
314:                         if (ret) {
315:                             cout << "prime number";
316:                         } else {
317:                             cout << "not prime number";
318:                         }
319:                     }
320:                     flagJudge = true;
321:                     break;
322:                 }
323:             }
324:             //ヘルプ情報を表示する．
325:             if (! flagJudge) {
326:                 dispHelp(flagEnglish);
327:             }
328:         //ヘルプ情報を表示する．
329:         } else {
330:             dispHelp(flagEnglish);
331:         }
332:         //計算完了時刻

コマンドラインに指定した数字が素数かどうかを判定するときは、コマンドラインオプションではないため、main 関数に渡される argc, argv を舐めてみて、整数（isInteger）があれば素数判定を実行する。無ければヘルプを表示する。

解説：指定した文字列が整数かどうかを判定する

bigprime.cpp

145: /**
146:  * 指定した文字列が整数かどうかを判定する．
147:  * @param   string str 文字列
148:  * @return  boot true：整数である／整数でない
149: */
150: bool isInteger(const string str) {
151:     for (char const& c : str) {
152:         if (std::isdigit(c) == 0) {
153:             return false;
154:         }
155:     }
156:     return true;
157: }