galois.minimal_poly

galois.minimal_poly(element)

Computes the minimal polynomial \(m_e(x) \in \mathrm{GF}(p)[x]\) of a Galois field element \(e \in \mathrm{GF}(p^m)\).

The minimal polynomial of a Galois field element \(e \in \mathrm{GF}(p^m)\) is the polynomial of minimal degree over \(\mathrm{GF}(p)\) for which \(e\) is a root when evaluated in \(\mathrm{GF}(p^m)\). Namely, \(m_e(x) \in \mathrm{GF}(p)[x] \in \mathrm{GF}(p^m)[x]\) and \(m_e(e) = 0\) over \(\mathrm{GF}(p^m)\).

Parameters

element (galois.FieldArray) – Any element \(e\) of the Galois field \(\mathrm{GF}(p^m)\). This must be a 0-D array.

Returns

The minimal polynomial \(m_e(x)\) over \(\mathrm{GF}(p)\) of the element \(e\).

Return type

galois.Poly

Examples

In [1]: GF = galois.GF(2**4)

In [2]: e = GF.primitive_element; e
Out[2]: GF(2, order=2^4)

In [3]: m_e = galois.minimal_poly(e); m_e
Out[3]: Poly(x^4 + x + 1, GF(2))

# Evaluate m_e(e) in GF(2^4)
In [4]: m_e(e, field=GF)
Out[4]: GF(0, order=2^4)

For a given element \(e\), the minimal polynomials of \(e\) and all its conjugates are the same.

# The conjugates of e
In [5]: conjugates = np.unique(e**(2**np.arange(0, 4))); conjugates
Out[5]: GF([2, 3, 4, 5], order=2^4)

In [6]: for conjugate in conjugates:
   ...:     print(galois.minimal_poly(conjugate))
   ...: 
Poly(x^4 + x + 1, GF(2))
Poly(x^4 + x + 1, GF(2))
Poly(x^4 + x + 1, GF(2))
Poly(x^4 + x + 1, GF(2))

Not all elements of \(\mathrm{GF}(2^4)\) have minimal polynomials with degree-\(4\).

In [7]: e = GF.primitive_element**5; e
Out[7]: GF(6, order=2^4)

# The conjugates of e
In [8]: conjugates = np.unique(e**(2**np.arange(0, 4))); conjugates
Out[8]: GF([6, 7], order=2^4)

In [9]: for conjugate in conjugates:
   ...:     print(galois.minimal_poly(conjugate))
   ...: 
Poly(x^2 + x + 1, GF(2))
Poly(x^2 + x + 1, GF(2))

In prime fields, the minimal polynomial of \(e\) is simply \(m_e(x) = x - e\).

In [10]: GF = galois.GF(7)

In [11]: e = GF(3); e
Out[11]: GF(3, order=7)

In [12]: m_e = galois.minimal_poly(e); m_e
Out[12]: Poly(x + 4, GF(7))

In [13]: m_e(e)
Out[13]: GF(0, order=7)