ガロア体演算で y = x*x を最適化する

StackOverflow https://stackoverflow.com/questions/117352

質問

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 であると断言できる場合、上記のアルゴリズムに賢い最適化があるのだろうか。掛け算ではなく二乗をします。ところで、私は暗号の使用を望んでいません。GF(8) の x*x が x のビットを 0 ビットで 1 つずつインターリーブするという事実を利用したいだけです。

ビット インターリーブを行う非常に賢い方法はすでにありますが、GF(8) の x*x がビット インターリーブを行うことを (偶然) 知って以来、それをビット インターリーブに使用する試みをやめられません。最適化。

何か案は？

役に立ちましたか？

解決

テーブルベースですか？ リンク

そして、x*x に限定されると、それは疎行列になります。

ここにもう一つあります 良い紙（そして図書館）

他のヒント

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) ビットを盲目的にチェックするのではなく、引数内のすべての「興味深い」ビットが消費されるまでのみループが実行されるためです。

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

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

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

おそらくこれはあなたが探しているものではありませんが、マイナーな高速化が 1 つあります。

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

「a」と「b」を const としてマークすると、コンパイラが少し役立つかもしれません。または手動でループを展開します。助かったとしたら残念ですが…。

ところで、それは特許の地雷原ではないでしょうか？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top