galois.Poly.is_primitive

galois.Poly.is_primitive() → bool

Determines whether the polynomial $f (x)$ over $GF (q)$ is primitive.

Info

This is a method, not a property, to indicate this test is computationally expensive.

Returns:¶: True if the polynomial is primitive.

Notes¶

A degree- $m$ polynomial $f (x)$ over $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]: f.is_primitive()
Out[2]: True

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

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

The irreducible polynomial of $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]: f.is_irreducible()
Out[6]: True

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