4

我有这个 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 做了位交织的事情（偶然）我不能停止尝试将它用于位交织优化。

有任何想法吗？

4

6 回答 6

4

基于表？关联

当你被限制为 x*x 时，它是一个稀疏矩阵。

这是另一篇好论文（和一个图书馆）

于 2008-09-22T20:32:36.317 回答
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 回答
1

查找表绝对是多项式基伽罗瓦平方最快的。使用 GF(8) 时，它也是最快的乘法运算，但是对于 ECC 中使用的较大字段，表变得太大。对于更大领域的乘法，最好的算法是“从左到右结合”方法......（参见http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X算法 2.36，页50)。

于 2008-09-28T14:17:54.177 回答
0

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

于 2008-09-22T20:25:15.227 回答
0

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

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

于 2008-09-22T20:25:23.807 回答
0

将“a”和“b”标记为 const 可能会对编译器有所帮助。或者手动展开循环。要是能帮上忙就可惜了……

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

于 2008-09-22T20:37:10.813 回答