# Finite Field ## Metadata **Status**:: #x **Zettel**:: #zettel/fleeting **Created**:: [[2024-03-20]] **Wiki**:: [[Wikipedia Authors - Finite field]] **Topic**:: [[♯ Math]] ## Synopsis Finite Field is a [[Field]] with finite members. ## Prime Finite Field $GF(p)$ is the Prime Finite Field with the prime order $p$. An example of such field is the integers modulo $p$, annotated as ${\mathbb{Z}/p\mathbb{Z}}$. (**see**:: [[Modular Arithmetic]]) ## Prime Power Finite Field Aliases: Galois Extension. For $q = p^n$ where $p$ is a prime and $n > 1$, there exists a unique (up to isomorphism) finite field $\mathrm{GF}(q) = \mathbb{F}_q$ with q elements. ^hs77wz ### Example Polynomials Field For $\mathrm {GF} (q)$ where $q = p^n$, p is a prime, and n > 1. $ \mathrm {GF} (q)=\mathrm {GF} (p)[X]/(P) $ - P is an [[Irreducible Polynomial]] in $\mathrm {GF} (p)[X]$ of degree _n_ - Elements of `GF(q)` are the polynomials over ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ whose degree is strictly less than n. - Addition and subtraction are those of polynomials over ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ - Product of two elements is the reminder of the euclidean division by P of the product in $\mathrm {GF} (p)[X]$. See more about the operations in [[Extension Field Arithmetic]]. The annotation $\mathrm{GF(p)}[X]$ represents the set of all polynomials with a single variable X and all the coefficients are over the field $\mathrm{GF}(p)$. $ \mathrm{GF}(p)[X] = \{a_0 + a_1X + \ldots + a_nX^n \mid a_i \in \mathrm{GF}(p), n \in \mathbb{Z}_{\geq 0}\} $ $P$ has the form $P = a_0 + a_1X + \ldots + a_pX^p$ $\mathrm{GF}(q)$ is a subset of $\mathrm{GF}(p)[X]$. It contains only polynomials whose degree is at most $p$. $ \mathrm{GF}(q) = \{a_0 + a_1X + \ldots + a_nX^n \mid a_i \in \mathrm{GF}(p), n \in \mathbb{Z}_{\geq 0}, n \lt p\} $ > [!tip] Intuition of Polynomial Over Finite Field $\mathrm{GF}(p)$ > Similar to p-based number system. > [!summary] Different Moduli in Polynomial Over Finite Field $\mathrm{GF}(p)$ > - Modulus of coefficients is $p$. > - Modulus of the polynomial product s the irreducible polynomial $P$. ### Python Example There's a python library named [galois](https://mhostetter.github.io/galois/latest/) which can create the field $\mathrm {GF} (p^n)$. Example to get the reminder of polynomial division over finite field: ```python from sympy import rem, poly, GF from sympy.abc import x Z = GF(53, symmetric=False) t = poly(x**3 + x + 5, domain=Z) # see [1] y = poly(x**5 + 23*x**3 + x + 5, domain=Z) r = rem(y, t) print('y % t = r') print(f'y = {y.as_expr()}') print(f't = {t.as_expr()}') print(f'r = {r.as_expr()}') # => y % t = r # => y = x**5 + 23*x**3 + x + 5 # => t = x**3 + x + 5 # => r = 48*x**2 + 32*x + 1 ``` \[1] Attention that sympy allows negative number in finite field. See [[Sympy Finite Field Representation]] how to force non-negative coefficients. ### Numeric Encoding The polynomial can be represented as a number using p-based number system. For example, the polynomial $\sum_{i=0}^{n-1} a_ix^i$ over the field $\mathrm{GF}(p)$ can be represented as: $ \sum_{i=0}^{n-1}a_ip^i $ But Prime Power Field $\mathrm{GF}(q)$ when $q = p^n$ is not isomorphic to integer modular set ${\mathbb {Z} /q\mathbb {Z} }$. ${\mathbb {Z} /q\mathbb {Z} }$ is a ring since not every member has a multiplicative inverse.