{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 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 1 18 0 0 0 0 0 0 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 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 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 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 1 18 0 0 0 0 0 0 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 }{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 18 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 "" 0 257 1 {CSTYLE "" -1 -1 "" 1 18 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 {SECT 1 {PARA 3 "" 0 "" {TEXT -1 47 "Review of the factorizati on algorithm for Q[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 14 "Let f in Q[x]." }}{PARA 0 "" 0 "" {TEXT 263 12 "Assu mptions:" }}{PARA 0 "" 0 "" {TEXT -1 164 "After doing square-free fact orization we may also assume that f is square-free, and after doing pr impart(f,x) we may assume that f in Z[x] and that icontent(f,x)=1." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 34 "Let p be \+ a prime number such that:" }}{PARA 0 "" 0 "" {TEXT -1 65 " \"f mod p \" in Fp[x] is square-free and has the same degree as f." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 202 "Then we have seen how to find the monic irreducible factors of \"f mod p\", and by Hens el lifting we find approximations g1,g2,..,gn of the monic irreducible factors f1, f2, ..., fn in Qp[x], and one has:" }}{PARA 0 "" 0 "" {TEXT -1 21 " f = c*f1*f2*..*fn." }}{PARA 0 "" 0 "" {TEXT -1 173 "wh ere c=lcoeff(f,x) is an integer. We can use the Landau-Mignotte bound \+ to decide what the accuracy N of our approximations g1,..,gn of the ex act factors f1,..,fn should be." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 46 "Then, for each subset S of \{1,2,..,n\} w e take:" }}{PARA 0 "" 0 "" {TEXT -1 40 "g:=mods( expand(c*mul(g.i, i=S )) , p^N);" }}{PARA 0 "" 0 "" {TEXT -1 26 "g:=primpart( gcd(g,f) ,x); " }}{PARA 0 "" 0 "" {TEXT -1 499 "And this way we find all factors of \+ f. Of course, we start with subsets S that have 1 element, then 2 elem ents, etc, and every time we find a factor g in Z[x] then we throw awa y the corresponding g.i. That will make the number of remaining g.i sm aller and so the computation willl be faster. Furthermore, another adv antage of starting with 1 element, then 2 elements, etc, and throwing \+ away g.i that we no longer need, is that this way we will find not all factors, but just all irreducible factors." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 264 21 "Complexity esti mates:" }}{PARA 0 "" 0 "" {TEXT -1 145 "Everything in this algorithm i s \"fast\", except for one thing which is in principle exponential tim e, and that is that \{1,2,..,n\} has 2^n subsets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 136 "Let k be the number of m onic irreducible factors of f in Q[x], and let n (as above) be the num ber of irreducible monic factors in Fp[x]." }}{PARA 0 "" 0 "" {TEXT -1 200 "If you try random examples, then often n=k or n is close to k. In most situations we won't need to try many sets S that don't lead t o an irreducible factors. However, you can also make examples where:" }}{PARA 0 "" 0 "" {TEXT -1 37 "k = 1 (or k=small) and n is large." }}{PARA 0 "" 0 "" {TEXT 265 8 "Example:" }}{PARA 0 "" 0 "" {TEXT 266 42 "x-(sum of square roots of prime numbers); " }}{PARA 0 "" 0 "" {TEXT 267 35 "f:=evala(Norm(convert(%,RootOf))); " }}{PARA 0 "" 0 "" {TEXT -1 272 "When k=1 the algorithm will have to check all 2^n cases \+ (and when k=small it will have to check not all cases, but still a lot of cases), and so we see that the algorithm is not \"polynomial time \", it has \"exponential complexity\" (as a function of the degree of \+ the input)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 268 148 "Conclusion: In most cases the factorization al gorithm for Q[x] is fast, but you can construct cases where it is slow . The complexity is exponential." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 683 "The implementations of factorization in \+ Q[x] in Maple and also in other computer algebra systems follow the ab ove approach. They're fast on most examples, but nevertheless they hav e an exponential complexity. We will see below that there are other me thods of factorization, that do not have an exponential complexity, bu t a polynomial complexity (that means it is of order O(n^N) for some c onstant N, where n is the degree of f). Even though that sounds better , in practise those algorithms are not faster than the method given ab ove, because the cut-off point where the polynomial time algorithms be come better is so high that at that point none of the methods is pract ical anymore." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 67 "Other ways to f actor in Q[x], that have polynomial time complexity." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Let K be a subfield of L." }}{PARA 0 "" 0 "" {TEXT -1 42 "Suppose we can factor polynomials in L[x]." }}{PARA 0 "" 0 "" {TEXT -1 50 "How can we use this to factor polynomials in K[x]?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 251 "This m ay look strange, it would seem that factoring over a larger field L sh ould always be more difficult than factoring over a smaller field K. B ut sometimes it is indeed easier to factor over L than it is over K, a s we see in the following examples:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT 256 7 "Case 1:" }}{PARA 0 "" 0 "" {TEXT -1 6 " \+ K=Q" }}{PARA 0 "" 0 "" {TEXT -1 104 " L=complex numbers C, where w e represent elements not precisely, but by floating point approximatio ns." }}{PARA 0 "" 0 "" {TEXT -1 357 "If f in Q[x] or in C[x] and f is \+ monic then f will factor over C as f=(x-alpha.1)*..*(x-alpha.n) where \+ alpha.i in C, because C is algebraically closed. The alpha.i can be de termined only approximately, but with any accuracy that we desire. Use the variable Digits in Maple to set the numerical accuracy, and use f solve(f,x,complex) to determine the alpha.i." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 257 7 "Case 2:" }}{PARA 0 "" 0 "" {TEXT -1 5 " K=Q" }}{PARA 0 "" 0 "" {TEXT -1 32 " L=field of p-adic \+ numbers Q_p." }}{PARA 0 "" 0 "" {TEXT -1 278 "If f in Z[x] is square-f ree, then we can take a prime number p such that: \"f mod p\" is still square-free and has the same degree as f. Then, by factorization in F p[x] and by Hensel-lifting we can determine the irreducible factors of f in Qp[x] up to any accuracy that we desire." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 7 "Suppose" }}{PARA 0 "" 0 "" {TEXT -1 12 "1) f in K[x]" }} {PARA 0 "" 0 "" {TEXT -1 18 "2) K subfield of L" }}{PARA 0 "" 0 "" {TEXT -1 28 "3) alpha in L is a root of f" }}{PARA 0 "" 0 "" {TEXT -1 55 "4) g in K[x] is the minimum polynomial of alpha over K." }}{PARA 0 "" 0 "" {TEXT 259 6 "Then: " }{TEXT -1 32 "g is an irreducible facto r of f." }}{PARA 0 "" 0 "" {TEXT -1 28 "We can apply this in case 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } {TEXT 260 7 "Proof: " }{TEXT -1 110 "We know that to determine g we ne ed to determine a K-linear dependence between alpha^0, alpha^1, alpha^ 2, ...." }}{PARA 0 "" 0 "" {TEXT -1 236 "We also know that g is irredu cible, if it were reducible then there would be a factor of g that als o has alpha as a root, and that contradicts the fact that g is the mon ic polynomial in K[x] of *minimal* degree that has alpha as a root." } }{PARA 0 "" 0 "" {TEXT -1 124 "Now f and g both have root alpha, so gc d(f,g) is non-trivial, and since g is irreducible it follows that g is a factor of f." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 261 24 "More generally, suppose:" }}{PARA 0 "" 0 "" {TEXT -1 12 "1) f in K[x]" }}{PARA 0 "" 0 "" {TEXT -1 18 "2) K subfield of L" }} {PARA 0 "" 0 "" {TEXT -1 39 "3) f1 = irreducible factor of f in L[x]" }}{PARA 0 "" 0 "" {TEXT -1 68 "4) g is polynomial in K[x] of minimal d egree such that f1 divides g." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 262 6 "Then: " }{TEXT -1 32 "g is an irreducible factor of f." }} {PARA 0 "" 0 "" {TEXT -1 83 "We can apply this both in case 1 and in c ase 2. The proof is more or less the same." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "Now we will illustrate case 1:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "restart;f:=x^12-32*x^10-36*x^9+426*x^8+780*x^7-148*x^6+1860*x ^5+5901*x^4+6996*x^3+26308*x^2-32640*x+56056;\n" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 25 "v:=[fsolve(f,x,complex)];" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 17 "readlib(lattice):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "alpha:=v[1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "g:=minpoly(alpha,2); # Search minimum polynomial of d egree 2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "g:=subs(_X=x,g); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "g:=gcd(g,f); # found no factor" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "g:=subs(_X=x,min poly(alpha,3)); # search minpoly of degree 3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "g:=gcd(g,f); # found no factor" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "g:=subs(_X=x,minpoly(alpha,4)); # search \+ minpoly of degree 4" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "g:=g cd(g,f); # found something" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 302 "Us ually we would need to set Digits to a higher value for this to work, \+ but in this example Digits=10 was sufficient. The number of Digits tha t we need depends on the degree and on the size of the coefficients (w hich can be bounded by the Landau-Mignotte bound) of the factor g that we are looking for." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 328 "The minpoly algorithm searches for a polynomial g of d egree <= d (in the example we tried d = 2, 3 and 4) that has coefficie nts g0,...,gd that have absolute value <= B(d,Digits). The polynomial \+ g that the algorithms searches should have a root that is close to alp ha, or in other words g(alpha) is close to 0. Or in other words:" }} {PARA 0 "" 0 "" {TEXT -1 46 "g0*alpha^0 + g1*alpha^1 + ... gd*alpha^d \+ (*)" }}{PARA 0 "" 0 "" {TEXT -1 19 "is approximately 0." }}{PARA 0 " " 0 "" {TEXT -1 458 "The bound B(d,Digits) on the coefficients of g de pends on the accuracy (=Digits) of the root alpha, and on the degree b ound d. Of course B(d,Digits) will be an increasing function of d and \+ Digits. If g has degree d and if the coefficients of g are large, then minpoly(alpha,d) will only find g if Digits is sufficiently high. Thi s is obvious, when there are many digits in g, we can not expect to re construct them all if we don't have enough digits of alpha." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 268 "So we see in ( *) that the minpoly algorithm needs to find a Z-linear relation betwee n: alpha^0, alpha^1, ..., alpha^d. If B is the bound on the coefficien ts g0,..,gd in Z of this relation, then alpha needs to have at least a certain accuracy Digits, that depends on B." }}{PARA 0 "" 0 "" {TEXT -1 297 "This Z-linear relation is only approximate because alpha is no t exact. So what we are really looking for is not that (*) is exactly \+ equal to zero, we search for \"small\" integers g0,..,gd such that (*) is very close to zero. By \"small\" we mean: abs(g.i) <= some bound B (the Landau-Mignotte bound)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 138 "It turns out that the problem above, to \+ find small integers g0,..,gd such that (*) is close to 0, can be reduc ed to the following problem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 269 58 "(**) Given a lattice, find a short vector in t his lattice." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 270 139 "Definition: A lattice L is a subset of R^n tha t can be written as Z*b1+Z*b2+..+Z*bn, where b1,..,bn in R^n are linea rly independent over R." }}{PARA 0 "" 0 "" {TEXT -1 87 "The b1,..,bn i s called a basis of the lattice, and n is called the rank of the latti ce." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 256 "" 0 "" {TEXT -1 60 " Definition: We will say that a vector v in the lattice L is " }{TEXT 273 5 "short" }{TEXT -1 4 " if:" }}{PARA 257 "" 0 "" {TEXT 271 16 "1) \+ v is not zero" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 272 89 "2) v is \+ not much longer than the shortest non-zero vector in the lattice, more precisely:" }}{PARA 0 "" 0 "" {TEXT 275 63 "length(v) <= 2^( (n-1)/2 \+ ) * length(w) for any non-zero w in L." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 206 "The problem (**) is solved by the so -called LLL-algorithm (Lenstra, Lenstra and Lovasz). We will not descr ibe the algorithm here, but only that we can use the algorithm in Mapl e with the following commands:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 47 "readlib(lattice): # Load the command in \+ Maple." }}{PARA 0 "" 0 "" {TEXT -1 54 "v:=lattice(b1, b2, .., bn); # C ompute a reduced basis." }}{PARA 0 "" 0 "" {TEXT -1 48 "v:=v[1]; # Pic k the first element of this basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 66 "And then v will be a short vector in the \+ lattice Z*b1 + .. + Z*bn." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 274 4 "Note" }{TEXT -1 169 ": Maple allows more than just lattices as input, if b1, .., bn in R^m where m>n, and b1..bn are linearly independent over R, then Maple will allow this as input as well." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 102 "How to translate the problem (*) into th e problem (**)? We need that the following things are \"small\":" }} {PARA 0 "" 0 "" {TEXT -1 65 "g0, g1, .. , gd, and g0*alpha^0 + g1*alp ha^1 + ... + gd*alpha^d." }}{PARA 0 "" 0 "" {TEXT -1 373 "We do this b y taking the following d+1 vectors b0,..,bd in R^(d+2), (so strictly \+ speaking this will not be the basis of a lattice as in the definition \+ above, where the rank of the lattice was the same as the dimension of \+ the R-vector space in which we placed the lattice. We can make it into a lattice by adding another vector to it, but in Maple that won't be \+ necessary)." }}{PARA 0 "" 0 "" {TEXT -1 32 "b0 = [1, 0, 0, ...,0, C*al pha^0]" }}{PARA 0 "" 0 "" {TEXT -1 32 "b1 = [0, 1, 0, ...,0, C*alpha^1 ]" }}{PARA 0 "" 0 "" {TEXT -1 3 "..." }}{PARA 0 "" 0 "" {TEXT -1 32 "b d = [0, 0, 0, .., 1, C*alpha^d]" }}{PARA 0 "" 0 "" {TEXT -1 25 "where \+ C is some constant." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 94 "If we find a short vector v = g0*b0 + ... + gd*bd in t he set Z*b0+..+Z*bd, then we have that:" }}{PARA 0 "" 0 "" {TEXT -1 46 "g.i = v[i+1] is small because v is small, and:" }}{PARA 0 "" 0 "" {TEXT -1 69 "g0*alpha^0 + ... + gd*alpha^d = v[d+2]/C is small because v is small." }}{PARA 0 "" 0 "" {TEXT -1 50 "And this is precisely wha t we need in problem (*)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "alpha;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "for i from 0 to \+ 4 do b.i:=[0$i,1,0$(4-i),C*alpha^i] od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Lets say we want:" }}{PARA 0 "" 0 "" {TEXT -1 15 "abs(g.i ) < 10^2" }}{PARA 0 "" 0 "" {TEXT -1 3 "and" }}{PARA 0 "" 0 "" {TEXT -1 44 "abs(g0*alpha^0 + ... + gd*alpha^d) < 10^(-8)" }}{PARA 0 "" 0 " " {TEXT -1 56 "then C=10^2 / 10^(-8) = 10^10 seems a reasonable choice ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "C:=10^10;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "for i from 0 to 4 do b.i:=map(round ,b.i) od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "lattice([b0,b1 ,b2,b3,b4]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 168 "This procedure w ants real numbers as input, not complex numbers. But we can fix that b y replacing the last entry by two entries, namely the real and the ima ginary part:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "for i from \+ 0 to 4 do b.i := subsop(-1 = op([Re(b.i[-1]), Im(b.i[-1])]) ,b.i) od; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "lattice([b0,b1,b2,b3,b4 ]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[1];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "g:=add(v[i+1]*x^i,i=0..4);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "gcd(g,f);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "So this worked well. But again, often you will h ave to set Digits to a higher value, otherwise it won't work." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 413 "Now lets try the method Case 2. We saw that we could factor using floating point computations, and since (approximat ions of) p-adic numbers are quite similar, we expect that to work as w ell. The only difference is that Qp, unlike C, is not algebraically cl osed. So we may not assume that we can find a factor x-alpha of degree 1, and then just use alpha as above, we should consider factors of de gree > 1 as well." }}{PARA 0 "" 0 "" {TEXT -1 69 "But we will see that this does not make the problem really different." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 911 "Hensel_lift := proc(f,g,h,x,N,p)\n # Inpu t: a positive integer n, and\n # monic polynomials f,g,h in Z[x] suc h that:\n # h is f*g mod p.\n\n # Output: monic polynomials F, G s uch that:\n # h is F * G mod p^N.\n local s,t,f0,g0,R,q,F,G,n;\n \+ \n # Compute s and t:\n if Gcdex(f,g,x,'s','t') mod p<>1 then\n \+ ERROR( \"f and g should have Gcd 1 modulo p\")\n fi;\n F, G := f, g; # Now the accuracy is 1.\n for n from 1 to N-1 do\n # \+ Compute f0, g0 such that (F+f0*p^n)*(G+g0*p^n) is\n # h modulo \+ p^(n+1).\n # Take f0, g0 = R*t, R*s as explained above.\n \+ R:=( Expand(h-F*G) mod p^(n+1))/p^n;\n f0, g0 := R*t, R*s;\n \+ # Now reduce f0, g0 to meet the degree conditions,\n # w hile at the same time keeping f0*g+g0*f the\n # same, namely R. \n f0:=Rem(f0,f,x,'q') mod p;\n g0:=Expand(g0+q*g) mod p ;\n F, G := F+f0*p^n, G+g0*p^n\n od;\n F, G\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 750 "HenselLift:=proc(L::list,h,x::name ,N::posint,p::posint)\n # Input: a list L=[f1,f2,...fk] of polynomia ls such that\n # f1*f2*...*fk is h modulo p, and all f.i have Gcd 1. \n #\n # Output: a list [F1,F2,..Fk] such that\n # F1*F2*..*Fk i s h modulo p^n.\n local l,L1,L2,h1,h2;\n l:=nops(L);\n if l=0 th en\n ERROR(\"wrong input\")\n elif l=1 then\n [h]\n el if l=2 then\n [Hensel_lift(op(L),h,x,N,p)]\n else\n L1, \+ L2 := L[1..iquo(l,2)], L[iquo(l,2)+1..-1];\n # Take the products .\n h1, h2 := convert(L1,`*`), convert(L2,`*`);\n # Lift t he products:\n h1, h2 := Hensel_lift(h1,h2,h,x,N,p);\n # L ift L1 and L2 and return the answer\n [op(procname(L1,h1,x,N,p)) , op(procname(L2,h2,x,N,p))]\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "sqr free(f,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Sqrfree(f) mo d 101;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "So f is still square-f ree modulo p=101, so p=101 is a suitable prime number (p does not divi de discrim(f,x))." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "p:=101; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "v:=Factors(f) mod p;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "v:=[seq(i[1],i=v[2])];" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 133 "The required accuracy depends on the Landau-Mignotte bound, which we haven't computed, so we'll just p ick something for the accuracy:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "acc:=4; # lower accuracy would probably be OK as well." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "v:=HenselLift(v,f,x,acc,p); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Now the previous method for f actoring f worked as follows:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 214 "subsets:=proc(L)\n # Input: list or set.\n # Output: list of \+ all subsets.\n local e,R,i;\n if nops(L)=0 then\n [ \{\} ]\n el se\n e:=L[1]:\n R:=procname(L[2..-1]);\n [op(R), seq(i uni on \{e\},i=R)]\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "monic_factors:=\{seq(gcd(f,mods(expand(convert(S,`*`)),p^acc)), S= subsets(v))\};" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "However, this m ethod is exponential in n, where n is the number of factors modulo p, \+ which is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(v);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 224 "To avoid exponential complexity, \+ we should not try to reconstruct a factor of f in Z[x] from several fa ctors of f in Qp[x], we should reconstruct a factor of f in Z[x] from \+ just 1 factor in Qp[x]. So lets take such a factor:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "f1:=mods(v[1],p^acc);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "gcd(f,f1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 100 "We see that f1 in Qp[x] (which we have determined up to \+ accuracy acc) is not a factor of f in Z[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "As explained above, we need to \+ find a polynomial" }}{PARA 0 "" 0 "" {TEXT -1 40 "g=g0*x^0 + ... + gd* x^d with g1..gd in Z" }}{PARA 0 "" 0 "" {TEXT -1 23 "such that f1 divi des g." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 211 "Lets assume that we know that f1 is a factor of a polynomial g in Z[x] of degree <=6. Then we can take d=6. If the degree is actually l ower than 6 (which it is), then g.d, g.(d-1),.. will be zero, but that 's OK." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "Now f1 divides g if and only if rem(g,f1,x)=0." }}{PARA 0 "" 0 "" {TEXT -1 102 "However, since we have f1 only up to accuracy acc, we ca n not expect zero, but only zero modulo p^acc." }}{PARA 0 "" 0 "" {TEXT -1 41 "So rem(g,f1,x) is just zero modulo p^acc." }}{PARA 0 "" 0 "" {TEXT -1 61 "So rem(g,f1,x)-p^acc*add(R.i*x^i, i=0..degree(f1,x)- 1) = 0" }}{PARA 0 "" 0 "" {TEXT -1 27 "for some integers R0, R1,.. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "d:=6; # degree bound ( there is no reason to take 6, we could have taken something else)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "g:=add(g.i * x^i, i=0..6);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "zero:=rem(g,f1,x)-p^acc*a dd(R.i*x^i,i=0..degree(f1,x)-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "big_number:=10^3; # Other large numbers are also fine ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "zero:=big_number * zer o; # result is still zero" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Now \+ we will consider the following vector:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 95 "v = [g0, g1, g2, .., gd, coeff(zero,x ,0), coeff(zero,x,1), ... , coeff(zero,x,degree(f1,x)-1)]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 137 "If g0,..,gd are \+ the g.i that we are looking for, well, then all g.i are small, and f1 \+ divides g, so zero=0. So then: v is a small vector." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "v:=[seq(g.i,i=0..6), seq(coeff(zero,x,i), i=0..degree(f1,x)-1)];" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "Now v = g0*b0 + g1*b1 + .. + gd*bd + R0*c.0+ R1*c.1 + .. " }}{PARA 0 "" 0 "" {TEXT -1 6 "where:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 24 "b.i := map(coeff,v,g.i);" }}{PARA 0 "" 0 "" {TEXT -1 24 " c.i := map(coeff,v.R.i);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 116 "Since g0,..,gd,R0,R1,.. are integers, we see that v is a short vector in the lattice spanned by the b.i and the c.i." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "for i from 0 to d do b.i : = map(coeff,v,g.i) od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "f or i from 0 to degree(f1,x)-1 do c.i:=map(coeff,v,R.i) od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 109 "[seq(b.i,i=0..d),seq(c.i,i=0..degr ee(f1,x)-1)]; # this spans the lattice, and v is an element of that la ttice" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "lattice(%);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[1];" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 26 "g:=add(v[i+1]*x^i,i=0..d);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "g:=gcd(f,g);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 420 "So we constructed a factor g from just 1 p-adic factor, \+ not from several. The combinatorial explosion (the exponentially many \+ subsets S) doesn't appear in this approach. Because of that, this appr oach does not exponential complexity, one can show that the complexity is polynomial. Nevertheless, in practical examples (i.e. examples tha t we can handle on a normal computer) it is \"never\" faster than the default method." }}}}}{MARK "1" 0 }{VIEWOPTS 1 1 0 1 1 1803 }