{VERSION 7 1 "Linux" "7.1" } {USTYLETAB {PSTYLE "Heading 4" -1 20 1 {CSTYLE "" -1 -1 "MS Serif" 1 12 0 0 0 1 1 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 5" -1 200 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 3 3 2 144 2 0 2 2 -1 1 }{PSTYLE "Ordered List 1 " -1 201 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 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Text Output" -1 2 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 "Bullet Item" -1 15 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 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Left Justified Maple Output" -1 12 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Help" -1 10 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Author" -1 19 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 8 8 2 0 2 0 2 2 -1 1 }{PSTYLE "Diagnostic" -1 9 1 {CSTYLE "" -1 -1 "Courier" 1 12 40 120 40 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 "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "MS Serif" 1 16 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 2 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 3" -1 202 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 3 3 2 72 2 0 2 2 -1 1 }{PSTYLE "Maple Plot" -1 13 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 "Norm al" -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 "Dash Item" -1 16 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 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "MS Serif" 1 14 0 0 0 1 1 1 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Orde red List 4" -1 203 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 3 3 2 108 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 "Line Printed Output" -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 "List Item" -1 14 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 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Wa rning" -1 7 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 "Fixed Width" -1 17 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "He ading 1" -1 3 1 {CSTYLE "" -1 -1 "MS Serif" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 2" -1 204 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 3 3 2 36 2 0 2 2 -1 1 } {CSTYLE "Equation Label" -1 200 "Courier" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Text" -1 201 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Page Number" -1 33 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {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 "Dictionary Hyperlink" -1 45 "MS Serif" 1 12 147 0 15 1 2 2 1 2 2 2 0 0 0 1 }{CSTYLE "2D Input" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 202 "Courier" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "MS Serif" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }{PSTYLE "" -1 205 1 {CSTYLE "" -1 -1 "Times" 1 12 255 0 0 1 2 1 2 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 203 66 "Sz\303\241m\303\255t\303 \263g\303\251pes sz\303\241melm\303\251let" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 18 "J\303\241rai Antal" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 68 "Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\2 41lnak" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "1. A pr\303\255mek el oszl\303\241sa, szit\303\241l\303\241s" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 63 "2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263 dszerek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 64 "3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\26 3dszerek" }}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 18 "4. Lucas-sorozatok" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 23 "5. Alkalmaz\30 3\241sok " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "6. Sz\303\241mok \303\251s polinomok" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 45 "7. Gyors Four ier-transzform\303\241ci\303\263" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT 205 38 "8. Elliptikus f\303\274ggv\303\2 51nyek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251 ken" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 65 "10. Faktoriz\303\241l\303\241s elliptikus g\303\274rb\303\251 kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 55 "11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 37 "12. Polinomfaktoriz\303\241l \303\241s" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "restart; with(PolynomialTools);" }}{PARA 11 "" 1 "" {XPPMATH 20 "73I0CoefficientListG6\"I2CoefficientVectorGF$I-GcdFreeBas isGF$I?GreatestFactorialFactorizationGF$I(HurwitzGF$I1IsSelfReciprocal GF$I2MinimalPolynomialGF$I0PDEToPolynomialGF$I0PolynomialToPDEGF$I0Shi ftEquivalentGF$I7ShiftlessDecompositionGF$I(ShortenGF$I(ShorterGF$I%So rtGF$I&SplitGF$I'SplitsGF$I*TranslateGF$" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 6 "12.1. " }{TEXT 206 57 "Polinomfaktoriz\303\241l\303\241s \+ modulo egy pr\303\255m." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 17 "12.2 . Visszavezet" }{TEXT 206 8 "\303\251" }{TEXT 206 3 "s n" }{TEXT 206 8 "\303\251" }{TEXT 206 19 "gyzetmentes esetre." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "SquareFree: =proc(a,x,p) local i,out,b,c,y,z,w;\n" }{MPLTEXT 1 0 36 "i:=1; out:=[] ; b:=diff(a,x) mod p;\n" }{MPLTEXT 1 0 67 "if b=0 then error \"zero de rivative; substitute x^p with p\"; fi;\n" }{MPLTEXT 1 0 41 "c:=Gcd(a,b ) mod p; w:=Quo(a,c,x) mod p;\n" }{MPLTEXT 1 0 23 "while degree(c)<>0 \+ do\n" }{MPLTEXT 1 0 22 " y:=Gcd(w,c) mod p;\n" }{MPLTEXT 1 0 24 " z: =Quo(w,y,x) mod p;\n" }{MPLTEXT 1 0 21 " out:=[op(out),z];\n" } {MPLTEXT 1 0 11 " i:=i+1;\n" }{MPLTEXT 1 0 30 " w:=y; c:=Quo(c,y,x) \+ mod p;\n" }{MPLTEXT 1 0 28 "od; out:=[c,op(out),w]; end;" }}{PARA 11 " " 1 "" {XPPMATH 20 "f*6%I\"aG6\"I\"xGF%I\"pGF%6)I\"iGF%I$outGF%I\"bGF% I\"cGF%I\"yGF%I\"zGF%I\"wGF%F%F%C*>F)\"\"\">F*7\">F+-I$modGF%6$-I%diff G%*protectedG6$F$F&F'@$/F+\"\"!YQGzero~derivative;~substitute~x^p~with ~pF%>F,-F76$-I$GcdG6$F;I(_syslibGF%6$F$F+F'>F/-F76$-I$QuoGF%6%F$F,F&F' ?(F%F2F2F%0-I'degreeGF;6#F,F?C(>F--F76$-FF6$F/F,F'>F.-F76$-FN6%F/F-F&F '>F*7$-I#opGF;6#F*F.>F),&F)F2F2F2>F/F->F,-F76$-FN6%F,F-F&F'>F*7%F,F\\o F/F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "`mod`:=mods; x: ='x'; a:=x^15-1; debug(SquareFree); SquareFree(a,x,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%modsG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"xG6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&*$)I\"xG6\"\"#:\"\"\"F(F( !\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "I+SquareFreeG6\"" }}{PARA 9 "" 1 "" {TEXT 207 43 "\{--> enter SquareFree, args = x^15-1, x, 5" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " 7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 9 "" 1 "" {TEXT 207 85 "<-- ERROR in SquareFree (now at top level) = zero derivative; \+ substitute x^p with p\}" }}{PARA 8 "" 1 "" {TEXT 208 61 "Error, (in Sq uareFree) zero derivative; substitute x^p with p" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "SquareFree(a,x,11);" }}{PARA 9 "" 1 "" {TEXT 207 44 "\{--> enter SquareFree, args = x^15-1, x, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",$*&\"\"%\"\"\")I\"xG6\"\"#9F%F%" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&*$)I\"xG 6\"\"#:\"\"\"F(F(!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"\",&*$)I \"xG6\"\"#:F#F#F#!\"\"" }}{PARA 9 "" 1 "" {TEXT 207 54 "<-- exit Squar eFree (now at top level) = [1, x^15-1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"\",&*$)I\"xG6\"\"#:F#F#F#!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "SquareFree(x^3+3*x^2+3*x+1,x,11);" }}{PARA 9 "" 1 "" {TEXT 207 53 "\{--> enter SquareFree, args = x^3+3*x^2+3*x+1, x, 11" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"$\"\"\")I\"xG6\"\"\"#F%F %*&\"\"&F%F'F%!\"\"F$F%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"xG6\" \"\"#\"\"\"F(*&F'F(F%F(F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG 6\"\"\"\"F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6\"\"\"\"F%F%" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6\"\"\"\"F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I \"xG6\"\"\"\"F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6\"\"\"\"F%F %" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }} {PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6\"\"\"\"F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"\"F#F#,&I \"xG6\"F#F#F#" }}{PARA 9 "" 1 "" {TEXT 207 57 "<-- exit SquareFree (no w at top level) = [1, 1, 1, x+1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7& \"\"\"F#F#,&I\"xG6\"F#F#F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This procedure find the factorization of t he polynomial P of\n" }{MPLTEXT 1 0 67 "# the variable X modulo the pr ime number p in the form of product\n" }{MPLTEXT 1 0 59 "# P_i^i, wher e each P_i is square free. The list of P_i's\n" }{MPLTEXT 1 0 18 "# is given back.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 59 "squarefreefactor:=proc(P,X,p) local Pm,D,PP,L,LL,Q,R,i,j;\n" } {MPLTEXT 1 0 14 "Pm:=P mod p;\n" }{MPLTEXT 1 0 41 "if degree(Pm)<=1 th en RETURN([Pm]); fi;\n" }{MPLTEXT 1 0 23 "PP:=diff(Pm,X) mod p;\n" } {MPLTEXT 1 0 14 "if PP=0 then\n" }{MPLTEXT 1 0 73 " for i from 0 whil e p*i<=degree(Pm) do PP:=PP+coeff(Pm,X,i*p)*X^i; od;\n" }{MPLTEXT 1 0 40 " LL:=squarefreefactor(PP,X,p); L:=[];\n" }{MPLTEXT 1 0 57 " for \+ i to nops(LL) do L:=[op(L),0$j=1..p-1,LL[i]]; od;\n" }{MPLTEXT 1 0 14 " RETURN(L);\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 60 "D:=Gcd(Pm,P P) mod p; if degree(D)=0 then RETURN([Pm]); fi;\n" }{MPLTEXT 1 0 67 "Q :=Quo(Pm,D,X) mod p; PP:=Gcd(Q,D) mod p; Divide(Q,PP,'R') mod p;\n" } {MPLTEXT 1 0 34 "[R,op(squarefreefactor(D,X,p))];\n" }{MPLTEXT 1 0 4 " end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"PG6\"I\"XGF%I\"pGF%6+I#Pm GF%I\"DGF%I#PPGF%I\"LGF%I#LLGF%I\"QGF%I\"RGF%I\"iGF%I\"jGF%F%F%C,>F)-I $modGF%6$F$F'@$1-I'degreeG%*protectedG6#F)\"\"\"-I'RETURNGF;6#7#F)>F+- F56$-I%diffGF;6$F)F&F'@$/F+\"\"!C'?(F0FJF=F%1*&F'F=F0F=F9>F+,&F+F=*&-I &coeffGF;6%F)F&FNF=)F&F0F=F=>F--I1squarefreefactorGF%6%F+F&F'>F,7\"?(F 0F=F=-I%nopsGF;6#F-I%trueGF;>F,7%-I#opGF;6#F,-I\"$GF;6$FJ/F1;F=,&F'F=F =!\"\"&F-6#F0-F?F_o>F*-F56$-I$GcdGF%6$F)F+F'@$/-F:6#F*FJF>>F.-F56$-I$Q uoGF%6%F)F*F&F'>F+-F56$-F^p6$F.F*F'-F56$-I'DivideGF%6%F.F+.F/F'7$F/-F^ o6#-FX6%F*F&F'F%F%F%" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "12.3. V " }{TEXT 206 8 "\303\251" }{TEXT 206 11 "ges testek." }}{PARA 0 "" 0 " " {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "n:=8; Rij ndaelPoly:=Nextprime(Z^n,Z) mod 2; alpha:=Z;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,*$)I\"ZG6\"\"\") \"\"\"F(*$)F%\"\"%F(F(*$)F%\"\"$F(F(F%F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"ZG6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "x: =234; xx:=convert(x,base,2); xxx:=add(xx[i]*Z^(i-1),i=1..nops(xx));\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$M#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"!\"\"\"F#F$F#F$F$F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,I\"ZG6 \"\"\"\"*$)F#\"\"$F%F%*$)F#\"\"&F%F%*$)F#\"\"'F%F%*$)F#\"\"(F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "y:=111; yy:=convert(y,base,2 ); yyy:=add(yy[i]*Z^(i-1),i=1..nops(yy));" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7)\"\"\"F#F#F#\" \"!F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",.\"\"\"F#I\"ZG6\"F#*$)F$\"\" #F#F#*$)F$\"\"$F#F#*$)F$\"\"&F#F#*$)F$\"\"'F#F#" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 68 "zzz:=modpol(xxx+yyy,RijndaelPoly,Z,2); zz:=Coe fficientList(zzz,Z);\n" }{MPLTEXT 1 0 36 "z:=add(zz[i]*2^(i-1),i=1..no ps(zz));" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"ZG6\"\"\"(\"\"\"F(F( F(*$)F%\"\"#F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"\"\"\"!F#F$F$F $F$F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$L\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "zzz:=modpol(xxx*yyy,RijndaelPoly,Z,2); zz:=Coeff icientList(zzz,Z);\n" }{MPLTEXT 1 0 38 "z:=add(zz[i]*2^(i-1),i=1..nops (zz));\n" }}{PARA 11 "" 1 "" {XPPMATH 20 ",.*$)I\"ZG6\"\"\"'\"\"\"F(*$ )F%\"\"&F(F(*$)F%\"\"%F(F(*$)F%\"\"$F(F(*$)F%\"\"#F(F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7)\"\"\"\"\"!F#F#F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$D\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "zzz: =modpol(1/xxx,RijndaelPoly,Z,2); zz:=CoefficientList(zzz,Z);\n" } {MPLTEXT 1 0 36 "z:=add(zz[i]*2^(i-1),i=1..nops(zz));" }}{PARA 11 "" 1 "" {XPPMATH 20 ",.*$)I\"ZG6\"\"\"(\"\"\"F(*$)F%\"\"'F(F(*$)F%\"\"%F(F (*$)F%\"\"#F(F(F%F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7*\"\"\"F#F# \"\"!F#F$F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$:#" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "12.4. Fak" }{TEXT 206 33 "toriz\303\241l \303\241s k\303\274" }{TEXT 206 1 "l" }{TEXT 206 8 "\303\266" }{TEXT 206 2 "nb" }{TEXT 206 8 "\303\266" }{TEXT 206 1 "z" }{TEXT 206 8 "\305 \221" }{TEXT 206 4 " fok" }{TEXT 206 8 "\303\272" }{TEXT 206 12 " fakt orokra." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "PartialFactorDD:=proc(a,x,p) local aa,L,aaa,w,i;\n" } {MPLTEXT 1 0 27 "i:=1; w:=x; aa:=a; L:=[];\n" }{MPLTEXT 1 0 26 "while \+ i<=degree(aa)/2 do\n" }{MPLTEXT 1 0 27 " w:=Rem(w^p,aa,x) mod p;\n" } {MPLTEXT 1 0 27 " aaa:=Gcd(aa,w-x) mod p;\n" }{MPLTEXT 1 0 19 " L:=[ op(L),aaa];\n" }{MPLTEXT 1 0 18 " if aaa<>1 then\n" }{MPLTEXT 1 0 30 " aa:=Quo(aa,aaa,x) mod p:\n" }{MPLTEXT 1 0 27 " w:=Rem(w,aa,x) \+ mod p;\n" }{MPLTEXT 1 0 15 " fi; i:=i+1;\n" }{MPLTEXT 1 0 23 "od; L:= [op(L),aa]; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"aG6\"I\"xGF%I \"pGF%6'I#aaGF%I\"LGF%I$aaaGF%I\"wGF%I\"iGF%F%F%C(>F-\"\"\">F,F&>F)F$> F*7\"?(F%F0F0F%1F-,$*&#F0\"\"#F0-I'degreeG%*protectedG6#F)F0F0C'>F,-I$ modGF%6$-I$RemG6$F=I(_syslibGF%6%)F,F'F)F&F'>F+-FB6$-I$GcdGFF6$F),&F,F 0F&!\"\"F'>F*7$-I#opGF=6#F*F+@$0F+F0C$>F)-FB6$-I$QuoGFF6%F)F+F&F'>F,-F B6$-FE6%F,F)F&F'>F-,&F-F0F0F0>F*7$FTF)F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "`mod`:=mods; x:='x'; a:=x^15-1; debug(PartialFact orDD); PartialFactorDD(a,x,11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%mod sG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"xG6\"" }}{PARA 11 " " 1 "" {XPPMATH 20 ",&*$)I\"xG6\"\"#:\"\"\"F(F(!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "I0PartialFactorDDG6\"" }}{PARA 9 "" 1 "" {TEXT 207 49 "\{--> enter PartialFactorDD, args = x^15-1, x, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"xG6\"" }} {PARA 11 "" 1 "" {XPPMATH 20 ",&*$)I\"xG6\"\"#:\"\"\"F(F(!\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*$) I\"xG6\"\"#6\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&*$)I\"xG6\"\"\"& \"\"\"F(F(!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#,&*$)I\"xG6\"\"\"& \"\"\"F)F)!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"xG6\"\"#5\"\" \"F(*$)F%\"\"&F(F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&*$)I\"xG6\" \"\"'\"\"\"!\"\"F%F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I\"xG6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$ )I\"xG6\"\"#5\"\"\"F(*$)F%\"\"&F(F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,&*$)I\"xG6\"\"\"&\"\"\"F)F)!\"\",(*$)F&\"#5F)F)F$F)F)F)" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%,&*$)I\"xG6\"\"\"&\"\"\"F)F)!\"\",(*$)F&\"#5F)F)F$F)F)F )F)" }}{PARA 9 "" 1 "" {TEXT 207 70 "<-- exit PartialFactorDD (now at \+ top level) = [x^5-1, x^10+x^5+1, 1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%,&*$)I\"xG6\"\"\"&\"\"\"F)F)!\"\",(*$)F&\"#5F)F)F$F)F)F)F)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 60 "# This procedure find the factorization of the square-free\n" }{MPLTEXT 1 0 63 "# polynomial P of the variable X modulo the prime number p in\n" } {MPLTEXT 1 0 65 "# the form of product P_i, i=0.. where each P_i has o nly degree\n" }{MPLTEXT 1 0 59 "# i irreducible factors. The list of P _i's is given back.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 49 "degreefactor:=proc(P,X,p) local V,W,D,PP,L,j,d;\n" } {MPLTEXT 1 0 50 "V:=P mod p; if degree(V)<1 then RETURN([V]); fi;\n" } {MPLTEXT 1 0 15 "L:=[1]; W:=X;\n" }{MPLTEXT 1 0 31 "for d while 2*d<=d egree(V) do\n" }{MPLTEXT 1 0 50 " W:=Powmod(W,p,V,X) mod p; D:=Gcd(W- X,V) mod p;\n" }{MPLTEXT 1 0 41 " if D<>1 then V:=Quo(V,D,X) mod p; f i;\n" }{MPLTEXT 1 0 38 " L:=[op(L),D]; W:=Rem(W,V,X) mod p;\n" } {MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 44 "if degree(V)=d then RETURN([o p(L),V]); fi;\n" }{MPLTEXT 1 0 56 "if degree(V)>d then L:=[op(L),1$j=d ..degree(V),V]; fi;\n" }{MPLTEXT 1 0 7 "L; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"PG6\"I\"XGF%I\"pGF%6)I\"VGF%I\"WGF%I\"DGF%I#PPGF%I \"LGF%I\"jGF%I\"dGF%F%F%C*>F)-I$modGF%6$F$F'@$2-I'degreeG%*protectedG6 #F)\"\"\"-I'RETURNGF96#7#F)>F-7#F;>F*F&?(F/F;F;F%1,$*&\"\"#F;F/F;F;F7C '>F*-F36$-I'PowmodGF%6&F*F'F)F&F'>F+-F36$-I$GcdGF%6$,&F*F;F&!\"\"F)F'@ $0F+F;>F)-F36$-I$QuoGF%6%F)F+F&F'>F-7$-I#opGF96#F-F+>F*-F36$-I$RemGF%6 %F*F)F&F'@$/F7F/-F=6#7$F[oF)@$2F/F7>F-7%F[o-I\"$GF96$F;/F.;F/F7F)F-F%F %F%" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 9 "12.5. Has" }{TEXT 206 8 "\303\255" }{TEXT 206 1 "t" }{TEXT 206 8 "\303\241" }{TEXT 206 2 "s." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "PartialFactorSplit:=proc(a,x,d,p) local t,i;\n" }{MPLTEXT 1 0 69 "t:=rand(); t:=convert(t,base,p); t:=add(t[i]*x^(i-1),i=1..nops(t)) ;\n" }{MPLTEXT 1 0 55 "t:=modpol(t,a,x,p); t:=modpol(t^((p^d-1)/2)-1,a ,x,p);\n" }{MPLTEXT 1 0 45 "t:=Gcd(t,a) mod p; [t,Quo(a,t,x) mod p]; e nd;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"xGF%I\"dGF%I\"pGF% 6$I\"tGF%I\"iGF%F%F%C)>F*-I%randG6$%*protectedGI(_syslibGF%F%>F*-I(con vertGF16%F*I%baseGF%F(>F*-I$addGF16$*&&F*6#F+\"\"\")F&,&F+F?F?!\"\"F?/ F+;F?-I%nopsGF16#F*>F*-I'modpolGF06&F*F$F&F(>F*-FJ6&,&)F*,&*&#F?\"\"#F ?)F(F'F?F?FSFBF?F?FBF$F&F(>F*-I$modGF%6$-I$GcdGF06$F*F$F(7$F*-FX6$-I$Q uoGF06%F$F*F&F(F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "de bug(PartialFactorSplit); PartialFactorSplit(x^5-1,x,1,11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I3PartialFactorSplitG6\"" }}{PARA 9 "" 1 "" {TEXT 207 54 "\{--> enter PartialFactorSplit, args = x^5-1, x, 1, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-]uI3kQ" }}{PARA 11 "" 1 "" {XPPMATH 20 "7.\"\"!\"\"%\"\"'\"\"$F%F$\"\"*F%F'F'F&\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",8*&\"\"%\"\"\"I\"xG6\"F%F%*&\"\"'F%)F&\"\"#F%F% *&\"\"$F%)F&F-F%F%*&F)F%)F&F$F%F%*&F$F%)F&\"\"&F%F%*&\"\"*F%)F&F)F%F%* &F)F%)F&\"\"(F%F%*&F5F%)F&\"\")F%F%*&F5F%)F&F5F%F%*&F-F%)F&\"#5F%F%*$) F&\"#6F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,*&\"\"$\"\"\"I\"xG6\"F%F %*$)F&\"\"#F%F%*$)F&F$F%F%*&\"\"%F%)F&F.F%F%F.!\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 ",,*&\"\"#\"\"\")I\"xG6\"\"\"%F%!\"\"*&\"\"$F%)F'F,F%F** &F,F%)F'F$F%F%*&F,F%F'F%F%\"\"&F*" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(* $)I\"xG6\"\"\"#\"\"\"F(*&F'F(F%F(F(F'!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6\"\"\"#\"\"\"F)*&F(F)F&F)F)F(!\"\",**$)F&\" \"$F)F)*&F(F)F%F)F+*&\"\"&F)F&F)F+F2F+" }}{PARA 9 "" 1 "" {TEXT 207 79 "<-- exit PartialFactorSplit (now at top level) = [x^2+2*x-2, x^3-2 *x^2-5*x-5]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6\"\"\"#\" \"\"F)*&F(F)F&F)F)F(!\"\",**$)F&\"\"$F)F)*&F(F)F%F)F+*&\"\"&F)F&F)F+F2 F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "expand((x^2+2*x-2)*(x ^3-2*x^2-5*x-5)) mod 11;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&*$)I\"xG6 \"\"\"&\"\"\"F(F(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "P artialFactorSplit(x^2+2*x-2,x,1,11);\n" }{MPLTEXT 1 0 43 "PartialFacto rSplit(x^3-2*x^2-5*x-5,x,1,11);" }}{PARA 9 "" 1 "" {TEXT 207 58 "\{--> enter PartialFactorSplit, args = x^2+2*x-2, x, 1, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-l#*=2Yp" }}{PARA 11 "" 1 "" {XPPMATH 20 "7.\"\"!\" \"#\"\"\"\"\"(F%F&\"\"$\"\"%\"\"'\"\")F(F$" }}{PARA 11 "" 1 "" {XPPMATH 20 ",8*&\"\"#\"\"\"I\"xG6\"F%F%*$)F&F$F%F%*&\"\"(F%)F&\"\"$F% F%*$)F&\"\"%F%F%*&F+F%)F&\"\"&F%F%*&F-F%)F&\"\"'F%F%*&F0F%)F&F+F%F%*&F 6F%)F&\"\")F%F%*&F;F%)F&\"\"*F%F%*&F0F%)F&\"#5F%F%*&F$F%)F&\"#6F%F%" } }{PARA 11 "" 1 "" {XPPMATH 20 ",$*&\"\"$\"\"\"I\"xG6\"F%!\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"!\"\"*&\"\"$F#I\"xG6\"F#F#" }} {PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6\"\"\"\"\"\"%!\"\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "7$,&I\"xG6\"\"\"\"\"\"%!\"\",&F$F&\"\"&F(" }} {PARA 9 "" 1 "" {TEXT 207 61 "<-- exit PartialFactorSplit (now at top \+ level) = [x-4, x-5]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,&I\"xG6\"\" \"\"\"\"%!\"\",&F$F&\"\"&F(" }}{PARA 9 "" 1 "" {TEXT 207 64 "\{--> ent er PartialFactorSplit, args = x^3-2*x^2-5*x-5, x, 1, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-B+)H,t(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7.\"\"* \"#5\"\"\"\"\"(\"\"%F&\"\")F%F#F(F&\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",:\"\"*\"\"\"*&\"#5F$I\"xG6\"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$ *&F#F$)F'F7F$F$*&F7F$)F'F#F$F$*&F-F$)F'F&F$F$*&F+F$)F'\"#6F$F$" }} {PARA 11 "" 1 "" {XPPMATH 20 ",(\"\"$\"\"\"*&\"\"&F$I\"xG6\"F$F$*$)F' \"\"#F$!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*&\"\"#\"\"\")I\"xG6\" F$F%F%*&\"\"$F%F'F%F%F$!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&I\"xG6 \"\"\"\"\"\"#F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,&I\"xG6\"\"\"\"\" \"#F&,(*$)F$F'F&F&*&\"\"%F&F$F&!\"\"\"\"$F&" }}{PARA 9 "" 1 "" {TEXT 207 67 "<-- exit PartialFactorSplit (now at top level) = [x+2, x^2-4*x +3]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,&I\"xG6\"\"\"\"\"\"#F&,(*$)F $F'F&F&*&\"\"%F&F$F&!\"\"\"\"$F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "expand((x-4)*(x-5)) mod 11; expand((x+2)*(x^2-4*x+3)) mod 11; " }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"xG6\"\"\"#\"\"\"F(*&F'F(F%F( F(F'!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 ",**$)I\"xG6\"\"\"$\"\"\"F(* &\"\"#F()F%F*F(!\"\"*&\"\"&F(F%F(F,F.F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "PartialFactorSplit(x^2-4*x+3,x,1,11);" }}{PARA 9 "" 1 "" {TEXT 207 58 "\{--> enter PartialFactorSplit, args = x^2-4*x+3, x, 1, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-YHH;1t" }}{PARA 11 "" 1 "" {XPPMATH 20 "7.\"\"\"\"\"%\"\"(\"\"*\"\"$F&F#F$F&F#\"\"'\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 ",:\"\"\"F#*&\"\"%F#I\"xG6\"F#F#*&\"\"(F# )F&\"\"#F#F#*&\"\"*F#)F&\"\"$F#F#*&F/F#)F&F%F#F#*&F-F#)F&\"\"&F#F#*$)F &\"\"'F#F#*&F%F#)F&F)F#F#*&F-F#)F&\"\")F#F#*$)F&F-F#F#*&F7F#)F&\"#5F#F #*&F+F#)F&\"#6F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"%!\"\"*&\"\" &\"\"\"I\"xG6\"F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"xG6\"\"\"#\"\"\"F(*&\"\"%F(F%F(!\"\"\"\" $F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6\"\"\"#\"\"\"F)*&\" \"%F)F&F)!\"\"\"\"$F)F)" }}{PARA 9 "" 1 "" {TEXT 207 65 "<-- exit Part ialFactorSplit (now at top level) = [x^2-4*x+3, 1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6\"\"\"#\"\"\"F)*&\"\"%F)F&F)!\"\"\"\"$F)F )" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "PartialFactorSplit(x^2 -4*x+3,x,1,11);" }}{PARA 9 "" 1 "" {TEXT 207 58 "\{--> enter PartialFa ctorSplit, args = x^2-4*x+3, x, 1, 11" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"-dO02l5" }}{PARA 11 "" 1 "" {XPPMATH 20 "7-\"\"%\"#5\"\")\"\"!F&\" \"&F'\"\"*\"\"\"F)F#" }}{PARA 11 "" 1 "" {XPPMATH 20 ",4\"\"%\"\"\"*& \"#5F$I\"xG6\"F$F$*&\"\")F$)F'\"\"#F$F$*&\"\"&F$)F'F.F$F$*&F.F$)F'\"\" 'F$F$*&\"\"*F$)F'\"\"(F$F$*$)F'F*F$F$*$)F'F4F$F$*&F#F$)F'F&F$F$" }} {PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"\"!\"\"*&\"\"%F#I\"xG6\"F#F#" }} {PARA 11 "" 1 "" {XPPMATH 20 ",&\"\"$!\"\"I\"xG6\"\"\"\"" }}{PARA 11 " " 1 "" {XPPMATH 20 ",&\"\"$!\"\"I\"xG6\"\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,&\"\"$!\"\"I\"xG6\"\"\"\",&F&F(F(F%" }}{PARA 9 "" 1 "" {TEXT 207 62 "<-- exit PartialFactorSplit (now at top level) = [-3+x, x-1]\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,&\"\"$!\"\"I\"xG6\"\"\"\", &F&F(F(F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "expand((x-3)*( x-1)) mod 11; " }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"xG6\"\"\"#\"\" \"F(*&\"\"%F(F%F(!\"\"\"\"$F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "PartialFactorSplit(x^10+x^5+1,x,2,11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,0*$)I\"xG6\"\"\"'\"\"\"F)*&\"\"#F))F&\"\"&F)!\"\"*&\" \"$F))F&\"\"%F)F)*$)F&F0F)F)*&F+F))F&F+F)F.*&F2F)F&F)F)F-F),,*$F1F)F)* &F+F)F4F)F)*$F6F)F)*&F-F)F&F)F.F+F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "expand((x^6-2*x^5+3*x^4+x^3-2*x^2+4*x+5)*(x^4+2*x^3+x ^2-5*x-2)) mod 11;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",(*$)I\"xG6\"\"#5 \"\"\"F(*$)F%\"\"&F(F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "PartialFactorSplit(x^6-2*x^5+3*x^4+x^3-2*x^2+4*x+5,x,2,11);\n" } {MPLTEXT 1 0 47 "PartialFactorSplit(x^4+2*x^3+x^2-5*x-2,x,2,11);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6\"\"\"#\"\"\"F)*&\"\"$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 "7$,,*$)I\"xG6\"\"\"%\"\"\"F)*&\"\"#F))F& \"\"$F)F)*$)F&F+F)F)*&\"\"&F)F&F)!\"\"F+F2F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "expand((x^2+3*x-2)*(x^4-5*x^3-2*x^2-3*x+3)) mod 1 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",0*$)I\"xG6\"\"\"'\"\"\"F(*&\"\"#F ()F%\"\"&F(!\"\"*&\"\"$F()F%\"\"%F(F(*$)F%F/F(F(*&F*F()F%F*F(F-*&F1F(F %F(F(F,F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "PartialFactorS plit(x^4-5*x^3-2*x^2-3*x+3,x,2,11);\n" }{MPLTEXT 1 0 47 "PartialFactor Split(x^4+2*x^3+x^2-5*x-2,x,2,11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$ ,,*$)I\"xG6\"\"\"%\"\"\"F)*&\"\"&F))F&\"\"$F)!\"\"*&\"\"#F))F&F0F)F.*& F-F)F&F)F.F-F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6\"\"\"# \"\"\"F)*&\"\"%F)F&F)F)\"\"&F),(F$F)*&F(F)F&F)!\"\"F+F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "expand((x^2+4*x+5)*(x^2-2*x+4)) mod 11;" }}{PARA 11 "" 1 "" {XPPMATH 20 ",,*$)I\"xG6\"\"\"%\"\"\"F(*&\"\" #F()F%\"\"$F(F(*$)F%F*F(F(*&\"\"&F(F%F(!\"\"F*F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "PartialFactorSplit(x^4-5*x^3-2*x^2-3*x+3,x,2, 11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"\",,*$)I\"xG6\"\"\"%F#F#*& \"\"&F#)F'\"\"$F#!\"\"*&\"\"#F#)F'F0F#F.*&F-F#F'F#F.F-F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "PartialFactorSplit(x^4-5*x^3-2*x^2- 3*x+3,x,2,11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,,*$)I\"xG6\"\"\"%\" \"\"F)*&\"\"&F))F&\"\"$F)!\"\"*&\"\"#F))F&F0F)F.*&F-F)F&F)F.F-F)F)" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "PartialFactorSplit(x^4-5*x^ 3-2*x^2-3*x+3,x,2,11);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$,(*$)I\"xG6 \"\"\"#\"\"\"F)F&F)F)F),(F$F)*&\"\"&F)F&F)F)\"\"$F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "expand((x^2+x+1)*(x^2+5*x+3)) mod 11;" }} {PARA 11 "" 1 "" {XPPMATH 20 ",,*$)I\"xG6\"\"\"%\"\"\"F(*&\"\"&F()F%\" \"$F(!\"\"*&\"\"#F()F%F/F(F-*&F,F(F%F(F-F,F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 70 "# This procedure try to fac tor a product P of different irreducible \n" }{MPLTEXT 1 0 65 "# polyn omials of X modulo p each known to be the same degree d.\n" }{MPLTEXT 1 0 66 "# The parameter K is the limit for the random tries. The list \+ of\n" }{MPLTEXT 1 0 36 "# the found factors is given back.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 53 "fixdegreef actor:=proc(P,X,p,d,K) local T,D,Q,j,i,r;\n" }{MPLTEXT 1 0 51 "if degr ee(P)<=d then RETURN([P]); fi; r:=rand(p);\n" }{MPLTEXT 1 0 21 "for i \+ to K do T:=0;\n" }{MPLTEXT 1 0 51 " for j to 2*degree(P) do T:=expand (T*X+r()); od;\n" }{MPLTEXT 1 0 37 " T:=Powmod(T,(p^d-1)/2,P,X) mod p ;\n" }{MPLTEXT 1 0 24 " D:=Gcd(P,T+1) mod p;\n" }{MPLTEXT 1 0 47 " i f degree(D)>0 and degree(D)F 0-I%randGF%6#F'?(F/\"\"\"FAF)I%trueGF6C'>F+\"\"!?(F.FAFA,$*&\"\"#FAF4F AFAFB>F+-I'expandGF66#,&*&F+FAF&FAFA-F0F%FA>F+-I$modGF%6$-I'PowmodGF%6 &F+,&*&#FAFIFA)F'F(FAFAFZ!\"\"F$F&F'>F,-FS6$-I$GcdGF%6$F$,&F+FAFAFAF'@ $32FE-F56#F,2FaoF4C&>F--FS6$-I$QuoGF%6%F$F,F&F'>F--I0fixdegreefactorGF %6'F-F&F'F(F)>F,-F]p6'F,F&F'F(F)-F96#7$-I#opGF6Fbo-Ffp6#F-F;F%F%F%" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 62 "# Thi s procedure try to factor a polynomial P of X modulo p.\n" }{MPLTEXT 1 0 54 "# The parameter K is the limit for the random tries.\n" } {MPLTEXT 1 0 48 "# The list of the found factors is given back.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 64 "modfactor: =proc(P,X,p,K) local L,LL,LLL,LLLL,D,j,i,x,y,c,r,PP;\n" }{MPLTEXT 1 0 55 "L:=[]; c:=1; r:=rand(p); LL:=squarefreefactor(P,X,p);\n" }{MPLTEXT 1 0 22 "for i to nops(LL) do\n" }{MPLTEXT 1 0 14 " PP:=LL[i];\n" } {MPLTEXT 1 0 49 " if degree(PP)=0 then c:=c*PP mod p; next; fi;\n" } {MPLTEXT 1 0 30 " LLL:=degreefactor(PP,X,p);\n" }{MPLTEXT 1 0 25 " f or j to nops(LLL) do\n" }{MPLTEXT 1 0 17 " PP:=LLL[j];\n" }{MPLTEXT 1 0 51 " if degree(PP)=0 then c:=c*PP mod p; next; fi;\n" } {MPLTEXT 1 0 42 " LLLL:=fixdegreefactor(PP,X,p,j-1,K);\n" }{MPLTEXT 1 0 32 " D:=map(x->degree(x),LLLL);\n" }{MPLTEXT 1 0 45 " if ma x(op(D))>j-1 then RETURN(FAIL) fi;\n" }{MPLTEXT 1 0 41 " D:=map(pro c(x,y) [x,y] end,LLLL,i);\n" }{MPLTEXT 1 0 23 " L:=[op(L),op(D)];\n " }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 27 "od; [c,op(L)]; e nd;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"PG6\"I\"XGF%I\"pGF%I\"KGF% 6.I\"LGF%I#LLGF%I$LLLGF%I%LLLLGF%I\"DGF%I\"jGF%I\"iGF%I\"xGF%I\"yGF%I \"cGF%I\"rGF%I#PPGF%F%F%C(>F*7\">F3\"\"\">F4-I%randGF%6#F'>F+-I1square freefactorGF%6%F$F&F'?(F0F:F:-I%nopsG%*protectedG6#F+I%trueGFFC&>F5&F+ 6#F0@$/-I'degreeGFF6#F5\"\"!C$>F3-I$modGF%6$*&F3F:F5F:F'\\>F,-I-degree factorGF%6%F5F&F'?(F/F:F:-FE6#F,FHC)>F5&F,6#F/FM>F--I0fixdegreefactorG F%6'F5F&F',&F/F:F:!\"\"F(>F.-I$mapGFF6$f*6#F1F%6$I)operatorGF%I&arrowG F%F%-FPFjoF%F%F%F-@$2Fco-I$maxGFF6#-I#opGFF6#F.-I'RETURNGFF6#I%FAILGFF >F.-Fgo6%f*6$F1F2F%F%F%7$F1F2F%F%F%F-F0>F*7$-Fep6#F*Fdp7$F3FcqF%F%F%" }}}}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} }{SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "13. Az AKS-teszt" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "14. A szita m\303\263dszerek alapjai" }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 25 "15. Sz\303\241mtest szita" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "16. Vegyes probl" }{TEXT 205 8 " \303\251" }{TEXT 205 1 "m" }{TEXT 205 8 "\303\241" }{TEXT 205 1 "k" }} }{EXCHG {PARA 205 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {XPPEDIT 19 1 "" "%#%?G" }}}} {MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }