Exponentiation in GF2[x]/P(x)

gf_mul.py

import math

poly  = 0xa195150d15*2+1
degree = int(math.log(poly)/math.log(2))
f = (1 << degree)

def multiply(a, b, poly):
    r = 0
    for i in range(64):
        if ((a & (1 << i)) != 0):
            r ^= b
        b = (b << 1)
        if (b & f):
            b ^= poly
    return r

def exp(x, n, poly):
    if n == 0:
        return 1
    y = 1
    while n > 1:
        if n % 2 == 0:
            x = multiply(x, x, poly)
            n = n / 2
        else:
            y = multiply(x, y, poly)
            x = multiply(x, x, poly)
            n = (n - 1) / 2
    return multiply(x, y, poly)