Polynomial Arithmetic¶
Standard arithmetic¶
After creating a polynomial over a finite field, nearly any polynomial arithmetic operation can be performed using Python operators.
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))
Expand any section for more details.
Addition: f + g
Add two polynomials.
In [4]: f + g
Out[4]: 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 [5]: f + GF(3)
Out[5]: Poly(x^3 + 4x + 6, GF(7))
In [6]: GF(3) + f
Out[6]: Poly(x^3 + 4x + 6, GF(7))
Additive inverse: -f
In [7]: -f
Out[7]: Poly(6x^3 + 3x + 4, GF(7))
Any polynomial added to its additive inverse results in zero.
In [8]: f + -f
Out[8]: Poly(0, GF(7))
Subtraction: f - g
Subtract one polynomial from another.
In [9]: f - g
Out[9]: 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 [10]: f - GF(3)
Out[10]: Poly(x^3 + 4x, GF(7))
In [11]: GF(3) - f
Out[11]: Poly(6x^3 + 3x, GF(7))
Multiplication: f * g
Multiply two polynomials.
In [12]: f * g
Out[12]: 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 [13]: f * GF(3)
Out[13]: Poly(3x^3 + 5x + 2, GF(7))
In [14]: GF(3) * f
Out[14]: 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 [15]: f * 4
Out[15]: Poly(4x^3 + 2x + 5, GF(7))
In [16]: f + f + f + f
Out[16]: 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 [17]: p = GF.characteristic; p
Out[17]: 7
In [18]: f * p
Out[18]: 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 [19]: f // g
Out[19]: 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 [20]: f // GF(3)
Out[20]: Poly(5x^3 + 6x + 1, GF(7))
In [21]: GF(3) // g
Out[21]: Poly(0, GF(7))
Remainder: f % g
Divide one polynomial by another and keep the remainder.
In [22]: f % g
Out[22]: 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 [23]: f % GF(3)
Out[23]: Poly(0, GF(7))
In [24]: GF(3) % g
Out[24]: Poly(3, GF(7))
Divmod: divmod(f, g)
Divide one polynomial by another and return the quotient and remainder.
In [25]: divmod(f, g)
Out[25]: (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 [26]: divmod(f, GF(3))
Out[26]: (Poly(5x^3 + 6x + 1, GF(7)), Poly(0, GF(7)))
In [27]: divmod(GF(3), g)
Out[27]: (Poly(0, GF(7)), Poly(3, GF(7)))
Exponentiation: f ** 3
Exponentiate a polynomial to a non-negative exponent.
In [28]: f ** 3
Out[28]: Poly(x^9 + 5x^7 + 2x^6 + 6x^5 + 2x^4 + 4x^2 + 3x + 6, GF(7))
In [29]: pow(f, 3)
Out[29]: Poly(x^9 + 5x^7 + 2x^6 + 6x^5 + 2x^4 + 4x^2 + 3x + 6, GF(7))
In [30]: f * f * f
Out[30]: 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.
# Efficiently computes (f ** 123456789) % g
In [31]: pow(f, 123456789, g)
Out[31]: Poly(x + 2, GF(7))
Special arithmetic¶
Polynomial objects also work on several special arithmetic operations. Below are some examples.
In [32]: GF = galois.GF(31)
In [33]: f = galois.Poly([1, 30, 0, 26, 6], field=GF); f
Out[33]: Poly(x^4 + 30x^3 + 26x + 6, GF(31))
In [34]: g = galois.Poly([4, 17, 3], field=GF); g
Out[34]: Poly(4x^2 + 17x + 3, GF(31))
Compute the polynomial greatest common divisor using gcd() and egcd().
In [35]: galois.gcd(f, g)
Out[35]: Poly(1, GF(31))
In [36]: galois.egcd(f, g)
Out[36]:
(Poly(1, GF(31)),
Poly(14x + 13, GF(31)),
Poly(12x^3 + 19x^2 + 22x + 26, GF(31)))
Factor a polynomial into its irreducible polynomial factors using factors().
In [37]: galois.factors(f)
Out[37]: ([Poly(x^2 + 5, GF(31)), Poly(x^2 + 30x + 26, GF(31))], [1, 1])
Polynomial evaluation¶
Polynomials are evaluated by invoking __call__(). They can be evaluated at scalars.
In [38]: GF = galois.GF(31)
In [39]: f = galois.Poly([1, 0, 0, 15], field=GF); f
Out[39]: Poly(x^3 + 15, GF(31))
In [40]: f(26)
Out[40]: GF(14, order=31)
# The equivalent field calculation
In [41]: GF(26)**3 + GF(15)
Out[41]: GF(14, order=31)
Or they can be evaluated at arrays element-wise.
In [42]: x = GF([26, 13, 24, 4])
# Evaluate f(x) element-wise at a 1-D array
In [43]: f(x)
Out[43]: GF([14, 11, 13, 17], order=31)
In [44]: X = GF([[26, 13], [24, 4]])
# Evaluate f(x) element-wise at a 2-D array
In [45]: f(X)
Out[45]:
GF([[14, 11],
[13, 17]], order=31)
Or they 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 [46]: f
Out[46]: Poly(x^3 + 15, GF(31))
# Evaluate f(x) at the 2-D square matrix
In [47]: f(X, elementwise=False)
Out[47]:
GF([[ 2, 20],
[25, 23]], order=31)
# The equivalent matrix operation
In [48]: np.linalg.matrix_power(X, 3) + GF(15)*GF.Identity(X.shape[0])
Out[48]:
GF([[ 2, 20],
[25, 23]], order=31)