BIGNUMライブラリ、遅いプライム発電

Question

私はBIGNUMライブラリを開発しています

：http://pastebin.com/nFgF3zjW 私はミラーラビンアルゴリズム（isprime()）を実装し、それは一例にOpenSSLのBN_is_prime_fasttest用に比べ、非常に遅いです。

プロファイリングを試みましたが、最も実行される機能はbn_shr_atomicとbn_cmpです。 これをもっと速くするにはどうすればいいですか？

Answer 1

GNU複数精度演算ライブラリはMiller-Rabinを実装しています。それのマニュアルは次の場所にあります。

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

私はあなたの計算を高速化にポインタのためにその実施を検討することをお勧め。しかし、任意精度の算術演算は、本来、レジスタに収まる数値を扱うよりも遅くなるでしょう。

編集：

使用するアルゴリズム、そして得られた確率の品質の間のトレードオフもあります。つまり、OpenSSLがどのようなテストを使用しているかはわかりません。

Answer 2

大きな推測：自分のライブラリを本当に使いたい場合は、まず分割アルゴリズムを長い分割で置き換えます。

あなたのdivisonの内側ループにcmpとshrがありますか？あなたのプロファイルの主要貢献者を呼び出すか、どこか別の人から来ていますか？一般に、あなたがプロファイルを作成するときは、大きな貢献者である上位レベルの機能を最初に調べる必要があります。アルゴリズムを変更すると、低レベルの機能をチューニングするよりも通常より有益です。