{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 "" 0 1 0 0 0 0 0 1 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 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 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 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 285 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 1 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 "" 0 256 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 28 "The ring of 10-adic numb ers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 42 "L et a be a positive integer. We know that:" }}{PARA 0 "" 0 "" {TEXT -1 10 "a mod 10^n" }}{PARA 0 "" 0 "" {TEXT -1 39 "is the same as: the las t n digits of a." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 78 "Now, let a be any integer and we will look at the followi ng infinite sequence:" }}{PARA 0 "" 0 "" {TEXT -1 58 "S = ( a mod 10^1 , a mod 10^2, a mod 10^3, a mod 10^4,....)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 114 "Let Z/10^n denote the set of i ntegers modulo 10^n. Then the n'th entry of S can be viewed as an elem ent of Z/10^n." }}{PARA 0 "" 0 "" {TEXT -1 71 "We can view S as an ele ment of the following infinite product of rings:" }}{PARA 0 "" 0 "" {TEXT -1 41 " Z/10^1 * Z/10^2 * Z/10^3 * Z/10^4 * ...." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 133 "Note, however, that when i,j are positive integers and ii) of S modulo 10^i. So we do not consider every element of Z/10 * \+ Z/10^2 * ... but only those that satisfy this relation." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Now define the set \+ " }{TEXT 256 6 "Z_10 " }{TEXT -1 172 "as the set of all elements S of Z/10^1 * Z/10^2 * Z/10^3 * Z/10^4 * .... that have that property, i .e. that if i " 0 "" {MPLTEXT 1 0 15 "-123 mod 10^50;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "Negative integers will at some point have just 9's on the left. Note that " }{TEXT 267 5 "Z_10 " }{TEXT -1 49 " also contains some rational numbers, but not all:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 14 "1/2 mod 10^50;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "r:=1/3 mod 10^50;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "r*3 mod 10^50;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "So we have an element in " }{TEXT 268 5 "Z_10 " }{TEXT -1 157 "con sisting of .....6666667, i.e. one 7 and then infinitely many 6's on t he left of that. Multiplying that element by 3 gives 1, so that elemen t will be 1/3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "The set " }{TEXT 269 6 "Z_10 i" }{TEXT -1 270 "s a ring, n ot a field, because we can not divide by all non-zero elements. We can represent elements by \"integers with infinitely many digits\", or we can also write it as a number with base beta as follows:\nsum_\{n >= \+ 0\} a.n * beta^n where a.n is in the range 0..beta-1" }}{PARA 0 "" 0 "" {TEXT -1 38 "and where beta=10 in the case of Z_10." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "In the same way we can also define " }{TEXT 270 3 "Z_p" }{TEXT -1 27 " as the set of for mal sums:" }}{PARA 0 "" 0 "" {TEXT -1 65 " sum_\{n >= 0\} a.n * p^n \+ where the a.i are in the range 0..p-1." }}{PARA 0 "" 0 "" {TEXT -1 5 "This " }{TEXT 271 3 "Z_p" }{TEXT -1 106 " is called the ring of p-adi c integers. This ring has no zero divisors if and only if p is a prime number." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "When p is a prime number then the fraction field " }{TEXT 272 3 "Q _p" }{TEXT -1 4 " of " }{TEXT 273 3 "Z_p" }{TEXT -1 31 " is the set of all formal sums:" }}{PARA 0 "" 0 "" {TEXT -1 64 "sum_\{n >= -N\} a.n \+ * p^n where the a.i are in the range 0..p-1." }}{PARA 0 "" 0 "" {TEXT -1 9 "This set " }{TEXT 274 4 "Q_p " }{TEXT -1 38 "is called the field of p-adic numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(padic);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r:=eval p(1/3,7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "evalp(3*r,7); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "evalp( 1/20! , 7);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "evalp( 1/20! , 7,20);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evalp(20!*% , 7);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalp( sqrt(2), 7);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "evalp(%^2, 7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evalp( sqrt(3), 7);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "Q_7 does not contain any element whose s quare equals 3. Note that Fp also contains no element whose square equ als 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Now lets look at " }{TEXT 275 5 "Z_10 " }{TEXT -1 85 "again, and cons ider the element r:=1/7, so r is the root of the polynomial 7*x-1 in \+ " }{TEXT 276 5 "Z_10." }{TEXT -1 51 " To determine r in Z_10 is the sa me as determining:" }}{PARA 0 "" 0 "" {TEXT -1 41 "r mod 10^1, r mod 1 0^2, r mod 10^3, ....." }}{PARA 0 "" 0 "" {TEXT -1 21 "Lets do that fo r now:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^1;" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^4;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^6;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/ 7 mod 10^7;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^8 ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^9;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "1/7 mod 10^10;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "1/7 mod 10^11;" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 29 "If r is the exact element in " }{TEXT 277 5 "Z_10 \+ " }{TEXT -1 351 "that is a root of the polynomial 7*x-1, then what we \+ have computed above are approximations of r. First with 1 digit accura te, then with 2 digits accurate, then with 3, up to 11 digits. We have computed r modulo 10^1, then modulo 10^2, then modulo 10^3, etc. Ever y time we got one more digit of the 10-adic number r (which has infini tely many digits)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 386 "But it seems that what we are doing here is not efficien t. When we computed 1/7 mod 10^11 (for which Maple will use igcdex) we only got 1 new digit, all the other ones were already known at that p oint. So the question arises: instead of computing all 11 digits, coul d we not just compute the one new digit, making use of the 10 digits t hat we already knew from the previous computation?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "So, what we want is, give n r modulo 10^n, compute r modulo 10^(n+1). This process is called \+ " }{TEXT 278 15 "HENSEL LIFTING." }}{PARA 0 "" 0 "" {TEXT -1 135 "Then we only need to compute r modulo 10^1, and we can increase the accura cy (compute r modulo a higher power of 10) by Hensel lifting." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 125 "What we \+ are doing is solving the equation 7*x-1 in Z_10. Solving is the same a s factoring the polynomial 7*x-1 into: 7*(x-r)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 118 "Assume that we have fact ored 7*x-1 into the form 7*(x-r) up to accuracy n. That means: we have an integer r such that:" }}{PARA 0 "" 0 "" {TEXT -1 43 "7*x-1 is equi valent to 7*(x-r) modulo 10^n." }}{PARA 0 "" 0 "" {TEXT -1 206 "Now we want to Hensel lift this factorization, which means: we want to incre ase its accuracy n. Lets say we want to lift this equation up to accur acy n+1. That means we have to find an integer r' such that:" }}{PARA 0 "" 0 "" {TEXT -1 48 "7*x-1 is equivalent to 7*(x-r') modulo 10^(n+1) ." }}{PARA 0 "" 0 "" {TEXT -1 171 "The last n digits of r' and r will \+ be the same, we only have to determine 1 new digit. We may assume that r is reduced modulo 10^n (i.e. 0 <= r < 10^n). Now we can write:" }} {PARA 0 "" 0 "" {TEXT -1 15 "r' = r + d*10^n" }}{PARA 0 "" 0 "" {TEXT -1 92 "and what we need to do is compute the number d, which we can ta ke in the range 0..9. We get:" }}{PARA 0 "" 0 "" {TEXT -1 47 "7*x-1 sh ould be 7*(x-r-d*10^n) modulo 10^(n+1)." }}{PARA 0 "" 0 "" {TEXT -1 181 "So: 7*x-1 - 7*(x-r-d*10^n) should be divisible by 10^(n+1), and w e already know that it is divisible by 10^n. So we can divide it by 10 ^n, and then the equation becomes of the form:" }}{PARA 0 "" 0 "" {TEXT -1 29 "a + b*d should be 0 modulo 10" }}{PARA 0 "" 0 "" {TEXT -1 82 "where a and b are integers that we find by computing (7*x-1 -7* (x-r-d*10^n))/10^n." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "n:=11 ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "r:=1/7 mod 10^11;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "r:=r+d*10^n;" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " (r*7-1)/10^n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "solve(%,d) mod 10;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "r:=subs(d=%,r); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "Now we've increased the accur acy from 11 to 12. Lets Hensel lift it further to accuracy 20." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "for n from 12 to 19 do\n r :=r+d*10^n;\n r:=subs(d = solve( (r*7-1)/10^n , d) mod 10, r)\nod; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "1/7 mod 10^n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "Now lets Hensel lift some other factorizations, this time over " }{TEXT 279 4 "Z_7," }{TEXT -1 21 " the 7-adic integers." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=7;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 9 "h:=x^2-2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Factor(h) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=op(1,%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "g:=op(2,%%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Expan d(h-f*g) mod p^1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Expand (h-f*g) mod p^2;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "We will view \+ f,g,h now as polynomials in " }{TEXT 280 3 "Z_7" }{TEXT -1 126 "[x]. A s we see, the product f*g is h up to accuracy 1, but not up to accurac y 2. We will try to Hensel lift the factorization:" }}{PARA 0 "" 0 "" {TEXT -1 8 " h = f*g" }}{PARA 0 "" 0 "" {TEXT -1 68 "That is, suppose \+ that the factorization has accuracy n, which means:" }}{PARA 0 "" 0 " " {TEXT -1 33 "h is equivalent to f*g modulo p^n" }}{PARA 0 "" 0 "" {TEXT -1 58 "Then we want to compute new f and g such that we will get :" }}{PARA 0 "" 0 "" {TEXT -1 38 "h is equivalent to f*g modulo p^(n+1 )." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "And this process converges in the ring " }{TEXT 281 3 "Z_7" }{TEXT -1 87 "[x]. So, after infinitely many steps we would get an exact factorizat ion of h=x^2-2 in " }{TEXT 282 3 "Z_7" }{TEXT -1 4 "[x]." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 241 "How do we Hensel \+ lift the polynomials f and g (which have accuracy n) up to accuracy n+ 1? Since f and g are already correct modulo p^n, we only need to add s omething that is a multiple of p^n, we don't need any lower powers of \+ p. So we take:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "New f := f + f0 * p^n;" }}{PARA 0 "" 0 "" {TEXT -1 19 "Ne w g:=g + g0 *p^n;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 105 "Then we compute h-f*g, divide it by p^n, then equate it \+ to 0 modulo p, and then solve f0 and g0 modulo p." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 291 "for n from 1 to 5 do\n f:=f+f0*p^n;\n g :=g+g0*p^n;\n should_be_zero_modp := expand( (h-f*g)/p^n ) mod p;\n \+ should_be_zero_modp := \{coeffs(should_be_zero_modp,x)\};\n # Solv e this, reduce mod p, and substitute into f and g:\n f,g := op(subs( solve(should_be_zero_modp) mod p, [f,g]))\nod;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(h - f*g);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "% m od p^n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "g;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "r:=x-f;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " r^2 mod p^n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "In general the He nsel lifting procedure works as follows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Suppose f,g,h in " }{TEXT 283 1 "Z " }{TEXT -1 21 "[x] and suppose that:" }}{PARA 0 "" 0 "" {TEXT -1 195 " h is equivalent to f*g modulo p^n where n>=1\nand suppose furtherm ore that f,g,h are monic (i.e. the highest coefficient of f (which is \+ lcoeff(f,x) in Maple) should be 1, and same for g and h)." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "Now suppose furthe rmore that:" }}{PARA 0 "" 0 "" {TEXT -1 15 " Gcd(f,g) mod p" }}{PARA 0 "" 0 "" {TEXT -1 117 "equals 1, so f and g have no common factors in Fp[x] (recall that Fp is the field with p elements, it is Z modulo p) ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "Then , one can find polynomials f0 and g0, such that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "degree(f0,x) < degree(f,x )" }}{PARA 0 "" 0 "" {TEXT -1 26 "degree(g0,x) < degree(g,x)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "(f+f0 * p^n) * \+ (g+g0 * p^n) is equivalent to h modulo p^(n+1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "By repeating this infinit ely many times, one will find polynomials F, G in " }{TEXT 284 3 "Z_p " }{TEXT -1 91 "[x] such that h is exactly (not just modulo some power of p) equal to F*G, and furthermore:" }}{PARA 0 "" 0 "" {TEXT -1 34 " F is equivalent to f modulo p, and" }}{PARA 0 "" 0 "" {TEXT -1 30 "G i s equivalent to g modulo p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "How to find f0 and g0? Well, modulo p^(n+1) we \+ get" }}{PARA 0 "" 0 "" {TEXT -1 111 "(f+f0*p^n)*(g+g0*p^n) - h is \+ f*g-h + p^n*(f0*g + g0*f) + p^(2n)*f0*g0, which is equivalent to (assu me n>=1)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "f*g-h + p^n*(f0*g + g0*f) modulo p^(n+1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "Now compute h-f*g modulo \+ p^(n+1), this must be of the form R*p^n for some R in " }{TEXT 285 1 " Z" }{TEXT -1 38 "[x] because h is f*g up to accuracy n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "Then the equation be comes:" }}{PARA 0 "" 0 "" {TEXT -1 56 "p^n*R = p^n*(f0*g + g0*f) modul o p^(n+1) in other words:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 27 "R = f0*g + g0*f modulo p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 145 "This has a unique soluti on f0 and g0 modulo p (with the conditions on the degree above) that c an be computed by the Extended Euclidean Algorithm." }}{PARA 0 "" 0 " " {TEXT -1 3 "Do:" }}{PARA 0 "" 0 "" {TEXT -1 28 " Gcdex(f,g,x,'s','t' ) mod p;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "then s*f + t*g is 1 mod p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 29 "So: R*t*g + R*s*f is R mod p." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "Now if we take f 0=R*t and g0=R*s then f0, g0 do not necessarily satisfy the degree con ditions (degree(f0) < degree(f) and degree(g0) < degree(g)). So we hav e to reduce R*t to get degree < degree(f,x). So we take:" }}{PARA 0 " " 0 "" {TEXT -1 66 "f0:=Rem(R*t,f,x,'q') mod p; and we'll have degre e(f0) " 0 "" {MPLTEXT 1 0 911 "Hensel_lift := proc(f,g,h ,x,N,p)\n # Input: a positive integer n, and\n # monic polynomials 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 explai ned 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 condit ions,\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:=Ex pand(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 917 "HenselLift:=proc (L::list,h,x::name,N::posint,p::posint)\n # Recursive algorithm for \+ Hensel lifting when there are\n # more than 2 factors. Note: This is not the most efficient\n # way to do it but it's fine for us.\n # \n # Input: a list L=[f1,f2,...fk] of polynomials 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 is h modulo p^n.\n l ocal l,L1,L2,h1,h2;\n l:=nops(L);\n if l=0 then\n ERROR(\"wr ong input\")\n elif l=1 then\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 := c onvert(L1,`*`), convert(L2,`*`);\n # Lift the products:\n \+ h1, h2 := Hensel_lift(h1,h2,h,x,N,p);\n # Lift L1 and L2 and ret urn 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 31 "h:= x^8+2*x^6+37*x^4-36*x^2+324;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "p:=5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "L:=Factors(h) mod p;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "L:=[seq(i[1],i=L [2])];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(L,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(% - h);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "% mod p;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 32 "n:=10; L:=HenselLift(L,h,x,n,p);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "convert(L,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "expand(% - h);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 10 "% mod p^n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 " The Maple function mod always produces non-negative numbers, if a and \+ m are integers and m>0 then:" }}{PARA 0 "" 0 "" {TEXT -1 9 " a mod m; " }}{PARA 0 "" 0 "" {TEXT -1 28 "will be in the range 0..m-1." }} {PARA 0 "" 0 "" {TEXT -1 32 "A very similar function is mods." }} {PARA 0 "" 0 "" {TEXT -1 10 " a mods m;" }}{PARA 0 "" 0 "" {TEXT -1 59 "will produce a number in the range -iquo(m-1,2)..iquo(m,2)" }} {PARA 0 "" 0 "" {TEXT -1 35 "that is equivalent wiht a modulo m." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "If we wan t to obtain factors in " }{TEXT 286 1 "Z" }{TEXT -1 122 "[x] of h then we have to use mods instead of mod, because mod will only produce pos itive numbers, whereas factors of h in " }{TEXT 287 2 "Z[" }{TEXT -1 36 "x] could have negative coefficients." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(0,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(1,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(2,5) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(3,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(4,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "mods(5,5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "L;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "L:=ma p(mods,L,p^n); # same as [seq(mods(i,p^n),i=L)];" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 26 "for i in L do gcd(i,h) od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "We have obtained factors in " }{TEXT 288 3 "Z_5 " }{TEXT -1 124 "[x], i.e. factors with 5-adic coefficients, but it tu rns out that when we mods these factors the results are not factors in " }{TEXT 289 1 "Z" }{TEXT -1 9 "[x] of h." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 53 "But maybe h does not have any f actors of degree 2 in " }{TEXT 290 1 "Z" }{TEXT -1 4 "[x]?" }}{PARA 0 "" 0 "" {TEXT -1 34 "That is very well possible. Since " }{TEXT 291 3 "Z_5" }{TEXT -1 102 " is a larger ring than Z, it is possible that the re are factors of degree 2 in Z_5[x] but not in Z[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 "Does h have any factor s of odd degree in " }{TEXT 292 1 "Z" }{TEXT -1 4 "[x]?" }}{PARA 0 "" 0 "" {TEXT -1 42 "That must be impossible, because if f in " }{TEXT 293 1 "Z" }{TEXT -1 46 "[x] is a factor of h, then we can factor f in \+ " }{TEXT 294 3 "Z_5" }{TEXT -1 120 "[x], and the result should be a su blist of the list L computed above. But we have only even degree facto rs in that list." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "So the conclusion is: either h is irreducible in " } {TEXT 295 1 "Z" }{TEXT -1 247 "[x], or it is a product of two irreduci ble polynomials f and g of degree 4. These f and g (modulo p^n) must b e products of two elements of L. So what we'll do is: take all product s of 2 elements of L, mods them, and check if they're a factor of h." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "possible_factors:=\{seq(s eq(mods(expand(L[i]*L[j]),p^n),i=1+j..4),j=1..4)\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "possible_factors:=\{seq(gcd(i,h),i=possib le_factors)\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "convert(p ossible_factors,`*`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ex pand(%-h);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(h);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "80 8 1" 0 } {VIEWOPTS 1 1 0 1 1 1803 }