{VERSION 4 0 "IBM INTEL NT" "4.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 Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1
{CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }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 1 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0
" -1 256 1 {CSTYLE "" -1 -1 "Helvetica" 0 12 0 0 0 0 2 1 2 0 0 0 0 0
0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 }{PSTYLE "R3 Font 2" -1 257 1
{CSTYLE "" -1 -1 "Courier" 0 12 0 0 97 0 2 2 2 0 0 0 0 0 0 1 }0 0 0
-1 -1 -1 0 0 0 0 0 0 0 0 }{PSTYLE "R3 Font 3" -1 258 1 {CSTYLE "" -1
-1 "New century schoolbook" 0 12 0 0 0 0 2 1 2 0 0 0 0 0 0 1 }0 0 0
-1 -1 -1 0 0 0 0 0 0 0 0 }}
{SECT 0 {EXCHG {PARA 258 "" 0 "" {TEXT -1 23 "Finite Splitting Fields
" }}{PARA 0 "" 0 "" {TEXT -1 291 "Michael Monagan\n\nThis worksheet is
an application of Maple to doing some simple calculations over finite
fields GF(p^k).\nThe application is from error correcting codes and w
as brought to us by Nicolas Sendrier, INRIA, France, in May/90.\nWe we
re given a polynomial f(x) of the following form\n" }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 26 "f := a -> 1+x^2+a*x^3+x^4;" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%\"fGR6#%\"aG6\"6$%)operatorG%&arrowGF(,*\"\"\"F-*$)%
\"xG\"\"#F-F-*&9$F-)F0\"\"$F-F-*$)F0\"\"%F-F-F(F(F(" }}}{EXCHG {PARA
0 "" 0 "" {TEXT -1 298 "\nwhere a = alpha was a given element in K = G
F(2^17), and we were asked to determine if the polynomial f(alpha) spl
its into linear factors over K. It turned out that for the alpha we w
ere given, the polynomial did not split. We were then asked to find a
n element a in K such that f(a) did split.\n" }}{PARA 0 "" 0 "" {TEXT
-1 208 "First let us define the field K(alpha) = GF(2^17) in Maple. W
e will represent the elements in K as polynomials in alpha where the m
inimial polynomial for alpha over GF(2) is this one (which was given t
o us)\n" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "minpoly := y^17 + y^3 + \+
1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(minpolyG,(*$)%\"yG\"#<\"\"\"F
**$)F(\"\"$F*F*F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "\nWe can c
heck that this polynomial is irreducible over the ground field GF(2)"
}}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Factor(minpoly) mod 2;" }}{PARA
11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"yG\"#<\"\"\"F(*$)F&\"\"$F(F(F(F(" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 222 "\nIn Maple we represent the elem
ents of a general finite field GF(p^k) as polynomials in alpha where a
lpha is a RootOf the minimal polynomial. And we use the alias command
so that RootOf(minpoly) will print nicely as alpha" }}{PARA 0 "> " 0
"" {MPLTEXT 1 0 36 "alias( alpha = RootOf(y^17+y^3+1) ):" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 44 "\nAs an example, here is the inverse of a
lpha" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Normal(1/alpha) mod 2;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%&alphaG\"#;\"\"\"F(*$)F&\"\"#F(F
(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "\nThus our polynomial in x o
ver K is" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f(alpha);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#,*\"\"\"F$*$)%\"xG\"\"#F$F$*&%&alphaGF$)F'\"\"$F
$F$*$)F'\"\"%F$F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 318 "\nOur quest
ion is: does f(alpha) split over GF(2^17) into linear factors?\nThis c
an be answered by trying to factor f(alpha) and looking to see if all \+
the factors are linear. But since we are only interested in the linea
r factors, we can just test to see how many roots the the polynomial h
as - which is more efficient." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Ro
ots(f(alpha)) mod 2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$7$,2*$)%&alp
haG\"#:\"\"\"F**$)F(\"#9F*F**$)F(\"#7F*F**$)F(\"#5F*F**$)F(\"\"*F*F**$
)F(\"\")F*F**$)F(\"\"&F*F*F*F*F*7$,6*$)F(\"#;F*F*F&F*F.F**$)F(\"#6F*F*
F4F*F7F**$)F(\"\"(F*F*F:F**$)F(\"\"$F*F*F(F*F*" }}}{EXCHG {PARA 0 ""
0 "" {TEXT -1 251 "\nThis says that there are two roots each with mult
iplicity 1. So the polynomial did not split into linear factors. Not
e, another efficient way to test if a polynomial over a finite field f
actors into linear factors is to test if this condition holds" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "Rem( x^(2^17), f(alpha), x ) = x;"
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%$RemG6%*$)%\"xG\"'s58\"\"\",*F+F+
*$)F)\"\"#F+F+*&%&alphaGF+)F)\"\"$F+F+*$)F)\"\"%F+F+F)F)" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 431 "\nBut we better not try to compute this \+
remainder because the input polynomial has degree 131072!! This calcu
lation can be computed efficiently using the Powmod function which use
s binary powering with remainder to compute this remainder. The idea \+
is to compute this remainder as Rem( Rem( (131072)/2, f(alhpa), x )^
2, f(alpha), x ). It is a good excercise to write a little program to
do this and to determine the actual cost." }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 25 "Powmod(x,2^17,f,x) mod 2;" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 250 "\nNow th
e next question was to try to find an element a of GF(2^17) such that \+
f(a) splits into linear factors. We do this by simply trying a random
polynomial in alpha (of degree 16 or less) until we find a good one. \+
Here is a little loop to do this" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 2
"do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " a := subs( y=alpha, Randp
oly(16,y) mod 2 );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 " if Powmod(
x, 2^17, f(a), x ) mod 2 = x then print(a); break fi;" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 0 "" {TEXT -1 0 "" }}{PARA
11 "" 1 "" {XPPMATH 20 "6#>%\"aG,0*$)%&alphaG\"#;\"\"\"F**$)F(\"#:F*F*
*$)F(\"#7F*F**$)F(\"#6F*F**$)F(\"\"&F*F**$)F(\"\"$F*F*F*F*" }}{PARA
11 "" 1 "" {XPPMATH 20 "6#>%\"aG,6*$)%&alphaG\"#;\"\"\"F**$)F(\"#7F*F*
*$)F(\"#6F*F**$)F(\"\")F*F**$)F(\"\"(F*F**$)F(\"\"'F*F**$)F(\"\"%F*F**
$)F(\"\"#F*F*F(F*F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,2*$)%&
alphaG\"#;\"\"\"F**$)F(\"#9F*F**$)F(\"#8F*F**$)F(\"#6F*F**$)F(\"#5F*F*
*$)F(\"\")F*F**$)F(\"\"&F*F*F(F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"aG,.*$)%&alphaG\"#;\"\"\"F**$)F(\"#:F*F**$)F(\"#8F*F**$)F(\"#7F*F**$
)F(\"\"*F*F**$)F(\"\")F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,8
*$)%&alphaG\"#;\"\"\"F**$)F(\"#9F*F**$)F(\"#8F*F**$)F(\"#7F*F**$)F(\"#
5F*F**$)F(\"\")F*F**$)F(\"\"(F*F**$)F(\"\"%F*F**$)F(\"\"#F*F*F(F*F*F*
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,8*$)%&alphaG\"#;\"\"\"F**$)
F(\"#:F*F**$)F(\"#9F*F**$)F(\"#8F*F**$)F(\"#6F*F**$)F(\"\"(F*F**$)F(\"
\"'F*F**$)F(\"\"%F*F**$)F(\"\"#F*F*F(F*F*F*" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%\"aG,<*$)%&alphaG\"#;\"\"\"F**$)F(\"#:F*F**$)F(\"#9F*
F**$)F(\"#8F*F**$)F(\"#7F*F**$)F(\"#6F*F**$)F(\"\"*F*F**$)F(\"\"(F*F**
$)F(\"\"'F*F**$)F(\"\"&F*F**$)F(\"\"#F*F*F(F*F*F*" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%\"aG,0*$)%&alphaG\"#;\"\"\"F**$)F(\"#:F*F**$)F(\"#9F*
F**$)F(\"\"*F*F**$)F(\"\"(F*F**$)F(\"\"%F*F*F(F*" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%\"aG,6*$)%&alphaG\"#;\"\"\"F**$)F(\"#9F*F**$)F(\"#5F*
F**$)F(\"\"(F*F**$)F(\"\"'F*F**$)F(\"\"&F*F**$)F(\"\"%F*F**$)F(\"\"$F*
F*F(F*F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,0*$)%&alphaG\"#;
\"\"\"F**$)F(\"#7F*F**$)F(\"#5F*F**$)F(\"\"*F*F**$)F(\"\")F*F**$)F(\"
\"(F*F**$)F(\"\"$F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,4*$)%&
alphaG\"#;\"\"\"F**$)F(\"#:F*F**$)F(\"#9F*F**$)F(\"#8F*F**$)F(\"\"*F*F
**$)F(\"\"(F*F**$)F(\"\"&F*F**$)F(\"\"$F*F*F*F*" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%\"aG,2*$)%&alphaG\"#;\"\"\"F**$)F(\"#:F*F**$)F(\"#9F*
F**$)F(\"#8F*F**$)F(\"#5F*F**$)F(\"\"(F*F**$)F(\"\"#F*F*F(F*" }}{PARA
11 "" 1 "" {XPPMATH 20 "6#>%\"aG,:*$)%&alphaG\"#;\"\"\"F**$)F(\"#:F*F*
*$)F(\"#8F*F**$)F(\"#7F*F**$)F(\"#5F*F**$)F(\"\"*F*F**$)F(\"\")F*F**$)
F(\"\"(F*F**$)F(\"\"'F*F**$)F(\"\"&F*F**$)F(\"\"%F*F**$)F(\"\"#F*F*" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#,:*$)%&alphaG\"#;\"\"\"F(*$)F&\"#:F(F
(*$)F&\"#8F(F(*$)F&\"#7F(F(*$)F&\"#5F(F(*$)F&\"\"*F(F(*$)F&\"\")F(F(*$
)F&\"\"(F(F(*$)F&\"\"'F(F(*$)F&\"\"&F(F(*$)F&\"\"%F(F(*$)F&\"\"#F(F("
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "\nA final check" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 18 "Roots(f(a)) mod 2;" }}{PARA 12 "" 1 ""
{XPPMATH 20 "6#7&7$,.*$)%&alphaG\"#;\"\"\"F**$)F(\"#6F*F**$)F(\"\"*F*F
**$)F(\"\")F*F**$)F(\"\"#F*F*F(F*F*7$,6*$)F(\"#:F*F**$)F(\"#8F*F**$)F(
\"#5F*F**$)F(\"\"'F*F**$)F(\"\"&F*F**$)F(\"\"%F*F**$)F(\"\"$F*F*F4F*F(
F*F*F*F*7$,6*$)F(\"#9F*F**$)F(\"#7F*F*F+F*F.F*F1F**$)F(\"\"(F*F*FBF*FH
F*F(F*F*F*F*7$,2FPF*F.F*F1F*FBF*FHF*FKF*F4F*F(F*F*" }}}{EXCHG {PARA 0
"" 0 "" {TEXT -1 23 "\nThus our polynomial is" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 5 "f(a);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,*\"\"\"F$*$)
%\"xG\"\"#F$F$*&,:*$)%&alphaG\"#;F$F$*$)F-\"#:F$F$*$)F-\"#8F$F$*$)F-\"
#7F$F$*$)F-\"#5F$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'FLF$F$
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 278 "\nFor the interested reader,
the Roots function uses a probabilistic method to compute the roots o
f a polynomial over a finite field. The idea is very nice. Consider \+
a polynomial in x over GF(p) where p is prime. We know from Fermat's \+
little theorem that the following is true" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 16 "'a^p = a mod p';" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/
)%\"aG%\"pG-%$modG6$F%F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "This \+
means that the polynomial x^p-x has roots 0,1,...,p-1 over GF(p), i.e.
it factors as follows" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "x^p-x = P
roduct( x-i, i=0..p-1 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&)%\"xG%
\"pG\"\"\"F&!\"\"-%(ProductG6$,&F&F(%\"iGF)/F.;\"\"!,&F'F(F)F(" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 428 "So suppose we are given a polynom
ial a(x) and we want to compute the roots. We can compute the product
of all the linear factors by computing the g = Gcd( a(x), x^p-x ). T
his Gcd calculation needs to be computed carefully if p is large. So \+
the next thing to do is to split g into the linear factors to get the \+
roots. Here comes the probabilistic part of the algorithm. We know t
hat we can write (assuming p is an odd prime)" }}{PARA 0 "> " 0 ""
{MPLTEXT 1 0 44 "x^p-x = x*(x^((p-1)/2)-1) * (x^((p-1)/2)+1);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&)%\"xG%\"pG\"\"\"F&!\"\"*(F&F(,&)F&
,&F'#F(\"\"##F)F/F(F(F)F(F(,&F,F(F(F(F(" }}}{EXCHG {PARA 0 "" 0 ""
{TEXT -1 66 "\nIgnoring the factor of x, consider now the following ca
lculations" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "'g1 = Gcd( a(x), x^((
p-1)/2)-1 ) mod p', 'g2 = Gcd(a(x), x^((p-1)/2)+1) mod p';" }}{PARA
11 "" 1 "" {XPPMATH 20 "6$/%#g1G-%$modG6$-%$GcdG6$-%\"aG6#%\"xG,&)F.,&
%\"pG#\"\"\"\"\"##!\"\"F5F4F4F7F4F2/%#g2G-F&6$-F)6$F+,&F0F4F4F4F2" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 686 "\nThese two calculations will wit
h good probability split the product of linear factors g into two part
s. The next idea is instead of computing these Gcd's, to choose an el
ement beta at random from GF(p) and compute using x = x+beta instead. \+
The polynomial (x+beta)^((p-1)/2)-1 will now be a product of differe
nt linear factors. The idea then is to do the above Gcd calculation f
or g1 with different beta's until you get a non-trivial splitting of g
. Repeat on each factor of g until g is completely split into linear \+
factors. That's the idea. One can show that the idea generalizes to \+
arbitrary finite fields GF(p^k) and a similar idea can be used to hand
le the special case p=2." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{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 0 0" 166 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1
2 33 1 1 }