{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" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 63 "2. Egyszer\305\261 faktori z\303\241l\303\241si m\303\263dszerek" }}{PARA 0 "" 0 "" {TEXT 201 0 " " }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 64 "3. Egyszer\305\261 pr\303\2 55mtesztel\303\251si m\303\263dszerek" }}{PARA 0 "" 0 "" {TEXT 201 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "restart; with(numtheory) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7QI&GIgcdG6\"I)bigomegaGF$I&cfracGF $I)cfracpolGF$I+cyclotomicGF$I)divisorsGF$I)factorEQGF$I*factorsetGF$I 'fermatGF$I)imagunitGF$I&indexGF$I/integral_basisGF$I)invcfracGF$I'inv phiGF$I*issqrfreeGF$I'jacobiGF$I*kroneckerGF$I'lambdaGF$I)legendreGF$I )mcombineGF$I)mersenneGF$I(migcdexGF$I*minkowskiGF$I(mipolysGF$I%mlogG F$I'mobiusGF$I&mrootGF$I&msqrtGF$I)nearestpGF$I*nthconverGF$I)nthdenom GF$I)nthnumerGF$I'nthpowGF$I&orderG%*protectedGI)pdexpandGF$I$phiGF$I# piGF$I*pprimrootGF$I)primrootGF$I(quadresGF$I+rootsunityGF$I*safeprime GF$I&sigmaGF$I*sq2factorGF$I(sum2sqrGF$I$tauGF$I%thueGF$" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 6 "3.1. K" }{TEXT 206 8 "\303\251" }{TEXT 206 2 "rd" }{TEXT 206 8 "\303\251" }{TEXT 206 2 "s." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "3.2. Feladat. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 53 "# This procedure do Wilson's test. The \+ return value\n" }{MPLTEXT 1 0 56 "# is a pair of lower two digits of ( n-1)!+1 in base n.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 42 "wilsontest:=proc(n::posint) local i,r,m;\n" }{MPLTEXT 1 0 15 "r:=1; m:=n^2;\n" }{MPLTEXT 1 0 41 "for i from 2 to n-1 do r:= r*i mod m od;\n" }{MPLTEXT 1 0 40 "r:=r+1 mod m; [irem(r,n),iquo(r,n)] end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6%I\"iGF%I\"rGF%I\" mGF%F%F%C'>F(\"\"\">F)*$)F$\"\"#F,?(F'F0F,,&F$F,F,!\"\"I%trueG%*protec tedG>F(-I$modGF%6$*&F(F,F'F,F)>F(-F86$,&F(F,F,F,F)7$-I%iremGF56$F(F$-I %iquoGF5FBF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 39 "# This procedure do Wilson's test and\n" }{MPLTEXT 1 0 41 "# look for Wilson numbers until a given\n" }{MPLTEXT 1 0 10 "# l imit.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 32 " wilson:=proc(n) local i,r,p,w;\n" }{MPLTEXT 1 0 15 "p:=[]; w:=[];\n" } {MPLTEXT 1 0 22 "for i from 2 to n do\n" }{MPLTEXT 1 0 21 " r:=wilson test(i);\n" }{MPLTEXT 1 0 18 " if r[1]=0 then\n" }{MPLTEXT 1 0 19 " \+ p:=[op(p),i];\n" }{MPLTEXT 1 0 36 " if r[2]=0 then w:=[op(w),i] f i\n" }{MPLTEXT 1 0 6 " fi\n" }{MPLTEXT 1 0 14 "od; [w,p] end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6&I\"iGF%I\"rGF%I\"pGF%I\"wG F%F%F%C&>F)7\">F*F-?(F'\"\"#\"\"\"F$I%trueG%*protectedGC$>F(-I+wilsont estGF%6#F'@$/&F(6#F1\"\"!C$>F)7$-I#opGF36#F)F'@$/&F(6#F0F=>F*7$-FB6#F* F'7$F*F)F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "wilson(10 00);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$7%\"\"&\"#8\"$j&7du\"\"#\"\"$F $\"\"(\"#6F%\"#<\"#>\"#B\"#H\"#J\"#P\"#T\"#V\"#Z\"#`\"#f\"#h\"#n\"#r\" #t\"#z\"#$)\"#*)\"#(*\"$,\"\"$.\"\"$2\"\"$4\"\"$8\"\"$F\"\"$J\"\"$P\" \"$R\"\"$\\\"\"$^\"\"$d\"\"$j\"\"$n\"\"$t\"\"$z\"\"$\"=\"$\">\"$$>\"$( >\"$*>\"$6#\"$B#\"$F#\"$H#\"$L#\"$R#\"$T#\"$^#\"$d#\"$j#\"$p#\"$r#\"$x #\"$\"G\"$$G\"$$H\"$2$\"$6$\"$8$\"$<$\"$J$\"$P$\"$Z$\"$\\$\"$`$\"$f$\" $n$\"$t$\"$z$\"$$Q\"$*Q\"$(R\"$,%\"$4%\"$>%\"$@%\"$J%\"$L%\"$R%\"$V%\" $\\%\"$d%\"$h%\"$j%\"$n%\"$z%\"$([\"$\"\\\"$*\\\"$.&\"$4&\"$@&\"$B&\"$ T&\"$Z&\"$d&F&\"$p&\"$r&\"$x&\"$(e\"$$f\"$*f\"$,'\"$2'\"$8'\"$<'\"$>' \"$J'\"$T'\"$V'\"$Z'\"$`'\"$f'\"$h'\"$t'\"$x'\"$$o\"$\"p\"$,(\"$4(\"$> (\"$F(\"$L(\"$R(\"$V(\"$^(\"$d(\"$h(\"$p(\"$t(\"$(y\"$(z\"$4)\"$6)\"$@ )\"$B)\"$F)\"$H)\"$R)\"$`)\"$d)\"$f)\"$j)\"$x)\"$\"))\"$$))\"$())\"$2* \"$6*\"$>*\"$H*\"$P*\"$T*\"$Z*\"$`*\"$n*\"$r*\"$x*\"$$)*\"$\"**\"$(**" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 10 "3.3. Probl" }{TEXT 206 8 " \303\251" }{TEXT 206 3 "ma." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {SECT 0 {PARA 4 "" 0 "" {TEXT 206 18 "3.4. Fermat-teszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "n:=(2 ^28-9)/7; 3&^(n-1) mod n; 2&^(n-1)mod n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")@zMQ" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "\")*[D-\"" }}}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "3.5. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 65 "# This procedure do Fermat's test for the number n with base a. \n" }{MPLTEXT 1 0 61 "# If the result is false, the number is composit e, if FAIL,\n" }{MPLTEXT 1 0 22 "# then may be prime.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 39 "fermattest:=proc(n::p osint,a::posint)\n" }{MPLTEXT 1 0 65 "if type(n,even) then error \"fir st argument must be odd\",n fi;\n" }{MPLTEXT 1 0 57 "if n<3 then error \"first argument is too small\",n fi;\n" }{MPLTEXT 1 0 59 "if n<=a th en error \"second argument is too large\",a fi;\n" }{MPLTEXT 1 0 55 "i f modp(a&^(n-1),n)<>1 then RETURN(false) fi; FAIL end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protectedG'I\"aGF&F'F&F&F&C' @$-I%typeGF(6$F%I%evenGF(Y6$Q;first~argument~must~be~oddF&F%@$2F%\"\"$ Y6$Q " 0 "" {MPLTEXT 1 0 48 "n:=(2^28-9)/7; fermattest(n,3); fermattest(n,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")@zMQ" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*prot ectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}}} {SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "3.6. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 62 "# This procedure look for pseudoprimes until a given \+ limit n\n" }{MPLTEXT 1 0 27 "# in bases in the list L.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 62 "pseudoprime:=proc(n:: posint,L::list(posint)) local pp,i,a,t;\n" }{MPLTEXT 1 0 9 "pp:=[];\n" }{MPLTEXT 1 0 35 "for i from max(3,op(L))+1 to n do\n" }{MPLTEXT 1 0 33 " if type(i,even) then next fi;\n" }{MPLTEXT 1 0 17 " for a in L \+ do\n" }{MPLTEXT 1 0 25 " t:=fermattest(i,a);\n" }{MPLTEXT 1 0 28 " \+ if not t then break fi\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 18 " if t=FAIL then\n" }{MPLTEXT 1 0 46 " if not isprime(i) then p p:=[op(pp),i] fi\n" }{MPLTEXT 1 0 6 " fi\n" }{MPLTEXT 1 0 11 "od; pp \+ end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protecte dG'I\"LGF&-I%listGF(6#F'6&I#ppGF&I\"iGF&I\"aGF&I\"tGF&F&F&C%>F/7\"?(F0 ,&-I$maxGF(6$\"\"$-I#opGF(6#F*\"\"\"F?F?F?F%I%trueGF(C%@$-I%typeGF(6$F 0I%evenGF(\\?&F1F*F@C$>F2-I+fermattestGF&6$F0F1@$4F2[@$/F2I%FAILGF(@$4 -I(isprimeG6$F(I(_syslibGF&6#F0>F/7$-F=6#F/F0F/F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "pseudoprime(10000,[2]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "78\"$T$\"$h&\"$X'\"%06\"%(Q\"\"%H<\"%0>\"%Z?\"%l C\"%,F\"%@G\"%xK\"%LS\"%pV\"%rV\"%\"o%\"%ha\"%,m\"%dz\"%@$)\"%\"[)\"%6 *)" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "3.7. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n " }{MPLTEXT 1 0 38 "# This procedure look for Carmichael\n" }{MPLTEXT 1 0 34 "# numbers until a given limit n.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 36 "carmichael:=proc(n) local L,i,a, t;\n" }{MPLTEXT 1 0 8 "L:=[];\n" }{MPLTEXT 1 0 22 "for i from 2 to n d o\n" }{MPLTEXT 1 0 33 " if type(i,even) then next fi;\n" }{MPLTEXT 1 0 31 " if isprime(i) then next fi;\n" }{MPLTEXT 1 0 26 " for a from \+ 2 to i-1 do\n" }{MPLTEXT 1 0 25 " if igcd(i,a)=1 then\n" }{MPLTEXT 1 0 27 " t:=fermattest(i,a);\n" }{MPLTEXT 1 0 30 " if not t \+ then break fi\n" }{MPLTEXT 1 0 8 " fi\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 34 " if t=FAIL then L:=[op(L),i] fi\n" }{MPLTEXT 1 0 10 "od; L end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6&I\"LGF%I \"iGF%I\"aGF%I\"tGF%F%F%C%>F'7\"?(F(\"\"#\"\"\"F$I%trueG%*protectedGC& @$-I%typeGF26$F(I%evenGF2\\@$-I(isprimeG6$F2I(_syslibGF%6#F(F9?(F)F/F0 ,&F(F0F0!\"\"F1@$/-I%igcdGF26$F(F)F0C$>F*-I+fermattestGF%FG@$4F*[@$/F* I%FAILGF2>F'7$-I#opGF26#F'F(F'F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "carmichael(10000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7 )\"$h&\"%06\"%H<\"%lC\"%@G\"%,m\"%6*)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 62 "# Much larger speed can be obta ined using that a number n is\n" }{MPLTEXT 1 0 67 "# Carmichael number if and only if it is squre free, has at least\n" }{MPLTEXT 1 0 66 "# \+ three prime factors and p-1 divides n-1 for every prime factor\n" } {MPLTEXT 1 0 11 "# p of n.\n" }{MPLTEXT 1 0 3 "#\n" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 11 "3.8. Lemma." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 11 "3.9. Lemma." }}{PARA 0 "" 0 " " {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 7 "3.10. T" } {TEXT 206 8 "\303\251" }{TEXT 206 4 "tel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 11 "3.11. Defin" }{TEXT 206 8 "\303\255" }{TEXT 206 2 "ci" }{TEXT 206 8 "\303\263" }{TEXT 206 1 "." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "3.12. Euler t" }{TEXT 206 8 "\303\251" }{TEXT 206 5 "tel e." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 16 "3.13. Gauss lemm" }{TEXT 206 10 "\303\241ja" }{TEXT 206 1 "." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 34 "3.14. Gauss kvadratikus recip rocit" }{TEXT 206 8 "\303\241" }{TEXT 206 4 "si t" }{TEXT 206 8 "\303 \266" }{TEXT 206 2 "rv" }{TEXT 206 8 "\303\251" }{TEXT 206 4 "nye." }} }{SECT 1 {PARA 4 "" 0 "" {TEXT 206 11 "3.15. Defin" }{TEXT 206 8 "\303 \255" }{TEXT 206 2 "ci" }{TEXT 206 8 "\303\263" }{TEXT 206 1 "." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 7 "3.16. T" }{TEXT 206 8 "\303\251" }{TEXT 206 4 "tel." }}{PARA 0 "" 0 " " {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 7 "3.17. P" } {TEXT 206 8 "\303\251" }{TEXT 206 4 "lda." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 20 "3.18. A Jacobi-szimb " }{TEXT 206 8 "\303\263" }{TEXT 206 8 "lum kisz" }{TEXT 206 8 "\303\2 41" }{TEXT 206 1 "m" }{TEXT 206 8 "\303\255" }{TEXT 206 1 "t" }{TEXT 206 8 "\303\241" }{TEXT 206 3 "sa." }}{PARA 0 "" 0 "" {TEXT 201 0 "" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 39 "# Thi s recursive procedure calculates\n" }{MPLTEXT 1 0 40 "# the Jacobi sym bol (n|m) for integers\n" }{MPLTEXT 1 0 30 "# m>2 and n, where m is od d.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 51 "jac obisymbol:=proc(n::integer,m::posint) local s;\n" }{MPLTEXT 1 0 64 "if type(m,even) then error \"second argument must be odd\" fi;\n" } {MPLTEXT 1 0 27 "if n=0 then RETURN(0) fi;\n" }{MPLTEXT 1 0 27 "if n=1 then RETURN(1) fi;\n" }{MPLTEXT 1 0 14 "if n<0 then \n" }{MPLTEXT 1 0 30 " if type((m-1)/2,odd) then \n" }{MPLTEXT 1 0 33 " RETURN(-ja cobisymbol(-n,m))\n" }{MPLTEXT 1 0 8 " else\n" }{MPLTEXT 1 0 32 " \+ RETURN(jacobisymbol(-n,m))\n" }{MPLTEXT 1 0 6 " fi\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 22 "if type(n,even) then\n" }{MPLTEXT 1 0 40 " if type((irem(m,16)^2-1)/8,odd) then\n" }{MPLTEXT 1 0 34 " RETURN (-jacobisymbol(n/2,m))\n" }{MPLTEXT 1 0 8 " else\n" }{MPLTEXT 1 0 33 " RETURN(jacobisymbol(n/2,m))\n" }{MPLTEXT 1 0 6 " fi\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 51 "if n>m then RETURN(jacobisymbol(irem( n,m),m)) fi;\n" }{MPLTEXT 1 0 51 "if type(irem((m-1)/2,2)*irem((n-1)/2 ,2),odd) then\n" }{MPLTEXT 1 0 22 " -jacobisymbol(m,n)\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 21 " jacobisymbol(m,n)\n" }{MPLTEXT 1 0 4 "fi\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I \"nG6\"I(integerG%*protectedG'I\"mGF&I'posintGF(6#I\"sGF&F&F&C)@$-I%ty peGF(6$F*I%evenGF(YQ@$2F%F8@%-F16$,&*&#F>\"\"#F>F*F>F>FH!\"\"I$odd GF(-F:6#,$-I-jacobisymbolGF&6$,$F%FJF*FJ-F:6#FO@$-F16$F%F3@%-F16$,&*&# F>\"\")F>)-I%iremGF(6$F*\"#;FIF>F>FgnFJFK-F:6#,$-FP6$,$*&FHF>F%F>F>F*F J-F:6#Fao@$2F*F%-F:6#-FP6$-F[o6$F%F*F*@%-F16$*&-F[o6$FFFIF>-F[o6$,&Fdo F>FHFJFIF>FK,$-FP6$F*F%FJFipF&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "debug(jacobisymbol); jacobisymbol(76,131);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I-jacobisymbolG6\"" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter jacobisymbol, args = 76, 131\n" }{TEXT 207 42 "\{- -> enter jacobisymbol, args = 38, 131\n" }{TEXT 207 42 "\{--> enter ja cobisymbol, args = 19, 131\n" }{TEXT 207 42 "\{--> enter jacobisymbol, args = 131, 19\n" }{TEXT 207 41 "\{--> enter jacobisymbol, args = 17, 19\n" }{TEXT 207 39 "\{--> enter jacobisymbol, args = 19, 17" }} {PARA 9 "" 1 "" {TEXT 207 40 "\{--> enter jacobisymbol, args = 2, 17\n " }{TEXT 207 40 "\{--> enter jacobisymbol, args = 1, 17\n" }{TEXT 207 51 "<-- exit jacobisymbol (now in jacobisymbol) = 1\}\n" }{TEXT 207 51 "<-- exit jacobisymbol (now in jacobisymbol) = 1\}\n" }{TEXT 207 49 "<-- exit jacobisymbol (now in jacobisymbol) = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit jaco bisymbol (now in jacobisymbol) = 1\}\n" }{TEXT 207 49 "<-- exit jacobi symbol (now in jacobisymbol) = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "! \"\"" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit jacobisymbol (now in ja cobisymbol) = 1\}\n" }{TEXT 207 51 "<-- exit jacobisymbol (now in jaco bisymbol) = 1\}\n" }{TEXT 207 46 "<-- exit jacobisymbol (now at top le vel) = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 18 "# What is this?\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 41 "jacobiprob a:=proc(a,b,p,n) local i,j,L;\n" }{MPLTEXT 1 0 31 "for i from 0 to n-1 do L:=[];\n" }{MPLTEXT 1 0 64 " for j from 0 to p-1 do L:=[op(L),jac obi(a,b+(i*p+j)*a)]; od;\n" }{MPLTEXT 1 0 13 " print(L);\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I \"pGF%I\"nGF%6%I\"iGF%I\"jGF%I\"LGF%F%F%?(F*\"\"!\"\"\",&F(F/F/!\"\"I% trueG%*protectedGC%>F,7\"?(F+F.F/,&F'F/F/F1F2>F,7$-I#opGF36#F,-_I*numt heoryG6$F3I(_syslibGF%I'jacobiGF%6$F$,&F&F/*&,&*&F*F/F'F/F/F+F/F/F$F/F /-I&printGF3F=F%F%F%" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.19. \+ Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 14 "3.20. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verboseproc=2);" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "print(jacobi);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$' I\"aG6\"-I#OrGF&6$I(integerG%*protectedG-I$NotGF&6#I)constantGF+'I\"bG F&-F(6$I*nonnegintGF+F,6%I#b2GF&I\"qGF&I\"sGF&6#IaoCopyright~(c)~1992~ by~the~University~of~Waterloo.~All~rights~reserved.GF&F&C$@&0%&nargsG \"\"#Y6$QBexpecting~2~arguments,~but~got~%1F&F>43-I%typeGF+6$F%.F*-FF6 $F1.F4O-.%)procnameG6#%%argsG@%3/-I%iremGF+6$F%F?\"\"!/-FV6$F1F?FXFXC' >F6F1?(F&\"\"\"FinF&/-FV6%F6\"\"%.F7FX>F6F7@%/-FV6%F6F?F^oFXC$F_o>F8-I +jacobi_auxGF&6$F?-I$absGF+6#F%>F8Fin@$32F%FX/-FV6$F6F]o\"\"$>F8,$F8! \"\"*&F8Fin-Fgo6$FioF6FinF&F&6$FgoFgo" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 14 "3.21. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "print(legendre);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"aG6\"-I#OrGF&6$I(integerG%*protectedG-I$ NotGF&6#I)constantGF+'I\"pGF&-F(6$I&primeGF&F,F&6#IinCopyright~(c)~199 4~by~Waterloo~Maple~Inc.~All~rights~reserved.GF&F&@'0%&nargsG\"\"#Y6$Q Bexpecting~2~arguments,~but~got~%1F&F93-I%typeGF+6$F%.F*-F@6$F1.F4-&I* numtheoryG6$F+I(_syslibGF&6#.I'jacobiGF&6$F%F1O-.%)procnameG6#%%argsGF &F&6$FMI'jacobiG6$F+/I+modulenameGF&FH" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 29 "3.22. Soloway-Strassen-teszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "n:=561; 5&^(n-1) \+ mod n; 5&^((n-1)/2) mod n; jacobi(5,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$h&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#n" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 14 "3.23. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 62 "# This procedure do the Soloway-Strassen probabilistic test.\n" }{MPLTEXT 1 0 59 "# The first parameter is the integer to test, the se cond \n" }{MPLTEXT 1 0 60 "# the number of rounds. if the result is fa lse, the number\n" }{MPLTEXT 1 0 47 "# is composite, if FAIL, then pro bably prime.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 59 "solowaystrasse n:=proc(n::posint,m::posint) local i,b,rnd;\n" }{MPLTEXT 1 0 65 "if ty pe(n,even) then error \"first argument must be odd\",n fi;\n" } {MPLTEXT 1 0 57 "if n<5 then error \"first argument is too small\",n f i;\n" }{MPLTEXT 1 0 20 "rnd:=rand(2..n-2);\n" }{MPLTEXT 1 0 25 "for i \+ to m do b:=rnd();\n" }{MPLTEXT 1 0 41 " if igcd(b,n)>1 then RETURN(fa lse) fi;\n" }{MPLTEXT 1 0 70 " if modp(b&^((n-1)/2),n)<>modp(jacobi(b ,n),n) then RETURN(false) fi\n" }{MPLTEXT 1 0 13 "od; FAIL end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protectedG'I\"mG F&F'6%I\"iGF&I\"bGF&I$rndGF&F&F&C'@$-I%typeGF(6$F%I%evenGF(Y6$Q;first~ argument~must~be~oddF&F%@$2F%\"\"&Y6$QF.-I%randGF&6#;\"\"#,&F%\"\"\"FC!\"\"?(F,FEFEF*I%trueGF(C%>F--F.F&@$2 FE-I%igcdGF(6$F-F%-I'RETURNGF(6#I&falseGF(@$0-I%modpGF(6$-I#&^GF&6$F-, &*&#FEFCFEF%FEFEFinFFF%-FX6$-_I*numtheoryG6$F(I(_syslibGF&I'jacobiGF&F PF%FQI%FAILGF(F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "deb ug(solowaystrassen); solowaystrassen(5,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I0solowaystrassenG6\"" }}{PARA 9 "" 1 "" {TEXT 207 40 "\{ --> enter solowaystrassen, args = 5, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F#,&-f*F#F#6#I(builtinGF#F#\"$$RF#F#F#I%FAILG%*protectedG6% \"\"'\"\"#\"\"\"F/F.F/F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 " I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit soloways trassen (now at top level) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I %FAILG%*protectedG" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 25 "3.24. Mi ller-Rabin-teszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 56 "millerrabin:=proc(n::posint,b::posint) local j,e,r,bb;\n" }{MPLTEXT 1 0 57 "if n<9 then ERROR(`first parameter is \+ too small`,n) fi;\n" }{MPLTEXT 1 0 61 "if type(n,even) then ERROR(`fir st parameter is even`,n) fi;\n" }{MPLTEXT 1 0 58 "if b<2 then ERROR(`s econd parameter is too small`,b) fi;\n" }{MPLTEXT 1 0 59 "if n<=b then ERROR(`second parameter is too large`,b) fi;\n" }{MPLTEXT 1 0 15 "e:= 0; r:=n-1;\n" }{MPLTEXT 1 0 42 "while type(r,even) do e:=e+1; r:=r/2 o d;\n" }{MPLTEXT 1 0 49 "bb:=modp(b&^r,n); if bb=1 then RETURN(FAIL) fi ;\n" }{MPLTEXT 1 0 51 "for j to e while bb<>n-1 do bb:=modp(bb&^2,n) o d;\n" }{MPLTEXT 1 0 42 "if j=e+1 then RETURN(false) fi; FAIL; end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protectedG'I\"bG F&F'6&I\"jGF&I\"eGF&I\"rGF&I#bbGF&F&F&C.@$2F%\"\"*-I&ERRORGF(6$I=first ~parameter~is~too~smallGF&F%@$-I%typeGF(6$F%I%evenGF(-F56$I8first~para meter~is~evenGF&F%@$2F*\"\"#-F56$I>second~parameter~is~too~smallGF&F*@ $1F%F*-F56$I>second~parameter~is~too~largeGF&F*>F-\"\"!>F.,&F%\"\"\"FO !\"\"?(F&FOFOF&-F:6$F.FF-,&F-FOFOFO>F.,$*&#FOFBFOF.FOFO>F/-I%modpG F(6$-I#&^GF&6$F*F.F%@$/F/FO-I'RETURNGF(6#I%FAILGF(?(F,FOFOF-0F/FN>F/-F gn6$-Fjn6$F/FBF%@$/F,FV-F_o6#I&falseGF(FaoF&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "rabin:=proc(n::posint,m::posint) local i,j,b, e,r,rnd;\n" }{MPLTEXT 1 0 57 "if n<9 then ERROR(`first parameter is to o small`,n) fi;\n" }{MPLTEXT 1 0 61 "if type(n,even) then ERROR(`first parameter is even`,n) fi;\n" }{MPLTEXT 1 0 34 "rnd:=rand(2..n-1); e:= 0; r:=n-1;\n" }{MPLTEXT 1 0 42 "while type(r,even) do e:=e+1; r:=r/2 o d;\n" }{MPLTEXT 1 0 15 "for i to m do\n" }{MPLTEXT 1 0 13 " b:=rnd(); \n" }{MPLTEXT 1 0 40 " if 1n-1 do modp(%&^2,n) od;\n" }{MPLTEXT 1 0 35 " if j=e+1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 13 "od; FAIL en d;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protectedG 'I\"mGF&F'6(I\"iGF&I\"jGF&I\"bGF&I\"eGF&I\"rGF&I$rndGF&F&F&C*@$2F%\"\" *-I&ERRORGF(6$I=first~parameter~is~too~smallGF&F%@$-I%typeGF(6$F%I%eve nGF(-F76$I8first~parameter~is~evenGF&F%>F1-I%randGF&6#;\"\"#,&F%\"\"\" FI!\"\">F/\"\"!>F0FH?(F&FIFIF&-F<6$F0F>C$>F/,&F/FIFIFI>F0,$*&#FIFGFIF0 FIFI?(F,FIFIF*I%trueGF(C(>F.-F1F&@$2FI-I$gcdGF&6$F.F%-I'RETURNGF(6#I&f alseGF(-I%modpGF(6$-I#&^GF&6$F.F0F%@$/I\"%GF&FI\\?(F-FIFIF/0FhoFH-Fao6 $-Fdo6$FhoFGF%@$/F-FSF\\oI%FAILGF(F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "trueisprime:=proc(n::posint) local f;\n" }{MPLTEXT 1 0 31 "if n<2 then RETURN(false) fi;\n" }{MPLTEXT 1 0 67 "if n=2 or n=3 or n=5 or n=7 or n=11 or n=13 then RETURN(true) fi;\n" }{MPLTEXT 1 0 42 "if 1F*-I,millerrabinGF&6$F%F.@$/F*F2 -F0F)>F*-FX6$F%F;FZ@$2F%\"(`OP\"FD>F*-FX6$F%F=FZ@$2F%\"(,gK&FD>F*-FX6$ F%F?FZ@$2F%\"+^<.:KFD>F*-FX6$F%FAFZ@$2F%\".Z()*GI_@FD>F*-FX6$F%FCFZ@$2 F%\".$Qg'\\ZZ$FD>F*-FX6$F%\"# " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 49 "# This procedure do M iller's deterministic test\n" }{MPLTEXT 1 0 55 "# based on GRH. The pa rameter is the integer to test.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 3 " \n" }{MPLTEXT 1 0 42 "millertest:=proc(n::posint) local i,b,t;\n " }{MPLTEXT 1 0 31 "if n=1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 67 "if n=2 or n=3 or n=5 or n=7 or n=11 or n=13 then RETURN(true) fi;\n" }{MPLTEXT 1 0 40 "if type(n,even) then RETURN(false) fi;\n" }{MPLTEXT 1 0 31 "if n=9 then RETURN(false) fi;\n" }{MPLTEXT 1 0 27 "b:=floor(2. 0002*ln(n)^2);\n" }{MPLTEXT 1 0 22 "for i from 2 to b do\n" }{MPLTEXT 1 0 50 " if not millerrabin(n,i) then RETURN(false) fi;\n" }{MPLTEXT 1 0 13 "od; true end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#'I\"nG6\"I' posintG%*protectedG6%I\"iGF&I\"bGF&I\"tGF&F&F&C)@$/F%\"\"\"-I'RETURNGF (6#I&falseGF(@$55555/F%\"\"#/F%\"\"$/F%\"\"&/F%\"\"(/F%\"#6/F%\"#8-F26 #I%trueGF(@$-I%typeGF(6$F%I%evenGF(F1@$/F%\"\"*F1>F+-I&floorG6$F(I(_sy slibGF&6#*&$\"&-+#!\"%F0*$)-I#lnGFU6#F%F " 0 "" {MPLTEXT 1 0 15 " millertest(17);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*protectedG" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 18 "3.29. Lucas-teszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "# \n" }{MPLTEXT 1 0 33 "# This procedure do Lucas' test\n" }{MPLTEXT 1 0 37 "# for the number n on the naive way\n" }{MPLTEXT 1 0 16 "# using base a\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 36 "naivelucastest:=proc(n,a) local m;\n" }{MPLTEXT 1 0 39 "if igcd(a, n)>1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 47 "if modp(a&^(n-1),n)<> 1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 24 "for m from 2 to n-2 do\n " }{MPLTEXT 1 0 43 " if modp(a&^m,n)=1 then RETURN(false) fi\n" } {MPLTEXT 1 0 13 "od; true end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I \"nG6\"I\"aGF%6#I\"mGF%F%F%C&@$2\"\"\"-I%igcdG%*protectedG6$F&F$-I'RET URNGF/6#I&falseGF/@$0-I%modpGF/6$-I#&^GF%6$F&,&F$F,F,!\"\"F$F,F1?(F(\" \"#F,,&F$F,F@F>I%trueGF/@$/-F86$-F;6$F&F(F$F,F1FBF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 33 "# This proced ure do Lucas' test\n" }{MPLTEXT 1 0 40 "# for the number n using the s et S of \n" }{MPLTEXT 1 0 29 "# factors of n-1 and base a\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 33 "lucastest:=proc(n, a,S) local p;\n" }{MPLTEXT 1 0 59 "if n<=a then ERROR(`second paramete r is too large`,a) fi;\n" }{MPLTEXT 1 0 39 "if igcd(a,n)>1 then RETURN (false) fi;\n" }{MPLTEXT 1 0 47 "if modp(a&^(n-1),n)<>1 then RETURN(fa lse) fi;\n" }{MPLTEXT 1 0 15 "for p in S do\n" }{MPLTEXT 1 0 50 " if \+ modp(a&^((n-1)/p),n)=1 then RETURN(FAIL) fi\n" }{MPLTEXT 1 0 21 "od; \+ true end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"nG6\"I\"aGF%I \"SGF%6#I\"pGF%F%F%C'@$1F$F&-I&ERRORG%*protectedG6$I>second~parameter~ is~too~largeGF%F&@$2\"\"\"-I%igcdGF/6$F&F$-I'RETURNGF/6#I&falseGF/@$0- I%modpGF/6$-I#&^GF%6$F&,&F$F4F4!\"\"F$F4F8?&F)F'I%trueGF/@$/-F?6$-FB6$ F&*&FDF4F)FEF$F4-F96#I%FAILGF/FGF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 33 "# This procedure do Lucas' test \n" }{MPLTEXT 1 0 35 "# for numbers n*k^m+1 with small \n" }{MPLTEXT 1 0 21 "# n,k,m and base a.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 " \n" }{MPLTEXT 1 0 39 "speclucas:=proc(n,k,m,a) local S,N,p;\n" } {MPLTEXT 1 0 18 "S:=factorset(n);\n" }{MPLTEXT 1 0 41 "if m>0 then S:= S union factorset(k) fi;\n" }{MPLTEXT 1 0 13 "N:=n*k^m+1;\n" }{MPLTEXT 1 0 57 "if N<=a then ERROR(`last parameter is too large`,a) fi;\n" } {MPLTEXT 1 0 39 "if igcd(a,N)>1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 47 "if modp(a&^(N-1),N)<>1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 15 "for p in S do\n" }{MPLTEXT 1 0 50 " if modp(a&^((N-1)/p),N)=1 the n RETURN(FAIL) fi\n" }{MPLTEXT 1 0 21 "od; true end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"nG6\"I\"kGF%I\"mGF%I\"aGF%6%I\"SGF%I\"N GF%I\"pGF%F%F%C*>F*-_I*numtheoryG6$%*protectedGI(_syslibGF%I*factorset GF%6#F$@$2\"\"!F'>F*-I&unionGF36$F*-F06#F&>F+,&*&F$\"\"\")F&F'FCFCFCFC @$1F+F(-I&ERRORGF36$I " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 63 "# This procedure try to find a large prime using Lucas' test.\n" } {MPLTEXT 1 0 62 "# The search goes for n,n+1,n+2,... between numbers n *k^m+1.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 69 "largewithlucas:=proc(n::posint,k::posint,m::posint) local i,a,aa,f ;\n" }{MPLTEXT 1 0 58 "if k<2 then ERROR(`second parameter is too smal l`,k) fi;\n" }{MPLTEXT 1 0 17 "for i from n do\n" }{MPLTEXT 1 0 12 " \+ f:=FAIL;\n" }{MPLTEXT 1 0 32 " for a from 2 while f=FAIL do\n" } {MPLTEXT 1 0 35 " f:=speclucas(i,k,m,a); aa:=a;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 24 " print(i*k^m+1,aa,f);\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%'I\"nG6\"I'posintG%*pro tectedG'I\"kGF&F''I\"mGF&F'6&I\"iGF&I\"aGF&I#aaGF&I\"fGF&F&F&C$@$2F*\" \"#-I&ERRORGF(6$I>second~parameter~is~too~smallGF&F*?(F.F%\"\"\"F&I%tr ueGF(C%>F1I%FAILGF(?(F/F5F;F&/F1F?C$>F1-I*speclucasGF&6&F.F*F,F/>F0F/- I&printGF(6%,&*&F.F;)F*F,F;F;F;F;F0F1F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "debug(largewithlucas); debug(speclucas); largewith lucas(1,2,16);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I/largewithlucasG6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "I*speclucasG6\"" }}{PARA 9 "" 1 "" {TEXT 207 43 "\{--> enter largewithlucas, args = 1, 2, 16" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter speclucas, args = 1, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"&Pb'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }} {PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithluca s) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 41 " \{--> enter speclucas, args = 1, 2, 16, 3" }}{PARA 11 "" 1 "" {XPPMATH 20 "<\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"&Pb'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = true\}" }} {PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"&Pb'\"\"$I%tru eG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" } }{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter speclucas, args = 2, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'t58" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in largewithlucas) = f alse\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'t5 8\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*p rotectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter speclucas, args = 3, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'4m >" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in largewit hlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protected G" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'4m>\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter spec lucas, args = 4, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'X@E" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in la rgewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*pro tectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'X@E\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{-- > enter speclucas, args = 5, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'\"oF$" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit s peclucas (now in largewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'\"oF$\"\"#I&falseG%*protecte dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter speclucas, args = 6, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 " <$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"' enter speclucas, args = 7, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'`(e%" }} {PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in largewithluca s) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 %\"'`(e%\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%F AILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter specluca s, args = 8, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'*GC&" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in l argewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*pr otectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'*GC&\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{-- > enter speclucas, args = 9, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'D)*e" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit sp eclucas (now in largewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'D)*e\"\"#I&falseG%*protected G" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 10, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 " <$\"\"#\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'h`l" }}{PARA 9 "" 1 " " {TEXT 207 52 "<-- exit speclucas (now in largewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'h`l\"\"#I& falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protected G" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 11, 2 , 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'(*3s" }} {PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in largewithluca s) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 %\"'(*3s\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%F AILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter specluca s, args = 12, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = FAI L\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 12, 2, 16, 3" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\" \"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }} {PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithluca s) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 9 "" 1 "" {TEXT 207 42 " \{--> enter speclucas, args = 12, 2, 16, 4" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\" $" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%F AILG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 12, 2, 16, 5" }} {PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"$" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in larg ewithlucas) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protect edG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 12, 2, 16, 6" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\" \"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%F AILG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"'" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 12, 2, 16, 7" }} {PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 51 "< -- exit speclucas (now in largewithlucas) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"(" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 12, 2, 16, 8" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lk y" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\")" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 12, 2, 16, 9" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"'Lky" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = FAIL\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"*" }}{PARA 9 "" 1 "" {TEXT 207 43 "\{--> enter speclu cas, args = 12, 2, 16, 10" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\" $" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'Lky" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%* protectedG" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit speclucas (now in largewithlucas) = true\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*pr otectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'Lky\"#5I%trueG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{-- > enter speclucas, args = 13, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'p>&)" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit spe clucas (now in largewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6%\"'p>&)\"\"#I&falseG%*protectedG" }} {PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 14, 2, 16, 2" }}{PARA 11 " " 1 "" {XPPMATH 20 "<$\"\"#\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\" \"#\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'0v\"*" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in largewithlucas) = false\}" }} {PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'0v\"*\"\"#I& falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protected G" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 15, 2 , 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"$\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "<%\"\"#\"\"$\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" 'TI)*" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in larg ewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*prote ctedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'TI)*\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{-- > enter speclucas, args = 16, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(x&[5" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclu cas (now in largewithlucas) = false\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(x&[5\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }}{PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 17, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"#<" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"(8T6\"" }}{PARA 9 "" 1 "" {TEXT 207 52 "<-- exit speclucas (now in largewithlucas) = false\}" }}{PARA 11 " " 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(8T6\"\"\"#I&falseG%*pr otectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%FAILG%*protectedG" }} {PARA 9 "" 1 "" {TEXT 207 42 "\{--> enter speclucas, args = 18, 2, 16, 2" }}{PARA 11 "" 1 "" {XPPMATH 20 "<$\"\"#\"\"$" }}{PARA 9 "" 1 "" {TEXT 207 64 "<-- ERROR in speclucas (now in largewithlucas) = interru pted\}\n" }{TEXT 207 62 "<-- ERROR in largewithlucas (now at top level ) = interrupted\}" }}{PARA 7 "" 1 "" {TEXT 208 33 "Warning, computati on interrupted" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.30. Felada t." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "3.31. P" }{TEXT 206 8 "\303\251" }{TEXT 206 10 "pin-teszt." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 36 "# This procedure do the Pepin test\n" } {MPLTEXT 1 0 36 "# for the Fermat number 2^(2^m)+1.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 36 "pepin:=proc(m::nonnegin t) local N;\n" }{MPLTEXT 1 0 30 "if m=0 then RETURN(true) fi;\n" } {MPLTEXT 1 0 15 "N:=2^(2^m)+1;\n" }{MPLTEXT 1 0 51 "if modp(3&^((N-1)/ 2),N)=N-1 then RETURN(true) fi;\n" }{MPLTEXT 1 0 10 "false end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6#'I\"mG6\"I*nonnegintG%*protectedG6#I \"NGF&F&F&C&@$/F%\"\"!-I'RETURNGF(6#I%trueGF(>F*,&)\"\"#)F6F%\"\"\"F8F 8@$/-I%modpGF(6$-I#&^GF&6$\"\"$,&*&#F8F6F8F*F8F8FD!\"\"F*,&F*F8F8FEF/I &falseGF(F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "pepin(4) ; pepin(5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*protectedG" }} {PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.32. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 31 "3.32. Pocklington-Lehmer-t eszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 49 "# This procedure do the Lehmer- Pocklington test\n" }{MPLTEXT 1 0 53 "# for the number n using the sub set S of factors of\n" }{MPLTEXT 1 0 51 "# n-1 and base a. Returns wit h the reduced set S.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 35 "LPtest:=proc(n,S,a) local p,newS;\n" }{MPLTEXT 1 0 57 "if n<=a then ERROR(`last parameter is too large`,a) fi;\n" } {MPLTEXT 1 0 39 "if igcd(a,n)>1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 47 "if modp(a&^(n-1),n)<>1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 10 "newS:=S;\n" }{MPLTEXT 1 0 15 "for p in S do\n" }{MPLTEXT 1 0 70 " \+ if igcd(modp(a&^((n-1)/p),n)-1,n)=1 then newS:=newS minus \{p\} fi\n" }{MPLTEXT 1 0 22 "od; newS; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"nG6\"I\"SGF%I\"aGF%6$I\"pGF%I%newSGF%F%F%C(@$1F$F' -I&ERRORG%*protectedG6$IF*F&?&F)F&I%trueGF0@$/-F76$,&-F@6$-FC6$F'*&FEF5F)FFF$F5F5 FFF$F5>F*-I&minusGF06$F*<#F)F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 50 "# This procedure try to find a \+ large prime using\n" }{MPLTEXT 1 0 67 "# Lehmer-Pocklington test. The \+ search goes for n,n+1,... between \n" }{MPLTEXT 1 0 20 "# numbers n*k^ m+1.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 45 "l argewithLP:=proc(n,k,m) local i,a,aa,S,S0;\n" }{MPLTEXT 1 0 58 "if k<2 then ERROR(`second parameter is too small`,k) fi;\n" }{MPLTEXT 1 0 19 "S0:=factorset(k);\n" }{MPLTEXT 1 0 17 "for i from n do\n" } {MPLTEXT 1 0 58 " if n<=k^m then S:=S0 else S:=S0 union factorset(i) \+ fi;\n" }{MPLTEXT 1 0 46 " for a from 2 while S<>\{\} and S<>false do \n" }{MPLTEXT 1 0 29 " S:=LPtest(i*k^m+1,S,a);\n" }{MPLTEXT 1 0 12 " aa:=a;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 19 " if S=fals e then\n" }{MPLTEXT 1 0 29 " print(i*k^m+1,aa,false)\n" }{MPLTEXT 1 0 8 " else\n" }{MPLTEXT 1 0 28 " print(i*k^m+1,aa,true)\n" } {MPLTEXT 1 0 6 " fi\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"nG6\"I\"kGF%I\"mGF%6'I\"iGF%I\"aGF%I#aaGF%I\"SGF%I #S0GF%F%F%C%@$2F&\"\"#-I&ERRORG%*protectedG6$I>second~parameter~is~too ~smallGF%F&>F--_I*numtheoryG6$F4I(_syslibGF%I*factorsetGF%6#F&?(F)F$\" \"\"F%I%trueGF4C%@%1F$)F&F'>F,F->F,-I&unionGF46$F--F96#F)?(F*F1F@F%30F ,<\"0F,I&falseGF4C$>F,-I'LPtestGF%6%,&*&F)F@FEF@F@F@F@F,F*>F+F*@%/F,FR -I&printGF46%FXF+FR-Fhn6%FXF+FAF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "debug(largewithLP); largewithLP(1,2,16);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I,largewithLPG6\"" }}{PARA 9 "" 1 "" {TEXT 207 40 "\{--> enter largewithLP, args = 1, 2, 16" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"&Pb'\"\"$I%tru eG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'t58\"\"#I&falseG%*prot ectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'4m>\"\"#I&falseG%*protectedG " }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'X@E\"\"#I&falseG%*protectedG " }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'\"oF$\"\"#I&falseG%*protecte dG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'&)\"\"#I&f alseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'0v\"*\"\"#I&f alseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"'TI)*\"\"#I&fa lseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(x&[5\"\"#I&fa lseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(8T6\"\"\"#I&f alseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"# " }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"* " }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "< #\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#9" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#:" } }{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "<\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6% \"(\\'z6\"#>I%trueG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\" \"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(&=X7 \"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(@2J\"\"\"#I& falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"# " }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "<\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 %\"(diP\"\"\"&I%trueG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<# \"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"($z T9\"\"#I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(Ht]\"\"\"# I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(lGd\"\"\"#I& falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(,%Q;\"\"#I&fa lseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%\"(PRq\"\"\"#I&f alseG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "<#\"\"#" }}{PARA 9 "" 1 "" {TEXT 207 59 "<-- ERROR in largewithLP (now at top level) = interrupte d\}" }}{PARA 7 "" 1 "" {TEXT 208 33 "Warning, computation interrupted " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 59 "# This procedure try to find factors of n having the form\n" }{MPLTEXT 1 0 51 "# a*k+b from k=1 until K or the square root of n.\n" }{MPLTEXT 1 0 57 "# Note that LPtest capable to prove that factors n have\n" } {MPLTEXT 1 0 58 "# the form f*k+1, where f is the factorised part of n -1,\n" }{MPLTEXT 1 0 50 "# and a test treated later capable to prove t hat\n" }{MPLTEXT 1 0 56 "# factors have the form f*k+1 or f*k-1, where f is the\n" }{MPLTEXT 1 0 27 "# factorised part of n+1.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 60 "tryfactors:=proc(a: :posint,b::integer,n::posint,K::posint)\n" }{MPLTEXT 1 0 15 "local nn, i,f;\n" }{MPLTEXT 1 0 58 "if a=1 then error \"first parameter is too s mall\",a fi;\n" }{MPLTEXT 1 0 62 "if b<=1-a then error \"second parame ter is too small\",b fi;\n" }{MPLTEXT 1 0 15 "f:=[]; nn:=n;\n" } {MPLTEXT 1 0 35 "for i to K while (i*a+b)^2<=nn do\n" }{MPLTEXT 1 0 29 " if modp(nn,i*a+b)=0 then \n" }{MPLTEXT 1 0 23 " f:=[op(f),i*a +b];\n" }{MPLTEXT 1 0 21 " nn:=nn/(i*a+b);\n" }{MPLTEXT 1 0 13 " \+ i:=i-1;\n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 18 "od; f \+ end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&'I\"aG6\"I'posintG%*protecte dG'I\"bGF&I(integerGF('I\"nGF&F''I\"KGF&F'6%I#nnGF&I\"iGF&I\"fGF&F&F&C (@$/F%\"\"\"Y6$Q=first~parameter~is~too~smallF&F%@$1F*,&F7F7F%!\"\"Y6$ Q>second~parameter~is~too~smallF&F*>F37\">F1F-?(F2F7F7F/1*$),&*&F%F7F2 F7F7F*F7\"\"#F7F1@$/-I%modpGF(6$F1FI\"\"!C%>F37$-I#opGF(6#F3FI>F1*&F1F 7FIF>>F2,&F2F7F7F>F3F&F&F&" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 " 3.34. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.35. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" } }}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 18 "3.36. Proth-teszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 14 "3.37. \+ Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 62 "# This procedure do the Proth t est for the number n=h*2^m+1.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 59 "proth:=proc(h::posint,m::posint) local a,b,n; n:=h*2^m+1;\n" } {MPLTEXT 1 0 60 "if h>=2^m then error \"first parmeter is too large\", h fi;\n" }{MPLTEXT 1 0 69 "if not type(h,odd) then error \"first param eter must be odd\",h fi;\n" }{MPLTEXT 1 0 36 "if m=1 or m=2 then retur n true fi;\n" }{MPLTEXT 1 0 62 "if m=3 then if h=5 then return true el se return false fi fi;\n" }{MPLTEXT 1 0 55 "# 2 is not a quadratic res idue mod n, we start with 3\n" }{MPLTEXT 1 0 50 "# (2*a|n)=(a|n), henc e enough to try odd bases a\n" }{MPLTEXT 1 0 22 "for a from 3 by 2 do \n" }{MPLTEXT 1 0 35 " b:=2&^m mod a; b:=h*b+1 mod a; \n" }{MPLTEXT 1 0 49 " # by quadratic reciprocity, (a|n)=(n|a)=(b|a)\n" }{MPLTEXT 1 0 38 " b:=modp(2&^m,a); b:=modp(h*b+1,a);\n" }{MPLTEXT 1 0 42 " if jacobi(b,a)=0 then return false fi;\n" }{MPLTEXT 1 0 26 " if jacobi( b,a)=-1 then\n" }{MPLTEXT 1 0 72 " if modp(a&^((n-1)/2),n)=n-1 then return true else return false fi;\n" }{MPLTEXT 1 0 7 " fi;\n" } {MPLTEXT 1 0 9 "od end;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"hG6 \"I'posintG%*protectedG'I\"mGF&F'6%I\"aGF&I\"bGF&I\"nGF&F&F&C(>F.,&*&F %\"\"\")\"\"#F*F3F3F3F3@$1F4F%Y6$QF--I$modGF&6 $-I#&^GF&6$F5F*F,>F--FV6$,&*&F%F3F-F3F3F3F3F,>F--I%modpGF(FW>F--F\\oFg n@$/-_I*numtheoryG6$F(I(_syslibGF&I'jacobiGF&6$F-F,\"\"!FP@$/Fao!\"\"@ %/-F\\o6$-FY6$F,,&*&#F3F5F3F.F3F3FdpF[pF.,&F.F3F3F[pFHFPF&F&F&" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "proth(11,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I%trueG%*protectedG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "ifactor(11*2^5+1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "- I!G6\"6#\"$`$" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "3.38. T" } {TEXT 206 8 "\303\251" }{TEXT 206 4 "tel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 54 "# This test may be used if n-1=FR, where the factors\n" } {MPLTEXT 1 0 58 "# of F are known, and there is given a bound B such t hat\n" }{MPLTEXT 1 0 60 "# R has no primedivisor less then B, and FB>s qrt(N). First\n" }{MPLTEXT 1 0 53 "# we have to use the Lehmer - Pockl ington test with\n" }{MPLTEXT 1 0 59 "# the set of divisors of F. Afte r this the second step is\n" }{MPLTEXT 1 0 39 "# to find an appropriat e base a to R.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 3 " \n" } {MPLTEXT 1 0 45 "PLtestsecondstep:=proc(n,F,a) local p,newS;\n" } {MPLTEXT 1 0 57 "if n<=a then ERROR(`last parameter is too large`,a) f i;\n" }{MPLTEXT 1 0 39 "if igcd(a,n)>1 then RETURN(false) fi;\n" } {MPLTEXT 1 0 47 "if modp(a&^(n-1),n)<>1 then RETURN(false) fi;\n" } {MPLTEXT 1 0 51 "if igcd(modp(a&^F-1,n),n)=1 then RETURN(true) fi;\n" }{MPLTEXT 1 0 17 "FAIL end; " }}{PARA 11 "" 1 "" {XPPMATH 20 "f *6%I\"nG6\"I\"FGF%I\"aGF%6$I\"pGF%I%newSGF%F%F%C'@$1F$F'-I&ERRORG%*pro tectedG6$I " 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 }