# Polynomial Arithmetic¶

In the sections below, the finite field $$\mathrm{GF}(7)$$ and polynomials $$f(x)$$ and $$g(x)$$ are used.

In : GF = galois.GF(7)

In : f = galois.Poly([1, 0, 4, 3], field=GF); f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g = galois.Poly([2, 1, 3], field=GF); g
Out: Poly(2x^2 + x + 3, GF(7))


## Standard arithmetic¶

After creating a polynomial over a finite field, nearly any polynomial arithmetic operation can be performed using Python operators. Expand any section for more details.

Addition: f + g

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : f + g
Out: Poly(x^3 + 2x^2 + 5x + 6, GF(7))


Add a polynomial and a finite field scalar. The scalar is treated as a 0-degree polynomial.

In : f + GF(3)
Out: Poly(x^3 + 4x + 6, GF(7))

In : GF(3) + f
Out: Poly(x^3 + 4x + 6, GF(7))

Additive inverse: -f
In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : -f
Out: Poly(6x^3 + 3x + 4, GF(7))


In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : f + -f
Out: Poly(0, GF(7))

Subtraction: f - g

Subtract one polynomial from another.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : f - g
Out: Poly(x^3 + 5x^2 + 3x, GF(7))


Subtract finite field scalar from a polynomial, or vice versa. The scalar is treated as a 0-degree polynomial.

In : f - GF(3)
Out: Poly(x^3 + 4x, GF(7))

In : GF(3) - f
Out: Poly(6x^3 + 3x, GF(7))

Multiplication: f * g

Multiply two polynomials.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : f * g
Out: Poly(2x^5 + x^4 + 4x^3 + 3x^2 + x + 2, GF(7))


Multiply a polynomial and a finite field scalar. The scalar is treated as a 0-degree polynomial.

In : f * GF(3)
Out: Poly(3x^3 + 5x + 2, GF(7))

In : GF(3) * f
Out: Poly(3x^3 + 5x + 2, GF(7))

Scalar multiplication: f * 3

Scalar multiplication is essentially repeated addition. It is the “multiplication” of finite field elements and integers. The integer value indicates how many additions of the field element to sum.

In : f * 4
Out: Poly(4x^3 + 2x + 5, GF(7))

In : f + f + f + f
Out: Poly(4x^3 + 2x + 5, GF(7))


In finite fields $$\mathrm{GF}(p^m)$$, the characteristic $$p$$ is the smallest value when multiplied by any non-zero field element that always results in 0.

In : p = GF.characteristic; p
Out: 7

In : f * p
Out: Poly(0, GF(7))

Division: f // g

Divide one polynomial by another. Floor division is supported. True division is not supported since fractional polynomials are not currently supported.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : f // g
Out: Poly(4x + 5, GF(7))


Divide a polynomial by a finite field scalar, or vice versa. The scalar is treated as a 0-degree polynomial.

In : f // GF(3)
Out: Poly(5x^3 + 6x + 1, GF(7))

In : GF(3) // g
Out: Poly(0, GF(7))

Remainder: f % g

Divide one polynomial by another and keep the remainder.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : f % g
Out: Poly(x + 2, GF(7))


Divide a polynomial by a finite field scalar, or vice versa, and keep the remainder. The scalar is treated as a 0-degree polynomial.

In : f % GF(3)
Out: Poly(0, GF(7))

In : GF(3) % g
Out: Poly(3, GF(7))

Divmod: divmod(f, g)

Divide one polynomial by another and return the quotient and remainder.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : divmod(f, g)
Out: (Poly(4x + 5, GF(7)), Poly(x + 2, GF(7)))


Divide a polynomial by a finite field scalar, or vice versa, and keep the remainder. The scalar is treated as a 0-degree polynomial.

In : divmod(f, GF(3))
Out: (Poly(5x^3 + 6x + 1, GF(7)), Poly(0, GF(7)))

