galois.Poly¶

class galois.Poly(coeffs, field=None, order='desc')[source]¶

Bases: object

Create a polynomial over a Galois field, \(p(x) \in \mathrm{GF}(q)[x]\).

The polynomial \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) has coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) in \(\mathrm{GF}(q)\).

Parameters

coeffs (array_like) – List of polynomial coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) with type galois.GF, numpy.ndarray, list, or tuple. The first element is the highest-degree element if order="desc" or the first element is the 0-th degree element if order="asc".
field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2. If coeffs is a Galois field array, then that field is used and the field argument is ignored.
order (str, optional) – The interpretation of the coefficient degrees, either "desc" (default) or "asc". For "desc", the first element of coeffs is the highest degree coefficient \(x^{N-1}\)) and the last element is the 0-th degree element \(x^0\).

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Create a polynomial over \(\mathrm{GF}(2)[x]\).

In [82]: galois.Poly([1,0,1,1])
Out[82]: Poly(x^3 + x + 1, GF(2))

In [83]: galois.Poly.Degrees([3,1,0])
Out[83]: Poly(x^3 + x + 1, GF(2))

Create a polynomial over \(\mathrm{GF}(7)[x]\).

In [84]: GF7 = galois.GF_factory(7, 1)

In [85]: galois.Poly([4,0,3,0,0,2], field=GF7)
Out[85]: Poly(4x^5 + 3x^3 + 2, GF(7))

In [86]: galois.Poly.Degrees([5,3,0], coeffs=[4,3,2], field=GF7)
Out[86]: Poly(4x^5 + 3x^3 + 2, GF(7))

Polynomial arithmetic using binary operators.

In [87]: a = galois.Poly([1,0,6,3], field=GF7); a
Out[87]: Poly(x^3 + 6x + 3, GF(7))

In [88]: b = galois.Poly([2,0,2], field=GF7); b
Out[88]: Poly(2x^2 + 2, GF(7))

In [89]: a + b
Out[89]: Poly(x^3 + 2x^2 + 6x + 5, GF(7))

In [90]: a - b
Out[90]: Poly(x^3 + 5x^2 + 6x + 1, GF(7))

# Compute the quotient of the polynomial division
In [91]: a / b
Out[91]: Poly(4x, GF(7))

# True division and floor division are equivalent
In [92]: a / b == a // b
Out[92]: True

# Compute the remainder of the polynomial division
In [93]: a % b
Out[93]: Poly(5x + 3, GF(7))

Constructors

`Degrees`(degrees[, coeffs, field])	Create a polynomial over \(\mathrm{GF}(q)[x]\) from its non-zero degrees.
`Identity`([field])	Create the identity polynomial, \(p(x) = x \in \mathrm{GF}(q)[x]\).
`Integer`(integer[, field, order])	Create a polynomial over \(\mathrm{GF}(q)[x]\) from its integer representation.
`One`([field])	Create the one polynomial, \(p(x) = 1 \in \mathrm{GF}(q)[x]\).
`Roots`(roots[, field])	Create a monic polynomial in \(\mathrm{GF}(q)[x]\) from its roots.
`Zero`([field])	Create the zero polynomial, \(p(x) = 0 \in \mathrm{GF}(q)[x]\).

Methods

divmod(dividend, divisor)

Attributes

`coeffs`	The polynomial coefficients as a Galois field array.
`coeffs_asc`	The polynomial coefficients \(\{a_0, a_1, \dots, a_{N-1}\}\) as a Galois field array in degree-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).
`coeffs_desc`	The polynomial coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) as a Galois field array in degree-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).
`degree`	The degree of the polynomial, i.e. the highest degree with non-zero coefficient.
`field`	The finite field to which the coefficients belong.
`integer`	The integer representation of the polynomial.
`order`	The interpretation of the ordering of the polynomial coefficients.

classmethod Degrees(degrees, coeffs=None, field=<class 'galois.gf2.GF2'>)[source]¶

Create a polynomial over \(\mathrm{GF}(q)[x]\) from its non-zero degrees.

Parameters

degrees (list) – The 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).
roots (array_like) – List of roots in \(\mathrm{GF}(q)\) of the desired polynomial.
field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)[x]\) by specifying the degrees with non-zero coefficients.

In [94]: galois.Poly.Degrees([3,1,0])
Out[94]: Poly(x^3 + x + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(7)[x]\) by specifying the degrees with non-zero coefficients.

In [95]: GF7 = galois.GF_factory(7, 1)

In [96]: galois.Poly.Degrees([3,1,0], coeffs=[5,2,1], field=GF7)
Out[96]: Poly(5x^3 + 2x + 1, GF(7))

classmethod Identity(field=<class 'galois.gf2.GF2'>)[source]¶

Create the identity polynomial, \(p(x) = x \in \mathrm{GF}(q)[x]\).

Parameters: field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.
Returns: The polynomial \(p(x)\).
Return type: galois.Poly

Examples

Construct the identity polynomial over \(\mathrm{GF}(2)[x]\).

In [97]: galois.Poly.Identity()
Out[97]: Poly(x, GF(2))

Construct the identity polynomial over \(\mathrm{GF}(7)[x]\).

In [98]: GF7 = galois.GF_factory(7, 1)

