Returns the Conway polynomial $C_{p,m}(x)$ over $\mathrm{GF}(p)$ with degree $m$.

Parameters:¶

characteristic: int¶

The prime characteristic $p$ of the field $\mathrm{GF}(p)$ that the polynomial is over.

degree: int¶

The degree $m$ of the Conway polynomial.

search: bool = False¶

Manually search for Conway polynomials if they are not included in Frank Luebeck’s database. The default is False.

Slower performance

Manually searching for a Conway polynomial is very computationally expensive.

Returns:¶

The degree-$m$ Conway polynomial $C_{p,m}(x)$ over $\mathrm{GF}(p)$.

Raises:¶

LookupError – If search=False and the Conway polynomial $C_{p,m}$ is not found in Frank Luebeck’s database.

Notes

A degree-$m$ polynomial $f(x)$ over $\mathrm{GF}(p)$ is the Conway polynomial $C_{p,m}(x)$ if it is monic, primitive, compatible with Conway polynomials $C_{p,n}(x)$ for all $n\mid m$, and is lexicographically first according to a special ordering.

A Conway polynomial $C_{p,m}(x)$ is compatible with Conway polynomials $C_{p,n}(x)$ for $n\mid m$ if $C_{p,n}(x^r)$ divides $C_{p,m}(x)$, where $r=\frac{p^m-1}{p^n-1}$.

The Conway lexicographic ordering is defined as follows. Given two degree-$m$ polynomials $g(x)=\sum _{i=0}^m{g}_i{x}^i$ and $h(x)=\sum _{i=0}^m{h}_i{x}^i$, then $g<h$ if and only if there exists $i$ such that $g_j=h_j$ for all $j>i$ and $(-1{)}^{m-i}{g}_i<(-1{)}^{m-i}{h}_i$.

The Conway polynomial $C_{p,m}(x)$ provides a standard representation of $\mathrm{GF}(p^m)$ as a splitting field of $C_{p,m}(x)$. Conway polynomials provide compatibility between fields and their subfields and, hence, are the common way to represent extension fields.

References

• http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/CP7.html

• Lenwood S. Heath, Nicholas A. Loehr, New algorithms for generating Conway polynomials over finite fields, Journal of Symbolic Computation, Volume 38, Issue 2, 2004, Pages 1003-1024, https://www.sciencedirect.com/science/article/pii/S0747717104000331.

Examples

All Conway polynomials are primitive.

In [1]: GF = galois.GF(7)

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

In [3]: g = galois.Poly([1, 6, 0, 4], field=GF); g
Out[3]: Poly(x^3 + 6x^2 + 4, GF(7))

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

In [5]: g.is_primitive()
Out[5]: True

They are also consistent with all smaller Conway polynomials.

In [6]: f.is_conway_consistent()
Out[6]: True

In [7]: g.is_conway_consistent()
Out[7]: True

Among the multiple candidate Conway polynomials, the lexicographically first (accordingly to a special lexicographical order) is the Conway polynomial.

In [8]: f.is_conway()
Out[8]: False

In [9]: g.is_conway()
Out[9]: True

In [10]: galois.conway_poly(7, 3)
Out[10]: Poly(x^3 + 6x^2 + 4, GF(7))