{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 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 1 1 0 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 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 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 0 }
{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 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 0 }{CSTYLE "" -1 263 "" 0 1 0 0 
0 0 0 1 0 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 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 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 0 }{CSTYLE "" -1 
267 "" 0 1 0 0 0 0 0 1 0 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 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 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 0 }
{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 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 "Heading 1" 0 3 1 {CSTYLE "" -1 -1 
"" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 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 {SECT 0 {PARA 3 "" 0 "" {TEXT -1 33 "Lattice reduction in dime
nsion 2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 263 
7 "Input: " }{TEXT -1 39 "Two linearly independent vectors v1, v2" }}
{PARA 0 "" 0 "" {TEXT 264 7 "Output:" }{TEXT -1 54 " Two vectors w1, w
2 such that  if L = Z*v1 + Z*v2 then" }}{PARA 0 "" 0 "" {TEXT -1 88 " \+
   w1 = a shortest vector in L  (meaning that no vector in L - \{0\}  \+
is shorter than w1)" }}{PARA 0 "" 0 "" {TEXT -1 96 "    w2 = a second-
shortest vector in L  (meaning that no vector in L - Z*w1 is shorter t
han w2)." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1082 "lattice_dim2 :
= proc(v1, v2)\n   local k,w1,w2;\n   w1, w2 := v1, v2;\n   if dot(w2,
w2) < dot(w1,w1) then\n       w1, w2 := w2, w1\n   fi;\n   # At this p
oint, w1 is the shortest of the two input\n   # vectors v1,v2 and w2 i
s the other input vector.\n   do\n      k := choose_k(w1,w2);\n      w
2 := w2 - k*w1;\n      # We picked k in such a way that the angle\n   \+
   # between w2 and w1 would be as close to 90 degrees\n      # as pos
sible.\n      # In dimension 2 this implies (drawing a picture will\n \+
     # help you see why this is true) that after this step,\n      # w
2 must be shorter than w1 unless w1 is the shortest\n      # vector in
 the lattice.  So if w2 is not shorter than\n      # w1, which we test
 in the following \"if\", then w1\n      # is the shortest vector in t
he lattice.\n      if dot(w2,w2) >= dot(w1,w1) then\n          # w1 = \+
shortest, w2 = second shortest\n          return [ w1, w2 ]\n      fi;
\n      # At this point dot(w2,w2) < dot(w1,w1) so\n      # w2 is shor
ter than w1. Now we interchange,\n      # so after this, w1 will be sh
orter than w2\n      w1,w2 := w2,w1\n   od:\nend;" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%-lattice_dim2Gj+6$%#v1G%#v2G6%%\"kG%#w1G%#w2G6\"F-C%>
6$8%8&6$9$9%@$2-%$dotG6$F2F2-F96$F1F1>F06$F2F1?(F-\"\"\"F@F-%%trueGC&>
8$-%)choose_kGF0>F2,&F2F@*&FDF@F1F@!\"\"@$1F;F8O7$F1F2>F0F>F-F-F-6$\"
\"!FQ" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 265 6 "Input:" }{TEXT -1 30 " t
wo vectors (given as lists)\n" }{TEXT 266 7 "Output:" }{TEXT -1 16 " t
he dot-product" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "dot:=proc
(a::list,b::list)\n    local i;\n    add(a[i]*b[i],i=1..nops(a))\nend;
\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$dotGj+6$'%\"aG%%listG'%\"bGF)
6#%\"iG6\"F.-%$addG6$*&&9$6#8$\"\"\"&9%F5F7/F6;F7-%%nopsG6#F4F.F.F.6$
\"\"!F@" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 267 6 "Input:" }{TEXT -1 20 "
 Two vectors v1, v2." }}{PARA 0 "" 0 "" {TEXT 268 7 "Output:" }{TEXT 
-1 21 " integer k such that:" }}{PARA 0 "" 0 "" {TEXT -1 61 "  -1/2 * \+
dot(v1,v1) < dot(v2-k*v1,  v1)  <=  1/2 * dot(v1,v1)" }}{PARA 0 "" 0 "
" {TEXT -1 59 "This means that we choose the integer k in such a way t
hat:" }}{PARA 0 "" 0 "" {TEXT -1 82 "      the angle between  v2-k*v1 \+
  and  v1  is as close to 90 degrees as possible." }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 77 "choose_k := proc(v1,v2)\n  local k,d,dv;\n  \+
round( dot(v2,v1)/dot(v1,v1) )\nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%)choose_kGj+6$%#v1G%#v2G6%%\"kG%\"dG%#dvG6\"F--%&roundG6#*&-%$dotG
6$9%9$\"\"\"-F36$F6F6!\"\"F-F-F-6$\"\"!F<" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT 262 20 "Example application:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 92 "Let r be a rational number, numerator and
 denominator have no more than 30 digits, let m be:" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 12 "m := 101^33;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"mG\"^o,LGhuXXZ()p.,#)fS&3:o2kU\"RqC!3kJ&3!p)Q\"" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "and let r mod m be:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "r_mod_m := 104050679131615278976359
9089118302501036221058130103345411920800046;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%(r_mod_mG\"^oY+!3#>TXL5I\"e5AO5]-$=\"*3*fj(*y_hJ\"z10
/\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Note that m has:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "length(m);" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#\"#n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "digits,
 and we need to find 2 * (less than 30 digits).  So it seems that this
 should be possible." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT 261 10 "Question: " }{TEXT -1 8 " find r." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 8 "Remark: " }{TEXT -1 244 "
 There is a faster algorithm for this particular problem  (see the hel
p page of iratrecon). However, we want to demonstrate how to use the l
attice reduction algorithm, so we will solve this problem using the la
ttice reduction algorithm instead." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 56 "Let's try our implementation on this part
icular example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "v1 := [m
, 0];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v1G7$\"^o,LGhuXXZ()p.,#)fS
&3:o2kU\"RqC!3kJ&3!p)Q\"\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 19 "v2 := [r_mod_m, 1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G7$
\"^oY+!3#>TXL5I\"e5AO5]-$=\"*3*fj(*y_hJ\"z10/\"\"\"\"" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 117 "We have explained before that L := Z*v1 \+
+ Z*v2 is the set of all [a,b] for which a congruent to r_mod_m * b mo
dulo m." }}{PARA 0 "" 0 "" {TEXT -1 30 "So if r = a/b then [a,b] in L.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "Given
 a rational number r=a/b,  define the \"size\" of r as the length of t
he vector [a,b]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lattice
_dim2(v1, v2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7$7$\"=J<L!fV.F$p56K
\"3*!=C\\S1nuw*=(e%eNc$7$!G:[Zz#\\76VO\"))p(e[/m)*>&!H6#H\"=&\\xMLr8zy
^M#QE^K\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "w1, w2 := op(%
):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "We see now that the shortes
t vector in L-\{0\} is w1,  and the shortest vector in L-Z*w1 is w2." 
}}{PARA 0 "" 0 "" {TEXT -1 111 "This means that the rational number of
 smallest \"size\" that is equivalent to r_mod_m modulo m is the follo
wing:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "r1 := w1[1]/w1[2];
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r1G#!=J<L!fV.F$p56K\"3*\"=C\\S1
nuw*=(e%eNc$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "length(nume
r(r1)), length(denom(r1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#GF#" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 100 "Furthermore, the rational numb
er of second-smallest \"size\" that is congruent to r_mod_m modulo m i
s:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "r2 := w2[1]/w2[2];" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r2G#\"G:[Zz#\\76VO\"))p(e[/m)*>&\"
H6#H\"=&\\xMLr8zy^M#QE^K\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 256 73 "It
 is possible to prove that the above algorithm lattice_dim2 is optimal
:" }}{PARA 0 "" 0 "" {TEXT -1 3 "   " }{TEXT 258 56 "lattice_dim2  alw
ays finds a shortest vector w1 in L-\{0\}" }}{PARA 0 "" 0 "" {TEXT -1 
2 "  " }{TEXT 259 40 "as well as a shortest vector in L - Z*w1" }
{TEXT -1 51 "   (which we refer to as a second shortest vector)." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 535 "For a lo
ng time, it was not known how to generalize this to higher dimension. \+
 The algorithm given by Lenstra, Lenstra, and Lovasz in their paper fr
om 1983 was a breakthrough. They gave an algorithm that worked very we
ll, and were able to prove that, although their algorithm for dimensio
n > 2 is not optimal, they could prove that it was almost-optimal, in \+
the sense that the k-th vector in the output of their algorithm was no
 longer than 2^((n-1)/2) times the k-th shortest vector, where n = dim
ension(L). And that's good enough in " }{TEXT 257 4 "many" }{TEXT -1 
14 " applications." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 125 "The running time of the LLL depends polynomially on the \+
dimension n, as well as on the number of digits in the input vectors.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 187 "It w
as later proven that an optimal algorithm for arbitrary dimension n, i
.e. an algorithm that is proven to produce the shortest vector, is an \+
NP-hard problem.  An NP-hard problem means:" }}{PARA 0 "" 0 "" {TEXT 
-1 99 "   *)  At the moment nobody can give an algorithm that is faste
r than an exponential function in n." }}{PARA 0 "" 0 "" {TEXT -1 80 " \+
  *)  It is generally believed that a polynomial time algorithm does n
ot exist." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
135 "Of course: exponential in n is not a problem when n=2.  So you sh
ould not be surprised that a simple optimal algorithm exists when n=2.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "Thus \+
the situation is:   it is believed that an " }{TEXT 269 17 "optimal al
gorithm" }{TEXT -1 1 " " }{TEXT 270 23 "would be extremely slow" }
{TEXT -1 79 "  (exponential time as a function of n),  and Lenstra, Le
nstra, Lovasz gave an " }{TEXT 271 53 "almost-optimal algorithm that r
uns in polynomial time" }{TEXT -1 682 ". In Maple we can reduce lattic
es of dimension 100 in just an hour or so. But the development did not
 stop, there now exist very fast lattice-reduction algorithms that can
 reduce lattices of dimension somewhere around 1000. Again, this will \+
produce an \"almost\" shortest vector.  Nobody has any real hope of fi
nding \"the\" shortest vector in lattices of high dimension because no
body has any real hope that NP-hard problems can be solved when n is l
arge: It is widely believed that no polynomial-time solution can exist
 for NP-hard problems, however, attempts to prove this have not been s
uccessful. The million-dollar prize that was put on this will likely n
ot change this situation." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 35 "La
ttice reduction in dimension >= 2" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 92 "Read chapter 16 of the book Modern Comput
er Algebra for an explanation of the LLL algorithm." }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "You can view Maple's im
plementation as follows:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "
interface(verboseproc=2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "op(IntegerRelations:-LLL);
" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#j+6#'%\"LG<$%$setG%%listG63%\"bG%#
bsG%\"BG%#BeG%\"hG%\"iG%\"jG%\"kG%\"lG%#muG%\"MG%\"nG%\"NG%\"uG%$blaG%
'othersG%(OptionsG6$%)rememberG%aoCopyright~(c)~1991~by~the~University
~of~Waterloo.~All~rights~reserved.G6\"C8>8,9$>837#-%/ProcessOptionsG6&
\"\"\"7#9\"T#84@$0FE7\"Y6$Q9unexpected~option(s):~%0F?-%#opG6#FE>8/-%%
nopsG6#FB>8$-%&ArrayG6#;FJFY>8%Fin>8&Fin>81-Fjn6$F\\o;FJ,&FYFJFJ!\"\">
8.-%'MatrixG6$FB/%%fillG.82@&4-%%typeG6$Fio.-F[p6#%(numericGYQ2invalid
~argumentsF?34&FN6#.%(integerG2-__%.LinearAlgebraG%(LA_MainG%%RankG6#F
ioFYYQCthe~vectors~are~linearly~dependentF?-%)userinfoG6&FJ.T%%Cstarti
ng~lattice~reduction~at~timeG-%%timeGF?@$F^qC%>FB-T'Fiq-F]r6&FJF_r%Dfi
nishing~lattice~reduction~at~timeGFbrO-%(convertG6$FB%)listlistG-F]r6%
FJF_r%Pperforming~reductions~using~rational~arithmeticG?(8)FJFJFY%%tru
eG>&Fhn6#Fes&Fio6$Fes;FJFgo>80-_Ffq%0ColumnDimensionGFiq?(FesFJFJFYFfs
C%>&F^oFisFhs?(8*FJFJ,&FesFJFJFgoFfsC$>&Fbo6$FesFgt*&-F^s6$7#-%$seqG6$
*&&Fhs6#8+FJ&&F^o6#FgtFfuFJ/Fgu;FJF^t%\"+GFJ&F`oFjuFgo>Fet-_Feq%*Vecto
rAddG6(FetFiuFJ,$F[uFgo/.%(inplaceG%&falseG/.%.outputoptionsGFQ>&F`oFi
s-F^s6$7#-Fbu6$*$)&FetFfu\"\"#FJF[vF]v>FguFfw?(F?FJFJF?1FguFYC$-T)6&Fh
nFboFgu,&FguFJFJFgo@%1*&,&#\"\"$\"\"%FJ*$)&Fbo6$FguF^xFfwFJFgoFJ&F`o6#
F^xFJ&F`oFfuC$?(Fes,&FguFJFfwFgoFgoFJFfs-F\\x6&FhnFboFguFes>Fgu,&FguFJ
FJFJC.>8-Fhx>8',&F\\yFJ*&)FfyFfwFJFjxFJFJ>Fhx*(FfyFJFjxFJFhyFgo>F\\y*(
FjxFJF\\yFJFhyFgo>FjxFhy>8(&FhnF[y>Fcz&FhnFfu>FezFbz-F]r6%FfwF_r-%$cat
G6&.%0Interchanging~vGF^x.%'~and~vGFgu?(FgtFJFJF_yFfsC%>Fbz&Fbo6$F^xFg
t>Fc[l&Fbo6$FguFgt>Ff[lFbz?(FesFcyFJFYFfsC%>Fbz&Fbo6$FesFgu>F\\\\l,&&F
bo6$FesF^xFJ*&FfyFJF\\\\lFJFgo>F`\\l,&*&FhxFJF\\\\lFJFJFbzFJ@$2FfwFgu>
FguF^x>Fes.Fes>Fgt.FgtFir7#-%\"$G6$.-F^s6$Fhs.F)/FesF\\oF?F?6*%,LLLDef
aultsG%,LLLDefaultsG%$LLLG%$LLLG%+LLLIntegerG%+LLLIntegerG%'NewMusG%'N
ewMusG6#!+E$R>\"=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 197 "The above p
rocedure uses computations with rational numbers. There is also a modi
fication of the LLL algorithm that only performs computations with int
egers, and does not use any rational numbers. " }}}}}{MARK "0 1 0" 0 }
{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }