{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 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 1 {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_dim2GR6$%#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-" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT 265 6 "Input:" }{TEXT -1 30 " two vectors
 (given as lists)\n" }{TEXT 266 7 "Output:" }{TEXT -1 16 " the dot-pro
duct" }}}{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#>%$dotGR6$'%\"aG%%listG'%\"bGF)6#%\"iG
6\"F.-%$addG6$*&&9$6#8$\"\"\"&9%F5F7/F6;F7-%%nopsG6#F4F.F.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 " integ
er 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 that:" }}
{PARA 0 "" 0 "" {TEXT -1 82 "      the angle between  v2-k*v1   and  v
1  is as close to 90 degrees as possible." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 98 "choose_k := proc(v1,v2)\n  local k,d,dv;\n  dv := d
ot(v1,v1);\n  d  := dot(v2,v1);\n  iquo(d, dv)\nend;" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#>%)choose_kGR6$%#v1G%#v2G6%%\"kG%\"dG%#dvG6\"F-C%>8&
-%$dotG6$9$F4>8%-F26$9%F4-%%iquoG6$F6F0F-F-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$\"GYl!)pGf\"QOV#*>!pwXg')*>&\"H(GC<\"G+rVTy1K
a4BQE^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 "" {TEXT -1 100 "Furthermore, the
 rational number of second-smallest \"size\" that is congruent to r_mo
d_m modulo m is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "r2 := w
2[1]/w2[2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r2G#\"GYl!)pGf\"QOV#
*>!pwXg')*>&\"H(GC<\"G+rVTy1Ka4BQE^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 "l
attice_dim2  always 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 vec
tor)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 535 
"For a long time, it was not known how to generalize this to higher di
mension.  The algorithm given by Lenstra, Lenstra, and Lovasz in their
 paper from 1983 was a breakthrough. They gave an algorithm that worke
d very well, and were able to prove that, although their algorithm for
 dimension > 2 is not optimal, they could prove that it was almost-opt
imal, in the sense that the k-th vector in the output of their algorit
hm was no longer than 2^((n-1)/2) times the k-th shortest vector, wher
e n = dimension(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 polynomial
ly 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 was later proven that an optimal algorithm for arbitrary dimen
sion n, i.e. an algorithm that is proven to produce the shortest vecto
r, 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 faster than an exponential function in n." }}{PARA 0 "" 0 "" {TEXT 
-1 80 "   *)  It is generally believed that a polynomial time algorith
m does not 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 should 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 "o
ptimal algorithm" }{TEXT -1 1 " " }{TEXT 270 23 "would be extremely sl
ow" }{TEXT -1 79 "  (exponential time as a function of n),  and Lenstr
a, Lenstra, Lovasz gave an " }{TEXT 271 53 "almost-optimal algorithm t
hat runs in polynomial time" }{TEXT -1 682 ". In Maple we can reduce l
attices of dimension 100 in just an hour or so. But the development di
d not stop, there now exist very fast lattice-reduction algorithms tha
t can reduce lattices of dimension somewhere around 1000. Again, this \+
will produce an \"almost\" shortest vector.  Nobody has any real hope \+
of finding \"the\" shortest vector in lattices of high dimension becau
se nobody has any real hope that NP-hard problems can be solved when n
 is large: It is widely believed that no polynomial-time solution can \+
exist for NP-hard problems, however, attempts to prove this have not b
een successful. The million-dollar prize that was put on this will lik
ely not change this situation." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 
35 "Lattice reduction in dimension >= 2" }}{PARA 0 "" 0 "" {TEXT -1 0 
"" }}{PARA 0 "" 0 "" {TEXT -1 68 "Read chapter 16 of the book for an e
xplanation of the LLL algorithm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 47 "You can view Maple's implementation as fo
llows:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verbosep
roc=2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "op(lattice);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#R6\"61%\"bG%#bsG%\"BG%#BeG%\"hG%\"iG%
\"jG%\"kG%\"lG%#muG%\"MG%\"nG%\"NG%$optG%\"uG6$%)rememberG%aoCopyright
~(c)~1991~by~the~University~of~Waterloo.~All~rights~reserved.GF$C8@'/9
#\"\"\">8,9\"/F;\"\"#C%>F>&F?6#F<>81&F?6#FA@$4-%'memberG6$FG<#.%(integ
erGYQ/invalid~option6\"YQ3too~many~argumentsFT@$4-%%typeG6$F><$.%$setG
.%%listGYQ2invalid~argumentsFT>8/-%%nopsG6#F>>8$-%&arrayG6#;F<F^o>8%Fd
o>8&Fdo>82-Feo6$Fgo;F<,&F^oF<F<!\"\"?(8)F<F<F^o%%trueGC$@'-FZ6$&F>6#Fd
pFin>&FcoF[q-Feo6#Fjp-FZ6$Fjp-.FeoFE>F]q-%%copyGF_q-%&ERRORG6#.%8wrong
~type~of~argumentsG@&/FdpF<>80-&%'linalgG6#.%(vectdimG6#F]q0F`rF_rFgq>
Fdp.Fdp>8*.F[s>8.-Feo6#7#-%\"$G6$.-%(convertG6$F]qFin/FdpFgo@&4-FZ6$F^
s.-%'matrixG6#%(numericGYF\\o30FGFP2-&Fbr6#.%%rankG6#F^sF^oYQCthe~vect
ors~are~linearly~dependentFT-%)userinfoG6&F<.%(latticeG%Cstarting~latt
ice~reduction~at~timeG-%%timeGF$@$/FGFPC%>F>-%0lattice/integerG6#-%%ev
alGF\\u-F`u6&F<Fbu%Dfinishing~lattice~reduction~at~timeGFeu-%'RETURNG6
#-Fgs6$F>%)listlistG-F`u6%F<Fbu%Pperforming~reductions~using~rational~
arithmeticG?(FdpF<F<F^oFepC%>&FioF[q-F_vFfr?(F[sF<F<,&FdpF<F<FbpFepC$>
&F]p6$FdpF[s*&-Fgs6$7#-%$seqG6$*&&F]q6#8+F<&&Fio6#F[sF`xF</Fax;F<F_r%
\"+GF<&F[pFdxFbp>F_w-&Fbr6#.%'mataddG6&F_wFcxF<,$FewFbp>&F[pF[q-Fgs6$7
#-F\\x6$*$)&F_wF`xFAF<FexFgx>FaxFA?(F$F<F<F$1FaxF^oC$-%/lattice/newmus
G6&-%#opG6#Fco-Fcz6#F]pFax,&FaxF<F<Fbp@%1*&,&#\"\"$\"\"%F<*$)&F]p6$Fax
FgzFAF<FbpF<&F[p6#FgzF<&F[pF`xC$?(Fdp,&FaxF<FAFbpFbpF<Fep-F`z6&FbzFezF
axFdp>Fax,&FaxF<F<F<C.>8-Fa[l>8',&Fe[lF<*&)F_\\lFAF<Fc[lF<F<>Fa[l*&*&F
_\\lF<Fc[lF<F<Fa\\lFbp>Fe[l*&*&Fc[lF<Fe[lF<F<Fa\\lFbp>Fc[lFa\\l>8(-F_v
6#&FcoFd[l>F`]l-F_v6#&FcoF`x>Fd]l-F_v6#F]]l-F`u6%FAFbu-%$catG6&.%0Inte
rchanging~vGFgz.%'~and~vGFax?(F[sF<F<Fh[lFepC%>F]]l&F]p6$FgzF[s>Fd^l&F
]p6$FaxF[s>Fg^lF]]l?(FdpF\\\\lF<F^oFepC%>F]]l&F]p6$FdpFax>F]_l,&&F]p6$
FdpFgzF<*&F_\\lF<F]_lF<Fbp>Fa_l,&*&Fa[lF<F]_lF<F<F]]lF<@$2FAFax>FaxFgz
>FdpFir>F[sF\\sF`vFasF$F$F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 232 "T
he above procedure uses computations with rational numbers. There is a
lso a modification of the LLL algorithm that only performs computation
s with integers, and does not use any rational numbers. This leads to \+
faster running times:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "op
(`lattice/integer`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#R6$%#AAG%#UUG6
:%\"iG%\"jG%\"nG%\"mG%\"AG%\"BG%\"lG%\"tG%#ddG%\"kG%\"rG%\"dG%\"cG%#d0
G%#d1G%#d2G%\"qG%%flagG%%kmaxG%\"UG%&A1adjG%#jjG%%colsG%%rowsG6#%fnCop
yright~(c)~1997~Waterloo~Maple~Inc.~All~rights~reserved.G6\"C0>8&-&%'l
inalgG6#.%'rowdimG6#9$>8'-&FH6#.%'coldimGFL-%)userinfoG6%\"\"#.%(latti
ceG%;constructing~work~matricesG>8(-%&arrayG6$;\"\"\"FE;F\\oFO>8)-Fin6
$F[oF[o?(8$F\\oF\\oFE%%trueG?(8%F\\oF\\oFOFdo>&Fgn6$FcoFfo&FMFio>8/-Fi
n6$;\"\"!FE7$F\\o-%$addG6$*$)&Fgn6$F\\o8*FXF\\o/FipF]o-FV6%F\\oFY%4beg
inning~reductionG>8-FX>86F\\o>85Fdo?(FBF\\oF\\oFB2F_q,&FEF\\oF\\oF\\oC
)@$2FaqF_qC&?(FcoF\\oF\\oF_qFdoC%>8+-Fcp6$*&&Fgn6$FcoFipF\\o&Fgn6$F_qF
ipF\\oFjp?(FipF\\oF\\o,&FcoF\\oF\\o!\"\"Fdo>F^r-%%iquoG6$,&*&F^rF\\o&F
\\p6#FipF\\oF\\o*&&F_o6$FipFcoF\\o&F_o6$FipF_qF\\oFhr&F\\p6#,&FipF\\oF
\\oFhr@%/FcoF_q>&F\\p6#F_qF^r>&F_o6$FcoF_qF^r@$/F\\tF`pYQDthe~ivectors
~are~linearly~dependant6\">Faq,&FaqF\\oF\\oF\\o-FV6%FXFY(%0reached~col
umn~GFaq?(Fco,&F_qF\\oF\\oFhrFhrF\\oFcqC(>8.-%%modsG6$F_t&F\\p6#Fco>84
-F[s6$,&F_tF\\oF`uFhrFdu@$/FguF`p\\?(FfoF\\oF\\oFOFdo>&Fgn6$F_qFfo,&F`
vF\\o*&FguF\\oFhoF\\oFhr?(FfoF\\oF\\oFgrFdo>&F_o6$FfoF_q,&FfvF\\o*&Fgu
F\\o&F_o6$FfoFcoF\\oFhr>F_tF`u>81F\\t>82&F\\p6#F]u>83&F\\p6#,&F_qF\\oF
XFhr>80&F_o6$F]uF_q@%2,$*&F^wF\\oFdwF\\oFX*$)F`wFXF\\oC)>8,-F[s6$,&F_x
F\\o*$)FiwFXF\\oF\\oF`w-FV6%\"\"$FY(%2switching~at~row~GF_q?(FfoF\\oF
\\oFOFdoC%>F^rF`v>F`v&Fgn6$F]uFfo>FcyF^r?(FcoF\\oF\\oFgwFdoC%>F^r&F_o6
$FcoF]u>FiyF_t>F_tF^r?(Ffo,&F_qF\\oF\\oF\\oF\\oFaqFdoC%>F^r&F_oFdy>Faz
-F[s6$,&*&&F_oFavF\\oFdwF\\oF\\o*&FiwF\\oFazF\\oF\\oF`w>Fgz-F[s6$,&*&F
^rF\\oFdxF\\oF\\oFhzFhrFdw>FawFdx@%2FXF_qC$>F_qF]u>Fcq%&falseG>FcqFdoC
$>F_qF^z>FcqFdo@$/9#FXC&>87F`o-%3linalg/det/ipseudoG6+FMFEFO.F^r8;8:88
Fdo.F\\p?(FfoF\\oF\\oFEFdoC$>89&Fc\\l6#Ffo?(FcoF\\oF\\oFEFdo>&F^\\l6$F
coFj\\l*&-Fcp6$*&&Fgn6$Fco&Fd\\lF]tF\\o&Fe\\lFavF\\o/F_qF[oF\\oF\\pFhr
>9%-%%evalG6#F^\\l-F]^l6#FgnFBFBFB" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 114 "To understand how the algorithm works, don't spend too much ti
me reading the above code. Instead, read chapter 16." }}}}}{MARK "0" 
0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }