galois.Poly¶
-
class
galois.
Poly
(coeffs, field=None, order='desc')[source]¶ Create a polynomial \(p(x)\) over \(\mathrm{GF}(q)\).
The polynomial \(p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) has coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(q)\).
- Parameters
coeffs (array_like) – List of polynomial coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) with type
galois.GFArray
,numpy.ndarray
,list
, ortuple
. The first element is the highest-degree element iforder="desc"
or the first element is the 0-th degree element iforder="asc"
.field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
None
which representsgalois.GF2
. Ifcoeffs
is a Galois field array, then that field is used and thefield
argument is ignored.order (str, optional) – The interpretation of the coefficient degrees, either
"desc"
(default) or"asc"
. For"desc"
, the first element ofcoeffs
is the highest degree coefficient \(x^{d}\)) and the last element is the 0-th degree element \(x^0\).
- Returns
The polynomial \(p(x)\).
- Return type
Examples
Create a polynomial over \(\mathrm{GF}(2)\).
In [205]: galois.Poly([1,0,1,1]) Out[205]: Poly(x^3 + x + 1, GF(2)) In [206]: galois.Poly.Degrees([3,1,0]) Out[206]: Poly(x^3 + x + 1, GF(2))
Create a polynomial over \(\mathrm{GF}(2^8)\).
In [207]: GF = galois.GF(2**8) In [208]: galois.Poly([124,0,223,0,0,15], field=GF) Out[208]: Poly(124x^5 + 223x^3 + 15, GF(2^8)) # Alternate way of constructing the same polynomial In [209]: galois.Poly.Degrees([5,3,0], coeffs=[124,223,15], field=GF) Out[209]: Poly(124x^5 + 223x^3 + 15, GF(2^8))
Polynomial arithmetic using binary operators.
In [210]: a = galois.Poly([117,0,63,37], field=GF); a Out[210]: Poly(117x^3 + 63x + 37, GF(2^8)) In [211]: b = galois.Poly([224,0,21], field=GF); b Out[211]: Poly(224x^2 + 21, GF(2^8)) In [212]: a + b Out[212]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8)) In [213]: a - b Out[213]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8)) # Compute the quotient of the polynomial division In [214]: a / b Out[214]: Poly(202x, GF(2^8)) # True division and floor division are equivalent In [215]: a / b == a // b Out[215]: True # Compute the remainder of the polynomial division In [216]: a % b Out[216]: Poly(198x + 37, GF(2^8)) # Compute both the quotient and remainder in one pass In [217]: divmod(a, b) Out[217]: (Poly(202x, GF(2^8)), Poly(198x + 37, GF(2^8)))
- special-members
__call__
Constructors
Coeffs
(coeffs[, field, order])Constructs a polynomial over \(\mathrm{GF}(q)\) from its coefficients.
Degrees
(degrees[, coeffs, field])Constructs a polynomial over \(\mathrm{GF}(q)\) from its non-zero degrees.
Identity
([field])Constructs the identity polynomial \(p(x) = x\) over \(\mathrm{GF}(q)\).
Integer
(integer[, field])Constructs a polynomial over \(\mathrm{GF}(q)\) from its integer representation.
One
([field])Constructs the one polynomial \(p(x) = 1\) over \(\mathrm{GF}(q)\).
Random
(degree[, field])Constructs a random polynomial over \(\mathrm{GF}(q)\) with degree \(d\).
Roots
(roots[, multiplicities, field])Constructs a monic polynomial in \(\mathrm{GF}(q)[x]\) from its roots.
Zero
([field])Constructs the zero polynomial \(p(x) = 0\) over \(\mathrm{GF}(q)\).
Methods
derivative
([k])Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} p(x)\) of the polynomial \(p(x)\).
roots
([multiplicity])Calculates the roots \(r\) of the polynomial \(p(x)\), such that \(p(r) = 0\).
Attributes
The coefficients of the polynomial in degree-descending order.
The degree of the polynomial, i.e. the highest degree with non-zero coefficient.
An array of the polynomial degrees in degree-descending order.
The Galois field to which the coefficients belong.
The integer representation of the polynomial.
The non-zero coefficients of the polynomial in degree-descending order.
An array of the polynomial degrees that have non-zero coefficients, in degree-descending order.
-
classmethod
Coeffs
(coeffs, field=None, order='desc')[source]¶ Constructs a polynomial over \(\mathrm{GF}(q)\) from its coefficients.
Alias of
galois.Poly
constructor.- Parameters
coeffs (array_like) – List of polynomial coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) with type
galois.GFArray
,numpy.ndarray
,list
, ortuple
. The first element is the highest-degree element iforder="desc"
or the first element is the 0-th degree element iforder="asc"
.field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
None
which representsgalois.GF2
. Ifcoeffs
is a Galois field array, then that field is used and thefield
argument is ignored.order (str, optional) – The interpretation of the coefficient degrees, either
"desc"
(default) or"asc"
. For"desc"
, the first element ofcoeffs
is the highest degree coefficient \(x^{d}\)) and the last element is the 0-th degree element \(x^0\).
- Returns
The polynomial \(p(x)\).
- Return type
-
classmethod
Degrees
(degrees, coeffs=None, field=None)[source]¶ Constructs a polynomial over \(\mathrm{GF}(q)\) from its non-zero degrees.
- Parameters
degrees (list) – List of polynomial degrees with non-zero coefficients.
coeffs (array_like, optional) – List of corresponding non-zero coefficients. The default is
None
which corresponds to all one coefficients, i.e.[1,]*len(degrees)
.field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is`None` which represents
galois.GF2
.
- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) by specifying the degrees with non-zero coefficients.
In [218]: galois.Poly.Degrees([3,1,0]) Out[218]: Poly(x^3 + x + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) by specifying the degrees with non-zero coefficients.
In [219]: GF = galois.GF(2**8) In [220]: galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF) Out[220]: Poly(251x^3 + 73x + 185, GF(2^8))
-
classmethod
Identity
(field=<class 'numpy.ndarray over GF(2)'>)[source]¶ Constructs the identity polynomial \(p(x) = x\) over \(\mathrm{GF}(q)\).
- Parameters
field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct the identity polynomial over \(\mathrm{GF}(2)\).
In [221]: galois.Poly.Identity() Out[221]: Poly(x, GF(2))
Construct the identity polynomial over \(\mathrm{GF}(2^8)\).
In [222]: GF = galois.GF(2**8) In [223]: galois.Poly.Identity(field=GF) Out[223]: Poly(x, GF(2^8))
-
classmethod
Integer
(integer, field=<class 'numpy.ndarray over GF(2)'>)[source]¶ Constructs a polynomial over \(\mathrm{GF}(q)\) from its integer representation.
The integer value \(i\) represents the polynomial \(p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) over field \(\mathrm{GF}(q)\) if \(i = a_{d}q^{d} + a_{d-1}q^{d-1} + \dots + a_1q + a_0\) using integer arithmetic, not finite field arithmetic.
- Parameters
integer (int) – The integer representation of the polynomial \(p(x)\).
field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from its integer representation.
In [224]: galois.Poly.Integer(5) Out[224]: Poly(x^2 + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) from its integer representation.
In [225]: GF = galois.GF(2**8) In [226]: galois.Poly.Integer(13*256**3 + 117, field=GF) Out[226]: Poly(13x^3 + 117, GF(2^8))
-
classmethod
One
(field=<class 'numpy.ndarray over GF(2)'>)[source]¶ Constructs the one polynomial \(p(x) = 1\) over \(\mathrm{GF}(q)\).
- Parameters
field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct the one polynomial over \(\mathrm{GF}(2)\).
In [227]: galois.Poly.One() Out[227]: Poly(1, GF(2))
Construct the one polynomial over \(\mathrm{GF}(2^8)\).
In [228]: GF = galois.GF(2**8) In [229]: galois.Poly.One(field=GF) Out[229]: Poly(1, GF(2^8))
-
classmethod
Random
(degree, field=<class 'numpy.ndarray over GF(2)'>)[source]¶ Constructs a random polynomial over \(\mathrm{GF}(q)\) with degree \(d\).
- Parameters
degree (int) – The degree of the polynomial.
field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2)\).
In [230]: galois.Poly.Random(5) Out[230]: Poly(x^5 + x^4, GF(2))
Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2^8)\).
In [231]: GF = galois.GF(2**8) In [232]: galois.Poly.Random(5, field=GF) Out[232]: Poly(82x^5 + 236x^4 + 208x^3 + 49x^2 + 52x + 226, GF(2^8))
-
classmethod
Roots
(roots, multiplicities=None, field=None)[source]¶ Constructs a monic polynomial in \(\mathrm{GF}(q)[x]\) from its roots.
The polynomial \(p(x)\) with \(d\) roots \(\{r_0, r_1, \dots, r_{d-1}\}\) is:
\[ \begin{align}\begin{aligned}p(x) &= (x - r_0) (x - r_1) \dots (x - r_{d-1})\\p(x) &= a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\end{aligned}\end{align} \]- Parameters
roots (array_like) – List of roots in \(\mathrm{GF}(q)\) of the desired polynomial.
multiplicities (array_like, optional) – List of multiplicity of each root. The default is
None
which corresponds to all ones.field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is`None` which represents
galois.GF2
.
- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from a list of its roots.
In [233]: roots = [0, 0, 1] In [234]: p = galois.Poly.Roots(roots); p Out[234]: Poly(x^3 + x^2, GF(2)) In [235]: p(roots) Out[235]: GF([0, 0, 0], order=2)
Construct a polynomial over \(\mathrm{GF}(2^8)\) from a list of its roots.
In [236]: GF = galois.GF(2**8) In [237]: roots = [121, 198, 225] In [238]: p = galois.Poly.Roots(roots, field=GF); p Out[238]: Poly(x^3 + 94x^2 + 174x + 89, GF(2^8)) In [239]: p(roots) Out[239]: GF([0, 0, 0], order=2^8)
-
classmethod
Zero
(field=<class 'numpy.ndarray over GF(2)'>)[source]¶ Constructs the zero polynomial \(p(x) = 0\) over \(\mathrm{GF}(q)\).
- Parameters
field (galois.GFArray, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(p(x)\).
- Return type
Examples
Construct the zero polynomial over \(\mathrm{GF}(2)\).
In [240]: galois.Poly.Zero() Out[240]: Poly(0, GF(2))
Construct the zero polynomial over \(\mathrm{GF}(2^8)\).
In [241]: GF = galois.GF(2**8) In [242]: galois.Poly.Zero(field=GF) Out[242]: Poly(0, GF(2^8))
-
derivative
(k=1)[source]¶ Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} p(x)\) of the polynomial \(p(x)\).
For the polynomial
\[p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\]the first formal derivative is defined as
\[p'(x) = (d) \cdot a_{d} x^{d-1} + (d-1) \cdot a_{d-1} x^{d-2} + \dots + (2) \cdot a_{2} x + a_1\]where \(\cdot\) represents scalar multiplication (repeated addition), not finite field multiplication, e.g. \(3 \cdot a = a + a + a\).
- Parameters
k (int, optional) – The number of derivatives to compute. 1 corresponds to \(p'(x)\), 2 corresponds to \(p''(x)\), etc. The default is 1.
- Returns
The \(k\)-th formal derivative of the polynomial \(p(x)\).
- Return type
References
Examples
Compute the derivatives of a polynomial over \(\mathrm{GF}(2)\).
In [243]: p = galois.Poly.Random(7); p Out[243]: Poly(x^7 + x^4 + x^3 + x, GF(2)) In [244]: p.derivative() Out[244]: Poly(x^6 + x^2 + 1, GF(2)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [245]: p.derivative(2) Out[245]: Poly(0, GF(2))
Compute the derivatives of a polynomial over \(\mathrm{GF}(7)\).
In [246]: GF = galois.GF(7) In [247]: p = galois.Poly.Random(11, field=GF); p Out[247]: Poly(3x^11 + x^10 + 3x^9 + 2x^8 + 6x^7 + x^4 + x^2 + 6x + 4, GF(7)) In [248]: p.derivative() Out[248]: Poly(5x^10 + 3x^9 + 6x^8 + 2x^7 + 4x^3 + 2x + 6, GF(7)) In [249]: p.derivative(2) Out[249]: Poly(x^9 + 6x^8 + 6x^7 + 5x^2 + 2, GF(7)) In [250]: p.derivative(3) Out[250]: Poly(2x^8 + 6x^7 + 3x, GF(7)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [251]: p.derivative(7) Out[251]: Poly(0, GF(2))
Compute the derivatives of a polynomial over \(\mathrm{GF}(2^8)\).
In [252]: GF = galois.GF(2**8) In [253]: p = galois.Poly.Random(7, field=GF); p Out[253]: Poly(63x^7 + 173x^6 + 166x^5 + 121x^4 + 238x^3 + 76x^2 + 183x + 219, GF(2^8)) In [254]: p.derivative() Out[254]: Poly(63x^6 + 166x^4 + 238x^2 + 183, GF(2^8)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [255]: p.derivative(2) Out[255]: Poly(0, GF(2^8))
-
roots
(multiplicity=False)[source]¶ Calculates the roots \(r\) of the polynomial \(p(x)\), such that \(p(r) = 0\).
This implementation uses Chien’s search to find the roots \(\{r_0, r_1, \dots, r_{k-1}\}\) of the degree-\(d\) polynomial
\[p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0,\]where \(k \le d\). Then, \(p(x)\) can be factored as
\[p(x) = (x - r_0)^{m_0} (x - r_1)^{m_1} \dots (x - r_{k-1})^{m_{k-1}},\]where \(m_i\) is the multiplicity of root \(r_i\) and
\[\sum_{i=0}^{k-1} m_i = d.\]The Galois field elements can be represented as \(\mathrm{GF}(q) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{q-2}\}\), where \(\alpha\) is a primitive element of \(\mathrm{GF}(q)\).
\(0\) is a root of \(p(x)\) if:
\[a_0 = 0\]\(1\) is a root of \(p(x)\) if:
\[\sum_{j=0}^{d} a_j = 0\]The remaining elements of \(\mathrm{GF}(q)\) are powers of \(\alpha\). The following equations calculate \(p(\alpha^i)\), where \(\alpha^i\) is a root of \(p(x)\) if \(p(\alpha^i) = 0\).
\[ \begin{align}\begin{aligned}p(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0\\p(\alpha^i) &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0}\\p(\alpha^i) &= \sum_{j=0}^{d} \lambda_{i,j}\end{aligned}\end{align} \]The next power of \(\alpha\) can be easily calculated from the previous calculation.
\[ \begin{align}\begin{aligned}p(\alpha^{i+1}) &= a_{d}(\alpha^{i+1})^{d} + a_{d-1}(\alpha^{i+1})^{d-1} + \dots + a_1(\alpha^{i+1}) + a_0\\p(\alpha^{i+1}) &= a_{d}(\alpha^i)^{d}\alpha^d + a_{d-1}(\alpha^i)^{d-1}\alpha^{d-1} + \dots + a_1(\alpha^i)\alpha + a_0\\p(\alpha^{i+1}) &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0}\\p(\alpha^{i+1}) &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{aligned}\end{align} \]- Parameters
multiplicity (bool, optional) – Optionally return the multiplicity of each root. The default is
False
, which only returns the unique roots.- Returns
galois.GFArray – Galois field array of roots of \(p(x)\).
np.ndarray – The multiplicity of each root. Only returned if
multiplicity=True
.
References
Examples
Find the roots of a polynomial over \(\mathrm{GF}(2)\).
In [256]: p = galois.Poly.Roots([0,]*7 + [1,]*13); p Out[256]: Poly(x^20 + x^19 + x^16 + x^15 + x^12 + x^11 + x^8 + x^7, GF(2)) In [257]: p.roots() Out[257]: GF([0, 1], order=2) In [258]: p.roots(multiplicity=True) Out[258]: (GF([0, 1], order=2), array([ 7, 13]))
Find the roots of a polynomial over \(\mathrm{GF}(2^8)\).
In [259]: GF = galois.GF(2**8) In [260]: p = galois.Poly.Roots([18,]*7 + [155,]*13 + [227,]*9, field=GF); p Out[260]: Poly(x^29 + 106x^28 + 27x^27 + 155x^26 + 230x^25 + 38x^24 + 78x^23 + 8x^22 + 46x^21 + 210x^20 + 248x^19 + 214x^18 + 172x^17 + 152x^16 + 82x^15 + 237x^14 + 172x^13 + 230x^12 + 141x^11 + 63x^10 + 103x^9 + 167x^8 + 199x^7 + 127x^6 + 254x^5 + 95x^4 + 93x^3 + 3x^2 + 4x + 208, GF(2^8)) In [261]: p.roots() Out[261]: GF([ 18, 155, 227], order=2^8) In [262]: p.roots(multiplicity=True) Out[262]: (GF([ 18, 155, 227], order=2^8), array([ 7, 13, 9]))
-
property
coeffs
¶ The coefficients of the polynomial in degree-descending order. The entries of
galois.Poly.degrees
are paired withgalois.Poly.coeffs
.Examples
In [263]: GF = galois.GF(7) In [264]: p = galois.Poly([3, 0, 5, 2], field=GF) In [265]: p.coeffs Out[265]: GF([3, 0, 5, 2], order=7)
- Type
-
property
degree
¶ The degree of the polynomial, i.e. the highest degree with non-zero coefficient.
Examples
In [266]: GF = galois.GF(7) In [267]: p = galois.Poly([3, 0, 5, 2], field=GF) In [268]: p.degree Out[268]: 3
- Type
-
property
degrees
¶ An array of the polynomial degrees in degree-descending order. The entries of
galois.Poly.degrees
are paired withgalois.Poly.coeffs
.Examples
In [269]: GF = galois.GF(7) In [270]: p = galois.Poly([3, 0, 5, 2], field=GF) In [271]: p.degrees Out[271]: array([3, 2, 1, 0])
- Type
-
property
field
¶ The Galois field to which the coefficients belong. The
galois.Poly.field
property is a subclass ofgalois.GFArray
. This property is settable.Examples
In [272]: GF = galois.GF(2**8) # The primitive polynomial of the field GF(p^m) is degree-m over GF(p)[x] In [273]: prim_poly = GF.irreducible_poly; prim_poly Out[273]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2)) In [274]: prim_poly.field Out[274]: <class 'numpy.ndarray over GF(2)'> # Convert the primitive polynomial from GF(p)[x] to GF(p^m)[x] In [275]: prim_poly.field = GF; prim_poly Out[275]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2^8)) # The primitive element alpha is a root of the primitive polynomial in GF(p^m) In [276]: prim_poly(GF.primitive_element) Out[276]: GF(0, order=2^8)
- Type
-
property
integer
¶ The integer representation of the polynomial. For polynomial \(p(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0\) with elements in \(a_k \in \mathrm{GF}(q)\), the integer representation is \(i = a_{d} q^{d} + a_{d-1} q^{d-1} + \dots + a_1 q + a_0\) (using integer arithmetic, not finite field arithmetic).
Examples
In [277]: GF = galois.GF(7) In [278]: p = galois.Poly([3, 0, 5, 2], field=GF) In [279]: p.integer Out[279]: 1066 In [280]: p.integer == 3*7**3 + 5*7**1 + 2*7**0 Out[280]: True
- Type
-
property
nonzero_coeffs
¶ The non-zero coefficients of the polynomial in degree-descending order. The entries of
galois.Poly.nonzero_degrees
are paired withgalois.Poly.nonzero_coeffs
.Examples
In [281]: GF = galois.GF(7) In [282]: p = galois.Poly([3, 0, 5, 2], field=GF) In [283]: p.nonzero_coeffs Out[283]: GF([3, 5, 2], order=7)
- Type
-
property
nonzero_degrees
¶ An array of the polynomial degrees that have non-zero coefficients, in degree-descending order. The entries of
galois.Poly.nonzero_degrees
are paired withgalois.Poly.nonzero_coeffs
.Examples
In [284]: GF = galois.GF(7) In [285]: p = galois.Poly([3, 0, 5, 2], field=GF) In [286]: p.nonzero_degrees Out[286]: array([3, 1, 0])
- Type