This worksheet gives some MAPLE procedures for performing basic calculations over finite fields. This file includes the command readlib(GF): so all the commands in that package will be available when ffield.mpl is read in. (In Maple v 7, the Maple GF package was revised, rendering this ffield.mpl unusable. In this case, the package had to be rewritten and you should use ffield_v7.mpl instead. Some of the sytax has changed as well. Use ffield0_v7.mws for a Maple worksheet explaining the new sytax.)

The ffield.mpl package contains the following routines (among others):

• cartesian_product(L1,L2) and cartesian_power:=(L,n), which takes the Cartesian product and power (resp.) of lists.
• irreducible(d,p,x), which returns an irreducible monic polynomial of degree d over F_p, p prime.
• irreducibles(d,p,x), which returns all irreducible monic polynomials of degree d over F_p, p prime.
• proportion_primes_poly_irred(f,N), which returns the proportion of primes <N for which f is irreducible mod p.
• lambda0(n,p) (where the number of irreducible polynomials mod p of degree n with (maximum) period p^n-1 is lambda0(n,p)).
• Psi0(n,p) (where the number of irreducible polynomials mod p of degree n is Psi0(n,p)).
• irreducibles_and_period(d,p) returns all irreducible monic polynomials of degree d over F_p, p prime.
• irreducible_and_period(d,p) returns an irred monic polynomial of degree d over F_p, p prime, and it's period.
• galoisfield(p,d), p a prime, which returns a list [gf,f,FF], gf of elements of the field of p^d elements which can be added, multiplied using the commands in the GF package, f the irreducible polynomial generating the field, FF the galois field structure from GF
• gf_intmult(x,y,FF) which multiplies in GF BUT y in FF, x an integer; it computes the product.
• roots_to_poly(f,m) which returns list of solutions to f=0 mod m (where f is f0(x), f0 defined using arrow notation).
• gf_eval_poly(f,x,a,FF) which evaluates f at a in GF field FF; f must have integer coefficients. Also, gf_eval_poly_convert(f,x,a,FF) which evaluates f at a (in GF notation) in GF field FF in ConvertOut form (i.e., a polynomial in eta); f must have integer coefficients. Also, gf_eval_poly_output(f,x,a,FF) which evaluates f at a (in GF notation) in GF field FF in ConvertOut form (i.e., an integer 0..p^d-1).
• gf_eval_poly2(f,x,y,a,b,FF) evaluates a polynomial in 2 variables f at x=a,y=b in GF field G; f must have integer coefficients (a,b in GF notation, i.e., as a polynomial in 10^4 with coefficients in 0..p-1).
• gf_power(a,n,FF) evaluates a^n in GF field FF (where n is any integer, possibly negative or 0).
• order_gf(a,p,d), which returns the order of a in the cyclic group gf^x, where gf is the Galois field of order p^d and char p, and 0 if a=0 otherwise.
• is_primitive_gf(a,p,d), which returns true if a generates the cyclic group gf^x, where gf is the Galois field of order p^d and char p, and false otherwise.
• primitive_gf(p,d), which returns a primitive element of the finite field of order p^d, char p, given by GF. Also, primitive_gf_convert(p,d), which returns a primitive element in ConvertOut form, and primitive_gf_output(p,d), which returns a primitive element in output form.
• primitives_gf(p,d), which returns all primitive elements. Also, primitives_gf_convert(p,d), primitives_gf_output(p,d), which do the obvious thing.
• log_gf(x,b,p,d), which returns log of x to base b in the finite field of order p^d, char p, given by GF, if b is primitive, infty otherwise (x,b must be in GF notation). Also, log_gf_input(x,b,p,d), which returns log of x to base b (x,b are integers from 0 to p^d-1 representing elements of the FF via GF's input).
• matrix_gf(a,p,d), which returns the matrix representation of the element a (in GF notation), with respect to the basis 1,x,...,x^(d-1), where FF is identified with F_p[x]/(f), where f is the irreducible polynomial generating FF.
• roots_to_poly_gf(f,x,p,d), which returns list of solutions to f=0 in Galois field GF(p,d) of char p, where f is f0(x), f0:=x->expression in x, solutions are written in GF notation i.e., as a polynomial in 10^4 with coefficients in 0..p-1. Also, roots_to_poly_gf_output(f,x,p,d), which returns list of solutions to f=0 in output form, and roots_to_poly_gf_convert(f,x,p,d), which returns list of solutions to f=0 in ConvertOut form.
• gf_mult_table(p,d), which returns the multiplication table of the finite field FF in output form.
• gf_add_table(p,d), which returns the addition table of the finite field FF in output form.

In addition, there are some special routines for quadratic extensions and technical routines for manipulating polynomials which are documented in the mpl file.

ffields0.mws,wdj,7-5-99

> restart;

> #read `d:/maplestuff/bin.win/ffield.mpl`;

> read `c:/oldd//mapleV4/bin.win/ffield.mpl`;

We can find an irreducible polynomial of degree 3 over F_5 by using the irreducible command. This first searches over "likely" candidates.

> irreducible(3,5,x);

We can find all irreducible polynomial of degree 3 over F_5 by using the irreducibles command.

> irreducibles(3,5);

Pick one of these irreducible polynomials. How likely will it be irreducible modulo some other prime? The command proportion_primes_poly_irred(f,N) helps investigate this.

> proportion_primes_poly_irred(1+x+x^3,100);

The number of such irreducibles of degree 3 mod 5 is given by the Psi0 command.

> Psi0(3,5);

Moreover, we can find all irreducible polynomial of degree 3 over F_5 and their period, by using the irreducibles_and_period command. Of course, this is slower than simply using the irreducibles command.

> irreducibles_and_period(3,5);

The number of such irreducibles with maximal period (124) is given by the lambda0 command

> lambda0(3,5);

>

> print(`degree prob irred poly has max period prob poly is irred`);
for n from 3 to 24 do
print(n,` `,evalf(Psi0(n,2)^(-1)*lambda0(n,2)),` `,evalf(Psi0(n,2)/(2^n-2)));
od;

The degrees which are multiples of 12 are "worst" than the others in some sense. This can be explored graphically by plotting the probability that a randomly choosen irreducible polynomial of a fixed degree n has maximum period, n=3,4,5,....,100.

> A:=plots[listplot]([1,1,seq(Psi0(n,2)^(-1)*lambda0(n,2),n=3..100)],view=[3..100,0..1.1]):
B:=plot(1,t=0..100):
plots[display]([A,B]);

To construct a finite field with p^d elements of characteristic p, we use the galoisfield command. This command returns a triple:

(a) The elements of the field in a list, each element being written in "GF notation", ie as a polynomial in 10000 with coefficients in 0...p-1.

(b) The irreducible polynomial generating the field extension.

(c) The GF data structure for the finite field.

> GF0:=galoisfield(2,1);
F2:=GF0[1];
f:=GF0[2];
FF:=GF0[3];

> GF0:=galoisfield(2,2);
F4:=GF0[1];
f:=GF0[2];
FF:=GF0[3];

> L1:=seq(FF[input](i),i=0..3);
L2:=seq(FF[output](x),x=L1);
L2:=seq(FF[ConvertOut](b),b=L1);
L3:=seq(FF[ConvertIn](c),c=L2);

The multiplication table of F_4 is easy to determine using the gf_mult_table command.

> gf_mult_table(2,2);

The addition table of F_4 is easy to determine using the gf_add_table command

> gf_add_table(2,2);

> f:=x->x^100-43*x^47+9;
gf_eval_poly(f(x),x,0,FF);
gf_eval_poly(f(x),x,10000,FF);
gf_eval_poly(f(x),x,10001,FF);
gf_eval_poly(f(x),x,1,FF);

Let us confirm "manually" (using gf_add, gf_intmult, gf_power) that 10000 is indeed a root of f.

> x1:=gf_power(10000,100,FF);
x2:=gf_power(10000,47,FF);
x3:=gf_intmult(-43,x2,FF);
x4:=gf_add(x1,x3,FF);
x5:=gf_intmult(9,1,FF);
gf_add(x4,x5,FF);

We confirm this yet again by computing all the roots of f using roots_to_poly_gf.

> roots_to_poly_gf(f(x),x,2,2);

Finally, we are also able to evaluate polynomials in 2 variables using the gf_eval_poly2 command.

> F:=(x,y)->x^2*y+x^3+2*x*y^2:
gf_eval_poly2(F(x,y),x,y,10000,10001,FF);

Though a root finding routine for polynomials in 2 variables wasn't written, it is not hard to write down some commands which do the job.

> SOLNS:=[]:
F4e2:=cartesian_power(F4,2):
temp:=0:
for P in F4e2 do
temp:=gf_eval_poly2(F(x,y),x,y,P[1],P[2],FF);
if temp=0 then SOLNS:=[op(SOLNS),P];
fi;
od:
SOLNS;

Each element of the finite extension FF of F_p can be regarded as an element of the quotient ring F_p[x]/(f). This ring is an F_p-vector space with basis 1,x,...,x^(d-1). Each element of FF acts on this vector space as a linear transformation which has a matrix representation. The command matrix_gf returns this dxd matrix.

> GF0:=galoisfield(2,4);
F8:=GF0[1];
seq(FF[output](x),x=F8);
matrix_gf(10001,2,4);

What is the least positive power of a=10001 which is 1 in FF? The order_gf command gives the answer.

> order_gf(10001,2,4);
order_gf(0,2,4);
and over F_5:
is_primitive_gf(2,5,1);
order_gf(2,5,1);

Of course, the order cannot be any larger than p^d-1. When the order of x is as large as possible (p^d-1) then the element x is called primitive. The is_primitive_gf returns true if the element is primitive, and false otherwise.

> is_primitive_gf(10001,2,4);
is_primitive_gf(10000,2,4);

All the primitives can be found using primitives_gf, in one form or another. (Of course, the command primitives_gf is faster.)

> primitives_gf(2,4);
primitives_gf_convert(2,4);
primitives_gf_output(2,4);

Since b=10000 is primitive, we know that there must be an n>0 such that b^n=10001. The least such n is called the logarithm of x=10001 to the base b. The command log_gf computes this.

> log_gf(10001,10000,2,4);
log_gf_input(3,2,2,4);

> log_gf(3,2,5,1);
and confirmation:
3^3 mod 5;

To illustrate some of the commands special to finite fields, let us take p=53 and comute the integers 1<m<p which are not squares mod p using the nonsqrsmodp command. These allow us to construct a quadratic extension F_53[sqrt(m)]=F_p + F_p*sqrt(m), whose elements we represent as pairs [a,b] <--> a + b*sqrt(m). The list below allows us to take m=2, which we shall do.

> nonsqrsmodp(53);

Here's how to multiply 1 + sqrt(m) by 2 + 3*sqrt(m) in F_53[sqrt(2)] using the quadfieldmult command.

> quadfieldmult([1,1],[2,3],2,53);

The norm of an element a + b*sqrt(m) is a^2 + m*b^2. The plot of all elements in F_53[sqrt(2)] of norm 4 is the following pretty picture, obtained using the plotlevelnorm command. Note the remarkable symmetry.

> plotlevelnorm(4,2,53);

The MAPLE 5.1 worksheet for this html page is ffield0.mws.
Created 7-8-99 by