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