{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 1 }{PSTYLE "Normal
" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }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 1 }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 1 }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 1 }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 67 "Given a fl
oating point complex number, find its minimal polynomial." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "restart; " }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 13 "Digits := 40;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%'DigitsG\"#S" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "alpha := .
002753340381990234990115493078115778952576 + 1.14504730312692296514767
7457351240915890*I;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&alphaG^$$\"I
wD&*yd6yI\\:,*\\B!*>QSLv#!#U$\"I!*e\"4C^tXxw9lH#p7.t/X6!#R" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 51 "This alpha is a solution of a polynomial \+
g in Z[x]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 42 "Given to you is the following information:" }}{PARA 0 "" 0 "" 
{TEXT -1 16 "  degree(g) < 8." }}{PARA 0 "" 0 "" {TEXT -1 54 "  coeffi
cients of g have absolute value less than 300." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 164 "Find such polynomial g. \+
  Of course g(alpha) should be 0, but we only know 40 digits of alpha,
 so g(alpha) will not necessarily be equal to 0, just very close to 0.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "g := add(c[i] * x^i, i=
0..7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,2&%\"cG6#\"\"!\"\"\"*
&&F'6#F*F*%\"xGF*F**&&F'6#\"\"#F*)F.F2F*F**&&F'6#\"\"$F*)F.F7F*F**&&F'
6#\"\"%F*)F.F<F*F**&&F'6#\"\"&F*)F.FAF*F**&&F'6#\"\"'F*)F.FFF*F**&&F'6
#\"\"(F*)F.FKF*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "We have the \+
following equation for our 8 unknowns c0 .. c7 in Z." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 84 "subs(x=alpha,g) = 0;  # Note: Make sure t
hat Digits >= 40 so we don't loose accuracy" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#/,2&%\"cG6#\"\"!\"\"\"*&^$$\"IwD&*yd6yI\\:,*\\B!*>QSLv#
!#U$\"I!*e\"4C^tXxw9lH#p7.t/X6!#RF)&F&6#F)F)F)*&^$$!Ic?OB&y(o'*>X(3.)
\\^Xd768F1$\"I0+x9t(33L?AY4uwz&*4aI'F.F)&F&6#\"\"#F)F)*&^$$!INO'f0](*z
]x'*RfV[G\"o*H3\"!#T$!I\"*emIl\\V_a<_@UB-QOG,:F1F)&F&6#\"\"$F)F)*&^$$
\"Ix%>Edc,>Rp%\\vuuNi4,><F1$!IacxB(>gJdAaEq'fQmqV`;FAF)&F&6#\"\"%F)F)*
&^$$\"Ifzak7t]=7qit:'HP)ecmBFA$\"I'p))G9Yd&=_')*eLgU<M.$o>F1F)&F&6#\"
\"&F)F)*&^$$!I.*e5v)*)*\\VzEh]$Ret_t`AF1$\"I%>t%zat$p>Y(o>.%>.zq<D$FAF
)&F&6#\"\"'F)F)*&^$$!Iz;mR%4Z*G\">=#Q\"e\\xShRM%FA$!Io38ZtLA<#RZAJ+hY'
Ra!e#F1F)&F&6#\"\"(F)F)F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 49 "We c
an split this up into two seperate equations:" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 25 "vars:=\{seq(c[i],i=0..7)\};" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%%varsG<*&%\"cG6#\"\"!&F'6#\"\"\"&F'6#\"\"#&F'6#\"\"$&
F'6#\"\"%&F'6#\"\"&&F'6#\"\"'&F'6#\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 42 "eq1 := collect(subs(x=alpha,g), vars, Re);" }}{PARA 
12 "" 1 "" {XPPMATH 20 "6#>%$eq1G,2&%\"cG6#\"\"!\"\"\"*&$\"IwD&*yd6yI
\\:,*\\B!*>QSLv#!#UF*&F'6#F*F*F**&$\"Ic?OB&y(o'*>X(3.)\\^Xd768!#RF*&F'
6#\"\"#F*!\"\"*&$\"INO'f0](*z]x'*RfV[G\"o*H3\"!#TF*&F'6#\"\"$F*F8*&$\"
Ix%>Edc,>Rp%\\vuuNi4,><F4F*&F'6#\"\"%F*F**&$\"Ifzak7t]=7qit:'HP)ecmBF<
F*&F'6#\"\"&F*F**&$\"I.*e5v)*)*\\VzEh]$Ret_t`AF4F*&F'6#\"\"'F*F8*&$\"I
z;mR%4Z*G\">=#Q\"e\\xShRM%F<F*&F'6#\"\"(F*F8" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 42 "eq2 := collect(subs(x=alpha,g), vars, Im);" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$eq2G,0*&$\"I!*e\"4C^tXxw9lH#p7.t/X6
!#R\"\"\"&%\"cG6#F*F*F**&$\"I0+x9t(33L?AY4uwz&*4aI'!#UF*&F,6#\"\"#F*F*
*&$\"I\"*emIl\\V_a<_@UB-QOG,:F)F*&F,6#\"\"$F*!\"\"*&$\"IacxB(>gJdAaEq'
fQmqV`;!#TF*&F,6#\"\"%F*F;*&$\"I'p))G9Yd&=_')*eLgU<M.$o>F)F*&F,6#\"\"&
F*F**&$\"I%>t%zat$p>Y(o>.%>.zq<D$F?F*&F,6#\"\"'F*F**&$\"Io38ZtLA<#RZAJ
+hY'Ra!e#F)F*&F,6#\"\"(F*F;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "Th
e matrix for these equations is:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 66 "M := matrix(2,8,[seq( [seq(coeff(j,c[i]),i=0..7)], j=
[eq1,eq2])]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"MGK%'matrixG6#7$7
*\"\"\"$\"IwD&*yd6yI\\:,*\\B!*>QSLv#!#U$!Ic?OB&y(o'*>X(3.)\\^Xd768!#R$
!INO'f0](*z]x'*RfV[G\"o*H3\"!#T$\"Ix%>Edc,>Rp%\\vuuNi4,><F0$\"Ifzak7t]
=7qit:'HP)ecmBF3$!I.*e5v)*)*\\VzEh]$Ret_t`AF0$!Iz;mR%4Z*G\">=#Q\"e\\xS
hRM%F37*\"\"!$\"I!*e\"4C^tXxw9lH#p7.t/X6F0$\"I0+x9t(33L?AY4uwz&*4aI'F-
$!I\"*emIl\\V_a<_@UB-QOG,:F0$!IacxB(>gJdAaEq'fQmqV`;F3$\"I'p))G9Yd&=_'
)*eLgU<M.$o>F0$\"I%>t%zat$p>Y(o>.%>.zq<D$F3$!Io38ZtLA<#RZAJ+hY'Ra!e#F0
Q(pprint06\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "The matrix is a b
it difficult to read like this, to display it more clearly use:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "old_digits := Digits; Digits
:=5;map(evalf,M); Digits:=old_digits;" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#>%+old_digitsG\"#S" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'DigitsG\"
\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#K%'matrixG6#7$7*$\"\"\"\"\"!$\"
&Lv#!\"($!&6J\"!\"%$!&I3\"!\"'$\"&!><F0$\"&mO#F3$!&PD#F0$!&SM%F37*$F*F
*$\"&]9\"F0$\"&aI'F-$!&8]\"F0$!&Ml\"F3$\"&$o>F0$\"&=D$F3$!&0e#F0Q(ppri
nt16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'DigitsG\"#S" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 36 "Now lets look at the solutions of M:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "sol:=linalg[linsolve](M,[0,0
]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$solGK%'vectorG6#7*&%#_tG6#\"
\"\"&F*6#\"\"#&F*6#\"\"$&F*6#\"\"%&F*6#\"\"&&F*6#\"\"',.*&$\"I%)o#**Rc
<`P,\"y*omO!R4+OW!#SF,F)F,F,*&$\"ITmnu([TW]z?qn=?qL$3Ht!#UF,F-F,!\"\"*
&$\"If$HEl&3_s<kPc5C8&)ei;eF@F,F0F,FE*&$\"IUi!=**oOjj\\3f$3%\\()yIkS'F
DF,F3F,F,*&$\"IO@-Ayn<G(\\^y)f9/A*oni(F@F,F6F,F,*&$\"I\"z0(*=$*\\X4*oN
=[SO0`\"**>%FDF,F9F,FE,.*&$\"I.MLz<Da(***fZH\"[HVv3jV%F@F,F-F,F,*&$\"I
M&Qd?OZPI+e`_vl*G(\\h)[FDF,F0F,FE*&$\"Ill1'H6CXl)y[![j*z\\\\*o\"eF@F,F
3F,FE*&$\"IS8$yu#yDe@'*HIHP8OCD.KFDF,F6F,F,*&$\"I\"[A`YNKr#)fP!>#=F\\J
Xpi(F@F,F9F,F,*&$\"I;;\"Qo$z#f\")3Bv\"*p**>y^)*e&FDF,F)F,F,Q(pprint26
\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 174 "This isn't helpful at all.
 How are we going to find values for the following variables _t1, _t2,
 .. in such a way that all 8 entries (which are: c[0],..,c[7]) are int
egers???" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
143 "It's easy to make sure that the first 6 entries (c[0] .. c[5]  = \+
 _t1 .. _t6) are integers, but the last two c[6],c[7] need to be integ
ers too." }}{PARA 0 "" 0 "" {TEXT -1 124 "You can try all you want, bu
t with standard linear algebra methods you can't find an integer solut
ion \"sol\" of the matrix M." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT -1 40 "We're going to need something different." }}
{PARA 0 "" 0 "" {TEXT -1 120 "We want:  eq1 to be very close to 0     \+
 (in theory we want eq1 = 0 but due to round off errors we can't hope \+
for that)." }}{PARA 0 "" 0 "" {TEXT -1 3 "Now" }}{PARA 0 "" 0 "" 
{TEXT -1 57 "     eq1 is very close to 0     <====>   C * eq1 is small
" }}{PARA 0 "" 0 "" {TEXT -1 27 "where C is some big number." }}{PARA 
0 "" 0 "" {TEXT -1 151 "Lets take C = 10^40 because we had 40 digits a
ccurate.  Then the digits after the decimal point in C*eq1 are not acc
urate, so we may round to integers." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 15 "C := 10^Digits;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"CG\"J++++++++++++++++++++\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 36 "eq1 := collect( C*eq1, vars, round);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%$eq1G,2*&\"J++++++++++++++++++++\"\"\"\"&%\"cG6#\"\"!
F(F(*&\"GE&*yd6yI\\:,*\\B!*>QSLv#F(&F*6#F(F(F(*&\"Jg0iL_y(o'*>X(3.)\\^
Xd768F(&F*6#\"\"#F(!\"\"*&\"Hkjf0](*z]x'*RfV[G\"o*H3\"F(&F*6#\"\"$F(F6
*&\"JqZ>Edc,>Rp%\\vuuNi4,><F(&F*6#\"\"%F(F(*&\"H'zak7t]=7qit:'HP)ecmBF
(&F*6#\"\"&F(F(*&\"JI!*e5v)*)*\\VzEh]$Ret_t`AF(&F*6#\"\"'F(F6*&\"Hoh'R
%4Z*G\">=#Q\"e\\xShRM%F(&F*6#\"\"(F(F6" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 36 "eq2 := collect( C*eq2, vars, round);" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#>%$eq2G,0*&\"J+*e\"4C^tXxw9lH#p7.t/X6\"\"\"&%\"cG6
#F(F(F(*&\"G+x9t(33L?AY4uwz&*4aI'F(&F*6#\"\"#F(F(*&\"J5*emIl\\V_a<_@UB
-QOG,:F(&F*6#\"\"$F(!\"\"*&\"HlvPs>gJdAaEq'fQmqV`;F(&F*6#\"\"%F(F6*&\"
Jgp))G9Yd&=_')*eLgU<M.$o>F(&F*6#\"\"&F(F(*&\"H>t%zat$p>Y(o>.%>.zq<D$F(
&F*6#\"\"'F(F(*&\"J!o38ZtLA<#RZAJ+hY'Ra!e#F(&F*6#\"\"(F(F6" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 187 "Now we no longer want eq1 = eq2 = 0,  we
 just want eq1 and eq2 to be small integers.  We also want c0 .. c7 to
 be small. In other words, we want the following vector to have small \+
length:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "v := [ seq(c[i],
 i=0..7), eq1, eq2 ];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"vG7,&%\"c
G6#\"\"!&F'6#\"\"\"&F'6#\"\"#&F'6#\"\"$&F'6#\"\"%&F'6#\"\"&&F'6#\"\"'&
F'6#\"\"(,2*&\"J++++++++++++++++++++\"F,F&F,F,*&\"GE&*yd6yI\\:,*\\B!*>
QSLv#F,F*F,F,*&\"Jg0iL_y(o'*>X(3.)\\^Xd768F,F-F,!\"\"*&\"Hkjf0](*z]x'*
RfV[G\"o*H3\"F,F0F,FF*&\"JqZ>Edc,>Rp%\\vuuNi4,><F,F3F,F,*&\"H'zak7t]=7
qit:'HP)ecmBF,F6F,F,*&\"JI!*e5v)*)*\\VzEh]$Ret_t`AF,F9F,FF*&\"Hoh'R%4Z
*G\">=#Q\"e\\xShRM%F,F<F,FF,0*&\"J+*e\"4C^tXxw9lH#p7.t/X6F,F*F,F,*&\"G
+x9t(33L?AY4uwz&*4aI'F,F-F,F,*&\"J5*emIl\\V_a<_@UB-QOG,:F,F0F,FF*&\"Hl
vPs>gJdAaEq'fQmqV`;F,F3F,FF*&\"Jgp))G9Yd&=_')*eLgU<M.$o>F,F6F,F,*&\"H>
t%zat$p>Y(o>.%>.zq<D$F,F9F,F,*&\"J!o38ZtLA<#RZAJ+hY'Ra!e#F,F<F,FF" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "So the question now is:  How do we
 find integers c0..c7 such that the length of v is small?" }}{PARA 0 "
" 0 "" {TEXT -1 31 "If we can accomplish that then:" }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 84 "  c0 .. c7   (the coeff
icients of g) are small integers   (which is what we wanted)." }}
{PARA 0 "" 0 "" {TEXT -1 79 "  eq1, eq2 are small integers,  which imp
lies that g(alpha) is very close to 0." }}{PARA 0 "" 0 "" {TEXT -1 0 "
" }}{PARA 0 "" 0 "" {TEXT -1 36 "So then the problem would be solved.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "Now v
 is a linear combination of the following 8 vectors:" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 56 "for i from 0 to 7 do\n  V[i] := map( coef
f, v, c[i] )\nod;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"!7,
\"\"\"F'F'F'F'F'F'F'\"J++++++++++++++++++++\"F'" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%\"VG6#\"\"\"7,\"\"!F'F)F)F)F)F)F)\"GE&*yd6yI\\:,*\\B
!*>QSLv#\"J+*e\"4C^tXxw9lH#p7.t/X6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
>&%\"VG6#\"\"#7,\"\"!F)\"\"\"F)F)F)F)F)!Jg0iL_y(o'*>X(3.)\\^Xd768\"G+x
9t(33L?AY4uwz&*4aI'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"$7
,\"\"!F)F)\"\"\"F)F)F)F)!Hkjf0](*z]x'*RfV[G\"o*H3\"!J5*emIl\\V_a<_@UB-
QOG,:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"%7,\"\"!F)F)F)\"
\"\"F)F)F)\"JqZ>Edc,>Rp%\\vuuNi4,><!HlvPs>gJdAaEq'fQmqV`;" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"&7,\"\"!F)F)F)F)\"\"\"F)F)\"H'zak7
t]=7qit:'HP)ecmB\"Jgp))G9Yd&=_')*eLgU<M.$o>" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%\"VG6#\"\"'7,\"\"!F)F)F)F)F)\"\"\"F)!JI!*e5v)*)*\\Vz
Eh]$Ret_t`A\"H>t%zat$p>Y(o>.%>.zq<D$" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>&%\"VG6#\"\"(7,\"\"!F)F)F)F)F)F)\"\"\"!Hoh'R%4Z*G\">=#Q\"e\\xShRM%!
J!o38ZtLA<#RZAJ+hY'Ra!e#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "Hence
 v is an element of  L := Z*V0 + .. + Z*V7." }}{PARA 0 "" 0 "" {TEXT 
-1 33 "We have the following basis of L:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 31 "basis_L := [seq(V[i], i=0..7)]:" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 155 "Unfortunately, all our basis elements have very l
ong length  (they all have lenght around 10^40,   but we want length s
omewhere in the 10^2 or 10^3 range)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" 
}}{PARA 0 "" 0 "" {TEXT -1 108 "Lets compute a new basis of the same L
 using the LLL algorithm, also called the lattice-reduction algorithm.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "with(IntegerRelations);
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%%$LLLG%1LinearDependencyG%%PSLQG
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "new_L := LLL(basis_L);
" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&new_LG7*7,\"$]\"\"$\"H!\"&\"#$)
!$N#!$H$!$5\"!$q\"!$?$\"$:$7,!$+\"!$%>\"#?!#B\"$X\"\"$2#\"#b\"#&)\"$?'
\"$q)7,\"$+$\"$K'\"#()\"$J\"!$2&!$8(!$0$!$S$\"%g8!$I'7,!0H)GFh3w7!/bPR
HrkH!/Uz!GMG@%!/#o%Q#y3=)!/^<]f`x[!/dCK>^tU!/I9S$))H%p\"./P!zPx6!.wdf^
Q\\#\".DClgd(=7,\"/TNSFGd\"*\"/')y)G(R.R\"/(>mA^$Q\")\"/EdN\\j)G\"!/Oh
_k_%f%\"/MJ[>h.!*!/nL%H4RB%\"/VrqHzXy!.=1)=$*>Q\".23l9\"o;7,!0cT]^E'>:
\"/bpofiXU\"/#Rzs+2P'\"0>Ca/#)fV\"\"/F4%f:L*e\"/;9r1$H:\"!/+_j3$f*e!/+
k9tK(o&!.!ewu')zd!.&e*zd/$[7,!/1iMCq<C\"/2A%\\Z(4\"*!0Wlg%QMZ<!/C2#)*[
D=#!/ev1](zl*\"/x'R\\gF(p\"/T+/Y?:;\"0-^vO%*p1\"\".CfW\"z0&)\".\\sb4N(
H7,!/_1)RU(Rz\"0R6%prig?\"0xnaY!Q==!0)*3hh.^'G\"0\\yRh5R%=!0LUH\\')H@
\"!.CV\\2Y>$\"0W8$zP?[;!.Wfp!Hr**\"/R&3Ua-W\"" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 142 "The improved basis, found by the LLL (Lenstra, Lenstr
a, Lovasz) algorithm finds 3 short vectors. Lets determine the corresp
onding polynomials:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "v1,v
2,v3 := new_L[1], new_L[2], new_L[3]:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 31 "g1 := add(v1[i+1]*x^i, i=0..7);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#g1G,2\"$]\"\"\"\"*&\"$\"HF'%\"xGF'F'*&\"\"&F')F*\"\"
#F'!\"\"*&\"#$)F')F*\"\"$F'F'*&\"$N#F')F*\"\"%F'F/*&\"$H$F')F*F,F'F/*&
\"$5\"F')F*\"\"'F'F/*&\"$q\"F')F*\"\"(F'F/" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 31 "g2 := add(v2[i+1]*x^i, i=0..7);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%#g2G,2\"$+\"!\"\"*&\"$%>\"\"\"%\"xGF*F'*&\"#?F*)F+
\"\"#F*F**&\"#BF*)F+\"\"$F*F'*&\"$X\"F*)F+\"\"%F*F**&\"$2#F*)F+\"\"&F*
F**&\"#bF*)F+\"\"'F*F**&\"#&)F*)F+\"\"(F*F*" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 31 "g3 := add(v3[i+1]*x^i, i=0..7);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%#g3G,2\"$+$\"\"\"*&\"$K'F'%\"xGF'F'*&\"#()F')F*\"\"
#F'F'*&\"$J\"F')F*\"\"$F'F'*&\"$2&F')F*\"\"%F'!\"\"*&\"$8(F')F*\"\"&F'
F7*&\"$0$F')F*\"\"'F'F7*&\"$S$F')F*\"\"(F'F7" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 20 "and lets check them:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 17 "subs(x=alpha,g1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
^$$!#Y!#R$\"\"!F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "subs(x
=alpha,g2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#^$$\"#t!#R$\"\"\"!#P" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "subs(x=alpha,g3);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#^$$\"#6!#Q$\"\"$!#P" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 141 "So they all seem to have alpha as a root (at l
east up to very high accuracy). But if g1, g2 both have alpha as a roo
t, then so does their gcd" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
16 "g := gcd(g1,g2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.\"#]!
\"\"*&\"#(*\"\"\"%\"xGF*F'*&\"#NF*)F+\"\"#F*F**&\"#PF*)F+\"\"$F*F**&\"
#bF*)F+\"\"%F*F**&\"#&)F*)F+\"\"&F*F*" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 16 "g := gcd(g, g3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%\"gG,.\"#]!\"\"*&\"#(*\"\"\"%\"xGF*F'*&\"#NF*)F+\"\"#F*F**&\"#PF*)F+
\"\"$F*F**&\"#bF*)F+\"\"%F*F**&\"#&)F*)F+\"\"&F*F*" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 16 "subs(x=alpha,g);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#^$$\"$0\"!#R$\"\"$!#P" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 536 "and there we have the polynomial g we're looking for.  We only
 knew that deg(g) < 8.  And we found 3 short vectors. Had we known tha
t deg(g) < 6, then we would have only found one short vector.  Because
 our degree-bound was too high, we found solutions g1,g2,g3 that were \+
not the minimal polynomials of alpha. However, they were multiples of \+
the minimal polynomial. Getting the minimal polynomial itself was then
 simply a matter of taking the gcd   (or, we could of course also have
 redone all of the work but then using that deg(g)<6)." }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 192 "Why is it that ther
e were 3 linearly independent short vectors? Well, because there are 3
 linearly independent polynomials of degree < 8 that have alpha as a s
olution, for example these three:" }}{PARA 0 "" 0 "" {TEXT -1 28 "    \+
g,   x*g,   and x^2 * g." }}{PARA 0 "" 0 "" {TEXT -1 81 "The span of t
he three short vectors corresponds to the span of   g,  x*g,  x^2*g." 
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 250 "Note that the three short vectors  (whos
e span gives us the span of  g, x*g, x^2*g)  are much shorter than the
 other vectors.  This means that the determinant of the lattice was mu
ch bigger than it needed to be for LLL to give us these three vectors.
" }}{PARA 0 "" 0 "" {TEXT -1 181 "LLL can successfully find the \"vect
ors we want\" whenever the \"vectors we want\" are about 2^(n/2) times
 smaller than the \"vectors we don't want\".  But they're much smaller
 than that:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "LENGTH := pr
oc(w)  evalf( sqrt(add(i^2,i=w))) end;" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%'LENGTHGj+6#%\"wG6\"F(F(-%&evalfG6#-%%sqrtG6#-%$addG6$*$)%\"iG
\"\"#\"\"\"/F49$F(F(F(6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "
These were the lengths of the elements in the basis of L we constructe
d:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Digits:=5;" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%'DigitsG\"\"&" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 20 "map(LENGTH,basis_L);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#7*$\"&++\"\"#O$\"&]9\"F&$\"&6J\"F&$\"&8]\"F&$\"&\"><F&$\"&&o>F&$
\"&SD#F&$\"&4e#F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "and these ar
e the lengths of the elements of the new basis, that was constructed b
y LLL:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "map(LENGTH, new_L
);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7*$\"&C@(!\"#$\"&V7\"!\"\"$\"&D$
>F)$\"&>'=\"#5$\"&x'=F.$\"&%[CF.$\"&ac#F.$\"&-!\\F." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 10 "%[4]/%[3];" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#$\"&Zj*\"\"'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evalf
(2^(8/2));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"#;\"\"!" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 236 "So the \"vectors we don't want\" are aro
und 10^11 times bigger than the \"vectors we do want\". But they only \+
need to be about 16 times bigger in order for LLL to successfully sepa
rate \"the vectors we want\" from \"the vectors we don't want\"." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "So if the
se last 5 vectors were about this many times smaller:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "s := %%/%;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"sG$\"&<-'\"\"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
171 "then LLL would still have been able to compute the \"vectors we w
ant\" for us.  We have 5 of these \"vectors we don't want\". So if the
 determinant had been this much smaller:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 4 "s^5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&w\"z\"#W" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "then LLL probably still would h
ave found the vectors we want." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 495 "Now we had 2 equations, each contributin
g about 10^40 to the determinant. So that's 10^80 all together. But 10
^80 / s^5   would have probably been OK. So that means that we've used
 more than twice the number of digits that was necessary (that's hinds
ight of course).  In any case, we can expect that with Digits=20, the \+
computation would still be successful, but with Digits=10 it would not
 be successfull.   Lets set Digits=20 and see if it still works.  Then
 set Digits=10 and see if it fails." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "Digits:=20;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'Dig
itsG\"#?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 128 "Now go back to the b
eginning of the worksheet  (skip the line \"restart\" and \"Digits:=40
\") and re-do everything, see if it works." }}{PARA 0 "" 0 "" {TEXT 
-1 245 "--> Indeed, with Digits=20 we still find the same \"g\".   But
 Digits=10 is probably not going to be enough because then the \"vecto
rs we don't want\" won't be long enough anymore, so LLL can't separate
 them from the \"vectors we want\". But lets try:" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 11 "Digits:=10;" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#>%'DigitsG\"#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "With this to
o low setting of Digits, we find the wrong g." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 51 "A diffe
rent way to get the same result  (using rem)" }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "alpha := .00275334
0381990234990115493078115778952576 + 1.1450473031269229651476774573512
40915890*I;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&alphaG^$$\"IwD&*yd6y
I\\:,*\\B!*>QSLv#!#U$\"I!*e\"4C^tXxw9lH#p7.t/X6!#R" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 39 "f1 := (x-alpha) * (x-conjugate(alpha));" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#f1G*&,&%\"xG\"\"\"^$$!IwD&*yd6yI\\:
,*\\B!*>QSLv#!#U$!I!*e\"4C^tXxw9lH#p7.t/X6!#RF(F(,&F'F(^$F*$\"I!*e\"4C
^tXxw9lH#p7.t/X6F/F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "D
igits:=20;  # we know now that 20 was enough" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%'DigitsG\"#?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 17 "f1 := expand(f1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,(*$)
%\"xG\"\"#\"\"\"F**&$\"5-)*p/)Rw!o1b!#AF*F(F*!\"\"^$$\"5\\])\\\"G24968
!#>$\"\"!F5F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "f1 := coll
ect(f1, x, Re);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,(*$)%\"xG\"
\"#\"\"\"F**&$\"5-)*p/)Rw!o1b!#AF*F(F*!\"\"$\"5\\])\\\"G24968!#>F*" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "g := add(c[i]*x^i,i=0..7);
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,2&%\"cG6#\"\"!\"\"\"*&&F'6#
F*F*%\"xGF*F**&&F'6#\"\"#F*)F.F2F*F**&&F'6#\"\"$F*)F.F7F*F**&&F'6#\"\"
%F*)F.F<F*F**&&F'6#\"\"&F*)F.FAF*F**&&F'6#\"\"'F*)F.FFF*F**&&F'6#\"\"(
F*)F.FKF*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 148 "If g in Z[x],  an
d if alpha is a solution of g, then so is conjugate(alpha), and hence \+
f1 must divide g.  That means that the following must be zero" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "rem(g,f1,x);" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#,2*&,0&%\"cG6#\"\"\"F)*&$\"5C6i%[Pe56J\"!#>F)&F'6#
\"\"$F)!\"\"*&$\"5kw:ER/7(*=<F-F)&F'6#\"\"&F)F)*&$\"5vnl(\\E3dOD#F-F)&
F'6#\"\"(F)F1*&$\"5gjtG)p;d)RG!#@F)&F'6#\"\"'F)F)*&$\"5b+ztR%=!*RW\"FA
F)&F'6#\"\"%F)F1*&$\"5-)*p/)Rw!o1b!#AF)&F'6#\"\"#F)F)F)%\"xGF)F)&F'6#
\"\"!F)*&$\"5\\])\\\"G24968F-F)FOF)F1*&$\"5IuLBK?20><F-F)FHF)F)*&$\"5T
W/\"=XY8QD#F-F)FBF)F1*&$\"5#R4znC!HXBPFAF)F;F)F1*&$\"5d$yNw/guK*=FAF)F
5F)F)*&$\"5@uG\\*HTM+A(FNF)F.F)F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
48 "and this leaves us with the following equations:" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 23 "eqns := \{coeffs(%, x)\};" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#>%%eqnsG<$,0&%\"cG6#\"\"!\"\"\"*&$\"5\\])\\\"G2496
8!#>F+&F(6#\"\"#F+!\"\"*&$\"5IuLBK?20><F/F+&F(6#\"\"%F+F+*&$\"5TW/\"=X
Y8QD#F/F+&F(6#\"\"'F+F3*&$\"5#R4znC!HXBP!#@F+&F(6#\"\"(F+F3*&$\"5d$yNw
/guK*=FCF+&F(6#\"\"&F+F+*&$\"5@uG\\*HTM+A(!#AF+&F(6#\"\"$F+F3,0&F(6#F+
F+*&$\"5C6i%[Pe56J\"F/F+FQF+F3*&$\"5kw:ER/7(*=<F/F+FJF+F+*&$\"5vnl(\\E
3dOD#F/F+FDF+F3*&$\"5gjtG)p;d)RGFCF+F=F+F+*&$\"5b+ztR%=!*RW\"FCF+F7F+F
3*&$\"5-)*p/)Rw!o1bFPF+F0F+F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "N
ow take:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "C := 10^Digits;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG\"6++++++++++\"" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 54 "and again, we want the following to be a \+
short vector:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "v := [ seq
(c[i],i=0..7), C * eqns[1], C * eqns[2] ];" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%\"vG7,&%\"cG6#\"\"!&F'6#\"\"\"&F'6#\"\"#&F'6#\"\"$&F'
6#\"\"%&F'6#\"\"&&F'6#\"\"'&F'6#\"\"(,0*&\"6++++++++++\"F,F&F,F,*&$\"5
\\])\\\"G24968F,F,F-F,!\"\"*&$\"5IuLBK?20><F,F,F3F,F,*&$\"5TW/\"=XY8QD
#F,F,F9F,FE*&$\"5#R4znC!HXBPFEF,F<F,FE*&$\"5d$yNw/guK*=FEF,F6F,F,*&$\"
5@uG\\*HTM+A(!\"#F,F0F,FE,0*&FAF,F*F,F,*&$\"5C6i%[Pe56J\"F,F,F0F,FE*&$
\"5kw:ER/7(*=<F,F,F6F,F,*&$\"5vnl(\\E3dOD#F,F,F<F,FE*&$\"5gjtG)p;d)RGF
EF,F9F,F,*&$\"5b+ztR%=!*RW\"FEF,F3F,FE*&$\"5-)*p/)Rw!o1bFUF,F-F,F," }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "Now again, v is a linear combinat
ion of the following vectors:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 68 "for i from 0 to 7 do\n  V[i] := map(round, map( coeff, v, c[i] )
)\nod;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"!7,\"\"\"F'F'F'
F'F'F'F'\"6++++++++++\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#
\"\"\"7,\"\"!F'F)F)F)F)F)F)F)\"6++++++++++\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%\"VG6#\"\"#7,\"\"!F)\"\"\"F)F)F)F)F)!6!\\])\\\"G2496
8\"3)*p/)Rw!o1b" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"$7,\"
\"!F)F)\"\"\"F)F)F)F)!3uG\\*HTM+A(!6S7@Y[Pe56J\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%\"VG6#\"\"%7,\"\"!F)F)F)\"\"\"F)F)F)\"6+VPLA.s]!><!4
1!ztR%=!*RW\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"&7,\"\"!
F)F)F)F)\"\"\"F)F)\"4OyNw/guK*=\"6Smdh#R/7(*=<" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%\"VG6#\"\"'7,\"\"!F)F)F)F)F)\"\"\"F)!65WW5=XY8QD#\"4
OO(G)p;d)RG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"VG6#\"\"(7,\"\"!F)
F)F)F)F)F)\"\"\"!4R4znC!HXBP!6]xcw\\E3dOD#" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 20 "and lets \"LLL\" this:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 28 "LLL( [ seq(V[i], i=0..7) ]);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#7*7,\"#]\"#(*\"#:\"#g!#!*!$A\"!#b!#&)!$<%!$+#7,\"$+#\"$
)Q\"#5\"$V\"!$D$!$^%!$l\"!$b#!$B$\"%!G\"7,!$+$!$K&\"#d!$)H\"$o%\"$S'\"
$!>\"$D%!%85\"$)G7,\"'/_v!'**\\a!'+7J\"(S6;\"!'([j%\"'BT&)\"'x.<!'4:E!
&^-$\"&k\\'7,\"(%ed9!(<`O\"!&P4#!(wl6\"!'<vY!'z5^\"')>2$!'T#R$!&ra\"!&
m'>7,!'(\\g(!(2TZ\"!'Gc$*!'G[n!(&*f$=\"&HS&!(ar=\"!'sdA\"&%=:\"%il7,\"
'L[%*!''eG(\"(\"HCA\"'3J6\"'mE&)!'_1J!'\")p@!'0)G'\"&^Q*\"&c5#7,!(<C<#
!'iP'*!'NpT\"')Hz(\"(X$f5!(W-6\"\"')[.\"!(aVt\"\"%SN\"&))R*" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "short vectors are:" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "v1,v2,v3 := %[1], %[2], %[3]:" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "corresponding polynomials are" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 95 "g1 := add(v1[i+1]*x^i, i=0..
7); g2 := add(v2[i+1]*x^i, i=0..7); g3 := add(v3[i+1]*x^i, i=0..7);" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g1G,2\"#]\"\"\"*&\"#(*F'%\"xGF'F'*
&\"#:F')F*\"\"#F'F'*&\"#gF')F*\"\"$F'F'*&\"#!*F')F*\"\"%F'!\"\"*&\"$A
\"F')F*\"\"&F'F7*&\"#bF')F*\"\"'F'F7*&\"#&)F')F*\"\"(F'F7" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%#g2G,2\"$+#\"\"\"*&\"$)QF'%\"xGF'F'*&\"#5F')F
*\"\"#F'F'*&\"$V\"F')F*\"\"$F'F'*&\"$D$F')F*\"\"%F'!\"\"*&\"$^%F')F*\"
\"&F'F7*&\"$l\"F')F*\"\"'F'F7*&\"$b#F')F*\"\"(F'F7" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%#g3G,2\"$+$!\"\"*&\"$K&\"\"\"%\"xGF*F'*&\"#dF*)F+\"
\"#F*F**&\"$)HF*)F+\"\"$F*F'*&\"$o%F*)F+\"\"%F*F**&\"$S'F*)F+\"\"&F*F*
*&\"$!>F*)F+\"\"'F*F**&\"$D%F*)F+\"\"(F*F*" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 273 "Up to fairly high accuracy, they all have alpha as a roo
t.  So it seems likely that the \"true exact value of alpha, which of \+
course is not given to us\" is a root of each of these g1,g2,g3, and i
f that's the case, then g1,g2,g3 have a common root and hence the gcd \+
is not 1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "g :=  gcd(  gc
d(g1,g2) , g3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.\"#]!\"\"*&
\"#(*\"\"\"%\"xGF*F'*&\"#NF*)F+\"\"#F*F**&\"#PF*)F+\"\"$F*F**&\"#bF*)F
+\"\"%F*F**&\"#&)F*)F+\"\"&F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 12 "rem(g,f1,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"\"!F$" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "that's a bit too close to 0 for my
 taste, let's try:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Digit
s:=25;  rem(g,f1,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'DigitsG\"#D
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&$\"-XX1HV7!#G!\"\"*&$\",bK_[1#!#
F\"\"\"%\"xGF,F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "OK, that look
s less suspicious." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "subs(
x=alpha,g);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#^$$!$]\"!#C$!\"#!#A" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "That looks good too." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "1 0 0" 9 }{VIEWOPTS 1 
1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }