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

Question

我有这个 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 做了位交织（偶然），我就无法停止尝试将它用于位-交错优化。

有什么想法吗？

Answer 1

基于表格？ 链接

当你仅限于 x*x 时，它就是一个稀疏矩阵。

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

Answer 2

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）位。

基于表格的方法会更快。

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

将“a”和“b”标记为 const 可能会对编译器有所帮助。或者用手展开环。如果有帮助的话那就太遗憾了...

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

Answer 7

平方

x*x mod r(x)

只是x中位i的所有权重与

w_i = x^{i*2} mod r(x)

的叠加。 这可以使用 3 个 64 位查找表并行进行评估。

  i0to2 = x & 0b111;
  i3to5 = x & 0b111000;
  i6to7 = x >> 6;
  return (k0to2 >> (i0to2 * 8)) ^ 
         (k3to5 >> i3to5) ^
         (k6to7 >> (i6to7 * 8);

这可以简化为两个 3 位表，并且附加逻辑知道位 1 == 1 的权重——即

result ^= (x & 1)

。 同样，位 4 == r(x) - x^8 的权重仅留下两个 64 位表

k1to3, k5to7

。 这里编码表适合 64 位寄存器，例如 k0to2 中的字节 3 (0b11) 将对应于 w_0 ^ w_1 == 5（对于所有多项式 r(x)）。