{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 24 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 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 295 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 300 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 304 "" 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 58 "Factorizat ion of squarefree polynomials over finite fields" }{TEXT 304 1 "." } {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 28 "Properties of fi nite fields." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 257 42 "Definitio n: 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\}) ho momorphism:" }}{PARA 0 "" 0 "" {TEXT -1 6 "Z -> F" }}{PARA 0 "" 0 "" {TEXT -1 238 "where Z is the ring of 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, t hen Q is a subfield of F." }}{PARA 0 "" 0 "" {TEXT -1 64 "When the cha racteristic is p, then Fp = Z/pZ is a subfield of F." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 258 41 "Example s of fields with characteristic p:" }}{PARA 0 "" 0 "" {TEXT -1 39 "1) \+ Fp = Z/pZ is a 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 elem ents where n=degree(f,x)." }}{PARA 0 "" 0 "" {TEXT -1 167 "3) Fp(x). \+ The fraction field of Fp[x], i.e. all rational functions in x with coe fficients in Fp. This field has characteristic p, but it has infinitel y 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 fiel d 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 178 "Proof: (a+b)^p = add( binomial(p,i) * a^i * b^(p-i), i=0 ..p), and whenever 0 < i < p one has binomial(p,i) is zero mod p. 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 ch aracteristic 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 when you have fields K and L a nd you have a non-zero homomorphism" }}{PARA 0 "" 0 "" {TEXT -1 11 "Ph i: K -> L" }}{PARA 0 "" 0 "" {TEXT -1 23 "then Phi is one-to-one." }} {PARA 0 "" 0 "" {TEXT -1 78 "Proof: If Phi is non-zero then Phi(1)=1 b ecause 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 an s=1/(a-b) in K such that s* (a-b)=1. So then Phi(s*(a-b))=Phi(s)*( Phi(a) - Phi(b) ) = Phi(1)=1, a nd 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 64 "So we see that the homomorphism Phi: F -> F is al ways one-to-one" }}{PARA 0 "" 0 "" {TEXT -1 188 "If F contains finitel y many elements (like in example 1 and example 2, but not in example 3 ) we can conclude that Phi is also onto, so then Phi is an automorphis m. This Phi is called the: " }{TEXT 264 23 "Frobenius Automorphism." } }{PARA 0 "" 0 "" {TEXT -1 170 "When F contains infinitely many element s, like in example 3, then Phi need not be onto. The image of Fp(x) un der 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 405 "Proof: f has degree p, and so it \+ can not have more than p solutions, because whenever you have a soluti on x=alpha, you can divide f by x-alpha, reducing the degree of f by 1 . And since the degree of f is p, we can only reduce the degree p time s, so there can only be at most p solutions. Therefore we only need to show that all elements of Fp are solutions of f. We will give two dif ferent proofs of that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 406 "-> Proof #1: Let Fp* denote the set of non-zero ele ments of Fp. We need to show that every element of Fp* is a solution o f f/x = x^(p-1)-1. Let a in Fp*. What we need to show is that a^(p-1) \+ = 1 (this is called Fermat's little theorem). Now Fp* is a group under multiplication. The order of this group (i.e. the number of elements) is p-1. If a is an element of a group with p-1 elements, then a^(p-1) = 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 407 " -> Proof #2: Phi is an automorphism of Fp. Any automorphism must se nd 0 to 0, send 1 to 1, send 1+1 to 1+1, send 1+1+1 to 1+1+1. Now all \+ elements of Fp are of the form 0, 1, 1+1, 1+1+1, .. and so Fp can have only one automorphism, namely the identity. But Phi is also an automo rphism, so it must be the identity on Fp. So Phi(a) must be equal to a for all a in Fp, and we conclude a^p-a=0 for all a in Fp." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 292 11 "Conclusion:" }} {PARA 0 "" 0 "" {TEXT -1 155 "If F is a field of characteristic p, the n Fp is a subfield of F. And the only elements of F for which Phi(a)=a are those that are in that subfield Fp of F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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) mod 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 "Phi(b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "P hi(a+b);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Factor(x^4+3) m od 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 "" {TEXT -1 400 "Phi acts non-trivially on all ele ments of F that are outside of Fp. Now if F is a finite field, then Ph i must be onto (because with a finite set, one-to-one is the same as o nto) and so Phi permutes the elements of F. We see then that if we rep eat Phi a number of times, we must at some point get back to where we \+ started. Let's see how often we need to apply Phi on a in order to get back to a again:" }}}{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 "Phi(%);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 7 "Phi(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{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 irreducibl e factor of f to K, factoring again, adjoining a root to the field, et c., we can find a field L such that" }}{PARA 0 "" 0 "" {TEXT -1 37 "1) L contains 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, ... , alpha.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 spl itting field always exists, for any field K and for any polynomial f i n K[x]. One can prove:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 266 13 "Proposition: " }{TEXT 300 141 "The splitting field of f over K is uni que up to isomorphism. That is, if L1 and L2 satisfy the conditions 1) and 2) then they are isomorphic." }}{PARA 0 "" 0 "" {TEXT -1 16 "Sket ch of proof:" }}{PARA 0 "" 0 "" {TEXT -1 865 "Take a splitting field L . We construct a splitting field using the repeated factorization, and we need to show that the field we are construct is isomorphic to L. D uring the construction of our splitting field, we extend our field in \+ every step with a root alpha.i. During this process, we can also const ruct a homomorphism from the field we're extending every time to the f ield L. This is done by sending the element alpha.i by which we extend our field to a suitable element of L. Namely, if alpha.i is a root of the irreducible factor g of f (irreducible over the field we've const ructed up to that point), then compute the roots of g in L and send al pha.i to one of those roots. When we've completed our construction 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 defined as the spli tting 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 13 "Propositi on: " }{TEXT 299 18 "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 13 "Proposition: " }{TEXT 298 42 "The \+ intersection of F.q1 and F.q2 is F.q3." }}{PARA 0 "" 0 "" {TEXT -1 39 "Proof: This follows from the fact that:" }}{PARA 0 "" 0 "" {TEXT -1 75 "Phi^n(a) = a and 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 11 "Corollary: " }{TEXT 297 54 "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 "Let again q = p^n, with p prime and n a p ositive integer." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 269 13 "Propo sition: " }{TEXT 296 56 "up to isomorphism, Fq is the only field with \+ q elements." }}{PARA 0 "" 0 "" {TEXT -1 261 "Proof: Let L be a field w ith q elements. Let a be a non-zero element of L. The same proof as pr oof # 1 in lemma 2 shows that a^(q-1)=1. Therefore every element of L \+ is a root of x^q-x, and we see that L is the splitting 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 "Proposition: " }{TEXT 295 89 "For every positive integer n there exists an irreducible polynomial of de gree 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 integer d that divides n we have a subfield F.p^d of Fq, and this is a complete list of subfields . One can count (one can find a formula using the principle of inclusi on-exclusion) how many elements alpha in Fq are element of some proper subfield of Fq. This number is smaller than p^n. So there exists an a lpha in Fq that is not an element of any proper subfield of Fq, and th is 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 isomorph ic to Fp[x]/(f). So the degree of f must be equal 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 293 13 "Proposition: " }{TEXT 294 118 "Let q be \+ a prime-power and let Fq* be the multiplicative group of non-zero elem ents in Fq. Then Fq* is a cyclic group." }}{PARA 0 "" 0 "" {TEXT -1 393 "Proof: Fq* is a finite abelian group. Hence, if n is the highest \+ order of an element in this group, then a^n=1 for any a in Fq*. But th en a^(n+1) - a = 0 for any element a in Fq. So this equation has at le ast q solutions, so n+1 is at least q, and n is at least q-1, which is the order of the group Fq*. Hence Fq* contains an element of order at least (hence equal to) q-1 and so it is cyclic." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{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 irreducible 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 be 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 polynomial of degree n\n f:=x^n+randpoly(x,d egree=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_p oly(5,x,p);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "g:=irreducib le_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, RootO f(g)) mod p;" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 42 "Intermezzo: Sho rt sketch of Galois theory." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "Let q=p^n. The set of all automorphisms of Fq i s:" }}{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 identi ty automorphism. Now G is a cyclic group generated by the Frobenius Au tomorphism Phi. When H is a subgroup of G (since G is cyclic the only \+ possible subgroups are the cyclic groups generated by Phi^d where d di vides n) then Fq^H denotes the set of all a in Fq such that a is invar iant under all elements 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 c orrespondence between the subgroups of the group Galois group G (the g roup of all automorphisms of Fq), and the subfields of Fq. If H1 and H 2 are subgroups of G, and if H1 is a subgroup of H2 then Fq^H2 is a su bfield of Fq^H1." }}{PARA 0 "" 0 "" {TEXT -1 433 "Something similar ho lds for Q as well. If f is a polynomial in Q[x], and L is the splittin g field of f over Q, then one can look at the group G of all automorph isms of L. Then there is a 1-1 correspondence between the subgroups of G and the subfields of L. The trivial group \{1\} corresponds to L, a nd the full Galois group G corresponds to Q. This means that if a in \+ L, and a is invariant 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 subfields of L is called the " }{TEXT 274 22 "Galois corresp ondence," }{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 to 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 "Th e degree of the splitting field equals the number of elements of the G alois group. So, to find all roots of f we need an algebraic extension of degree 20. 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. What are some of the subfields? Well, the discriminant is a quadra tic expression in terms of the roots. So sqrt(discriminant) is in the \+ splitting field." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "ifactor (discrim(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 corre spond to a subgroup of G. It corresponds to the group H which consists of all automorphisms Psi: L -> L for which Psi(a)=a for all a in Q( s qrt(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 nil potent 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 89 "An element a in R is called a zero-divis or if a<>0 and there exists b<>0 such that a*b=0." }}{PARA 0 "" 0 "" {TEXT -1 87 "An element a in R is called nilpotent if there is a posit ive integer n such that a^n=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 303 5 "Note:" }{TEXT -1 104 " A non-zero nilpote nt element is always a zero-divisor. But a zero-divisor is not necessa rily nilpotent." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "Let K be a field and let f be a polynomial in K[x]." }} {PARA 0 "" 0 "" {TEXT 301 29 "Consider 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 ar e the irreducible factors of f, and e1..e.n are the multiplicities. Th en, by the Chinese Remainder Theorem we have:" }}{PARA 0 "" 0 "" {TEXT -1 3 " " }{TEXT 302 55 "R is isomorphic to K[x]/(f1^e1) * ... \+ * K[x]/(f.n^e.n)." }}{PARA 0 "" 0 "" {TEXT -1 116 "Under this isomorph ism, an element a in R corresponds to a sequence (a.1, a.2, .., a.n) w here a.i in K[x]/(f.i^e.i)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 385 "An element a in R is nilpotent if and only if \+ a.i is nilpotent for each i. This happens if and only if each a.i is d ivisible by f.i, so a is nilpotent if and only if a is a multiple of f 1 * f2 * .. * fn. So there are non-zero nilpotent 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 we conclude:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 276 86 "Lemma 1: R has no non-zero nilp otent elements if and only if f in K[x] is square-free." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 260 "Given a polynomial \+ in f, we can always compute a square-free factorization, f=f1^1 * f2^2 * ..., where each of the f.i is squarefree. The main step in the squa re-free factorization is computing the gcd of f and f'. This gcd is 1 \+ if and only if f is squarefree." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 277 59 "Lemma 2: R has zero-divis ors if and only if f is reducible." }}{PARA 0 "" 0 "" {TEXT -1 312 "Pr oof: If f is not square-free then R has nonzero nilpotent elements, an d 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 multipli city 1 in f (so f/f.i is not divisible by f.i). In that case R is isom orphic to a product of fields:" }}{PARA 0 "" 0 "" {TEXT -1 35 " R iso morphic 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-divisor s of R is the set of all non-zero a (that means that at least one of t he 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 shows 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 (h ere we view a as a polynomial in x)." }}{PARA 0 "" 0 "" {TEXT -1 55 "N ote that we say that gcd(a,f) is trivial in two cases:" }}{PARA 0 "" 0 "" {TEXT -1 101 " *) When gcd(a,f)=f, in which case a is zero in R \+ (so viewed as a polynomial, a is divisible by f)." }}{PARA 0 "" 0 "" {TEXT -1 104 " *) Or when gcd(a,f)=1, in which case we have s*a+t*f=1 , for some s,t. 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 113 "a is \+ a zero-divisor if and only if gcd(a,f) is non-trivial, if and only if \+ a is not zero and not invertible in R." }}{PARA 0 "" 0 "" {TEXT -1 68 "Note: a is invertible means that there is an s in R such that s*a=1. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "So we conclude the following:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 279 95 "Finding a non-trivial factorization of f is equivalent to finding \+ a zero-divisor in R=K[x]/(f)." }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 118 "Why? Well, if a is a non-trivial factor of f in K[x], then if \+ we view a as an element of R, then it is a zero-divisor." }}{PARA 0 " " 0 "" {TEXT -1 142 "Conversely, if a is a zero-divisor, then, if we v iew it as an element of K[x], and take the gcd with f, then we get a n on-trivial factor of f." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 22 "Facto rization in Fp[x]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 232 "We will now focus on the case K=Fp, we will look at how \+ to factor polynomials f in Fp[x]. After using the square-free factoriz ation algorithm we may assume that f is square-free. So, R=Fp[x]/(f) i s 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 c ompute with it because we don't know the f.i, the K.i, we even don't \+ know the number n of irreducible factors. But what we can compute with is the Frobenius homomorphism Phi, that 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 nilpotent because we assume that f is squaref ree. So a^i <> 0 for any positive integer 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 ri ng to itself is called an automorphism), called the " }{TEXT 281 22 "F robenius 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 invar iant under Phi if and only if all a.i are 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 T heorem gives the following correspondences:" }}{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 = K er(Phi-1) corresponds under the Chinese Remainder theorem to a subring Fp * .. * Fp of K1 * K2 *.. * Kn. This 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 "Lemma 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 "Since R is a finite set, and Phi is 1-1 \+ because f is square-free, if we just keep on applying Phi, starting wi th the element x, eventually we will 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 o n 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 wher e q=p^7, and then Phi^7 would be the identity. But we see that Phi^7(x ) <> x, we have Phi^10(x)=x. Since every element of Fp[x]/(f) can be p resented as a polynomial in x, we see that Phi^10(a)=a for every a in \+ R, so Phi is an automorphism of R of order 10. That the order is 10 c an only be explained when f is a product of a polynomial of degree 2 a nd a polynomial of degree 5, because then 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 (tha t means Phi^5 is the identity on F.p^5 and Phi^i is not the identity f or 1<=i<5). Since ilcm(2,5)=10 that would 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 irreducible factors of f in Fp[x] . So n = dim Ker(Phi-1) = 2. How to compute 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 choose a basis (we take: x^0, x^1 , .., x^6) of R as an Fp-vector space, then Phi-1 corresponds to a mat rix 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 image s of these basis elements under the map Phi-1 are:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "images_basis:=map(a -> Phi(a)-a mod p, basi s);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 107 "Now write these images as column vectors on the given basis, and construct the matrix A with th ese columns:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "A:=matrix(d egree(f,x),degree(f,x), [seq(seq( coeff(i,x,j), i=images_basis), j=0.. degree(f,x)-1)] );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 123 "Now determ ine a basis for Ker(Phi-1), which corresponds to a basis of Ker(A). No te that Nullspace means the same as kernel." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Nullspace(A) mod p;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "Translate these vectors back to polynomials (use again th e basis x^0, x^1, ..). Then we get:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "basis_ker_Phi_minus_1 := \{seq(add(i[j+1]*x^j,j=0..de gree(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^10 is the identity on R. Let's ch eck that in terms of matrices. The matrix of Phi is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "images_basis_under_Phi:=map(Phi,basis);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 118 "Phi_matrix:=matrix(degre e(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 isomorphic to F.p^2 * Fp^5. The kernel of Phi-1 is S which corresponds under the Chinese Remainder Theorem to F p * 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 corresp onds to Fp * F.p^5, which has dimension 6 over Fp. We can check all of these statements by computing the matrices of Phi^2-1 and Phi^5-1 in \+ the same way as we did above, and then computing the Nullspace, but we won't do that." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 376 "After these example computations, we'll focus again on w hat our goal was, i.e. to factor the polynomial f, which we assume to \+ be square-free. So what we're looking for are zero-divisors. So we sea rch for elements a, that under the Chinese Remainder theorem correspon d to (a.1 , a.2 ,.., a.n) such that at least one a.i=0 and at least on e a.i <> 0. We do this in several steps:" }}{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 o f 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))=d im(Nullspace(A))=1 we can stop, f is irreducible. But if n>1 we have s till gained something by computing S=Ker(Phi-1), namely the following: " }}{PARA 0 "" 0 "" {TEXT -1 311 "We are searching for zero divisors i n R. The method of finding zero divisors starts by taking a random ele ment a in R. But it's not so easy to deal with such an a because the a .i are in K.i, so the a.i could be in different fields K.i (the K.i ar e different when the degrees of the factors of f are different).\n" }} {PARA 0 "" 0 "" {TEXT -1 344 "Now we will not pick a random element in R, but a random element in S that is not in Fp (so an element a in S \+ for which has(a,x)=true). Then a corresponds to (a.1 , a.2, .., a.n) b ut now all the a.i are in the same field, namely they are in Fp. Furth ermore: not all a.i are the same, because then a would be in Fp. Now w e 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 the 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 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 "0 0 1" 28 }{VIEWOPTS 1 1 0 1 1 1803 }