{VERSION 4 0 "IBM INTEL LINUX" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 1 18 0 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 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 0 }1 0 0 0 8 4 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 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 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 33 "Liste des facteurs premiers de n." }} {PARA 0 "" 0 "" {TEXT -1 71 "La fonction suivante rend la liste des fa cteurs premiers de l'entier n." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "PrimeDivs := proc(n) \nmap(t->t[1],op(2,ifactors(n)));\nend;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%*PrimeDivsGR6#%\"nG6\"F(F(-%$mapG6$R 6#%\"tGF(6$%)operatorG%&arrowGF(&9$6#\"\"\"F(F(F(-%#opG6$\"\"#-%)ifact orsG6#F3F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "PrimeDivs (25452);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7&\"\"#\"\"$\"\"(\"$,\"" } }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 75 "Construction d'un nombre M de l'ordre de 10^100 de petits facteurs premiers" }{TEXT 256 0 "" }{TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 120 "BigEvenNumber := proc(n) \nlocal M,i;\nM := 2;\ni := 5000;\nwhile M < 10^n do \n M := M * ithprime(i) ;\n i := i+1;\nod;\n M\nend;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%.BigEvenNumberGR6#%\"nG6$ %\"MG%\"iG6\"F+C&>8$\"\"#>8%\"%+]?(F+\"\"\"F4F+2F.)\"#59$C$>F.*&F.F4-% )ithprimeG6#F1F4>F1,&F1F4F4F4F.F+F+F+" }}}{PARA 0 "" 0 "" {TEXT -1 10 " Exemple :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "M100 := BigEv enNumber(100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%M100G\"cq')G8lih< Ij\\&*['e[Zv\\/1?#ym&oSFEA+8zP(p$\\^S)GS,'R9WDZ\"e.B+F" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "ifactor(M100);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*P-%!G6#\"\"#\"\"\"-F%6#\"&@)[F(-F%6#\"&4)[F(-F%6#\"&*z [F(-F%6#\"&z([F(-F%6#\"&\\'[F(-F%6#\"&6'[F(-F%6#\"&Z'[F(-F%6#\"&h'[F(- F%6#\"&n([F(-F%6#\"&x'[F(-F%6#\"&\"y[F(-F%6#\"&d([F(-F%6#\"&(y[F(-F%6# \"&B'[F(-F%6#\"&L([F(-F%6#\"&<)[F(-F%6#\"&>'[F(-F%6#\"&z'[F(-F%6#\"&J( [F(-F%6#\"&h([F(-F%6#\"&t'[F(-F%6#\"&^([F(" }}}}{SECT 0 {PARA 3 "" 0 " " {TEXT -1 18 " Le test de Lucas." }}{PARA 0 "" 0 "" {TEXT -1 41 " Luc as(P,a) rend vrai si et seulement si " }}{PARA 0 "" 0 "" {TEXT -1 61 " 1) P est premier.\n 2) a est un genetrateur de (Z/PZ )*" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 252 "Lucas := proc(P,a)\nlocal i , primefactors;\nif a &^ (P-1) mod P \+ <> 1 then RETURN(false) \nelse primefactors := PrimeDivs(P);\n for \+ i from 1 to nops(primefactors)\n do if (a &^ ((P-1)/primefactors[i] )) mod P = 1 then RETURN(false) fi od\nfi;\ntrue\nend;\n" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#>%&LucasGR6$%\"PG%\"aG6$%\"iG%-primefactorsG6\"F ,C$@%0-%$modG6$-%#&^G6$9%,&9$\"\"\"F9!\"\"F8F9-%'RETURNG6#%&falseGC$>8 %-%*PrimeDivsG6#F8?(8$F9F9-%%nopsG6#FA%%trueG@$/-F16$-F46$F6*&F7F9&FA6 #FFF:F8F9F;FJF,F,F," }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 40 " Construction d'un grand nombre premier. " }}{PARA 0 "" 0 "" {TEXT -1 87 "La fonction bigprime commence par con struire un nombre pair M, de la taille desiree et " }}{PARA 0 "" 0 "" {TEXT -1 95 "de facteurs premiers plutot petits. Puis on applique le t est de Lucas lucas(P,2) successivement" }}{PARA 0 "" 0 "" {TEXT -1 85 "aux nombres P = M+1, 2M+1,....., kM+1,.... jusqu'a obtenir un nombre premier dont le" }}{PARA 0 "" 0 "" {TEXT -1 86 "groupe multiplicatif \+ est engendre par 2. On accelere le calcul en construisant d'abord" }} {PARA 0 "" 0 "" {TEXT -1 79 "le nombre Q produit des 200 nombres premi ers, et, pour chaque P = kM+1 candidat" }}{PARA 0 "" 0 "" {TEXT -1 89 "a etre premier, on commence par calculer le pgcd de P et Q. Si ce pgc d est distinct de 1," }}{PARA 0 "" 0 "" {TEXT -1 78 "il est inutile d e lancer le test de Lucas Lucas(P,2) car P n'est pas premier." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 236 "BigPrime := proc(n) \nlocal M,P,Q;\nM := BigEvenNumber(n);\nQ := \+ product(ithprime(i),i=2..200);\nfor P from M + 1 by M do\n if igcd( P,Q) = 1 then \n if Lucas(P,2) then print(\"nombre d'essais \",(P-1 )/M) ; RETURN(P) fi; \n fi\n od;\nend;\n\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%)BigPrimeGR6#%\"nG6%%\"MG%\"PG%\"QG6\"F,C%>8$-%.BigEv enNumberG6#9$>8&-%(productG6$-%)ithprimeG6#%\"iG/F<;\"\"#\"$+#?(8%,&F/ \"\"\"FDFDF/F,%%trueG@$/-%%igcdG6$FBF5FD@$-%&LucasG6$FBF?C$-%&printG6$ Q1nombre~d'essais~6\"*&,&FBFDFD!\"\"FDF/FW-%'RETURNG6#FBF,F,F," }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {SECT 0 {PARA 3 "" 0 "" {TEXT -1 14 "La recompense " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "P := BigPrime(200);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$Q1nombre~d'essais~6\"\"$9%" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"PG\"hw(RV()HJyXh)*)pYcYu5l9,t=OGd2An!o$R@Bh.JLDg[#p qMsW?2UJ@$)4'[#p4%G!**)[w))fu0'4 " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 138 "Avec un peu de patience (environ 2 ou 3 minutes sur ma \+ machine PC Pentium 1GHZ) bigprime(500) donne un nombre premier de 50 0 chiffres. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "7 2 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }