4

GF(8) で乗算を行うこの C コードがあります。

int32_t GaloisMultiply (int32_t a, int32_t b) 
{
    int32_t i;
    int32_t mask = 0x100;
    int32_t y = 0;

    for(i=0;i<8;i++) 
    {
        if(b & mask) 
        {
            y ^= a;
        }
        mask >>= 1;
        y <<= 1;
    }

    if(b & 0x1) 
    {
        y ^= a;
    }

    return(y);
}

それは多かれ少なかれ教科書の実装です。

a が常に b であると断言できる場合、上記のアルゴリズムに巧妙な最適化があるのではないかと思います。たとえば、乗算の代わりに 2 乗を行います。私はところで暗号化を使用した後ではありません。GF(8) の x*x が x のビットをゼロ ビットで 1 つずつインターリーブするという事実を利用したいだけです。

ビットインターリーブを行うための非常に巧妙な方法がすでにありますが、GF(8) の x*x がビットインターリーブを行うことを (偶然に) 知ったので、ビットインターリーブにそれを使用しようとするのを止めることはできません。最適化。

何か案は？

4

6 に答える 6

4

テーブルベース？リンク

x*x に制限されている場合、それは疎行列です。

ここに別の優れた論文（およびライブラリ）があります

于 2008-09-22T20:32:36.317 に答える
1

ルックアップ テーブルは、多項式ベースのガロア二乗で間違いなく最速です。また、GF(8) を使用する場合の乗算では最速ですが、ECC で使用されるように、より大きなフィールドに対してテーブルが大きくなりすぎます。より大きなフィールドでの乗算の場合、最適なアルゴリズムは「左から右への結合」メソッドです... ( http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273Xアルゴリズム 2.36、ページを参照) 50)。

于 2008-09-28T14:17:54.177 に答える
1 
int32_t GaloisMultiply( int32_t a ) 
{
  int32_t y = 0;
  int32_t b = a & 0x01ff;

  while ( b ) 
  {
    if ( b & 1 ) 
      y ^= a;

    a <<= 1;
    b >>= 1;
  }
  return y;
}

または、必要に応じて:

int32_t GaloisMultiply( int32_t a ) 
{
  int32_t y = 0;
  for ( int32_t b = a & 0x01ff; b; b >>= 1 )
  {
    if ( b & 1 ) 
      y ^= a;

    a <<= 1;
  }
  return y;
}

このアプローチが上記の元のコードよりも効率的である主な理由は、すべての (9) ビットをやみくもにチェックするのではなく、引数内のすべての「興味深い」ビットが消費されるまでループが実行されるためです。

ただし、テーブルベースのアプローチの方が高速です。

于 2008-09-22T20:38:56.347 に答える
0

もう少し良い仕事をするために、おそらくいくつかのアセンブリを書くことができます。ただし、これがアプリケーションのボトルネックであるとしたら、かなり驚かれることでしょう。プロファイリングを行いましたか？この関数は、最適化する価値があるとは思えません。

于 2008-09-22T20:25:15.227 に答える
0

これはおそらくあなたが探しているものではありませんが、ここに 1 つのマイナーなスピードアップがあります。

引数が同じであることが保証されている場合は、引数を 1 つだけ渡します。

于 2008-09-22T20:25:23.807 に答える
0

"a" と "b" を const としてマークすると、コンパイラが少し役立つ場合があります。または手でループを展開します。参考になれば悲しいですが…

ところで、それは特許地雷原ではありませんか?

于 2008-09-22T20:37:10.813 に答える