{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 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal " -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 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 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 46 "General st rategy of solving problems with LLL." }}{PARA 0 "" 0 "" {TEXT -1 1 " \+ " }}{PARA 0 "" 0 "" {TEXT -1 134 "Given a problem P that looks like a \+ somewhat linear problem. How to solve it with LLL (lattice reduction). Here is a general strategy." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 "Step 1. Figure out a vector v such that if you knew v, then you'd be able to solve the problem." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 486 "Step 2. Find a lattice \+ L such that v is in L. Construct L in such a way that it is likely th at v is the shortest non-zero vector in L. Note that if v has length | |v||, then the only way that v can possibly be the shortest vector in L is when det(L) > ||v||^n where n=rank(L). We want to make it like ly that v is the shortest vector in L and that all vectors in L outsid e of Z*v are a good deal longer than v. To make this likely, we have to make sure that det(L) is large enough." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 288 "Step 3. Use the LLL algorithm to find a short vector in L. If the vectors outside of Z*v are suff iciently much longer than v (LLL is garuanteed to find the shortest v ector whenever the second shortest vector is at least 2^((n-1)/2) time s longer) then LLL will find the vector v or -v." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 74 "Step 4. Read off the ans wer of your problem from the vector found by LLL." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "Example:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 " c is a rational number, and its numerator and denomin ator have no more than 30 digits." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 9 "Now m is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "m := 13^60;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG \"^o,kj1jW/mO(*4$32PXinSW.K8'>y$*oWF " 0 "" {MPLTEXT 1 0 75 "c_m := 680367523923950392141152223233556311131653231110632798400 0266346089;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$c_mG\"^o*3YjE+S)zK16 JKlJ6JcNBBA:T@R]R#R_n.o" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Questi on: What is c?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 42 "OK, lets apply the general strategy above." }}{PARA 0 "" 0 "" {TEXT -1 103 "Step 1. Let v = [a, b] where a,b are integers suc h that c = a/b. Clearly, if we knew v, we'd have c." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 136 "Step 2. L = \{ [a b] \+ | a is congruent to b * c_m modulo m \}.\nNow we have to feed L to \+ the LLL algorithm (called \"lattice\" in Maple)." }}{PARA 0 "" 0 "" {TEXT -1 136 "The probability that a random vector is in L is 1/m beca use if you have random numbers, the chance that they are congruent mod m is 1/m." }}{PARA 0 "" 0 "" {TEXT -1 18 "Hence, det(L) = m." }} {PARA 0 "" 0 "" {TEXT -1 44 "Now we have the following two elements of L:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "v1 := [m , 0]:" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "v2 := [c_m , 1]:" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 199 "And so we have a sublattice Z*v1 \+ + Z*v2 of L. This sublattice has determinant m*1 - 0*c_m = m. So it ha s the same determinant as L, but it is a sublattice, so it must be equ al to L: Z*v1+Z*v2 = L." }}{PARA 0 "" 0 "" {TEXT -1 107 "Hence v1, \+ v2 is a basis of L. In order to tell Maple which lattice we want to \+ \"LLL\", we need such a basis." }}{PARA 0 "" 0 "" {TEXT -1 32 "How big is the determinant of L?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evalf(m);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+trPko\"#d" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 233 "the numbers a,b we want to determ ine have <30 digits, so 2 * less than 30, that's less than 60, and m \+ has 67 digits, so we should have a good chance of finding a,b, it woul d seem that det(L) is big enough. So here is our basis of L:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "L := [ v1, v2]:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "and now we compute a new basis:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "with(IntegerRelations):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "L := LLL(L);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"LG7$7$\":#=;#G$*pw*=(e%eN!=J " 0 "" {MPLTEXT 1 0 10 " v := L[1]:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "and v = [a, b] whe re c = a/b, so we have:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " c := v[1]/v[2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"cG#!:#=;#G$*pw* =(e%eN\"=J " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 1 0" 1 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }