galois.Poly.is_conway(search: bool = False) → bool

Checks whether the degree-\(m\) polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is the Conway polynomial \(C_{p,m}(x)\).

Why is this a method and not a property?

This is a method to indicate it is a computationally expensive task.

Parameters:

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:

True if the polynomial \(f(x)\) is the Conway polynomial \(C_{p,m}(x)\).

Raises:

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

See also

conway_poly, Poly.is_conway_consistent, Poly.is_primitive

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

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