gf_mul.py

#!/usr/bin/python3

import functools

#    1+0x+x^2+0x^3+0x^4+x^5
p = [1, 0, 1, 0, 0, 1]

def format_polynom(xs):
    return " + ".join(reversed([("x^{}".format(i) if i > 0 else "1") for i, x in enumerate(xs) if x == 1]))

def reduce_polynom(res, t, p):
    b = []
    for r in res:
        if len(r) >= len(p):
            a = []
            for i, x in enumerate(r[len(p) - 1:]):
                if x == 1:
                    a.append(t[i + len(p)])
            a.append(r[:len(p) - 1])
            b.append(add(a))
        else:
            b.append(r)
    return b

def add(xs):
    a = [0] * len(max(xs, key=len))
    for x in xs:
        for i, b in enumerate(x):
            if b == 1:
                a[i] += 1

    return [1 if v % 2 != 0 else 0 for v in a]

def gen_table(p):
    t = {}
    x = list(i for i, v in enumerate(p) if v == 1)[-2] + 1
    for i in range((len(p) - 2) * 2 - len(p) + 2):
        t[i+len(p)] = add(reduce_polynom([[0] * i + p[:x]], t, p))
    return t

table = gen_table(p)

def mul(xs, ys):
    res = [[0] * i + ys for i, x in enumerate(xs) if x == 1]
    return add(reduce_polynom(res, table, p))

def exp(x, k):
    return functools.reduce(mul, [x] * k)

alpha = [0, 0, 1]
priv_a = 5
priv_b = 11

pub_a = exp(alpha, priv_a)
pub_b = exp(alpha, priv_b)

print("k_{{pub,A}} = {}".format(format_polynom(pub_a)))
print("k_{{pub,B}} = {}".format(format_polynom(pub_b)))

k1 = exp(pub_a, priv_b)
k2 = exp(pub_b, priv_a)

def arr_eq(a, b):
    return all(x == y for x,y in zip(a, b))

if len(k1) != len(k2) or not arr_eq(k1, k2):
    print("rip")

print("k = {}".format(format_polynom(k1)))