# 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)]]