{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 }{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 -1 26 "Square free factorization.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 216 "If f is in Q[x], then f is called square
-free when f has no multiple roots. Since the multiple roots are the r
oots of f and of diff(f,x), we get that f is squarefree if and only if
 g:=gcd(f, diff(f,x)) is a constant." }}{PARA 0 "" 0 "" {TEXT -1 0 "" 
}}{PARA 0 "" 0 "" {TEXT -1 239 "In general, we can always write f = f1
^1 * f2^2 * ... * fn^n where each of the f.i is squarefree, and gcd(f.
i, f.j)=1 when i<>j.  Such a factorization is called a square-free fac
torization of f. The easiest way to obtain one is as follows:" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 21 "g:=gcd(f,
 diff(f,x));" }}{PARA 0 "" 0 "" {TEXT -1 56 "If g is a constant, then \+
f is squarefree and we're done." }}{PARA 0 "" 0 "" {TEXT -1 67 "If not
, we can obtain by recursion a squarefree factorization of g:" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "g=g1^1 * \+
g2^2 * ..." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 37 "and now f2=g1, f3=g2, etc, therefore:" }}{PARA 0 "" 0 "" {TEXT 
-1 26 "f1=f / (g1^2 * g2^3 * ...)" }}{PARA 0 "" 0 "" {TEXT -1 39 "whic
h leads to the following algorithm:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 412 "SQUAREFREE := proc(f,x)\n   # Input: a polynomial in
 x\n   # Output [f1,f2,..] such that f=f1^1 * f2^2 * ...\n   # and suc
h that the f.i are co-prime (i.e. gcd(f.i, f.j)=1\n   # when i<>j) and
 also squarefree.\n   local g,v,i;\n   g:=gcd(f,diff(f,x));\n   if not
 has(g,x) then # If x doesn't appear in g then\n       [f]\n   else\n \+
      v:=procname(g,x);\n       [normal(f/mul(v[i]^(i+1),i=1..nops(v))
) , op(v)]\n   fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "
f:=x^2*(x^2-1)^2*(x+1)^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
19 "v:=SQUAREFREE(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "
mul(v[i]^i,i=1..nops(v));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
12 "expand(%-f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "v:=sqrf
ree(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "v[1]*mul(i[1]^
i[2], i=v[2]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "f:=expand
(4*(x-3)^3*(x-2)^7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "v:=
sqrfree(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "v[1]*mul(i[1
]^i[2], i=v[2]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "v:=SQUA
REFREE(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "mul(v[i]^i,
i=1..nops(v));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(% \+
- f);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 79 "When we compute in Fp[x]
 a similar procedure does not always work. For example:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=5;" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 40 "F := Expand( (x-2)^5 * (x-3)^10 ) mod p;" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "diff(F,x) mod p;" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 15 "Gcd(%,F) mod p;" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 102 "It is possible for a polynomial in Fp[x] to have degre
e > 0 and still have derivative=0. In that case:" }}{PARA 0 "" 0 "" 
{TEXT -1 30 " g := Gcd(f, diff(f,x)) mod p;" }}{PARA 0 "" 0 "" {TEXT 
-1 87 "will be equal to f, and since we haven't reduced the degree we \+
can not apply recursion." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 54 "This can only happen when f is an element of  Fp[x
^p]." }}{PARA 0 "" 0 "" {TEXT -1 67 "So f = a_n * (x^p)^n + a_\{n-1\} \+
* (x^p)^(n-1) + ... + a_0 * (x^p)^0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" 
}}{PARA 0 "" 0 "" {TEXT -1 39 "But then, in Fp[x], f will be equal to:
" }}{PARA 0 "" 0 "" {TEXT -1 37 "f  =  (a_n * x^n + ... + a_0 *x^0)^p.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 206 "Ther
efore, we can obtain a square-free factorization of f (which is of deg
ree n*p) by doing (by recursion) a squarefree factorization of the pol
ynomial:\n a_n * x^n + ... + a_0 *x^0, which has only degree n." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "There is \+
one more complication though:" }}{PARA 0 "" 0 "" {TEXT -1 349 "In char
acteristic 0, when f has an irreducible factor g with multiplicity e>0
, (so g^e divides f and g^(e+1) does not) then diff(f,x) has an irredu
cible factor g with multiplicity e-1. In characteristic p this is only
 true when p does not divide e. When p does divide e, then diff(f,x) h
as factor g not with multiplicity e-1 but with multiplicity e." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 " Write an
 implementation for square-free factorization in Fp[x]." }}}}{MARK "19
 15 0" 64 }{VIEWOPTS 1 1 0 1 1 1803 }