我有这个C代码可以在GF(8)上做乘法：

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的位与零位一一交错的事实。

已经有相当聪明的方法进行位交织，但是由于我发现GF(8)中的x * x可以进行位交织(偶然)，所以我不能停止尝试将其用于位交织优化。

有任何想法吗？

解决方案

我们可能会编写一些程序集来做更好的工作。但是，如果这是我们应用程序的瓶颈，我会感到非常惊讶。你做过任何分析吗？此功能似乎不值得优化。

这可能不是我们想要的，但是这是一个较小的加速：

如果保证它们相同，则仅传递一个参数。

基于表？关联

而且当我们限于x * x时，它是一个稀疏矩阵。

这是另一篇好论文(和图书馆)

将" a"和" b"标记为const可能会对编译器有所帮助。或者手动展开循环。如果有帮助的话，那会很可悲。

顺便说一下，这不是一个专利雷区吗？

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)。