Polynomial Rings

Polynomial Rings

The polynomial ring $R[x]$ over a ring $R$ consists of all polynomials with coefficients in $R$. We represent a polynomial as a list of coefficients: [a0, a1, a2, ...] represents $a_0 + a_1 x + a_2 x^2 + \cdots$.

Polynomial Arithmetic mod $p$

Over $\mathbb{Z}_p$, all coefficient arithmetic is done modulo $p$:

def poly_add(f, g, p):
    n = max(len(f), len(g))
    result = [0] * n
    for i in range(len(f)):
        result[i] = (result[i] + f[i]) % p
    for i in range(len(g)):
        result[i] = (result[i] + g[i]) % p
    # Strip trailing zeros
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result

Polynomial Multiplication mod $p$

Standard convolution with coefficients reduced mod $p$:

$\left(\sum_i a_i x^i\right)\left(\sum_j b_j x^j\right) = \sum_k \left(\sum_{i+j=k} a_i b_j\right) x^k$

Polynomial Evaluation

To evaluate $f(a)$ in $\mathbb{Z}_p$, use Horner's method:

def poly_eval(f, a, p):
    result = 0
    for coeff in reversed(f):
        result = (result * a + coeff) % p
    return result

Your Task

Implement poly_add(f, g, p), poly_mul(f, g, p), and poly_eval(f, a, p) for polynomials over $\mathbb{Z}_p$. Strip trailing zeros from results.