0

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 倍高速です。下位バージョンは、単純に % :/ を使用するのと同じくらい高速です。下位バージョンを高速化するためのその他の提案はありますか?

乾杯コンラッド

4

2 に答える 2

2

累乗2^N --mを使用する理由は、小さい場合、形式の単語のモジュロ（HI * 2 ^ N + LO）mod 2 ^ Nmを2つに分割できる（またはより多くのピース）に減少します

    (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を繰り返し乗算して累積することにより、再び合計に戻すことができます。通常、1回の反復で十分です。

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（またはネオン）多項式（キャリーフリー）乗算を使用することを提案します。私が大きく誤解していなければ、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ğrulYanık、ÇetinK.Koç、
Acta Applicandae Mathematica 2006年9月、第93巻、第1〜3号、33〜55ページの論文）

于 2013-03-20T09:46:18.760 に答える
0

ダニエルの答えに追加：有限体のみが多くの要素の素数を持つことができます。ただし、これらは p を法とする計算と同型であるため、多くの素数 p の要素が必要です (これは高速です!)。p^r (r > 1) を持つ有限体に対して、多くの元は決して Z/p^r Z に同型ではありません (つまり、計算 mod p^r)。

編集: GF(p^r) で計算を実装する場合は、次数 r の GF(p)[x] で既約多項式 p(x) を選択し、GF(p)[x] / (p (x)) つまり、mod p(x) を計算します (したがって、多項式除算を実装する必要があります)。Singular や Macaulay 2 などのコンピューター代数システムでこのようなものをいじることができます。

于 2013-03-19T14:33:13.220 に答える