In : divmod(GF(3), g)
Out: (Poly(0, GF(7)), Poly(3, GF(7)))

Exponentiation: f ** 3

Exponentiate a polynomial to a non-negative exponent.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : f ** 3
Out: Poly(x^9 + 5x^7 + 2x^6 + 6x^5 + 2x^4 + 4x^2 + 3x + 6, GF(7))

In : pow(f, 3)
Out: Poly(x^9 + 5x^7 + 2x^6 + 6x^5 + 2x^4 + 4x^2 + 3x + 6, GF(7))

In : f * f * f
Out: Poly(x^9 + 5x^7 + 2x^6 + 6x^5 + 2x^4 + 4x^2 + 3x + 6, GF(7))

Modular exponentiation: pow(f, 123456789, g)

Exponentiate a polynomial to a non-negative exponent and reduce modulo another polynomial. This performs efficient modular exponentiation.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

# Efficiently computes (f ** 123456789) % g
In : pow(f, 123456789, g)
Out: Poly(x + 2, GF(7))


## Evaluation¶

Polynomial objects may also be evaluated at scalars, arrays, or square matrices. Expand any section for more details.

Evaluation (element-wise): f(x) or f(X)

Polynomials are evaluated by invoking __call__(). They can be evaluated at scalars.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : f(5)
Out: GF(1, order=7)

# The equivalent field calculation
In : GF(5)**3 + 4*GF(5) + GF(3)
Out: GF(1, order=7)


Or they can be evaluated at arrays element-wise.

In : x = GF([5, 6, 3, 4])

# Evaluate f(x) element-wise at a 1-D array
In : f(x)
Out: GF([1, 5, 0, 6], order=7)

In : X = GF([[5, 6], [3, 4]])

# Evaluate f(x) element-wise at a 2-D array
In : f(X)
Out:
GF([[1, 5],
[0, 6]], order=7)

Evaluation (square matrix): f(X, elementwise=False)

Polynomials can also be evaluated at square matrices. Note, this is different than element-wise array evaluation. Here, the square matrix indeterminate is exponentiated using matrix multiplication. So $$f(x) = x^3$$ evaluated at the square matrix X equals X @ X @ X.

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : f(X, elementwise=False)
Out:
GF([[1, 1],
[4, 2]], order=7)

# The equivalent matrix operation
In : np.linalg.matrix_power(X, 3) + 4*X + GF(3)*GF.Identity(X.shape)
Out:
GF([[1, 1],
[4, 2]], order=7)

Composition: f(g)

Polynomial composition $$f(g(x))$$ is easily performed using an overload to __call__().

In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : f(g)
Out: Poly(x^6 + 5x^5 + 2x^3 + x^2 + 3x, GF(7))


## Special arithmetic¶

Polynomial objects also work on several special arithmetic operations. Expand any section for more details.

Greatest common denominator: galois.gcd(f, g)
In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : d = galois.gcd(f, g); d
Out: Poly(1, GF(7))

In : f % d
Out: Poly(0, GF(7))

In : g % d
Out: Poly(0, GF(7))


See gcd() for more details.

Extended greatest common denominator: galois.egcd(f, g)
In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : g
Out: Poly(2x^2 + x + 3, GF(7))

In : d, s, t = galois.egcd(f, g)

In : d, s, t
Out: (Poly(1, GF(7)), Poly(6x + 5, GF(7)), Poly(4x^2 + 6x, GF(7)))

In : f*s + g*t == d
Out: True


See egcd() for more details.

Factor into irreducible polynomials: galois.factors(f) == f.factors()
In : f
Out: Poly(x^3 + 4x + 3, GF(7))

In : galois.factors(f)
Out: ([Poly(x + 4, GF(7)), Poly(x^2 + 3x + 6, GF(7))], [1, 1])

In : f.factors()
Out: ([Poly(x + 4, GF(7)), Poly(x^2 + 3x + 6, GF(7))], [1, 1])


See factors() or galois.Poly.factors() for more details.