{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 } {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 "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 }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 1 }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 1 }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 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 "" {MPLTEXT 1 0 3095 "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 w as not a common factor of f1,f2, then we did\n # not yet calculate g modulo a sufficiently large\n # number m. So we'll compute g mo dulo a higher number\n # by using more primes:\n p := nextprim e(p)\n od\nend;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,modular_gcdGj+6 %%#F1G%#F2G%\"xG6)%#f1G%#f2G%\"lG%\"pG%#gpG%\"gG%\"mG6\"F2C'>8$-%)prim partG6#9$>8%-F76#9%>8&-%%igcdG6$-%'lcoeffG6$F59&-FE6$F;FG>8'\"\"#?(F2 \"\"\"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; FcoO-F7Fbo>FKFXF2F2F26%FVFV\"'k88" }}}{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,.\"#]\"\"\"*&\"#&)F')% \"xG\"\"&F'!\"\"*&\"#bF')F+\"\"%F'F-*&\"#PF')F+\"\"$F'F-*&\"#NF')F+\" \"#F'F-*&\"#(*F'F+F'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "f 2 := expand( f1*randpoly(x,degree=N)*(x-30));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#f2G,:*&\"&SK)\"\"\"%\"xGF(F(\"&+&))F(*&\"'$>D$F()F) \"\"#F(!\"\"*&\"';)R\"F()F)\"\"'F(F(*&\"''**4#F()F)\"\"&F(F/*&\"'rd=F( )F)\"\"%F(F/*&\"'EF()F)\"# 5F(F(*&\"'#)HEF()F)\"\"*F(F(*&\"'`@HF()F)\"\")F(F(*&\"'!>#QF()F)\"\"(F (F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "f1 := expand( f1*ran dpoly(x,degree=N)*x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,8*&\"% +J\"\"\"%\"xGF(!\"\"*&\"%kQF()F)\"\"#F(F**&\"%IUF()F)\"\"'F(F(*&\"&A3 \"F()F)\"\"&F(F**&\"%j]F()F)\"\"%F(F(*&\"&T4\"F()F)\"\"$F(F(*&\"%DQF() F)\"#6F(F**&\"%&z\"F()F)\"#5F(F**&\"%!o'F()F)\"\"*F(F(*&\"%%)RF()F)\" \")F(F**&\"$H'F()F)\"\"(F(F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "trace(modular_gcd)(f1,f2,x);" }}{PARA 9 "" 1 "" {TEXT -1 259 "\{ --> enter modular_gcd, args = -3100*x-3864*x^2+4230*x^6-10822*x^5+5063 *x^4+10941*x^3-3825*x^11-1795*x^10+6680*x^9-3984*x^8-629*x^7, 83240*x+ 88500-325193*x^2+139816*x^6-209996*x^5-185771*x^4-251726*x^3-6715*x^11 +192345*x^10+262982*x^9+292153*x^8+382190*x^7, x" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,8*&\"%+J\"\"\"%\"xGF(!\"\"*&\"%kQF()F)\"\"#F(F** &\"%IUF()F)\"\"'F(F(*&\"&A3\"F()F)\"\"&F(F**&\"%j]F()F)\"\"%F(F(*&\"&T 4\"F()F)\"\"$F(F(*&\"%DQF()F)\"#6F(F**&\"%&z\"F()F)\"#5F(F**&\"%!o'F() F)\"\"*F(F(*&\"%%)RF()F)\"\")F(F**&\"$H'F()F)\"\"(F(F*" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#f2G,:*&\"&SK)\"\"\"%\"xGF(F(\"&+&))F(*&\"'$>D$F ()F)\"\"#F(!\"\"*&\"';)R\"F()F)\"\"'F(F(*&\"''**4#F()F)\"\"&F(F/*&\"'r d=F()F)\"\"%F(F/*&\"'EF()F )\"#5F(F(*&\"'#)HEF()F)\"\"*F(F(*&\"'`@HF()F)\"\")F(F(*&\"'!>#QF()F)\" \"(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"lG\"#&)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%# gpG,,*$)%\"xG\"\"'\"\"\"F**$)F(\"\"&F*F**$)F(\"\"%F*F**$)F(\"\"$F*F**$ )F(\"\"#F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,,*&\"#&)\"\"\") %\"xG\"\"'F(F(*&F'F()F*\"\"&F(F(*&F'F()F*\"\"%F(F(*&F'F()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(\"\"$F*F**$)F(\"\"#F*F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,. *$)%\"xG\"\"*\"\"\"F**&\"\"#F*)F(\"\"'F*F**$)F(\"\"&F*F**$)F(\"\"$F*F* *&F,F*)F(F,F*F*F(F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"&" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,,*$)%\"xG\"\"(\"\"\"F**&\"\"%F*)F(\"\"'F*F**&F,F *)F(\"\"#F*F**&\"\"&F*F(F*F*F,F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"pG\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,,*$)%\"xG\"\"&\"\" \"F**&\"\"'F*)F(\"\"$F*F**&F.F*)F(\"\"#F*F**&F.F*F(F*F*F1F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,,*&\"#&)\"\"\")%\"xG\"\"&F(F(*&\"$5&F ()F*\"\"$F(F(*&\"$b#F()F*\"\"#F(F(*&F1F(F*F(F(\"$q\"F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\" gG,,*&\"\"$\"\"\")%\"xG\"\"&F(!\"\"*&\"\"%F()F*F'F(F(*&\"\"#F()F*F1F(F (*&F1F(F*F(F(F+F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#8" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,.*$)%\"xG\"\"&\"\"\"F**&\"\"'F* )F(\"\"%F*F**&\"\"*F*)F(\"\"$F*F**&F)F*)F(\"\"#F*F*F(F*F.F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.*&\"#e\"\"\")%\"xG\"\"&F(!\"\"*&\"#P F()F*\"\"$F(F(*&\"#NF()F*\"\"#F(F(*&\"#YF(F*F(F(\"#]F,*&\"#bF()F*\"\"% F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"$V\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG \"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#gpG,.*$)%\"xG\"\"&\"\"\"F** &\"\"%F*)F(F,F*F**&\"\"#F*)F(\"\"$F*F**&\"\"'F*)F(F/F*F**&F,F*F(F*F*F) F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,.*&\"#&)\"\"\")%\"xG\"\"& F(F(*&\"#PF()F*\"\"$F(F(*&\"#NF()F*\"\"#F(F(*&\"#(*F(F*F(!\"\"\"#]F6*& \"#bF()F*\"\"%F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"mG\"% " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "6 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }