ガロア体を列挙するプログラム

$${GF(2)}$$上の多項式を入力として、その根を$${\alpha}$$とした場合の$${\alpha}$$のべきをすべて列挙するプログラムを作成した。原始多項式を入力できた場合$${GF(2^m)}$$(mは原始多項式の次数)の拡大ガロア体を得ることができる。この結果を眺めていく。

プログラム

pythonで記述。$${GF(2)}$$上多項式はbool型配列primitive_funcで与える。primitive_func[i]がTrueならば$${x^i}$$の係数は1、そうでないなら$${x^i}$$の係数は0とする。名前はprimitive_funcだが原始多項式を入力しなくても列挙はしてくれる。コードの例における入力配列は[True, False, True, True]で、これに対応する多項式は$${1 + x^2 + x^3}$$である。

# coding: utf-8

# a3*x^3 + a2*x^2 + a1*x + a0 -> [a0, a1, a2, a3]
def Galois(primitive_func):
    deg = len(primitive_func) - 1
    print("Primitive Function: ", end="")
    print(primitive_func)
    print("--------------")
    
    # ret = primitive_func[:-1].copy()
    ret = [False] * deg
    ret[0] = True
    tmp_digit = 0
    
    print("alpha^0:", end='')
    print(ret)
    for j in range(2**deg)[:-1]:
        print("alpha^"+str(j + 1)+":", end='')
        
        carry = ret[deg-1]
        for i in range(deg-1, -1, -1):
            if i == 0:
                tmp_digit = False
            else:
                tmp_digit = ret[i-1]
            if carry:
                tmp_digit = tmp_digit ^ primitive_func[i]
            ret[i] = tmp_digit
        print(ret)
    
    
Galois([True,False,True, True])

上のコードの結果(最後のNoneは省略)

Primitive Function: [True, False, True, True]
--------------
alpha^0:[True, False, False]
alpha^1:[False, True, False]
alpha^2:[False, False, True]
alpha^3:[True, False, True]
alpha^4:[True, True, True]
alpha^5:[True, True, False]
alpha^6:[False, True, True]
alpha^7:[True, False, False]

$${\alpha^7}$$で初めて1([True, False, False])に戻っているから、$${\alpha}$$の位数7であり、$${\alpha}$$は原始元であることが分かる。また、この入力多項式は原始多項式である。

入力$${1 + x^3}$$では

Primitive Function: [True, False, False, True]
--------------
alpha^0:[True, False, False]
alpha^1:[False, True, False]
alpha^2:[False, False, True]
alpha^3:[True, False, False]
alpha^4:[False, True, False]
alpha^5:[False, False, True]
alpha^6:[True, False, False]
alpha^7:[False, True, False]

当然だが$${\alpha^3}$$で1になっているので、原始多項式ではない。

入力$${1 + x^3+x^4+x^5}$$では

Primitive Function: [True, False, False, True, True, True]
--------------
alpha^0:[True, False, False, False, False]
alpha^1:[False, True, False, False, False]
alpha^2:[False, False, True, False, False]
alpha^3:[False, False, False, True, False]
alpha^4:[False, False, False, False, True]
alpha^5:[True, False, False, True, True]
alpha^6:[True, True, False, True, False]
alpha^7:[False, True, True, False, True]
alpha^8:[True, False, True, False, True]
alpha^9:[True, True, False, False, True]
alpha^10:[True, True, True, True, True]
alpha^11:[True, True, True, False, False]
alpha^12:[False, True, True, True, False]
alpha^13:[False, False, True, True, True]
alpha^14:[True, False, False, False, False]
alpha^15:[False, True, False, False, False]
alpha^16:[False, False, True, False, False]
alpha^17:[False, False, False, True, False]
alpha^18:[False, False, False, False, True]
alpha^19:[True, False, False, True, True]
alpha^20:[True, True, False, True, False]
alpha^21:[False, True, True, False, True]
alpha^22:[True, False, True, False, True]
alpha^23:[True, True, False, False, True]
alpha^24:[True, True, True, True, True]
alpha^25:[True, True, True, False, False]
alpha^26:[False, True, True, True, False]
alpha^27:[False, False, True, True, True]
alpha^28:[True, False, False, False, False]
alpha^29:[False, True, False, False, False]
alpha^30:[False, False, True, False, False]
alpha^31:[False, False, False, True, False]

