{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 "" 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 0 ""
}}{PARA 0 "" 0 "" {TEXT -1 134 "Given a problem P that looks like a so
mewhat linear problem. How to solve it with LLL (lattice reduction). H
ere 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 k
new 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 16 "L := lattice(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
] where 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 8 0" 196 }{VIEWOPTS 1 1 0 1 1 1803 1 1
1 1 }{PAGENUMBERS 0 1 2 33 1 1 }