Computes the product of two polynomials (modulo another polynomial) in a given finite field

poly_modulo_multip.py

mod = lambda x, n: x % n if x >= 0 else mod(x+n, n)
vmod = lambda v, n: [mod(e, n) for e in v]

def multip(u, v, p):
    w = [0] * (len(u)+len(v)-1)
    for i, x in enumerate(u):
        for j, y in enumerate(v):
            w[i+j] += x*y

    return vmod(w, p)

# computes u*v (mod f) in F_p[x]
# u, v, f: polynomials as arrays, i.e [3,0,2] = 3x^2 + 0x + 2
# p: size of the finite field
def multip_modulo(u, v, f, p):
    w = multip(u, v, p)
    if len(w) < len(f):
        return w

    for i, e in enumerate(w):
       g = [(e // f[0]) * x for x in f]
       w = [mod(w[i] - g[i], p) for i in range(len(w))]
       w = w[[0 if x == 0 else 1 for x in w].index(1):]
       if len(w) < len(f):
           return w

    return w