原始多項式の個数

[←]　[↑]　[→]

---

本稿では原始多項式を

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

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

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

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

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

◇

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

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

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

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

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

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

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

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

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

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

  a=(6) (b) (7) (a) に対してa⁴+a³+1=0が成り立つから原始多項式は x⁴+x³+1

◇◇

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

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

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

∵ 1つの原始元をaとおくと、ゼロを除く全要素は a**0 a**1 ... a**(2ⁿ-2)と書ける。もしa**kも原始元だとすると(a**k)**m≠1 (m=1 ... (2 ⁿ -2))でなければならないので、どんな要素も2 ⁿ -1乗すると1になることに注意するとk*mは2 ⁿ -1の倍数ではありえない。つまりkは2 ⁿ -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**2² ... a**2ⁿ=aも同じ原始多項式の根である(上記のg(x)=x⁴+x+1の例では、(2)²=(4) (4)²=(3) (3)²=(5) (5)²=(2)が同じ原始多項式x⁴+x+1の根)。つまりn個の原始元が同じ原始多項式を持つ。

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

◇◇◇

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

n	g(x)	g[n:0]	φ(2^n -1)/n
2	x^2+x+1	7^2	φ(3)/2=2/2=1
3	x^3+x+1 x^3+x^2+1	b^2 d^2	φ(7)/3=6/3=2
4	x^4+x+1 x^4+x^3 +1	13^2 19^2	φ(15)/4=8/4=2
5	x^5+x^2+1 x^5+x^3+1 x^5+x^3+x^2+x+1 x^5+x^4+x^2+x+1 x^5+x^4+x^3+x+1 x^5+x^4+x^3+x^2+1	25^2 29^2 2f^2 37^2 3b^2 3d^2	φ(31)/5=30/5=6
6	x^6+x+1 x^6+x^4+x^3+x+1 x^6+x^5+1 x^6+x^5+x^2+x+1 x^6+x^5+x^3+x^2+1 x^6+x^5+x^4+x+1	43^2 5b^2 61^2 67^2 6d^2 73^2	φ(63)/6=36/6=6
7	x^7+x+1 x^7+x^3+1 x^7+x^3+x^2+x+1 x^7+x^4+1 x^7+x^4+x^3+x^2+1 x^7+x^5+x^2+x+1 x^7+x^5+x^3+x+1 x^7+x^5+x^4+x^3+1 x^7+x^5+x^4+x^3+x^2+x +1 x^7+x^6+1 x^7+x^6+x^3+x+1 x^7+x^6+x^4+x+1 x^7+x^6+x^4+x^2+1 x^7+x^6+x^5+x^2+1 x^7+x^6+x^5+x^3+x^2+x+1 x^7+x^6+x^5+x^4+1 x^7+x^6+x^5+x^4+x^2+x+1 x^7+x^6+x^5+x^4+x^3+x^2+1	83^2 89^2 8f^2 91^2 9d^2 a7^2 ab^2 b9^2 bf^2 c1^2 cb^2 d3^2 d5^2 e5^2 ef^2 f1^2 f7^2 fd^2	φ(127)/7=126/7=18
8	x^8+x^4+x^3+x^2+1 x^8+x^5+x^3+x+1 x^8+x^5+x^3+x^2+1 x^8+x^6+x^3+x^2+1 x^8+x^6+x^4+x^3+x^2+x+1 x^8+x^6+x^5+x+1 x^8+x^6+x^5+x^2+1 x^8+x^6+x^5+x^3+1 x^8+x^6+x^5+x^4+1 x^8+x^7+x^2+x+1 x^8+x^7+x^3+x^2+1 x^8+x^7+x^5+x^3+1 x^8+x^7+x^6+x+1 x^8+x^7+x^6+x^3+x^2+x+1 x^8+x^7+x^6+x^5+x^2+x+1 x^8+x^7+x^6+x^5+x^4+x^2+1	11d^2 12b^2 12d^2 14d^2 15f^2 163^2 165^2 169^2 171^2 187^2 18d^2 1a9^2 1c3^2 1cf^2 1e7^2 1f5^2	φ(255)/8=128/8=16

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

---

[←]　[↑]　[→]