c - 有限素数领域中的代数C片段

我需要在16位CPU上的有限质数字段中求解多项式。我见过人们在使用GF((2^16)+1), GF((2^16)-15)和GF((2^32)-5)字段。我猜这些选择源于多个优化的事实。但是，除了使用“ mod”之外，我不知道任何进一步的优化。如果有人向我指出了一个很好的资源，给了我代码片段，或解释了为什么人们使用那些奇怪的素数而不是说GF((2^16)-1)，我将不胜感激。

编辑：GF（（2 ^ 16）+1）中的无％模数：

uint32_t mod_0x10001(uint32_t divident)
{
  uint16_t least;
  uint16_t most;

  least = divident & 0xFFFF;
  most = divident >> 16;

  if (least >= most) {
    return least - most;
  } else {
    return 0x10001 + least - most;
  }
}

编辑：GF（2 ^ 16-15）中的无％模数：

uint32_t mod_0xFFF1(uint32_t divident)
{
  uint16_t least;
  uint16_t most;
  uint32_t remainder;

  least = divident & 0xFFFF;
  most = divident >> 16;

  /**
   * divident mod 2^16-15
   * = (most * 2^N + least) mod 2^16-15
   * = [(most * 2^N mod 2^16-15) + (least mod 2^16-15)] mod 2^16-15
   * = [ 15 * most               + least              ] mod 2^16-15
   */
  remainder = 15 * most         + least;

  while (remainder >= 0xFFF1) {
      remainder -= 0xFFF1;
  }

  return remainder;
}

更新：我在MSP430上测量了性能：较高版本比较低版本快4倍。较低的版本与仅使用％：/一样快。还有其他建议来加快较低版本的速度吗？

干杯
康拉德

最佳答案

使用2 ^ N-m次幂的原因是由于以下事实：计算格式为（HI * 2 ^ N + LO）mod 2 ^ Nm的单词的模可以分解为两个（或减少到

    (HI*2^N+LO) mod (2^N-m) ==
    ((HI*2^N) mod (2^N-m) + LO mod (2^N-m)) mod (2^N-m)
    (m * HI  + LO ) mod (2^N-m).

m * HI + LO的值最多具有log2（m）位，比计算机字数还多-通过重复乘以m并累加，log2（m）位值可以再次折回总和。通常，一次迭代就足够了。

如果m小，m ^ 2或m ^ 3也可以相当小-那么人们可以应用该技术来计算大数的模数：

    [AAAAA | BBBBB | CCCCC | DDDDD | EEEEE ] mod (2^N-m) ==
     EEEEE * 1 mod (2^N-m) +
     DDDDD * m mod (2^N-m) +
     CCCCC * (m^2) mod (2^N-m) + ... etc.

在以10为底的基础上相同

    1234 5678 9812 mod 9997 ==
              9812 mod 9997 +
            3*5678 mod 9997 +
            9*1234 mod 9997 ==
            3 7952 mod 9997 == ( 7952 + 3*3 ) mod 9997 = 7961

    Here 9997 doesn't have to prime, we are using 10^4 instead of 2^N and m = 3

对于GF（2 ^ n）计算，典型的加速是root ^ n和log（n）的查找表。然后乘法减为加法。如果目标系统不是某个16位系统，我建议使用SSE4.2（或Neon）多项式（无进位）乘法。如果我没有大错，那么GF中的多项式计算应该可以卷积：

for (i=0;i<N*2-1;i++) temp[i]=popcount(A & (bit_reverse(B)<<N)>>i);
//  A = 11010, B=01101, reverse B = 10110
//
//  11010     11010     11010    11010   11010  11010   11010    11010     11010
//      10110    10110    10110   10110  10110 10110  10110   10110    10110
// 0000000000 00010000  0000000  010100  10010 001000 0011000 00010000 000000000
//      0        1         0      0       0      1      0        1        0
// 010001010 to be divided by the generator polynomial using typical CRC approach

Further reading用于比较GF（2 ^ n）乘法：

（Serdar S. Erdem，TuğrulYanık，ÇetinK.Koç的论文，
数学应用学报
2006年9月，第93卷，第1-3期，第33-55页）