{VERSION 5 0 "IBM INTEL LINUX" "5.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 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "Thanks to John Cook for su bmitting an earlier version of this to me, and sharing it with everyon e!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{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 181 "You will also need to choos e a primitive polynomial. A function for creating a list of primitive polynomials is in the following section. If you know one, skip ahead that section." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "p := 3; \+ \nn := 2;\nq := p^n;" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 31 "Finding \+ irreducible polynomials" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 101 "The fi eld GF(q) is a splitting field for x^(q-1) - 1. I want to factor thi s polynomial and find one" }}{PARA 0 "" 0 "" {TEXT -1 92 "of the facto rs with degree n such that p^n = q that has a root that will generate \+ the field." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "SF := Factors(x^(q-1) - 1) mod p:" }}{PARA 0 "" 0 "" {TEXT -1 94 "The second parameter retu rned by Factors returns the irreducible factors in the factorization. " }}{PARA 0 "" 0 "" {TEXT -1 69 "Loop through these factors and find o nes that can generate the field." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 361 "PrimFactors := []:\nfor FactorIndx from 1 to nops(SF[2]) do\n i f (degree(SF[2,FactorIndx,1])= n) then\n if (Primitive(SF[2,Facto rIndx,1]) mod p) then\n PrimFactors := [op(PrimFactors),SF[2,F actorIndx,1]]; \+ end if; \n end if;\nend do;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "The v ariable \"PrimFactors\" now contains a list of polynomials that should generate the field. To be on" }}{PARA 0 "" 0 "" {TEXT -1 41 "the saf e side, verify that one was found." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "if(nops(PrimFactors) <= 0) then\n print(\"No primitive polynomia ls found\");\nend if;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "You can use PrimFactors, from the \+ previous subsection, to get a factor or you can use " }}{PARA 0 "" 0 " " {TEXT -1 40 "a polynomial that you know is primitive." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "#f := PrimFactors[1];\nf := x^2+2*x +2;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Create a short name ali as (" }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 32 ") for the roo t 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 elem ent can be uniquely represented as a polynomial in " }{TEXT 256 1 "a" }{TEXT -1 89 " of degree less than n.\nEvery nonzero element can be u niquely represented as a power of " }{XPPEDIT 18 0 "alpha;" "6#%&alpha G" }{TEXT -1 19 " between 0 and q-2." }}{PARA 0 "" 0 "" {TEXT -1 95 "M aple 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 "account of the polynomial it satisfies a nd the modulus p." }}{PARA 0 "" 0 "" {TEXT -1 95 "It will be handy to \+ have a table to go back and forth between the expression of a field el ement" }}{PARA 0 "" 0 "" {TEXT -1 19 "as a polynomial in " }{TEXT 258 1 "a" }{TEXT -1 34 " and the expression as a power of " }{TEXT 259 2 " a." }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "You should check th at " }{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 "FieldTable := Matrix(q,2):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 273 "MakeTable := 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 FieldTab le[indx+1,1] := prim_elt^indx;\n FieldTable[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 initialized." }{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 p rint only matrices smaller than 10 by 10. The following command allow s you to print larger matrices..\n" }{MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "#interface(rtablesize=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 162 "When doing operations on the field, it would be nice to \+ have all results in terms of the power of the \nprimitive element rat her than as elements of the field. \n" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 428 "Eform := proc(element)\n local indx;\n\n if (element = 0) then\n RETURN(0);\n end if;\n\n indx := 1;\n while (indx < RowDimension(FieldTable)) do\n if (FieldTable[indx,2] = element) then\n RETURN(FieldTable[indx,1]);\n end if;\n indx := indx + 1;\n end do;\n print(element, \": Element not associated w ith a root power!\");\n RETURN(0); #These last two lines only occur \+ if the while loop fails.\nend proc:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "The next thing I want is a routine is to multiply matrices wher e the matrix elements are from" }}{PARA 0 "" 0 "" {TEXT -1 46 "the fin ite field that was just constructed. " }}{PARA 0 "" 0 "" {TEXT -1 123 "If we just multiply the matrices using M.N the result is not red uced mod p and it is not reduced using the equation that " }{TEXT 260 1 "a" }{TEXT -1 11 " satisfies." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "M:= Matrix(2,2,[[1+alpha,alpha^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(expand, N);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(modp, N1, p);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "Well that gets us part of the way. The follow ing function takes a matrix A and applies Normal () mod p to reduce mo dulo the polynomial that " }{TEXT 261 2 "a " }{TEXT -1 68 "satisfies. \+ \nIt also changes to the exponential form by using Eform." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 302 "MatEform := proc(A,p)\n local i, j, k, W;\n\n W := Matrix(RowDimension(A), ColumnDimension(A));\n \+ for i from 1 to RowDimension(A) do\n for k from 1 to ColumnDimens ion(A) do\n W[i,k] := Normal(A[i,k]) mod p;\n W[i,k] : = Eform(W[i,k]);\n end do;\n end do;\n RETURN(W);\nend proc: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "MatEform(M.M.M.M,p);" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "This is a similar routine for po lynomials 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 fu nction." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 366 "PolyEform := proc(poly, var, p)\n local retpoly, indx, coef;\n\n retpoly := 0;\n for in dx from 0 to degree(poly) do\n coef := coeff(poly, var, indx);\n \+ if (coef <> 0) then\n coef := Normal(coef) mod p;\n \+ coef := Eform(coef);\n retpoly := retpoly + coef*var^indx; \n end if;\n end do;\n sort(retpoly);\n RETURN(retpoly);\ne nd proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 34 "Finite Field Operations - Matrices" }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "Start with some very simple opera tions on the field. Verify that the following results are correct for " }}{PARA 0 "" 0 "" {TEXT -1 24 "the defined Finite 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 t o some matrix examples in the field" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "A := Matrix([[alpha^105,alpha^10],[alpha^115,alpha^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 LinearAlge bra 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 "N o 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 37 "Finite Field Operations - Polynom ials" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 90 "The goal here is to work w ith polynomials where the coefficients are members of the field." }} {PARA 0 "" 0 "" {TEXT -1 47 "Start with a couple of very simple polyno mials." }}{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 +alpha;" }}}{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(N ormal(expand(g*g2*g3)) mod p);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "Better, but what I really want is to convert the coefficients into th e 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 "" }}}}}{MARK "20" 0 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }