{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 "" -1 256 "" 1 24 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 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 40 "Factorization over algebr
aic extensions." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 64 "Let K be a field, and suppose we can factor polynomials i
n K[x]." }}{PARA 0 "" 0 "" {TEXT -1 29 "Let L be K(alpha) = K[x]/(f).
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "How c
an we factor a polynomial F in L[x]?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" 
}}{PARA 0 "" 0 "" {TEXT -1 8 "Example:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 39 "restart; f:=factor(x^6-6*x^4+9*x^2+23);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "alias(alpha=RootOf(f));" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "F:=evala(Normal( f/(x-alpha) ));" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "evala(Factor(F, alpha ));
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "How does Maple do that?" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 163 "First of
 all, we may assume that F is square-free. If it is not square-free, w
e can apply the square-free factorization algorithm. In our example F \+
is square-free." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 175 "In this example K=Q and L=Q(alpha). We have F in L[x]. I
f we sustitute for alpha all 6 roots (call them alpha1, alpha2, .., al
pha6) of f, and we take the product, then we get:" }}{PARA 0 "" 0 "" 
{TEXT -1 39 "  P = evala(Norm(F)), which is in K[x]." }}{PARA 0 "" 0 "
" {TEXT -1 32 "and F is a factor of P. In fact:" }}{PARA 0 "" 0 "" 
{TEXT -1 23 " P = F1 * F2 * ... * F6" }}{PARA 0 "" 0 "" {TEXT -1 35 "w
here F.i = subs(alpha=alpha.i, F)." }}{PARA 0 "" 0 "" {TEXT -1 81 "And
 alpha is one of these alpha.i, so the factor F appears in this factor
ization." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "P:=evala(Norm( \+
F ));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "evala(Rem( P, F, x
));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Zero, so indeed F is a fac
tor of P." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
290 "Now all the F.i are square-free because F is square-free. But the
 product P is not square-free. So this can only happen when some of th
e F.i have common factors. It can even happen that some or all of the \+
F.i are the same, for example, if we want to factor the following poly
nomial in L[x]:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 171 "If we want to compute evala(Facto
r(f, alpha)), then in the above procedure P would be f^6, all the f.i \+
= subs(alpha=alpha.i,f) would be equal because f doesn't have alpha." 
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "Let's r
eturn to the problem of factoring F. We want to have:" }}{PARA 0 "" 0 
"" {TEXT -1 15 " P square-free." }}{PARA 0 "" 0 "" {TEXT -1 65 "This c
an be achieved as follows: Instead of factoring F, we take:" }}{PARA 
0 "" 0 "" {TEXT -1 25 " G := subs(x = x + a, F);" }}{PARA 0 "" 0 "" 
{TEXT -1 79 "where a is some random element of L=K(alpha). If we take \+
a random, and we take:" }}{PARA 0 "" 0 "" {TEXT -1 19 " P = evala(Norm
(G))" }}{PARA 0 "" 0 "" {TEXT -1 181 "then with high probability P wil
l be square-free. We will show how we can use this to factor G, and th
en by the reverse substitution: subs(x=x-a, ..) we obtain a factorizat
ion of F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "a:=alpha+3;" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "G:=subs(x=x+a,F); P:=sqrfr
ee( evala(Norm(G)) ); # not square-free" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "a:=alpha^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 92 "G:=subs(x=x+a,F); P:=sqrfree( evala(Norm(G)) ); # again not squa
re-free, we're very unlucky:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 17 "a:=alpha^2+alpha;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "
G:=subs(x=x+a,F); P:=sqrfree( evala(Norm(G)) ); # OK, square-free:" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "P:=P[2][1][1];" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "G:=evala(Expand(G));" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 223 "Now P = G.1 * G.2 * ... * G.6 where G.i \+
= subs(alpha=alpha.i, G). We say that the G.i are the conjugates of G \+
over K, that is, the G.i are obtained from G by applying automorphisms
 of L over K to G. And G is one of the G.i." }}{PARA 0 "" 0 "" {TEXT 
-1 319 "Note that the degree of P must equal [L: K] * degree(G). If it
 is lower than that, then all coefficients of G were in a proper subfi
eld of L, and then what happened is that we didn't compute the norm ov
er the extension L:K, but over some smaller extension. When this happe
ns, we need to take another random value for a." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 242 "Now factor P in K[x], sa
y P = P1*P2*..*Pn,  (the P.i are not the G.i, because the P.i are in K
[x] and the G.i are in L[x]). Since P is square-free, all the multipli
cities of the P.i are 1. Then we get the following factorization of G \+
in L[x]:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
44 "G = gcd(P1,G) * gcd(P2,G) * ... * gcd(Pn,G)." }}{PARA 0 "" 0 "" 
{TEXT -1 82 "(we assumed G to be monic, otherwise there we can be off \+
by some constant factor)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 54 "This is a factorization of G into irreducible fact
ors." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "v:=factors(P);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "\{seq(gcd(i[1],G), i=v[2])\}
;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "subs(x=x-a,%);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(%,`*`);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "evala(Expand(% - F));" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "26" 0 }{VIEWOPTS 1 1 0 
1 1 1803 }