galois.Poly
- class galois.Poly(coeffs, field=None, order='desc')
Create a polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).
The polynomial \(f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) has coefficients \(\{a_{d}, a_{d-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(p^m)\).
- Parameters
coeffs (tuple, list, numpy.ndarray, galois.FieldArray) – The polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) with type
galois.FieldArray
. Alternatively, an iterabletuple
,list
, ornumpy.ndarray
may be provided and the Galois field domain is taken from thefield
keyword argument.field (galois.FieldClass, optional) –
The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.
None
(default): If the coefficients are agalois.FieldArray
, they won’t be modified. If the coefficients are not explicitly in a Galois field, they are assumed to be from \(\mathrm{GF}(2)\) and are converted usinggalois.GF2(coeffs)
.galois.FieldClass
: The coefficients are explicitly converted to this Galois fieldfield(coeffs)
.
order (str, optional) –
The interpretation of the coefficient degrees.
"desc"
(default): The first element ofcoeffs
is the highest degree coefficient, i.e. \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\)."asc"
: The first element ofcoeffs
is the lowest degree coefficient, i.e. \(\{a_0, a_1, \dots, a_{d-1}, a_d\}\).
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Create a polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly([1,0,1,1]) Out[1]: Poly(x^3 + x + 1, GF(2)) In [2]: galois.Poly.Degrees([3,1,0]) Out[2]: Poly(x^3 + x + 1, GF(2))
Create a polynomial over \(\mathrm{GF}(2^8)\).
In [3]: GF = galois.GF(2**8) In [4]: galois.Poly([124,0,223,0,0,15], field=GF) Out[4]: Poly(124x^5 + 223x^3 + 15, GF(2^8)) # Alternate way of constructing the same polynomial In [5]: galois.Poly.Degrees([5,3,0], coeffs=[124,223,15], field=GF) Out[5]: Poly(124x^5 + 223x^3 + 15, GF(2^8))
Polynomial arithmetic using binary operators.
In [6]: a = galois.Poly([117,0,63,37], field=GF); a Out[6]: Poly(117x^3 + 63x + 37, GF(2^8)) In [7]: b = galois.Poly([224,0,21], field=GF); b Out[7]: Poly(224x^2 + 21, GF(2^8)) In [8]: a + b Out[8]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8)) In [9]: a - b Out[9]: Poly(117x^3 + 224x^2 + 63x + 48, GF(2^8)) # Compute the quotient of the polynomial division In [10]: a / b Out[10]: Poly(202x, GF(2^8)) # True division and floor division are equivalent In [11]: a / b == a // b Out[11]: True # Compute the remainder of the polynomial division In [12]: a % b Out[12]: Poly(198x + 37, GF(2^8)) # Compute both the quotient and remainder in one pass In [13]: divmod(a, b) Out[13]: (Poly(202x, GF(2^8)), Poly(198x + 37, GF(2^8)))
Constructors
__init__
()Degrees
(degrees[, coeffs, field])Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its non-zero degrees.
Identity
([field])Constructs the polynomial \(f(x) = x\) over \(\mathrm{GF}(p^m)\).
Integer
(integer[, field])Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its integer representation.
One
([field])Constructs the polynomial \(f(x) = 1\) over \(\mathrm{GF}(p^m)\).
Random
(degree[, seed, field])Constructs a random polynomial over \(\mathrm{GF}(p^m)\) with degree \(d\).
Roots
(roots[, multiplicities, field])Constructs a monic polynomial over \(\mathrm{GF}(p^m)\) from its roots.
String
(string[, field])Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its string representation.
Zero
([field])Constructs the polynomial \(f(x) = 0\) over \(\mathrm{GF}(p^m)\).
Methods
derivative
([k])Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} f(x)\) of the polynomial \(f(x)\).
reverse
()Returns the \(d\)-th reversal \(x^d f(\frac{1}{x})\) of the polynomial \(f(x)\) with degree \(d\).
roots
([multiplicity])Calculates the roots \(r\) of the polynomial \(f(x)\), such that \(f(r) = 0\).
Special Methods
__add__
(other)Adds two polynomials.
__divmod__
(other)Divides two polynomials and returns the quotient and remainder.
__floordiv__
(other)Divides two polynomials and returns the quotient.
__mod__
(other)Divides two polynomials and returns the remainder.
__mul__
(other)Multiplies two polynomials.
__pow__
(other)Exponentiates the polynomial to an integer power.
__sub__
(other)Subtracts two polynomials.
__truediv__
(other)Divides two polynomials and returns the quotient.
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 array class 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.
The string representation of the polynomial, without specifying the Galois field.
- classmethod Degrees(degrees, coeffs=None, field=None)
Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its non-zero degrees.
- Parameters
degrees (tuple, list, numpy.ndarray) – The polynomial degrees with non-zero coefficients.
coeffs (tuple, list, numpy.ndarray, galois.FieldArray, optional) – The corresponding non-zero polynomial coefficients with type
galois.FieldArray
. Alternatively, an iterabletuple
,list
, ornumpy.ndarray
may be provided and the Galois field domain is taken from thefield
keyword argument. The default isNone
which corresponds to all ones.field (galois.FieldClass, optional) –
The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.
None
(default): If the coefficients are agalois.FieldArray
, they won’t be modified. If the coefficients are not explicitly in a Galois field, they are assumed to be from \(\mathrm{GF}(2)\) and are converted usinggalois.GF2(coeffs)
.galois.FieldClass
: The coefficients are explicitly converted to this Galois fieldfield(coeffs)
.
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) by specifying the degrees with non-zero coefficients.
In [1]: galois.Poly.Degrees([3,1,0]) Out[1]: Poly(x^3 + x + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) by specifying the degrees with non-zero coefficients.
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Degrees([3,1,0], coeffs=[251,73,185], field=GF) Out[3]: Poly(251x^3 + 73x + 185, GF(2^8))
- classmethod Identity(field=<class 'numpy.ndarray over GF(2)'>)
Constructs the polynomial \(f(x) = x\) over \(\mathrm{GF}(p^m)\).
- Parameters
field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(f(x) = x\).
- Return type
Examples
Construct the identity polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.Identity() Out[1]: Poly(x, GF(2))
Construct the identity polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Identity(field=GF) Out[3]: Poly(x, GF(2^8))
- classmethod Integer(integer, field=<class 'numpy.ndarray over GF(2)'>)
Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its integer representation.
- Parameters
integer (int) – The integer representation of the polynomial \(f(x)\).
field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Notes
The integer value \(i\) represents the polynomial \(f(x) = a_d x^{d} + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) over the field \(\mathrm{GF}(p^m)\) if \(i = a_{d}(p^m)^{d} + a_{d-1}(p^m)^{d-1} + \dots + a_1(p^m) + a_0\) using integer arithmetic, not finite field arithmetic.
Said differently, if the polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) are considered as the “digits” of a radix-\(p^m\) value, the polynomial’s integer representation is the decimal value (radix-\(10\)).
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from its integer representation.
In [1]: galois.Poly.Integer(5) Out[1]: Poly(x^2 + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) from its integer representation.
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Integer(13*256**3 + 117, field=GF) Out[3]: Poly(13x^3 + 117, GF(2^8))
- classmethod One(field=<class 'numpy.ndarray over GF(2)'>)
Constructs the polynomial \(f(x) = 1\) over \(\mathrm{GF}(p^m)\).
- Parameters
field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(f(x) = 1\).
- Return type
Examples
Construct the one polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.One() Out[1]: Poly(1, GF(2))
Construct the one polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.One(field=GF) Out[3]: Poly(1, GF(2^8))
- classmethod Random(degree, seed=None, field=<class 'numpy.ndarray over GF(2)'>)
Constructs a random polynomial over \(\mathrm{GF}(p^m)\) with degree \(d\).
- Parameters
degree (int) – The degree of the polynomial.
seed (int, numpy.random.Generator, optional) – Non-negative integer used to initialize the PRNG. The default is
None
which means that unpredictable entropy will be pulled from the OS to be used as the seed. Anumpy.random.Generator
can also be passed. If so, it is used directly whendtype != np.object_
. Its state is used to seedrandom.seed()
, otherwise.field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Examples
Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.Random(5) Out[1]: Poly(x^5 + x^2, GF(2))
Construct a random degree-\(5\) polynomial over \(\mathrm{GF}(2^8)\) with a given seed. This produces repeatable results.
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Random(5, seed=123456789, field=GF) Out[3]: Poly(60x^5 + 241x^4 + 166x^3 + 230x^2 + 156x + 46, GF(2^8)) In [4]: galois.Poly.Random(5, seed=123456789, field=GF) Out[4]: Poly(60x^5 + 241x^4 + 166x^3 + 230x^2 + 156x + 46, GF(2^8))
Construct multiple polynomials with one global seed.
In [5]: rng = np.random.default_rng(123456789) In [6]: galois.Poly.Random(5, seed=rng, field=GF) Out[6]: Poly(60x^5 + 241x^4 + 166x^3 + 230x^2 + 156x + 46, GF(2^8)) In [7]: galois.Poly.Random(5, seed=rng, field=GF) Out[7]: Poly(205x^5 + 206x^4 + 211x^3 + 149x^2 + 173x + 126, GF(2^8))
- classmethod Roots(roots, multiplicities=None, field=None)
Constructs a monic polynomial over \(\mathrm{GF}(p^m)\) from its roots.
- Parameters
roots (tuple, list, numpy.ndarray, galois.FieldArray) – The roots of the desired polynomial with type
galois.FieldArray
. Alternatively, an iterabletuple
,list
, ornumpy.ndarray
may be provided and the Galois field domain is taken from thefield
keyword argument.multiplicities (tuple, list, numpy.ndarray, optional) – The corresponding root multiplicities. The default is
None
which corresponds to all ones, i.e.[1,]*len(roots)
.field (galois.FieldClass, optional) –
The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over.
None
(default): If the roots are agalois.FieldArray
, they won’t be modified. If the roots are not explicitly in a Galois field, they are assumed to be from \(\mathrm{GF}(2)\) and are converted usinggalois.GF2(roots)
.galois.FieldClass
: The roots are explicitly converted to this Galois fieldfield(roots)
.
- Returns
The polynomial \(f(x)\).
- Return type
Notes
The polynomial \(f(x)\) with \(k\) roots \(\{r_1, r_2, \dots, r_k\}\) with multiplicities \(\{m_1, m_2, \dots, m_k\}\) is
\[ \begin{align}\begin{aligned}f(x) &= (x - r_1)^{m_1} (x - r_2)^{m_2} \dots (x - r_k)^{m_k}\\f(x) &= a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\end{aligned}\end{align} \]with degree \(d = \sum_{i=1}^{k} m_i\).
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from a list of its roots.
In [1]: roots = [0, 0, 1] In [2]: p = galois.Poly.Roots(roots); p Out[2]: Poly(x^3 + x^2, GF(2)) # Evaluate the polynomial at its roots In [3]: p(roots) Out[3]: GF([0, 0, 0], order=2)
Construct a polynomial over \(\mathrm{GF}(2^8)\) from a list of its roots with specific multiplicities.
In [4]: GF = galois.GF(2**8) In [5]: roots = [121, 198, 225] In [6]: multiplicities = [1, 2, 1] In [7]: p = galois.Poly.Roots(roots, multiplicities=multiplicities, field=GF); p Out[7]: Poly(x^4 + 152x^3 + 85x^2 + 223x + 147, GF(2^8)) # Evaluate the polynomial at its roots In [8]: p(roots) Out[8]: GF([0, 0, 0], order=2^8)
- classmethod String(string, field=<class 'numpy.ndarray over GF(2)'>)
Constructs a polynomial over \(\mathrm{GF}(p^m)\) from its string representation.
- Parameters
string (str) – The string representation of the polynomial \(f(x)\).
field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.
- Returns
The polynomial \(f(x)\).
- Return type
Notes
The string parsing rules include:
Either
^
or**
may be used for indicating the polynomial degrees. For example,"13x^3 + 117"
or"13x**3 + 117"
.Multiplication operators
*
may be used between coefficients and the polynomial indeterminatex
, but are not required. For example,"13x^3 + 117"
or"13*x^3 + 117"
.Polynomial coefficients of 1 may be specified or omitted. For example,
"x^3 + 117"
or"1*x^3 + 117"
.The polynomial indeterminate can be any single character, but must be consistent. For example,
"13x^3 + 117"
or"13y^3 + 117"
.Spaces are not required between terms. For example,
"13x^3 + 117"
or"13x^3+117"
.Any combination of the above rules is acceptable.
Examples
Construct a polynomial over \(\mathrm{GF}(2)\) from its string representation.
In [1]: galois.Poly.String("x^2 + 1") Out[1]: Poly(x^2 + 1, GF(2))
Construct a polynomial over \(\mathrm{GF}(2^8)\) from its string representation.
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.String("13x^3 + 117", field=GF) Out[3]: Poly(13x^3 + 117, GF(2^8))
- classmethod Zero(field=<class 'numpy.ndarray over GF(2)'>)
Constructs the polynomial \(f(x) = 0\) over \(\mathrm{GF}(p^m)\).
- Parameters
field (galois.FieldClass, optional) – The Galois field \(\mathrm{GF}(p^m)\) the polynomial is over. The default is
galois.GF2
.- Returns
The polynomial \(f(x) = 0\).
- Return type
Examples
Construct the zero polynomial over \(\mathrm{GF}(2)\).
In [1]: galois.Poly.Zero() Out[1]: Poly(0, GF(2))
Construct the zero polynomial over \(\mathrm{GF}(2^8)\).
In [2]: GF = galois.GF(2**8) In [3]: galois.Poly.Zero(field=GF) Out[3]: Poly(0, GF(2^8))
- __add__(other)
Adds two polynomials.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
The polynomial \(c(x) = a(x) + b(x)\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x + 1, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + x^2, GF(2)) In [3]: a + b Out[3]: Poly(x^5 + x^3 + x^2 + x + 1, GF(2))
- __divmod__(other)
Divides two polynomials and returns the quotient and remainder.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
galois.Poly – The quotient polynomial \(q(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
galois.Poly – The remainder polynomial \(r(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^3 + x, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + x, GF(2)) In [3]: q, r = divmod(a, b) In [4]: q, r Out[4]: (Poly(x^2, GF(2)), Poly(x, GF(2))) In [5]: b*q + r Out[5]: Poly(x^5 + x^3 + x, GF(2))
- __floordiv__(other)
Divides two polynomials and returns the quotient.
True division and floor division are equivalent.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
The quotient polynomial \(q(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^3 + x^2, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + x^2, GF(2)) In [3]: divmod(a, b) Out[3]: (Poly(x^2 + x, GF(2)), Poly(x^2, GF(2))) In [4]: a // b Out[4]: Poly(x^2 + x, GF(2))
- __init__()
- __mod__(other)
Divides two polynomials and returns the remainder.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
The remainder polynomial \(r(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + x, GF(2)) In [3]: divmod(a, b) Out[3]: (Poly(x^2 + 1, GF(2)), Poly(x, GF(2))) In [4]: a % b Out[4]: Poly(x, GF(2))
- __mul__(other)
Multiplies two polynomials.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
The polynomial \(c(x) = a(x) b(x)\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^2 + 1, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + x^2, GF(2)) In [3]: a * b Out[3]: Poly(x^8 + x^7 + x^5 + x^4 + x^3 + x^2, GF(2))
- __pow__(other)
Exponentiates the polynomial to an integer power.
- Parameters
other (int) – The non-negative integer exponent.
- Returns
The polynomial \(a(x)**b\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^4, GF(2)) In [2]: a**3 Out[2]: Poly(x^15 + x^14 + x^13 + x^12, GF(2)) In [3]: a * a * a Out[3]: Poly(x^15 + x^14 + x^13 + x^12, GF(2))
- __sub__(other)
Subtracts two polynomials.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
The polynomial \(c(x) = a(x) - b(x)\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^4, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + x^2 + x, GF(2)) In [3]: a - b Out[3]: Poly(x^5 + x^4 + x^3 + x^2 + x, GF(2))
- __truediv__(other)
Divides two polynomials and returns the quotient.
True division and floor division are equivalent.
- Parameters
other (galois.Poly) – The polynomial \(b(x)\).
- Returns
The quotient polynomial \(q(x)\) such that \(a(x) = b(x)q(x) + r(x)\).
- Return type
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^2 + x, GF(2)) In [2]: b = galois.Poly.Random(3); b Out[2]: Poly(x^3 + 1, GF(2)) In [3]: divmod(a, b) Out[3]: (Poly(x^2, GF(2)), Poly(x, GF(2))) In [4]: a / b Out[4]: Poly(x^2, GF(2))
- derivative(k=1)
Computes the \(k\)-th formal derivative \(\frac{d^k}{dx^k} f(x)\) of the polynomial \(f(x)\).
- 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 \(f(x)\).
- Return type
Notes
For the polynomial
\[f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\]the first formal derivative is defined as
\[f'(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. For example, \(3 \cdot a = a + a + a\).
References
Examples
Compute the derivatives of a polynomial over \(\mathrm{GF}(2)\).
In [1]: p = galois.Poly.Random(7); p Out[1]: Poly(x^7 + x^5 + x^4 + x^3 + x, GF(2)) In [2]: p.derivative() Out[2]: Poly(x^6 + x^4 + x^2 + 1, GF(2)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [3]: p.derivative(2) Out[3]: Poly(0, GF(2))
Compute the derivatives of a polynomial over \(\mathrm{GF}(7)\).
In [4]: GF = galois.GF(7) In [5]: p = galois.Poly.Random(11, field=GF); p Out[5]: Poly(3x^11 + 2x^10 + 2x^9 + 4x^8 + 5x^7 + 2x^6 + 5x^5 + 5x^4 + 2x^3 + 2x^2 + x + 5, GF(7)) In [6]: p.derivative() Out[6]: Poly(5x^10 + 6x^9 + 4x^8 + 4x^7 + 5x^5 + 4x^4 + 6x^3 + 6x^2 + 4x + 1, GF(7)) In [7]: p.derivative(2) Out[7]: Poly(x^9 + 5x^8 + 4x^7 + 4x^4 + 2x^3 + 4x^2 + 5x + 4, GF(7)) In [8]: p.derivative(3) Out[8]: Poly(2x^8 + 5x^7 + 2x^3 + 6x^2 + x + 5, GF(7)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [9]: p.derivative(7) Out[9]: Poly(0, GF(7))
Compute the derivatives of a polynomial over \(\mathrm{GF}(2^8)\).
In [10]: GF = galois.GF(2**8) In [11]: p = galois.Poly.Random(7, field=GF); p Out[11]: Poly(96x^7 + 154x^6 + 218x^5 + x^4 + 103x^3 + 89x^2 + 189x + 44, GF(2^8)) In [12]: p.derivative() Out[12]: Poly(96x^6 + 218x^4 + 103x^2 + 189, GF(2^8)) # k derivatives of a polynomial where k is the Galois field's characteristic will always result in 0 In [13]: p.derivative(2) Out[13]: Poly(0, GF(2^8))
- reverse()
Returns the \(d\)-th reversal \(x^d f(\frac{1}{x})\) of the polynomial \(f(x)\) with degree \(d\).
- Returns
The \(n\)-th reversal \(x^n f(\frac{1}{x})\).
- Return type
Notes
For a polynomial \(f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) with degree \(d\), the \(d\)-th reversal is equivalent to reversing the coefficients.
\[\textrm{rev}_d f(x) = x^d f(x^{-1}) = a_0 x^d + a_{1} x^{d-1} + \dots + a_{d-1} x + a_d\]Examples
In [1]: GF = galois.GF(7) In [2]: f = galois.Poly([5, 0, 3, 4], field=GF); f Out[2]: Poly(5x^3 + 3x + 4, GF(7)) In [3]: f.reverse() Out[3]: Poly(4x^3 + 3x^2 + 5, GF(7))
- roots(multiplicity=False)
Calculates the roots \(r\) of the polynomial \(f(x)\), such that \(f(r) = 0\).
- Parameters
multiplicity (bool, optional) – Optionally return the multiplicity of each root. The default is
False
which only returns the unique roots.- Returns
galois.FieldArray – Galois field array of roots of \(f(x)\). The roots are ordered in increasing order.
np.ndarray – The multiplicity of each root, only returned if
multiplicity=True
.
Notes
This implementation uses Chien’s search to find the roots \(\{r_1, r_2, \dots, r_k\}\) of the degree-\(d\) polynomial
\[f(x) = a_{d}x^{d} + a_{d-1}x^{d-1} + \dots + a_1x + a_0,\]where \(k \le d\). Then, \(f(x)\) can be factored as
\[f(x) = (x - r_1)^{m_1} (x - r_2)^{m_2} \dots (x - r_k)^{m_k},\]where \(m_i\) is the multiplicity of root \(r_i\) and \(d = \sum_{i=1}^{k} m_i\).
The Galois field elements can be represented as \(\mathrm{GF}(p^m) = \{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\}\), where \(\alpha\) is a primitive element of \(\mathrm{GF}(p^m)\).
\(0\) is a root of \(f(x)\) if \(a_0 = 0\). \(1\) is a root of \(f(x)\) if \(\sum_{j=0}^{d} a_j = 0\). The remaining elements of \(\mathrm{GF}(p^m)\) are powers of \(\alpha\). The following equations calculate \(f(\alpha^i)\), where \(\alpha^i\) is a root of \(f(x)\) if \(f(\alpha^i) = 0\).
\[ \begin{align}\begin{aligned}f(\alpha^i) &= a_{d}(\alpha^i)^{d} + a_{d-1}(\alpha^i)^{d-1} + \dots + a_1(\alpha^i) + a_0\\f(\alpha^i) &\overset{\Delta}{=} \lambda_{i,d} + \lambda_{i,d-1} + \dots + \lambda_{i,1} + \lambda_{i,0}\\f(\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}f(\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\\f(\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\\f(\alpha^{i+1}) &= \lambda_{i,d}\alpha^d + \lambda_{i,d-1}\alpha^{d-1} + \dots + \lambda_{i,1}\alpha + \lambda_{i,0}\\f(\alpha^{i+1}) &= \sum_{j=0}^{d} \lambda_{i,j}\alpha^j\end{aligned}\end{align} \]References
Examples
Find the roots of a polynomial over \(\mathrm{GF}(2)\).
In [1]: p = galois.Poly.Roots([0,]*7 + [1,]*13); p Out[1]: Poly(x^20 + x^19 + x^16 + x^15 + x^12 + x^11 + x^8 + x^7, GF(2)) In [2]: p.roots() Out[2]: GF([0, 1], order=2) In [3]: p.roots(multiplicity=True) Out[3]: (GF([0, 1], order=2), array([ 7, 13]))
Find the roots of a polynomial over \(\mathrm{GF}(2^8)\).
In [4]: GF = galois.GF(2**8) In [5]: p = galois.Poly.Roots([18,]*7 + [155,]*13 + [227,]*9, field=GF); p Out[5]: 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 [6]: p.roots() Out[6]: GF([ 18, 155, 227], order=2^8) In [7]: p.roots(multiplicity=True) Out[7]: (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
degrees
are paired withcoeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF); p Out[2]: Poly(3x^3 + 5x + 2, GF(7)) In [3]: p.coeffs Out[3]: 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 [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF); p Out[2]: Poly(3x^3 + 5x + 2, GF(7)) In [3]: p.degree Out[3]: 3
- Type
- property degrees
An array of the polynomial degrees in degree-descending order. The entries of
degrees
are paired withcoeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF); p Out[2]: Poly(3x^3 + 5x + 2, GF(7)) In [3]: p.degrees Out[3]: array([3, 2, 1, 0])
- Type
- property field
The Galois field array class to which the coefficients belong.
Examples
In [1]: a = galois.Poly.Random(5); a Out[1]: Poly(x^5 + x^3, GF(2)) In [2]: a.field Out[2]: <class 'numpy.ndarray over GF(2)'>
In [3]: GF = galois.GF(2**8) In [4]: b = galois.Poly.Random(5, field=GF); b Out[4]: Poly(205x^5 + 59x^4 + 98x^3 + 197x^2 + 178x + 137, GF(2^8)) In [5]: b.field Out[5]: <class 'numpy.ndarray over GF(2^8)'>
- Type
- property integer
The integer representation of the polynomial. For the polynomial \(f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0\) over the field \(\mathrm{GF}(p^m)\), the integer representation is \(i = a_d (p^m)^{d} + a_{d-1} (p^m)^{d-1} + \dots + a_1 (p^m) + a_0\) using integer arithmetic, not finite field arithmetic.
Said differently, if the polynomial coefficients \(\{a_d, a_{d-1}, \dots, a_1, a_0\}\) are considered as the “digits” of a radix-\(p^m\) value, the polynomial’s integer representation is the decimal value (radix-\(10\)).
Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF); p Out[2]: Poly(3x^3 + 5x + 2, GF(7)) In [3]: p.integer Out[3]: 1066 In [4]: p.integer == 3*7**3 + 5*7**1 + 2*7**0 Out[4]: True
- Type
- property nonzero_coeffs
The non-zero coefficients of the polynomial in degree-descending order. The entries of
nonzero_degrees
are paired withnonzero_coeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF); p Out[2]: Poly(3x^3 + 5x + 2, GF(7)) In [3]: p.nonzero_coeffs Out[3]: 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
nonzero_degrees
are paired withnonzero_coeffs
.Examples
In [1]: GF = galois.GF(7) In [2]: p = galois.Poly([3, 0, 5, 2], field=GF); p Out[2]: Poly(3x^3 + 5x + 2, GF(7)) In [3]: p.nonzero_degrees Out[3]: array([3, 1, 0])
- Type