{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 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 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "Diagnostic" 7 9 1 {CSTYLE "" -1 -1 "" 0 1 64 128 64 1 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 }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 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3098 "modular_gcd := pro c(F1,F2,x)\nlocal f1,f2,l,p,gp,g,m;\n # The following two lines get r id of fractions.\n # Note: You can't do F1 := primpart(F1,x) because \n # F1 is the input and you can't change the input.\n f1 := primpar t(F1);\n f2 := primpart(F2);\n # integer gcd of the leading coeffici ents.\n l := igcd( lcoeff(f1,x), lcoeff(f2,x) );\n p := 2;\n do\n \+ while irem(l,p)=0 do\n # while l vanishes mod p take the ne xt prime:\n p := nextprime(p)\n od;\n gp := Gcd(f1,f2) mod p;\n # gp = modular gcd.\n #\n # g = \"our gcd so far \". g is \"known\" modulo m.\n #\n # if g has not been assign ed yet (so then we're\n # in the first loop) then set g = gp, and \+ set\n # m = p because we \"know\" g modulo p.\n # \n # Als o, if degree gp < degree g\n # then degree g is higher than the de gree of the\n # true gcd, because each gp has degree at least as\n # high as the true gcd. So all previous gcd's mod p,\n # whic h I've combined together into g, had too high\n # degree. So I'll \+ discard all of them. Then, all I know\n # at that point is the new gp. So I'll let g be gp\n # and I then know g modulo p, so m := p . \n #\n if not assigned(g) or degree(gp,x)degree(g,x) then\n # if degree(gp,x )>degree(g,x) then the degree\n # of gp is too high, so then I won't use it.\n # Otherwise, then I know g mod m,\n # but known I also know g mod p,\n # so I can calculate g mod p *m with the Chinese\n # remainder theorem.\n # Note, I 'm actually using l*gp because I know l*g\n # has integer coef ficients.\n #\n # The new g is congruent to the old g \+ mod m,\n # but at the same time congruent to gp mod p.\n \+ g := mods(chrem([g,l * gp],[m,p]), p*m);\n # Now g is \"kno wn\" modulo a larger number, namely:\n m := m*p;\n if \+ divide(f1,g) and divide(f2,g) then\n # Only return the ans wer g if it is a common\n # factor of f1,f2, which we test with \"divide\".\n # Then simplify g with \"primpart\".\n # Since the degree of each gp (and hence of g)\n \+ # is at least the degree of the true gcd, we've\n # fo und a common factor of f1,f2 with degree at\n # least as h igh as the degree of the gcd, so it\n # must be the gcd. S o we can be confident that the\n # result is correct.\n \+ RETURN( primpart(g) )\n fi;\n fi;\n # If \+ g was not a common factor of f1,f2, then we did\n # not yet calcul ate g modulo a sufficiently large\n # number m. So we'll compute g modulo a higher number\n # by using more primes:\n p := nextp rime(p)\n od\nend;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,modular_gcdG R6%%#F1G%#F2G%\"xG6)%#f1G%#f2G%\"lG%\"pG%#gpG%\"gG%\"mG6\"F2C'>8$-%)pr impartG6#9$>8%-F76#9%>8&-%%igcdG6$-%'lcoeffG6$F59&-FE6$F;FG>8'\"\"#?(F 2\"\"\"FNF2%%trueGC&?(F2FNFNF2/-%%iremG6$F@FK\"\"!>FK-%*nextprimeG6#FK >8(-%$modG6$-%$GcdG6$F5F;FK@&54-%)assignedG6#8)2-%'degreeG6$FfnFG-Ffo6 $FcoFGC%>Fco*&F@FNFfnFN>8*FK>Fco-%%modsG6$FcoF^p42FhoFeoC%>Fco-Fap6$-% &chremG6$7$FcoF\\p7$F^pFK*&FKFNF^pFN>F^pF^q@$3-%'divideG6$F5Fco-Fcq6$F ;Fco-%'RETURNG6#-F7Fbo>FKFXF2F2F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N := 5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"\"& " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "f1 := randpoly(x,degree =N);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,.*$)%\"xG\"\"&\"\"\"\"# x*$)F(\"\"%F*\"#m*$)F(\"\"$F*\"#a*$)F(\"\"#F*!\"&F(\"#**!#h\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "f2 := expand( f1*randpoly(x, degree=N)*(x-30));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G,:*$)%\"xG \"\"#\"\"\"\"')4?\"F(\"'U.9*$)F(\"\"'F*\"'w;<*$)F(\"\"&F*\"&>#z*$)F(\" \"%F*\"'z>?*$)F(\"\"$F*!&DE$*$)F(\"#6F*!%]Q*$)F(\"#5F*\"'w76*$)F(\"\"* F*\"'U=7*$)F(\"\")F*\"'Tr9*$)F(\"\"(F*!&[)H!'gM6\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "f1 := expand( f1*randpoly(x,degree= N)*x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,8*$)%\"xG\"\"#\"\"\" \"%!y(*$)F(\"\"'F*!%mw*$)F(\"\"&F*!%&\\'*$)F(\"\"%F*\"% " 0 "" {MPLTEXT 1 0 28 " trace(modular_gcd)(f1,f2,x);" }}{PARA 9 "" 1 "" {TEXT -1 257 "\{--> en ter modular_gcd, args = 7780*x^2-7666*x^6-6495*x^5+3417*x^4-3377*x^3+7 7*x^11-3553*x^10-10055*x^9-12168*x^8-12379*x^7-2501*x, 120098*x^2+1403 42*x+171676*x^6+79219*x^5+201979*x^4-32625*x^3-3850*x^11+111276*x^10+1 21842*x^9+147141*x^8-29848*x^7-113460, x" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,8*$)%\"xG\"\"#\"\"\"\"%!y(*$)F(\"\"'F*!%mw*$)F(\"\"&F*!%& \\'*$)F(\"\"%F*\"%%#f2G,:*$)%\"xG\"\"#\"\"\"\"')4?\"F(\"'U.9*$)F( \"\"'F*\"'w;<*$)F(\"\"&F*\"&>#z*$)F(\"\"%F*\"'z>?*$)F(\"\"$F*!&DE$*$)F (\"#6F*!%]Q*$)F(\"#5F*\"'w76*$)F(\"\"*F*\"'U=7*$)F(\"\")F*\"'Tr9*$)F( \"\"(F*!&[)H!'gM6\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"lG\"#x " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,**$)%\"xG\"\"'\"\"\"\"\"\"*$)F(\"\"$F*F+*$)F(\" \"#F*F+F(F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,**$)%\"xG\"\"'\" \"\"\"#x*$)F(\"\"$F*F+*$)F(\"\"#F*F+F(F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,**$)%\"xG \"\"'\"\"\"\"\"\"*$)F(\"\"$F*F+*$)F(\"\"#F*F+F(F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,( *$)%\"xG\"\"'\"\"\"\"\"\"*$)F(\"\"$F*\"\"#F(F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,*%\"xG!\"\"*$)F&\"\"$\"\"\"\"\"\"*$)F&\"\"#F+F** $)F&\"\"'F+F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,,*$)%\"xG\"\"'\"\"\"\"\"\"*$)F(\"\"&F*\"\"$*$)F(\"\"%F*\"\"# *$)F(F3F*F3F(F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.%\"xG!\"\"* $)F&\"\"&\"\"\"\"\"'*$)F&\"\"%F+!\"'*$)F&\"\"$F+!\"&*$)F&\"\"#F+\"\"** $)F&F,F+!#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"#I" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%\"pG\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#8" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#gpG,.*$)%\"xG\"\"&\"\"\"\"\"\"*$)F(\"\"%F*\"# 7*$)F(\"\"$F*\"#6*$)F(\"\"#F*F)F(F)\"\"*F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.*$)%\"xG\"\"&\"\"\"\"#x*$)F(\"\"%F*\"$C**$)F(\" \"$F*\"$Z)*$)F(\"\"#F*\"$&QF(F7\"$$p\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.* $)%\"xG\"\"&\"\"\"!\"\"*$)F(\"\"%F*\"\"\"*$)F(\"\"$F*\"\"#*$)F(F3F*!\" &F(F6F.F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#<" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#gpG,.*$)%\"xG\"\"&\"\"\"\"\"\"*$)F(\"\"%F*\"# 8*$)F(\"\"$F*\"\"'*$)F(\"\"#F*\"\"(F(\"#6\"#9F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.*$)%\"xG\"\"&\"\"\"\"#x*$)F(\"\"%F*\"#m*$)F(\" \"$F*\"#a*$)F(\"\"#F*!\"&F(\"#**!#h\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"$@#" }}{PARA 9 "" 1 "" {TEXT -1 77 "<-- exit mo dular_gcd (now at top level) = 77*x^5+66*x^4+54*x^3-5*x^2+99*x-61\}" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$)%\"xG\"\"&\"\"\"\"#x*$)F&\"\"%F( \"#m*$)F&\"\"$F(\"#a*$)F&\"\"#F(!\"&F&\"#**!#h\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "6 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }