{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 "2D Output" 2 20 "" 0 1 0 0 255 1 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 "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {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 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG \"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"sG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"n G\"\")" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 31 "Finding irreducible po lynomials" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 101 "The field GF(q) is \+ a splitting field for x^(q-1) - 1. I want to factor this polynomial a nd find one" }}{PARA 0 "" 0 "" {TEXT -1 92 "of the factors with degree n such that p^n = q that has a root that will generate the 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 irreducible factors in the factorization." }}{PARA 0 "" 0 "" {TEXT -1 69 "Loop through these factors and find ones that can gene rate the field." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 361 "PrimFactors := \+ []:\nfor FactorIndx from 1 to nops(SF[2]) do\n if (degree(SF[2,Facto rIndx,1])= s) then\n if (Primitive(SF[2,FactorIndx,1]) mod p) the n\n PrimFactors := [op(PrimFactors),SF[2,FactorIndx,1]]; \+ \+ end if;\n end if;\nend do ;\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "The variable \"PrimFactor s\" 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(PrimFacto rs) <= 0) then\n print(\"No primitive polynomials found\");\nend if; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {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 fa ctor 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" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,(*$)%\"xG\"\"#\"\"\"F**&F)F*F(F*F*F)F*" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Create a short name alias (" } {XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 32 ") for the root of th e polynomial" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "alias(alpha=RootOf( f));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&alphaG" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 69 "In GF(q) each element can be uniquely represented \+ as a polynomial in " }{TEXT 256 1 "a" }{TEXT -1 89 " of degree less t han n.\nEvery nonzero element can be uniquely represented as a power o f " }{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 "account 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 f orth between 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 expression 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 "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_e lt^indx = Normal (prim_elt^indx ) mod pp);\n FieldTable[indx+1,1] := prim_elt^indx;\n FieldTable[indx+1,2] := Normal(prim_elt^indx) mod \+ pp;\nend do:\nend proc;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*MakeTabl eGf*6%%#qqG%#ppG%)prim_eltG6#%%indxG6\"F,?(8$\"\"!\"\"\",&9$F0F0!\"\"% %trueGC%-%&printG6#/)9&F.-%$modG6$-%'NormalG6#F:9%>&%+FieldTableG6$,&F .F0F0F0F0F:>&FE6$FG\"\"#F " 0 "" {MPLTEXT 1 0 21 "MakeTable(q,p,alpha);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#/\"\"\"F$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&alphaGF$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&al phaG\"\"#\"\"\",&F&F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&alp haG\"\"$\"\"\",&F&\"\"#F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&a lphaG\"\"%\"\"\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&alphaG \"\"&\"\"\",$F&\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&alphaG\" \"'\"\"\",&F&\"\"#F*F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&alphaG \"\"(\"\"\",&F&F(\"\"#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$)%&alph aG\"\")\"\"\"F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{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 larg er 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"* [BsM\"-%'MATRIXG6#7+7$\"\"\"F,7$%&alphaGF.7$*$)F.\"\"#F,,&F.F,F,F,7$*$ )F.\"\"$F,,&F.F2F,F,7$*$)F.\"\"%F,F27$*$)F.\"\"&F,,$F.F27$*$)F.\"\"'F, ,&F.F2F2F,7$*$)F.\"\"(F,,&F.F,F2F,7$*$)F.\"\")F,F," }}}}{SECT 0 {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 fini te fields easier." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 162 "When doing operations on the field, it would be n ice to have all results in terms of the power of the \nprimitive eleme nt rather than as elements of the field. \n" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 462 "Eform := proc(element)\n local elt, indx;\n\n el t := Normal(element) mod p;\n if (elt = 0) then\n RETURN(0);\n \+ end if;\n\n indx := 1;\n while (indx < RowDimension(FieldTable)) do\n if (FieldTable[indx,2] = elt) then\n RETURN(FieldTa ble[indx,1]);\n end if;\n indx := indx + 1;\n end do;\n pri nt(element,elt, \": Element not associated with a root power!\");\n \+ RETURN(0); #These last two lines only occur if the while loop fails.\n end proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 116 "Finv := proc( element)\nlocal elt, deg;\n\nelt := Eform(element);\ndeg := degree(elt ,alpha);\nRETURN(alpha^(n-deg));\nend;\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%FinvGf*6#%(elementG6$%$eltG%$degG6\"F+C%>8$-%&EformG6#9$>8%-% 'degreeG6$F.%&alphaG-%'RETURNG6#)F8,&%\"nG\"\"\"F4!\"\"F+F+F+" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Finv(alpha^5);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#*$)%&alphaG\"\"$\"\"\"" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 59 "Procedures for Matrices and Polynomials over a Finit e 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 multip ly 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 using M.N the result is not reduced mod p and it is not reduced using the equatio n 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*a lpha,0]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG-%'RTABLEG6$\"*/98 N\"-%'MATRIXG6#7$7$,&%&alphaG\"\"\"F0F0*$)F/\"#=F07$,&F/\"\"#F0F0\"\"! " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "N := M^4;" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#>%\"NG-%'RTABLEG6$\"*_\\FN\"-%'MATRIXG6#7$7$,&*$ ),&*$),&%&alphaG\"\"\"F6F6\"\"#F6F6*&)F5\"#=F6,&F5F7F6F6F6F6F7F6F6*(F3 F6F9F6F;F6F6,&*(F1F6F4F6F9F6F6*(F4F6)F5\"#OF6F;F6F67$,&*(F;F6F4F6F1F6F 6*(F9F6)F;F7F6F4F6F6,&F " 0 "" {MPLTEXT 1 0 21 "N1 := map(expand, N);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#N1G-%'RTABLEG6$\"*%=t^8-%'MATRIXG6#7$7$,:\"\"\"F/*&\"\"%F/%&a lphaGF/F/*&\"\"$F/)F2\"#=F/F/*$)F2F1F/F/*&F1F/)F2F4F/F/*&\"\"'F/)F2\" \"#F/F/*&FF/F/*&F1F/)F 2\"#QF/F/*&F1F/)F2\"#PF/F/*$)F2\"#OF/F/,0*$F@F/F/*&F4F/FDF/F/*&F4F/FHF /F/*$F5F/F/*&F1F/FKF/F/*&FF/FQF/F/7$,4F7F>*&\"\"(F/F:F/F/ *&\"\"*F/F=F/F/*&\"\")F/F@F/F/*&\"#;F/FDF/F/*&\"\"&F/F2F/F/*&\"#5F/FHF /F/F/F/*&F>F/F5F/F/,0FTF>*&F`oF/FDF/F/*&F1F/FHF/F/FWF/*&F1F/FKF/F/*&F1 F/FNF/F/FPF/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "map(modp, N 1, p);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"*%3z^8-%'MATRI XG6#7$7$,0\"\"\"F-%&alphaGF-*$)F.\"\"%F-F-*$)F.\"\"$F-F-*$)F.\"#QF-F-* $)F.\"#PF-F-*$)F.\"#OF-F-,**$)F.\"#@F-F-*$)F.\"#=F-F-F5F-*&\"\"#F-FF-F-F-F-*& FFF-FCF-F-,0F?FF*&FFF-FKF-F-FNF-FBF-F5F-F8F-F;F-" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 141 "Well that gets us part of the way. The following function takes a matrix A and applies Normal () mod p to reduce modul o the polynomial that " }{TEXT 261 2 "a " }{TEXT -1 68 "satisfies. \n It 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), ColumnDimension(A));\n fo r i from 1 to RowDimension(A) do\n for k from 1 to ColumnDimensio n(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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$ \"*)=5`8-%'MATRIXG6#7$7$*$)%&alphaG\"\"(\"\"\"*$)F.\"\"$F07$*$)F.\"\"% F0F1" }}}{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(pol y, var)\n local retpoly, indx, coef;\n\n retpoly := 0;\n for ind x from 0 to degree(poly) do\n coef := coeff(poly, var, indx);\n \+ if (coef <> 0) then\n coef := Eform(coef);\n retpo ly := retpoly + coef*var^indx;\n end if;\n end do;\n sort(ret poly);\n RETURN(retpoly);\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 277 "MatPolyEform := proc(A,var,p)\n local i, j, k, W; \n\n W := Matrix(RowDimension(A), ColumnDimension(A));\n for i fro m 1 to RowDimension(A) do\n for k from 1 to ColumnDimension(A) do \n W[i,k] := PolyEform(A[i,k],var);\n end do;\n end do; \n RETURN(W);\nend proc:" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 47 "E xamples: Finite Field Operations with Matrices" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "Start with some very simple operations 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 "N ormal(alpha^10) mod p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g := Norm al(alpha^5 + alpha^10) mod p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Efo rm(g);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g := Normal(alpha^5 * alp ha^10) mod p;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Eform(g);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$%&alphaG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&%&alphaG\"\"\"F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"gG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"gG,&%&alphaG\"\"\"\"\"#F'" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#*$)%&alphaG\"\"(\"\"\"" }}}{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,alpha^120]]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "B := Mat rix([[alpha^125,alpha^13],[alpha^15,alpha^14]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'RTABLEG6$\"*'**RZ8-%'MATRIXG6#7$7$*$)%&alphaG \"$0\"\"\"\"*$)F0\"#5F27$*$)F0\"$:\"F2*$)F0\"$?\"F2" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"BG-%'RTABLEG6$\"*wQMN\"-%'MATRIXG6#7$7$*$)%&alpha G\"$D\"\"\"\"*$)F0\"#8F27$*$)F0\"#:F2*$)F0\"#9F2" }}}{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 := M atEform(A,p);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "BNorm := MatEform( B,p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ANormG-%'RTABLEG6$\"*?AeM \"-%'MATRIXG6#7$7$%&alphaG*$)F.\"\"#\"\"\"7$*$)F.\"\"$F2F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&BNormG-%'RTABLEG6$\"*%Q3\\8-%'MATRIXG6#7$ 7$*$)%&alphaG\"\"&\"\"\"F.7$*$)F0\"\"(F2*$)F0\"\"'F2" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "Addition is as you would expect. Note LinearAl gebra 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"*gb\"y8-%'MAT RIXG6#7$7$\"\"!\"\"\"7$F,*$)%&alphaG\"\"&F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"*/(>y8-%'MATRIXG6#7$7$\"\"!\"\"\"7$F,*$)% &alphaG\"\"&F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"*/>#y8 -%'MATRIXG6#7$7$\"\"!\"\"\"7$F,*$)%&alphaG\"\"&F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"*S!yj8-%'MATRIXG6#7$7$,&*$)%&alphaG\"$0\" \"\"\"F1*$)F/\"$D\"F1F1,&*$)F/\"#5F1F1*$)F/\"#8F1F17$,&*$)F/\"$:\"F1F1 *$)F/\"#:F1F1,&*$)F/\"$?\"F1F1*$)F/\"#9F1F1" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "No surprises with Multi plication " }{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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6$\"*Gn#y8-%'MATRIXG6#7$7$,&*$)%&alphaG\"$I#\"\"\"F1*$ )F/\"#DF1F1,&*$)F/\"$=\"F1F1*$)F/\"#CF1F17$,&*$)F/\"$S#F1F1*$)F/\"$N\" F1F1,&*$)F/\"$G\"F1F1*$)F/\"$M\"F1F1" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#-%'RTABLEG6$\"*s)Gy8-%'MATRIXG6#7$7$*$)%&alphaG\"\"%\"\"\"*$)F.\"\"& F07$F.F1" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 50 "Examples: Finite Fi eld 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 cou ple of very simple polynomials." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " g := alpha*x + alpha;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "g2 := alph a^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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,&*&%&alphaG\"\"\"%\"xGF(F(F'F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g2G,(*&)%&alphaG\"\"#\"\"\")%\"xGF)F*F**&F(F*F,F* F*F(F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g3G,**&)%&alphaG\"\"$\"\" \")%\"xGF)F*F**&)F(\"\"#F*)F,F/F*F**&F(F*F,F*F*F(F*" }}}{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) );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,:*&)%&alphaG\"\"'\"\"\")%\"xGF' F(F(*(\"\"#F()F&\"\"&F()F*F.F(F(*&F%F(F/F(F(*(F,F()F&\"\"%F()F*F3F(F(* (\"\"$F(F-F(F4F(F(*(F3F(F2F()F*F6F(F(*&)F&F6F(F8F(F(*&F-F(F8F(F(*(F6F( F:F()F*F,F(F(*(F,F(F2F(F=F(F(*(F6F(F:F(F*F(F(*$F:F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "Try to control it by using the standard N ormal function" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "sort(Normal(expand(g*g2*g3)) mod p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,&%&alphaG\"\"#F&\"\"\"F',.*$)%\"xG\"\"'F'F'*&F$ F')F+\"\"&F'F'*&,&F%F'F'F'F')F+\"\"%F'F'*&,&F%F&F'F'F')F+\"\"$F'F'*&F1 F')F+F&F'F'*&F&F'F%F'F'F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "Bett er, but what I really want is to convert the coefficients into the pro per 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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g4G*&,&%&alphaG\"\"#F(\"\"\"F),.*$)%\"xG \"\"'F)F)*&F&F))F-\"\"&F)F)*&,&F'F)F)F)F))F-\"\"%F)F)*&,&F'F(F)F)F))F- \"\"$F)F)*&F3F))F-F(F)F)*&F(F)F'F)F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g4G,.*&)%&alphaG\"\"'\"\"\")%\"xGF)F*F**&)F(\"\"%F*)F,\"\"&F* F**$)F,F/F*F**&F(F*)F,\"\"$F*F**$)F,\"\"#F*F**$)F(F6F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "PolyEform(g4^3,x,p);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#,.*&)%&alphaG\"\"#\"\"\")%\"xG\"#=F(F(*&)F&\"\"% F()F*\"#:F(F(*$)F*\"#7F(F(*&)F&\"\"$F()F*\"\"*F(F(*$)F*\"\"'F(F(F&F(" }}}{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 "9 4 4 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }{RTABLE_HANDLES 134722348 135131404 135274952 135173184 135179084 135310188 134739996 135343876 134582220 134908384 }{RTABLE M7R0 I6RTABLE_SAVE/134722348X,%)anythingG6"6"[gl!"%!!!#3"*"#"""-%'RootOfG6#,(*$%#_ZG ""#F'F-F.F.F'*$F(F.*$F(""$*$F(""%*$F(""&*$F(""'*$F(""(*$F("")F'F(,&F(F'F'F',&F( F.F'F'F.,$F(F.,&F(F.F.F',&F(F'F.F'F'F& } {RTABLE M7R0 I6RTABLE_SAVE/135131404X,%)anythingG6"6"[gl!"%!!!#%"#"#,&-%'RootOfG6#,(*$%#_ZG" "#"""F-F.F.F/F/F/F/,&F(F.F/F/*$F("#=""!F& } {RTABLE M7R0 I6RTABLE_SAVE/135274952X,%)anythingG6"6"[gl!"%!!!#%"#"#,&*$,&*$,&-%'RootOfG6#,( *$%#_ZG""#"""F1F2F2F3F3F3F3F2F3*&F,"#=,&F,F2F3F3F3F3F2F3*(F+F2F,F5F6F3F3,&*(F6F 3F+F3F)F3F3*(F,F5F6F2F+F3F3,&*(F)F3F+F3F,F5F3*(F+F3F,"#OF6F3F3,&F7F3*&F,F>F6F2F 3F& } {RTABLE M7R0 I6RTABLE_SAVE/135173184X,%)anythingG6"6"[gl!"%!!!#%"#"#,:"""F(-%'RootOfG6#,(*$% #_ZG""#F(F.F/F/F(""%*$F)"#=""$*$F)F0F(*$F)F3F0*$F)F/""'*$F)"#@F7*$F)"#?"#:*$F)" #>"#7*$F)"#QF0*$F)"#PF0*$F)"#OF(,4F4F/F5""(F6""*F8"")F:"#;F)""&F="#5F(F(F1F/,0F 8F(F:F3F=F3F1F(F@F0FBF7FDF/,0F8F/F:FKF=F0F1F(F@F0FBF0FDF(F& } {RTABLE M7R0 I6RTABLE_SAVE/135179084X,%)anythingG6"6"[gl!"%!!!#%"#"#,0"""F(-%'RootOfG6#,(*$% #_ZG""#F(F.F/F/F(F(*$F)""%F(*$F)""$F(*$F)"#QF(*$F)"#PF(*$F)"#OF(,2F0F/F2F(*$F)" #@F/*$F)"#?F(F)F/*$F)"#>F(F(F(*$F)"#=F/,*F;F(FAF(F4F(F8F/,0F;F/F=F/F?F(FAF(F4F( F6F(F8F(F& } {RTABLE M7R0 I6RTABLE_SAVE/135310188X,%)anythingG6"6"[gl!"%!!!#%"#"#*$-%'RootOfG6#,(*$%#_ZG" "#"""F-F.F.F/""(*$F(""%*$F(""$F3F& } {RTABLE M7R0 I6RTABLE_SAVE/134739996X,%)anythingG6"6"[gl!"%!!!#%"#"#*$-%'RootOfG6#,(*$%#_ZG" "#"""F-F.F.F/"$0"*$F("$:"*$F("#5*$F("$?"F& } {RTABLE M7R0 I6RTABLE_SAVE/135343876X,%)anythingG6"6"[gl!"%!!!#%"#"#*$-%'RootOfG6#,(*$%#_ZG" "#"""F-F.F.F/"$D"*$F("#:*$F("#8*$F("#9F& } {RTABLE M7R0 I6RTABLE_SAVE/134582220X,%)anythingG6"6"[gl!"%!!!#%"#"#-%'RootOfG6#,(*$%#_ZG""# """F,F-F-F.*$F'""$*$F'F-F.F& } {RTABLE M7R0 I6RTABLE_SAVE/134908384X,%)anythingG6"6"[gl!"%!!!#%"#"#*$-%'RootOfG6#,(*$%#_ZG" "#"""F-F.F.F/""&*$F(""(F'*$F(""'F& }