c - Bignum ライブラリ、スロー プライム ジェネレーター

Question

bignum ライブラリを開発しています: http://pastebin.com/nFgF3zjW Miller-Rabin アルゴリズム ( isprime()) を実装しましたが、たとえば OpenSSL の BN_is_prime_fasttest と比較すると非常に遅いです。

プロファイリングを試みたところ、最も実行される関数はbn_shr_atomicとbn_cmpです。これをより速くする方法はありますか？

Answer 1

GNU Multiple Precision Arithmetic ライブラリは Miller-Rabin を実装しています。ドキュメントは次の場所にあります。

http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions

計算を高速化するためのポインターの実装を調べることをお勧めします。ただし、任意精度の算術演算は、レジスタに収まる数値を扱うよりも本質的に遅くなります。

編集：

使用されるアルゴリズムと、結果として得られる確率の質の間にもトレードオフがあります。とはいえ、OpenSSL が使用するテストはわかりません。

Answer 2

おおまかな推測: 本当に独自のライブラリを使用したい場合は、最初に除算アルゴリズムを長い除算に置き換えます。

私の推測を検証するには: あなたの部門の内側のループに cmp と shr があります。一般に、プロファイリングを行うときは、最初に大きな影響を与える上位レベルの関数を確認する必要があります。アルゴリズムを変更することは、通常、低レベルの関数を調整するよりも有益です。