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

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

サンプル・プログラム

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

bigprime.cpp 更新履歴
バージョン	更新日	内容
1.0.0	2023/03/12	初版

使用ライブラリ

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

ビルド

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

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

  74: /**
  75:  * べき剰余を求める．
  76:  * @param  number $base 基数
  77:  * @param  number $exp  指数
  78:  * @param  number $mod  除数
  79:  * @return    number べき剰余
  80: */
  81: mpz_class modpow(mpz_class base, mpz_class exp, mpz_class mod) {
  82:     mpz_class res = 1;
  83:     while (exp > 0) {
  84:         if ((exp & 1) == 1) {
  85:             res = (res * base) % mod;
  86:         }
  87:         base = (base * base) % mod;
  88:         exp >>= 1;
  89:     }
  90:     return res;
  91: }

  93: /**
  94:  * 指定した整数をミラー・ラビン判定法を使って素数かどうかを判定する．
  95:  * @param   mpz_class n  判定したい整数
  96:  * @return  bool true:素数である／false:素数でない
  97: */
  98: bool millerRabinPrimalityTest(mpz_class n) {
  99:     if (n <= 1)      return false;
100:     if (n == 2)     return true;
101:     if (n % 2 == 0) return false;
102:     vector<mpz_class> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
103:     mpz_class s = 0, d = n - 1;
104:     while (d % 2 == 0) {
105:         s++;
106:         d >>= 1;
107:     }
108:     for (auto a : A) {
109:         if (a % n == 0) return true;
110:         mpz_class t, x = modpow(a, d, n);
111:         if (x != 1) {
112:             for (t = 0; t < s; ++t) {
113:                 if (x == n - 1)     break;
114:                 x = x * x % n;
115:             }
116:             if (t == s) return false;
117:         }
118:     }
119:     return true;
120: }

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

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

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

122: /**
123:  * 指定した桁数の巨大素数を求める．
124:  * @param   mpz_class *prime 素数を格納する
125:  * @param   long num 桁数
126:  * @return  なし
127: */
128: void getBigPrime(mpz_class *prime, unsigned long num) {
129:     bool ret;
130:
131:     //多倍長整数構造体を初期化する．
132:     mpz_t a;
133:     mpz_init(a);
134:     mpz_t n;
135:     mpz_init(n);
136:     mpz_t b;
137:     mpz_init_set_ui(b, 10);
138:     mpz_pow_ui(n, b, num);
139:
140:     //メルセンヌ・ツイスタ法で疑似乱数生成器のステート構造体を初期化する．
141:     gmp_randstate_t state;
142:     gmp_randinit_default(state);
143:     //時間をseedにする．
144:     time_t rtime;
145:     time(&rtime);
146:     gmp_randseed_ui(state, rtime);
147:
148:     //10万回まで乱数を発生させ，素数だったら戻り値にする．
149:     for (unsigned i = 0; i < 100000; i++) {
150:         //乱数を求める
151:         mpz_urandomm(a, state, n);
152:         *prime = (mpz_class)a;
153:         //素数かどうか判定する
154:         ret = millerRabinPrimalityTest(*prime);
155:         if (ret)    break;
156:     }
157:
158:     //後処理
159:     mpz_clear(a);
160:     gmp_randclear(state);
161: }