在伽罗瓦域算术中优化y = x * x

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

题

我有这个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，我是否对上述算法进行了巧妙的优化，例如我做平方而不是乘法。我不是在加密使用btw之后。我只是想利用GF（8）中的x * x将x的位逐位与零位交错的事实。

已经有很聪明的方法来进行比特交织，但是因为我发现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）位。

基于表格的方法会更快。

查找表绝对是多项式基数galois平方最快的。使用GF（8）时，它也是乘法最快的，但是对于ECC中使用的较大字段，表格太大了。对于较大字段中的乘法，最佳算法是“从左到右合并”方法...（参见 http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X 算法2.36，第50页。

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

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

如果保证相同，则只传递一个参数。

它可能有助于编译器标记“a”。和“b”作为常数。或者手动展开循环。如果有帮助的话会很难过......

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top