{VERSION 6 0 "SUN SPARC SOLARIS" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 268 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 269 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 271 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 272 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 274 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 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 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 } {PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Error" 7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 1 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 "Maple Output" 0 11 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 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 1 }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 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {SECT 0 {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 199 "Then we have seen how to find the monic irreducible factors of \"f mod p\" in Fp[x], an d by Hensel lifting we find approximations of the monic irreducible fa ctors f1, f2, ..., fn in Qp[x], and one has:" }}{PARA 0 "" 0 "" {TEXT -1 24 " f = c*f1*f2*..*fn." }}{PARA 0 "" 0 "" {TEXT -1 165 "where c=lcoeff(f,x) is an integer. We can use the Landau-Mignotte bound to \+ decide what the accuracy N of our approximations of the p-adic 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\} we take:" }} {PARA 0 "" 0 "" {TEXT -1 40 "g:=mods( expand(c*mul(f.i, i=S)) , p^N); " }}{PARA 0 "" 0 "" {TEXT -1 26 "g:=primpart( gcd(g,f) ,x);" }}{PARA 0 "" 0 "" {TEXT -1 501 "And this way we find all factors of f. Of cour se, we start with subsets S that have 1 element, then 2 elements, etc, and every time we find a factor g in Z[x] then we throw away the corr esponding f.i. That will make the number of remaining f.i smaller and \+ so the computation willl be faster. Furthermore, another advantage of \+ starting with 1 element, then 2 elements, etc, and throwing away f.i's 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 estimates:" } }{PARA 0 "" 0 "" {TEXT -1 156 "Everything in this algorithm is \"polyn omial-time\", except for one thing which is in principle exponential t ime, 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 monic irreducible factors of f in Q[x], and let n (as above) be the n umber 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 707 "The implementations of factorization in \+ Q[x] in Maple and also in other computer algebra systems used to follo w the above approach. They're fast on most examples, but nevertheless \+ they have an exponential complexity. We will see below that there are \+ other methods of factorization, that do not have an exponential comple xity, but a polynomial complexity (that means their running time is of order O(n^N) for some constant N, where n is the degree of f). Even t hough that sounds better, in practise those algorithms are not faster \+ than the method given above, because the cut-off point where the polyn omial time algorithms become better is so high that at that point none of the methods is practical anymore." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 67 "Other ways to factor in Q[x], that have polynomial time c omplexity." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Let K be a subfield \+ of L." }}{PARA 0 "" 0 "" {TEXT -1 42 "Suppose we can factor polynomial s in L[x]." }}{PARA 0 "" 0 "" {TEXT -1 50 "How can we use this to fact or polynomials in K[x]?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 251 "This may look strange, it would seem that factoring over a larger field L should always be more difficult than factoring \+ over a smaller field K. But sometimes it is indeed easier to factor ov er L than it is over K, as 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 we represent elements not precisely, but b y floating point approximations." }}{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-a lpha.1)*..*(x-alpha.n) where alpha.i in C, because C is algebraically \+ closed. The alpha.i can be determined only approximately, but with any accuracy that we desire. Use the variable Digits in Maple to set the \+ numerical accuracy, and use fsolve(f,x,complex) to determine the alpha .i." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 257 7 "Ca se 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-free, then we can take a prime number p su ch that: \"f mod p\" is still square-free and has the same degree as f . Then, by factorization in Fp[x] and by Hensel-lifting we can determi ne the irreducible factors of f in Qp[x] up to any accuracy that we de sire." }}{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 o ver K." }}{PARA 0 "" 0 "" {TEXT 259 6 "Then: " }{TEXT -1 32 "g is an i rreducible factor of f." }}{PARA 0 "" 0 "" {TEXT -1 28 "We can apply t his 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 de termine g we need to determine a K-linear dependence between alpha^0, \+ alpha^1, alpha^2, ...." }}{PARA 0 "" 0 "" {TEXT -1 236 "We also know t hat g is irreducible, if it were reducible then there would be a facto r of g that also has alpha as a root, and that contradicts the fact th at g is the monic polynomial in K[x] of *minimal* degree that has alph a as a root." }}{PARA 0 "" 0 "" {TEXT -1 124 "Now f and g both have ro ot alpha, so gcd(f,g) is non-trivial, and since g is irreducible it fo llows 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 su bfield 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 degree 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 case 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-14 8*x^6+1860*x^5+5901*x^4+6996*x^3+26308*x^2-32640*x+56056;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,:*$)%\"xG\"#7\"\"\"F**&\"#KF*)F(\"#5F *!\"\"*&\"#OF*)F(\"\"*F*F/*&\"$E%F*)F(\"\")F*F**&\"$!yF*)F(\"\"(F*F**& \"$[\"F*)F(\"\"'F*F/*&\"%g=F*)F(\"\"&F*F**&\"%,fF*)F(\"\"%F*F**&\"%'*p F*)F(\"\"$F*F**&\"&3j#F*)F(\"\"#F*F**&\"&SE$F*F(F*F/\"&cg&F*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "v:=[fsolve(f,x,complex)];" } }{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"vG7.^$$!+iN@9M!\"*$!+330K\\zE\"F)$!+iN@99F)^$FF$\" +iN@99F)^$$\"+330KZF)FH^$FNFK" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "alpha:=v[1];" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%&alphaG^$$!+iN@9M!\"*$!+330K " 0 "" {MPLTEXT 1 0 71 "g:=polytools[minpoly](alpha, 2); # Search minimum polynomial of degree 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(\"&Fu\"\"\"\"*&\"%>\")F'%#_XGF'F'*&\"%*=\"F')F* \"\"#F'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "g:=subs(_X=x,g );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,(\"&Fu\"\"\"\"*&\"%>\")F' %\"xGF'F'*&\"%*=\"F')F*\"\"#F'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "g:=gcd(g,f); # found no factor" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "g:=subs(_X=x,polytools[minpoly](alpha,3)); # search minpoly of deg ree 3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,*\"&Ho\"!\"\"*&\"&uC\" \"\"\"%\"xGF*F**&\"%;$)F*)F+\"\"#F*F**&\"%'Q\"F*)F+\"\"$F*F*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "g:=gcd(g,f); # found no fact or" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "g:=subs(_X=x,polytools[minpoly](alpha,4)); \+ # search minpoly of degree 4" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG ,,\"#\\\"\"\"*&\"#SF'%\"xGF'F'*&\"#EF')F*\"\"#F'F'*&\"\")F')F*\"\"$F'F '*$)F*\"\"%F'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "g:=gcd(g ,f); # found something" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,,\"# \\\"\"\"*&\"#SF'%\"xGF'F'*&\"#EF')F*\"\"#F'F'*&\"\")F')F*\"\"$F'F'*$)F *\"\"%F'F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 302 "Usually we would n eed to set Digits to a higher value for this to work, but in this exam ple Digits=10 was sufficient. The number of Digits that we need depend s on the degree and on the size of the coefficients (which can be boun ded 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 degree <= d (in t he example we tried d = 2, 3 and 4) that has coefficients g0,...,gd th at have absolute value <= B(d,Digits). The polynomial g that the algor ithms searches should have a root that is close to alpha, 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 depends on the \+ accuracy (=Digits) of the root alpha, and on the degree bound d. Of co urse 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(alph a,d) will only find g if Digits is sufficiently high. This is obvious, when there are many digits in g, we can not expect to reconstruct the m 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 th e minpoly algorithm needs to find a Z-linear relation between: alpha^0 , alpha^1, ..., alpha^d. If B is the bound on the coefficients g0,..,g d in Z of this relation, then alpha needs to have at least a certain a ccuracy Digits, that depends on B." }}{PARA 0 "" 0 "" {TEXT -1 297 "Th is Z-linear relation is only approximate because alpha is not exact. S o what we are really looking for is not that (*) is exactly equal to z ero, we search for \"small\" integers g0,..,gd such that (*) is very c lose to zero. By \"small\" we mean: abs(g.i) <= some bound B (the Land au-Mignotte bound)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 138 "It turns out that the problem above, to find small int egers g0,..,gd such that (*) is close to 0, can be reduced to the foll owing problem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 269 58 "(**) Given a lattice, find a short vector in this lattic e." }}{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 that can be \+ written as Z*b1+Z*b2+..+Z*bn, where b1,..,bn in R^n are linearly indep endent over R." }}{PARA 0 "" 0 "" {TEXT -1 87 "The b1,..,bn is called \+ a basis of the lattice, and n is called the rank of the lattice." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 256 "" 0 "" {TEXT -1 60 "Definit ion: We will say that a vector v in the lattice L is " }{TEXT 273 5 "s hort" }{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 precise ly:" }}{PARA 0 "" 0 "" {TEXT 275 63 "length(v) <= 2^( (n-1)/2 ) * leng th(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-cal led LLL-algorithm (Lenstra, Lenstra and Lovasz). We will not describe \+ the algorithm here, but only that we can use the algorithm in Maple wi th the following commands:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "v:=LLL(b1, b2, .., bn); # Compute a reduced basis ." }}{PARA 0 "" 0 "" {TEXT -1 48 "v:=v[1]; # Pick 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 inpu t as well." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 102 "How to translate the problem (*) into the problem (**)? We nee d that the following things are \"small\":" }}{PARA 0 "" 0 "" {TEXT -1 65 "g0, g1, .. , gd, and g0*alpha^0 + g1*alpha^1 + ... + gd*alpha^ d." }}{PARA 0 "" 0 "" {TEXT -1 373 "We do this by 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 a nother vector to it, but in Maple that won't be necessary)." }}{PARA 0 "" 0 "" {TEXT -1 32 "b0 = [1, 0, 0, ...,0, C*alpha^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 "bd = [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 f ind a short vector v = g0*b0 + ... + gd*bd in the set Z*b0+..+Z*bd, t hen we have that:" }}{PARA 0 "" 0 "" {TEXT -1 46 "g.i = v[i+1] is smal l 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 what we need in problem (*) ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "alpha;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#^$$!+iN@9M!\"*$!+330K " 0 "" {MPLTEXT 1 0 57 "for i from 0 to 4 do b||i:=[0$i,1,0$(4-i),C*alp ha^i] od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b0G7(\"\"\"\"\"!F'F'F' *&^$$F&F'$F'F'F&%\"CGF&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b1G7(\" \"!\"\"\"F&F&F&*&^$$!+iN@9M!\"*$!+330K%#b2G7(\"\"!F&\"\"\"F&F&*&^$$\"+XU&ol)!\"*$\"+s#=F= \"!\")F'%\"CGF'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b3G7(\"\"!F&F&\" \"\"F&*&^$$!+(yn52*!\"*$!+-RYPb!\")F'%\"CGF'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b4G7(\"\"!F&F&F&\"\"\"*&^$$!+hD6%\\'!\")$\"+QRsZ?!\" (F'%\"CGF'" }}}{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 / 1 0^(-8) = 10^10 seems a reasonable choice." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 9 "C:=10^10;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG \",+++++\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "for i from 0 \+ to 4 do b||i:=map(round,b||i) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %#b0G7(\"\"\"\"\"!F'F'F'\",+++++\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%#b1G7(\"\"!\"\"\"F&F&F&^$!,?c8UT$!,!330K<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b2G7(\"\"!F&\"\"\"F&F&^$\",]Caol)\"-+s#=F=\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b3G7(\"\"!F&F&\"\"\"F&^$!,qyn52*!-+ -RYPb" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b4G7(\"\"!F&F&F&\"\"\"^$!- +hD6%\\'\".+!QRsZ?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "with( IntegerRelations):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "LLL([ b0,b1,b2,b3,b4]);" }}{PARA 8 "" 1 "" {TEXT -1 52 "Error, (in IntegerRe lations:-LLL) invalid arguments\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 168 "This procedure wants real numbers as input, not complex numbers. \+ But we can fix that by replacing the last entry by two entries, namely the real and the imaginary part:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "for i from 0 to 4 do b||i := subsop(-1 = op([Re(b||i[ -1]), Im(b||i[-1])]) ,b||i) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% #b0G7)\"\"\"\"\"!F'F'F'\",+++++\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%#b1G7)\"\"!\"\"\"F&F&F&!,?c8UT$!,!330K<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b2G7)\"\"!F&\"\"\"F&F&\",]Caol)\"-+s#=F=\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b3G7)\"\"!F&F&\"\"\"F&!,qyn52*!-+-RYPb" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b4G7)\"\"!F&F&F&\"\"\"!-+hD6%\\'\" .+!QRsZ?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "LLL([b0,b1,b2,b 3,b4]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7'7)\"#\\\"#S\"#E\"\")\"\" \"!$g\"\"$+%7)\"&kl'\"&E\"G\"&u!=\"%Mn\"%:5\"&+^(\"&?z\"7)\"&l7'\"&D_& \"'$3E\"\"&AG&\"%pu!'!>^\"!&+G)7)!'Ac=\"'9$\\\"\"%:7!&D'G!%[l\"&?O)\"& !)=%7)!&I*o!'owB\"&%*f&\"&p)e\"&v1\"\"&IH)\"&S/'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"vG7)\"#\\\"#S\"#E\"\")\"\"\"!$g\"\"$+%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "g:=add(v[i+1]*x^i,i=0..4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,,\"#\\\"\"\"*&\"#SF'%\"xGF'F'*&\"#EF')F*\"\"#F'F '*&\"\")F')F*\"\"$F'F'*$)F*\"\"%F'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "gcd(g,f);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,\"#\\\" \"\"*&\"#SF%%\"xGF%F%*&\"#EF%)F(\"\"#F%F%*&\"\")F%)F(\"\"$F%F%*$)F(\" \"%F%F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "So this worked well. \+ But again, often you will have to set Digits to a higher value, otherw ise 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 (approximations of) p-adic numbers are quite similar, we ex pect that to work as well. The only difference is that Qp, unlike C, i s not algebraically closed. So we may not assume that we can find a fa ctor x-alpha of degree 1, and then just use alpha as above, we should \+ consider factors of degree > 1 as well." }}{PARA 0 "" 0 "" {TEXT -1 69 "But we will see that this does not make the problem really differe nt." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 909 "Hensel_lift := proc (f,g,h,x,N,p)\n # Input: a positive integer n, and\n # monic polyn omials f,g,h in Z[x] such that:\n # h is f*g mod p.\n\n # Output: \+ monic polynomials F, G such 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) i s\n # h modulo p^(n+1).\n # Take f0, g0 = R*t, R*s as ex plained 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 co nditions,\n # while 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 749 "HenselLift:= proc(L::list,h,x::name,N::posint,p::posint)\n # Input: a list L=[f1, f2,...fk] of polynomials such that\n # f1*f2*...*fk is h modulo p, a nd all f.i have Gcd 1.\n #\n # Output: a list [F1,F2,..Fk] such th at\n # F1*F2*..*Fk is h modulo p^n.\n local l,L1,L2,h1,h2;\n l:= nops(L);\n if l=0 then\n error \"wrong input\"\n elif l=1 th en\n [h]\n elif 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 the products:\n h1, h2 := Hensel_lift(h1,h2 ,h,x,N,p);\n # Lift 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;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,:*$)%\"xG\"#7\"\"\"F(*&\"#KF()F&\"#5F(!\"\"*&\"#OF()F& \"\"*F(F-*&\"$E%F()F&\"\")F(F(*&\"$!yF()F&\"\"(F(F(*&\"$[\"F()F&\"\"'F (F-*&\"%g=F()F&\"\"&F(F(*&\"%,fF()F&\"\"%F(F(*&\"%'*pF()F&\"\"$F(F(*& \"&3j#F()F&\"\"#F(F(*&\"&SE$F(F&F(F-\"&cg&F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "sqrfree(f,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #7$\"\"\"7#7$,:*$)%\"xG\"#7F$F$*&\"#KF$)F*\"#5F$!\"\"*&\"#OF$)F*\"\"*F $F0*&\"$E%F$)F*\"\")F$F$*&\"$!yF$)F*\"\"(F$F$*&\"$[\"F$)F*\"\"'F$F0*& \"%g=F$)F*\"\"&F$F$*&\"%,fF$)F*\"\"%F$F$*&\"%'*pF$)F*\"\"$F$F$*&\"&3j# F$)F*\"\"#F$F$*&\"&SE$F$F*F$F0\"&cg&F$F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Sqrfree(f) mod 101;" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#7$\"\"\"7#7$,:*$)%\"xG\"#7F$F$*&\"#pF$)F*\"#5F$F$*&\"#lF$)F*\"\"*F$F $*&\"#AF$)F*\"\")F$F$*&\"#tF$)F*\"\"(F$F$*&\"#aF$)F*\"\"'F$F$*&\"#UF$) F*\"\"&F$F$*&\"#VF$)F*\"\"%F$F$*&\"#FF$)F*\"\"$F$F$*&\"#[F$)F*\"\"#F$F $*&\"#%)F$F*F$F$F$F$F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 109 "So f i s still square-free modulo p=101, so p=101 is a suitable prime number \+ (p does not divide discrim(f,x))." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "p:=101;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"$, \"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "v:=Factors(f) mod p; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"vG7$\"\"\"7(7$,(*$)%\"xG\"\"#F &F&*&\"\"%F&F,F&F&\"#yF&F&7$,(F*F&*&\"#&*F&F,F&F&\"#OF&F&7$,(F*F&*&\"# $)F&F,F&F&F0F&F&7$,(F*F&*&F/F&F,F&F&\"#LF&F&7$,(F*F&*&\"#AF&F,F&F&\"#< F&F&7$,(F*F&*&F4F&F,F&F&\"#\")F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "v:=[seq(i[1],i=v[2])];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7(,(*$)%\"xG\"\"#\"\"\"F+*&\"\"%F+F)F+F+\"#yF+,(F'F+*&\"#& *F+F)F+F+\"#OF+,(F'F+*&\"#$)F+F)F+F+F.F+,(F'F+*&F-F+F)F+F+\"#LF+,(F'F+ *&\"#AF+F)F+F+\"# " 0 "" {MPLTEXT 1 0 54 "acc:=4; # l ower accuracy would probably be OK as well." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$accG\"\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "v:=HenselLift(v,f,x,acc,p);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>% \"vG7(,(*$)%\"xG\"\"#\"\"\"F+*&\"\"%F+F)F+F+\")+j'o%F+,(F'F+*&\"*&RgS5 F+F)F+F+\")9T>dF+,(F'F+*&\")%QG:(F+F)F+F+\")z$G:(F+,(F'F+*&F-F+F)F+F+ \")6T>dF+,(F'F+*&\")@?`KF+F)F+F+\");?`KF+,(F'F+*&F1F+F)F+F+\").j'o%F+ " }}}{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))\};" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%.monic_factorsG<* \"\"\",:*$)%\"xG\"#7F&F&*&\"#KF&)F*\"#5F&!\"\"*&\"#OF&)F*\"\"*F&F0*&\" $E%F&)F*\"\")F&F&*&\"$!yF&)F*\"\"(F&F&*&\"$[\"F&)F*\"\"'F&F0*&\"%g=F&) F*\"\"&F&F&*&\"%,fF&)F*\"\"%F&F&*&\"%'*pF&)F*\"\"$F&F&*&\"&3j#F&)F*\" \"#F&F&*&\"&SE$F&F*F&F0\"&cg&F&,,*$FGF&F&*&FHF&FKF&F&*&FPF&FOF&F&*&FHF &F*F&F0\"#8F&,,FUF&*&F+F&FKF&F0*&\"#_F&FOF&F&*&\"#'*F&F*F&F0\"#))F&,4* $F7F&F&*&F+F&F;F&F&*&\"#gF&F?F&F&*&\"$c\"F&FCF&F&*&\"$U#F&FGF&F&*&\"$w #F&FKF&F&*&FeoF&FOF&F&*&\"$C$F&F*F&F&\"$P'F&,4F\\oF&*&FHF&F;F&F0*&\"#= F&F?F&F0*&\"#[F&FCF&F&*&\"$T#F&FGF&F&*&\"$+$F&FKF&F0*&\"$'**F&FOF&F&*& \"%%=\"F&F*F&F0\"%7VF&,,\"#\\F&*&\"#SF&F*F&F&*&\"#EF&FOF&F&*&F8F&FKF&F &FUF&,4F\\oF&*&F8F&F;F&F0*&F@F&F?F&F&*&\"#%)F&FCF&F&*&\"$J\"F&FGF&F0*& \"$/#F&FKF&F0*&\"%O7F&FOF&F&*&\"%+;F&F*F&F0\"%W6F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "However, this method 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);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"' " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 224 "To avoid exponential complex ity, we should not try to reconstruct a factor of f in Z[x] from sever al factors 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);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#f1G,(*$)%\"xG\"\"#\"\"\"F**&\"\"%F*F(F*F*\")+ j'o%F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "gcd(f,f1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{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)" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "g:=add(g||i * x^i, i=0..6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,0%#g0G\"\"\"*&%#g1GF'%\"xGF'F'*&%#g2GF')F*\"\"#F 'F'*&%#g3GF')F*\"\"$F'F'*&%#g4GF')F*\"\"%F'F'*&%#g5GF')F*\"\"&F'F'*&%# g6GF')F*\"\"'F'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "zero:= rem(g,f1,x)-p^acc*add(R||i*x^i,i=0..degree(f1,x)-1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%zeroG,4*&,.%#g1G\"\"\"*&\")%Gmo%F)%#g3GF)!\"\"*& \"1cy5EyW'>#F)%#g5GF)F)*&\"2C#30\"*)Qdj#F)%#g6GF)F-*&\"*O.$\\PF)%#g4GF )F)*&\"\"%F)%#g2GF)F-F)%\"xGF)F)%#g0GF)*&\")+j'o%F)F9F)F-*&\"1+#HeK\\k >#F)F6F)F)*&\"9+Gl6'=Fv#QRH5F)F3F)F-*&\"2+o21wfrv\"F)F0F)F-*&\"*+_Y(=F )F,F)F)*&\"*,/1/\"F)%#R0GF)F-*(FGF)%#R1GF)F:F)F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "big_number:=10^3; # Other large numbers are a lso fine." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+big_numberG\"%+5" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "zero:=big_number * zero; # r esult is still zero" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%zeroG,4*(\"% +5\"\"\",.%#g1GF(*&\")%Gmo%F(%#g3GF(!\"\"*&\"1cy5EyW'>#F(%#g5GF(F(*&\" 2C#30\"*)Qdj#F(%#g6GF(F.*&\"*O.$\\PF(%#g4GF(F(*&\"\"%F(%#g2GF(F.F(%\"x GF(F(*&F'F(%#g0GF(F(*&\",++Imo%F(F:F(F.*&\"4++?HeK\\k>#F(F7F(F(*&\"<++ !Gl6'=Fv#QRH5F(F4F(F.*&\"5++!o21wfrv\"F(F1F(F.*&\"-++?lu=F(F-F(F(*&\"- +5SgS5F(%#R0GF(F.*(\"-+5SgS5F(%#R1GF(F;F(F." }}}{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 vecto r." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "v:=[seq(g||i,i=0..6), seq(coeff(zero,x,i),i=0..degree(f1,x)-1)];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"vG7+%#g0G%#g1G%#g2G%#g3G%#g4G%#g5G%#g6G,0*&\"%+5\" \"\"F&F0F0*&\",++Imo%F0F(F0!\"\"*&\"4++?HeK\\k>#F0F*F0F0*&\"<++!Gl6'=F v#QRH5F0F,F0F3*&\"5++!o21wfrv\"F0F+F0F3*&\"-++?lu=F0F)F0F0*&\"-+5SgS5F 0%#R0GF0F3,0*&F/F0F'F0F0*&\",+SGmo%F0F)F0F3*&\"4+g&y5EyW'>#F0F+F0F0*& \"5+SA30\"*)Qdj#F0F,F0F3*&\"-+gLI\\PF0F*F0F0*&\"%+SF0F(F0F3*&\"-+5SgS5 F0%#R1GF0F3" }}}{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 := ma p(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 50 "for i from 0 to d do b||i := map(coeff,v,g||i) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b0G7+\"\" \"\"\"!F'F'F'F'F'\"%+5F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b1G7+\" \"!\"\"\"F&F&F&F&F&F&\"%+5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b2G7+ \"\"!F&\"\"\"F&F&F&F&!,++Imo%!%+S" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %#b3G7+\"\"!F&F&\"\"\"F&F&F&\"-++?lu=!,+SGmo%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b4G7+\"\"!F&F&F&\"\"\"F&F&\"4++?HeK\\k>#\"-+gLI\\P" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b5G7+\"\"!F&F&F&F&\"\"\"F&!5++!o2 1wfrv\"\"4+g&y5EyW'>#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b6G7+\"\"! F&F&F&F&F&\"\"\"!<++!Gl6'=Fv#QRH5!5+SA30\"*)Qdj#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "for i from 0 to degree(f1,x)-1 do c||i:=map(c oeff,v,R||i) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#c0G7+\"\"!F&F&F &F&F&F&!-+5SgS5F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#c1G7+\"\"!F&F& F&F&F&F&F&!-+5SgS5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 111 "[seq (b||i,i=0..d),seq(c||i,i=0..degree(f1,x)-1)]; # this spans the lattice , and v is an element of that lattice" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7+7+\"\"\"\"\"!F&F&F&F&F&\"%+5F&7+F&F%F&F&F&F&F&F&F'7+F&F&F%F&F&F&F &!,++Imo%!%+S7+F&F&F&F%F&F&F&\"-++?lu=!,+SGmo%7+F&F&F&F&F%F&F&\"4++?He K\\k>#\"-+gLI\\P7+F&F&F&F&F&F%F&!5++!o21wfrv\"\"4+g&y5EyW'>#7+F&F&F&F& F&F&F%!<++!Gl6'=Fv#QRH5!5+SA30\"*)Qdj#7+F&F&F&F&F&F&F&!-+5SgS5F&7+F&F& F&F&F&F&F&F&F9" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "LLL(%);" } }{PARA 12 "" 1 "" {XPPMATH 20 "6#7+7+!#\\\"\"*\"#9\"#=\"\"(\"\"\"\"\"! F+F+7+\"#\\\"#S\"#E\"\")F*F+F+F+F+7+F+F%F&F'F(F)F*F+F+7+!#5!#_\"#)*!$6 \"!$7\"\"$,#\"$P#F+F+7+!#@!\"(\"#W!$/#\"$%G!$9#\"$X\"F+F+7+!#V!$B\"\"$ m#!$o\"!$1#!$#>!$W$F+F+7+\"#T!$D\"\"$=\"\"$<#!$2&!$*R\"$=$F+F+7+F*F+F+ F+F+F+F+\"%+5F+7+F+F*F+F+F+F+F+F+FS" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7+!# \\\"\"*\"#9\"#=\"\"(\"\"\"\"\"!F,F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "g:=add(v[i+1]*x^i,i=0..d);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.\"#\\!\"\"*&\"\"*\"\"\"%\"xGF*F**&\"#9F*)F+\"\" #F*F**&\"#=F*)F+\"\"$F*F**&\"\"(F*)F+\"\"%F*F**$)F+\"\"&F*F*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "g:=gcd(f,g);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,,\"#\\\"\"\"*&\"#SF'%\"xGF'F'*&\"#EF')F*\" \"#F'F'*&\"\")F')F*\"\"$F'F'*$)F*\"\"%F'F'" }}}{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 "0 1 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }