# Chapter 14: Calculations # # Maple has a function gcdex which calculates (f, g) for polynomials f # and g, as well as polynomials s and t such that # # (f, g) = sf + tg . # # If we take # > f = x^3+x^3+x+1,g = x^4+x^3+x+1; # in Q[x], we obtain # > gcdex(x^3 + x^2 + x + 1, x^4 + x^3 + x + 1, x, 's', 't'); 1 + x > s;t; 2 1/2 - 1/2 x - 1/2 x 1/2 + 1/2 x # # 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^3+x+1)+(1/2+x/2)(x^4+x^3+x+1); # # To calculate modulo a prime p, use the function Gcdex . Here is # example 14.1: # > Gcdex(x^4 + x^3 + x^2 + 3*x + 2, x^5 - x^4 - x^3 + 2*x^2 - x - 2, x, > 's', 't') mod 11; 1 + x > s;t; 3 2 4 x + 6 x + 3 x + 8 2 7 x + 8 x + 2 # # Maple is very useful for a calculation like example 14.5. We have # > f := x^6 + 5*x^5 + 4*x^4 + 2*x^3 + 6*x^2 + x + 3; 6 5 4 3 2 f := x + 5 x + 4 x + 2 x + 6 x + x + 3 # # To compute x^7, x^14 , x^21 , x^28 and x^35 in terms of the basis # {1, x, .... , x^6} of V, we can use the function modpol which reduces # a polynomial modulo a prime number p and a polynomial f. # > modpol(x^7, f, x, 7); 4 3 2 4 x + 4 x + x + 2 x + 1 > modpol(x^14, f, x, 7); 5 4 3 2 3 x + 2 x + 3 x + 3 x + 4 x + 3 > modpol(x^21, f, x, 7); 5 4 3 2 4 x + x + x + x + 3 x + 3 > modpol(x^28, f, x, 7); 4 3 2 2 x + 5 x + 5 x + 3 > modpol(x^35, f, x, 7); 5 4 2 5 x + 5 x + 3 x + 3 # # Then we input the linear algebra package, and set up the matrix A: # > with(linalg): Warning, the protected names norm and trace have been redefined and unprotected > A := transpose(array([[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]])); [1 1 3 3 3 3] [ ] [0 2 4 3 0 0] [ ] [0 1 3 1 5 3] A := [ ] [0 4 3 1 5 0] [ ] [0 4 2 1 2 5] [ ] [0 0 3 4 0 5] # # To compute the kernel of A-I we can use the function Nullspace. # > Ident := array(1..6,1..6, identity); Ident := array(identity, 1 .. 6, 1 .. 6, []) > Nullspace(matadd(A, -Ident)) mod 7; {[1, 0, 0, 0, 0, 0], [0, 3, 6, 5, 1, 1]} # # Now we set # > g := 3*x + 6*x^2 + 5*x^3 + x^4 + x^5; 2 3 4 5 g := 3 x + 6 x + 5 x + x + x # # To check the greatest common divisors (g+a, f) for a in F(7), we use # the function Gcd : # > Gcd(g+4, f) mod 7; 2 x + 3 x + 5 > Gcd(g+5, f) mod 7; 4 3 x + 2 x + 6 x + 2 # # We check the greatest common divisor of this quartic with its # derivative: # > Gcd(x^4 + 2*x^3 + 6*x + 2, diff(x^4 + 2*x^3 + 6*x + 2, x)) mod 7; 2 x + x + 3 # # Lastly, we verify the factorization. # > Expand((x^2 + x + 3)^2*(x^2 + 3*x + 5)) mod 7; 6 5 4 3 2 x + 5 x + 4 x + 2 x + 6 x + x + 3 # # Maple 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) mod 7; 2 2 2 (x + x + 3) (x + 3 x + 5) # # We can use this to check that x^5 - 5x + 12 is irreducible modulo 7 # or use the function Irreduc : # > Irreduc(x^5 - 5*x + 12) mod 7; true # # You can also factor polynomials over Q: # > factor(x^6 + x^5 + 4*x^4 + 2*x^3 + 6*x^2 + x + 3); 2 4 3 2 (x + 1) (x + x + 3 x + x + 3)