Chapter 14: Calculations

Mathematica has a package "Algebra" with a function PolynomialExtendedGCD which calculates (f, g) for two polynomials f and g, as well as polynomials s and t such that

(f, g) = sf + tg .

First load the package:

<< Algebra`PolynomialExtendedGCD`

If we take   f = (x^3)+(x^2)+x+1 , g = (x^4)+(x^3)+x+1  ∈ ℚ[x] , we obtain

PolynomialExtendedGCD[x^3 + x^2 + x + 1,  
      x^4 + x^3 + x + 1]

Thus

( (x^3)+(x^2)+x+1, (x^4)+(x^3)+x+1 ) = x+1

and

x+1  =  ((1/2) - (x/2) - ((x^2)/2))( (x^3)+(x^2)+x+1 ) + ((1/2) + (x/2))( (x^4)+(x^3)+x+1 )

The function can also calculate in (Subscript[𝔽, p]) . Here is example 14.1:

PolynomialExtendedGCD[x^4  +  x^3  +  x^2  +  3  x  +  2,  
      x^5  -  x^4  -  x^3  +  2  x^2  -  x  -  2,  
      Modulus -> 11]

Mathematica is very useful for a calculation like example 14.5. We have

f  =  3 + x + 6 (x^2) + 2 (x^3) + 4 (x^4) + 5 (x^5) + (x^6)

To compute (x^7), (x^14), (x^21), (x^28), and (x^35) in term of the basis {1, x, ..., (x^6)} of V, we can use the function  PolynomialMod which reduces a polynomial modulo a natural number n and a
polynomial f.

PolynomialMod[ x^7, {f, 7}]

PolynomialMod[ x^14, {f, 7}]

PolynomialMod[ x^21, {f, 7}]

PolynomialMod[ x^28, {f, 7}]

PolynomialMod[ x^35, {f, 7}]

Then

A  =  
        Transpose[{{1, 0, 0, 0, 0, 0}, {1, 2, 1, 4, 4, 0}, {3, 4, 3, 3, 2, 
              3}, {3, 3, 1, 1, 1, 4}, {3, 0, 5, 5, 2, 0}, {3, 0, 3, 0, 5, 
              5}}];

MatrixForm[A]

To compute the kernel of  A-I we can use the function Nullspace.

NullSpace[A - IdentityMatrix[6],  Modulus -> 7]

Now we set

g  =  3  x  +  6  x^2  +  5  x^3  +  x^4  +  x^5

To check the greatest common divisors (g+a,f) for  a ∈  (Subscript[𝔽, 7]), we use the function PolynomialGCD:

PolynomialGCD[g + 4, f, Modulus -> 7]

PolynomialGCD[g + 5, f, Modulus -> 7]

We check the greatest common divisor of this quartic with its derivative:

PolynomialGCD[2 + 6 x + 2 (x^3) + (x^4), 
      PolynomialMod[D[2 + 6 x + 2 (x^3) + (x^4), x], 7], 
      Modulus -> 7]

Lastly, we verify the factorization.

PolynomialMod[Expand[(5 + 3 x + (x^2))*(3 + x + (x^2))^2], 
      7]

Mathematica does have a built-in function which implements Berlekamp's algorithm:

Factor[
      x^6  +  5  x^5  +  4  x^4  +  2  x^3  +  6  x^2  +  x  +  
        3, Modulus -> 7]

We can use this to check that  (x^5)- 5x + 12 is irreducible modulo 7:

Factor[x^5  -  5  x  +  12,  Modulus -> 7]

You can also factor polynomials over Q:

Factor[
      x^6  +  x^5  +  4  x^4  +  2  x^3  +  6  x^2  +  x  +  
        3]