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.

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$$.

Examples

All Conway polynomials are primitive.

In : GF = galois.GF(7)

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

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

In : f.is_primitive()
Out: True

In : g.is_primitive()
Out: True


They are also consistent with all smaller Conway polynomials.

In : f.is_conway_consistent()
Out: True

In : g.is_conway_consistent()
Out: True


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

In : f.is_conway()
Out: False

In : g.is_conway()
Out: True

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