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

Examples:

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

coefficients

Returns the coefficients of the binary polynomial.

Parameters:

  • width (Optional[int]) –

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

evaluate

Evaluates the 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)

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.