galois.is_primitive¶

galois.is_primitive(poly: Poly) → bool¶

Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive.

Parameters¶

poly: Poly¶

A degree-\(m\) polynomial \(f(x)\) over \(\mathrm{GF}(q)\).

Returns¶

True if the polynomial is primitive.

See also

is_irreducible, primitive_poly, matlab_primitive_poly, primitive_polys

Notes

A degree-\(m\) polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive if it is irreducible and \(f(x)\ |\ (x^k - 1)\) for \(k = q^m - 1\) and no \(k\) less than \(q^m - 1\).

References

• Algorithm 4.77 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf

Examples

All Conway polynomials are primitive.

In [1]: f = galois.conway_poly(2, 8); f
Out[1]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [2]: galois.is_primitive(f)
Out[2]: True

In [3]: f = galois.conway_poly(3, 5); f
Out[3]: Poly(x^5 + 2x + 1, GF(3))

In [4]: galois.is_primitive(f)
Out[4]: True

The irreducible polynomial of \(\mathrm{GF}(2^8)\) for AES is not primitive.

In [5]: f = galois.Poly.Degrees([8, 4, 3, 1, 0]); f
Out[5]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2))

In [6]: galois.is_irreducible(f)
Out[6]: True

In [7]: galois.is_primitive(f)
Out[7]: False