2

私は、RSA に関する元の論文で提示された Solovay-Strassen 素数性テストをプログラムする予定です。

さらに、小さな bignum ライブラリを作成する必要があるため、bignum の便利な表現を探しているときに、次の仕様に出会いました。

struct {
  int sign;
  int size;
  int *tab;
} bignum;

また、カラツバ法を使用した乗算ルーチンも作成します。

だから、私の質問のために：

bignum 構造体に整数データを格納するには、どのベースが便利でしょうか?

注: GMP などの bignum にサードパーティまたは組み込みの実装を使用することは許可されていません。

ありがとうございました。

4

4 に答える 4

3

2 の累乗。

単純な実装では、オーバーフローすることなく 2 桁を乗算できるように、おそらくマシン上の単語の半分のサイズです。つまり、65536 または 4294967296 です。または、同じ理由で最大の整数型の半分のサイズになる可能性がありますが、全体的にパフォーマンスが向上する可能性があります。

しかし、私はそのようなライブラリを実際に実装したことはありません。最もよく知られているアルゴリズムを使用している場合、学校スタイルの長い乗算を行うことはありません。カラツバ掛け算 (およびその他の巧妙なトリック) は、桁のサイズの 2 倍以上の整数で実行されることでメリットが得られる可能性がありますが、パフォーマンスがどのように機能するかはわかりません。もしそうなら、256 と 32 ビットの算術演算、または 65536 と 64 ビットの算術演算を使用するのが最善です。

いずれにせよ、表現がバイナリの場合は、各操作に便利なように、より大きな 2 のべき乗ベースを選択できます。たとえば、データを乗算では基数 2^16 として扱い、加算では基数 2^32 として扱うことができます。エンディアンに注意すれば、すべて同じです。私はおそらくベース 2^16 から始めます (2^8 では無理ですが、最初からエンディアンネスを正しく取得する必要があるため)。最適化は、最適な塩基を特定することです。

バイトの倍数ではないサイズを使用することも可能ですが、基数に応じて特定の場所のストレージに未使用のビットがあるため、すべてに同じ基数を使用する必要があります。

于 2010-04-18T22:51:44.467 に答える
2

次の操作を大量に実行します。

ab+ cd ...;

最大ワード サイズの 1/4 を選択するか、最大ワード サイズの 1/2 から 1 ～ 2 ビット少ない値を選択します。これは、64 ビット システムでは 2^16 または 2^30 になり、32 ビット システムでは 2^8 または 2^14 になります。ハードウェアではなく、コンパイラがサポートする最大サイズを使用してください。

64 ビット システムで 2^31 を選択すると、オーバーフローすることなく 4 つの積を追加できることを意味します。2^30 を選択すると、オーバーフローすることなく 16 個の製品を追加できます。オーバーフローせずに追加できるほど、使用できる中間ブロックが大きくなります。

ワード サイズの 1/4 を選択すると、ネイティブ型が残るため、結果を保存しやすくなります。オーバーフローもほとんど無視できます。これにより、基本的にコードの記述が高速になり、エラーが発生しにくくなり、メモリ効率がわずかに向上します。数学と一緒に多くのビット操作が好きでない限り、これをお勧めします。

より大きなベースを選択すると、大きな O 番号がよりよく見えます。実際には、ベースが大きい方がおそらく高速ですが、期待する 4 倍の速度向上にはなりません。

于 2010-04-18T23:23:56.747 に答える
1

使用する基数は 2 のべき乗でなければなりません。符号を別々に追跡するように見えるので、数値自体を格納するために unsigned int を使用できます。一度にこれらの数値の 2 個/桁/単位を乗算する機能が必要になるため、サイズは使用可能なワード サイズの半分以下にする必要があります。つまり、x86 では unsigned int は 32 ビットなので、数字を 16 ビット以下にする必要があります。unsigned int の積の中間結果に「long long」を使用することもできます。次に、ベースの 2^32 を見ています。最後に考慮すべきことは、積の合計を追加したい場合があるということです。これは、使用するビット数を減らしないとオーバーフローします。

パフォーマンスが大きな問題ではない場合は、base 256 を使用するだけで十分です。後でこれらのパラメーターを簡単に変更できるように、typedef と定義済みの定数を使用することができます。

于 2010-04-18T22:52:34.963 に答える
1

タブ配列の整数は符号なしである必要があります。それらは、乗算しても製品を表すことができる最大のサイズ (ベース) である必要があります。たとえば、コンパイラ/プロセッサが 64 ビットの unsigned long long をサポートしている場合、「数字」の配列に uint32_t を使用できます。コンパイラ/プロセッサが 32 ビット製品しかネイティブに生成できない場合は、uint16_t を使用する必要があります。

2 つの配列を合計すると、オーバーフローに対処する必要があります。組み立ては簡単です。C では、オーバーフローの検出を容易にするために、1 つ少ないビット (31 または 15) を使用することを選択できます。

また、エンディアンと、エンディアンとアルゴリズムがキャッシュの動作に及ぼす影響も考慮してください。

于 2010-04-18T22:54:57.683 に答える