{VERSION 4 0 "SUN SPARC SOLARIS" "4.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 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 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 1 {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!\"*$!+330KF6^$$\"+#>\\zE\"F)$!+iN@99F)^$FB$\"+iN@99F)^$$\"+330 KZF)FD^$FJFG" }}}{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 mini mum 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[minp oly](alpha,3)); # search minpoly of degree 3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,*!&Ho\"\"\"\"*&\"&uC\"F'%\"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 factor" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "g:=su bs(_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 need to set Digits to a higher value for this to work, but in this example Digits=10 was suff icient. The number of Digits that we need depends on the degree and on the size of the coefficients (which can be bounded by the Landau-Mign otte 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 the example we tried d \+ = 2, 3 and 4) that has coefficients g0,...,gd that have absolute value <= B(d,Digits). The polynomial g that the algorithms searches should \+ have a root that is close to alpha, or in other words g(alpha) is clos e 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,Digit s) on the coefficients of g depends on the accuracy (=Digits) of the r oot alpha, and on the degree bound d. Of course B(d,Digits) will be an increasing function of d and Digits. If g has degree d and if the coe fficients of g are large, then minpoly(alpha,d) will only find g if Di gits is sufficiently high. This is obvious, when there are many digits in g, we can not expect to reconstruct them all if we don't have enou gh 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 f ind a Z-linear relation between: alpha^0, alpha^1, ..., alpha^d. If B \+ is the bound on the coefficients g0,..,gd in Z of this relation, then \+ alpha needs to have at least a certain accuracy Digits, that depends o n B." }}{PARA 0 "" 0 "" {TEXT -1 297 "This Z-linear relation is only a pproximate because alpha is not exact. So what we are really looking f or is not that (*) is exactly equal to zero, we search for \"small\" i ntegers 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 t hat the problem above, to find small integers g0,..,gd such that (*) i s close to 0, can be reduced to the following problem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 269 58 "(**) Given a lattic e, find a short vector in this lattice." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 270 139 "Definition: A latti ce L is a subset of R^n that can be written as Z*b1+Z*b2+..+Z*bn, wher e b1,..,bn in R^n are linearly independent over R." }}{PARA 0 "" 0 "" {TEXT -1 87 "The b1,..,bn is called a basis of the lattice, and n is c alled the rank of the lattice." }}{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 (Lenstr a, Lenstra and Lovasz). We will not describe the algorithm here, but o nly that we can use the algorithm in Maple with the following commands :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "read lib(lattice): # Load the command in Maple." }}{PARA 0 "" 0 "" {TEXT -1 54 "v:=lattice(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..b n 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 the problem (**)? We need t hat 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 b e 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 wh ich we placed the lattice. We can make it into a lattice by adding ano ther 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 26 "latti ce([b0,b1,b2,b3,b4]);" }}{PARA 8 "" 1 "" {TEXT -1 38 "Error, (in latti ce) 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 26 "lattice([b0,b1,b2,b3,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 911 "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) 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 # 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;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,Hensel_liftGR6(%\"f G%\"gG%\"hG%\"xG%\"NG%\"pG6+%\"sG%\"tG%#f0G%#g0G%\"RG%\"qG%\"FG%\"GG% \"nG6\"F7C&@$0-%$modG6$-%&GcdexG6'9$9%9'.8$.8%9)\"\"\"-%&ERRORG6#QCf~a nd~g~should~have~Gcd~1~modulo~p6\">6$8*8+6$FAFB?(8,FIFI,&9(FIFI!\"\"%% trueGC'>8(*&-F<6$-%'ExpandG6#,&9&FI*&FQFIFRFIFX)FH,&FUFIFIFIFI)FHFUFX> 6$8&8'6$*&FfnFIFGFI*&FfnFIFEFI>Feo-F<6$-%$RemG6&FeoFAFC.8)FH>Ffo-F<6$- F[o6#,&FfoFI*&FapFIFBFIFIFH>FP6$,&FQFI*&FeoFIFboFIFI,&FRFI*&FfoFIFboFI FIFPF7F7F7" }}}{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 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 t hen\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;" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%+HenselLiftGR6''%\"LG%%listG%\"hG'% \"xG%%nameG'%\"NG%'posintG'%\"pGF06'%\"lG%#L1G%#L2G%#h1G%#h2G6\"F9C$>8 $-%%nopsG6#9$@)/F<\"\"!-%&ERRORG6#Q,wrong~input6\"/F<\"\"\"7#9%/F<\"\" #7#-%,Hensel_liftG6'-%#opGF?FL9&9'9(C&>6$8%8&6$&F@6#;FJ-%%iquoG6$F6$8'8(6$-%(convertG6$Fen%\"*G-Fio6$FfnF[p>Fdo-FQ 6(FeoFfoFLFUFVFW7$-FT6#-9!6'FenFeoFUFVFW-FT6#-Fep6'FfnFfoFUFVFWF9F9F9 " }}}{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 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7$\"\"\"7(7$,(*$)%\"xG\"\"#F &F&*&\"#&*F&F,F&F&\"#\")F&F&7$,(F*F&*&\"\"%F&F,F&F&\"#LF&F&7$,(F*F&*&F 4F&F,F&F&\"#yF&F&7$,(F*F&*&F/F&F,F&F&\"#OF&F&7$,(F*F&*&\"#AF&F,F&F&\"# " 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+\"#\")F+,(F'F+*&\" \"%F+F)F+F+\"#LF+,(F'F+*&F1F+F)F+F+\"#yF+,(F'F+*&F-F+F)F+F+\"#OF+,(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+*&\"*&RgS5F+F)F+F+\").j'o%F+,(F'F+*&\"\"% F+F)F+F+\")6T>dF+,(F'F+*&F1F+F)F+F+\")+j'o%F+,(F'F+*&F-F+F)F+F+\")9T>d F+,(F'F+*&\")@?`KF+F)F+F+\");?`KF+,(F'F+*&\")%QG:(F+F)F+F+\")z$G:(F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Now the previous method for fac toring f worked as follows:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 214 "subsets:=proc(L)\n # Input: list or set.\n # Output: list of al l subsets.\n local e,R,i;\n if nops(L)=0 then\n [ \{\} ]\n else \n e:=L[1]:\n R:=procname(L[2..-1]);\n [op(R), seq(i union \{e\},i=R)]\n fi\nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(subsets GR6#%\"LG6%%\"eG%\"RG%\"iG6\"F,@%/-%%nopsG6#9$\"\"!7#<\"C%>8$&F26#\"\" \">8%-9!6#&F26#;\"\"#!\"\"7$-%#opG6#F=-%$seqG6$-%&unionG6$8&<#F8/FPF=F ,F,F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "monic_factors:=\{s eq(gcd(f,mods(expand(convert(S,`*`)),p^acc)), S=subsets(v))\};" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%.monic_factorsG<*\"\"\",4*$)%\"xG\" \")F&F&*&\"\"%F&)F*\"\"(F&!\"\"*&\"#=F&)F*\"\"'F&F0*&\"#[F&)F*\"\"&F&F &*&\"$T#F&)F*F-F&F&*&\"$+$F&)F*\"\"$F&F0*&\"$'**F&)F*\"\"#F&F&*&\"%%= \"F&F*F&F0\"%7VF&,4F(F&*&F+F&F.F&F0*&F4F&F3F&F&*&\"#%)F&F7F&F&*&\"$J\" F&F;F&F0*&\"$/#F&F>F&F0*&\"%O7F&FBF&F&*&\"%+;F&F*F&F0\"%W6F&,,*$F;F&F& *&F-F&F>F&F&*&FCF&FBF&F&*&F-F&F*F&F0\"#8F&,,\"#\\F&*&\"#SF&F*F&F&*&\"# EF&FBF&F&*&F+F&F>F&F&FVF&,,FVF&*&\"#7F&F>F&F0*&\"#_F&FBF&F&*&\"#'*F&F* F&F0\"#))F&,4F(F&*&F^oF&F.F&F&*&\"#gF&F3F&F&*&\"$c\"F&F7F&F&*&\"$U#F&F ;F&F&*&\"$w#F&F>F&F&*&F]pF&FBF&F&*&\"$C$F&F*F&F&\"$P'F&,:*$)F*F^oF&F&* &\"#KF&)F*\"#5F&F0*&\"#OF&)F*\"\"*F&F0*&\"$E%F&F)F&F&*&\"$!yF&F.F&F&*& \"$[\"F&F3F&F0*&\"%g=F&F7F&F&*&\"%,fF&F;F&F&*&\"%'*pF&F>F&F&*&\"&3j#F& FBF&F&*&\"&SE$F&F*F&F0\"&cg&F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "However, this method is exponential in n, where n is the number of fa ctors 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 complexity, we should not t ry to reconstruct a factor of f in Z[x] from several factors of f in Q p[x], we should reconstruct a factor of f in Z[x] from just 1 factor i n 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*!\"\"\").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 s ee 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 i n Z" }}{PARA 0 "" 0 "" {TEXT -1 23 "such that f1 divides g." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 211 "Lets assume th at 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 lower 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 i f 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 can 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'*&%#g4 GF')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\"\"\"*&\")ni'o%F)%#g3GF)!\"\"*&\"1\"QG`HXk>#F)%#g5GF)F)*&\"2Y D]Jf1O&RF)%#g6GF)F)*&\"*?aRi&F)%#g4GF)F-*&\"\"'F)%#g2GF)F)F)%\"xGF)F)% #g0GF)*&\").j'o%F)F9F)F-*&\"1,4qp'[k>#F)F6F)F)*&\"9VaW)Q%yL2FRH5F)F3F) F-*&\"2gA`fTRdj#F)F0F)F)*&\"*=y>\"GF)F,F)F-*&\"*,/1/\"F)%#R0GF)F-*(FGF )%#R1GF)F:F)F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "big_numbe r:=10^3; # Other large numbers are also fine." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+big_numberG\"%+5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "zero:=big_number * zero; # result is still zero" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%%zeroG,4*&,.%#g1G\"\"\"*&\")ni'o%F)% #g3GF)!\"\"*&\"1\"QG`HXk>#F)%#g5GF)F)*&\"2YD]Jf1O&RF)%#g6GF)F)*&\"*?aR i&F)%#g4GF)F-*&\"\"'F)%#g2GF)F)F)%\"xGF)\"%+5*&F;F)%#g0GF)F)*&\",+IImo %F)F9F)F-*&\"4+5!4qp'[k>#F)F6F)F)*&\"<+IWX%)Q%yL2FRH5F)F3F)F-*&\"5++EK &fTRdj#F)F0F)F)*&\"-+!=y>\"GF)F,F)F-*&\"-+5SgS5F)%#R0GF)F-*(\"-+5SgS5F )%#R1GF)F:F)F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "Now we will con sider 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 64 "v:=[seq(g||i,i=0..6), seq(coeff(zero,x,i),i=0..deg ree(f1,x)-1)];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"vG7+%#g0G%#g1G%# g2G%#g3G%#g4G%#g5G%#g6G,0F&\"%+5*&\",+IImo%\"\"\"F(F1!\"\"*&\"4+5!4qp' [k>#F1F*F1F1*&\"<+IWX%)Q%yL2FRH5F1F,F1F2*&\"5++EK&fTRdj#F1F+F1F1*&\"-+ !=y>\"GF1F)F1F2*&\"-+5SgS5F1%#R0GF1F2,0F'F.*&\",+qEmo%F1F)F1F2*&\"4+5Q G`HXk>#F1F+F1F1*&\"5+ga-:$f1O&RF1F,F1F1*&\"-++U&Ri&F1F*F1F2*&\"%+gF1F( F1F1*&\"-+5SgS5F1%#R1GF1F2" }}}{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 th e 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&!,+IImo%\"%+g" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b3G7+\"\"!F&F&\"\"\"F&F&F&!-+!=y>\"G!,+qEmo%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b4G7+\"\"!F&F&F&\"\"\"F&F&\"4+5!4qp '[k>#!-++U&Ri&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#b5G7+\"\"!F&F&F&F &\"\"\"F&\"5++EK&fTRdj#\"4+5QG`HXk>#" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%#b6G7+\"\"!F&F&F&F&F&\"\"\"!<+IWX%)Q%yL2FRH5\"5+ga-:$f1O&R" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "for i from 0 to degree(f1,x) -1 do c||i:=map(coeff,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&!,+IImo%\"%+g7+F&F&F&F%F&F&F&!-+!=y>\"G!,+qEmo %7+F&F&F&F&F%F&F&\"4+5!4qp'[k>#!-++U&Ri&7+F&F&F&F&F&F%F&\"5++EK&fTRdj# \"4+5QG`HXk>#7+F&F&F&F&F&F&F%!<+IWX%)Q%yL2FRH5\"5+ga-:$f1O&R7+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 11 "lattice(%);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7+7+\" #))!\")!#W\"#S!#6\"\"\"\"\"!F+F+7+F+F%F&F'F(F)F*F+F+7+F%F&\"#W!#c\"#TF )F*F+F+7+!#8!#a\"#KF2\"#=\"#t!#%*F+F+7+!#S!\"'!$b\"!$j\"!$8\"!$T#!$=\" F+F+7+\"#?\"$/\"\"$?\"!$6\"!$$QF0!$.\"F+F+7+\"\"&!$4\"!$f\"!$5$F?\"$'G \"$P\"F+F+7+F*F+F+F+F+F+F+\"%+5F+7+F+F*F+F+F+F+F+F+FO" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7+\"#))!\")!#W\"#S!#6\"\"\"\"\"!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,.\"#))\"\"\"*&\"\")F'%\"xGF'!\" \"*&\"#WF')F*\"\"#F'F+*&\"#SF')F*\"\"$F'F'*&\"#6F')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,,*$)%\"xG\"\"%\"\"\"F**&\"#7F*) F(\"\"$F*!\"\"*&\"#_F*)F(\"\"#F*F**&\"#'*F*F(F*F/\"#))F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 420 "So we constructed a factor g from just 1 p-adic factor, not fr om several. The combinatorial explosion (the exponentially many subset s S) doesn't appear in this approach. Because of that, this approach d oes not exponential complexity, one can show that the complexity is po lynomial. Nevertheless, in practical examples (i.e. examples that we c an handle on a normal computer) it is \"never\" faster than the defau lt method." }}}}}{MARK "1" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }