# Irreducible Polynomial
## Metadata
**Status**:: #x
**Zettel**:: #zettel/literature
**Created**:: [[2024-03-25]]
**Wiki**:: [Wikipedia](https://en.wikipedia.org/wiki/Irreducible_polynomial)
**Parent**:: [[Elliptic Curve]]
## Synopsis
In mathematics, an **irreducible polynomial** is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials (with non-zero degree).
Another definition is that a polynomial $p(x)$ is irreducible if it cannot be written as $g(x) \cdot h(x)$ where both g, h has strict lesser degree than p.
The irreducible polynomial acts as the role of prime number for polynomials defined over $\mathrm{GF}(p)$, and is used as the modulus in the [[Finite Field#Prime Power Finite Field|Galois Extension]].
## Irreducible Polynomials of a Given Degree
Find irreducible polynomials of degree d over the prime [[Finite Field]] $\mathrm{GF}(p)$.
The following two algorithms both require a [factoring algorithm].
### Factor $X^{p^d}-X$
According to [Wikipedia](https://en.wikipedia.org/wiki/Finite_field#Irreducible_polynomials_of_a_given_degree), if $q = p^n$ then $X^q-X$ is the product of all monic irreducible polynomials over $\mathrm{GF}(p)$, whose degree divides n. Because any number divides itself, the irreducible polynomial of degree d is a factor of $X^{p^d} -X$. To find the irreducible polynomial of degree d, we can use a [factoring algorithm] to obtain the factor list of $X^{p^d} -X$, and then select any factor with the degree d.
> [!info] Monic Polynomial
> Polynomial which leading coefficient is 1.
Example code to find the irreducible polynomial of degree 3 using [[♯ Sympy|Sympy]]:
```python
from sympy import poly, GF, factor_list
from sympy.abc import x
Z = GF(2, symmetric=False)
y = poly(x**(2**3) - x, domain=Z)
for p in factor_list(y)[1]:
print(p[0].as_expr())
# => x
# => x + 1
# => x**3 + x + 1
# => x**3 + x**2 + 1
```
There are two irreducible polynomial of degree 3
- $x^3 + x + 1$
- $x^3 + x^2 + 1$
### Search and Test
Factoring $X^{p^d}-X$ is expansive. A practical algorithm is iterate all candidates and test whether it is irreducible by using a [factoring algorithm].
The python library galios uses such [an algorithm](https://github.com/mhostetter/galois/blob/main/src/galois/_polys/_irreducible.py) to find irreducible polynomials.
```python
import galois
print(galois.GF(2**3).properties)
# => Galois Field:
# => name: GF(2^3)
# => characteristic: 2
# => degree: 3
# => order: 8
# => irreducible_poly: x^3 + x + 1
# => is_primitive_poly: True
# => primitive_element: x
```
[factoring algorithm]: https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Factoring_algorithms