galois.is_primitive¶
- class galois.is_primitive(poly)¶
Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive.
A degree-\(n\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive if \(f(x)\ |\ (x^k - 1)\) for \(k = p^n - 1\) and no \(k\) less than \(p^n - 1\).
- Parameters
poly (galois.Poly) – A polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
- Returns
True
if the polynomial is primitive.- Return type
References
Algorithm 4.77 from https://cacr.uwaterloo.ca/hac/about/chap4.pdf
Examples
All Conway polynomials are primitive.
In [527]: f = galois.conway_poly(2, 8); f Out[527]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) In [528]: galois.is_primitive(f) Out[528]: True In [529]: f = galois.conway_poly(3, 5); f Out[529]: Poly(x^5 + 2x + 1, GF(3)) In [530]: galois.is_primitive(f) Out[530]: True
The irreducible polynomial of \(\mathrm{GF}(2^8)\) for AES is not primitive.
In [531]: f = galois.Poly.Degrees([8,4,3,1,0]); f Out[531]: Poly(x^8 + x^4 + x^3 + x + 1, GF(2)) In [532]: galois.is_primitive(f) Out[532]: False