{VERSION 6 0 "IBM INTEL LINUX" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 1 12 255 0 0 1 2 1 2 
2 1 2 0 0 0 1 }{CSTYLE "2D Output" -1 20 "Times" 1 12 0 0 255 1 2 2 2 
2 2 1 0 0 0 1 }{CSTYLE "Text" -1 200 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 
0 0 0 1 }{CSTYLE "" -1 256 "helvetica" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 
2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Line Printed O
utput" -1 6 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 
0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "
" -1 -1 "Courier" 1 12 255 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 
0 2 0 2 2 -1 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times
" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }
{PSTYLE "Left Justified Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times
" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }
{PSTYLE "" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 
1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 24 "Examples of using RECDEN
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "Set the path to where the rec
den src code is and read in the code." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 52 "restart;\ncurrentdir(\"/home/mmonagan/sydney/recden\"
);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%=/home/mmonagan/sydney/recdenG
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "read \"recden\";" }}}
{EXCHG {PARA 256 "" 0 "" {TEXT 200 1 " " }{TEXT -1 0 "" }{TEXT 200 
188 "Recursive Dense representation of polynomial uses internal Maple \+
structure, named POLYNOMIAL, which is a recursive array. Using rpoly()
, we can build POLYNOMIAL from polynomial expression." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "a := 2*x^2-y^2;" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%\"aG,&*&\"\"#\"\"\")%\"xGF'F(F(*$)%\"yGF'F(!\"\"" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "A := rpoly(a,[x,y]);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG,&*&\"\"#\"\"\")%\"xGF'F(F(*$)%
\"yGF'F(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "lprint(A);
" }}{PARA 6 "" 1 "" {TEXT -1 48 "POLYNOMIAL([0, [x, y], []],[[0, 0, -1
], 0, [2]])" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "a := rpoly(A
); # convert back to rational polynomial." }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"aG,&*&\"\"#\"\"\")%\"xGF'F(F(*$)%\"yGF'F(!\"\"" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "lprint(a);" }}{PARA 6 "" 1 "
" {TEXT -1 9 "2*x^2-y^2" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 200 262 "Usin
g lprint, we can see the actual data structure. The first operant is t
he ringtype, where <ringtype>::=[M::nonnegint, X::list(name), E::list(
rpolytype], ie, M is the charateristic of the ring, X is a list of var
iables, and E is the extension field expression." }}{PARA 0 "" 0 "" 
{TEXT 200 0 "" }}{PARA 0 "" 0 "" {TEXT 200 72 "The following is a set \+
of function that you can obtain information of A:" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 11 "getring(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#7%\"\"!7$%\"xG%\"yG7\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
11 "getpoly(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%7%\"\"!F%!\"\"F%7
#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "getchar(A);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "getvars(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$%\"x
G%\"yG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "getexts(A);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
200 151 "To create a polynomial x^2+b*y+3 where b=sqrt(2), we use the \+
following rpoly(a::polynomial(rational),X::\{name,list(name)\},E::ext,
M::posint)::POLYNOMIAL" }}{PARA 0 "" 0 "" {TEXT 200 76 "The first way \+
is to input the minimal polynomial for sqrt(2), namely, b^2-2." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "f := rpoly(x^2+b*y+3,[x,y,b]
,b^2-2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG-%$modG6$,(*$)%\"xG
\"\"#\"\"\"F-*&%\"bGF-%\"yGF-F-\"\"$F--%$<,>G6#,&*$)F/F,F-F-F,!\"\"" }
}}{EXCHG {PARA 0 "" 0 "" {TEXT 200 48 " The second way is to input sqr
t(2) as a RootOf." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "f := r
poly(x^2+b*y+3,[x,y,b],b=RootOf(z^2-2));" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%\"fG-%$modG6$,(*$)%\"xG\"\"#\"\"\"F-*&%\"bGF-%\"yGF-F-\"\"$F--
%$<,>G6#,&*$)F/F,F-F-F,!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 10 "lprint(f);" }}{PARA 6 "" 1 "" {TEXT -1 66 "POLYNOMIAL([0, [x, y,
 b], [[-2, 0, 1]]],[[[3], [0, 1]], 0, [[1]]])" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 160 "# Examples of creating rring:\nK := rring(z,z^2
-2);       # Create R[z]/<z^2-2> \nKxy := rring(K,[x,y]);     # Create
 R[x,y,z]/<z^2-2>\nf := rpoly(x^2+z*y+3,Kxy); " }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"KG7%\"\"!7#%\"zG7#7%!\"#F&\"\"\"" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%$KxyG7%\"\"!7%%\"xG%\"yG%\"zG7#7%!\"#F&\"\"\"" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG-%$modG6$,(*$)%\"xG\"\"#\"\"\"F-
*&%\"zGF-%\"yGF-F-\"\"$F--%$<,>G6#,&*$)F/F,F-F-F,!\"\"" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT 200 76 "If we want to create f := x^2+b*y+3 (mod
 5) where b=sqrt(2), we can do this:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 48 "f := rpoly(x^2+b*y+3,[x,y,b],b=RootOf(z^2-2),5);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG-%$modG6$,(*$)%\"xG\"\"#\"\"\"F-
*&%\"bGF-%\"yGF-F-\"\"$F--%$<,>G6$,&*$)F/F,F-F-F1F-\"\"&" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT 200 131 "Hence, we could build polynomials in fi
nite fields (Galois fields). Example: f := x*y^2-y in GF(16) represent
ed by Z2[x]/<x^4+x+1>." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "G
F16 := rring(x,x^4+x+1,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%GF16G
7%\"\"#7#%\"xG7#7'\"\"\"F+\"\"!F,F+" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 19 "P := rring(GF16,y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%\"PG7%\"\"#7$%\"yG%\"xG7#7'\"\"\"F,\"\"!F-F," }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 22 "f := rpoly(x*y^2-y,P);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"fG-%$modG6$,&*&%\"xG\"\"\")%\"yG\"\"#F+F+F-F+-%$<,>
G6$,(*$)F*\"\"%F+F+F*F+F+F+F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 54 "# or directly:\nf := rpoly(x*y^2-y, [y,x], x^4+x+1, 2);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG-%$modG6$,&*&%\"xG\"\"\")%\"yG\"
\"#F+F+F-F+-%$<,>G6$,(*$)F*\"\"%F+F+F*F+F+F+F." }}}{EXCHG {PARA 0 "" 
0 "" {TEXT 200 92 "Be careful here. We should list the function variab
le and then the field extension variable." }}{PARA 0 "" 0 "" {TEXT 
200 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 148 "# Multiple exte
nsions:\na := 'a':  b := 'b':\ng1 := Nextprime(z^2+z,z) mod 2;\nalias(
a=RootOf(g1)):\ng2 := Nextprime(g1,z,a) mod 2;\nalias(b=RootOf(g2)):" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g1G,(*$)%\"zG\"\"#\"\"\"F*F(F*F*F
*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g2G,(*$)%\"zG\"\"#\"\"\"F*F(F*
%\"aGF*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 119 "# create f := a
*x^2+b*x*y+a*b*y^2+y in Z[2][x,y,a,b]/<g1,g2>:\nf := rpoly(z*x^2+w*x*y
+z*w*y^2+y,[x,y,z,w],[z=b,w=a],2);\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%\"fG-%$modG6$,**&%\"zG\"\"\")%\"xG\"\"#F+F+*(%\"wGF+F-F+%\"yGF+F+*
(F*F+F0F+)F1F.F+F+F1F+-%$<,>G6%,(*$)F*F.F+F+F*F+F0F+,(*$)F0F.F+F+F0F+F
+F+F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "lprint(f);" }}
{PARA 6 "" 1 "" {TEXT -1 115 "POLYNOMIAL([2, [x, y, z, w], [[[0, 1], [
1], [1]], [1, 1, 1]]],[[0, [[1]], [0, [0, 1]]], [0, [[0, 1]]], [[0, [1
]]]])" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 200 163 "Again, we need to be c
areful when listing the variables. We use z to represent b and w to re
present a. Since b is the RootOf(z^2+z+a), we need to write z before w
." }}{PARA 0 "" 0 "" {TEXT 200 0 "" }}{PARA 0 "" 0 "" {TEXT 200 72 "Th
e following is a list of functions to test properties of a POLYNOMIAL:
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g := rpoly(2*x,[x,y,z,w
],[z=b,w=a],2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG-%$modG6$\"\"
!-%$<,>G6%,(*$)%\"zG\"\"#\"\"\"F1F/F1%\"wGF1,(*$)F2F0F1F1F2F1F1F1F0" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "h := rpoly(z*x,[x,z],[z=a]
,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"hG-%$modG6$*&%\"zG\"\"\"%
\"xGF*-%$<,>G6$,(*$)F)\"\"#F*F*F)F*F*F*F2" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 31 "iszerorpoly(f);\niszerorpoly(g);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#%&falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "isunivariate(f); \nisuniv
ariate(h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
29 "ismonomial(f);\nismonomial(h);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
%&falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 29 "isconstant(f);\nisconstant(g);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
%%trueG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "K := getring(f):
\nisretrpoly(f, K);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "hassamering(f,h);\nhassameri
ng(f,g);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 200 18 "Mod
ulo operations:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 150 "g := rp
oly(10*x^2-7*z*x+5*y-w,[x,y,z,w],[z=b,w=a],11);\ng := modsrpoly(g); # \+
change to symmetric ring\ng := modprpoly(g); # change back to positive
 ring" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG-%$modG6$,**&\"#5\"\"\"
)%\"xG\"\"#F+F+*(\"\"%F+%\"zGF+F-F+F+*&\"\"&F+%\"yGF+F+*&F*F+%\"wGF+F+
-%$<,>G6%,(*$)F1F.F+F+F1F+F6F+,(*$)F6F.F+F+F6F+F+F+\"#6" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%\"gG-%$modG6$,**$)%\"xG\"\"#\"\"\"!\"\"*(\"\"%
F-%\"zGF-F+F-F-*&\"\"&F-%\"yGF-F-%\"wGF.-%$<,>G6%,(*$)F1F,F-F-F1F-F5F-
,(*$)F5F,F-F-F5F-F-F-\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG-%$
modG6$,**&\"#5\"\"\")%\"xG\"\"#F+F+*(\"\"%F+%\"zGF+F-F+F+*&\"\"&F+%\"y
GF+F+*&F*F+%\"wGF+F+-%$<,>G6%,(*$)F1F.F+F+F1F+F6F+,(*$)F6F.F+F+F6F+F+F
+\"#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 200 26 "Create random polynomia
ls:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 "A := randpoly([x,y],
 coeffs=proc() randpoly([z,w],degree=1) end proc, dense, degree=3):" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "A := rpoly(A,[x,y,z,w],[z=
b,w=a],2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"AG-%$modG6$,.*&,(%\"
zG\"\"\"%\"wGF,F,F,F,)%\"xG\"\"$F,F,*&,(*&,&F+F,F,F,F,%\"yGF,F,F-F,F,F
,F,)F/\"\"#F,F,*&,(*&F*F,)F5F7F,F,*&,&F-F,F,F,F,F5F,F,F+F,F,F/F,F,*$)F
5F0F,F,F:F,F,F,-%$<,>G6%,(*$)F+F7F,F,F+F,F-F,,(*$)F-F7F,F,F-F,F,F,F7" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "# degree of A in main var
iable or other variable:\ndegrpoly(A);\ndegrpoly(A,z);" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "B := randpoly([x,y], coef
fs=proc() randpoly([z,w],degree=1) end proc, dense, degree=3):\nB := r
poly(B,[x,y,z,w],[z=b,w=a],2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"
BG-%$modG6$,.*&,(%\"zG\"\"\"%\"wGF,F,F,F,)%\"xG\"\"$F,F,*&,&*&F*F,%\"y
GF,F,F-F,F,)F/\"\"#F,F,*&,(*&,&F-F,F,F,F,)F4F6F,F,*&F+F,F4F,F,F,F,F,F/
F,F,*&F*F,)F4F0F,F,*&F+F,F;F,F,*&,&F+F,F,F,F,F4F,F,-%$<,>G6%,(*$)F+F6F
,F,F+F,F-F,,(*$)F-F6F,F,F-F,F,F,F6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
200 44 "Adding, substracting, multiplying, dividing:" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 59 "addrpoly(A,B);\nsubrpoly(A,B);\nmulrpoly(
A,B);\ndivrpoly(A,B);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#-%$modG6$,.*&
,&*&%\"wG\"\"\"%\"yGF+F+F+F+F+)%\"xG\"\"#F+F+*&,**&%\"zGF+)F,F/F+F+*&,
(F3F+F*F+F+F+F+F,F+F+F3F+F+F+F+F.F+F+*&,&F3F+F*F+F+)F,\"\"$F+F+*&,&F*F
+F+F+F+F4F+F+*&,&F3F+F+F+F+F,F+F+F+F+-%$<,>G6%,(*$)F3F/F+F+F3F+F*F+,(*
$)F*F/F+F+F*F+F+F+F/" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#-%$modG6$,.*&,
&*&%\"wG\"\"\"%\"yGF+F+F+F+F+)%\"xG\"\"#F+F+*&,**&%\"zGF+)F,F/F+F+*&,(
F3!\"\"F*F+F+F+F+F,F+F+F3F+F+F7F+F.F+F+*&,&F3F7F*F+F+)F,\"\"$F+F+*&,&F
*F+F+F+F+F4F+F+*&,&F3F7F+F7F+F,F+F+F+F+-%$<,>G6%,(*$)F3F/F+F+F3F+F*F+,
(*$)F*F/F+F+F*F+F+F+F/" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#-%$modG6$,8*
&%\"zG\"\"\")%\"xG\"\"'F)F)*&,**&,&*&F(F)%\"wGF)F)F)F)F)%\"yGF)F)F(F)F
2F)F)F)F))F+\"\"&F)F)*&,&*&,(F(F)F2F)F)F)F))F3\"\"#F)F)*&,&F2F)F)F)F)F
(F)F)F))F+\"\"%F)F)*&,**(F(F)F2F))F3\"\"$F)F)*&F0F)F:F)F)*&,(F<F)F2F)F
)F)F)F3F)F)F<F)F))F+FDF)F)*&,.*&F(F))F3F?F)F)*&F2F)FCF)F)*&,&F(F)F)F)F
)F:F)F)*&,&F<F)F)F)F)F3F)F)F(F)F2F)F))F+F;F)F)*&,,*&F9F))F3F5F)F)*&,&F
<F)F2F)F)FLF)F)*&FQF)F:F)F)*&,&F(F)F2F)F)F3F)F)F)F)F)F+F)F)*&F9F))F3F,
F)F)*&FGF)FLF)F)*&,&F1F)F2F)F)FCF)F)*&F(F)F:F)F)*&FOF)F3F)F)-%$<,>G6%,
(*$)F(F;F)F)F(F)F2F),(*$)F2F;F)F)F2F)F)F)F;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#%&falseG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "This d
oesn't work because A and B are not univariate" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 18 "remrpoly(A,B,'Q');" }}{PARA 8 "" 1 "" {TEXT 
-1 52 "Error, (in remrpoly) polynomials must be univariate\n" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "G := randpoly([x,y], coeffs
=proc() randpoly([z,w],degree=1) end proc, dense, degree=4):\nG := rpo
ly(G,[x,y,z,w],[z=b,w=a],2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"GG
-%$modG6$,4*&,&%\"zG\"\"\"%\"wGF,F,)%\"xG\"\"%F,F,*&,&*&,(F+F,F-F,F,F,
F,%\"yGF,F,F-F,F,)F/\"\"$F,F,*&,**&,&F+F,F,F,F,)F5\"\"#F,F,F3F,F+F,F,F
,F,)F/F=F,F,*&,(F:F,*&,&F-F,F,F,F,F5F,F,F,F,F,F/F,F,*&F+F,)F5F0F,F,*&F
+F,)F5F7F,F,FAF,F+F,F,F,-%$<,>G6%,(*$)F+F=F,F,F+F,F-F,,(*$)F-F=F,F,F-F
,F,F,F=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "To make G monic we inv
ert the leading coefficient of G" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 37 "L := lcrpoly(G);\ninvL := invrpoly(L);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%\"LG-%$modG6$,&%\"zG\"\"\"%\"wGF*-%$<,>G6%,(*$
)F)\"\"#F*F*F)F*F+F*,(*$)F+F2F*F*F+F*F*F*F2" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%%invLG-%$modG6$,&*&%\"zG\"\"\"%\"wGF+F+F+F+-%$<,>G6%,
(*$)F*\"\"#F+F+F*F+F,F+,(*$)F,F3F+F+F,F+F+F+F3" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 60 "G := mulrpoly(invL,G); # A scalar multiplicati
on\nlcrpoly(G);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"GG-%$modG6$,4*$
)%\"xG\"\"%\"\"\"F-*&,(*(%\"zGF-%\"wGF-%\"yGF-F-*&,&F2F-F-F-F-F1F-F-F2
F-F-)F+\"\"$F-F-*&,**&,&F1F-F2F-F-)F3\"\"#F-F-F0F-F1F-F2F-F-)F+F=F-F-*
&,*F:F-*&,(F1F-F2F-F-F-F-F3F-F-*&F1F-F2F-F-F-F-F-F+F-F-*&,(F4F-F2F-F-F
-F-)F3F,F-F-*&FEF-)F3F7F-F-FAF-F1F-F2F--%$<,>G6%,(*$)F1F=F-F-F1F-F2F-,
(*$)F2F=F-F-F2F-F-F-F=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%$modG6$\"
\"\"-%$<,>G6%,(*$)%\"zG\"\"#F&F&F-F&%\"wGF&,(*$)F/F.F&F&F/F&F&F&F." }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "F := mulrpoly(A,G):\nH := m
ulrpoly(B,G):\n# Now, G is the gcd of F and H." }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 37 "Now G is a common divisor of F and H." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "divrpoly(F,G);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Compute
 the GCD of  F and H using two primes (irreducibles)  and chrem" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "p1 := rpoly(y^3,[y,z,w],[z=b
,w=a],2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p1G-%$modG6$*$)%\"yG\"
\"$\"\"\"-%$<,>G6%,(*$)%\"zG\"\"#F,F,F3F,%\"wGF,,(*$)F5F4F,F,F5F,F,F,F
4" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "# find the next monic \+
irreducible rpoly.\nP1 := nmirpoly(p1);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%#P1G-%$modG6$,&*$)%\"yG\"\"$\"\"\"F-%\"zGF--%$<,>G6%,(*$)F.\"
\"#F-F-F.F-%\"wGF-,(*$)F6F5F-F-F6F-F-F-F5" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 85 "Fp := phirpoly(F,P1);  Hp := phirpoly(H,P1); \n# ph
irpoly(F,P1) means taking F mod P1." }}{PARA 12 "" 1 "" {XPPMATH 20 "6
#>%#FpG-%$modG6$,6*&,(%\"zG\"\"\"%\"wGF,F,F,F,)%\"xG\"\"(F,F,*&,**&,&*
&F-F,F+F,F,F-F,F,%\"yGF,F,*&,&F-F,F,F,F,F+F,F,F-F,F,F,F,)F/\"\"'F,F,*&
,**&F*F,)F6\"\"#F,F,*&F8F,F6F,F,F7F,F-F,F,)F/\"\"&F,F,*&,,*&F-F,F>F,F,
F3F,F7F,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,*&,,*&,(F5F,F-F,F,F,F,F>F,F,*&,&F7F,F-F,F,F6F,F,F+F,F-F,
F,F,F,)F/F?F,F,*&,**&,&F5F,F,F,F,F>F,F,F6F,F+F,F-F,F,F/F,F,*&F+F,F>F,F
,*(F-F,F+F,F6F,F,F,F,-%$<,>G6&,&*$)F6FNF,F,F+F,,(*$)F+F?F,F,F+F,F-F,,(
*$)F-F?F,F,F-F,F,F,F?" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#HpG-%$modG
6$,8*&,(%\"zG\"\"\"%\"wGF,F,F,F,)%\"xG\"\"(F,F,*&,(*(F-F,F+F,%\"yGF,F,
*&,&F-F,F,F,F,F+F,F,F-F,F,)F/\"\"'F,F,*&,**&,(F5F,F-F,F,F,F,)F4\"\"#F,
F,*&,(*&F-F,F+F,F,F-F,F,F,F,F4F,F,F+F,F,F,F,)F/\"\"&F,F,*&,**$F=F,F,*&
F6F,F4F,F,F5F,F,F,F,)F/\"\"%F,F,*&,**&,&FAF,F,F,F,F=F,F,*&F*F,F4F,F,FA
F,F,F,F,)F/\"\"$F,F,*&,&FLF,*&F-F,F4F,F,F,)F/F>F,F,*&,**&,&F5F,F-F,F,F
=F,F,*&FMF,F4F,F,F5F,F,F,F,F/F,F,*&F-F,F=F,F,F4F,F-F,F,F,-%$<,>G6&,&*$
)F4FPF,F,F+F,,(*$)F+F>F,F,F+F,F-F,,(*$)F-F>F,F,F-F,F,F,F>" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 89 "Now, Fp and Hp are univariate, so we can \+
use remrpoly, and hence the Euclidean algorithm." }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 23 "remrpoly(Fp,Hp,'Q'): Q;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#-%$modG6$\"\"\"-%$<,>G6&,&*$)%\"yG\"\"$F&F&%\"zGF&,(*$)
F/\"\"#F&F&F/F&%\"wGF&,(*$)F4F3F&F&F4F&F&F&F3" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 26 "G1 := gcdrpoly( Fp, Hp ); " }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%#G1G-%$modG6$,2*$)%\"xG\"\"%\"\"\"F-*&,(*(%\"wGF-%\"z
GF-%\"yGF-F-*&,&F1F-F-F-F-F2F-F-F1F-F-)F+\"\"$F-F-*&,**&,&F2F-F1F-F-)F
3\"\"#F-F-F0F-F2F-F1F-F-)F+F=F-F-*&,*F:F-*&,(F2F-F1F-F-F-F-F3F-F-*&F1F
-F2F-F-F-F-F-F+F-F-*&F;F-F3F-F-F2F-F1F-F-F--%$<,>G6&,&*$)F3F7F-F-F2F-,
(*$)F2F=F-F-F2F-F1F-,(*$)F1F=F-F-F1F-F-F-F=" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 45 "Now repeat modulo a second prime, and combine" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "P2 := nmirpoly(P1);\nG2 := g
cdrpoly( phirpoly(F,P2),phirpoly(H,P2));" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%#P2G-%$modG6$,(*$)%\"yG\"\"$\"\"\"F-%\"zGF-F-F--%$<,>G6%,(*$)F
.\"\"#F-F-F.F-%\"wGF-,(*$)F6F5F-F-F6F-F-F-F5" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%#G2G-%$modG6$,.*$)%\"xG\"\"%\"\"\"F-*&,(*(%\"wGF-%\"z
GF-%\"yGF-F-*&,&F1F-F-F-F-F2F-F-F1F-F-)F+\"\"$F-F-*&,**&,&F2F-F1F-F-)F
3\"\"#F-F-F0F-F2F-F1F-F-)F+F=F-F-*&,*F:F-*&,(F2F-F1F-F-F-F-F3F-F-*&F1F
-F2F-F-F-F-F-F+F-F-*&,&FCF-F-F-F-F3F-F-FCF--%$<,>G6&,(*$)F3F7F-F-F2F-F
-F-,(*$)F2F=F-F-F2F-F1F-,(*$)F1F=F-F-F1F-F-F-F=" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 38 "GG := liftrpoly(chremrpoly([G1,G2])); " }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GGG-%$modG6$,4*$)%\"xG\"\"%\"\"\"F-
*&,(*(%\"wGF-%\"zGF-%\"yGF-F-*&,&F1F-F-F-F-F2F-F-F1F-F-)F+\"\"$F-F-*&,
**&,&F2F-F1F-F-)F3\"\"#F-F-F0F-F2F-F1F-F-)F+F=F-F-*&,*F:F-*&,(F2F-F1F-
F-F-F-F3F-F-*&F1F-F2F-F-F-F-F-F+F-F-*&,(F4F-F1F-F-F-F-)F3F,F-F-*&FEF-)
F3F7F-F-FAF-F2F-F1F--%$<,>G6%,(*$)F2F=F-F-F2F-F1F-,(*$)F1F=F-F-F1F-F-F
-F=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "Here, chremrpoly returns \+
an rpoly in the field Z2[x,y,z,w]/<p1*p2,g1,g2>,\nSo we would to lift \+
the result to Z[2][x,y,z,w]/<g1,g2>." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 15 "subrpoly(G,GG);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%
$modG6$\"\"!-%$<,>G6%,(*$)%\"zG\"\"#\"\"\"F/F-F/%\"wGF/,(*$)F0F.F/F/F0
F/F/F/F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "72 \+
0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }