{VERSION 5 0 "IBM INTEL LINUX" "5.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 Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 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 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 261 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
262 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 266 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 2 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 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 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 }{PSTYLE "" 0 256 1 {CSTYLE "
" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 
0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 
{CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }2 0 0 -1 -1 -1 0 
0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 }2 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 260 
1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }2 0 0 -1 -1 -1 
0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 261 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 }2 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "m := n^sigma; # blocking factor" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG)%\"nG%&sigmaG" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 35 "s := n^tau; # number of giant steps" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"sG)%\"nG%$tauG" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 49 "r := simplify( (n/m) / s); # number of baby
 steps" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"rG)%\"nG,(\"\"\"F(%&sigm
aG!\"\"%$tauGF*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 256 "
" 0 "" {TEXT -1 79 "Standard matrix arithmetic, quadratic B/M, Chinese
 remainder integer arithmetic" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "
Step 2.1: Compute " }{XPPEDIT 18 0 "B^j y" "6#*&)%\"BG%\"jG\"\"\"%\"yG
F'" }{TEXT -1 2 ", " }{TEXT 256 1 "j" }{TEXT -1 9 " = 0,...," }{TEXT 
257 1 "r" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "substep1 := sim
plify( r * m * n^2 * r );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)subste
p1G)%\"nG,(\"\"%\"\"\"%&sigmaG!\"\"*&\"\"#F)%$tauGF)F+" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 18 "Step 2.2: Compute " }{XPPEDIT 18 0 "Z = B
^r" "6#/%\"ZG)%\"BG%\"rG" }{TEXT -1 21 " by repeated squaring" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "substep2 := simplify( n^3 * \+
r);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)substep2G)%\"nG,(\"\"%\"\"\"
%&sigmaG!\"\"%$tauGF+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Step 2.3
: Compute " }{XPPEDIT 18 0 "x^Tr*Z^k;" "6#*&)%\"xG%#TrG\"\"\")%\"ZG%\"
kGF'" }{TEXT -1 2 ", " }{TEXT 258 1 "k" }{TEXT -1 9 " = 0,...," }
{TEXT 259 2 "s " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "substep3
 := simplify( s * m * n^2 * n/m);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%)substep3G)%\"nG,&%$tauG\"\"\"\"\"$F)" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 19 "Step 2.4: Compute (" }{XPPEDIT 18 0 "x^Tr*Z^k;" "6#*&)%\"
xG%#TrG\"\"\")%\"ZG%\"kGF'" }{TEXT -1 3 ") (" }{XPPEDIT 18 0 "B^j y" "
6#*&)%\"BG%\"jG\"\"\"%\"yGF'" }{TEXT -1 1 ")" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 46 "substep4 := simplify( r * s * m^2 * n * n/m );" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)substep4G*$)%\"nG\"\"$\"\"\"" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "Step 3: Blocked Berlekamp/Massey f
or  " }{TEXT 270 1 "n" }{TEXT -1 7 " moduli" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 39 "step3 := simplify( (n/m)^2 * m^3 * n );" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%&step3G)%\"nG,&\"\"$\"\"\"%&sigmaGF)" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "Step 4: Determinant of generator m
atrix polynomial for " }{TEXT 271 1 "n" }{TEXT -1 7 " moduli" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "step4 := simplify( m^3 * n *
 n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&step4G)%\"nG,&%&sigmaG\"\"
$\"\"#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "Overall bit compl
exity" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "eval([substep1, su
bstep2, substep3, substep4, step3, step4], \{sigma=1/3, tau=1/3\});" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#7(*$)%\"nG\"\"$\"\"\"*$)F&#\"#5F'F(F)
F$F)F$" }}}{EXCHG {PARA 261 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" 
{TEXT -1 2 "``" }{TEXT 267 54 "The asymptotically best algorithms freq
uently turn out" }}{PARA 259 "" 0 "" {TEXT 268 52 "to be worst on all \+
problems for which they are used." }{TEXT -1 2 "''" }}{PARA 260 "" 0 "
" {TEXT -1 4 "--- " }{TEXT 269 37 "D. G. CANTOR and H. ZASSENHAUS (198
1)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 257 "" 0 "" {TEXT -1 29 "F
ast matrix multiplication O(" }{XPPEDIT 18 0 "n^omega" "6#)%\"nG%&omeg
aG" }{TEXT -1 40 "), linear B/M, linear integer arithmetic" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 18 "Step 2.1: Compute " }{XPPEDIT 18 0 "B^j y
" "6#*&)%\"BG%\"jG\"\"\"%\"yGF'" }{TEXT -1 2 ", " }{TEXT 260 1 "j" }
{TEXT -1 9 " = 0,...," }{TEXT 261 2 "r " }{TEXT -1 3 "by " }{XPPEDIT 
18 0 "B^(2^i)" "6#)%\"BG)\"\"#%\"iG" }{TEXT -1 2 " [" }{XPPEDIT 18 0 "
B^0 y" "6#*&%\"BG\"\"!%\"yG\"\"\"" }{TEXT -1 9 " | ... | " }{XPPEDIT 
18 0 "B^(2^i - 1)" "6#)%\"BG,&)\"\"#%\"iG\"\"\"F)!\"\"" }{TEXT -1 3 " \+
y]" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "fastsubstep1 := simpl
ify( n^omega * r );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-fastsubstep1
G)%\"nG,*%&omegaG\"\"\"F)F)%&sigmaG!\"\"%$tauGF+" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 18 "Step 2.2: Compute " }{XPPEDIT 18 0 "Z = B^r" "6#/%
\"ZG)%\"BG%\"rG" }{TEXT -1 21 " by repeated squaring" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 39 "fastsubstep2 := simplify( n^omega * r);" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-fastsubstep2G)%\"nG,*%&omegaG\"\"
\"F)F)%&sigmaG!\"\"%$tauGF+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "St
ep 2.3: Compute " }{XPPEDIT 18 0 "x^Tr*Z^k;" "6#*&)%\"xG%#TrG\"\"\")%
\"ZG%\"kGF'" }{TEXT -1 2 ", " }{TEXT 262 1 "k" }{TEXT -1 9 " = 0,...,
" }{TEXT 263 2 "s " }{TEXT -1 3 "as " }{TEXT 265 3 "fat" }{TEXT -1 17 
" vectors times a " }{TEXT 266 4 "thin" }{TEXT -1 8 " matrix." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "fastsubstep3 := simplify( s \+
* (n/(m*s))^2 * (m*s)^omega * r, 'power', 'symbolic' );" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%-fastsubstep3G)%\"nG,*%$tauG!\"#\"\"$\"\"\"*&F
*F+%&sigmaGF+!\"\"*&,&F-F+F(F+F+%&omegaGF+F+" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 18 "Step 2.3: Compute " }{XPPEDIT 18 0 "x^Tr*Z^k;" "6#*&)%
\"xG%#TrG\"\"\")%\"ZG%\"kGF'" }{TEXT -1 2 ", " }{TEXT 273 1 "k" }
{TEXT -1 9 " = 0,...," }{TEXT 274 2 "s " }{TEXT -1 23 "as rectangular \+
product:" }}{PARA 0 "" 0 "" {TEXT -1 7 "       " }{XPPEDIT 18 0 "s" "6
#%\"sG" }{TEXT -1 10 " parts of " }{XPPEDIT 18 0 "x^Tr" "6#)%\"xG%#TrG
" }{TEXT -1 28 " to make them thin leads to " }{XPPEDIT 18 0 "m*s" "6#
*&%\"mG\"\"\"%\"sGF%" }{TEXT -1 4 " by " }{XPPEDIT 18 0 "n" "6#%\"nG" 
}{TEXT -1 7 " times " }{XPPEDIT 18 0 "n" "6#%\"nG" }{TEXT -1 9 " (name
ly " }{XPPEDIT 18 0 "Z" "6#%\"ZG" }{TEXT -1 20 ") product of length " 
}{XPPEDIT 18 0 "r" "6#%\"rG" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 86 "fastsubstep3 := simplify( s * n^(omega-theta) * (m
*s)^theta * r, 'power', 'symbolic');" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%-fastsubstep3G)%\"nG,,%&omegaG\"\"\"%&thetaG!\"\"*&,&%&sigmaGF)%$t
auGF)F)F*F)F)F)F)F.F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "Step 2.3
: using Huang/Pan " }{XPPEDIT 18 0 "n" "6#%\"nG" }{TEXT -1 4 " by " }
{XPPEDIT 18 0 "b" "6#%\"bG" }{TEXT -1 7 " times " }{XPPEDIT 18 0 "n" "
6#%\"nG" }{TEXT -1 4 " by " }{XPPEDIT 18 0 "n^r" "6#)%\"nG%\"rG" }
{TEXT -1 7 " where " }{XPPEDIT 18 0 "r = sigma+tau" "6#/%\"rG,&%&sigma
G\"\"\"%$tauGF'" }}{PARA 0 "" 0 "" {TEXT -1 15 "(same as above)" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 115 "# fastsubstep3 := simplify(
 s * n^( (2*(1-sigma-tau) + (sigma+tau-zeta)*omega)/(1-zeta) ) * r, 'p
ower','symbolic');" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 19 "Step 2.4: Compute (" }{XPPEDIT 18 0 "x^Tr
*Z^k;" "6#*&)%\"xG%#TrG\"\"\")%\"ZG%\"kGF'" }{TEXT -1 3 ") (" }
{XPPEDIT 18 0 "B^j y" "6#*&)%\"BG%\"jG\"\"\"%\"yGF'" }{TEXT -1 1 ")" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "fastsubstep4 := simplify( \+
r^2/s * (m*s)^omega * n/m, 'power', 'symbolic' );" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%-fastsubstep4G)%\"nG,*\"\"$\"\"\"*&F(F)%&sigmaGF)!\"
\"*&F(F)%$tauGF)F,*&,&F+F)F.F)F)%&omegaGF)F)" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 63 "Step 3: (Displacement complexity) Blocked Berlekamp/Mas
sey for " }{TEXT 264 2 "n " }{TEXT -1 6 "moduli" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 36 "faststep3 := simplify( m^2 * n * n);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%*faststep3G)%\"nG,&%&sigmaG\"\"#F)\"\"\"" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "Step 3: (Gilles) Matrix half GC
D for polys of degree " }{XPPEDIT 18 0 "n" "6#%\"nG" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 62 "faststep3 := simplify(m^omega * n/m * n, \+
'power', 'symbolic');" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*faststep3G
)%\"nG,(*&%&sigmaG\"\"\"%&omegaGF*F*\"\"#F*F)!\"\"" }}}{EXCHG {PARA 0 
"" 0 "" {TEXT -1 76 "Step 4: Leading and constant coefficient of gener
ator matrix polynomial for " }{TEXT 272 1 "n" }{TEXT -1 7 " moduli" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "faststep4 := simplify( m^om
ega * n, 'power', 'symbolic' );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*
faststep4G)%\"nG,&*&%&sigmaG\"\"\"%&omegaGF*F*F*F*" }}}{EXCHG {PARA 0 
"" 0 "" {TEXT -1 22 "Overall bit complexity" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 94 "total := eval([fastsubstep1, fastsubstep2, fastsub
step3, fastsubstep4, faststep3, faststep4]);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%&totalG7()%\"nG,*%&omegaG\"\"\"F*F*%&sigmaG!\"\"%$tau
GF,F&)F',,F)F*%&thetaGF,*&,&F+F*F-F*F*F0F*F*F*F*F+F,)F',*\"\"$F**&F5F*
F+F*F,*&F5F*F-F*F,*&F2F*F)F*F*)F',(*&F+F*F)F*F*\"\"#F*F+F,)F',&F;F*F*F
*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "expos:=simplify(map(x \+
-> log[n](x), total), 'symbolic');" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
>%&exposG7(,*%&omegaG\"\"\"F(F(%&sigmaG!\"\"%$tauGF*F&,.F'F(%&thetaGF*
*&F-F(F)F(F(*&F-F(F+F(F(F(F(F)F*,,\"\"$F(*&F1F(F)F(F**&F1F(F+F(F**&F)F
(F'F(F(*&F'F(F+F(F(,(F4F(\"\"#F(F)F*,&F4F(F(F(" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 45 "expos:=subs(theta=(omega-2)/(1-zeta), expos);
" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&exposG7(,*%&omegaG\"\"\"F(F(%&s
igmaG!\"\"%$tauGF*F&,.F'F(*&,&F'F(\"\"#F*F(,&F(F(%%zetaGF*F*F**(F.F(F0
F*F)F(F(*(F.F(F0F*F+F(F(F(F(F)F*,,\"\"$F(*&F5F(F)F(F**&F5F(F+F(F**&F)F
(F'F(F(*&F'F(F+F(F(,(F8F(F/F(F)F*,&F8F(F(F(" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 51 "parfrac := proc(e) convert(e, parfrac, omega); end
:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 "minsigmatau := map(par
frac,solve(\{expos[2]=expos[3], expos[2]=expos[5]\}, \{sigma,tau\}));
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,minsigmatauG<$/%&sigmaG,&\"\"\"
F)*&,(%&omegaG!\"\"F)F)%%zetaGF)F),*F,!\"#*&F.F)F,F)F-\"\"#F)*$)F,F2F)
F)F-F)/%$tauG*&,&F,F)F2F-F)F/F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 61 "minexpos:=map(parfrac,map(simplify,subs(minsigmatau,expos)));
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%
)minexposG7(,&%&omegaG\"\"\"*&,&F(F(%%zetaG!\"\"F(,*F'!\"#*&F+F(F'F(F,
\"\"#F(*$)F'F0F(F(F,F(F&F&,&F'F(*&,*\"\"$F(*&F6F(F+F(F,F'F,F/F(F(F-F,F
(F&,&F'F(*&,&F'F,F0F(F(F-F,F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 19 "numzeta:=0.2946289;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(numzet
aG$\"(*GYH!\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "numomega:
=2.375477;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)numomegaG$\"(xaP#!\"'
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "minnumexpos:=subs(\{zet
a=numzeta,omega=numomega\}, minexpos);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%,minnumexposG7($\"+MEE(p#!\"*F&F&$\"+H&Rkd#F(F&$\"+uo=/AF(" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "minnumsigmatau:=subs(\{zeta
=numzeta,omega=numomega\}," }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "minsi
gmatau);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%/minnumsigmatauG<$/%&sig
maG$\"+1CCp]!#5/%$tauG$\"+d7!Hr\"F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 15 "Table 1, Line 3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "s
ubs(\{zeta=0\},[minexpos,minsigmatau]);" }}{PARA 12 "" 1 "" {XPPMATH 
20 "6#7$7(,&%&omegaG\"\"\"*&F'F',(F&!\"#\"\"#F'*$)F&F+F'F'!\"\"F'F%F%,
&F&F'*&,&\"\"$F'F&F.F'F)F.F'F%,&F&F'*&,&F&F.F+F'F'F)F.F'<$/%&sigmaG,&F
'F'*&,&F&F.F'F'F'F)F.F'/%$tauG*&,&F&F'F+F.F'F)F." }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 15 "Table 1, Line 5" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 62 "subs(\{zeta=0,omega=evalf(log[2](7))\}, [minexpos,min
sigmatau]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7$7($\"+IttTI!\"*F%F%$
\"+Rv]_GF'F%$\"+J^7=EF'<$/%&sigmaG$\"+9!yQw&!#5/%$tauG$\"+2zH#*=F1" }}
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "T
able 1, Line 6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "subs(\{ze
ta=0,omega=numomega\}, [minexpos,minsigmatau]);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#7$7($\"+-gE@F!\"*F%F%$\"+&=I9f#F'F%$\"+$=TcC#F'<$/%&sig
maG$\"+;=vV_!#5/%$tauG$\"+p\"e$)H\"F1" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 0 "" }{TEXT 276 24 "Division free char poly:" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 66 "Step 4: Char poly: Determinant of generat
or matrix polynomial for " }{TEXT 275 1 "n" }{TEXT -1 7 " moduli" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "charfaststep4 := simplify( m
^omega * n *n, 'power', 'symbolic' );" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#>%.charfaststep4G)%\"nG,&*&%&sigmaG\"\"\"%&omegaGF*F*\"\"#F*" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "Overall bit complexity" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 102 "chartotal := eval([fastsubstep1, f
astsubstep2, fastsubstep3, fastsubstep4, faststep3, charfaststep4]);" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*chartotalG7()%\"nG,*%&omegaG\"\"
\"F*F*%&sigmaG!\"\"%$tauGF,F&)F',,F)F*%&thetaGF,*&,&F+F*F-F*F*F0F*F*F*
F*F+F,)F',*\"\"$F**&F5F*F+F*F,*&F5F*F-F*F,*&F2F*F)F*F*)F',(*&F+F*F)F*F
*\"\"#F*F+F,)F',&F;F*F<F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
64 "charexpos:=simplify(map(x -> log[n](x), chartotal), 'symbolic');" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*charexposG7(,*%&omegaG\"\"\"F(F(%
&sigmaG!\"\"%$tauGF*F&,.F'F(%&thetaGF**&F-F(F)F(F(*&F-F(F+F(F(F(F(F)F*
,,\"\"$F(*&F1F(F)F(F**&F1F(F+F(F**&F)F(F'F(F(*&F'F(F+F(F(,(F4F(\"\"#F(
F)F*,&F4F(F7F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "charexpos
:=subs(theta=(omega-2)/(1-zeta), charexpos);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%*charexposG7(,*%&omegaG\"\"\"F(F(%&sigmaG!\"\"%$tauGF
*F&,.F'F(*&,&F'F(\"\"#F*F(,&F(F(%%zetaGF*F*F**(F.F(F0F*F)F(F(*(F.F(F0F
*F+F(F(F(F(F)F*,,\"\"$F(*&F5F(F)F(F**&F5F(F+F(F**&F)F(F'F(F(*&F'F(F+F(
F(,(F8F(F/F(F)F*,&F8F(F/F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
121 "charminsigmatau := map(parfrac,map(simplify,solve(\{charexpos[2]=
charexpos[3], charexpos[2]=charexpos[6]\}, \{sigma,tau\})));" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%0charminsigmatauG<$/%&sigmaG,&\"\"\"F)*&,(
%&omegaG!\"#\"\"#F)*&F.F)%%zetaGF)F)F),,F)F)F0!\"\"F,F2*$)F,F.F)F)*&F0
F)F,F)F2F2F)/%$tauG*&,&!\"%F)*&F.F)F,F)F)F)F1F2" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 73 "charminexpos:=map(parfrac,map(simplify,subs(ch
arminsigmatau,charexpos)));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%-char
minexposG7(,&%&omegaG\"\"\"*&,&\"\"#F(*&F+F(%%zetaGF(!\"\"F(,,F(F(F-F.
F'F.*$)F'F+F(F(*&F-F(F'F(F.F.F(F&F&,&F'F(*&,*\"\"'F(*&F6F(F-F(F.*&F+F(
F'F(F.*(F+F(F-F(F'F(F(F(F/F.F(,(F'F(F(F.*&,&F'F+*&\"\"%F(F-F(F.F(F/F.F
(F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "charnumzeta:=numzeta
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,charnumzetaG$\"(*GYH!\"(" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "charnumomega:=numomega;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-charnumomegaG$\"(xaP#!\"'" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "charminnumexpos:=subs(\{zeta
=charnumzeta,omega=charnumomega\}, charminexpos);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%0charminnumexposG7($\"+\\U^1G!\"*F&F&$\"+w'pYk#F($\"+
\"\\(*pY#F(F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "charminnum
sigmatau := subs(\{zeta=charnumzeta,omega=charnumomega\}, charminsigma
tau);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%3charminnumsigmatauG<$/%&si
gmaG$\"+vv;&R$!#5/%$tauG$\"+Q*fWH#F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 60 "Comparison of radical to logarithmic factors in running time" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Digits:=50:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "n1:=10000;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#n1G\"&++\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 29 "evalf((log[2](n1)/n1^(1/3)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#$\"S9bJQ[ROMIQik:@ST:,v^S(4w;'!#]" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}
{MARK "74 0 0" 0 }{VIEWOPTS 1 1 0 3 2 1804 1 1 1 1 }{PAGENUMBERS 0 1 
2 33 1 1 }