galois.conway_poly(characteristic: int, degree: int, search: bool = False) → Poly

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.

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)\).

See also

Poly.is_conway, Poly.is_conway_consistent, Poly.is_primitive, primitive_poly

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\ |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\ |\ 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

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))