p を素数としたとき位数が pⁿ の有限体は同型を除いて一意.
(Moore, E. H. (1896), "A doubly-infinite system of simple groups" section 3)
ここから位数が 2ⁿ の有限体 GF(2ⁿ) は一意.
GF(2ⁿ) はその原始元αから 0 以外のすべての要素が生成されるので
GF(2ⁿ) = {0,1,α²,α³,...,α^(2ⁿ-2)} ここで α^(2ⁿ-1) = 1
つまり、原始元の乗算 α· で 0 以外のすべての要素を巡回できる.
係数が {0,1} の、n-1次までの一変数多項式の集合 F(n) を考える.
F(n) = { aₙ₋₁ xⁿ⁻¹ + aₙ₋₂ xⁿ⁻² + aₙ₋₃ xⁿ⁻³ + ... + a₁ x + a₀ | aₖ ∈ {0,1} }
F(n) の要素の多項式の項同士の和を取るときに係数の排他的論理和を使用する.
ここではこの多項式の和の記号にも + を使用する.
このとき F(n) と + は群をなす.
- 単位元は零多項式
- 逆元は、排他的論理和の性質により、自身が逆元となる.
例:
(x² + 1) + 0
= x² + 1
(x² + 1) + (x² + 1)
= 0
(x² + 1) + (x² + x)
= x + 1
F(n) の要素の多項式同士の積を次のように定義する.
- 項同士の積は通常の多項式の積と同様
- 項同士の和に係数の排他的論理和を使用 (多項式の和の定義に従う)
- 結果が
n次以上の多項式になる場合は、あらかじめ決めておいたn次原始多項式※で割った余りを結果とする
ここではこの多項式の積に通常の積の記法を使用する.
※原始多項式 :原始元αを持つ最小次数の多項式
例:
(x² + x + 1)·(x + 1)
= x³ + x² + x + x² + x + 1 = x³ + 1
(x³ + 1)·(x + 1) ( F(2⁴) 上の積 )
= x⁴ + x + x³ + 1
= x⁴ + x³ + x + 1
= x ( ここで 4次原始多項式は x⁴ + x³ + 1 )
(原始多項式のデータについては https://docs.xilinx.com/v/u/en-US/xapp052 を参照のこと.)
この F(n) と和および積の定義は体をなすことが知られている.
F(n) は位数 2ⁿ の有限体となる.
F(n) は多項式の係数 {aₙ₋₁, aₙ₋₂,...,a₁, a₀} を各桁と見なすことで、 n-bit の二進数の全体と一致する.
g(x) を原始多項式とする.
g(x) の x での商 h(x) を考えるとき、
x では割り切れない(原始多項式は既約)ことから、定数項は 1.
よって、
g(x) = x·h(x) + 1
よって、g(x) による有限体での積の定義を適用したとき
x·h(x) = g(x) + 1 = 1
となり、h(x) は有限体の積における x の逆元であることがわかる.
gmask および hmask をそれぞれ g(x) および h(x) の二進数表現とする.
このとき次の関係が成立する.
hmask = gmask >> 1 (ここで >> は符号無し右シフト)
gmask および hmask を使用した、
ガロア LFSR の1ステップの疑似コードの次に示す.
unsigned input, lsb, tmp, output;
lsb = input & 1u; /* Get LSB */
tmp = input >> 1; /* Unsigned right shift */
if (lsb) { /* If the output bit is 1, */
output = tmp ^ hmask; /* apply toggle mask. */
} else {
output = tmp; /* noop */
}
このアルゴリズムの多項式表現上の意味について示す.
input, output および input >> 1 の多項式表現をそれぞれ i(x), o(x) および s(x) とする.
lsb = 1のとき
input >> 1 に対する左シフトを s(x) に対する x の乗算に対応付けると
i(x) = x · s(x) + 1
{- 多項式の和の排他的論理和 -}
i(x) + 1 = x · s(x)
o(x)
{- tmp = input >> 1, output = tmp ^ hmask , 多項式の和の排他的論理和 -}
= s(x) + h(x)
{- h(x) は x の逆元 -}
= h(x) · x · s(x) + h(x)
{- i(x) + 1 = x · s(x) -}
= h(x) · (i(x) + 1) + h(x)
{- 多項式の和の排他的論理和 -}
= h(x) · i(x)
lsb = 0のとき
input >> 1 に対する左シフトを s(x) に対する x の乗算に対応付けると
i(x) = x · s(x)
o(x)
{- tmp = input >> 1, output = tmp -}
= s(x)
{- h(x) は x の逆元 -}
= h(x) · x · s(x)
{- i(x) = x · s(x) -}
= h(x) · i(x)
よって、 lsb = 0 および lsb = 1 いずれの場合も
o(x) = h(x) · i(x)
であることが示された. //
つまり、ガロアLFSRの 1ステップは、
入力 i(x) に対して原始元 x の逆元である h(x) を乗ずることで、
出力 o(x) が得られる.
原始元の逆元による生成で、体のすべての要素を巡回できる.
unsigned input, lsb, tmp, output;
lsb = input & 1u;
tmp = input >> 1;
if (lsb) {
output = tmp ^ hmask;
} else {
output = tmp;
}
i(x) : input
o(x) : output
s(x) : input >> 1
h(x) : x の逆元 ( h(x)·x = 1 )
inputのlsbが1のとき
input = ((input >> 1) << 1) + 1 ⇔ i(x) = x·s(x) + 1
lsb = input & 1u; // ⇔ lsb は i(i) の定数項, i(i) の定数項が 1
tmp = input >> 1; // ⇔ tmp は s(x) = h(x)·x·s(x) = h(x)·(x·s(x) + 1) + h(x)
// = h(x)·i(x) + h(x)
output = tmp ^ hmask; // ⇔ o(x) = s(x) + h(x) = h(x)·i(x) + h(x) + h(x)
// = h(x)·i(x)
inputのlsbが0のとき
input = (input >> 1) << 1 ⇔ i(x) = x·s(x)
lsb = input & 1u; // ⇔ lsb は i(i) の定数項, i(i) の定数項が 0
tmp = input >> 1; // ⇔ tmp は s(x) = h(x)·x·s(x) = h(x)·(x·s(x))
// = h(x)·i(x)
output = tmp; // ⇔ o(x) = s(x)
// = h(x)·i(x)