{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\"I'posintG%*protect edG6%I\"iGF&I\"rGF&I\"mGF&F&F&C'>F+\"\"\">F,*$)F%\"\"#F/?(F*F3F/,&F%F/ F/!\"\"I%trueGF(>F+-I$modGF&6$*&F+F/F*F/F,>F+-F:6$,&F+F/F/F/F,7$-I%ire mGF(6$F+F%-I%iquoGF(FDF&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 "# limit.\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:=wilsontest(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] fi\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\"r GF%I\"pGF%I\"wGF%F%F%C&>F)7\">F*F-?(F'\"\"#\"\"\"F$I%trueG%*protectedG C$>F(-I+wilsontestGF%6#F'@$/&F(6#F1\"\"!C$>F)7$-I#opGF36#F)F'@$/&F(6#F 0F=>F*7$-FB6#F*F'7$F*F)F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "wilson(1000);" }}{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-\"" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "3.5. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "3.6. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "3.7. Feladat. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{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 "tele." }} {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 reciproc it" }{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 40 "\{--> enter jacobisymbol, args = 131, 19" }}{PARA 9 "" 1 "" {TEXT 207 41 "\{--> enter jacobisym bol, args = 17, 19\n" }{TEXT 207 41 "\{--> enter jacobisymbol, args = \+ 19, 17\n" }{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 jacobisy mbol (now in jacobisymbol) = 1\}\n" }{TEXT 207 49 "<-- exit jacobisymb ol (now in jacobisymbol) = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}{PARA 9 "" 1 "" {TEXT 207 51 "<-- exit jacobisymbol (now in jacobis ymbol) = 1\}\n" }{TEXT 207 51 "<-- exit jacobisymbol (now in jacobisym bol) = 1\}\n" }{TEXT 207 46 "<-- exit jacobisymbol (now at top level) \+ = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"\"" }}}}{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\"bGF&-F(6$I*nonnegintGF+F,6%I#b2GF&I\"qGF&I\"sGF&6#IaoC opyright~(c)~1992~by~the~University~of~Waterloo.~All~rights~reserved.G F&F&C$@&0%&nargsG\"\"#Y6$QBexpecting~2~arguments,~but~got~%1F&F>43-I%t ypeGF+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%F6 F?F^oFXC$F_o>F8-I+jacobi_auxGF&6$F?-I$absGF+6#F%>F8Fin@$32F%FX/-FV6$F6 F]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%*pr otectedG-I$NotGF&6#I)constantGF+'I\"pGF&-F(6$I&primeGF&F,F&6#IinCopyri ght~(c)~1994~by~Waterloo~Maple~Inc.~All~rights~reserved.GF&F&@'0%&narg sG\"\"#Y6$QBexpecting~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-.%)procname G6#%%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 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.23. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 25 "3.24. Mill er-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 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 58 "if b<2 then ERROR(`sec ond parameter is too small`,b) fi;\n" }{MPLTEXT 1 0 59 "if n<=b then E RROR(`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 od; \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) od ;\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 33 "# This procedure do Lucas' test\n" }{MPLTEXT 1 0 37 "# for the n umber 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 "naivelucas test:=proc(n,a) local m;\n" }{MPLTEXT 1 0 39 "if igcd(a,n)>1 then RETU RN(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 "o d; 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'RETURNGF/6#I&falseGF/@ $0-I%modpGF/6$-I#&^GF%6$F&,&F$F,F,!\"\"F$F,F1?(F(\"\"#F,,&F$F,F@F>I%tr ueGF/@$/-F86$-F;6$F&F(F$F,F1FBF%F%F%" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.30. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {SECT 1 {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 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.32. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 31 "3.33. Pocklington-L ehmer-teszt." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{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 62 "proth:=proc(h::posint,m::pos int) local a,b,n,ad; n:=h*2^m+1;\n" }{MPLTEXT 1 0 53 " if h>=2^m or n ot type(h,odd) then return FAIL fi;\n" }{MPLTEXT 1 0 38 " if m=1 or m =2 then return true fi;\n" }{MPLTEXT 1 0 57 " # 2 is not a quadratic \+ residue mod n, we start with 3\n" }{MPLTEXT 1 0 41 " a:=3; b:=2&^m mo d a; b:=h*b+1 mod a; \n" }{MPLTEXT 1 0 49 " # by quadratic reciprocit y, (a|n)=(n|a)=(b|a)\n" }{MPLTEXT 1 0 42 " if jacobi(b,a)=0 then retu rn false fi;\n" }{MPLTEXT 1 0 26 " if jacobi(b,a)=-1 then\n" } {MPLTEXT 1 0 70 " if a&^((n-1)/2) mod n=n-1 then return true else r eturn false fi;\n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 68 " # we \+ shall use the quasi-prime sequence 5,7,11,13,17,19,23,25,..\n" } {MPLTEXT 1 0 55 " # a random base would give only two trials in mean, \n" }{MPLTEXT 1 0 32 " # and this looks even better\n" }{MPLTEXT 1 0 16 " a:=5; ad:=2;\n" }{MPLTEXT 1 0 17 " while true do\n" }{MPLTEXT 1 0 36 " b:=2&^m mod a; b:=h*b+1 mod a;\n" }{MPLTEXT 1 0 44 " if jacobi(b,a)=0 then return false fi;\n" }{MPLTEXT 1 0 28 " if jacob i(b,a)=-1 then\n" }{MPLTEXT 1 0 72 " if a&^((n-1)/2) mod n=n-1 th en return true else return false fi;\n" }{MPLTEXT 1 0 9 " fi;\n" } {MPLTEXT 1 0 24 " a:=a+ad; ad:=6-ad;\n" }{MPLTEXT 1 0 7 " od;\n" } {MPLTEXT 1 0 6 "end;\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"hG6\"I 'posintG%*protectedG'I\"mGF&F'6&I\"aGF&I\"bGF&I\"nGF&I#adGF&F&F&C->F., &*&F%\"\"\")\"\"#F*F4F4F4F4@$51F5F%4-I%typeGF(6$F%I$oddGF(OI%FAILGF(@$ 5/F*F4/F*F6OI%trueGF(>F,\"\"$>F--I$modGF&6$-I#&^GF&6$F6F*F,>F--FK6$,&* &F%F4F-F4F4F4F4F,@$/-_I*numtheoryG6$F(I(_syslibGF&I'jacobiGF&6$F-F,\" \"!OI&falseGF(@$/FW!\"\"@%/-FK6$-FN6$F,,&*&#F4F6F4F.F4F4FfoF]oF.,&F.F4 F4F]oFEFin>F,\"\"&>F/F6?(F&F4F4F&FFC(FIFPFUF[o>F,,&F,F4F/F4>F/,&\"\"'F 4F/F]oF&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 1 {PARA 4 "" 0 "" {TEXT 206 7 "3.38. T" }{TEXT 206 8 "\303\251" }{TEXT 206 4 "tel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "3.39. \+ Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}}{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\303\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 Fourier-transzf orm\303\241ci\303\263" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 38 "8. Elliptikus f\303\274ggv\303\251nyek" }}{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\251ken" }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 65 "10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 55 "11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel" }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 37 "12. Polinomfaktoriz\303\241l\303\241s" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "13. A szita m\303\26 3dszerek alapjai" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "14. Az AKS teszt" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{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 }