原始多項式の個数

[] [] []


本稿では原始多項式を

xのべき乗 { 1 x x**2 ... x**(2n-2) } mod g(x) がゼロを除く全要素をつくすようなg(x)

と定義したが、数学の本を見るともう少し一般的なものとして定義されている。

GF(2n)のゼロを除く全要素は必ずある要素aのべき乗でつくされ、このようなa原始元という

・原始元を根とするような最小次数の多項式g(x)原始多項式という

つまりxは原始元でg(x)=0だからg(x)は原始多項式になっているが、他の要素も原始元でありうるし、それに対する原始多項式が存在するということである。

n=4ビットの例で見てみよう。

既約なg(x)3つあり、このうち2つが原始多項式になっていた。

  g(x)=x4+x+1                       g[4:0]=(10011)は原始多項式

  g(x)=x4+x3+1                      g[4:0]=(11001)は原始多項式

  g(x)=x4+x3+x2+x+1            g[4:0]=(11111)は既約だが原始多項式ではない

例えばg(x)=x4 + x + 1の場合に各要素のべき乗を計算すると、xすなわち16進ベクタ表記の(2)の他にもa=(3) (4) (5) (9) (b) (d) (e)が原始元になっており

  a=(2) (4) (3) (5) に対してa4+a+1=0が成り立つから原始多項式は x4+x+1

  a=(9) (b) (d) (e) に対してa4+a3+1=0が成り立つから原始多項式は x4+x3+1

同様に原始多項式でないg(x)=x4+x3+x2+x+1の場合も、a=(3) (5) (6) (7) (9) (a) (b) (e)が原始元になっており

  a=(3) (5) (e) (9) に対してa4+a+1=0が成り立つから原始多項式は x4+x+1

  a=(6) (b) (7) (a) に対してa4+a3+1=0が成り立つから原始多項式は x4+x3+1

◇◇

上記をふまえて、原始多項式の個数はφ(2 n -1)/nであることが言える。

(φ(N)1からN-1までの数のうちNと素な数の個数を示し、オイラーのトーシェント関数という)

まず、原始元は必ず存在することを認めると、原始元は全部でφ(2 n -1)個ある。

∵ 1つの原始元をaとおくと、ゼロを除く全要素は a**0 a**1 ... a**(2n-2)と書ける。もしa**kも原始元だとすると(a**k)**m≠1 (m=1 ... (2 n -2))でなければならないので、どんな要素も2 n -1乗すると1になることに注意するとk*m2 n -1の倍数ではありえない。つまりk2 n -1と互いに素でなければならない。

また、一般の多項式についてf(a**2)=(f(a))**2である

∵f(x)=Σc[k]x**kとすると、係数c[k]の加算はXOR、乗算はANDであることに注意して

(f(a))**2 =(Σc[k]a**k)**2 =Σ(c[k] AND c[k]) (a**k)**2 + Σ(c[k]c[j] XOR c[j]c[k]) (a**k) (a**j)

=Σc[k] (a**k)**2

=Σc[k] (a**2)**k = f(a**2)

したがってaがある原始多項式の根ならばa**2 a**22 ... a**2n=aも同じ原始多項式の根である(上記のg(x)=x4+x+1の例では、(2)2=(4) (4)2=(3) (3)2=(5) (5)2=(2)が同じ原始多項式x4+x+1の根)。つまりn個の原始元が同じ原始多項式を持つ。

結局、原始多項式の個数=原始元の個数/n=φ(2 n -1)/n

◇◇◇

nが小さい場合で確認してみると

n

g(x)

g[n:0]

φ(2 n -1)/n

2

x2+x+1

72

φ(3)/2=2/2=1

3

x3+x+1

x3+x2+1

b2

d2

φ(7)/3=6/3=2

4

x4+x+1

x4+x3 +1

132

192

φ(15)/4=8/4=2

5

x5+x2+1

x5+x3+1

x5+x3+x2+x+1

x5+x4+x2+x+1

x5+x4+x3+x+1

x5+x4+x3+x2+1

252

292

2f2

372

3b2

3d2

φ(31)/5=30/5=6

6

x6+x+1

x6+x4+x3+x+1

x6+x5+1

x6+x5+x2+x+1

x6+x5+x3+x2+1

x6+x5+x4+x+1

432

5b2

612

672

6d2

732

φ(63)/6=36/6=6

7

x7+x+1

x7+x3+1

x7+x3+x2+x+1

x7+x4+1

x7+x4+x3+x2+1

x7+x5+x2+x+1

x7+x5+x3+x+1

x7+x5+x4+x3+1

x7+x5+x4+x3+x2+x +1

x7+x6+1

x7+x6+x3+x+1

x7+x6+x4+x+1

x7+x6+x4+x2+1

x7+x6+x5+x2+1

x7+x6+x5+x3+x2+x+1

x7+x6+x5+x4+1

x7+x6+x5+x4+x2+x+1

x7+x6+x5+x4+x3+x2+1

832

892

8f2

912

9d2

a72

ab2

b92

bf2

c12

cb2

d32

d52

e52

ef2

f12

f72

fd2

φ(127)/7=126/7=18

8

x8+x4+x3+x2+1

x8+x5+x3+x+1

x8+x5+x3+x2+1

x8+x6+x3+x2+1

x8+x6+x4+x3+x2+x+1

x8+x6+x5+x+1

x8+x6+x5+x2+1

x8+x6+x5+x3+1

x8+x6+x5+x4+1

x8+x7+x2+x+1

x8+x7+x3+x2+1

x8+x7+x5+x3+1

x8+x7+x6+x+1

x8+x7+x6+x3+x2+x+1

x8+x7+x6+x5+x2+x+1

x8+x7+x6+x5+x4+x2+1

11d2

12b2

12d2

14d2

15f2

1632

1652

1692

1712

1872

18d2

1a92

1c32

1cf2

1e72

1f52

φ(255)/8=128/8=16

ちなみにn=16ではφ(65535)/16=32768/16=2048個もある。


[] [] []