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(193, order=3^5)

In [3]: poly = a.minimal_poly(); poly
Out[3]: Poly(x^5 + 2x^4 + 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(2α^4 + 2α + 2, order=3^5)

In [8]: poly = a.minimal_poly(); poly
Out[8]: Poly(x^5 + x^3 + x^2 + 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(α^59, order=3^5)

In [13]: poly = a.minimal_poly(); poly
Out[13]: Poly(x^5 + 2x^3 + 2x^2 + x + 1, 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)))