Ch11-ComputingInFields.mws

Extension fields and multiplicative inverses

İMike May, S.J., maymk@slu.edu, Saint Louis University

>    restart:

Given a field K, and a polynomial f(x), we know that the quotient ring L = K[x]/(f(x)) is a field if and only if f(x) is irreducible.  In that case the ideal (f(x)) is both prime and maximal.

The proof that L is a field is straight forward, using the maximality of the ideal (f(x)).  Unfortunately, the proof that L is a field only gives an existence proof for inverses.  It does not give an efficient means to compute in the extension field L  This worksheet gives an easy way to use Maple to find inverses, and thus to compute in these extension fields.

Case 1: The Gaussian rationals, Q[I]

We start with the Gaussian rationals, a field in which we know how to compute.

The field of Gaussian rationals Q[I], is isomorphic to the quotient ring Q[x]/( x^2+1 ).  This means that the usual ring operations of addition, subtraction, and multiplication are done by working in the polynomial ring Q[x], then taking the remainder after dividing by x^2+1 .  To look at specific cases, let u = a+b*I, v = c+d*I .  Compute u + v, u - v, and u*v.

>    u := a + b* x;  v := c + d*x; f := x^2 + 1;

u := a+b*x

v := c+d*x

f := x^2+1

>    'u' + 'v' = rem(u + v, f, x);
'u' - 'v' = rem(u - v, f, x);
'u' * 'v' = rem(u * v, f, x);

u+v = (b+d)*x+a+c

u-v = (b-d)*x+a-c

u*v = (a*d+b*c)*x+a*c-b*d

Thus:

      u+v = a+c+(b+d)*I

      u-v = a-c+(b-d)*I

      u*v = a*d-b*d+(a*d+b*c)*I .

The harder problem is doing division, with the sticking point being an efficient method of finding multiplicative inverses.  In Q[I], the inverse of u = a+b*I  is (a-b*I)/((a+b*I)*(a-b*I)) = (a-b*I)/(a^2+b^2) .  This rule for inverses is specific to the Gaussian rationals.  We need to find a method that produces multiplicative inverses using only the fact that f = x^2+1  is prime.  Such a method could be generalized to other fields.

Since f  is prime and u  is not in the ideal generated by f , the gcd of   u   and f  is 1.  This means there are polynomials A and B with u*A+f*B = 1 .  In the ring L = Q[x]/( f ),   f = 0 , so the polynomial A will be the multiplicative  inverse of    u   in L  We can recover A with the Maple command gcdex.

>    'u' = u; 'f' = f;
gcdex(u, f,x, 'uinv', 'g'):
u*uinv + f * g;
simplify(u*uinv + f * g);
'u'^(-1) = uinv;

u = a+b*x

f = x^2+1

(a+b*x)*(-b/(b^2+a^2)*x+a/(b^2+a^2))+(x^2+1)*b^2/(b^2+a^2)

1

1/u = -b/(b^2+a^2)*x+a/(b^2+a^2)

This gives the correct inverse for u.

It will be useful to turn the process above into a procedure we can call.

>    invf := proc(u, f, x)
        local uinv, g:
        gcdex(u, f, x, 'uinv', 'g'):
        uinv;
        end;

invf := proc (u, f, x) local uinv, g; gcdex(u,f,x,'uinv','g'); uinv end proc

Once we have multiplicative inverses it is straight forward to do division.

>    'u'/'v' = rem(u*invf(v, f, x), f, x);

u/v = (a*c+b*d)/(d^2+c^2)-(a*d-b*c)/(d^2+c^2)*x

Exercises:

1)  Let u and v be defined as above.  Compute u^4 . and v/u .

2)  Compute (2+3*I)^3/(4+5*I) , and (5+7*I)/((3+4*I)^6) .

Case II, L = Q[x]/(f(x)) for an irreducible polynomial f(x)

 The procedure worked out above is valid whenever   f   is an irreducible polynomial over Q[x].  For a different extension field, you can either  change the definition of    f   , or supply    f    directly to the procedures defined.

The one additional Maple command that may be of use is

     factor(f);

which lets you see if    f   is irreducible.

Exercises:

3)  Let   u = a+b*x, v = c+d*x .  Find   u*v, u^4, 1/v , and u/v    when    f = x^2+3 .

4)  Repeat the previous exercise with   f = x^5+2 .

Case III, Finite fields

Our general theorem has  L = K[x]/(f(x)) being a field, whenever K is a field and f(x) is an irreducible polynomial over K.  So far we have been looking at the case when K is Q, the field of rationals.  Our other favorite starting field is   F[p] = Z / pZ ,   the the prime field of p elements.  The procedure outlined above still works in that case, but the Maple syntax changes a little bit.  To work over the finite prime fields, we capitalize the Maple commands and append "mod p" to them.  Thus we use:

      Rem(u+v, f, x) mod p;                 instead of          rem(u+v, f, x);

      Gcdex(u, f, x, 'uinv', 'g') mod p;    instead of         gcdex(u, f, x, 'uinv', 'g');

and

     Factor(f) mod p;                           instead of          factor(f);

  

Consider the case with    p = 5   and   f = x^3+x+1 .  Verify that    f   is irreducible over   F[p] .

>    p := 5;
f := x^3 + x + 1;
Factor(f) mod p;

p := 5

f := x^3+x+1

x^3+x+1

Evaluate   u+v, u*v, x^3 ,  and u^3  in L = F[p] /( f ).

>    'u' + 'v' = Rem(u+v, f, x) mod p;
'u' * 'v' = Rem(u*v, f, x) mod p;
x^3 = Rem(x^3, f, x) mod p;
'u'^3 = expand(u^3);
'u'^3 = Rem(u^3, f, x) mod p;

u+v = (b+d)*x+a+c

u*v = b*x^2*d+(a*d+b*c)*x+a*c

x^3 = 4*x+4

u^3 = a^3+3*b*x*a^2+3*a*b^2*x^2+b^3*x^3

u^3 = a^3+4*b^3+(3*a^2*b+4*b^3)*x+3*a*b^2*x^2

We want a new inverse procedure for fields of finite charachteristic.

>    invfp := proc(u, f, x, p)
        local uinv, g:
        Gcdex(u, f, x, 'uinv', 'g') mod p:
        uinv;
        end;

invfp := proc (u, f, x, p) local uinv, g; `mod`(Gcdex(u,f,x,'uinv','g'),p); uinv end proc

Using this inverse procedure, we do some computations.

>    x^(-1) = invfp(x,f,x,p);
'u'/'v' = Rem(u*invfp(v,f,x,p), f, x) mod p;
(2 + 3*x)/(1+x) = Rem((2 + 3*x)*invfp(1 + x,f,x,p), f, x) mod p;

1/x = 4*x^2+4

u/v = (a*d^2+a*c^2+4*b*d^2)/(4*d^3+c*d^2+c^3)+(4*a*d*c+b*c^2)/(4*d^3+c*d^2+c^3)*x+(a*d^2+4*b*d*c)/(4*d^3+c*d^2+c^3)*x^2

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

Exercises:

5)  Find a cubic polynomial,  f,  that is irreducible over F[3].  

     Evaluate x^7  and x^(-1)  in   L = F[3] [x]/( f ).

     Find the multiplicative order of x in L.