{VERSION 6 0 "IBM INTEL LINUX" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "symbol" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "
" -1 257 "symbol" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "
symbol" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "symbol" 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "symbol" 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "symbol" 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0
0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading
1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }
1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "" 3 256 1 {CSTYLE "" -1 -1 "" 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }
{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1
-1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1
0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 25 "Finite Fields with RootO
f" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 15 "Mi
ke O'Sullivan" }}{PARA 258 "" 0 "" {TEXT -1 26 "San Diego State Univer
sity" }}{PARA 259 "" 0 "" {TEXT -1 12 "January 2005" }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 118 " The simplest \+
way to create an extension of a field is to adjoin a root of a polynom
ial with the RootOf() procedure. " }}{PARA 0 "" 0 "" {TEXT -1 106 "Th
is worksheet shows how to create a finite field and then how to work w
ith matrices and polynomials over " }}{PARA 0 "" 0 "" {TEXT -1 15 "a f
inite field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT
-1 99 "Thanks to John Cook for submitting an earlier version of this \+
to me, and sharing it with everyone!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT
-1 78 "Restart Maple and pull in the LinearAlgebra package that will b
e needed later." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "with(LinearAlgebra):" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "Define how many elements are in th
e field and the prime over which the field is to be built." }}{PARA 0
"" 0 "" {TEXT -1 58 "You will change these values to create different \+
fields. " }}{PARA 0 "" 0 "" {TEXT -1 176 "You will also need to choos
e a primitive polynomial. A function for creating a list of primitive
polynomials is in the following section. \nIf you know one, skip tha
t section." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "p := 3; \ns \+
:= 2;\nq := p^s;\nn := q-1;" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 31 "F
inding irreducible polynomials" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 101
"The field GF(q) is a splitting field for x^(q-1) - 1. I want to fac
tor this polynomial and find one" }}{PARA 0 "" 0 "" {TEXT -1 100 "of t
he factors with degree n (where p^n = q). Furthermore, I want to fin
d a primitive polynomial, " }}{PARA 0 "" 0 "" {TEXT -1 55 "generates t
he mulitplicative group of the finite field." }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 31 "SF := Factors(x^(n) - 1) mod p:" }}{PARA 0 "" 0 ""
{TEXT -1 94 "The second parameter returned by Factors returns the irre
ducible factors in the factorization." }}{PARA 0 "" 0 "" {TEXT -1 69 "
Loop through these factors and find ones that can generate the field.
" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 367 "PrimFactors := []:\nfor Factor
Indx from 1 to nops(SF[2]) do\n if (degree(SF[2,FactorIndx,1])= s) t
hen\n if (Primitive(SF[2,FactorIndx,1]) mod p) then\n Pri
mFactors := [op(PrimFactors),SF[2,FactorIndx,1]]; \+
\+
end if;\n end if;\nend do;\n" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "The variable \"PrimFactors\" now \+
contains a list of polynomials that should generate the field. To be \+
on" }}{PARA 0 "" 0 "" {TEXT -1 41 "the safe side, verify that one was \+
found." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "if(nops(PrimFactors) <= 0
) then\n print(\"No primitive polynomials found\");\nend if;" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT
-1 23 "Creating a Finite Field" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 83 "
You can use PrimFactors, from the previous section, to get a factor or
you can use " }}{PARA 0 "" 0 "" {TEXT -1 40 "a polynomial that you kn
ow is primitive." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "#f := P
rimFactors[1];\nf := x^2+2*x +2;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT
-1 27 "Create a short name alias (" }{XPPEDIT 18 0 "alpha;" "6#%&alpha
G" }{TEXT -1 32 ") for the root of the polynomial" }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 23 "alias(alpha=RootOf(f));" }}}{EXCHG {PARA 0 "" 0 ""
{TEXT -1 69 "In GF(q) each element can be uniquely represented as a po
lynomial in " }{TEXT 256 1 "a" }{TEXT -1 89 " of degree less than n.
\nEvery nonzero element can be uniquely represented as a power of " }
{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 19 " between 0 and q-2.
" }}{PARA 0 "" 0 "" {TEXT -1 95 "Maple has a Normal function that can \+
be used with \"mod p\" to reduce an arbitrary poynomial in " }{TEXT
257 1 "a" }{TEXT -1 9 ", taking " }}{PARA 0 "" 0 "" {TEXT -1 57 "accou
nt of the polynomial it satisfies and the modulus p." }}{PARA 0 "" 0 "
" {TEXT -1 95 "It will be handy to have a table to go back and forth b
etween the expression of a field element" }}{PARA 0 "" 0 "" {TEXT -1
19 "as a polynomial in " }{TEXT 258 1 "a" }{TEXT -1 34 " and the expre
ssion as a power of " }{TEXT 259 2 "a." }{TEXT -1 0 "" }}{PARA 0 "" 0
"" {TEXT -1 23 "You should check that " }{XPPEDIT 18 0 "alpha;" "6#%&
alphaG" }{TEXT -1 17 "^(p^n - 1) is 1.\n" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "FieldTa
ble := Matrix(q,2):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 273 "Mak
eTable := proc(qq, pp, prim_elt)\nlocal indx; global FieldTable;\n\n
\nfor indx from 0 to qq - 1 do\n print(prim_elt^indx = Normal (prim_
elt^indx ) mod pp);\n FieldTable[indx+1,1] := prim_elt^indx;\n Fie
ldTable[indx+1,2] := Normal(prim_elt^indx) mod pp;\nend do:\nend proc;
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "The field table will now be i
nitialized." }{MPLTEXT 1 0 0 "" }{TEXT -1 0 "" }{MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "MakeTable(q,p,alpha);" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT
-1 124 "Maple will normally print only matrices smaller than 10 by 10.
The following command allows you to print larger matrices..\n" }
{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "#interface(rtab
lesize=25);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "FieldTable;
" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 23 "Finite Field Procedures" }}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "Here are a few procedures to make \+
operations over finite fields easier." }}{PARA 0 "" 0 "" {TEXT -1 0 "
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 161 "When doing operations on the
field, it would be nice to have all results in terms of the power of \+
the \nprimitive element rather than as elements of the field. " }}
{PARA 0 "" 0 "" {TEXT -1 40 "The procedure Eform() does that for us.\n
" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 462 "Eform := proc(element)\n loc
al elt, indx;\n\n elt := Normal(element) mod p;\n if (elt = 0) the
n\n RETURN(0);\n end if;\n\n indx := 1;\n while (indx < Row
Dimension(FieldTable)) do\n if (FieldTable[indx,2] = elt) then\n \+
RETURN(FieldTable[indx,1]);\n end if;\n indx := indx + \+
1;\n end do;\n print(element,elt, \": Element not associated with \+
a root power!\");\n RETURN(0); #These last two lines only occur if t
he while loop fails.\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT
1 0 116 "Finv := proc(element)\nlocal elt, deg;\n\nelt := Eform(elemen
t);\ndeg := degree(elt,alpha);\nRETURN(alpha^(n-deg));\nend;\n" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Finv(alpha^5);" }}}}{SECT 1
{PARA 3 "" 0 "" {TEXT -1 59 "Procedures for Matrices and Polynomials o
ver a Finite Field" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "The next thing I want is a routine
is to multiply matrices where the matrix elements are from" }}{PARA
0 "" 0 "" {TEXT -1 46 "the finite field that was just constructed. \+
" }}{PARA 0 "" 0 "" {TEXT -1 123 "If we just multiply the matrices usi
ng M.N the result is not reduced mod p and it is not reduced using t
he equation that " }{TEXT 260 1 "a" }{TEXT -1 11 " satisfies." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "M:= Matrix(2,2,[[1+alpha,alp
ha^18],[1+2*alpha,0]]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "N
:= M^4;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "N1 := map(expan
d, N);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(modp, N1, p);
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 142 "Well that gets us part of th
e way. The following procedure takes a matrix A and applies Normal ()
mod p to reduce modulo the polynomial that " }{TEXT 261 2 "a " }
{TEXT -1 70 "satisfies. \nIt also changes to the exponential form by \+
using Eform()." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 259 "MatEform
:= proc(A)\n local i, j, k, W;\n\n W := Matrix(RowDimension(A), C
olumnDimension(A));\n for i from 1 to RowDimension(A) do\n for \+
k from 1 to ColumnDimension(A) do\n W[i,k] := Eform(A[i,k]);\n
end do;\n end do;\n RETURN(W);\nend proc:" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 18 "MatEform(M.M.M.M);" }}}{EXCHG {PARA 0 ""
0 "" {TEXT -1 77 "This is a similar routine for polynomials to powers \+
of the root in the field." }}{PARA 0 "" 0 "" {TEXT -1 64 "The variable
var for the polynomial is an input to the function." }}{PARA 0 "> "
0 "" {MPLTEXT 1 0 326 "PolyEform := proc(poly, var)\n local retpoly,
indx, coef;\n\n retpoly := 0;\n for indx from 0 to degree(poly) d
o\n coef := coeff(poly, var, indx);\n if (coef <> 0) then\n \+
coef := Eform(coef);\n retpoly := retpoly + coef*var^i
ndx;\n end if;\n end do;\n sort(retpoly);\n RETURN(retpoly)
;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 277 "MatPolyEfo
rm := proc(A,var,p)\n local i, j, k, W;\n\n W := Matrix(RowDimensi
on(A), ColumnDimension(A));\n for i from 1 to RowDimension(A) do\n \+
for k from 1 to ColumnDimension(A) do\n W[i,k] := PolyEfor
m(A[i,k],var);\n end do;\n end do;\n RETURN(W);\nend proc:" }
}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 47 "Examples: Finite Field Operati
ons with Matrices" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "Start with s
ome very simple operations on the field. Verify that the following re
sults are correct for" }}{PARA 0 "" 0 "" {TEXT -1 24 "the defined Fini
te Field" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Normal(alpha^5) mod p; \+
" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "Normal(alpha^10) mod p;" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g := Normal(alpha^5 + alpha^10) mod
p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Eform(g);" }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 38 "g := Normal(alpha^5 * alpha^10) mod p;" }}{PARA 0 "
> " 0 "" {MPLTEXT 1 0 9 "Eform(g);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT
-1 48 "Now move on to some matrix examples in the field" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 58 "A := Matrix([[alpha^105,alpha^10],[alpha^115,a
lpha^120]]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "B := Matrix([[alpha
^125,alpha^13],[alpha^15,alpha^14]]);" }}}{EXCHG {PARA 0 "" 0 ""
{TEXT -1 71 "Put the sample arays into the correct Normal form for the
current field" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ANorm := MatEform
(A,p);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "BNorm := MatEform(B,p);"
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "Addition is as you would expect
. Note LinearAlgebra Add() or '+' can be used" }{MPLTEXT 1 0 0 "" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "MatEform(Add(A,B),p);" }}{PARA 0 ">
" 0 "" {MPLTEXT 1 0 29 "MatEform(Add(ANorm,BNorm),p);" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 16 "MatEform(A+B,p);" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 6 "A + B;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 33 "No surprises with Multiplication " }
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "A.B;" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 16 "MatEform(A.B,p);" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT
-1 50 "Examples: Finite Field Operations with Polynomials" }}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 90 "The goal here is to work with polynomials
where the coefficients are members of the field." }}{PARA 0 "" 0 ""
{TEXT -1 47 "Start with a couple of very simple polynomials." }}{PARA
0 "> " 0 "" {MPLTEXT 1 0 21 "g := alpha*x + alpha;" }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 35 "g2 := alpha^2*x^2 + alpha*x +alpha;" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 49 "g3 := alpha^3*x^3 + alpha^2*x^2 + alpha*x +alp
ha;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Notice the ugly mess when \+
these polynomials are multiplied" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22
"sort(expand(g*g2*g3));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "Try to
control it by using the standard Normal function" }{MPLTEXT 1 0 0 ""
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "sort(Normal(expand(g*g2*g
3)) mod p);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "Better, but what I
really want is to convert the coefficients into the proper powers of \+
the root." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1
0 42 "g4 := sort(Normal(expand(g*g2*g3)) mod p);" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 24 "g4 := PolyEform(g4,x,p);" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 20 "PolyEform(g4^3,x,p);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "6" 0 }
{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }