Polynomial Arithmetic

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

In [1]: GF = galois.GF(7)

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

In [3]: g = galois.Poly([2, 1, 3], field=GF); g
Out[3]: 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

Add two polynomials.

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

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

In [6]: f + g
Out[6]: 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 [7]: f + GF(3)
Out[7]: Poly(x^3 + 4x + 6, GF(7))

In [8]: GF(3) + f
Out[8]: Poly(x^3 + 4x + 6, GF(7))
Additive inverse: -f
In [9]: f
Out[9]: Poly(x^3 + 4x + 3, GF(7))

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

Any polynomial added to its additive inverse results in zero.

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

In [12]: f + -f
Out[12]: Poly(0, GF(7))
Subtraction: f - g

Subtract one polynomial from another.

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

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

In [15]: f - g
Out[15]: 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 [16]: f - GF(3)
Out[16]: Poly(x^3 + 4x, GF(7))

In [17]: GF(3) - f
Out[17]: Poly(6x^3 + 3x, GF(7))
Multiplication: f * g

Multiply two polynomials.

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

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

In [20]: f * g
Out[20]: 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 [21]: f * GF(3)
Out[21]: Poly(3x^3 + 5x + 2, GF(7))

In [22]: GF(3) * f
Out[22]: 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 [23]: f * 4
Out[23]: Poly(4x^3 + 2x + 5, GF(7))

In [24]: f + f + f + f
Out[24]: 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 [25]: p = GF.characteristic; p
Out[25]: 7

In [26]: f * p
Out[26]: 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 [27]: f
Out[27]: Poly(x^3 + 4x + 3, GF(7))

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

In [29]: f // g
Out[29]: 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 [30]: f // GF(3)
Out[30]: Poly(5x^3 + 6x + 1, GF(7))

In [31]: GF(3) // g
Out[31]: Poly(0, GF(7))
Remainder: f % g

Divide one polynomial by another and keep the remainder.

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

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

In [34]: f % g
Out[34]: 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 [35]: f % GF(3)
Out[35]: Poly(0, GF(7))

In [36]: GF(3) % g
Out[36]: Poly(3, GF(7))
Divmod: divmod(f, g)

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

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

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

In [39]: divmod(f, g)
Out[39]: (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 [40]: divmod(f, GF(3))
Out[40]: (Poly(5x^3 + 6x + 1, GF(7)), Poly(0, GF(7)))

In [41]: divmod(GF(3), g)
Out[41]: (Poly(0, GF(7)), Poly(3, GF(7)))
Exponentiation: f ** 3

Exponentiate a polynomial to a non-negative exponent.

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

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

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

In [45]: f * f * f
Out[45]: 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 [46]: f
Out[46]: Poly(x^3 + 4x + 3, GF(7))

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

# Efficiently computes (f ** 123456789) % g
In [48]: pow(f, 123456789, g)
Out[48]: 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 [49]: f
Out[49]: Poly(x^3 + 4x + 3, GF(7))

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

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

Or they can be evaluated at arrays element-wise.

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

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

# Evaluate f(x) element-wise at a 2-D array
In [55]: f(X)
Out[55]: 
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 [56]: f
Out[56]: Poly(x^3 + 4x + 3, GF(7))

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

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

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

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

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

In [61]: f(g)
Out[61]: 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 [62]: f
Out[62]: Poly(x^3 + 4x + 3, GF(7))

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

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

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

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

See gcd() for more details.

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

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

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

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

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

See egcd() for more details.

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

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

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

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


Last update: Nov 04, 2022