# Extension Field Arithmetic ## Metadata **Status**:: #x **Zettel**:: #zettel/literature **Created**:: [[2024-03-30]] **Topic**:: [[♯ Math]] ## Synopsis ![[Finite Field#^hs77wz]] Elements in $\mathrm{GF}(q)$ are polynomials which degree is less than n, which have the form $\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1}$ with all coefficients are from the [[Finite Field#Prime Finite Field|Prime Finite Field]]. ## Addition Addition is defined by adding coefficients at the same degree using [[Modular Arithmetic]]. $ \begin{align} &\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1} \\ +\quad & \overline{b_0}_p + \overline{b_1}_{p}x + \ldots + \overline{b_{n-1}}_{p}x^{n-1} \\ \hline \\ =\quad & (\overline{a_0}_p + \overline{b_0}_p) + (\overline{a_1}_{p} + \overline{b_1}_{p})x + \ldots + (\overline{b_{n-1}}_{p} + \overline{b_{n-1}}_{p})x^{n-1} \\ \end{align} $ The addition identity is the constant polynomial $\overline{0}_p$. The addition inverse is the polynomial with modular additive inverse coefficients at each degree. $ \begin{align} &-(\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1}) \\ =\quad &-\overline{a_0}_p + (-\overline{a_1}_{p})x + \ldots + (-\overline{a_{n-1}}_{p})x^{n-1} \\ \end{align} $ Subtraction is defined as adding the inverse of the right hand operand. $ \begin{align} &\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1} \\ -\quad & (\overline{b_0}_p + \overline{b_1}_{p}x + \ldots + \overline{b_{n-1}}_{p}x^{n-1}) \\ \hline \\ =\quad &\overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{n-1}}_{p}x^{n-1} \\ +\quad & (-(\overline{b_0}_p + \overline{b_1}_{p}x + \ldots + \overline{b_{n-1}}_{p}x^{n-1})) \\ \end{align} $ ## Multiplication Let $P$ be the [[Irreducible Polynomial]] of the extension field $\mathrm{GF}(q)$. Product of two elements in $\mathrm{GF}(q)$ is the reminder of the euclidean division by P of the product in $\mathrm {GF} [p](X)$. ### Polynomial Product of $\mathrm{GF}[p](X)$ Given two polynomials A and B in $\mathrm{GF}[p](X)$ $ \begin{align} A = \overline{a_0}_p + \overline{a_1}_{p}x + \ldots + \overline{a_{m-1}}_{p}x^{m-1} \\ B = \overline{b_0}_p + \overline{b_1}_{p}x + \ldots + \overline{b_{n-1}}_{p}x^{n-1} \\ \end{align} $ The product of A and B is the sum of pair-wise multiplications where each term of one polynomial is multiplied by every term of the other. The result is the polynomial of degree $(m-1)(n-1)$. $ C = \overline{c_0}_p + \overline{c_1}_{p}x + \ldots + \overline{c_{(m-1)(n-1)}}_{p}x^{(m-1)(n-1)} $ The coefficient $\overline{c_i}_p$ is computed using the following equation: $ \overline{c_i}_p = \prod_{\substack{\forall j,k \\ j+k=i}}(\overline{a_j}_p \times \overline{b_k}_p) $ ### Remainder Divided by P The multiplication of A and B over $\mathrm{GF}(q)$ is the reminder of the euclidean division by P of the product C. $A \times B = C \bmod P$ > [!note] Euclidean Division > **Input**: a and b ≠ 0 two polynomials in the variable x; > **Output**: q, the quotient, and r, the remainder; > > ``` > begin > q := 0 > r := a > d := deg(b) > c := lc(b) > while deg(r) ≥ d do > s := (lc(r)/c) ⋅ x^(deg(r)−d) > q := q + s > r := r − sb > end do > return (q, r) > end > ``` > > - `deg(b)` returns the degree of the polynomial. For example $\mathrm{deg}(x^2 + 1) = 2$ > - `lc(c)` returns the non-zero coefficient of the term with the maximum degree. For example $\mathrm{lc}(4x^3+7x+5)=4$ > > – [Polynomial greatest common divisor - Wikipedia](https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division) ^7gzyba ```python def poly_divmod(a, b): """a, b, q, r represents polynomials tuple of coefficients from degree 0 to len-1. Returns q, r where - q is the quotient: a // b - r is the reminder: a % b """ d = len(b) r = a s_exp = len(r) - d q = [0] * max(1, s_exp + 1) c = b[-1] while s_exp >= 0: s_coeff, s_rem = divmod(r[-1], c) if s_rem != 0: break q[s_exp] = s_coeff for i in range(d): # degree of b has been raised by s_exp r[i + s_exp] -= s_coeff * b[i] if len(r) > 1: r.pop() s_exp -= 1 return q, r ``` ### Multiplicative Inverse and Division The multiplicative identity is the constant polynomial $\overline{1}_p$. The multiplicative inverse of the polynomial P is Q if $P \times Q = \overline{1}_p$. The algorithm for finding the multiplicative inverse is similar to the [[Modular Multiplicative Inverse]] algorithm, but with the substitution of `divmod` for the polynomial [[Extension Field Arithmetic#^7gzyba|Euclidean division algorithm]] described earlier. > [!important] Extended Euclidean Algorithm for Polynomials > Notice that the gcd of polynomials is required to be a monic polynomial. Divide result by the leading coefficient of the remainder. See more in the [example code](https://github.com/doitian/ecc-demo/blob/41cb148d5aef5f79059f54cc532e536ef8d3ebe4/ecc_demo/egcd.py#L19). > ![[Wikipedia Authors - Extended Euclidean Algorithm (Highlights)#^700420596]] Division is defined as multiplying the inverse of the right hand operand. $ P \div Q = P \times {\frac{1}{Q}} $ ## References - [poly.py at doitian/ecc-demo](https://github.com/doitian/ecc-demo/blob/main/ecc_demo/poly.py) - [py\_ecc euclidean division implementation](https://github.com/ethereum/py_ecc/blob/d5e5b2086483f9047cdaabf97eba7021bdf27168/py_ecc/fields/field_elements.py#L240-L245) - [Polynomial - Wikipedia](https://en.wikipedia.org/wiki/Polynomial_arithmetic) - [[Wikipedia Authors - Modular arithmetic (Highlights)]]