Skip to content

komm.BinaryPolynomial

Binary polynomial. A binary polynomial is a polynomial whose coefficients are elements in the finite field $\mathbb{F}_2 = \{ 0, 1 \}$.

The default constructor of the class expects the following:

Attributes:

  • value (int) –

    An integer whose binary digits represent the coefficients of the polynomial—the leftmost bit standing for the highest degree term. For example, the binary polynomial $X^4 + X^3 + X$ is represented by the integer 0b11010 = 0o32 = 26.

Examples:

>>> komm.BinaryPolynomial(0b11010)  # X^4 + X^3 + X
BinaryPolynomial(0b11010)

See also the class methods from_coefficients and from_exponents for alternative ways to construct a binary polynomial.

Algebraic structure

The binary polynomials form an Euclidean domain. The following operations are supported: addition (+), subtraction (-), multiplication (*), euclidean division (//), modulo (%), and exponentiation (**).

Examples:

>>> poly1 = komm.BinaryPolynomial(0b10111)  # X^4 + X^2 + X + 1
>>> poly2 = komm.BinaryPolynomial(0b101)  # X^2 + 1
>>> poly1 + poly2  # X^4 + X
BinaryPolynomial(0b10010)
>>> poly1 - poly2  # X^4 + X
BinaryPolynomial(0b10010)
>>> poly1 * poly2  # X^6 + X^3 + X + 1
BinaryPolynomial(0b1001011)
>>> poly1 // poly2  # X^2
BinaryPolynomial(0b100)
>>> poly1 % poly2  # X + 1
BinaryPolynomial(0b11)
>>> poly1 ** 2  # X^8 + X^4 + X^2 + 1
BinaryPolynomial(0b100010101)

from_coefficients classmethod

Constructs a binary polynomial from its coefficients.

Parameters:

  • coefficients (Array1D[int]) –

    The coefficients of the binary polynomial—the $i$-th element of the array standing for the coefficient of $X^i$. For example, [0, 1, 0, 1, 1] represents the binary polynomial $X^4 + X^3 + X$.

Examples:

>>> komm.BinaryPolynomial.from_coefficients([0, 1, 0, 1, 1])  # X^4 + X^3 + X
BinaryPolynomial(0b11010)

from_exponents classmethod

Constructs a binary polynomial from its exponents.

Parameters:

  • exponents (Array1D[int]) –

    The exponents of the nonzero terms of the binary polynomial. For example, [1, 3, 4] represents the binary polynomial $X^4 + X^3 + X$.

Examples:

>>> komm.BinaryPolynomial.from_exponents([1, 3, 4])  # X^4 + X^3 + X
BinaryPolynomial(0b11010)

degree: int property

The degree of the binary polynomial.

Examples:

>>> poly = komm.BinaryPolynomial(0b11010)  # X^4 + X^3 + X
>>> poly.degree
4

coefficients

Returns the coefficients of the binary polynomial.

Parameters:

  • width (int | None) –

    If this parameter is specified, the output will be filled with zeros on the right so that the its length will be the specified value.

Returns:

  • coefficients (Array1D[int]) –

    Coefficients of the binary polynomial. The $i$-th element of the array stands for the coefficient of $X^i$.

Examples:

>>> poly = komm.BinaryPolynomial(0b11010)  # X^4 + X^3 + X
>>> poly.coefficients()
array([0, 1, 0, 1, 1])
>>> poly.coefficients(width=8)
array([0, 1, 0, 1, 1, 0, 0, 0])

exponents

Returns the exponents of the binary polynomial.

Returns:

  • exponents (Array1D[int]) –

    Exponents of the nonzero terms of the binary polynomial. The exponents are returned in ascending order.

Examples:

>>> poly = komm.BinaryPolynomial(0b11010)  # X^4 + X^3 + X
>>> poly.exponents()
array([1, 3, 4])

reciprocal

Returns the reciprocal (reflexion) of the binary polynomial. The reciprocal of a binary polynomial is the polynomial with the coefficients in reversed order, that is, the coefficient of $X^i$ becomes the coefficient of $X^{n-i}$, where $n$ is the degree of the polynomial.

Returns:

  • result (BinaryPolynomial) –

    The binary polynomial with the reversed coefficients.

Examples:

>>> poly = komm.BinaryPolynomial(0b11010)  # X^4 + X^3 + X
>>> poly.reciprocal()  # X^3 + X + 1
BinaryPolynomial(0b1011)

evaluate

Evaluates the binary polynomial at a given point. Uses Horner's method.

Parameters:

  • point (RingElement) –

    The point at which the polynomial is evaluated. It must be an element of a ring in which multiplication by integers is defined.

Returns:

  • result (RingElement) –

    The result of evaluating the binary polynomial at point. It has the same type as point.

Examples:

>>> poly = komm.BinaryPolynomial(0b11010)  # X^4 + X^3 + X
>>> poly.evaluate(komm.Integer(7))  # same as 7**4 + 7**3 + 7
Integer(value=2751)

is_irreducible

Checks whether the binary polynomial is irreducible. A binary polynomial is irreducible if it is not divisible by any other nonconstant binary polynomial of smaller degree.

This method checks the irreducibility using Rabin's irreducibility test.

Returns:

  • result (bool) –

    True, if the binary polynomial is irreducible; False, otherwise.

Examples:

>>> komm.BinaryPolynomial(0b11011).is_irreducible()
False
>>> komm.BinaryPolynomial(0b11111).is_irreducible()
True
>>> komm.BinaryPolynomial(0b10011).is_irreducible()
True

is_primitive

Checks whether the binary polynomial is primitive. A binary polynomial of degree $m$ is primitive if it is irreducible and if the smallest positive integer $n$ such that the polynomial divides $X^n + 1$ is $n = 2^m - 1$.

Returns:

  • result (bool) –

    True, if the binary polynomial is primitive; False, otherwise.

Examples:

>>> komm.BinaryPolynomial(0b11011).is_primitive()
False
>>> komm.BinaryPolynomial(0b11111).is_primitive()
False
>>> komm.BinaryPolynomial(0b10011).is_primitive()
True

xgcd classmethod

Performs the extended Euclidean algorithm on two given binary polynomials.

gcd classmethod

Computes the greatest common divisor (gcd) of the arguments.

lcm classmethod

Computes the least common multiple (lcm) of the arguments.