{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 Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 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 }{CSTYLE " " -1 256 "helvetica" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "times" 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "courier" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "helvetica" 0 1 0 0 0 0 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 "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 }0 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 "Error" 7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 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 {SECT 1 {PARA 3 "" 0 "" {TEXT -1 1 " " }{TEXT 261 1 "Q" } {TEXT -1 11 "[X] by MGCD" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 " read MGCD;\nread PGCD;\nread recden;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 273 "The algorithm used is Brown's modular GCD algorithm with integ er reconstruction, not rational reconstruction, and trial division aft er one additional prime more than the minimum. Hence in this example, where one prime is sufficient to compute the GCD, two primes are used ." }}{PARA 0 "" 0 "" {TEXT -1 44 "The same logic is used for each modu lar GCD." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 215 "g := 12*x-11*y +23*z-13:\nabar := randpoly([x,y,z],dense):\nbbar := randpoly([x,y,z], dense):\na := expand(g*abar):\nb := expand(g*bbar):\nA := convert(a,PO LYNOMIAL,[x,y,z]):\nB := convert(b,POLYNOMIAL,[x,y,z]):\nMGCD(A,B); " }}{PARA 6 "" 1 "" {TEXT -1 35 "MGCD: GCD in Q[x, y, z], gamma = 12" }} {PARA 6 "" 1 "" {TEXT -1 20 "MGCD: Prime is 46327" }}{PARA 6 "" 1 "" {TEXT -1 35 " PGCD: Gcd in GF(46327)[x, y, z]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGC D: Gcd in GF(46327)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod \+ " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46 327)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46327)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 "MGCD: Prime is 46309" }} {PARA 6 "" 1 "" {TEXT -1 35 " PGCD: Gcd in GF(46309)[x, y, z]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46309)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46309)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGC D: Gcd in GF(46309)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod \+ " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #,*%\"xG\"#7*&\"#6\"\"\"%\"yGF(!\"\"*&\"#BF(%\"zGF(F(\"#8F*" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 " " {TEXT -1 4 " GF(" }{TEXT 257 1 " " }{TEXT 258 1 "q" }{TEXT 259 1 " \+ " }{TEXT -1 34 ")[X] by PGCD with field extensions" }}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 32 "restart;\nread recden;\nread PGCD;" }}{PARA 6 "" 1 "" {TEXT -1 28 "\"Reading recden for Maple 5\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 " GF(4)[" }{TEXT 260 3 "x,y" }{TEXT -1 1 "] " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 340 "p := 2:\nalias(alpha = RootOf(x^2+x+1)):\nX := [alpha,x,y]:\ng := expand(randpoly(X,degree=5 ,dense)) mod p:\na := expand(randpoly(X,degree=10,dense)*g) mod p:\nb \+ := expand(randpoly(X,degree=10,dense)*g) mod p:\nX := [x,y,w]:\nA := c onvert(a,POLYNOMIAL,X,w=alpha,p);\nB := convert(b,POLYNOMIAL,X,w=alpha ,p);\nst := time(): G := PGCD(A,B); time()-st;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"AG-%$modG6$,Z%\"wG\"\"\"*$)%\"yG\"\")\"\"\"F**$)F- \"\"#F/F**&F)F*)F-\"\"&F/F**&F)F/)F-\"\"%F/F**&F)F/)F-\"\"$F/F**&F)F/) F-\"#6F/F**&F)F/)F-\"\"*F/F**&F)F/F-F*F**&)%\"xG\"#9F/F)F/F**&)F-\"#8F /F)F/F**&F)F/)F-\"\"'F/F**&,6F*F*F-F**&,&F*F*F)F*F*F1F/F**&FPF/F:F/F** &FPF/F7F/F**$FKF/F**&FPF/)F-\"\"(F/F*F+F*F?F**$)F-\"#5F/F*F*)FEF5F/F** &,2F*F*F)F**$F:F/F*F6F*F3F**&FPF/FKF/F*FTF**&FPF/F,F/F*F*)FEFLF/F**&,* F9F*FRF**&FPF/F4F/F*FSF*F*)FEFVF/F**&,(F)F**&FPF/F-F/F*FOF*F*)FEF.F/F* *&,0F*F*F)F*FBF*F0F**$F7F/F**$F4F/F*FSF*F*)FEFAF/F**&,>F)F*FBF*F0F*Fgn F*F6F*FfoF*FhnF**&FUF/F)F/F*FinF**$F@F/F**&FPF/FXF/F**$F=F/F**&)F-\"#7 F/F)F/F**&FPF/FHF/F*F*FEF*F**&,8F)F*F-F*F0F*F9F*FfoF*FJF*FjoF*F?F*F\\p F**$F_pF/F**$FHF/F*F*)FEF2F/F**&,6FaoF*FQF*FRF*F]oF*FJF**&F,F/F)F/F*F? F*F\\pF**&FPF/F=F/F*FdpF*F*)FEF;F/F**&,.F-F*F0F*FhnF*FjoF*F+F*F[pF*F*) FEF8F/F*FTF*F\\pF**&FPF/F_pF/F**&,,F*F*F)F*FBF**&F)F/F1F/F*FgnF*F*)FEF `pF/F**&,&F)F*F0F*F*)FEFIF/F**&,*F)F*FaoF*FgnF*F6F*F*)FEFYF/F**&,(F-F* FOF*FeoF*F*)FEF>F/F*-%-anglebracketG6$,(*$)F)F2F/F*F)F*F*F*F2" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"BG-%$modG6$,R\"\"\"F)%\"wGF)%\"yGF )*&F*F))F+\"\"#\"\"\"F)*&,&F)F)F*F)F))F+\"\"$F/F)*$)F+\"\"&F/F)*&F1F/) F+\"\"'F/F)*&)F+\"\"(F/F*F/F)*&)F+\"\")F/F*F/F)*$)F+\"#7F/F)*&,8F)F)*& F1F/F+F)F)*&F1F/F-F/F)*&F*F/F2F/F)*&F*F/)F+\"\"%F/F)F4F)*$F;F/F)*&F1F/ F>F/F)*&F1F/)F+\"\"*F/F)*&F1F/)F+\"#5F/F)*&F*F/)F+\"#6F/F)F)%\"xGF)F)* &,6F)F)FEF)FFF)*$FIF/F)*&F1F/F5F/F)*$F8F/F)*&F1F/F;F/F)*$FNF/F)*$FQF/F )*&F1F/FTF/F)F))FVF.F/F)*&,4F+F)F,F)FYF)*&F*F/F8F/F)F=F)*&F*F/FNF/F)FP F)FinF)F@F)F))FVF3F/F)*&,6F)F)*&F*F/F+F/F)FFF)FGF)*&F1F/FIF/F)FZF)FenF )FKF)F=F)*&FQF/F*F/F)F))FVFJF/F)*&,2F)F)FEF)F0F)FcoF)F4F)F7F)FKF)FhnF) F))FVF6F/F)*&,,F+F)FFF)FHF)*&F*F/F5F/F)*$F>F/F)F))FVF9F/F)*&,0FboF)*$F -F/F)*$F2F/F)FYF)F4F)F]oF)F:F)F))FVF" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " ... mod , a fi eld extension of GF(4)" }}{PARA 6 "" 1 "" {TEXT -1 49 " ... mod <1+ w+y^3>, a field extension of GF(4)" }}{PARA 12 "" 1 "" {XPPMATH 20 "6# >%\"GG-%$modG6$,4\"\"\"F)*&,&F)F)%\"wGF)F)%\"yGF)F)*&F,F))F-\"\"#\"\" \"F)*&F,F1)F-\"\"$F1F)*&,(F,F)*&F,F1F-F1F)*&F+F1F3F1F)F)%\"xGF)F)*&,(F ,F)F.F)*$F3F1F)F))F9F0F1F)*&,*F)F)F,F)F7F)*$F/F1F)F))F9F4F1F)*&F,F1)F9 \"\"%F1F)*$)F9\"\"&F1F)-%-anglebracketG6$,(*$)F,F0F1F)F,F)F)F)F0" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#$\"%HQ!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 477 "There is no good code to solve this GCD problem nor the \+ following ones in Maple. \nIn all three cases, the subresultant algor ithm gets used and there is a blowup. Note also, that the above time \+ is slow. We would expect to see a factor of 10 to 100 improvement wit h kernel support. The same improvement is expected for the following \+ examples too. The new code handles all finite fields, small fields wh ich require field extensions, and fields with multiple field extension s." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "infolevel[Gcd] := 3: \+ \nst := time(): Gcd(a,b) mod p; time()-st;" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 56 "mod/Gcd/subres: degree of the pseudo remainder \+ is 11" }}{PARA 6 "" 1 "" {TEXT -1 56 "mod/Gcd/subres: degree of th e pseudo remainder is 10" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/sub res: degree of the pseudo remainder is 9" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subres: degree of the pseudo remainder is 8" }} {PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subres: degree of the pseudo re mainder is 7" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subres: degre e of the pseudo remainder is 6" }}{PARA 8 "" 1 "" {TEXT -1 44 "Error , (in unknown) modp1: invalid arguments" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&R*Q!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Problem from Hans Dobbertin (Coding Theory) over GF(2) in four variables" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 417 "A,B,C,Z := 'A,B,C,Z':\nz := (A^2*B^2*Z^2+A^2*B^2+B^2*Z^2+Z^2+B^2)/Z:\na := (B^2*C^2*A^2+B^2*C^2+C ^2*A^2+A^2+C^2)/A:\nb := (C^2*Z*B^2+C^2*Z+Z*B^2+B^2+Z)/B:\nc := (Z*A*C ^2+Z*A+A*C^2+C^2+A)/C:\nf := Z^2*A^3*B^2*C^2*(z^2*b^2*c^2+(a+z+1)^2*(a +c^2+1)):\np := expand(f) mod 2:\nq := diff(p,A) mod 2:\nX := [A,B,C,Z ]:\nP := convert(p,POLYNOMIAL,X,2);\nQ := convert(q,POLYNOMIAL,X,2);\n st := time(): G := PGCD(P,Q); time()-st;\nz := 'z':\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"PG-%$modG6$,<*()%\"BG\"\"'\"\"\")%\"CG\"\")F-) %\"ZG\"\"#F-\"\"\"*(F1F-)F+F3F-F.F-F4*(F.F-F1F-)F+\"\"%F-F4*()F+F0F-F. F-F1F-F4*&,&*&,&*&F1F-)F/F,F-F4*&F1F-F.F-F4F4F6F-F4*&F?F-F*F-F4F4%\"AG F4F4*&,**&,(*&,&*$F1F-F4*$)F2F9F-F4F4)F/F9F-F4F@F4FBF4F4F6F-F4*&,&FIF4 FBF4F4F8F-F4*&,(*&,&FLF4F4F4F4FNF-F4F@F4FBF4F4F*F-F4*&,&FSF4FBF4F4F;F- F4F4)FDF3F-F4*&,.*&)F2F,F-F.F-F4*&FenF-FNF-F4*&,&*&FJF-)F/F3F-F4*&FJF- F.F-F4F4F6F-F4FOF4*&,(*&FTF-FjnF-F4*&,&F4F4FKF4F4FNF-F4F[oF4F4F*F-F4*& ,&*&,*F4F4*$FenF-F4FKF4FLF4F4FNF-F4*&,&FeoF4FKF4F4F.F-F4F4F;F-F4F4)FD \"\"$F-F4*&,**&,(FinF4*&FMF-FNF-F4FBF4F4F6F-F4*&,&F^pF4FBF4F4F8F-F4*&, (F^oF4FSF4FBF4F4F*F-F4FUF4F4)FDF9F-F4*&,0FeoF4*$)F2F0F-F4*&,&FeoF4FfpF 4F4F.F-F4*&,.FfnF4F@F4FeoF4FBF4*&FjnF-F1F-F4FKF4F4F6F-F4*&,*FeoF4FKF4* &,&FeoF4FLF4F4FNF-F4F[oF4F4F8F-F4*&,0F4F4FeoF4FKF4FLF4FcoF4F@F4FBF4F4F *F-F4*&,*F4F4FfpF4FcoF4*&,*FKF4FfpF4FeoF4FLF4F4F.F-F4F4F;F-F4F4)FD\"\" &F-F4*&,**&,*FBF4F@F4*&FNF-F1F-F4F\\qF4F4F6F-F4*&,&FBF4F]rF4F4F8F-F4FQ F4FUF4F4)FDF,F-F4*&,**&,(FKF4FLF4F[oF4F4F6F-F4*&,&*&FgoF-FNF-F4FfoF4F4 F8F-F4F\\oF4FaoF4F4)FD\"\"(F-F4*&,&*&,&F^oF4FSF4F4F*F-F4*(FTF-FNF-F;F- F4F4)FDF0F-F4*&,(*&,,FKF4FfpF4FeoF4FLF4FeqF4F4F8F-F4*&,,F4F4FeoF4FKF4F LF4FcoF4F4F*F-F4FcqF4F4)FD\"\"*F-F4F3" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"QG-%$modG6$,.*&,&*&)%\"ZG\"\"#\"\"\")%\"CG\"\"'F/\"\"\"*&F,F/)F 1\"\")F/F3F3)%\"BGF.F/F3*&F*F/)F8F2F/F3*&,.*&)F-F2F/F5F/F3*&F>F/)F1\" \"%F/F3*&,&*&,&*$F,F/F3*$)F-FAF/F3F3)F1F.F/F3*&FEF/F5F/F3F3F7F/F3*&,&* &FEF/F@F/F3F4F3F3)F8FAF/F3*&,(*&,&FGF3F3F3F3FIF/F3*&,&F3F3FFF3F3F@F/F3 FJF3F3F:F/F3*&,&*&,*F3F3*$F>F/F3FFF3FGF3F3F@F/F3*&,&FYF3FFF3F3F5F/F3F3 )F8F6F/F3F3)%\"AGF.F/F3*&,0FYF3*$)F-F6F/F3*&,&FYF3F[oF3F3F5F/F3*&,.F?F 3F+F3FYF3F4F3*&FIF/F,F/F3FFF3F3F7F/F3*&,*FYF3FFF3*&,&FYF3FGF3F3F@F/F3F JF3F3FNF/F3*&,0F3F3FYF3FFF3FGF3FWF3F+F3F4F3F3F:F/F3*&,*F3F3F[oF3FWF3*& ,*FFF3F[oF3FYF3FGF3F3F5F/F3F3FfnF/F3F3)FhnFAF/F3*&,**&,(FFF3FGF3FJF3F3 F7F/F3*&,&*&FenF/F@F/F3FZF3F3FNF/F3FOF3FUF3F3)FhnF2F/F3*&,(*&,,FFF3F[o F3FYF3FGF3FjoF3F3FNF/F3*&,,F3F3FYF3FFF3FGF3FWF3F3F:F/F3FhoF3F3)FhnF6F/ F3F." }}{PARA 6 "" 1 "" {TEXT -1 34 " PGCD: Gcd in GF(2)[A, B, C, Z ]" }}{PARA 6 "" 1 "" {TEXT -1 51 " ... mod <1+Z^2+Z^5>, a field ext ension of GF(2)" }}{PARA 6 "" 1 "" {TEXT -1 50 " PGCD: GCD in GF(2) [Z][A, B, C] where 1+Z^2+Z^5" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... m od " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(2)[Z][A, \+ B] where 1+Z^2+Z^5" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 21 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 21 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 23 " ... mod " }}{PARA 6 " " 1 "" {TEXT -1 19 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 21 " ... mod " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#QCTrial~D ivisions~failed:~continuing6\"" }}{PARA 6 "" 1 "" {TEXT -1 21 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 23 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(2)[Z][A, B] where 1+Z^2+Z^5" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG-%$modG6$\"\"\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$ \"%9@!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "st := time(): \+ Gcd(p,q) mod 2; time()-st;" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/sub res: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm " }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresult ant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/s ubres: degree of the pseudo remainder is 1" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }} {PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant \+ algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subre s: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 " " {TEXT -1 55 "mod/Gcd/subres: degree of the pseudo remainder is 1 " }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresult ant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/s ubres: degree of the pseudo remainder is 2" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }} {PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant \+ algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subre s: degree of the pseudo remainder is 2" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subres: degree of the pseudo remainder is 1" }} {PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant \+ algrorithm" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subres: degree of the pseudo remainder is 3" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/s ubres: degree of the pseudo remainder is 2" }}{PARA 8 "" 1 "" {TEXT -1 43 "Error, (in expand/bigprod) object too large" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#$\"&qE#!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 59 "From SIGSAM Bulletin, Lewis/Wester Test Suite, Spring 2000." }} {PARA 0 "" 0 "" {TEXT -1 247 "The GCD is relatively large compared wit h the cofactors. But because the field extension is quadratic, we wou ld expect a big gain in performance if arithmetic in GF(q)[x] is in th e kernel for one field extension. A gain of a factor of 10 to 100." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 440 "p := 17027:\nt := RootOf( w^2+1):\na := (7*t*y*x^2*z^2-3*t+t*x*y*z+11*(x+1+t)*y^2+5*z+t+1)^5 *\n (3*t*x-7*t*y+2*z-3*t+1)^4:\nb := (7*t*y*x^2*z^2-3*t+t*x*y*z+11*(x +1+t)*y^2+5*z+t+1)^2 *\n (3*t*x-7*t*y+2*z-3*t+1)^7:\n# Test GCD(Ex pand(a) mod p,Expand(b) mod p) mod p;\na := Expand(a) mod p:\nb := Exp and(b) mod p:\nA := convert(a,POLYNOMIAL,[x,y,z,w],w=t,p):\nB := conve rt(b,POLYNOMIAL,[x,y,z,w],w=t,p):\nst := time(): G := PGCD(A,B); time ()-st;" }}{PARA 6 "" 1 "" {TEXT -1 50 " PGCD: GCD in GF(17027)[w][x , y, z] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027)[w][x, y] w here w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " .. . mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027) [w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " .. . mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " P GCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod < y-2>" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 " " 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " } }{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(1702 7)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " .. . mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 18 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 47 " \+ PGCD: GCD in GF(17027)[w][x, y] where w^2+1" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod < y-2>" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 18 " ... mod " }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"GG-%$modG6$,R\"%;v\"\"\"%\"wG\"%I8 *&,&\"%AdF*F+\"&nV\"F*%\"zGF*F**&,&\"%ENF*F+\"%kMF*)F1\"\"#\"\"\"F**&, &\"$#zF*F+\"&sN\"F*)F1\"\"$F8F**&,&\"%=yF*F+\"&#p5F*)F1\"\"%F8F**&,&\" &NQ\"F*F+\"%W!*F*)F1\"\"&F8F**$)F1\"\"'F8\"&(p:*&,0\"&sB\"F*F+\"&lR\"* &,&\"%i!*F*F+\"%5$*F*F1F8F**&,&\"&[e\"F*F+\"&J`\"F*F6F8F**&,&\"&CK\"F* F+\"%hQF*F=F8F**&,&\"&^N\"F*F+\"%C8F*FCF8F**&F+F*FIF8\"%$f\"F*%\"yGF*F **&,0\"%gQF*F+\"%=V*&,&\"&W,\"F*F+\"%5\")F*F1F8F**&,&\"&MO\"F*F+\"%\"* \\F*F6F8F**&,&\"%q6F*F+\"&4K\"F*F=F8F**&,&\"%jlF*F+\"%YTF*FCF8F**&,&\" &v6\"F*F+FfpF*FIF8F*F*)F_oF7F8F**&,.\"%$o$F*F+\"%J^*&,&\"%F:F*F+\"&*p6 F*F1F8F**&,&\"&05\"F*F+\"%\\QF*F6F8F**&,&\"&q,\"F*F+\"&gj\"F*F=F8F**&, &\"%2KF*F+\"&?Q\"F*FCF8F*F*)F_oF>F8F**&,.\"&wd\"F*F+\"&&e5*&,&\"%@uF*F +\"%+HF*F1F8F**&,&\"%`UF*F+\"%)3&F*F6F8F**&,&\"&Td\"F*F+\"%ODF*F=F8F** &F+F8FCF8\"%evF*)F_oFDF8F**&,,\"&`Y\"F*F+\"&En\"*&,&\"&CL\"F*F+\"%PJF* F1F8F**&,&\"%+XF*F+\"%x:F*F6F8F**$F=F8\"%]OF*)F_oFJF8F**&,*\"&kk\"F*F+ \"%s>*&,&\"&-O\"F*F+\"$Y)F*F1F8F**&F+F8F6F8\"%yjF*)F_oFMF8F**&,(\"%TuF *F+\"&J<\"F1\"&#)[\"F*)F_o\"\"(F8F**&F+F8)F_o\"\")F8\"%i#)*&,@\"%&*>F* F+\"&U5\"*&,&\"%YeF*F+\"&PI\"F*F1F8F**&,&\"&N-\"F*F+\"&*)G\"F*F6F8F**& ,&\"&#z8F*F+\"%v!)F*F=F8F**&,&\"%(y)F*F+\"%l=F*FCF8F*F]o\"%Z!**&,0F+\" %'=**&,&\"&'z8F*F+\"$^\"F*F1F8F**&,&\"%!y%F*F+\"&WB\"F*F6F8F**&,&\"%n# )F*F+\"%(*\\F*F=F8F**&,&\"&?D\"F*F+\"%[uF*FCF8F**&,&\"%1MF*F+\"%NAF*FI F8F**&F+F8FLF8\"&&\\;F*F_oF8F**&,0\"&\"H;F*F+\"%IV*&,&\"%'p*F*F+\"%s%) F*F1F8F**&,&\"%#=*F*F+\"%:cF*F6F8F**&,&\"&3=\"F*F+\"&K0\"F*F=F8F**&,& \"%w&*F*F+\"%#y%F*FCF8F**$FIF8\"%FPF*FgpF8F**&,0\"&Ch\"F*F+\"%XO*&,&\" %!*oF*F+\"%?dF*F1F8F**&,&\"&>e\"F*F+\"%3HF*F6F8F**&,&\"%H$)F*F+\"&V^\" F*F=F8F**&,&\"%S*)F*F+\"%%p#F*FCF8F**&,&\"&#z9F*F+F`xF*FIF8F*F*F\\rF8F **&,.\"&yM\"F*F+\"%Y)**&,&\"&mn\"F*F+FgnF*F1F8F**&,&\"%mLF*F+\"%,9F*F6 F8F**&,&\"%#3*F*F+\"&9@\"F*F=F8F**&,&\"%%z%F*F+Fa\\lF*FCF8F*F*F_sF8F** &,,\"&%37F*F+\"%dS*&,&\"%_HF*F+\"%gbF*F1F8F**&,&\"%X5F*F+\"%3NF*F6F8F* *&,&\"%mhF*F+\"&h3\"F*F=F8F*F*F^tF8F**&,*\"%qlF*F+\"%!y\"*&,&\"$c%F*F+ \"%mWF*F1F8F**&,&\"%$='F*F+F\\^lF*F6F8F*F*FitF8F**&,(\"%X@F*F+\"%'e**& ,&\"&$e7F*F+\"%WWF*F1F8F*F*F_uF8F**&,&FduF*F+FduF*FbuF8F*F*%\"xGF*F**& ,XF*F1F8F**&,&\"%bxF*F+\"$!pF*F6F8F**&,&FgoF *F+\"&1p\"F*F=F8F**$FCF8\"$G**&,4\"%bSF*F+\"&l@\"*&,&\"%T[F*F+\"&[p\"F *F1F8F**&,&\"%OyF*F+\"&:j\"F*F6F8F**&,&\"%XuF*F+\"&#>:F*F=F8F**&,&\"&b E\"F*F+\"&X3\"F*FCF8F**&,&\"&4L\"F*F+\"%b5F*FIF8F**&,&\"%:oF*F+\"&Xc\" F*FLF8F**&F+F8)F1F`uF8\"&.L\"F*F_oF8F**&,2\"&`5\"F*F+\"&cT\"*&,&\"&MC \"F*F+\"&T9\"F*F1F8F**&,&\"&(G7F*F+\"%>sF*F6F8F**&,&\"%zdF*F+\"&BA\"F* F=F8F**&,&\"%m@F*F+\"&U@\"F*FCF8F**&,&\"%@MF*F+\"%`lF*FIF8F*FK\"%4eF*F gpF8F**&,2\"%fHF*F+Fbcl*&,&\"%HjF*F+\"&#>5F*F1F8F**&,&\"&)G6F*F+\"%*e) F*F6F8F**&,&\"%%['F*F+\"%sNF*F=F8F**&,&\"&]G\"F*F+\"%QCF*FCF8F**&,&\"& *\\6F*F+\"&ab\"F*FIF8F**&,&\"%#Q\"F*F+FcalF*FLF8F*F*F\\rF8F**&,0\"&d> \"F*F+\"%iv*&,&\"%udF*F+\"%)**)F*F1F8F**&,&\"&;,\"F*F+\"%#f(F*F6F8F**& ,&\"&0q\"F*F+\"%V9F*F=F8F**&,&\"%i?F*F+\"%jpF*FCF8F**&,&\"&1Z\"F*F+F`f lF*FIF8F*F*F_sF8F**&,.\"%B))F*F+\"%7I*&,&\"$U\"F*F+\"%Q'*F*F1F8F**&,& \"%ZSF*F+\"&=J\"F*F6F8F**&,&\"&de\"F*F+\"%ZHF*F=F8F**&,&\"$&eF*F+\"&Uk \"F*FCF8F*F*F^tF8F**&,,\"&cF\"F*F+\"%2@*&,&\"%x7F*F+\"%n&*F*F1F8F**&,& \"%t')F*F+\"%l8F*F6F8F**&,&\"&ic\"F*F+FchlF*F=F8F*F*FitF8F**&,*\"%[EF* F+\"&*35*&F+F8F1F8\"&&)=\"*&,&\"$M*F*F+\"&$4;F*F6F8F*F*F_uF8F**$FbuF8 \"%JTF*)Fg^lF7F8F**&,:\"%=nF*F+\"%FJ*&,&\"&X\"F*F+\"$M$F*F= F8F*F]s\"&qZ\"F*F^tF8F**&,*F+\"%guFhhl\"$h(*$F6F8F`hlF\\t\"&*>9F*FitF8 F**&,&FfhlF*FgtF]ilF*F_uF8F*F*)Fg^lF>F8F**&,6\"%&3#F*F+\"%!y#*&,&\"&x+ \"F*F+\"&+R\"F*F1F8F*Fcam\"&zm\"*&,,*&,&\"%\"f$F*F+FebmF*F1F8F**&,&\"% &H(F*F+\"%UwF*F6F8F**&,&\"&Tj\"F*F+\"%@CF*F=F8F**&,&\"%nSF*F+\"%PCF*FC F8F*F]o\"&?i\"F*F_oF8F**&,6\"&e1\"F*F+\"%V)**&,&\"%z>F*F+\"&A6\"F*F1F8 F**&,&\"%p$*F*F+\"&&4;F*F6F8F**&,&\"$(fF*F+\"&$G5F*F=F8F**&,&\"%!)HF*F +\"%beF*FCF8F**&,&\"&f+\"F*F+\"%K(*F*FIF8F**&,&\"&%R;F*F+\"%S9F*FLF8F* *&,&\"%>')F*F+\"%(>)F*FealF8F**$)F1FcuF8\"&BG\"F*FgpF8F**&,4\"$:)F*F+F e]m*&,&\"%\"R'F*F+\"%KYF*F1F8F**&,&\"&O;\"F*F+\"&oH\"F*F6F8F**&,&F_[mF *F+\"$)>F*F=F8F**&,&\"%MqF*F+\"#]F*FCF8F**&,&\"&v,\"F*F+\"%JWF*FIF8F** &,&\"%Z%*F*F+\"%\\JF*FLF8F*Fdal\"%vxF*F\\rF8F**&,0F+\"%)\\'*&,&\"%\\%) F*F+\"%>oF*F1F8F**&,&\"&Vf\"F*F+\"%z%*F*F6F8F**&,&\"&u7\"F*F+\"%*o&F*F =F8F**&,&\"&6?\"F*F+\"%aPF*FCF8F**&,&\"%3DF*F+\"%.&*F*FIF8F*FKFfhmF*F_ sF8F**&,0\"%JSF*F+\"&'*H\"Fhhl\"&BP\"*&,&\"%=QF*F+\"&a9\"F*F6F8F*F\\t \"%jU*&,&\"%\\#)F*F+\"&,T\"F*FCF8F*F]oFfpF*F^tF8F**&,(\"%&f&F*Fgt\"%mk Ff_l\"%$R$F*FitF8F*F*)Fg^lFDF8F**&,,*&,**&,&\"&ZU\"F*F+\"&Pc\"F*F1F8F* *&,&FgoF*F+\"%g6F*F6F8F**&,&\"%tcF*F+\"&\"z8F*F=F8F*Ff_l\"$2)F*F_oF8F* *&,4\"%P " 0 "" {MPLTEXT 1 0 40 "st := time(): Gcd(a,b) mod p; time()-st;" }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/subres: using the subresultant algrorithm" }} {PARA 6 "" 1 "" {TEXT -1 56 "mod/Gcd/subres: degree of the pseudo re mainder is 10" }}{PARA 6 "" 1 "" {TEXT -1 55 "mod/Gcd/subres: degr ee of the pseudo remainder is 9" }}{PARA 7 "" 1 "" {TEXT -1 32 "Warn ing, computation interrupted" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "time()-st;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"'v[>!\"$" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT 256 2 " Q" }{TEXT -1 2 "( " }{XPPEDIT 18 0 "alpha;" "6#%&alphaG" }{TEXT -1 34 " )[X] by NGCD with field spli tting" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "restart;\nread recd en;\nread NGCD;\nread AGCD;\nread PGCD;" }}{PARA 6 "" 1 "" {TEXT -1 28 "\"Reading recden for Maple 5\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 573 "These first two examples just show that the field splitting id ea is working. So the basic method is compute the GCD modulo primes, \+ use rational reconstruction and check the result using trial division. But if the first field extension of low degree - the minimal polynom ial is degree 4 in the first example - choose the primes so that the m inimal polynomial splits into distinct linear factors so that the modu lar GCDs are mapped into GCDs over the integers modulo primes. Note, \+ Maple will solve these first two problems fine. The third one is a mo re difficult problem." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "Q(" } {XPPEDIT 18 0 "sqrt(2)+sqrt(3);" "6#,&-%%sqrtG6#\"\"#\"\"\"-F%6#\"\"$F (" }{TEXT -1 6 ")[x,y]" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 319 " alpha := RootOf(x^4-10*x^2+1):\nd := 2:\nX := [alpha,x,y]:\ng := randp oly(alpha)*x^d+\nrandpoly(alpha)*y^d+\nrandpoly(X,degree=d,dense):\na \+ := expand(randpoly(X,degree=d,dense)*g): \nb := expand(randpoly(X,degr ee=d,dense)*g):\nX := [x,y,w]:\nA := convert(a,POLYNOMIAL,X,w=alpha): \nB := convert(b,POLYNOMIAL,X,w=alpha):\nNGCD(A,B);" }}{PARA 6 "" 1 " " {TEXT -1 42 "NGCD: GCD in Q[w][x, y] mod " }}{PARA 6 " " 1 "" {TEXT -1 31 "NGCD: I will split w^4-10*w^2+1" }}{PARA 6 "" 1 " " {TEXT -1 68 " NGCD: Prime 46327 ... 46309 ... 46307 ... 46301 ... 46 279 ... 46273" }}{PARA 6 "" 1 "" {TEXT -1 72 " AGCD: w^4-10*w^2+1 = ( w+21667)*(w+12816)*(w+33457)*(w+24606) mod 46273" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 24606" }}{PARA 6 "" 1 "" {TEXT -1 32 " \+ PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... m od " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 3345 7" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 12816" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AG CD: | w = 21667" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46 273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGCD: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 18 " NGCD: Prime 4627 1" }}{PARA 6 "" 1 "" {TEXT -1 72 " AGCD: w^4-10*w^2+1 = (w+10751)*(w+ 14758)*(w+35520)*(w+31513) mod 46271" }}{PARA 6 "" 1 "" {TEXT -1 20 " \+ AGCD: | w = 35520" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in G F(46271)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 31513" }} {PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46271)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 10751" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46271)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AG CD: | w = 14758" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46 271)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGCD: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 58 " NGCD: Prime 4626 1 ... 46237 ... 46229 ... 46219 ... 46199" }}{PARA 6 "" 1 "" {TEXT -1 71 " AGCD: w^4-10*w^2+1 = (w+21828)*(w+39568)*(w+24371)*(w+6631) mod \+ 46199" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 24371" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46199)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " AGCD: | w = 6631" }}{PARA 6 "" 1 "" {TEXT -1 32 " P GCD: Gcd in GF(46199)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mo d " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 " " 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 21828 " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46199)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 39568" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46199)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGC D: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 " " {TEXT -1 58 " NGCD: Prime 46187 ... 46183 ... 46181 ... 46171 ... 46 153" }}{PARA 6 "" 1 "" {TEXT -1 71 " AGCD: w^4-10*w^2+1 = (w+35035)*( w+4338)*(w+11118)*(w+41815) mod 46153" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 11118" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in \+ GF(46153)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 41815" }} {PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46153)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 35035" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46153)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " AG CD: | w = 4338" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(461 53)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGCD: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 48 " NGCD: Prime 4614 7 ... 46141 ... 46133 ... 46103" }}{PARA 6 "" 1 "" {TEXT -1 71 " AGCD : w^4-10*w^2+1 = (w+8043)*(w+35556)*(w+10547)*(w+38060) mod 46103" }} {PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 38060" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46103)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 10547" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46103)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 35556" }} {PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46103)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " AGCD: | w = 8043" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46103)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGC D: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 " " {TEXT -1 138 " NGCD: Prime 46099 ... 46093 ... 46091 ... 46073 ... 4 6061 ... 46051 ... 46049 ... 46027 ... 46021 ... 45989 ... 45979 ... 4 5971 ... 45959" }}{PARA 6 "" 1 "" {TEXT -1 70 " AGCD: w^4-10*w^2+1 = \+ (w+8496)*(w+40371)*(w+5588)*(w+37463) mod 45959" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 37463" }}{PARA 6 "" 1 "" {TEXT -1 32 " \+ PGCD: Gcd in GF(45959)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... m od " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " AGCD: | w = 5588 " }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45959)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 40371" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45959)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 19 " AG CD: | w = 8496" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(459 59)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGCD: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 58 " NGCD: Prime 4595 3 ... 45949 ... 45943 ... 45893 ... 45887" }}{PARA 6 "" 1 "" {TEXT -1 71 " AGCD: w^4-10*w^2+1 = (w+41007)*(w+4880)*(w+26921)*(w+18966) mod \+ 45887" }}{PARA 6 "" 1 "" {TEXT -1 19 " AGCD: | w = 4880" }}{PARA 6 " " 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45887)[x, y]" }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 41007" }}{PARA 6 "" 1 "" {TEXT -1 32 " \+ PGCD: Gcd in GF(45887)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... m od " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 1896 6" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45887)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | w = 26921" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45887)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 56 " AGC D: images done for w^4-10*w^2+1 - interpolating ..." }}{PARA 6 "" 1 " " {TEXT -1 21 "NGCD: Trial Divisions" }}{PARA 12 "" 1 "" {XPPMATH 20 " 6#-%$modG6$,2!-'f%\\laj\"\"\"%\"wG\".khv)R9e*$)F)\"\"#\"\"\"\",%3>HRg* $)F)\"\"$F.!-Sl=)p*e*&,*\".x^/_&3SF(F)!.`;%4*eP*F+!-\"o;')4*RF0\"-6b$RF0!-YZk'))3%F(F:F.F(F(%\"xGF(F(*$)FNF-F.\".C cpO!H\\-%-anglebracketG6#,(*$)F)\"\"%F.F(F+!#5F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "Q(" }{XPPEDIT 18 0 "sqrt(2),sqrt(3+sqrt(2));" "6$- %%sqrtG6#\"\"#-F$6#,&\"\"$\"\"\"-F$6#\"\"#F+" }{TEXT -1 6 ")[x,y]" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 357 "alpha := RootOf(x^2-2):\nbe ta := RootOf(x^2-3-alpha):\nd := 2:\nX := [alpha,beta,x,y]:\ng := alph a*x^(d+1)+beta*y^(d+1)+randpoly(X,degree=d,dense):\na := expand(randpo ly(X,degree=d,dense)*g):\nb := expand(randpoly(X,degree=d,dense)*g):\n X := [x,y,v,u]:\nA := convert(a,POLYNOMIAL,X,[u=alpha,v=beta]):\nB := \+ convert(b,POLYNOMIAL,X,[u=alpha,v=beta]):\nG := NGCD(A,B);\n" }} {PARA 6 "" 1 "" {TEXT -1 49 "NGCD: GCD in Q[v, u][x, y] mod <-2+u^2, - 3-u+v^2>" }}{PARA 6 "" 1 "" {TEXT -1 35 "NGCD: I will split -2+u^2, -3 -u+v^2" }}{PARA 6 "" 1 "" {TEXT -1 178 " NGCD: Prime 46327 ... 46309 . .. 46307 ... 46301 ... 46279 ... 46273 ... 46271 ... 46261 ... 46237 . .. 46229 ... 46219 ... 46199 ... 46187 ... 46183 ... 46181 ... 46171 . .. 46153" }}{PARA 6 "" 1 "" {TEXT -1 45 " AGCD: -2+u^2 = (u+7728)*(u+ 38425) mod 46153" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 38425 " }}{PARA 6 "" 1 "" {TEXT -1 48 " AGCD: 7725+v^2 = (v+34361)*(v+11792 ) mod 46153" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 11792" }} {PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46153)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 34361" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46153)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 52 " AGCD: images done for 7725+v^2 - interpolatin g ..." }}{PARA 6 "" 1 "" {TEXT -1 19 " AGCD: | u = 7728" }}{PARA 6 " " 1 "" {TEXT -1 49 " AGCD: -7731+v^2 = (v+19603)*(v+26550) mod 46153 " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 26550" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46153)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 1 9603" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46153)[x, y] " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 53 " AGCD: images done for -7731+v^2 - interpolating ..." }}{PARA 6 " " 1 "" {TEXT -1 50 " AGCD: images done for -2+u^2 - interpolating ... " }}{PARA 6 "" 1 "" {TEXT -1 368 " NGCD: Prime 46147 ... 46141 ... 461 33 ... 46103 ... 46099 ... 46093 ... 46091 ... 46073 ... 46061 ... 460 51 ... 46049 ... 46027 ... 46021 ... 45989 ... 45979 ... 45971 ... 459 59 ... 45953 ... 45949 ... 45943 ... 45893 ... 45887 ... 45869 ... 458 63 ... 45853 ... 45841 ... 45833 ... 45827 ... 45823 ... 45821 ... 458 17 ... 45779 ... 45767 ... 45763 ... 45757 ... 45751" }}{PARA 6 "" 1 " " {TEXT -1 45 " AGCD: -2+u^2 = (u+4456)*(u+41295) mod 45751" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 41295" }}{PARA 6 "" 1 "" {TEXT -1 48 " AGCD: 4453+v^2 = (v+19409)*(v+26342) mod 45751" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 26342" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45751)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 19409" }} {PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45751)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 52 " AGCD: images done for 4453+v^2 - interpolating ..." }}{PARA 6 " " 1 "" {TEXT -1 19 " AGCD: | u = 4456" }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: -4459+v^2 = (v+28921)*(v+16830) mod 45751" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 16830" }}{PARA 6 "" 1 "" {TEXT -1 32 " \+ PGCD: Gcd in GF(45751)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " .. . mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 28921" }} {PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(45751)[x, y]" }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 53 " AGCD: images done for -4459+v^2 - interpolating ..." }}{PARA 6 " " 1 "" {TEXT -1 50 " AGCD: images done for -2+u^2 - interpolating ... " }}{PARA 6 "" 1 "" {TEXT -1 21 "NGCD: Trial Divisions" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"GG-%$modG6$,4\"#w\"\"\"%\"uG\"\"'*&,&\"#YF*F+ \"#\\F*%\"vGF*F**&,(\"#QF*F+!#&)*&F+F*F1\"\"\"\"#&)F*%\"yGF*F**&F+F7)F 9\"\"#F7!#***(F+F7F1F7)F9\"\"$F7F**&,*!$o\"F*F+\"#sF6!#`*&F+F7F9F7\"#< F*%\"xGF*F**&F+F7)FHF " 0 "" {MPLTEXT 1 0 375 "alpha := RootOf(x^4-2):\nbeta := RootOf(x^4- 3):\nd := 3:\nX := [alpha,beta,x,y]:\ng := alpha*x^(d+1)+beta*y^(d+1)+ randpoly(X,degree=d,dense):\na := expand(randpoly(X,degree=d,dense)*g) :\nb := expand(randpoly(X,degree=d,dense)*g):\nX := [x,y,v,u]:\nA := c onvert(a,POLYNOMIAL,X,[u=alpha,v=beta]):\nB := convert(b,POLYNOMIAL,X, [u=alpha,v=beta]):\nst := time(): G := NGCD(A,B); time()-st;\n" }} {PARA 6 "" 1 "" {TEXT -1 45 "NGCD: GCD in Q[v, u][x, y] mod " }}{PARA 6 "" 1 "" {TEXT -1 24 "NGCD: I will split u^4-2" }} {PARA 6 "" 1 "" {TEXT -1 25 "NGCD: I won't split v^4-3" }}{PARA 6 "" 1 "" {TEXT -1 68 " NGCD: Prime 46327 ... 46309 ... 46307 ... 46301 ... 46279 ... 46273" }}{PARA 6 "" 1 "" {TEXT -1 64 " AGCD: u^4-2 = (u+43 534)*(u+2739)*(u+34044)*(u+12229) mod 46273" }}{PARA 6 "" 1 "" {TEXT -1 19 " AGCD: | u = 2739" }}{PARA 6 "" 1 "" {TEXT -1 65 " AGCD: v^4 -3 = (v+28875)*(v+26624)*(v+17398)*(v+19649) mod 46273" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 17398" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 19649" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 28875" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 26624" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: images done for v^4-3 - inte rpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 43534" }} {PARA 6 "" 1 "" {TEXT -1 65 " AGCD: v^4-3 = (v+28875)*(v+26624)*(v+17 398)*(v+19649) mod 46273" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v \+ = 17398" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, \+ y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD : | v = 19649" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(4627 3)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD : | v = 28875" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(4627 3)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD : | v = 26624" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(4627 3)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: images done for v^4-3 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 12229" }}{PARA 6 "" 1 "" {TEXT -1 65 " AGCD: v^ 4-3 = (v+28875)*(v+26624)*(v+17398)*(v+19649) mod 46273" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 17398" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 19649" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 28875" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v = 26624" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: images done for v^4-3 - inte rpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 34044" }} {PARA 6 "" 1 "" {TEXT -1 65 " AGCD: v^4-3 = (v+28875)*(v+26624)*(v+17 398)*(v+19649) mod 46273" }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | v \+ = 17398" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(46273)[x, \+ y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD : | v = 19649" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(4627 3)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD : | v = 28875" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(4627 3)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD : | v = 26624" }}{PARA 6 "" 1 "" {TEXT -1 32 " PGCD: Gcd in GF(4627 3)[x, y]" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: images done for v^4-3 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: images done for u^4-2 - interpolating ..." }}{PARA 6 " " 1 "" {TEXT -1 198 " NGCD: Prime 46271 ... 46261 ... 46237 ... 46229 \+ ... 46219 ... 46199 ... 46187 ... 46183 ... 46181 ... 46171 ... 46153 \+ ... 46147 ... 46141 ... 46133 ... 46103 ... 46099 ... 46093 ... 46091 \+ ... 46073" }}{PARA 6 "" 1 "" {TEXT -1 64 " AGCD: u^4-2 = (u+7167)*(u+ 38906)*(u+15338)*(u+30735) mod 46073" }}{PARA 6 "" 1 "" {TEXT -1 20 " \+ AGCD: | u = 38906" }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in G F(46073)[v][x, y] where v^4-3" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... \+ mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 19 " AGCD: | u = 7167" }}{PARA 6 "" 1 "" {TEXT -1 47 " \+ PGCD: GCD in GF(46073)[v][x, y] where v^4-3" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod < y-1>" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " \+ ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }} {PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 30735" }}{PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(46073)[v][x, y] where v^4-3" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 " " {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " . .. mod " }}{PARA 6 "" 1 "" {TEXT -1 20 " AGCD: | u = 15338" }} {PARA 6 "" 1 "" {TEXT -1 47 " PGCD: GCD in GF(46073)[v][x, y] where v^4-3" }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 " " 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " } }{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 17 " ... mod " }}{PARA 6 "" 1 "" {TEXT -1 49 " AGCD: images done for u^4-2 - interpolating ..." }}{PARA 6 "" 1 "" {TEXT -1 21 "NGCD: Trial Divisions" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"GG -%$modG6$,@\"$)>\"\"\"%\"uG\"#s*$)F+\"\"#\"\"\"!#o*$)F+\"\"$F0!#d*&,( \"$5\"F*F+\"$?\"F2\"#KF*%\"vGF*F**&,&\"$Y\"F*F2!#:F*)F;F/F0F**&F3F0)F; F4F0!#R*&,,\"$/\"F*F+\"#'*F2!#`*&,&\"#)*F*F2\"#=F*F;F0F**&F3F0F@F0!#wF *%\"yGF*F**&,(!$I\"F*F2FN*&F3F0F;F0\"#OF*)FOF/F0F**&F3F0)FOF4F0\"#D*(F 3F0F;F0)FO\"\"%F0F**&,0\"#7F*F+F)F2!#(**&,&!#!)F*F2\"#FF*F;F0F*FM\"#\\ *&,(\"$I\"F*F2F\\oFS!#)*F*FOF0F**&F3F0FUF0\"#jF*%\"xGF*F**&,(\"#[F*F2 \"\")FS\"#WF*)FeoF/F0F**&F3F0)FeoF4F0\"\"&*$)FeoFenF0F/-%-anglebracket G6$,&*$)F;FenF0F*!\"$F*,&*$)F+FenF0F*!\"#F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&Dk\"!\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 717 "A s in the finite field case, there are good algorithms for the simple c ases, including the case of a single field extension. Maple will comp ute the first GCD using the heuristic or the modular algorithm, and th e second by converting to a single field extension. But for the third , the subresultant algorithm is used which blows up again. Again, in \+ comparing these timings, note that the modular algorithm timing above \+ will speed up by a factor of 10 to 100 once there is kernel support. \+ The degree of this problem is not too big, 7 and 7, so that the subres ultant algorithm terminates and we can get a comparison. Increase tha t to 10 and 10 and the subresultant algorithm will not terminate in a \+ reasonable time." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "infolev el[Gcd] := 3:\nst := time(): gcd(a,b); time()-st;" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/Gcd/doit: entering Gcd at time 547.483" }} {PARA 6 "" 1 "" {TEXT -1 49 "mod/Gcd/hensel: lifted y altered = \+ false " }}{PARA 6 "" 1 "" {TEXT -1 51 "mod/Gcd/hensel: lifted y^ 2 altered = false " }}{PARA 6 "" 1 "" {TEXT -1 209 "mod/Gcd/hensel : lifted y^3 altered = true U = [x^4+724460907324*x^3+94494008 1242*x^2+205087923665*x+726171227223+705791969366*x*y+490322095586*y+7 08173067395*x*y^2+971257821368*y^2+685083246543*y^3, 1]" }}{PARA 6 "" 1 "" {TEXT -1 34 "evala/Gcd/doit: heuristic failed" }}{PARA 6 "" 1 " " {TEXT -1 62 "evala/Gcd/doit: entering multivariate case at time \+ 548.126" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/Gcd/doit: entering Gcd at time 583.035" }}{PARA 6 "" 1 "" {TEXT -1 34 "evala/Gcd/doit: h euristic failed" }}{PARA 6 "" 1 "" {TEXT -1 62 "evala/Gcd/doit: ente ring number field case at time 583.480" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/Gcd/doit: entering Gcd at time 583.799" }}{PARA 6 "" 1 " " {TEXT -1 47 "evala/Gcd/doit: exiting Gcd at time 583.799" }} {PARA 6 "" 1 "" {TEXT -1 61 "evala/Gcd/doit: exiting number field ca se at time 584.544" }}{PARA 6 "" 1 "" {TEXT -1 47 "evala/Gcd/doit: \+ exiting Gcd at time 585.154" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/G cd/doit: entering Gcd at time 585.156" }}{PARA 6 "" 1 "" {TEXT -1 34 "evala/Gcd/doit: heuristic failed" }}{PARA 6 "" 1 "" {TEXT -1 47 "evala/Gcd/doit: exiting Gcd at time 585.493" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/Gcd/doit: entering Gcd at time 585.494" }} {PARA 6 "" 1 "" {TEXT -1 34 "evala/Gcd/doit: heuristic failed" }} {PARA 6 "" 1 "" {TEXT -1 62 "evala/Gcd/doit: entering number field c ase at time 585.649" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/Gcd/doit: \+ entering Gcd at time 585.971" }}{PARA 6 "" 1 "" {TEXT -1 47 "evala /Gcd/doit: exiting Gcd at time 585.972" }}{PARA 6 "" 1 "" {TEXT -1 61 "evala/Gcd/doit: exiting number field case at time 587.033" }}{PARA 6 "" 1 "" {TEXT -1 47 "evala/Gcd/doit: exiting Gcd at time \+ 587.054" }}{PARA 6 "" 1 "" {TEXT -1 48 "evala/Gcd/doit: entering Gc d at time 587.055" }}{PARA 6 "" 1 "" {TEXT -1 34 "evala/Gcd/doit: \+ heuristic failed" }}{PARA 6 "" 1 "" {TEXT -1 62 "evala/Gcd/doit: ent ering number field case at time 587.449" }}{PARA 6 "" 1 "" {TEXT -1 61 "evala/Gcd/doit: exiting number field case at time 589.789" }} {PARA 6 "" 1 "" {TEXT -1 47 "evala/Gcd/doit: exiting Gcd at time 5 89.809" }}{PARA 6 "" 1 "" {TEXT -1 56 "evala/Gcd/doit: exiting multi variate at time 590.893" }}{PARA 6 "" 1 "" {TEXT -1 47 "evala/Gcd/do it: exiting Gcd at time 591.570" }}{PARA 12 "" 1 "" {XPPMATH 20 "6 #,do*$)%\"xG\"\"%\"\"\"\"\"\"*$)F&\"\"#F(\"#C*&F&F)%\"yGF)\"#l*$)F/F,F (!#l*&F&F()-%'RootOfG6#,&*$)%#_ZGF'F(F)!\"#F)\"\"$F(#!#(*F,-F76#,&F:F) !\"$F)\"#bF6\"#O*&F6F)FAF)\"#g*&F6F(F&F(\"#***&F6F(F/F(\"#[*$)FAF,F(\" #t*&FAF(F&F(!#S*&FAF(F/F(\"#\\*$F5F(#!#dF,*$)F6F,F(!#M*&F5F()FAF>F(#!# RF,*&F5F(F/F(#!#`F,*&F5F()F/F>F(#\"#DF,*&F5F(F2F(!#Q*(F5F(F/F(FNF(F`o* (F5F(F2F(FAF(\"#=*&F5F(FAF(\"#;*&F5F(FNF(#!#:F,*(F5F(FAF(F/F(\"\"**(F5 F(FAF()F/F'F(#F)F,**F&F(F5F(FAF(F/F(!#\\*(F&F(F5F(F2F(#\"#jF,*(F&F(F5F (FAF(#\"#FF,*(F&F(F5F(FNF(#FSF,*(F&F(F5F(F/F(FQ*&)F&F>F(F5F(#\"\"&F,*& F+F(F5F(F'*(F+F(F5F(FAF(\"#AFJF)F&\"\"'F/\"#_" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&b[%!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "2" 0 }{VIEWOPTS 1 1 0 3 2 1804 }