0

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

编辑：GF（（2 ^ 16）+ 1）中的%-free模：

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) 中的 %-free 模数：

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 倍。较低的版本与使用 % :/ 一样快。有什么进一步的建议可以加快较低版本的速度吗？

干杯康拉德

4

2 回答 2

2

之所以使用幂 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) 位，比适合计算机字的多 - log2(m) 位的值可以通过反复与 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.

在 base 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

进一步阅读以比较 GF(2^n) 乘法：

（Serdar S. Erdem、Tuğrul Yanık、Çetin K. Koç 的论文，
Acta Applicandae Mathematica 2006 年 9 月，第 93 卷，第 1-3 期，第 33-55 页）

于 2013-03-20T09:46:18.760 回答
0

添加到丹尼尔的答案：有限域只能具有许多元素的素数。但是，您希望拥有许多素数 p 元素，因为这些元素与计算 mod p 同构（这很快！）。而具有 p^r (r > 1) 的有限域，许多元素从不与 Z/p^r Z 同构（即计算 mod p^r）。

编辑：如果你想在 GF(p^r) 中实现计算，你可以在 GF(p)[x] 中选择一个 r 度的不可约多项式 p(x) 并在 GF(p)[x] / (p (x)) 即你计算 mod p(x) （所以你必须实现多项式除法）。您可以在计算机代数系统（例如 Singular 或 Macaulay 2）中使用这些东西

于 2013-03-19T14:33:13.220 回答