$${\alpha^{14}}$$で1になっているので、原始多項式ではない。

入力$${1 + x +x^6}$$では

Primitive Function: [True, True, False, False, False, False, True]
--------------
alpha^0:[True, False, False, False, False, False]
alpha^1:[False, True, False, False, False, False]
alpha^2:[False, False, True, False, False, False]
alpha^3:[False, False, False, True, False, False]
alpha^4:[False, False, False, False, True, False]
alpha^5:[False, False, False, False, False, True]
alpha^6:[True, True, False, False, False, False]
alpha^7:[False, True, True, False, False, False]
alpha^8:[False, False, True, True, False, False]
alpha^9:[False, False, False, True, True, False]
alpha^10:[False, False, False, False, True, True]
alpha^11:[True, True, False, False, False, True]
alpha^12:[True, False, True, False, False, False]
alpha^13:[False, True, False, True, False, False]
alpha^14:[False, False, True, False, True, False]
alpha^15:[False, False, False, True, False, True]
alpha^16:[True, True, False, False, True, False]
alpha^17:[False, True, True, False, False, True]
alpha^18:[True, True, True, True, False, False]
alpha^19:[False, True, True, True, True, False]
alpha^20:[False, False, True, True, True, True]
alpha^21:[True, True, False, True, True, True]
alpha^22:[True, False, True, False, True, True]
alpha^23:[True, False, False, True, False, True]
alpha^24:[True, False, False, False, True, False]
alpha^25:[False, True, False, False, False, True]
alpha^26:[True, True, True, False, False, False]
alpha^27:[False, True, True, True, False, False]
alpha^28:[False, False, True, True, True, False]
alpha^29:[False, False, False, True, True, True]
alpha^30:[True, True, False, False, True, True]
alpha^31:[True, False, True, False, False, True]
alpha^32:[True, False, False, True, False, False]
alpha^33:[False, True, False, False, True, False]
alpha^34:[False, False, True, False, False, True]
alpha^35:[True, True, False, True, False, False]
alpha^36:[False, True, True, False, True, False]
alpha^37:[False, False, True, True, False, True]
alpha^38:[True, True, False, True, True, False]
alpha^39:[False, True, True, False, True, True]
alpha^40:[True, True, True, True, False, True]
alpha^41:[True, False, True, True, True, False]
alpha^42:[False, True, False, True, True, True]
alpha^43:[True, True, True, False, True, True]
alpha^44:[True, False, True, True, False, True]
alpha^45:[True, False, False, True, True, False]
alpha^46:[False, True, False, False, True, True]
alpha^47:[True, True, True, False, False, True]
alpha^48:[True, False, True, True, False, False]
alpha^49:[False, True, False, True, True, False]
alpha^50:[False, False, True, False, True, True]
alpha^51:[True, True, False, True, False, True]
alpha^52:[True, False, True, False, True, False]
alpha^53:[False, True, False, True, False, True]
alpha^54:[True, True, True, False, True, False]
alpha^55:[False, True, True, True, False, True]
alpha^56:[True, True, True, True, True, False]
alpha^57:[False, True, True, True, True, True]
alpha^58:[True, True, True, True, True, True]
alpha^59:[True, False, True, True, True, True]
alpha^60:[True, False, False, True, True, True]
alpha^61:[True, False, False, False, True, True]
alpha^62:[True, False, False, False, False, True]
alpha^63:[True, False, False, False, False, False]

$${\alpha^{63}}$$で初めて1になっているので、原始多項式である。