In [99]: galois.Poly.Identity(field=GF7)
Out[99]: Poly(x, GF(7))

classmethod Integer(integer, field=<class 'galois.gf2.GF2'>, order='desc')[source]¶

Create a polynomial over \(\mathrm{GF}(q)[x]\) from its integer representation.

The integer value \(d\) represents polynomial \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) over field \(\mathrm{GF}(q)\) if \(d = a_{N-1} q^{N-1} + \dots + a_1 q + a_0\) using integer arithmetic, not field arithmetic.

Parameters

integer (int) – The integer representation of the polynomial \(p(x)\).
field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)[x]\) from its integer representation.

In [100]: galois.Poly.Integer(5)
Out[100]: Poly(x^2 + 1, GF(2))

Construct a polynomial over \(\mathrm{GF}(7)[x]\) from its integer representation.

In [101]: GF7 = galois.GF_factory(7, 1)

In [102]: galois.Poly.Integer(9, field=GF7)
Out[102]: Poly(x + 2, GF(7))

classmethod One(field=<class 'galois.gf2.GF2'>)[source]¶

Create the one polynomial, \(p(x) = 1 \in \mathrm{GF}(q)[x]\).

Parameters: field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.
Returns: The polynomial \(p(x)\).
Return type: galois.Poly

Examples

Construct the one polynomial over \(\mathrm{GF}(2)[x]\).

In [103]: galois.Poly.One()
Out[103]: Poly(1, GF(2))

Construct the one polynomial over \(\mathrm{GF}(7)[x]\).

In [104]: GF7 = galois.GF_factory(7, 1)

In [105]: galois.Poly.One(field=GF7)
Out[105]: Poly(1, GF(7))

classmethod Roots(roots, field=<class 'galois.gf2.GF2'>)[source]¶

Create a monic polynomial in \(\mathrm{GF}(q)[x]\) from its roots.

The polynomial \(p(x)\) with roots \(\{r_0, r_1, \dots, r_{N-1}\}\) is:

\[p(x) = (x - r_0) (x - r_1) \dots (x - r_{N-1})\]

Parameters

roots (array_like) – List of roots in \(\mathrm{GF}(q)\) of the desired polynomial.
field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.

Returns

The polynomial \(p(x)\).

Return type

galois.Poly

Examples

Construct a polynomial over \(\mathrm{GF}(2)[x]\) from a list of its roots.

In [106]: roots = [0,0,1]

In [107]: p = galois.Poly.Roots(roots); p
Out[107]: Poly(x^3 + x^2, GF(2))

In [108]: p(roots)
Out[108]: GF([0, 0, 0], order=2)

Construct a polynomial over \(\mathrm{GF}(7)[x]\) from a list of its roots.

In [109]: GF7 = galois.GF_factory(7, 1)

In [110]: roots = [2,6,1]

In [111]: p = galois.Poly.Roots(roots, field=GF7); p
Out[111]: Poly(x^3 + 5x^2 + 6x + 2, GF(7))

In [112]: p(roots)
Out[112]: GF([0, 0, 0], order=7)

classmethod Zero(field=<class 'galois.gf2.GF2'>)[source]¶

Create the zero polynomial, \(p(x) = 0 \in \mathrm{GF}(q)[x]\).

Parameters: field (galois.GF, optional) – The field \(\mathrm{GF}(q)\) the polynomial is over. The default galois.GF2.
Returns: The polynomial \(p(x)\).
Return type: galois.Poly

Examples

Construct the zero polynomial over \(\mathrm{GF}(2)[x]\).

In [113]: galois.Poly.Zero()
Out[113]: Poly(0, GF(2))

Construct the zero polynomial over \(\mathrm{GF}(7)[x]\).

In [114]: GF7 = galois.GF_factory(7, 1)

In [115]: galois.Poly.Zero(field=GF7)
Out[115]: Poly(0, GF(7))

static divmod(dividend, divisor)[source]¶

property coeffs¶

The polynomial coefficients as a Galois field array. Coefficients are \(\{a_{N-1}, \dots, a_1, a_0\}\) if order="desc" or \(\{a_0, a_1, \dots, a_{N-1}\}\) if order="asc", where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type: galois.GF

property coeffs_asc¶

The polynomial coefficients \(\{a_0, a_1, \dots, a_{N-1}\}\) as a Galois field array in degree-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type: galois.GF

property coeffs_desc¶

The polynomial coefficients \(\{a_{N-1}, \dots, a_1, a_0\}\) as a Galois field array in degree-ascending order, where \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\).

Type: galois.GF

property degree¶

The degree of the polynomial, i.e. the highest degree with non-zero coefficient.

Type: int

property field¶

The finite field to which the coefficients belong.

Type: galois.GF

property integer¶

The integer representation of the polynomial. For \(p(x) = a_{N-1}x^{N-1} + \dots + a_1x + a_0\) with elements in \(\mathrm{GF}(q)\), the integer representation is \(d = a_{N-1} q^{N-1} + \dots + a_1 q + a_0\) (using integer arithmetic, not field arithmetic) where \(q\) is the field order.

Type: int

property order¶

The interpretation of the ordering of the polynomial coefficients. coeffs are in degree-descending order if order="desc" and in degree-ascending order if order="asc".

Type: str