galois.FieldArray.minimal_poly() → Poly

Computes the minimal polynomial of a finite field element \(a\).

Returns:

For scalar inputs, the minimal polynomial \(m_a(x)\) of \(a\) over \(\mathrm{GF}(p)\).

Raises:

  • NotImplementedError – If the array is a a square \(n \times n\) matrix (2-D array).

  • ValueError – If the array is not a single finite field element (scalar 0-D array).

Notes

An element \(a\) of \(\mathrm{GF}(p^m)\) has minimal polynomial \(m_a(x)\) over \(\mathrm{GF}(p)\). The minimal polynomial when evaluated in \(\mathrm{GF}(p^m)\) annihilates \(a\), that is \(m_a(a) = 0\). The minimal polynomial always divides the characteristic polynomial. In prime fields \(\mathrm{GF}(p)\), the minimal polynomial of \(a\) is simply \(m_a(x) = x - a\).

References

Examples

The minimal polynomial of the element \(a\).

In [1]: GF = galois.GF(3**5)

In [2]: a = GF.Random(); a
Out[2]: GF(161, order=3^5)

In [3]: poly = a.minimal_poly(); poly
Out[3]: Poly(x^5 + x^4 + x^2 + x + 1, GF(3))

# The minimal polynomial annihilates a
In [4]: poly(a, field=GF)
Out[4]: GF(0, order=3^5)

# The minimal polynomial always divides the characteristic polynomial
In [5]: divmod(a.characteristic_poly(), poly)
Out[5]: (Poly(1, GF(3)), Poly(0, GF(3)))

In [6]: GF = galois.GF(3**5, repr="poly")

In [7]: a = GF.Random(); a
Out[7]: GF(α^4 + α^3 + α, order=3^5)

In [8]: poly = a.minimal_poly(); poly
Out[8]: Poly(x^5 + 2x^4 + x^3 + 2x^2 + 2x + 2, GF(3))

# The minimal polynomial annihilates a
In [9]: poly(a, field=GF)
Out[9]: GF(0, order=3^5)

# The minimal polynomial always divides the characteristic polynomial
In [10]: divmod(a.characteristic_poly(), poly)
Out[10]: (Poly(1, GF(3)), Poly(0, GF(3)))

In [11]: GF = galois.GF(3**5, repr="power")

In [12]: a = GF.Random(); a
Out[12]: GF(α^110, order=3^5)

In [13]: poly = a.minimal_poly(); poly
Out[13]: Poly(x^5 + x^4 + 2x^3 + x^2 + 2, GF(3))

# The minimal polynomial annihilates a
In [14]: poly(a, field=GF)
Out[14]: GF(0, order=3^5)

# The minimal polynomial always divides the characteristic polynomial
In [15]: divmod(a.characteristic_poly(), poly)
Out[15]: (Poly(1, GF(3)), Poly(0, GF(3)))