{VERSION 2 3 "IBM INTEL NT" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 14 0 0 0 0 0 1 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 0 }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 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 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 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 126 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 47 1 1 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 256 41 "Algorithmes de Factoris ation dans F_p[X]\n" }{TEXT 258 57 "Danthony Laure - DM de Calcul Form el - Pour le 16/11/2001" }}}{EXCHG {PARA 257 "" 0 "" {TEXT -1 0 "" }} {PARA 257 "" 0 "" {TEXT 257 122 "On code ici l'algorithme de factorisa tion dans F_p[X] d\351crit dans le DM pour p>2. On r\351alise la facto risation enti\350rement." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 21 "Fonc tion Separedegres" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 273 "Separe degres:= proc(F,p,X)\nlocal Fk,H,L,k,n,aux;\n\nk:=0;\nH:=F;\nn:=degree (F);\nL:=[];\n\n while((degree(H)>0) and (k%-SeparedegresG:6%%\"FG%\"pG% \"XG6(%#FkG%\"HG%\"LG%\"kG%\"nG%$auxG6\"F1C(>8'\"\"!>8%9$>8(-%'degreeG 6#F8>8&7\"?(F1\"\"\"FBF132F5-F<6#F72F4F:C'>F4,&F4FBFBFB>8)-%$modG6$-%' PowmodG6&9&)9%F4F7FSFU>8$-FN6$-%$GcdG6$F7,&FLFBFS!\"\"FU>F?7$-%#opG6#F ?FW>F7-FN6$-%$QuoG6%F7FWFSFU-%'RETURNGF]oF1F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "Factor((X^2+2*X+3)*(X^3+2*X+3)*(X+3)) mod 7;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#**,(*$%\"XG\"\"#\"\"\"F&\"\"'\"\"$F(F( ,(F%F(F&F'F*F(F(,&F&F(F(F(F(,&F&F(F*F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "poly:=expand((X^2+2*X+3)*(X+3)*(X+1)*(X^2+6*X+3)) mod 7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%polyG,0*$%\"XG\"\"'\"\"\"*$F '\"\"&F+*$F'\"\"%F-*$F'\"\"$F)*$F'\"\"#F+F'F/F(F)" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 26 "expand((X+1)*(X+3)) mod 7;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$%\"XG\"\"#\"\"\"F%\"\"%\"\"$F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "expand((X^2+6*X+3)*(X^2+2*X+3)) mod 7;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*$%\"XG\"\"%\"\"\"*$F%\"\"$F'*$F%\" \"#F&F%F)F+F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Separedegr es(poly,7,X);\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,(*$%\"XG\"\"#\" \"\"F&\"\"%\"\"$F(,,*$F&F)F(*$F&F*F(F%F)F&F*F'F(" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 15 "Ca maaarche ..." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 22 "Fonction FactoriseAvec" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 379 "FactoriseAvec :=proc(F,X,p,d,T)\nlocal A,B,C,aux,deg _A,deg_B,deg_C;\nA:=Gcd(F,T) mod p; deg_A:=degree(A,X);\naux:=Powmod(T ,(p^d-1)/2,F,X) mod p;\nB:=Gcd(F,aux-1) mod p; deg_B:=degree(B,X);\nC: =Gcd(F,aux+1) mod p; deg_C:=degree(C,X);\n\nif ((deg_A=deg_B) and (deg _B=0)) or ((deg_A=deg_C) and (deg_C=0)) or ((deg_C=deg_B) and (deg_B=0 )) then\n RETURN(-1)\nelse\n RETURN([A,B,C]) fi;\nend;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%.FactoriseAvecG:6'%\"FG%\"XG%\"pG%\"dG%\"T G6)%\"AG%\"BG%\"CG%$auxG%°_AG%°_BG%°_CG6\"F4C*>8$-%$modG6$-%$ GcdG6$9$9(9&>8(-%'degreeG6$F79%>8'-F96$-%'PowmodG6&F?,&)F@9'#\"\"\"\" \"##!\"\"FSFRF>FFF@>8%-F96$-F<6$F>,&FHFRFUFRF@>8)-FD6$FWFF>8&-F96$-F<6 $F>,&FHFRFRFRF@>8*-FD6$F\\oFF@%553/FBFhn/Fhn\"\"!3/FBFco/FcoF\\p3/FcoF hnF[p-%'RETURNG6#FU-Fcp6#7%F7FWF\\oF4F4" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "FactoriseAvec(X^2+5*X+4,X,7,1,X);" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 35 "FactoriseAvec(X^2+5*X+4,X,7,1,X+1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,&%\"XG \"\"\"F&F&,&F%F&\"\"%F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "expand((X+1)*(X+4));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$%\"XG \"\"#\"\"\"F%\"\"&\"\"%F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "Ca m arche aussi ..." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 35 "Factorisatio n des termes de degr\351 d" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 20 "Pol ynomes al\351atoires" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 151 "Ran domPoly:=proc(X,p)\nlocal seed;\nseed:=rand(1..p-1);\nif rand(1..2)()= 1 then RETURN(seed())\nelse RETURN(expand(seed()+X*RandomPoly(X,p)) mo d p)\nfi\nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+RandomPolyG:6$%\" XG%\"pG6#%%seedG6\"F+C$>8$-%%randG6#;\"\"\",&9%F3!\"\"F3@%/--F06#;F3\" \"#F+F3-%'RETURNG6#-F.F+-F?6#-%$modG6$-%'expandG6#,&FAF3*&9$F3-F$6$FLF 5F3F3F5F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "seq(RandomPo ly(X,7),k=1..20);" }}{PARA 12 "" 1 "" {XPPMATH 20 "66,*\"\"&\"\"\"%\"X GF$*$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*F)F,*$F&F0F,F1F*,&F%F %F&F,,&F0F%F&F*,,F$F%F&F(F'F0F)F*F4F$F(F(,*F(F%F&F,F'F(F)F0F(" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "RandomNonConstantPoly:=(X,p) ->expand(rand(1..p-1)()+X*RandomPoly(X,p));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%6RandomNonConstantPolyG:6$%\"XG%\"pG6\"6$%)operatorG% &arrowGF)-%'expandG6#,&--%%randG6#;\"\"\",&9%F6!\"\"F6F)F6*&9$F6-%+Ran domPolyG6$F;F8F6F6F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "s eq(RandomNonConstantPoly(X,7),k=1..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6,,&\"\"'\"\"\"%\"XG\"\"&,(F%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&F0,(F0F%F&F+F*F%,&F+F%F&F% ,(F$F%F&F'F*F',&F'F%F&F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "evalf(add(degree(RandomNonConstantPoly(X,7),X),k=1..5000)/5000);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+++?)*>!\"*" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 25 "sum(d/2^d,d=1..infinity);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "L'esp\351 rance th\351orique correspond \340 l'exp\351rience." }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 30 "Factorisation du bloc concern\351" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 496 "FactoriseDegreFixe:=proc(F, d,p,X)\nlocal T,L,succes,L1,L2,L3;\nif degree(F,X)=d or degree(F,X)=0 \+ then RETURN([F]) fi;\nsucces:=false:\nto 50 while not(succes)\ndo\nT:= RandomNonConstantPoly(X,p);\nL:=FactoriseAvec(F,X,p,d,T);\nsucces:=nop s(L)=3\nod;\nif succes then\n L1:=FactoriseDegreFixe(L[1],d,p,X):\n \+ L2:=FactoriseDegreFixe(L[2],d,p,X):\n L3:=FactoriseDegreFixe(L[3],d,p ,X):\n if L1<>1515 and L2<>1515 and L3<>1515\n then RETURN([op(L1) ,op(L2),op(L3)]) else RETURN(1515) fi\nelse RETURN(1515) fi;\nend;" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%3FactoriseDegreFixeG:6&%\"FG%\"dG%\" pG%\"XG6(%\"TG%\"LG%'succesG%#L1G%#L2G%#L3G6\"F2C&@$5/-%'degreeG6$9$9' 9%/F7\"\"!-%'RETURNG6#7#F:>8&%&falseG?(F2\"\"\"FG\"#]4FDC%>8$-%6Random NonConstantPolyG6$F;9&>8%-%.FactoriseAvecG6'F:F;FPFFD/-%%nopsG6#FR \"\"$@%FDC&>8'-F$6&&FR6#FGF8(-F$6&&FR6#\"\"#F8)-F$6&&FR6#F enF " 0 "" {MPLTEXT 1 0 36 "Factor iseDegreFixe(X^2+5*X+4,1,7,X);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\" \"\",&F$F$%\"XGF$,&\"\"%F$F&F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "FactoriseDegreFixe(X^4+X^3+4*X^2+3*X+2,2,7,X);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\",(*$%\"XG\"\"#F$F'F(\"\"$F$,(F&F$F'\"\"'F) F$" }}}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 11 "Et enfin..." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "Toilettage:=proc(L)\nlocal i,Sres; \nSres:=NULL;\nfor i to nops(L) do if L[i]<>1 then Sres:=Sres,L[i] fi \+ od;\nRETURN([Sres])\nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+Toilet tageG:6#%\"LG6$%\"iG%%SresG6\"F+C%>8%%%NULLG?(8$\"\"\"F2-%%nopsG6#9$%% trueG@$0&F66#F1F2>F.6$F.F:-%'RETURNG6#7#F.F+F+" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 284 "Factorise:=proc(P,p,X)\nlocal Q,R,Lres,i,L;\n if degree(P,X)=0 then RETURN([1]) fi;\nQ:=Gcd(P,diff(P,X)) mod p;\nR:= Quo(P,Q,X) mod p;\nLres:=Factorise(Q,p,X);\nL:=Separedegres(R,p,X);\n \nfor i to nops(L) do Lres:=[op(Lres),op(FactoriseDegreFixe(L[i],i,p,X ))] od;\n\nRETURN(Toilettage(Lres))\nend;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*FactoriseG:6%%\"PG%\"pG%\"XG6'%\"QG%\"RG%%LresG%\"iG %\"LG6\"F0C)@$/-%'degreeG6$9$9&\"\"!-%'RETURNG6#7#\"\"\">8$-%$modG6$-% $GcdG6$F7-%%diffGF69%>8%-FB6$-%$QuoG6%F7F@F8FI>8&-F$6%F@FIF8>8(-%-Sepa redegresG6%FKFIF8?(8'F>F>-%%nopsG6#FV%%trueG>FR7$-%#opG6#FR-F]o6#-%3Fa ctoriseDegreFixeG6&&FV6#FenFenFIF8-F;6#-%+ToilettageGF^oF0F0" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Factorise(X^2+2*X+3,7,X);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#7#,(*$%\"XG\"\"#\"\"\"F&F'\"\"$F(" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "Factorise(X^4+X^3+4*X^2+3*X +2,7,X);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,(*$%\"XG\"\"#\"\"\"F&\" \"'\"\"$F(,(F%F(F&F'F*F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "Factorise((X+1)^3,7,X);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,&\"\"\" F%%\"XGF%F$F$" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 17 "Le test ultime. .." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Factorise(X^(5^2)-X,5, X);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#71,&%\"XG\"\"\"\"\"#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&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&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Factor(X^(5^2)-X) mod 5;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#*@,(\"\"#\"\"\"%\"XGF&*$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&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&F'F%F*F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "Factorise((X^(5^2)-X)*(2+X^2 +4*X)*(X^2+2*X+4)^3,5,X);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#75,(*$%\" XG\"\"#\"\"\"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,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(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "Fact orise((X^(5^2)-X)^2*(2+X^2+4*X)*(X^2+2*X+4)^3,5,X);" }}{PARA 8 "" 1 " " {TEXT -1 48 "Error, (in mod/Rem) too many levels of recursion" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "Factor((X^(5^2)-X)^2*(2+X^2+ 4*X)*(X^2+2*X+4)^3) mod 5;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*@,(\"\" #\"\"\"%\"XGF&*$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&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'F%F*F&F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "OK..." }}}}}}{MARK "1 1 0" 82 }{VIEWOPTS 1 1 0 1 1 1803 }