{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 261 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 278 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE " " -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 48 "Factorizat ion of polynomials over finite fields." }{TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 28 "Properties of finite fields." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }{TEXT 257 42 "Definition: The characteristic of \+ a field:" }}{PARA 0 "" 0 "" {TEXT -1 83 "Let F be a field. Then there \+ is a unique non-zero (i.e. image <> \{0\}) homomorphism:" }}{PARA 0 " " 0 "" {TEXT -1 6 "Z -> F" }}{PARA 0 "" 0 "" {TEXT -1 230 "where Z is \+ the integers. The kernel is an ideal in Z. It is either the zero ideal (0) or it is of the form (p) where p is a prime number. In the first \+ case the characteristic of F is 0, in the second case it is the prime \+ number p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "When the characteristic is 0, then Q is a subfield of F." }}{PARA 0 "" 0 "" {TEXT -1 57 "When the characteristic is p, then Fp is a subf ield of F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 258 41 "Examples of fields with characteristic p:" }} {PARA 0 "" 0 "" {TEXT -1 28 "1) Fp field with p elements" }}{PARA 0 " " 0 "" {TEXT -1 96 "2) Fp[x]/(f) where f is irreducible in Fp[x]. This field has q=p^n elements where n=degree(f,x)." }}{PARA 0 "" 0 "" {TEXT -1 166 "3) Fp(x) The fraction field of Fp[x], i.e. all rational functions in x with coefficients in Fp. This field has characteristic p, but it has infinitely many elements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 259 8 "Lemma 1:" }}{PARA 0 "" 0 "" {TEXT -1 108 "Let F be a field of characteristic p (when we write p we will \+ mean that p is a prime number, p is not zero)." }}{PARA 0 "" 0 "" {TEXT -1 19 "Let a,b in F. Then:" }}{PARA 0 "" 0 "" {TEXT -1 23 " (a +b)^p = a^p + b^p." }}{PARA 0 "" 0 "" {TEXT -1 4 "and:" }}{PARA 0 "" 0 "" {TEXT -1 23 " (a*b)^p = a^p * b^p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 179 "Proof: (a+b)^p = add( binomial(p, i) * a^i * b^(p-i), i=0..p), and whenever 0 < i < p one has that p div ides binomial(p,i). The second statement is trivial, it holds for any \+ field." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }{TEXT 261 22 "Lemma 1, reformulated:" }}{PARA 0 "" 0 "" {TEXT -1 51 "Let F be a field of characteristic p. Then the map:" }}{PARA 0 "" 0 "" {TEXT -1 11 "Phi: F -> F" }}{PARA 0 "" 0 "" {TEXT -1 22 "given by : Phi(a) = a^p" }}{PARA 0 "" 0 "" {TEXT -1 18 "is a homomorphism." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 262 16 "Note on Lemma 1:" }}{PARA 0 "" 0 "" {TEXT -1 76 "In general wh en you have fields K and L and you have a non-zero homomorphism" }} {PARA 0 "" 0 "" {TEXT -1 11 "Phi: K -> L" }}{PARA 0 "" 0 "" {TEXT -1 16 "then Phi is 1-1." }}{PARA 0 "" 0 "" {TEXT -1 78 "Proof: If Phi is \+ non-zero then Phi(1)=1 because Phi(a)=Phi(1*a)=Phi(1)*Phi(a)." }} {PARA 0 "" 0 "" {TEXT -1 162 "Now if a,b in K and a<>b then there is a n s=1/(a-b) in K such that s*(a-b)=1. So then Phi(s*(a-b))=Phi(s)*( Ph i(a) - Phi(b) ) = Phi(1)=1, and so Phi(a) <> Phi(b)." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 263 24 "Another note on Lemma 1:" }}{PARA 0 "" 0 "" {TEXT -1 58 "So we see that the h omomorphism Phi: F -> F is always 1-1." }}{PARA 0 "" 0 "" {TEXT -1 188 "If F contains finitely many elements (like in example 1 and examp le 2, but not in example 3) we can conclude that Phi is also onto, so \+ then Phi is an automorphism. This Phi is called the: " }{TEXT 264 23 " Frobenius Automorphism." }}{PARA 0 "" 0 "" {TEXT -1 170 "When F contai ns infinitely many elements, like in example 3, then Phi need not be o nto. The image of Fp(x) under Phi is Fp(x^p) which is a subfield of Fp (x) with index p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 8 "Lemma 2:" }}{PARA 0 "" 0 "" {TEXT -1 37 "Let F be a field of characteristic p." }}{PARA 0 "" 0 "" {TEXT -1 31 "Then: \{ a in F | a^p=a \} = Fp." }}{PARA 0 "" 0 "" {TEXT -1 81 "In other words: the \+ set solutions of the polynomial f=x^p-x in the field F is Fp." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 292 "Proof: f has degree p, and so it can not have more than p solutions, because w henever you have a solution x=alpha, you can divide f by x-alpha, redu cing the degree of f by 1. Therefore we only need to show that all ele ments of Fp are solutions of f. We will give two different proofs of t hat:" }}{PARA 0 "" 0 "" {TEXT -1 318 "-> Proof #1: Let Fp* denote the \+ set of non-zero elements of Fp. We need to show that every element of \+ Fp* is a solution of f/x = x^(p-1)-1. Let a in Fp*. What we need to sh ow is that a^(p-1) = 1 (this is called Fermat's little theorem). Now F p* is a group under multiplication. Take the product of all elements o f Fp*:" }}{PARA 0 "" 0 "" {TEXT -1 30 "P = 1 * 2 * ... * (p-1) in Fp. " }}{PARA 0 "" 0 "" {TEXT -1 63 "P is not equal to 0. Now multiply all elements by a, so we get:" }}{PARA 0 "" 0 "" {TEXT -1 33 "Q = a^(p-1) * 1 * 2 * .. * (p-1)." }}{PARA 0 "" 0 "" {TEXT -1 208 "However, if yo u multiply elements of Fp* by a then you only permute them, in other w ords: multiplication by a is a 1-1 map from Fp* to Fp*. Therefore, P=Q , and so a^(p-1) must be 1, which completes the proof." }}{PARA 0 "" 0 "" {TEXT -1 253 "-> Proof #2: Phi is an automorphism of Fp. An auto morphism sends 0 to 0, sends 1 to 1, sends 1+1 to 1+1, sends 1+1+1 to \+ 1+1+1, so Fp has only one automorphism, namely the trivial automorphis m. Hence Phi(a)=a for all a in Fp, so a^p-a=0 for all a in Fp." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "restart; p:=17;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "Phi:=proc(a) global p; Power(a,p) m od p end;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(3);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Phi(3+4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(a);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "P hi(b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Phi(a+b);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Factor(x^4+3) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "r:=RootOf(%,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "a:=1+r+r^2+r^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(a);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "P hi(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(%);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 202 "Let K be a field and let f in K[x ]. By repeated factoring of f, adjoining a root of an irreducible fact or of f to K, factoring again, adjoining a root to the field, etc., we can find a field L such that" }}{PARA 0 "" 0 "" {TEXT -1 37 "1) L con tains all roots alpha.i of f." }}{PARA 0 "" 0 "" {TEXT -1 84 "2) L is \+ generated over K by the roots of f, so L = K(alpha1, alpha2, ... , alp ha.n)." }}{PARA 0 "" 0 "" {TEXT -1 29 "Such a field L is called the " }{TEXT 265 16 "splitting field " }{TEXT -1 12 "of f over K." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 100 "So a splitting field always exists, for any field K and for any polynomial f in K[x] . One can prove:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 266 12 "Propo sition:" }}{PARA 0 "" 0 "" {TEXT -1 141 "The splitting field of f over K is unique up to isomorphism. That is, if L1 and L2 satisfy the cond itions 1) and 2) then they are isomorphic." }}{PARA 0 "" 0 "" {TEXT -1 16 "Sketch of proof:" }}{PARA 0 "" 0 "" {TEXT -1 865 "Take a splitt ing field L. We construct a splitting field using the repeated factori zation, and we need to show that the field we are construct is isomorp hic to L. During the construction of our splitting field, we extend ou r field in every step with a root alpha.i. During this process, we can also construct a homomorphism from the field we're extending every ti me to the field L. This is done by sending the element alpha.i by whic h we extend our field to a suitable element of L. Namely, if alpha.i i s a root of the irreducible factor g of f (irreducible over the field \+ we've constructed up to that point), then compute the roots of g in L \+ and send alpha.i to one of those roots. When we've completed our const ruction of a splitting field, we've obtained a homomorphism, which we then prove to be an isomorphism, from the field we've constructed to \+ the field L." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "Let p be a prime number and let n be a positive integer." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 267 29 "Definition of Fq where q= p^n." }}{PARA 0 "" 0 "" {TEXT -1 97 "The field Fq where q=p^n is defin ed as the splitting field of the polynomial f=x^(p^n)-x over Fp." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 268 31 "Proposition: Fq has q elements." }}{PARA 0 "" 0 "" {TEXT -1 130 "Proof: Let Phi^n denote the automorphism of Fq obtained by applyi ng the Frobenius automorphism Phi n times. So Phi^n(a) = a^(p^n)." }} {PARA 0 "" 0 "" {TEXT -1 142 "Fq is of the form Fp(alpha1, alpha2, ... ) where each of the alpha.i is a root of f. So each of the alpha.i is invariant under Phi^n, that is:" }}{PARA 0 "" 0 "" {TEXT -1 60 "Phi^n (alpha.i) = alpha.i for all generators alpha.i of Fp." }}{PARA 0 "" 0 "" {TEXT -1 405 "But then all polynomials in the alpha.i are also in variant under the automorphism Phi^n, so all elements of Fq are invari ant under Phi^n. So every element of Fq is a root of f, and since Fq w as the splitting field we know that every root of f is also an element of Fq. Now f is square-free (note that diff(f,x)=-1, so \"Gcd(f, diff (f,x)) mod p\" = 1) so f has precisely q=p^n roots. Hence Fq has q ele ments." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "Let q1=p^n and q2=p^m, and let d=igcd(n,m). Let q3=p^d." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }{TEXT 270 55 "Proposition: The intersection of F .q1 and F.q2 is F.q3." }}{PARA 0 "" 0 "" {TEXT -1 39 "Proof: This foll ows from the fact that:" }}{PARA 0 "" 0 "" {TEXT -1 75 "Phi^n(a) = a a nd Phi^m(a) = a is true if and only if Phi^d(a) = a is true." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 271 65 "Corollary: F.q1 is a subfield of F.q2 if and only if n divides m." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "Le t again q = p^n, with p prime and n a positive integer." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 269 69 "Proposition: up to isomorphism, Fq i s the only field with q elements." }}{PARA 0 "" 0 "" {TEXT -1 261 "Pro of: Let L be a field with q elements. Let a be a non-zero element of L . The same proof as proof # 1 in lemma 2 shows that a^(q-1)=1. Therefo re every element of L is a root of x^q-x, and we see that L is the spl itting field of x^q-x, so L is isomorphic to Fq." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 272 13 "Propositi on: " }{TEXT -1 89 "For every positive integer n there exists an irred ucible polynomial of degree n in Fp[x]." }}{PARA 0 "" 0 "" {TEXT -1 819 "Sketch of proof: Let q=p^n. Now Fq has p^n elements. For every in teger d that divides n we have a subfield F.p^d of Fq, and this is a c omplete list of subfields. One can count (one can find a formula using the principle of inclusion-exclusion) how many elements alpha in Fq a re element of some proper subfield of Fq. This number is smaller than \+ p^n. So there exists an alpha in Fq that is not an element of any prop er subfield of Fq, and this is equivalent to saying that Fp(alpha) is \+ not a proper subfield of Fq, so Fp(alpha)=Fq. Take the polynomial f in Fp[x] of smallest degree such that f(alpha)=0. Then f is irreducible \+ and Fp(alpha) is isomorphic to Fp[x]/(f). So the degree of f must be e qual to the dimension of Fq as an Fp-vector space, and since Fq has p^ n elements this dimension must be n, so degree(f,x)=n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 273 157 "Let q=p^n. If you want to compute in Fq, then you need to find an irreduc ible polynomial f in Fp[x] of degree n, and then Fq will be isomorphic to Fp[x]/(f)." }}{PARA 0 "" 0 "" {TEXT -1 60 "Such a polynomial can b e found with the following procedure:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 253 "irreducible_poly:=proc(n,x,p)\n local f;\n f:=x^ n;\n while not Irreduc(f) mod p do\n # Take a random monic poly nomial of degree n\n f:=x^n+randpoly(x,degree=n-1,coeffs=rand(0.. p-1))\n od;\n # Now f has degree n and is irreducible.\n f\nend; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "p:=13;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "f:=irreducible_poly(5,x,p);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "g:=irreducible_poly(5,x,p);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(f) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Factor(f, RootOf(g)) mod p;" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 42 "Intermezzo: Short sketch of Galoi s theory." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "Let q=p^n. The set of all automorphisms of Fq is:" }}{PARA 0 "" 0 "" {TEXT -1 41 "G = \{1, Phi, Phi^2, Phi^3, .., Phi^(n-1)\}" }}{PARA 0 "" 0 "" {TEXT -1 674 "Here 1 stands for the identity automorphism. N ow G is a cyclic group generated by the Frobenius Automorphism Phi. Wh en H is a subgroup of G (since G is cyclic the only possible subgroups are the cyclic groups generated by Phi^d where d divides n) then Fq^H denotes the set of all a in Fq such that a is invariant under all ele ments of H. When H is generated by Phi^d, then Fq^H is the set of all \+ a in Fq for which Phi^d(a)=a. Now this gives a 1-1 correspondence betw een the subgroups of the group Galois group G (the group of all automo rphisms of Fq), and the subfields of Fq. If H1 and H2 are subgroups of G, and if H1 is a subgroup of H2 then Fq^H2 is a subfield of Fq^H1." }}{PARA 0 "" 0 "" {TEXT -1 433 "Something similar holds for Q as well. If f is a polynomial in Q[x], and L is the splitting field of f over \+ Q, then one can look at the group G of all automorphisms of L. Then th ere is a 1-1 correspondence between the subgroups of G and the subfiel ds of L. The trivial group \{1\} corresponds to L, and the full Galois group G corresponds to Q. This means that if a in L, and a is invari ant under any isomorphism of L, then a is in Q." }}{PARA 0 "" 0 "" {TEXT -1 80 "This 1-1 correspondence between subgroups of G and subfie lds of L is called the " }{TEXT 274 22 "Galois correspondence," } {TEXT -1 35 " it is what Galois theory is about." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "Example:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f:=x^5+2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "galois(f,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 128 "This means that the Galois group has 20 elements, and is isomorphic t o a permutation group generated by (1 4 2 3) and (2 5 3 4)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 169 "The degree of \+ the splitting field equals the number of elements of the Galois group. So, to find all roots of f we need an algebraic extension of degree 2 0. Let's check:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(f );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "r:=RootOf(%);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "evala(Factor(f,r))/(x-r);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "r2:=RootOf(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "evala(Factor(f,\{r,r2\}));" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 254 "We see that Q(r,r2) contains all \+ the roots, and Q(r,r2) is indeed an extension of degree 5*4=20 of Q. W hat are some of the subfields? Well, the discriminant is a quadratic e xpression in terms of the roots. So sqrt(discriminant) is in the split ting field." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "ifactor(disc rim(f,x));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 359 "So Q( sqrt(5) ) is one of the subfields of L=Q(r,r2). This subfield must then correspond to a subgroup of G. It corresponds to the group H which consists of a ll automorphisms Psi: L -> L for which Psi(a)=a for all a in Q( sqrt(5 ) ). Since Q( sqrt(5) ) is an extension of Q of degree 2, H will be a \+ subgroup of G with index 2, so H will have 20/2=10 elements. " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "evala(Factor(x^2-5, \{r,r2\} ));" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 49 "Zero divisors and nilpo tent elements of K[x]/(f)." }}{PARA 0 "" 0 "" {TEXT -1 16 "Let R be a \+ ring." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 275 11 "Definition:" }} {PARA 0 "" 0 "" {TEXT -1 87 "An element a in R is called a zero-diviso r if a<>0 and there is a b<>0 such that a*b=0." }}{PARA 0 "" 0 "" {TEXT -1 96 "An element a in R is called nilpotent if a<>0 and there i s a positive integer n such that a^n=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "Let f be a polynomial in K[x]. Consi der the ring R=K[x]/(f)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 199 "Let f = f1^e1 * f2^e2 * f3^e3 *... * f.n^e.n be a factorization of f, so f1,..,fn are the irreducible factors of f, and e1..e.n are the multiplicities. Then, by the Chinese Remainder Theore m we have:" }}{PARA 0 "" 0 "" {TEXT -1 52 "R isomorphic to K[x]/(f1^e1 ) * ... * K[x]/(f.n^e.n)." }}{PARA 0 "" 0 "" {TEXT -1 116 "Under this \+ isomorphism, an element a in R corresponds to a sequence (a.1, a.2, .. , a.n) where a.i in K[x]/(f.i^e.i)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 400 "An element a in R is zero or nilpotent \+ if and only if a.i is zero or nilpotent for each i. This happens if an d only if each a.i is divisible by f.i, so a is zero or nilpotent if a nd only if a is a multiple of f1 * f2 * .. * fn. So there are nilpoten t elements if and only if there are non-zero multiples of f1 * .. * fn , and this happens if and only if at least one of the e.i is > 1. So w e conclude:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 276 69 "Lemma 1: R has no nilpotent elements if and only if f is square-free." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 236 "Given a polyno mial in f, we can always compute a square-free factorization, f=f1^1 * f2^2 * ..., where each of the f.i is squarefree. Note: have you finis hed your square-free factorization assignment for Fp[x]. Please turn i n your work." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 277 59 "Lemma 2: R has zero-divisors if and only if f i s reducible." }}{PARA 0 "" 0 "" {TEXT -1 304 "Proof: If f is not squar e-free then R has nilpotent elements, and these are zero-divisors. So \+ we may assume that f is square-free. So f = f1*f2*..*fn where each of \+ the f.i are irreducible and has multiplicity 1 in f (so f/f.i is not d ivisible by f.i). In that case R is isomorphic to a product of fields: " }}{PARA 0 "" 0 "" {TEXT -1 35 " R isomorphic to K1 * K2 * .. * Kn" }}{PARA 0 "" 0 "" {TEXT -1 373 "where K.i is the field K[x]/(f.i). Let a in R correspond to (a.1,..,a.n) under the Chinese remainder theorem , where a.i in K.i. Now the zero-divisors of R is the set of all non-z ero a (that means that at least one of the a.i is non-zero), for which at least one of the a.i=0. So we easily see that such elements exist \+ if and only if n>1, i.e. if and only if f is reducible." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 162 "The proof also show s that an element a in R=K[x]/(f) is a zero-divisor if and only if gcd (a,f) is a non-trivial factor of f (here we view a as a polynomial in \+ x)." }}{PARA 0 "" 0 "" {TEXT -1 170 "Note that gcd(a,f) is trivial mea ns that either gcd(a,f)=f, in which case a is zero in R, or gcd(a,f)=1 , in which case we have s*a+t*f=1, so s*a equals 1 in R. So we see:" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 278 39 "Lemma 3: If a is an element of R, then:" }}{PARA 0 "" 0 "" {TEXT 285 107 "a is a zero-divisor if and only if gcd(a,f) is non-triv ial, if and only if a<>0 and is not invertible in R." }}{PARA 0 "" 0 " " {TEXT -1 68 "Note: a is invertible means that there is an s in R suc h that s*a=1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 24 "So we see the following:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }{TEXT 279 95 "Finding a non-trivial factorization of f is equivalen t to finding a zero-divisor in R=K[x]/(f)." }{TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 22 "Factorization in Fp[x]" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 232 "We will now focus on t he case K=Fp, we will look at how to factor polynomials f in Fp[x]. Af ter using the square-free factorization algorithm we may assume that f is square-free. So, R=Fp[x]/(f) is isomorphic to a product of fields: " }}{PARA 0 "" 0 "" {TEXT -1 41 "R isomorphic to K1 * K2 * .. * Kn \+ (1)" }}{PARA 0 "" 0 "" {TEXT -1 23 "where K.i = Fp[x]/(f.i)" }}{PARA 0 "" 0 "" {TEXT -1 345 "and where f=f1* .. * fn is a factorization of \+ f into irreducible factors. Note that, even though the isomorphism in \+ (1) exists, we can not directly compute with it because we don't know the f.i, the K.i, we even don't know the number n of irreducible fact ors. But what we can compute with is the Frobenius homomorphism Phi, t hat sends a to a^p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 195 "Let a in R be non-zero. Now a is not a zero divisor be cause we assume that f is squarefree. So a^i <> 0 for any positive int eger i, in particular a^p<>0, in other words Phi(a)<>0. So we see that :" }}{PARA 0 "" 0 "" {TEXT -1 11 "Phi: R -> R" }}{PARA 0 "" 0 "" {TEXT -1 212 "has kernel Ker(Phi) = \{a in R | Phi(a)=0\} = \{0\}, so \+ Phi is not only a homomorphism, it is also 1-1 so it is an isomorphism from R to R (an isomorphism from a ring to itself is called an automo rphism), called the " }{TEXT 281 22 "Frobenius automorphism" }{TEXT -1 9 ". And, if" }}{PARA 0 "" 0 "" {TEXT -1 33 "a corresponds to (a1, \+ ..,an) then" }}{PARA 0 "" 0 "" {TEXT -1 46 "Phi(a) corresponds to (Phi (a1), ..., Phi(an))." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 142 "So: a is invariant under Phi if and only if all a.i ar e invariant under Phi, and we've seen that happens if and only if all \+ a.i are in Fp. Let" }}{PARA 0 "" 0 "" {TEXT -1 159 "S = \{a in R | Phi (a)=a\} = Ker( Phi-1 ) where 1 stands for the identity map from R to R . Then the Chinese Remainder Theorem gives the following correspondenc es:" }}{PARA 0 "" 0 "" {TEXT -1 28 "R <----> K1 * K2 * .. * Kn" }} {PARA 0 "" 0 "" {TEXT -1 30 "S <----> Fp * Fp * ...* Fp" }}{PARA 0 "" 0 "" {TEXT -1 172 "So S = Ker(Phi-1) corresponds under the Chines e Remainder theorem to a subring Fp * .. * Fp of K1 * K2 *.. * Kn. Thi s ring has dimension n as an Fp-vector space. So we see:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 280 28 "Le mma 4: n = dim Ker(Phi-1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Time for an example:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "f:=x^7+x^2+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "Phi:=proc(a ) global f,x,p; Powmod(a,p,f,x) mod p end;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 7 "Phi(1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "Phi(x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Phi(x+1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Phi(x^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Rem(x^10,f,x) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "Phi(x^3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Rem(x^15,f,x) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 167 "Sinc e R is a finite set, and Phi is 1-1 because f is square-free, if we ju st keep on applying Phi, starting with the element x, eventually we wi ll have to see x again." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " Phi(x); # 1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 2 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 4" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%) ; # 8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Phi(%); # 9" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "Phi(%); # So Phi^10(x)=x, so Phi^10 is the identity on R, the order of Phi is 10." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 712 "If f were irreducible, then R=Fp[x]/(f) \+ would be isomorphic to Fq where q=p^7, and then Phi^7 would be the ide ntity. But we see that Phi^7(x) <> x, we have Phi^10(x)=x. Since every element of Fp[x]/(f) can be presented as a polynomial in x, we see th at Phi^10(a)=a for every a in R, so Phi is an automorphism of R of ord er 10. That the order is 10 can only be explained when f is a product of a polynomial of degree 2 and a polynomial of degree 5, because the n R is isomorphic to F.p^2 * F.p^5. Now Phi has order 2 on F.p^2, and \+ Phi has order 5 on F.p^5 (that means Phi^5 is the identity on F.p^5 a nd Phi^i is not the identity for 1<=i<5). Since iclm(2,5)=10 that woul d make the order of Phi equal to 10 on R.." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 348 "So n must be 2, there are 2 i rreducible factors of f in Fp[x]. So n = dim Ker(Phi-1) = 2. How to co mpute that kernel? Well, R is a ring, it is also an Fp vector space of dimension 7. And Phi-1 is an Fp-linear map from R to R. So, when we c hoose a basis (we take: x^0, x^1, .., x^6) of R as an Fp-vector space, then Phi-1 corresponds to a matrix A." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "basis:=[seq(x^i,i=0..degree(f,x)-1)];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "The images of these basis elements under \+ the map Phi-1 are:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "image s_basis:=map(a -> Phi(a)-a mod p, basis);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 107 "Now write these images as column vectors on the given ba sis, and construct the matrix A with these columns:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "A:=matrix(degree(f,x),degree(f,x), [seq(s eq( coeff(i,x,j), i=images_basis), j=0..degree(f,x)-1)] );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 123 "Now determine a basis for Ker(Phi-1), wh ich corresponds to a basis of Ker(A). Note that Nullspace means the sa me as kernel." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Nullspace( A) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "Translate these vect ors back to polynomials (use again the basis x^0, x^1, ..). Then we ge t:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "basis_ker_Phi_minus_1 := \{seq(add(i[j+1]*x^j,j=0..degree(f,x)-1), i=%)\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n:=nops(%);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 17 "b1, b2 := op(%%);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 13 "Phi(b1) = b1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "Phi(b2) = b2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "r:=Rem(randpoly([b1,b2]),f,x) mod p; # random element in S=Fp[ b1,b2]" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Phi(r); # = r" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "r is an element of S, and so it \+ is an Fp-linear combination of b1 and b2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 117 "We've mentioned before that Phi^1 0 is the identity on R. Let's check that in terms of matrices. The mat rix of Phi is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "images_ba sis_under_Phi:=map(Phi,basis);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 118 "Phi_matrix:=matrix(degree(f,x),degree(f,x), [seq(seq( coeff(i ,x,j), i=images_basis_under_Phi), j=0..degree(f,x)-1)] );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "map(i -> i mod p, evalm(Phi_matrix^ 10));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 491 "Note that R is isomorph ic to F.p^2 * Fp^5. The kernel of Phi-1 is S which corresponds under t he Chinese Remainder Theorem to Fp * Fp, has dimension 2 over Fp. The \+ kernel of Phi^2-1 corresponds to F.p^2 * Fp, has dimension 3 over Fp, \+ and the kernel of Phi^5-1 corresponds to Fp * F.p^5, which has dimensi on 6 over Fp. We can check all of these statements by computing the ma trices of Phi^2-1 and Phi^5-1 in the same way as we did above, and the n computing the Nullspace, but we won't do that." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 376 "After these example comp utations, we'll focus again on what our goal was, i.e. to factor the p olynomial f, which we assume to be square-free. So what we're looking \+ for are zero-divisors. So we search for elements a, that under the Chi nese Remainder theorem correspond to (a.1 , a.2 ,.., a.n) such that at least one a.i=0 and at least one a.i <> 0. We do this in several step s:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "R \+ <----> K1 * K2 * .. * Kn" }}{PARA 0 "" 0 "" {TEXT -1 129 "Now compute \"Nullspace(A) mod p\" where A is the matrix of Phi-1, and we find a \+ basis as an Fp-vector space of the subring S of R." }}{PARA 0 "" 0 "" {TEXT -1 30 "S <----> Fp * Fp * ...* Fp" }}{PARA 0 "" 0 "" {TEXT -1 162 "If n=dim(Ker(Phi-1))=dim(Nullspace(A))=1 we can stop, f is irr educible. But if n>1 we have still gained something by computing S=Ker (Phi-1), namely the following:" }}{PARA 0 "" 0 "" {TEXT -1 311 "We are searching for zero divisors in R. The method of finding zero divisors starts by taking a random element a in R. But it's not so easy to dea l with such an a because the a.i are in K.i, so the a.i could be in di fferent fields K.i (the K.i are different when the degrees of the fact ors of f are different).\n" }}{PARA 0 "" 0 "" {TEXT -1 344 "Now we wil l not pick a random element in R, but a random element in S that is no t in Fp (so an element a in S for which has(a,x)=true). Then a corresp onds to (a.1 , a.2, .., a.n) but now all the a.i are in the same field , namely they are in Fp. Furthermore: not all a.i are the same, becaus e then a would be in Fp. Now we distinguish two cases:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 286 7 "Case 1)" }{TEXT -1 37 " p is a small prime number, e.g. p=2." }}{PARA 0 "" 0 "" {TEXT -1 109 "Then all the a.i in Fp can be represented by small integers (in t he range 0..p-1). Now consider the elements:" }}{PARA 0 "" 0 "" {TEXT -1 32 "a <-----> (a1, a2, .., an)" }}{PARA 0 "" 0 "" {TEXT -1 43 "a+1 <-----> (a1 + 1, a2 + 1, ..., an + 1)." }}{PARA 0 "" 0 "" {TEXT -1 3 "..." }}{PARA 0 "" 0 "" {TEXT -1 41 "a+p-1 <----> (a1 + p-1 , ..., an + p-1)." }}{PARA 0 "" 0 "" {TEXT -1 69 "Now there must be \+ zero-divisors amongs these elements a, a+1, a+2,..." }}{PARA 0 "" 0 " " {TEXT -1 235 "Why, well, take a.i such that not all a.j equal a.i. S uch a.i exists because otherwise a would be in Fp. Let b=-a.i mod p. T hen a+b would be (*,.,*,0,*,..*) where all * are elements in Fp, and n ot all of them are zero. So, when we take" }}{PARA 0 "" 0 "" {TEXT -1 19 "g1=Gcd(a,f) mod p; " }}{PARA 0 "" 0 "" {TEXT -1 20 "g2=Gcd(a+1,f) \+ mod p;" }}{PARA 0 "" 0 "" {TEXT -1 3 "..." }}{PARA 0 "" 0 "" {TEXT -1 24 "gp=Gcd(a+(p-1),f) mod p;" }}{PARA 0 "" 0 "" {TEXT -1 483 "then we \+ are certain to find a non-trivial factorization of f, namely g1*g2*..* gp. Now remove those g.i that are equal to 1. It could be that we then have found n factors, in which case we're done. Or we may have found \+ less than n factors (it is certain to have at least 2 factors). Then w e can take other elements of S to further factor the g.i in the same w ay (or we can just apply recursion on the g.i). We know when we can st op, because we know how many irreducible factors f has." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "b1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "b2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "p;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 38 "if has(b1,x) then a:=b1 else a:=b2 fi;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 119 "Now has(a,x)=true, so a is not in Fp, so a corresponds to (a1,..,an) where the a.i are in Fp, and are n ot all the same." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "P:=\{\} ; for i from 0 to p-1 do g:=Gcd(a+i,f) mod p; if g<>1 then P:=P union \+ \{g\} fi od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 288 "We see that we'v e found 2 factors of f, and since we already knew that dim(Ker-1)=2 we 're done. The method in case 1) works well when p is small, say p=2 or 3. But when p is large, say p=nextprime(10^10), then this is of cours e not very fast. In that case we'll have to do something else." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 287 8 "Case 2) \+ " }{TEXT -1 448 " p is not small. Take again a random a in S that is n ot in Fp. So a corresponds to (a1,a2,..,an) where a.i in Fp, where not all a.i are the same because a is not in Fp. If p is large then it is not likely that any of the a.i is 0 (if at least one of the a.i=0 the n we are lucky, because not all a.i are zero and so \"Gcd(a,f) mod p \" would give us a non-trivial factor of f). Now assume that we are no t lucky, so all a.i are non-zero, so Gcd(a,f)=1." }}{PARA 0 "" 0 "" {TEXT -1 150 "Then: a^(p-1) corresponds to (a1^(p-1), ..., an^(p-1)) a nd by Fermat's little theorem this is (1,1,..,1) so a^(p-1)=1. Let's c heck (note that a in S):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "while Gcd(a,f) mod p <> 1 do a:=a+1 mod p od; # Make sure Gcd(a,f)=1 " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "a;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Powmod(a,p-1,f,x) mod p;" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 249 "Now assume that p<>2, the case p=2 is handled in \+ Case 1) that handles small primes. So p-1 is even. And a.i (which we a ssumed non-zero) raised to the power p-1 is 1. Consider a.i^( (p-1)/2 \+ ). The square of this is 1, so the number itself is 1 or -1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "Let Fp* be the \+ set of non-zero elements of Fp, and let p>2. Then" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 282 58 "Lemma 5: Let p>2. Half of the elements of Fp* are squares." }}{PARA 0 "" 0 "" {TEXT -1 280 "Proof: Fp* is a gro up under multiplication. Consider the group homomorphism: k -> k^2 fr om Fp* to Fp*. Since the kernel of this group homomorphism is the gro up \{1, -1\} which has 2 elements, it follows that half of the set Fp* is in the image, so the image has (p-1)/2 elements." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 189 "Note: if c=d^2 is a \+ square in Fp*, then d^(p-1)=1, so we see that c is a solution of x^( ( p-1)/2 ) - 1. And since this equation has degree (p-1)/2, there are at most (p-1)/2 solutions, so:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 283 87 "Lemma 6: Let p>2. The squares in Fp* are the roots of the poly nomial x^( (p-1)/2 ) - 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 185 "If c is not a square, then c is not a root of tha t polynomial, so c^( (p-1)/2 ) is not 1, and raised to the power 2 it \+ becomes 1, so then c^( (p-1)/2 ) must be -1. So the conclusion is:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 284 107 "Let p>2 and take a rando m element c in Fp*. Then c^( (p-1)/2 ) is 1 with 50% chance and -1 wit h 50% chance." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 173 "Consider again the random element a in S, a not in Fp. I f Gcd(a,f) mod p does not give us a non-trivial factor of f, i.e. if a ll a.i are non-zero, then for each a.i we have:" }}{PARA 0 "" 0 "" {TEXT -1 63 "(a.i )^( (p-1)/2 ) is 1 with 50% chance and -1 with 50% c hance." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 14 "So we compute:" }}{PARA 0 "" 0 "" {TEXT -1 19 "b := a^( (p-1)/2 )." } }{PARA 0 "" 0 "" {TEXT -1 66 "Then b corresponds to an element (-1 or \+ 1, -1 or 1, ..., -1 or 1)." }}{PARA 0 "" 0 "" {TEXT -1 201 "If now b i s -1 or 1, then we're unlucky, all entries are the same, in which case we take another random a in S, a not in Fp. Otherwise, some of the en tries will be 1 and some will be -1. We have that:" }}{PARA 0 "" 0 " " {TEXT -1 46 "b-1 corresponds to (-2 or 0, -2 or 0, ...) and" }} {PARA 0 "" 0 "" {TEXT -1 43 "b+1 corresponds to (0 or 2, 0 or 2, ... \+ )." }}{PARA 0 "" 0 "" {TEXT -1 112 "Now where b-1 has a 0, b+1 has a n on-zero, and where b+1 has a 0, b-1 has a non-zero. Hence, if f is mon ic then:" }}{PARA 0 "" 0 "" {TEXT -1 30 " f = Gcd(b-1,f) * Gcd(b+1,f) ." }}{PARA 0 "" 0 "" {TEXT -1 75 "This is a non-trivial factorization \+ of f if and only if b is not in \{1,-1\}." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 6 "b1,b2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 824 "do\n a:=rand(0..p-1)()*b1+rand(0..p-1)()*b2 mod p;\n if not has(a,x) then\n lprint(\"a is a constant, so all a.i are the same\");\n # We'll have to take another random a, so we \+ go\n # back to the beginning of the loop with the\n \+ # following command:\n next\n fi;\n g:=Gcd(a,f) mod p;\n if g<>1 then\n lprint(\"Lucky case, some of the a.i are zero\");\n P:=\{g, Normal(f/g) mod p\};\n # exit \+ the loop:\n break\n fi;\n b:=Powmod(a,(p-1)/2, f,x) \+ mod p;\n if b^2 mod p = 1 then\n lprint(\"Unlucky case, b =1 or b=-1\");\n else\n lprint(\"Some of the b.i are 1, s ome are -1\");\n P:=\{Gcd(b-1,f) mod p, Gcd(b+1,f) mod p\};\n \+ # We found a non-trivial factorization, so exit the loop:\n \+ break\n fi\nod;" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 10 "C onjugates" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 288 11 "Definition:" }}{PARA 0 "" 0 "" {TEXT -1 75 "Let K \+ be a subfield of L, and assume that the degree of L over K is finite. " }}{PARA 0 "" 0 "" {TEXT -1 268 "Let alpha be an element of L. Since \+ the dimension of L as a K-vector space is finite, we have that alpha^0 , alpha^1, alpha^2, ... is linearly dependent over K, so alpha is a ro ot of some polynomial f in K[x], and if we take f with minimal degree \+ then f is irreducible." }}{PARA 0 "" 0 "" {TEXT -1 100 "Now we can tak e an algebraic extension of L that contains all roots alpha.1, .., alp ha.n of f. Then:" }}{PARA 0 "" 0 "" {TEXT -1 66 "alpha.1, ..., alpha.n (note that alpha is among these) are called " }{TEXT 289 31 "the conj ugates of alpha over K." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 290 12 "Proposition:" }}{PARA 0 "" 0 "" {TEXT -1 178 "If al pha in L, and Psi: L -> L is an automorphism of L over K (that means t hat Psi acts as the identity on K, so Psi(a)=a for all a in K) then Ps i(alpha) is a conjugate of alpha." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 176 "In other words: if f in K[x] is irreduci ble, if alpha in L and L is an algebraic extension of K, and if Psi is an automorphism of L over K, then Psi(alpha) is also a root of f." }} {PARA 0 "" 0 "" {TEXT -1 255 "Proof: If f = sum a.i * x^i, then f(al pha)=sum a.i * x^i = 0. Now Phi(a.i)=a.i because a.i in K and Phi is a n automorphism of L over K. So 0=Phi(0)=Phi( f(alpha) ) = sum Phi(a.i) * Phi(alpha)^i = sum a.i * Phi(alpha)^i = 0, so Phi(alpha) is a root \+ of f." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "E xample:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "p:=nextprime(10^1 0);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "f:=irreducible_poly( 5,x,p);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(f) mod p; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "alias(R=RootOf(f,x));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "Expand(subs(x=R,f)) mod p ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "R2:=Phi(R);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "R3:=Phi(R2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "R4:=Phi(R3);" }{XPPMATH 20 "6#>%#R4 G,,*$)%\"RG\"\"%\"\"\"\"+e!f3b'*$)F(\"\"$F*\"+'RM2$\\*$)F(\"\"#F*\"+'y f@g&F(\"*(f&*[p\"+f)>vg'\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "R5:=Phi(R4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "Phi( R5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "seq(Expand(subs(x=i ,f)) mod p , i=[R,R2,R3,R4,R5]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "Expand( mul(x-i,i=[R,R2,R3,R4,R5]) ) mod p;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 21 "Complexity estimates." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "The implementation of Phi:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "Phi:=proc(a) globa l f,x,p; Powmod(a,p,f,x) mod p end;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 193 "What if p=nextprime(10^20)? How to comp ute a^p modulo f (and modulo p) without doing 10^20 multiplications? T his can be done in O( log(p) ) operations in Fp[x]/(f) with the follow ing algorithm:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 297 "my_Powmod :=proc(a,n::nonnegint, p,f,x)\n global count_number_operations;\n co unt_number_operations:=count_number_operations+1;\n if n<4 then\n \+ Rem(a^n,f,x) mod p\n elif type(n,even) then\n Rem(procname(a,n /2,p,f,x)^2,f,x) mod p\n else\n Rem(procname(a,n-1,p,f,x)*a,f,x) mod p\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "my_p owmod:=proc()\n global count_number_operations;\n count_number_ope rations:=0;\n my_Powmod(args)\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "p:=nextprime(10^20);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=x^3+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(f) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "a: =2*x+3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "my_powmod(a,2,p, f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "my_powmod(a,3,p,f, x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "phi_a:=my_powmod(a,p ,p,f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "count_number_op erations;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "phi_phi_a:=my_ powmod(phi_a,p,p,f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "p hi_phi_phi_a:=my_powmod(phi_phi_a,p,p,f,x);" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 69 "We see that applying Phi does not take 10^20 operations , but only 95." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 578 "Of course the cost of each operation depends on n:=degre e(f,x). Also, if p is very large (say 100 digits or more) then the ope rations on the coefficients in Fp will also get slower. We will ignore this effect in the complexity estimate, we will just count every oper ation in Fp as having cost O(1). Then, the cost of Phi(a) is log(p) op erations, each which involves multiplying two polynomials of degree n \+ (with the basic method that is O(n^2)). Then the Remainder, that has c omplexity O(n^2) as well. So computing Phi of an element costs O(log(p )) * (O(n^2)+O(n^2)), which is:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 16 "O(log(p) * n^2)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "And we have to apply Phi \+ on: x^i, i=0..n-1, so then the cost is:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 21 "(*) O(log(p) * n^3)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 408 "The linear algebra \+ part (the Nullspace) can be done in O(n^3) operations over Fp, so that doesn't change the complexity. Then we have to do gcd computations (o rder n^2), about 1 or 2 (or more, if we often have bad luck in picking the random element in the set S) for every factor (there are at most \+ n), so that's about O(n^3). So we find that (*) is the complexity of f actoring f in Fp[x] with degree(f,x)=n." }}{PARA 0 "" 0 "" {TEXT -1 395 "One remark about this complexity: this is not an upperbound compl exity, it is an estimate of the *expectation value* of the computation time. The computation time can in principle not be bounded because th e algorithm uses randomness, and very low probability it will pick the wrong random element many times in a row. In practise this of course \+ doesn't happen, but theoretically it is a concern." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 29 "Distinct degree factorization" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 95 "Let f in Fp[x]. We will assume f is square-free, but for the most part it is not relevant her e." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 14 "Two questions:" }}{PARA 0 "" 0 "" {TEXT -1 80 "1) What are the degrees d1 < d2 < d3 < .. < dk, of the irreducible factors of f?" }}{PARA 0 "" 0 "" {TEXT -1 92 "2) Let f.d be the product of all irreducible factors of f of degree d. How to determine f.d?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "Note: if f is square-free then" }} {PARA 0 "" 0 "" {TEXT -1 30 " f = f.d1 * f.d2 * ... * f.dk." }}{PARA 0 "" 0 "" {TEXT -1 117 "If f is not square-free, then the right hand s ide is a proper factor of f, because the right-hand side is squarefree ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 205 "Of \+ course, both 1) and 2) can both be handled by the factorization algori thm given before, but we will see that 1) and 2) are easier than the g eneral factorization algorithm. Namely, we have the following:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "If g is a n irreducible polynomial of degree d', then:" }}{PARA 256 "" 0 "" {TEXT 291 137 "g divides x^(p^d)-x if and only if the roots of g are i n F.p^d if and only if F.p^d' is a subfield of F.p^d, if and only if d ' divides d." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "So, if f in Fp[x] then:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 97 "Gcd(f, x^(p^d) - x) = product of all irr educible factors g of f for which degree(g,x) divides d." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 193 "So, if d1 is the \+ lowest degree of any irreducible factor of f, then: f.d1 (defined abov e) can be determined by this gcd. Then we can divide f by it and searc h for the factors of degree d2, etc." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 479 "distinct_degree_factorization:=proc(f,x,p)\n local g,F,d,res;\n F:=f;\n if discrim(f,x) mod p = 0 then\n ERROR (\"we only implemented the case that f is square-free\")\n fi;\n d :=1;\n res:=NULL;\n while has(F,x) do\n g:=Gcd(F,x^(p^d)-x) m od p;\n # Since we have already removed all factors of degree < d from F,\n # we see that g contains *only* irreducible factors of degree d.\n F:=Normal(F/g) mod p;\n res:=res,g;\n d:=d +1\n od;\n [res]\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=7;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f:=x^6+3;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "distinct_degree_factorizatio n(f,x,p);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "So f only had irredu cible factors of degree 3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "f:=x^12-x-1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "distinc t_degree_factorization(f,x,p);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "This f has had only irreducible factors of degree 6." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "f:=x^9+x^3+3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "distinct_degree_factorization(f,x,p);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "We see that if every degree appear s only once, then we have a full factorization of f." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "Note that this is of co urse not very efficient, x^(p^d)-x has degree p^d which can be very la rge." }}{PARA 0 "" 0 "" {TEXT -1 128 "But note: if h=Rem(x^(p^d),f,x) then of course Gcd(f,x^(p^d)-x)=Gcd(f,h-x). And h has degree < degree (f,x), so h is small. And:" }}{PARA 0 "" 0 "" {TEXT -1 59 "h=Phi^d(x) \+ - x. This leads to a much faster implementation:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 590 "distinct_degree_factorization:=proc(f,x,p)\n local g,F,d,res,h;\n F:=f;\n if discrim(f,x) mod p = 0 then\n \+ ERROR(\"we only implemented the case that f is square-free\")\n \+ fi;\n d:=1;\n res:=NULL;\n h:=x;\n while has(F,x) do\n # Now h=x^(p^(d-1)) modulo f, so apply Phi to get x^(p^d) modulo f:\n \+ h:=Powmod(h,p,f,x) mod p;\n g:=Gcd(F,h-x) mod p;\n # Sin ce we have already removed all factors of degree < d from F,\n # \+ we see that g contains *only* irreducible factors of degree d.\n \+ F:=Normal(F/g) mod p;\n res:=res,g;\n d:=d+1\n od;\n [re s]\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "p:=nextprime(10 ^10);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "distinct_degree_factorization(f,x,p );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "Note that we saw before tha t:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 102 "F. p^d is precisely the set of roots of x^(p^d)-x in its splitting field \+ (which is also F.p^d) over Fp." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 16 "And furthermore:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 59 "The intersection of F.p^d 1 and F.p^d2 is F.p^igcd(d1,d2)." }}{PARA 0 "" 0 "" {TEXT -1 15 "So \+ we conclude:" }}{PARA 0 "" 0 "" {TEXT -1 60 "Gcd( x^(p^d1) - x, x^(p^ d2) - x) = x^(p^igcd(d1,d2)) - x." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 18 "Let's verify that:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "d1, d2:=6, 9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "d:=i gcd(d1,d2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "f1, f2, f := seq(x^(p^i)-x mod p, i=[d1,d2,d]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Gcd(f1,f2) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "7" 0 }{VIEWOPTS 1 1 0 1 1 1803 }