{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 "Courier" 1 12 255 0 0 1 2 2 2 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 206 1 {CSTYLE "" -1 -1 "Times" 1 12 255 0 0 1 2 1 2 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 203 66 "Sz\303\241m\303\255t\303 \263g\303\251pes sz\303\241melm\303\251let" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 18 "J\303\241rai Antal" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 68 "Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\2 41lnak" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "1. A pr\303\255mek el oszl\303\241sa, szit\303\241l\303\241s" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 63 "2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263 dszerek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 64 "3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\26 3dszerek" }}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 18 "4. Lucas-sorozatok" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 23 "5. Alkalmaz\30 3\241sok " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "6. Sz\303\241mok \303\251s polinomok" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 45 "7. Gyors Four ier-transzform\303\241ci\303\263" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {SECT 1 {PARA 3 "" 0 "" {TEXT 205 38 "8. Elliptikus f\303\274ggv\303\2 51nyek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251 ken" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 65 "10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251 kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 55 "11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel" }}{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)divisor sGF$I)factorEQGF$I*factorsetGF$I'fermatGF$I)imagunitGF$I&indexGF$I/int egral_basisGF$I)invcfracGF$I'invphiGF$I*issqrfreeGF$I'jacobiGF$I*krone ckerGF$I'lambdaGF$I)legendreGF$I)mcombineGF$I)mersenneGF$I(migcdexGF$I *minkowskiGF$I(mipolysGF$I%mlogGF$I'mobiusGF$I&mrootGF$I&msqrtGF$I)nea restpGF$I*nthconverGF$I)nthdenomGF$I)nthnumerGF$I'nthpowGF$I&orderG%*p rotectedGI)pdexpandGF$I$phiGF$I#piGF$I*pprimrootGF$I)primrootGF$I(quad resGF$I+rootsunityGF$I*safeprimeGF$I&sigmaGF$I*sq2factorGF$I(sum2sqrGF $I$tauGF$I%thueGF$" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "11.1. T" } {TEXT 206 12 "\303\251tel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This routin e randomly choose an elliptic \"curve\" modulo n,\n" }{MPLTEXT 1 0 53 "# where gcd(n,6)=1. The coordinates x,y are choosen\n" }{MPLTEXT 1 0 55 "# randomly, the parameter a too, and b is calculated.\n" }{MPLTEXT 1 0 57 "# The list [x,y,a,b] is given back or a divisor d of n.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 39 "ellrand:=p roc(n) local x,y,a,b,r,d,f;\n" }{MPLTEXT 1 0 19 "r:=rand(n); d:=n;\n" }{MPLTEXT 1 0 14 "while d=n do\n" }{MPLTEXT 1 0 52 " x:=r(n); y:=r(n) ; a:=r(n); b:=y^2-x^3-a*x mod n;\n" }{MPLTEXT 1 0 36 " d:=4*a^3+27*b^ 2 mod n; gcd(d,n);\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 34 "if %1 then return % fi;\n" }{MPLTEXT 1 0 15 "[x,y,a,b]; end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6)I\"xGF%I\"yGF%I\"aGF%I\"bG F%I\"rGF%I\"dGF%I\"fGF%F%F%C'>F+-I%randGF%F#>F,F$?(F%\"\"\"F4F%/F,F$C( >F'-F+F#>F(F8>F)F8>F*-I$modGF%6$,(*$)F(\"\"#F4F4*$)F'\"\"$F4!\"\"*&F)F 4F'F4FFF$>F,-F=6$,&*&\"\"%F4)F)FEF4F4*&\"#FF4)F*FBF4F4F$-I$gcdGF%6$F,F $@$32I\"%GF%F$2F4FXOFX7&F'F(F)F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 65 "# Addition on an elliptic \"cur ve\" modulo n, where gcd(n,6)=1.\n" }{MPLTEXT 1 0 61 "# P and Q are th e points to add and a,b are the parameters.\n" }{MPLTEXT 1 0 66 "# The return value is the sum of the points or a divisor d of n.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 36 "elladd:=pr oc(P,Q,a,b,n) local l,d;\n" }{MPLTEXT 1 0 29 "if P[3]=0 then return Q \+ fi;\n" }{MPLTEXT 1 0 29 "if Q[3]=0 then return P fi;\n" }{MPLTEXT 1 0 40 "if P=Q then return elldou(P,a,b,n) fi;\n" }{MPLTEXT 1 0 38 "if P[1 ]=Q[1] then return [0,1,0] fi;\n" }{MPLTEXT 1 0 29 "d:=igcdex(P[1]-Q[1 ],n,'l');\n" }{MPLTEXT 1 0 34 "if 1F ,-I'igcdexGF%6%,&FAFCFD!\"\"F).F+@$32FCF,2F,F)OF,>F+-I$modGF%6$*&,&&F$ 6#\"\"#FC&F&FZFLFCF+FCF)-FU6$,(*$)F+FenFCFCFAFLFDFLF)7%I\"%GF%-FU6$,&* &F+FC,&FAFCF]oFLFCFCFYFLF)FCF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 65 "# Doubling on an elliptic \"cur ve\" modulo n, where gcd(n,6)=1.\n" }{MPLTEXT 1 0 57 "# P is the point to double and a, b are the parameters.\n" }{MPLTEXT 1 0 52 "# The ret urn value is the double of the point P or\n" }{MPLTEXT 1 0 21 "# a div isor d of n.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 34 "elldou:=proc(P,a,b,n) local l,d;\n" }{MPLTEXT 1 0 29 "if P[3]= 0 then return P fi;\n" }{MPLTEXT 1 0 35 "if P[2]=0 then return [0,1,0] fi;\n" }{MPLTEXT 1 0 26 "d:=igcdex(2*P[2],n,'l');\n" }{MPLTEXT 1 0 34 "if 1F+-I'igcdexGF% 6%,$*&F8F;F6F;F;F(.F*@$32F;F+2F+F(OF+>F*-I$modGF%6$*&,&*&F1F;)&F$6#F;F 8F;F;F&F;F;F*F;F(-FJ6$,&*$)F*F8F;F;*&F8F;FPF;!\"\"F(7%I\"%GF%-FJ6$,&*& F*F;,&FPF;FZFXF;F;F6FXF(F;F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 52 "# This program compute k*P, k>=0 or a d ivisor of n\n" }{MPLTEXT 1 0 56 "# on an elliptic \"curve\" modulo n, \+ where gcd(n,6)=1.\n" }{MPLTEXT 1 0 43 "# It use the left-to-right bina ry method.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 38 "ellmul:=proc(P,k,a,b,n) local L,i,Q;\n" }{MPLTEXT 1 0 32 "if k=0 then return [0,1,0] fi;\n" }{MPLTEXT 1 0 29 "if P[3]=0 then return P \+ fi;\n" }{MPLTEXT 1 0 23 "L:=convert(k,base,2);\n" }{MPLTEXT 1 0 7 "Q:= P;\n" }{MPLTEXT 1 0 36 "for i from nops(L)-1 to 1 by -1 do\n" } {MPLTEXT 1 0 23 " Q:=elldou(Q,a,b,n);\n" }{MPLTEXT 1 0 40 " if type( Q,integer) then return Q fi;\n" }{MPLTEXT 1 0 18 " if L[i]=1 then\n" }{MPLTEXT 1 0 27 " Q:=elladd(P,Q,a,b,n);\n" }{MPLTEXT 1 0 42 " i f type(Q,integer) then return Q fi;\n" }{MPLTEXT 1 0 7 " fi;\n" } {MPLTEXT 1 0 11 "od; Q; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"P G6\"I\"kGF%I\"aGF%I\"bGF%I\"nGF%6%I\"LGF%I\"iGF%I\"QGF%F%F%C(@$/F&\"\" !O7%F1\"\"\"F1@$/&F$6#\"\"$F1OF$>F+-I(convertG%*protectedG6%F&I%baseGF %\"\"#>F-F$?(F,,&-I%nopsGF>6#F+F4F4!\"\"FHF4I%trueGF>C%>F--I'elldouGF% 6&F-F'F(F)@$-I%typeGF>6$F-I(integerGF>OF-@$/&F+6#F,F4C$>F--I'elladdGF% 6'F$F-F'F(F)FOF-F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "# \n" }{MPLTEXT 1 0 61 "# This brute force procedure calculate the numbe r of points\n" }{MPLTEXT 1 0 55 "# on an elliptic curve modulo p>3, a \+ prime. The curve\n" }{MPLTEXT 1 0 25 "# parameters are a, b. \n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 34 "ellcount:= proc(a,b,p) local x,c;\n" }{MPLTEXT 1 0 7 "c:=1;\n" }{MPLTEXT 1 0 67 " for x from 0 to p-1 do c:=c+numtheory[jacobi](x^3+a*x+b,p)+1; od;\n" } {MPLTEXT 1 0 7 "c; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"aG6\"I \"bGF%I\"pGF%6$I\"xGF%I\"cGF%F%F%C%>F*\"\"\"?(F)\"\"!F-,&F'F-F-!\"\"I% trueG%*protectedG>F*,(F*F--&I*numtheoryG6$F3I(_syslibGF%6#_F8I'jacobiG F%6$,(*$)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 60 "n:=nextprime(1008); E:=ellrand(n); m:=ell count(E[3],E[4],n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%45" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$`%\"#w\"$@'\"$A%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%Z5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "n:=10 09; E := [889, 300, 991, 649]; m := 974;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%45" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$*))\"$+$\"$\"**\"$\\'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$u*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "ifactor(974); ellmul([E[1],E[2],1],m,E[3],E[4],n);\n" }{MPLTEXT 1 0 34 "elldou([E[1],E[2],1],E[3],E[4],n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*&-I!G6\"6#\"\"#\"\"\"-F$6#\"$([F(" }}{PARA 11 "" 1 " " {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$e (\"$C)\"\"\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "11.2. T" }{TEXT 206 12 "\303\251tel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 52 "# This brute \+ force procedure calculate the high of\n" }{MPLTEXT 1 0 52 "# an ellipt ic curve modulo p>3, a prime. The curve\n" }{MPLTEXT 1 0 25 "# paramet ers are a, b. \n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 39 "ellhigh:=proc(a,b,p) local x,y,h,i,P;\n" }{MPLTEXT 1 0 7 "h:= 1;\n" }{MPLTEXT 1 0 24 "for x from 0 to p-1 do\n" }{MPLTEXT 1 0 26 " \+ y:=msqrt(x^3+a*x+b,p);\n" }{MPLTEXT 1 0 27 " if y=FAIL then next fi; \n" }{MPLTEXT 1 0 15 " P:=[x,y,1];\n" }{MPLTEXT 1 0 19 " for i from \+ 2 do\n" }{MPLTEXT 1 0 8 " i;\n" }{MPLTEXT 1 0 33 " P:=elladd(P,[ x,y,1],a,b,p);\n" }{MPLTEXT 1 0 23 " if P=[0,1,0] then\n" }{MPLTEXT 1 0 35 " if i>h then h:=i fi; break;\n" }{MPLTEXT 1 0 9 " fi; \n" }{MPLTEXT 1 0 33 " od; if 3*h>2*p then break fi;\n" }{MPLTEXT 1 0 11 "od; h; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"aG6\"I\"bGF% I\"pGF%6'I\"xGF%I\"yGF%I\"hGF%I\"iGF%I\"PGF%F%F%C%>F+\"\"\"?(F)\"\"!F0 ,&F'F0F0!\"\"I%trueG%*protectedGC'>F*-_I*numtheoryG6$F6I(_syslibGF%I&m sqrtGF%6$,(*$)F)\"\"$F0F0*&F$F0F)F0F0F&F0F'@$/F*I%FAILGF6\\>F-7%F)F*F0 ?(F,\"\"#F0F%F5C%F,>F--I'elladdGF%6'F-FJF$F&F'@$/F-7%F2F0F2C$@$2F+F,>F +F,[@$2,$*&FLF0F'F0F0,$*&FCF0F+F0F0FYF+F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ellrand(97);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7& \"#e\"#:\"\"!\"#$)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "ellhi gh(5,57,97); ellhigh(95,78,97);\n" }{MPLTEXT 1 0 39 "ellhigh(33,96,97) ; ellhigh(55,51,97);\n" }{MPLTEXT 1 0 38 "ellhigh(24,13,97);ellhigh(59 ,39,97);\n" }{MPLTEXT 1 0 38 "ellhigh(49,54,97);ellhigh(45,68,97);\n" }{MPLTEXT 1 0 35 "ellhigh(76,30,97);ellhigh(0,83,97);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$.\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#!)" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$;\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"#W" }}{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 "\"$-\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"$.\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 10 "11.3. A pr" }{TEXT 206 8 "\303\255" }{TEXT 206 10 "mtesz tek v" }{TEXT 206 13 "\303\241zlata" }{TEXT 206 1 "." }}{PARA 0 "" 0 " " {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "n:=1009; \+ E:=ellrand(n); m:=ellcount(E[3],E[4],n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%45" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#Q\"$.'\"$#e\"#l" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$g*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "E:=[889,300,991,649]; m:=974;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$*))\"$+$\"$\"**\"$\\'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$u*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "ifactor(m); el lmul([E[1],E[2],1],m,E[3],E[4],n);\n" }{MPLTEXT 1 0 34 "elldou([E[1],E [2],1],E[3],E[4],n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*&-I!G6\"6#\"\"# \"\"\"-F$6#\"$([F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" } }{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$e(\"$C)\"\"\"" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 55 "n1:=487; E1:=ellrand(n1); m1:=ellcount(E1[3] ,E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$([" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$a\"\"$\"[\"#r\"#_" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$l%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "E1:=[201,473,457,1 9]; m1:=530;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$,#\"$t%\"$d%\"#>" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"$I&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3],E1[4],n1 );\n" }{MPLTEXT 1 0 42 "ellmul([E1[1],E1[2],1],10,E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\"-F$6#\"\"&F(-F$6# \"#`F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$+%\"$a%\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n2:=53;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#`" }}}} {SECT 0 {PARA 4 "" 0 "" {TEXT 206 32 "11.4. A Goldwasser-Kilian-teszt. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "n:=1009; E:=ellrand(n); m:=ellcount(E[3],E[4],n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%45" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$F'\" $](\"$H\"\"#y" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%75" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "E:=[889,300,991,649]; m:=974;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$*))\"$+$\"$\"**\"$\\'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$u*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "ifact or(m); ellmul([E[1],E[2],1],m,E[3],E[4],n);\n" }{MPLTEXT 1 0 34 "elldo u([E[1],E[2],1],E[3],E[4],n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*&-I!G6 \"6#\"\"#\"\"\"-F$6#\"$([F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\" \"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$e(\"$C)\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "n1:=487; E1:=ellrand(n1); m1:=ellco unt(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$([" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#s\"$S$\"$'H\"#\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$?&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "E1:=[ 201,473,457,19]; m1:=530;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$,#\"$t %\"$d%\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$I&" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3] ,E1[4],n1);\n" }{MPLTEXT 1 0 39 "elldou([E1[1],E1[2],1],E1[3],E1[4],n1 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\"-F$6#\"\"&F( -F$6#\"#`F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"#o\"$)>\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "n2:=265; E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n 2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$l#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$I#\"$f#\"$r\"\"$O\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$m#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "E2:=[230,259,171, 136]; m2:=266;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$I#\"$f#\"$r\"\"$O \"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$m#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m2); ellmul([E2[1],E2[2],1],m2,E2[3],E2[4],n 2);\n" }{MPLTEXT 1 0 39 "elldou([E2[1],E2[2],1],E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\"-F$6#\"\"(F(-F$6# \"#>F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$3#\"#*)\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$p\"\"$)>\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$o#\"$Y\"\"$l#\"$+$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$^%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E 1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$U\"\"$\">\"\")\"#m" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$s%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "E1:=[142,191,8,66] ; m1:=472;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$U\"\"$\">\"\")\"#m" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"$s%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3],E1[4],n1 );\n" }{MPLTEXT 1 0 39 "elldou([E1[1],E1[2],1],E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "*&)-I!G6\"6#\"\"#\"\"$\"\"\"-F%6#\"#fF*" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$w\"\"$0\"\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$\\#\"$n#\"$_#\"$+%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$v%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E 1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$2$\"$b#\"$3%\"$K$" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$A&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "E1 := [307, 255, 4 08, 332]; m1 := 522;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$2$\"$b#\"$3 %\"$K$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$A&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3],E1[ 4],n1);\n" }{MPLTEXT 1 0 39 "elldou([E1[1],E1[2],1],E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\")-F$6#\"\"$F'F(- F$6#\"#HF(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$h\"\"#\\\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$Y#\"$F$\"$g$\"#I" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"$o%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1: =ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$7\"\"#*)\"$t#\"$,$" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$?&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m 1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$q\" \"$r$\"$#=\"$\"R" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$1&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "E1 := [170, 371, 182, 391]; m1 := 5 06;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$q\"\"$r$\"$#=\"$\"R" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$1&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3],E1[4],n1 );\n" }{MPLTEXT 1 0 39 "elldou([E1[1],E1[2],1],E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\"-F$6#\"#6F(-F$6#\" #BF(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"#s\"#]\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$3\"\"#R\"#;\"$P%" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"$u%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1: =ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$`%\"$2$\"$O$\"$Q$" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$l%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m 1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$9# \"$<%\"$7#\"$%[" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$G&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3] ,E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$O\"\"$g$\"$&>\"$A#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$#\\" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$Q$\"$C\"\"$Y%\"$f#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$p%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E 1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$b$\"$`%\"$\"H\"$v%" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$D&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m 1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$j\" \"$l#\"$&H\"$p$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$=&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "E1 := [163, 265, 295, 369]; m1 := 5 18;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$j\"\"$l#\"$&H\"$p$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$=&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3],E1[4],n1);\n" } {MPLTEXT 1 0 39 "elldou([E1[1],E1[2],1],E1[3],E1[4],n1);" }}{PARA 11 " " 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\"-F$6#\"\"(F(-F$6#\"#PF(" }} {PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$$Q\"$[\"\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$@$\"#')\"$V\"\"$e$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$![" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=e llrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$`$\"$E%\"$3$\"#E" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" $o%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1: =ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#g\"#Y \"$$G\"$h%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$?&" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$e%\"\"#\"$)Q\"#%*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$.&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E1:=ellrand(n1); m1:=ellcount(E1[3],E1[4],n1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$l$\"$I#\"$1\"\"$*R" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$-&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "E1 := [365, 230, \+ 106, 399]; m1 := 502;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$l$\"$I#\"$ 1\"\"$*R" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$-&" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 57 "ifactor(m1); ellmul([E1[1],E1[2],1],m1,E1[3],E 1[4],n1);\n" }{MPLTEXT 1 0 39 "elldou([E1[1],E1[2],1],E1[3],E1[4],n1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "*&-I!G6\"6#\"\"#\"\"\"-F$6#\"$^#F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$K\"\"$&=\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "n2:=251; E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$^#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7 &\"#5\"$k\"\"$6\"\"$)=" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$h#" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcoun t(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#u\"\"$\"$=#\" ##)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$k#" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$\\\"\"#R\"#d\"#O" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"$_#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2: =ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$?#\"$D#\"$1\"\"$>\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$d#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); \+ m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#5 \"#H\"$L\"\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$v#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3] ,E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#J\"#R\"$:\"\"#U" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$K#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$^\"\"#z\"#&*\"$&>" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$P#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2 :=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#5\"#A\"$o\"\"#j" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$ M#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "E2 := [10, 22, 168, 6 3]; m2 := 234;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#5\"#A\"$o\"\"#j" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$M#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m2); ellmul([E2[1],E2[2],1],m2,E2[3],E2[4],n2 );\n" }{MPLTEXT 1 0 39 "elldou([E2[1],E2[2],1],E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "*(-I!G6\"6#\"\"#\"\"\")-F$6#\"\"$F'F(-F$ 6#\"#8F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$,#\"$P\"\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"$z\"\"$F\"\"#d\"$k\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$\"G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#m\"$T#\"$?\"\"$6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$H#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m 2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$3# \"#k\"$'>\"$l\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$k#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3] ,E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$H\"\"#N\"$)=\"$z\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$S#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"#$)\"$B#\"$@#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$k#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2 :=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$e\"\"$3#\"#I\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" $l#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2: =ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#`\"#m \"$S#\"$O\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$M#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n 2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$'=\"$I#\"#l\"$z\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$n#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$R\"\"$w\"\"$+\"\"#*)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$c#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=e llrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#*)\"#M\"#9\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$ _#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:= ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$`\"\"# **\"$<\"\"$D\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$Y#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3] ,E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$^\"\"$N\"\"$!>\"#$*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$S#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"#x\"$]\"\"$P#\"#?" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"$w#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2: =ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#s\"$\\\"\"$S#\"$T\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$!G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); \+ m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$f \"\"$D#\"\")\"$V#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$\\#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3] ,E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#_\"\"#\"#(*\"$$=" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"$s#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "7&\"#o\"$C\"\"$I\"\"#\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$q#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " E2:=ellrand(n2); m2:=ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#s\"$:#\"$k\"\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" $f#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2: =ellcount(E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$(=\"$ 4\"\"#$*\"$7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$T#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E2:=ellrand(n2); m2:=ellcount(E2[3] ,E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$z\"\"#:\"$c\"\"$t\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$i#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "E2 := [179, 15, 156, 173]; m2 := 262;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$z\"\"#:\"$c\"\"$t\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$i#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifact or(m2); ellmul([E2[1],E2[2],1],m2,E2[3],E2[4],n2);\n" }{MPLTEXT 1 0 39 "elldou([E2[1],E2[2],1],E2[3],E2[4],n2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*&-I!G6\"6#\"\"#\"\"\"-F$6#\"$J\"F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$># \"$D\"\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "n3:=131; E3 :=ellrand(n3); m3:=ellcount(E3[3],E3[4],n3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$J\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#]\"$I\"\"#q \"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$F\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "E3:=ellrand(n3); m3:=ellcount(E3[3],E3[4],n3);" } }{PARA 11 "" 1 "" {XPPMATH 20 "7&\"$/\"\"#t\"#[\"$3\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$8\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " E3:=ellrand(n3); m3:=ellcount(E3[3],E3[4],n3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#K\"$G\"\"$/\"\"#p" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"$Y\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "E3 := [32, 128, 1 04, 69]; m3 := 146;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"#K\"$G\"\"$/ \"\"#p" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$Y\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "ifactor(m3); ellmul([E3[1],E3[2],1],m3,E3[3],E3 [4],n3);\n" }{MPLTEXT 1 0 39 "elldou([E3[1],E3[2],1],E3[3],E3[4],n3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "*&-I!G6\"6#\"\"#\"\"\"-F$6#\"#tF(" }} {PARA 11 "" 1 "" {XPPMATH 20 "7%\"\"!\"\"\"F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7%\"$5\"\"#E\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n4:=73;" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 20 "11.5. Atkin \+ tesztje." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "interface(echo=2);" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 ";" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 40 "# For a given negative discriminant -D\n" }{MPLTEXT 1 0 40 "# we calculate the idea l class number.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 50 "idealclassnumber:=proc(D) local a,b,c,n,h; h:=0;\n" } {MPLTEXT 1 0 25 "for a while 3*a^2<=D do\n" }{MPLTEXT 1 0 29 " b:=D m od 2; n:=(b^2+D)/4;\n" }{MPLTEXT 1 0 17 " while b<=a do\n" }{MPLTEXT 1 0 31 " if n mod a=0 then c:=n/a;\n" }{MPLTEXT 1 0 38 " if c> =a and igcd(a,b,c)=1 then\n" }{MPLTEXT 1 0 58 " if a=c or b=0 o r b=a then h:=h+1 else h:=h+2 fi;\n" }{MPLTEXT 1 0 11 " fi;\n" } {MPLTEXT 1 0 27 " fi; n:=n+b+1; b:=b+2;\n" }{MPLTEXT 1 0 7 " od;\n " }{MPLTEXT 1 0 11 "od; h; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I \"DG6\"6'I\"aGF%I\"bGF%I\"cGF%I\"nGF%I\"hGF%F%F%C%>F+\"\"!?(F'\"\"\"F0 F%1,$*&\"\"$F0)F'\"\"#F0F0F$C%>F(-I$modGF%6$F$F6>F*,&*&#F0\"\"%F0)F(F6 F0F0*&F?F0F$F0F0?(F%F0F0F%1F(F'C%@$/-F:6$F*F'F.C$>F)*&F*F0F'!\"\"@$31F 'F)/-I%igcdG%*protectedG6%F'F(F)F0@%55/F'F)/F(F./F(F'>F+,&F+F0F0F0>F+, &F+F0F6F0>F*,(F*F0F(F0F0F0>F(,&F(F0F6F0F+F%F%F%" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 40 "# For a given negative d iscriminant -D\n" }{MPLTEXT 1 0 43 "# this calculates the ideal class \+ number.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 43 "# This versions is \+ slower then the other!\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 58 "idealclassnumber2:=proc(D) local a,b,c,n,h,X,x,DD; h: =1;\n" }{MPLTEXT 1 0 22 "if type(D,even) then\n" }{MPLTEXT 1 0 12 " D D:=D/4;\n" }{MPLTEXT 1 0 34 " for a from 2 while 3*a^2<=D do\n" } {MPLTEXT 1 0 29 " X:=Roots(x^2+DD) mod a;\n" }{MPLTEXT 1 0 30 " \+ for b in X do b:=2*b[1];\n" }{MPLTEXT 1 0 33 " if b>a then b:=b-2 *a; fi;\n" }{MPLTEXT 1 0 23 " c:=(b^2+D)/4/a;\n" }{MPLTEXT 1 0 38 " if c>=a and igcd(a,b,c)=1 then\n" }{MPLTEXT 1 0 38 " \+ if a=c and b<0 then next fi;\n" }{MPLTEXT 1 0 17 " h:=h+1;\n" } {MPLTEXT 1 0 11 " fi;\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 16 " DD:=(D+1)/4 ;\n" }{MPLTEXT 1 0 34 " for a from 2 while 3*a^2<=D do\n" }{MPLTEXT 1 0 31 " X:=Roots(x^2+x+DD) mod a;\n" }{MPLTEXT 1 0 19 " for b i n X do\n" }{MPLTEXT 1 0 20 " b:=2*b[1]+1;\n" }{MPLTEXT 1 0 33 " \+ if b>a then b:=b-2*a; fi;\n" }{MPLTEXT 1 0 23 " c:=(b^2+D)/4/ a;\n" }{MPLTEXT 1 0 38 " if c>=a and igcd(a,b,c)=1 then\n" } {MPLTEXT 1 0 38 " if a=c and b<0 then next fi;\n" }{MPLTEXT 1 0 17 " h:=h+1;\n" }{MPLTEXT 1 0 11 " fi;\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 11 "fi; h; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"DG6\"6*I\"aGF%I\"bGF%I\"cGF%I \"nGF%I\"hGF%I\"XGF%I\"xGF%I#DDGF%F%F%C%>F+\"\"\"@%-I%typeG%*protected G6$F$I%evenGF5C$>F.,$*&#F1\"\"%F1F$F1F1?(F'\"\"#F1F%1,$*&\"\"$F1)F'F?F 1F1F$C$>F,-I$modGF%6$-I&RootsGF%6#,&*$)F-F?F1F1F.F1F'?&F(F,I%trueGF5C& >F(,$*&F?F1&F(6#F1F1F1@$2F'F(>F(,&F(F1*&F?F1F'F1!\"\">F),$*(F F+,&F+F1F1F1C$>F.,&F;F1FF,-FH6$-FK6#,(FNF1F-F1F.F1F' ?&F(F,FQC&>F(,&FUF1F1F1FXFhnF^oF+F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 40 "# For a given negative discrimi nant -D\n" }{MPLTEXT 1 0 43 "# this calculates the ideal class number. \n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 41 "# This versions is faster \+ as others for\n" }{MPLTEXT 1 0 23 "# large discriminants\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 24 "# NOT YET FINISHED!!!!\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 54 "idealclassnumbershank:= proc(D,f,b) local P,p,Q,d,DD;\n" }{MPLTEXT 1 0 53 "DD:=2^16; # have to adjust for an appropriate limit\n" }{MPLTEXT 1 0 46 "if D
F-\"&Ob'@$2F$F-O-I1idealclassnu mberGF%6#F$>F)-I%ceilGF%6#)F$*&\"\"\"F=$\"\"%\"\"!!\"\">F+**$F=F@F=-I% sqrtGF%F6F=I#PiG%*protectedGFA,&FDF=*&-&I*numtheoryGF%6#I'jacobiGF%6$, $F$FA\"\"#F=$FRF@FAFAFA>F+*&F+F=,&F=F=*&-FL6$FQ\"\"$F=$FZF@FAFAFA>F*\" \"&>F,FR?(F%F=F=F%1F*F)C%@$-I(isprimeGF%6#F*>F+*&F+F=,&F=F=*&-FL6$FQF* F=F*FAFAFA>F*,&F*F=F,F=>F,,&\"\"'F=F,FAF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 52 "# This procedure gives bac k the next foundamental \n" }{MPLTEXT 1 0 52 "# discriminant larger th en d. A discriminant have \n" }{MPLTEXT 1 0 61 "# to be larger then 6, congruent to 3 modulo 4 or congruent\n" }{MPLTEXT 1 0 52 "# to 4 or 8 modulo 16 and a square of an odd prime\n" }{MPLTEXT 1 0 44 "# may not divide it. The result is in form\n" }{MPLTEXT 1 0 48 "# [d,h,q1,q2,.. ], where d is the discriminant,\n" }{MPLTEXT 1 0 47 "# h is the ideal \+ class number in Q(sgrt(-d)),\n" }{MPLTEXT 1 0 65 "# and the q's are od d primes except maybe q1, which may 4 or 8.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 48 "nextdiscriminant:=proc(d) local \+ dd,dp,L,n,p,i;\n" }{MPLTEXT 1 0 17 "dd:=max(d+1,7);\n" }{MPLTEXT 1 0 15 "while true do\n" }{MPLTEXT 1 0 52 " if dd mod 16=4 or dd mod 16=8 or dd mod 4=3 then\n" }{MPLTEXT 1 0 19 " L:=[]; n:=dd;\n" } {MPLTEXT 1 0 26 " if type(n,even) then\n" }{MPLTEXT 1 0 54 " f or i from 0 while type(n,even) do n:=n/2; od;\n" }{MPLTEXT 1 0 17 " \+ L:=[2^i];\n" }{MPLTEXT 1 0 9 " fi;\n" }{MPLTEXT 1 0 18 " if n >=9 then\n" }{MPLTEXT 1 0 33 " if n mod 3=0 then n:=n/3;\n" } {MPLTEXT 1 0 47 " if n mod 3=0 then dd:=dd+1; next; fi;\n" } {MPLTEXT 1 0 23 " L:=[op(L),3];\n" }{MPLTEXT 1 0 11 " fi; \n" }{MPLTEXT 1 0 9 " fi;\n" }{MPLTEXT 1 0 18 " dp:=2; p:=5;\n" }{MPLTEXT 1 0 21 " while n>=p^2 do\n" }{MPLTEXT 1 0 33 " if n \+ mod p=0 then n:=n/p;\n" }{MPLTEXT 1 0 48 " if n mod p=0 then L: =false; break; fi;\n" }{MPLTEXT 1 0 23 " L:=[op(L),p];\n" } {MPLTEXT 1 0 11 " fi;\n" }{MPLTEXT 1 0 26 " p:=p+dp; dp:=6-d p;\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 41 " if L=false the n dd:=dd+1; next; fi;\n" }{MPLTEXT 1 0 41 " L:=[dd,idealclassnumber (dd),op(L)];\n" }{MPLTEXT 1 0 34 " if n>1 then L:=[op(L),n] fi;\n" }{MPLTEXT 1 0 12 " break;\n" }{MPLTEXT 1 0 8 " else\n" }{MPLTEXT 1 0 15 " dd:=dd+1;\n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 19 "o d; L; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"dG6\"6(I#dd GF%I#dpGF%I\"LGF%I\"nGF%I\"pGF%I\"iGF%F%F%C%>F'-I$maxG%*protectedG6$,& F$\"\"\"F4F4\"\"(?(F%F4F4F%I%trueGF1@%55/-I$modGF%6$F'\"#;\"\"%/F<\"\" )/-F=6$F'F@\"\"$C->F)7\">F*F'@$-I%typeGF16$F*I%evenGF1C$?(F,\"\"!F4F%F L>F*,$*&#F4\"\"#F4F*F4F4>F)7#)FWF,@$1\"\"*F*@$/-F=6$F*FFFRC%>F*,$*&#F4 FFF4F*F4F4@$FinC$>F',&F'F4F4F4\\>F)7$-I#opGF16#F)FF>F(FW>F+\"\"&?(F%F4 F4F%1*$)F+FWF4F*C%@$/-F=6$F*F+FRC%>F**&F*F4F+!\"\"@$FdpC$>F)I&falseGF1 [>F)7$FhoF+>F+,&F+F4F(F4>F(,&\"\"'F4F(Fjp@$/F)F^qFbo>F)7%F'-I1idealcla ssnumberGF%6#F'Fho@$2F4F*>F)7$FhoF*F_qFcoF)F%F%F%" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 69 "# This procedure write to a file all the foundamental discriminants\n" }{MPLTEXT 1 0 65 "# i n the interval II. The ideal class number h also calculated,\n" } {MPLTEXT 1 0 65 "# and written. First h is written on two bytes, then \+ the number\n" }{MPLTEXT 1 0 63 "# of the factors on one byte. The last factor is written on 4\n" }{MPLTEXT 1 0 68 "# bytes, the second and t hird last factors are written on 2 bytes,\n" }{MPLTEXT 1 0 46 "# all o ther factors are written on one byte.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 52 "discriminants:=proc(II,filename) local x,L,B,D,id;\n" }{MPLTEXT 1 0 16 "x:=op(1,II)-1;\n" }{MPLTEXT 1 0 13 "if x<7 then\n" }{MPLTEXT 1 0 37 " id:=fopen(filename,WRITE,BINA RY) \n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 38 " id:=fopen(filenam e,APPEND,BINARY) \n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 47 "B:=op(2 ,II); x:=nextdiscriminant(x); D:=x[1];\n" }{MPLTEXT 1 0 15 "while D<=B do\n" }{MPLTEXT 1 0 61 " writediscriminant(x,id); x:=nextdiscriminan t(D); D:=x[1];\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 13 "fclose(id) ;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I#IIG6 \"I)filenameGF%6'I\"xGF%I\"LGF%I\"BGF%I\"DGF%I#idGF%F%F%C)>F(,&-I#opG% *protectedG6$\"\"\"F$F4F4!\"\"@%2F(\"\"(>F,-I&fopenGF%6%F&I&WRITEGF%I' BINARYGF%>F,-F;6%F&I'APPENDGF%F>>F*-F16$\"\"#F$>F(-I1nextdiscriminantG F%6#F(>F+&F(6#F4?(F%F4F4F%1F+F*C%-I2writediscriminantGF%6$F(F,>F(-FI6# F+FK-I'fcloseGF%6#F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 61 "# This procedure write to a file a discrimin ant having size\n" }{MPLTEXT 1 0 66 "# up to ds bytes; if ds is not gi ven, ds=4 is the default value.\n" }{MPLTEXT 1 0 59 "# First h(-d) is \+ written on hs bytes; if hs is not given,\n" }{MPLTEXT 1 0 58 "# we pre suppose hs=ceil(ds/2+1/2), which is large enough\n" }{MPLTEXT 1 0 65 " # to contain the ideal class number h(-d)hs then ERROR(`too large ideal class number`,L[2]) fi;\n" }{MPLTEXT 1 0 53 "i f nops(B)=ds \+ do writebytes(id,[L[i]]); i:=i+1; k:=k-1; od;\n" }{MPLTEXT 1 0 52 "whi le k>0 do l:=ceil(ds/k); if l>ps then l:=ps fi;\n" }{MPLTEXT 1 0 30 " \+ B:=convert(L[i],base,256);\n" }{MPLTEXT 1 0 62 " if nops(B)>l then E RROR(`too large prime factor`,L[i]) fi;\n" }{MPLTEXT 1 0 53 " if nops (B)F-\"\"%>F-&%%argsG6#\"\"$@%1F3FB>F.-I% ceilGF%6#,&*&#\"\"\"F4FLF-FLFLFKFL>F.&F@6#F=@%1F3F=>F/F->F/&F@6#\"\"&> F,-I(convertGF76%&F$6#F4I%baseGF%\"$c#@$2F.-I%nopsGF76#F,-F66$I=too~la rge~ideal~class~numberGF%Fen@$2F[oF.>F,7$-I#opGF7F]o-I\"$GF76$\"\"!/F) ;,&F[oFLFLFLF.-I+writebytesGF%6$F&F,>F(FB>F*,&-F\\o6#F$FLF4!\"\"-F_p6$ F&7#F*?(F%FLFLF%1F-F*C%-F_p6$F&7#&F$6#F(>F(,&F(FLFLFL>F*,&F*FLFLFfp?(F %FLFLF%2FjoF*C*>F+-FG6#*&F-FLF*Ffp@$2F/F+>F+F/>F,-FY6%F`qFgnFhn@$2F+F[ o-F66$I7too~large~prime~factorGF%F`q@$2F[oF+>F,7$Feo-Fho6$Fjo/F);F]pF+ F^pFbqFdqF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 62 "# This procedure read from a file a discriminant havi ng size\n" }{MPLTEXT 1 0 66 "# up to ds bytes; if ds is not given, ds= 4 is the default value.\n" }{MPLTEXT 1 0 56 "# First h(-d) is read on \+ hs bytes; if hs is not given,\n" }{MPLTEXT 1 0 58 "# we presuppose hs= ceil(ds/2+1/2), which is large enough\n" }{MPLTEXT 1 0 65 "# to contai n the ideal class number h(-d)=ds do\n" }{MPLTEXT 1 0 40 " B:=readbytes(i d,1); L:=[op(L),B[1]];\n" }{MPLTEXT 1 0 22 " d:=d*B[1]; k:=k-1;\n" } {MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 52 "while k>0 do l:=ceil(ds/k); i f l>ps then l:=ps fi;\n" }{MPLTEXT 1 0 23 " B:=readbytes(id,l);\n" } {MPLTEXT 1 0 50 " B:=convert([B[j]*256^(j-1)$j=1..nops(B)],`+`);\n" } {MPLTEXT 1 0 33 " d:=d*B; L:=[op(L),B]; k:=k-1;\n" }{MPLTEXT 1 0 19 " od; [d,op(L)]; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I#idG6\"6,I\" iGF%I\"jGF%I\"kGF%I\"BGF%I\"lGF%I\"dGF%I\"LGF%I#dsGF%I#hsGF%I#psGF%F%F %C/@$2%&nargsG\"\"\"-I&ERRORG%*protectedG6#I0not~enough~argsGF%@%/F4F5 >F.\"\"%>F.&%%argsG6#\"\"#@%1F4FC>F/-I%ceilGF%6#,&*&#F5FCF5F.F5F5FLF5> F/&FA6#\"\"$@%1F4FP>F0F.>F0&FA6#F>>F*-I*readbytesGF%6$F$F/@$/F*\"\"!-I 'RETURNGF86#I%NULLGF8>F-7#-I(convertGF86$7#-I\"$GF86$*&&F*6#F(F5)\"$c# ,&F(F5F5!\"\"F5/F(;F5-I%nopsGF86#F*I\"+GF8>F*-FY6$F$F5>F)&F*6#F5>F,F5? (F%F5F5F%1F.F)C&Fbp>F-7$-I#opGF86#F-Ffp>F,*&F,F5FfpF5>F),&F)F5F5F[p?(F %F5F5F%2FgnF)C)>F+-FH6#*&F.F5F)F[p@$2F0F+>F+F0>F*-FY6$F$F+>F*F^o>F,*&F ,F5F*F5>F-7$F^qF*Fcq7$F,F^qF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This procedure sieve out disc riminants from a file for which\n" }{MPLTEXT 1 0 64 "# the function f \+ gives value true. The result is [n,e] where n\n" }{MPLTEXT 1 0 69 "# i s the number if good discriminants and e is the sum of 1/h(D)'s.\n" } {MPLTEXT 1 0 4 "# \n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 54 "sievedisc riminants:=proc(filename,f) local e,n,x,id;\n" }{MPLTEXT 1 0 48 "id:=f open(filename,READ,BINARY); e:=0.0; n:=0;\n" }{MPLTEXT 1 0 4 "do\n" } {MPLTEXT 1 0 28 " x:=readdiscriminant(id);\n" }{MPLTEXT 1 0 28 " if \+ x=NULL then break fi;\n" }{MPLTEXT 1 0 41 " if f(x) then n:=n+1; e:=e +1/x[2]; fi;\n" }{MPLTEXT 1 0 27 "od; fclose(id); [n,e]; end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6$I)filenameG6\"I\"fGF%6&I\"eGF%I\"nGF %I\"xGF%I#idGF%F%F%C(>F+-I&fopenGF%6%F$I%READGF%I'BINARYGF%>F($\"\"!F5 >F)F5?(F%\"\"\"F8F%I%trueG%*protectedGC%>F*-I1readdiscriminantGF%6#F+@ $/F*I%NULLGF:[@$-F&6#F*C$>F),&F)F8F8F8>F(,&F(F8*$&F*6#\"\"#!\"\"F8-I'f closeGF%F?7$F)F(F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "b adness:=x->x[2]/2^(nops(x)-3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I \"xG6\"F%6$I)operatorGF%I&arrowGF%F%*&&F$6#\"\"#\"\"\")F,,&-I%nopsG%*p rotectedGF#F-\"\"$!\"\"F4F%F%F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 28 " 2. Find good discriminants" }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 57 "# This procedure calculates square root of the number a\n" }{MPLTEXT 1 0 64 "# modulo a \"probable prime\" p. If p is not a prime, an error\n" }{MPLTEXT 1 0 26 "# message may be caus ed.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 69 "mo dsqrt:=proc(a::integer,p::posint) local k,s,r,n,ra,j,i,z,c,x,t,b;\n" } {MPLTEXT 1 0 67 "if p=1 or type(p,even) then ERROR(`not a prime in mod sqrt`,p) fi;\n" }{MPLTEXT 1 0 63 "if numtheory[jacobi](a,p)<>1 then ER ROR(`not a square`,a) fi;\n" }{MPLTEXT 1 0 15 "k:=p-1; s:=0;\n" } {MPLTEXT 1 0 43 "while type(k,even) do s:=s+1; k:=k/2; od;\n" } {MPLTEXT 1 0 60 "k:=(k-1)/2; r:=a&^(k+1) mod p; n:=a&^(2*k+1) m od p;\n" }{MPLTEXT 1 0 20 "ra:=rand(p); j:=1;\n" }{MPLTEXT 1 0 29 "for i to 100 while j<>-1 do\n" }{MPLTEXT 1 0 39 " z:=ra(); j:=numtheory[ jacobi](z,p);\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 62 "if i=100 th en ERROR(`probably not a prime in modsqrt`,p) fi;\n" }{MPLTEXT 1 0 22 "c:=z&^(2*k+1) mod p;\n" }{MPLTEXT 1 0 21 "while n<>1 do x:=n;\n" } {MPLTEXT 1 0 59 " for t from s to 0 by -1 while x<>1 do x:=x^2 mod p; od;\n" }{MPLTEXT 1 0 53 " if t=0 then ERROR(`not a prime in modsqrt` ,p) fi;\n" }{MPLTEXT 1 0 54 " b:=c&^(2^(t-1)) mod p; r:=r*b mod p; c: =b^2 mod p;\n" }{MPLTEXT 1 0 25 " n:=n*c mod p; s:=s-t;\n" }{MPLTEXT 1 0 19 "od; r; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"a G6\"I(integerG%*protectedG'I\"pGF&I'posintGF(6.I\"kGF&I\"sGF&I\"rGF&I \"nGF&I#raGF&I\"jGF&I\"iGF&I\"zGF&I\"cGF&I\"xGF&I\"tGF&I\"bGF&F&F&C1@$ 5/F*\"\"\"-I%typeGF(6$F*I%evenGF(-I&ERRORGF(6$I7not~a~prime~in~modsqrt GF&F*@$0-&I*numtheoryG6$F(I(_syslibGF&6#I'jacobiGF&6$F%F*F=-FC6$I-not~ a~squareGF&F%>F-,&F*F=F=!\"\">F.\"\"!?(F&F=F=F&-F?6$F-FAC$>F.,&F.F=F=F =>F-,$*&#F=\"\"#F=F-F=F=>F-,&FjnF=F[oFU>F/-I$modGF&6$-I#&^GF&6$F%,&F-F =F=F=F*>F0-Fao6$-Fdo6$F%,&*&F\\oF=F-F=F=F=F=F*>F1-I%randGF&6#F*>F2F=?( F3F=F=\"$+\"0F2FUC$>F4-F1F&>F2-FI6$F4F*@$/F3Fdp-FC6$I@probably~not~a~p rime~in~modsqrtGF&F*>F5-Fao6$-Fdo6$F4F\\pF*?(F&F=F=F&0F0F=C*>F6F0?(F7F .FUFW0F6F=>F6-Fao6$*$)F6F\\oF=F*@$/F7FWFB>F8-Fao6$-Fdo6$F5)F\\o,&F7F=F =FUF*>F/-Fao6$*&F/F=F8F=F*>F5-Fao6$*$)F8F\\oF=F*>F0-Fao6$*&F0F=F5F=F*> F.,&F.F=F7FUF/F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 54 "# This procedure put all the primes p below P to th e\n" }{MPLTEXT 1 0 46 "# table goodprimes, for which (n|p)=1, where\n" }{MPLTEXT 1 0 52 "# n is a given probable prime. Differences between \n" }{MPLTEXT 1 0 36 "# odd primes are read from a file.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 57 "goodprimes:=proc(fi lename,P,n,goodprimes) local p,id,d;\n" }{MPLTEXT 1 0 54 "if numtheory [jacobi](-1,n)=1 then goodprimes[-1]:=-1\n" }{MPLTEXT 1 0 31 " else g oodprimes[-1]:=0; fi;\n" }{MPLTEXT 1 0 54 "if numtheory[jacobi](-2,n)= 1 then goodprimes[-2]:=-2\n" }{MPLTEXT 1 0 31 " else goodprimes[-2]:= 0; fi;\n" }{MPLTEXT 1 0 51 "if numtheory[jacobi](2,n)=1 then goodprime s[2]:=2\n" }{MPLTEXT 1 0 29 " else goodprimes[2]:=0 fi;\n" }{MPLTEXT 1 0 40 "id:=fopen(filename,READ,BINARY); p:=3;\n" }{MPLTEXT 1 0 14 "wh ile p

&F(6#F9F9>F<\"\"!@%/-F16$!\"#F'F:>&F(6#FDFD>FFF?@ %/-F16$\"\"#F'F:>&F(6#FMFM>FOF?>F+-I&fopenGF%6%F$I%READGF%I'BINARYGF%> F*\"\"$?(F%F:F:F%2F*F&C&@%/-F16$F'F*F:>&F(6#F*F:>F\\oF?>F,-I)readdiffG F%6#F+@$/F,I%NULLGF4-I&ERRORGF46#I=not~enough~prime~differencesGF%>F*, &F*F:F,F:-I'fcloseGF%FboF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 49 "# This procedure put the square root of \+ p or -p\n" }{MPLTEXT 1 0 43 "# for all the odd primes p below P to the \n" }{MPLTEXT 1 0 41 "# table roots, for which (n|p)=1, where\n" } {MPLTEXT 1 0 52 "# n is a given probable prime. Differences between\n" }{MPLTEXT 1 0 53 "# odd primes are read from a file. Good primes came \n" }{MPLTEXT 1 0 26 "# from table goodprimes.\n" }{MPLTEXT 1 0 3 "#\n " }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 67 "goodprimeroots:=proc(filename ,P,n,goodprimes,roots) local p,id,d;\n" }{MPLTEXT 1 0 57 "if goodprime s[-1]<>0 then roots[-1]:=modsqrt(n-1,n) fi;\n" }{MPLTEXT 1 0 57 "if go odprimes[-2]<>0 then roots[-2]:=modsqrt(n-2,n) fi;\n" }{MPLTEXT 1 0 53 "if goodprimes[2]<>0 then roots[2]:=modsqrt(2,n) fi;\n" }{MPLTEXT 1 0 40 "id:=fopen(filename,READ,BINARY); p:=3;\n" }{MPLTEXT 1 0 19 "if n mod 4=1 then\n" }{MPLTEXT 1 0 16 " while p

0 then roots[p]:=modsqrt(p,n); fi;\n" } {MPLTEXT 1 0 22 " d:=readdiff(id);\n" }{MPLTEXT 1 0 62 " if d=NU LL then ERROR(`not enough prime differences`) fi;\n" }{MPLTEXT 1 0 13 " p:=p+d;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 6 "else\n" } {MPLTEXT 1 0 16 " while p

0 then\n" }{MPLTEXT 1 0 25 " if p mod 4=1 then\n" }{MPLTEXT 1 0 33 " roots[p]:=modsqrt(p,n);\n" }{MPLTEXT 1 0 12 " els e\n" }{MPLTEXT 1 0 35 " roots[p]:=modsqrt(n-p,n);\n" }{MPLTEXT 1 0 11 " fi;\n" }{MPLTEXT 1 0 9 " fi;\n" }{MPLTEXT 1 0 22 " \+ d:=readdiff(id);\n" }{MPLTEXT 1 0 62 " if d=NULL then ERROR(`not e nough prime differences`) fi;\n" }{MPLTEXT 1 0 13 " p:=p+d;\n" } {MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 20 "fi; fclose(id); end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6'I)filenameG6\"I\"PGF%I\"nGF%I+goodpr imesGF%I&rootsGF%6%I\"pGF%I#idGF%I\"dGF%F%F%C)@$0&F(6#!\"\"\"\"!>&F)F2 -I(modsqrtGF%6$,&F'\"\"\"F;F3F'@$0&F(6#!\"#F4>&F)F?-F86$,&F'F;\"\"#F3F '@$0&F(6#FFF4>&F)FJ-F86$FFF'>F,-I&fopenGF%6%F$I%READGF%I'BINARYGF%>F+ \"\"$@%/-I$modGF%6$F'\"\"%F;?(F%F;F;F%2F+F&C&@$0&F(6#F+F4>&F)F]o-F86$F +F'>F--I)readdiffGF%6#F,@$/F-I%NULLG%*protectedG-I&ERRORGFio6#I=not~en ough~prime~differencesGF%>F+,&F+F;F-F;?(F%F;F;F%FhnC&@$F[o@%/-FZ6$F+Ff nF;F^o>F_o-F86$,&F'F;F+F3F'FboFfoF^p-I'fcloseGF%FeoF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 55 "# This proced ure gives the next good discriminant for\n" }{MPLTEXT 1 0 62 "# the pr obably prime number n. The function value have to be\n" }{MPLTEXT 1 0 65 "# true for the discriminant. The condition (-d|n)=1 is checked.\n" }{MPLTEXT 1 0 43 "# Good prime roots came from table roots.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 65 "nextgooddi scriminantfor:=proc(id,n,f,roots) local x,i,j,s,q,ff;\n" }{MPLTEXT 1 0 4 "do\n" }{MPLTEXT 1 0 28 " x:=readdiscriminant(id);\n" }{MPLTEXT 1 0 35 " if x=NULL then return(NULL) fi;\n" }{MPLTEXT 1 0 16 " if f( x) then\n" }{MPLTEXT 1 0 36 " i:=3; q:=x[3]; s:=1; ff:=true;\n" } {MPLTEXT 1 0 45 " if q=4 or q=8 then i:=i+1 else q:=1 fi;\n" } {MPLTEXT 1 0 32 " for j from i to nops(x) do\n" }{MPLTEXT 1 0 67 " \+ if not type(roots[x[j]],integer) then ff:=false; break; fi;\n" } {MPLTEXT 1 0 39 " if x[j] mod 4=3 then s:=-s; fi;\n" }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 30 " if not ff then next; fi;\n" } {MPLTEXT 1 0 17 " i:=n mod 8;\n" }{MPLTEXT 1 0 45 " if i=1 or i= 5 then s:=1 else s:=-s; fi;\n" }{MPLTEXT 1 0 45 " if q=8 and (i=3 o r i=5) then s:=-s; fi;\n" }{MPLTEXT 1 0 28 " if s=1 then break; fi; \n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 19 "od; x; end;" } }{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I#idG6\"I\"nGF%I\"fGF%I&rootsGF%6(I \"xGF%I\"iGF%I\"jGF%I\"sGF%I\"qGF%I#ffGF%F%F%C$?(F%\"\"\"F2F%I%trueG%* protectedGC%>F*-I1readdiscriminantGF%6#F$@$/F*I%NULLGF4OF<@$-F'6#F*C-> F+\"\"$>F.&F*6#FC>F-F2>F/F3@%5/F.\"\"%/F.\"\")>F+,&F+F2F2F2>F.F2?(F,F+ F2-I%nopsGF4F@F3C$@$4-I%typeGF46$&F(6#&F*6#F,I(integerGF4C$>F/I&falseG F4[@$/-I$modGF%6$FgnFLFC>F-,$F-!\"\"@$4F/\\>F+-Fao6$F&FN@%5/F+F2/F+\" \"&FGFco@$3FM5/F+FCF_pFco@$/F-F2F]oF*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This procedure sieve out d iscriminants from a file for which\n" }{MPLTEXT 1 0 69 "# the function f gives value true, and conditions (-d|n)=1, (n|p)=1\n" }{MPLTEXT 1 0 68 "# are satisfied. The result is [m,e] where m is the number if go od\n" }{MPLTEXT 1 0 66 "# discriminants and e is the expected number o f elliptic curves.\n" }{MPLTEXT 1 0 4 "# \n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 58 "gooddiscriminantsfor:=proc(filename,n,f) local e,m,x, id;\n" }{MPLTEXT 1 0 34 "id:=fopen(filename,READ,BINARY);\n" }{MPLTEXT 1 0 15 "e:=0.0; m:=0;\n" }{MPLTEXT 1 0 4 "do\n" }{MPLTEXT 1 0 39 " x :=nextgooddiscriminantfor(id,n,f);\n" }{MPLTEXT 1 0 28 " if x=NULL th en break fi;\n" }{MPLTEXT 1 0 36 " m:=m+1; e:=e+2^(nops(x)-2)/x[2];\n " }{MPLTEXT 1 0 27 "od; fclose(id); [m,e]; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I)filenameG6\"I\"nGF%I\"fGF%6&I\"eGF%I\"mGF%I\"xGF%I# idGF%F%F%C(>F,-I&fopenGF%6%F$I%READGF%I'BINARYGF%>F)$\"\"!F6>F*F6?(F% \"\"\"F9F%I%trueG%*protectedGC&>F+-I8nextgooddiscriminantforGF%6%F,F&F '@$/F+I%NULLGF;[>F*,&F*F9F9F9>F),&F)F9*&)\"\"#,&-I%nopsGF;6#F+F9FK!\" \"F9&F+6#FKFPF9-I'fcloseGF%6#F,7$F*F)F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 66 "# This procedure gives the n ext good discriminant and its square\n" }{MPLTEXT 1 0 65 "# root for t he probably prime number n. The function value have\n" }{MPLTEXT 1 0 62 "# to be true for the discriminant. The condition (-d|n)=1 is\n" } {MPLTEXT 1 0 47 "# checked. Prime roots came from table roots.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 68 "nextgooddi scriminantroot:=proc(id,n,f,roots) local r,x,i,j,s,q,ff;\n" }{MPLTEXT 1 0 4 "do\n" }{MPLTEXT 1 0 28 " x:=readdiscriminant(id);\n" }{MPLTEXT 1 0 35 " if x=NULL then return(NULL) fi;\n" }{MPLTEXT 1 0 16 " if f (x) then\n" }{MPLTEXT 1 0 36 " i:=3; q:=x[3]; s:=1; ff:=true;\n" } {MPLTEXT 1 0 45 " if q=4 or q=8 then i:=i+1 else q:=1 fi;\n" } {MPLTEXT 1 0 32 " for j from i to nops(x) do\n" }{MPLTEXT 1 0 51 " \+ if roots[x[j]]=0 then ff:=false; break; fi;\n" }{MPLTEXT 1 0 39 " if x[j] mod 4=3 then s:=-s; fi;\n" }{MPLTEXT 1 0 9 " od;\n" } {MPLTEXT 1 0 30 " if not ff then next; fi;\n" }{MPLTEXT 1 0 17 " \+ j:=n mod 8;\n" }{MPLTEXT 1 0 45 " if j=1 or j=5 then s:=1 else s:= -s; fi;\n" }{MPLTEXT 1 0 45 " if q=8 and (j=3 or j=5) then s:=-s; f i;\n" }{MPLTEXT 1 0 23 " if s=1 then r:=1;\n" }{MPLTEXT 1 0 62 " \+ for j from i to nops(x) do r:=r*roots[x[j]] mod n; od;\n" }{MPLTEXT 1 0 47 " if q=4 then r:=r*2*roots[-1] mod n; fi;\n" }{MPLTEXT 1 0 19 " j:=n mod 8;\n" }{MPLTEXT 1 0 19 " if q=8 then\n" } {MPLTEXT 1 0 30 " if (j=3 or j=5) then\n" }{MPLTEXT 1 0 33 " \+ r:=r*2*roots[2] mod n\n" }{MPLTEXT 1 0 14 " else\n" } {MPLTEXT 1 0 34 " r:=r*2*roots[-2] mod n\n" }{MPLTEXT 1 0 13 " fi;\n" }{MPLTEXT 1 0 11 " fi;\n" }{MPLTEXT 1 0 14 " \+ break;\n" }{MPLTEXT 1 0 9 " fi;\n" }{MPLTEXT 1 0 7 " fi;\n" } {MPLTEXT 1 0 25 "od; [x[1],r] end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I#idG6\"I\"nGF%I\"fGF%I&rootsG6$%*protectedGI(_syslib GF%6)I\"rGF%I\"xGF%I\"iGF%I\"jGF%I\"sGF%I\"qGF%I#ffGF%F%F%C$?(F%\"\"\" F6F%I%trueGF*C%>F.-I1readdiscriminantGF%6#F$@$/F.I%NULLGF*OF?@$-F'6#F. C->F/\"\"$>F2&F.6#FF>F1F6>F3F7@%5/F2\"\"%/F2\"\")>F/,&F/F6F6F6>F2F6?(F 0F/F6-I%nopsGF*FCF7C$@$/&F(6#&F.6#F0\"\"!C$>F3I&falseGF*[@$/-I$modGF%6 $FgnFOFF>F1,$F1!\"\"@$4F3\\>F0-Fao6$F&FQ@%5/F0F6/F0\"\"&FJFco@$3FP5/F0 FFF_pFco@$/F1F6C(>F-F6?(F0F/F6FVF7>F--Fao6$*&F-F6FenF6F&@$FN>F--Fao6$, $*(\"\"#F6F-F6&F(6#FeoF6F6F&Fio@$FP@%Fcp>F--Fao6$,$*(FdqF6F-F6&F(6#Fdq F6F6F&>F--Fao6$,$*(FdqF6F-F6&F(6#!\"#F6F6F&F]o7$&F.6#F6F-F%F%F%" }}} {EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 29 " 3. Reduced form we look for" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "DD:=7; a:=1; b:=-DD; c:=(-DD )*(-DD-1)/4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }}{PARA 11 "" 1 " " {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#9" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "DD:=8; a:=1; b:=-DD; c:=(-DD)*(-DD-1)/4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#=" }}} {EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 23 " 4. Reduction of forms" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 68 "# This proced ure calculates for a quadratic form a*x*x+b*x*y+c*y*y\n" }{MPLTEXT 1 0 65 "# the corresponding reduced quadratic form. The values x, y for \n" }{MPLTEXT 1 0 63 "# which the reduced form takes the same value as the original\n" }{MPLTEXT 1 0 64 "# form for x=1, y=0 also calculate d. The new coefficients and\n" }{MPLTEXT 1 0 24 "# x, y are given back .\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 47 "redu ceform:=proc(a,b,c) local aa,bb,cc,x,y,q;\n" }{MPLTEXT 1 0 22 "aa:=a; \+ bb:=b; cc:=c;\n" }{MPLTEXT 1 0 13 "x:=1; y:=0;\n" }{MPLTEXT 1 0 56 "wh ile ccaa or (cc=aa and bb<0) do\n" }{MPLTEXT 1 0 43 " q:=bb+aa-1; q:=(q-(q mod (2*aa)))/2/aa;\n" }{MPLTEXT 1 0 48 " b b:=bb-2*aa*q; cc:=cc-q*(bb+q*aa); x:=x+q*y;\n" }{MPLTEXT 1 0 61 " if \+ ccF )F$>F*F&>F+F'>F,\"\"\">F-\"\"!?(F%F4F4F%5552F+F)1F*,$F)!\"\"2F)F*3/F+F )2F*F6C)>F.,(F*F4F)F4F4F>>F.,$*(#F4\"\"#F4,&F.F4-I$modGF%6$F.,$*&FJF4F )F4F4F>F4F)F>F4>F*,&F*F4*(FJF4F)F4F.F4F>>F+,&F+F4*&F.F4,&F*F4*&F)F4F.F 4F4F4F>>F,,&F,F4*&F.F4F-F4F4@$F;C(>F.F,>F,F->F-F.>F.F)>F)F+>F+F.@$F@C$ >F*,$F*F>>F,,$F,F>7'F)F*F+F,F-F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "DD:=7; a:=1; b:=-DD; c:=(-DD)*(-DD-1)/4; reduceform(a ,b,c);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#9" }}{PARA 11 "" 1 "" {XPPMATH 20 "7'\"\"\"F# \"\"#F#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "DD:=8; a:=1 ; b:=-DD; c:=(-DD)*(-DD-1)/4; reduceform(a,b,c);" }}{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 "7'\"\"\"\"\"!\"\"#F#F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 31 " 5. Find the algebraic integer" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 55 "# This procedure giv es the next good discriminant and\n" }{MPLTEXT 1 0 57 "# the trace of \+ the corresponding algebraic integer for \n" }{MPLTEXT 1 0 51 "# the pr obably prime number n. The function value\n" }{MPLTEXT 1 0 41 "# have \+ to be true for the discriminant.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 46 "nextgoodorder:=proc(id,n,f,roots) local x,t ;\n" }{MPLTEXT 1 0 4 "do\n" }{MPLTEXT 1 0 46 " x:=nextgooddiscriminan troot(id,n,f,roots);\n" }{MPLTEXT 1 0 35 " if x=NULL then return(NULL ) fi;\n" }{MPLTEXT 1 0 25 " t:=testorder(x[1],n);\n" }{MPLTEXT 1 0 29 " if t<>NULL then break fi;\n" }{MPLTEXT 1 0 17 "od; [x[1],t] end; " }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I#idG6\"I\"nGF%I\"fGF%I&rootsG6$ %*protectedGI(_syslibGF%6$I\"xGF%I\"tGF%F%F%C$?(F%\"\"\"F1F%I%trueGF*C &>F--I9nextgooddiscriminantrootGF%F#@$/F-I%NULLGF*OF9>F.-I*testorderGF %6$&F-6#F1F&@$0F.F9[7$F?F.F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 41 "# This procedure count good orders for \+ \n" }{MPLTEXT 1 0 51 "# the probably prime number n. The function valu e\n" }{MPLTEXT 1 0 41 "# have to be true for the discriminant.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 60 "countgoodo rders:=proc(discr,n,f,roots) local x,i,id; i:=0;\n" }{MPLTEXT 1 0 31 " id:=fopen(discr,READ,BINARY);\n" }{MPLTEXT 1 0 4 "do\n" }{MPLTEXT 1 0 35 " x:=nextgoodorder(id,n,f,roots);\n" }{MPLTEXT 1 0 36 " if x=NULL then break fi; i:=i+2;\n" }{MPLTEXT 1 0 34 "od; fclose(discr) ; i; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I&discrG6\"I\"nGF%I\"fG F%I&rootsG6$%*protectedGI(_syslibGF%6%I\"xGF%I\"iGF%I#idGF%F%F%C'>F.\" \"!>F/-I&fopenGF%6%F$I%READGF%I'BINARYGF%?(F%\"\"\"F:F%I%trueGF*C%>F-- I.nextgoodorderGF%6&F/F&F'F(@$/F-I%NULLGF*[>F.,&F.F:\"\"#F:-I'fcloseGF %6#F$F.F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 58 "# This procedure gives back the list of good orders f or \n" }{MPLTEXT 1 0 51 "# the probably prime number n. The function v alue\n" }{MPLTEXT 1 0 41 "# have to be true for the discriminant.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 58 "goodorders :=proc(discr,n,f) local x,i,id,L; i:=0; L:=[];\n" }{MPLTEXT 1 0 31 "id :=fopen(discr,READ,BINARY);\n" }{MPLTEXT 1 0 4 "do\n" }{MPLTEXT 1 0 35 " x:=nextgoodorder(id,n,f,roots);\n" }{MPLTEXT 1 0 17 " L:=[op(L) ,x];\n" }{MPLTEXT 1 0 36 " if x=NULL then break fi; i:=i+2;\n" } {MPLTEXT 1 0 26 "od; fclose(discr); L; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I&discrG6\"I\"nGF%I\"fGF%6&I\"xGF%I\"iGF%I#idGF%I\"LG F%F%F%C(>F*\"\"!>F,7\">F+-I&fopenGF%6%F$I%READGF%I'BINARYGF%?(F%\"\"\" F9F%I%trueG%*protectedGC&>F)-I.nextgoodorderGF%6&F+F&F'I&rootsG6$F;I(_ syslibGF%>F,7$-I#opGF;6#F,F)@$/F)I%NULLGF;[>F*,&F*F9\"\"#F9-I'fcloseGF %6#F$F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 59 "# This procedure test whether in the quadratic order \+ with\n" }{MPLTEXT 1 0 61 "# discriminant -D there is an element with n orm equal to n,\n" }{MPLTEXT 1 0 63 "# a probable prime. If such an el ement a+b*sqrt(-D) is found,\n" }{MPLTEXT 1 0 59 "# the trace of it is given back, else the result is NULL.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 37 "testform:=proc(D,n) local a,b,r, al;\n" }{MPLTEXT 1 0 49 "if numtheory[jacobi](-D,n)<>1 then RETURN() f i;\n" }{MPLTEXT 1 0 25 "b:=modsqrt(-D mod n,n);\n" }{MPLTEXT 1 0 35 "i f type(b+D,odd) then b:=b+n; fi;\n" }{MPLTEXT 1 0 33 "r:=reduceform(n, b,(b^2+D)/4/n);\n" }{MPLTEXT 1 0 19 "if D mod 4=0 then\n" }{MPLTEXT 1 0 43 " if r[1]<>1 or r[2]<>0 then RETURN() fi;\n" }{MPLTEXT 1 0 11 " \+ 2*r[4];\n" }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 43 " if r[1]<>1 or r[2]<>1 then RETURN() fi;\n" }{MPLTEXT 1 0 16 " 2*r[4]+r[5];\n" } {MPLTEXT 1 0 8 "fi; end;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 42 " 6. Factorization of the orders of curves" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 ";" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 ";" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 ";" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 ";" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 35 " 7. Set up the Hilbert polynomial" }}{PARA 0 " " 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 66 "# For a given negative discriminant -D this procedu re calculates\n" }{MPLTEXT 1 0 63 "# a list of all pairs of numbers [a ,b] representing a reduced\n" }{MPLTEXT 1 0 43 "# ideal and gives back the list of these.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 45 "allredideals:=proc(D) local a,b,c,L; L:=[];\n" } {MPLTEXT 1 0 25 "for a while 3*a^2<=D do\n" }{MPLTEXT 1 0 25 " for b \+ from -a to a do\n" }{MPLTEXT 1 0 41 " if b^2+D mod 4*a <> 0 then ne xt fi;\n" }{MPLTEXT 1 0 23 " c:=(b^2+D)/(4*a);\n" }{MPLTEXT 1 0 26 " if c1 th en next fi;\n" }{MPLTEXT 1 0 34 " if a=c and b<0 then next fi;\n" } {MPLTEXT 1 0 27 " if b=-a then next fi;\n" }{MPLTEXT 1 0 23 " L: =[op(L),[a,b]];\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 11 "od; L; \+ end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"DG6\"6&I\"aGF%I\"bGF%I\"c GF%I\"LGF%F%F%C%>F*7\"?(F'\"\"\"F/F%1,$*&\"\"$F/)F'\"\"#F/F/F$?(F(,$F' !\"\"F/F'I%trueG%*protectedGC)@$0-I$modGF%6$,&*$)F(F5F/F/F$F/,$*&\"\"% F/F'F/F/\"\"!\\>F),$*(#F/FFF/FAF/F'F8F/@$2F)F'FH@$2F/-I%igcdGF:6%F'F(F )FH@$3/F'F)2F(FGFH@$/F(F7FH>F*7$-I#opGF:6#F*7$F'F(F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 68 "# This proced ure calculate directly the parameters g2(L) and g3(L)\n" }{MPLTEXT 1 0 64 "# of the elliptic curve over the complex numbers corresponding\n " }{MPLTEXT 1 0 64 "# to a lattice k+l*al with a complex number al. Th e summing is\n" }{MPLTEXT 1 0 68 "# done for all k,l with absolute val ue less then K. You may change\n" }{MPLTEXT 1 0 57 "# Digits and incre ase K to obtain better approximation.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 57 "directparam:=proc(al,K) local k, l,s4,s6; s6:=0;\n" }{MPLTEXT 1 0 52 "for k while kF+\"\"!?(F(\"\"\"F0F %2F(F&C$>F*,&F*F0*&\"\"#F0)F(\"\"%!\"\"F0>F+,&F+F0*&F6F0)F(\"\"'F9F0?( F)F0F0F%2F)F&C$>F*,&F*F0*(F6F0)F)F8F9)F$F8F9F0>F+,&F+F0*(F6F0)F)F>F9)F $F>F9F0?(F)F0F0F%F@?(F(F0F0F%F1C$>F*,(F*F0*&F6F0),&F(F0*&F)F0F$F0F0F8F 9F0*&F6F0),&F(F0FTF9F8F9F0>F+,(F+F0*&F6F0)FSF>F9F0*&F6F0)FWF>F9F07$,$* &\"#gF0F*F0F0,$*&\"$S\"F0F+F0F0F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 69 "# This procedure calculate a cr ude approximation of the j-invariant\n" }{MPLTEXT 1 0 60 "# correspond ing to a reduced ideal with parameters a,b,-D.\n" }{MPLTEXT 1 0 63 "# \+ Simple summing is done for all k,l with absolute value less\n" } {MPLTEXT 1 0 65 "# then K. You may change Digits and increase K to obt ain better\n" }{MPLTEXT 1 0 18 "# approximation.\n" }{MPLTEXT 1 0 3 "# \n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 45 "directjinvariant:=proc(a,b, D,K) local al,p;\n" }{MPLTEXT 1 0 31 "al:=evalf((b+sqrt(-D))/2./a);\n" }{MPLTEXT 1 0 23 "p:=directparam(al,K);\n" }{MPLTEXT 1 0 36 "2^6*3^3* p[1]^3/(p[1]^3-27*p[2]^2);\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 " " {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I\"DGF%I\"KGF%6$I#alGF%I\"pGF%F%F%C% >F*-I&evalfG%*protectedG6#*(,&F&\"\"\"-I%sqrtGF%6#,$F'!\"\"F4F4$\"\"# \"\"!F9F$F9>F+-I,directparamGF%6$F*F(,$*(\"%G " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 58 "# This procedure calculates a c rude approximation of the\n" }{MPLTEXT 1 0 62 "# Hilbert polynomial fo r a given discriminant -D. To get the\n" }{MPLTEXT 1 0 61 "# j-invaria nts, simple summing up for all k,l with absolute\n" }{MPLTEXT 1 0 67 " # value less then K is used. You may change Digits and increase K\n" } {MPLTEXT 1 0 35 "# to obtain better approximation.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 3 " \n" }{MPLTEXT 1 0 51 "directhilbert:=proc(D,K) local p,j,P,L; global X;\n" }{MPLTEXT 1 0 34 "L:=allredideals(D); \+ P:=1;\n" }{MPLTEXT 1 0 15 "for p in L do\n" }{MPLTEXT 1 0 39 " j: =directjinvariant(p[1],p[2],D,K);\n" }{MPLTEXT 1 0 15 " P:=P*(X-j);\n " }{MPLTEXT 1 0 11 "od; P; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I \"DG6\"I\"KGF%6&I\"pGF%I\"jGF%I\"PGF%I\"LGF%F%F%C&>F+-I-allredidealsGF %6#F$>F*\"\"\"?&F(F+I%trueG%*protectedGC$>F)-I1directjinvariantGF%6&&F (6#F2&F(6#\"\"#F$F&>F**&F*F2,&I\"XGF%F2F)!\"\"F2F*F%6#FCF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 63 "# This proced ure calculate the coefficients of the product of\n" }{MPLTEXT 1 0 65 " # two pover series in order below n. The coefficients are given\n" } {MPLTEXT 1 0 64 "# as lists starting with the constant term and ending with the\n" }{MPLTEXT 1 0 24 "# term with order n-1.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 47 "cauchyprod:=proc(A,B, n) local c,i,j,C; C:=[];\n" }{MPLTEXT 1 0 30 "for i from 0 to n-1 do c :=0;\n" }{MPLTEXT 1 0 58 " for j from 0 to i do c:=c+A[j+1]*B [i-j+1]; od;\n" }{MPLTEXT 1 0 17 " C:=[op(C),c];\n" }{MPLTEXT 1 0 11 "od; C; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"BGF%I\"nG F%6&I\"cGF%I\"iGF%I\"jGF%I\"CGF%F%F%C%>F,7\"?(F*\"\"!\"\"\",&F'F2F2!\" \"I%trueG%*protectedGC%>F)F1?(F+F1F2F*F5>F),&F)F2*&&F$6#,&F+F2F2F2F2&F &6#,(F*F2F+F4F2F2F2F2>F,7$-I#opGF66#F,F)F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This procedure calcul ate the coefficients of the quotient of\n" }{MPLTEXT 1 0 65 "# two pov er series in order below n. The coefficients are given\n" }{MPLTEXT 1 0 64 "# as lists starting with the constant term and ending with the\n " }{MPLTEXT 1 0 24 "# term with order n-1.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 55 "cauchyquo:=proc(A,B,n) local c,i ,j,C; C:=[A[1]/B[1]];\n" }{MPLTEXT 1 0 23 "for i to n-1 do c:=0;\n" } {MPLTEXT 1 0 41 " for j to i do c:=c+C[j]*B[i-j+2]; od;\n" }{MPLTEXT 1 0 31 " C:=[op(C),(A[i+1]-c)/B[1]];\n" }{MPLTEXT 1 0 11 "od; C; end; " }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"AG6\"I\"BGF%I\"nGF%6&I\"cGF%I \"iGF%I\"jGF%I\"CGF%F%F%C%>F,7#*&&F$6#\"\"\"F3&F&F2!\"\"?(F*F3F3,&F'F3 F3F5I%trueG%*protectedGC%>F)\"\"!?(F+F3F3F*F8>F),&F)F3*&&F,6#F+F3&F&6# ,(F*F3F+F5\"\"#F3F3F3>F,7$-I#opGF96#F,*&,&&F$6#,&F*F3F3F3F3F)F5F3F4F5F ,F%F%F%" }}}{EXCHG {PARA 205 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This procedure calculate the coefficients of the q-expansion \n" }{MPLTEXT 1 0 60 "# with order below n. The 1/q term will not be g iven back.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 40 "qexpansion:=proc(n) local c,i,j,C,A,B;\n" }{MPLTEXT 1 0 34 "A:=[ 1,240*sigma[3](i)$i=1..n+1];\n" }{MPLTEXT 1 0 35 "B:=[1,-504*sigma[5]( i)$i=1..n+1];\n" }{MPLTEXT 1 0 25 "C:=cauchyprod(A,A,n+2);\n" } {MPLTEXT 1 0 25 "A:=cauchyprod(A,C,n+2);\n" }{MPLTEXT 1 0 25 "B:=cauch yprod(B,B,n+2);\n" }{MPLTEXT 1 0 8 "C:=[];\n" }{MPLTEXT 1 0 47 "for i \+ to n+1 do C:=[op(C),A[i+1]-B[i+1]]; od;\n" }{MPLTEXT 1 0 24 "C:=cauchy quo(A,C,n+1);\n" }{MPLTEXT 1 0 29 "map(i->1728*i,[C[2..n+1]]);\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6(I \"cGF%I\"iGF%I\"jGF%I\"CGF%I\"AGF%I\"BGF%F%F%C+>F+7$\"\"\"-I\"$G%*prot ectedG6$,$*&\"$S#F0-&_I*numtheoryG6$F3I(_syslibGF%I&sigmaGF%6#\"\"$6#F (F0F0/F(;F0,&F$F0F0F0>F,7$F0-F26$,$*&\"$/&F0-&F:6#\"\"&FAF0!\"\"FB>F*- I+cauchyprodGF%6%F+F+,&F$F0\"\"#F0>F+-FS6%F+F*FU>F,-FS6%F,F,FU>F*7\"?( F(F0F0FDI%trueGF3>F*7$-I#opGF36#F*,&&F+6#,&F(F0F0F0F0&F,FboFP>F*-I*cau chyquoGF%6%F+F*FD-I$mapGF36$f*FAF%6$I)operatorGF%I&arrowGF%F%,$*&\"%G< F0F(F0F0F%F%F%7#&F*6#;FVFDF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 61 "# This procedure calculate a j-invarian t corresponding to a\n" }{MPLTEXT 1 0 64 "# reduced ideal given by a, \+ b, and D. The prescribed precision\n" }{MPLTEXT 1 0 63 "# is Dig decim al digits. The coefficients of the q-expansion \n" }{MPLTEXT 1 0 66 "# have to be given by the global list ccoeff. The length of this\n" } {MPLTEXT 1 0 36 "# vector is doubled, if necessary.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 71 "jinvariant:=proc(a,b,D, Dig) local olddig,q,r,qq,eps,i; global ccoeff;\n" }{MPLTEXT 1 0 38 "ol ddig:=Digits; Digits:=Dig;\n" }{MPLTEXT 1 0 57 "q:=evalf(exp(2 *Pi*I*(b+sqrt(-D))/2./a)); r:=1/q;\n" }{MPLTEXT 1 0 26 "qq:=1.; eps:=10.^(-Dig);\n" }{MPLTEXT 1 0 45 "for i while abs(ccoeff[i]*qq)>a bs(r)*eps do\n" }{MPLTEXT 1 0 32 " r:=r+ccoeff[i]*qq; qq:=qq*q;\n" } {MPLTEXT 1 0 55 " if i=nops(ccoeff) then ccoeff:=qexpansion(2*i); fi; \n" }{MPLTEXT 1 0 27 "od; Digits:=olddig; r; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"aG6\"I\"bGF%I\"DGF%I$DigGF%6(I'olddigGF%I\"qGF%I\" rGF%I#qqGF%I$epsGF%I\"iGF%F%F%C+>F*I'DigitsGF%>F2F(>F+-I&evalfG%*prote ctedG6#-I$expGF%6#*.\"\"#\"\"\"I#PiGF7F>^#F>F>,&F&F>-I%sqrtGF%6#,$F'! \"\"F>F>$F=\"\"!FFF$FF>F,*$F+FF>F-$F>FH>F.)$\"#5FH,$F(FF?(F/F>F>F%2*&- I$absGF76#F,F>F.F>-FV6#*&&I'ccoeffGF%6#F/F>F-F>C%>F,,&F,F>FZF>>F-*&F-F >F+F>@$/F/-I%nopsGF76#Ffn>Ffn-I+qexpansionGF%6#,$*&F=F>F/F>F>>F2F*F,F% FaoF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 66 "# This procedure calculate the Hilbert polynomial corresponding \n " }{MPLTEXT 1 0 65 "# to a discriminant -D. After all reduced ideals a re calculated\n" }{MPLTEXT 1 0 63 "# a preliminary calculation is done to obtain a bound for the\n" }{MPLTEXT 1 0 64 "# l_1-norm of the coef ficient vector of the result and log[10]\n" }{MPLTEXT 1 0 64 "# of thi s + Dig decimal digits will be the precision used. The\n" }{MPLTEXT 1 0 65 "# resulting polynomial of the global variable X and an estimate \n" }{MPLTEXT 1 0 69 "# of the error are given back. The coefficients \+ of the q-expansion \n" }{MPLTEXT 1 0 66 "# have to be given by the glo bal list ccoeff. The length of this\n" }{MPLTEXT 1 0 34 "# list is dou bled, if necessary.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 57 "hilbert:=proc(D,Dig) local olddig,DD,ll,L,i,H,HH,eps, c;\n" }{MPLTEXT 1 0 18 "global ccoeff,X;\n" }{MPLTEXT 1 0 30 "olddig:= Digits; Digits:=Dig;\n" }{MPLTEXT 1 0 48 "DD:=evalf(sqrt(D)); ll:=0; L :=allredideals(D);\n" }{MPLTEXT 1 0 64 "for i in L do ll:=ll+log[10.]( abs(exp(Pi*DD/i[1]))+2101.); od;\n" }{MPLTEXT 1 0 38 "Digits:=Dig+ceil (ll); H:=1.;\n" }{MPLTEXT 1 0 76 "for i in L do H:=expand(H*(X -jinvariant(i[1],i[2],D,Digits))); od;\n" }{MPLTEXT 1 0 17 "HH :=0; eps:=0.;\n" }{MPLTEXT 1 0 28 "for i from 0 to nops(L) do\n" } {MPLTEXT 1 0 41 " c:=coeff(H,X,i); HH:=HH+round(c)*X^i;\n" }{MPLTEXT 1 0 57 " if abs(c-round(c))>eps then eps:=abs(c-round(c)); fi;\n" } {MPLTEXT 1 0 32 "od; Digits:=olddig; HH,eps; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"DG6\"I$DigGF%6+I'olddigGF%I#DDGF%I#llGF%I\"LGF%I\" iGF%I\"HGF%I#HHGF%I$epsGF%I\"cGF%F%F%C0>F(I'DigitsGF%>F3F&>F)-I&evalfG %*protectedG6#-I%sqrtGF%6#F$>F*\"\"!>F+-I-allredidealsGF%FF*,&F*\"\"\"-&I$logGF%6#$\"#5F>6#,&-I$absGF86#-I$expGF%6#*(I#PiGF 8FFF)FF&F,6#FF!\"\"FF$\"%,@F>FFFF>F3,&F&FF-I%ceilGF%6#F*FF>F-$FFF>?&F, F+FC>F--I'expandGF86#*&F-FF,&I\"XGF%FF-I+jinvariantGF%6&FW&F,6#\"\"#F$ F3FYFF>F.F>>F/$F>F>?(F,F>FF-I%nopsGF86#F+FCC%>F0-I&coeffGF86%F-FdoF,>F .,&F.FF*&-I&roundGF%6#F0FF)FdoF,FFFF@$2F/-FP6#,&F0FFFjpFY>F/F`q>F3F(6$ F.F/F%6$I'ccoeffGF%FdoF%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }} {PARA 0 "" 0 "" {TEXT 201 37 " 8. Factoring the Hilbert polynomial" } }{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This procedure find the factorization \+ of the polynomial P of\n" }{MPLTEXT 1 0 67 "# the variable X modulo th e prime number p in the form of product\n" }{MPLTEXT 1 0 59 "# P_i^i, \+ where each P_i is square free. The list of P_i's\n" }{MPLTEXT 1 0 18 " # is given back.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 67 "squarefreefactor:=proc(P,p) local Pm,D,PP,L,LL,Q,R,i, j; global X;\n" }{MPLTEXT 1 0 14 "Pm:=P mod p;\n" }{MPLTEXT 1 0 41 "if degree(Pm)<=1 then RETURN([Pm]); fi;\n" }{MPLTEXT 1 0 23 "PP:=diff(Pm ,X) mod p;\n" }{MPLTEXT 1 0 14 "if PP=0 then\n" }{MPLTEXT 1 0 73 " fo r i from 0 while p*i<=degree(Pm) do PP:=PP+coeff(Pm,X,i*p)*X^i; od;\n" }{MPLTEXT 1 0 38 " LL:=squarefreefactor(PP,p); L:=[];\n" }{MPLTEXT 1 0 57 " for i to nops(LL) do L:=[op(L),0$j=1..p-1,LL[i]]; od;\n" } {MPLTEXT 1 0 14 " RETURN(L);\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 60 "D:=Gcd(Pm,PP) mod p; if degree(D)=0 then RETURN([Pm]); fi;\n" } {MPLTEXT 1 0 67 "Q:=Quo(Pm,D,X) mod p; PP:=Gcd(Q,D) mod p; Divide(Q,PP ,'R') mod p;\n" }{MPLTEXT 1 0 32 "[R,op(squarefreefactor(D,p))];\n" } {MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"PG6\"I\"p GF%6+I#PmGF%I\"DGF%I#PPGF%I\"LGF%I#LLGF%I\"QGF%I\"RGF%I\"iGF%I\"jGF%F% F%C,>F(-I$modGF%F#@$1-I'degreeG%*protectedG6#F(\"\"\"-I'RETURNGF96#7#F (>F*-F46$-I%diffGF96$F(I\"XGF%F&@$/F*\"\"!C'?(F/FIF;F%1*&F&F;F/F;F7>F* ,&F*F;*&-I&coeffGF96%F(FFFMF;)FFF/F;F;>F,-I1squarefreefactorGF%6$F*F&> F+7\"?(F/F;F;-I%nopsGF96#F,I%trueGF9>F+7%-I#opGF96#F+-I\"$GF96$FI/F0;F ;,&F&F;F;!\"\"&F,6#F/-F=F^o>F)-F46$-I$GcdGF%6$F(F*F&@$/-F86#F)FIF<>F-- F46$-I$QuoGF%6%F(F)FFF&>F*-F46$-F]p6$F-F)F&-F46$-I'DivideGF%6%F-F*.F.F &7$F.-F]o6#-FW6$F)F&F%6#FFF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 60 "# This procedure try to find a root of a p olynomial P of X\n" }{MPLTEXT 1 0 61 "# modulo p. The polynomial is kn own to be product of degree\n" }{MPLTEXT 1 0 59 "# 1 irreducible polyn omials. The parameter K is the limit\n" }{MPLTEXT 1 0 63 "# for the ra ndom tries. The root found or FAIL is given back.\n" }{MPLTEXT 1 0 3 " #\n" }{MPLTEXT 1 0 3 " \n" }{MPLTEXT 1 0 50 "modpolyroot:=proc(P,p,K) \+ local L,PP,PPP,i,r,T,D;\n" }{MPLTEXT 1 0 46 "PP:=1; r:=rand(p); L:=squ arefreefactor(P,p);\n" }{MPLTEXT 1 0 21 "for i to nops(L) do\n" } {MPLTEXT 1 0 14 " PPP:=L[i];\n" }{MPLTEXT 1 0 25 " if degree(PPP)>0 \+ then\n" }{MPLTEXT 1 0 65 " if degree(PP)=0 or degree(PP)>degree(PPP ) then PP:=PPP; fi;\n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 5 "od; \n" }{MPLTEXT 1 0 40 "if degree(PP)=0 then RETURN(false) fi;\n" } {MPLTEXT 1 0 23 "while degree(PP)>1 do\n" }{MPLTEXT 1 0 17 " for i to K do\n" }{MPLTEXT 1 0 75 " T:=0; T:=X+r(); T:=Powmod(T,(p-1)/2,PP, X) mod p; D:=Gcd(P,T+1) mod p;\n" }{MPLTEXT 1 0 50 " if degree(D)>0 and degree(D)K then RETURN(FAIL) fi;\n" } {MPLTEXT 1 0 44 "od; -coeff(PP,X,0)/coeff(PP,X,1) mod p; end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"PG6\"I\"pGF%I\"KGF%6)I\"LGF%I#PPG F%I$PPPGF%I\"iGF%I\"rGF%I\"TGF%I\"DGF%F%F%C)>F*\"\"\">F--I%randGF%6#F& >F)-I1squarefreefactorGF%6$F$F&?(F,F2F2-I%nopsG%*protectedG6#F)I%trueG F>C$>F+&F)6#F,@$2\"\"!-I'degreeGF>6#F+@$5/-FI6#F*FG2FHFN>F*F+@$FM-I'RE TURNGF>6#I&falseGF>?(F%F2F2F%2F2FNC$?(F,F2F2F'F@C'>F.FG>F.,&I\"XGF%F2- F-F%F2>F.-I$modGF%6$-I'PowmodGF%6&F.,&*&#F2\"\"#F2F&F2F2Fdo!\"\"F*FinF &>F/-F]o6$-I$GcdGF%6$F$,&F.F2F2F2F&@$32FG-FI6#F/2FapFNC$@%1Fap,$*&FdoF 2FNF2F2>F*F/>F*-F]o6$-I$QuoGF%6%F*F/FinF&[@$2F'F,-FT6#I%FAILGF>-F]o6$, $*&-I&coeffGF>6%F*FinFGF2-F[r6%F*FinF2FfoFfoF&F%F%F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 37 " 9. Set up t he curves and the points" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 70 "# This proced ure calculate a random point on a given elliptic curve \n" }{MPLTEXT 1 0 33 "# modulo n with parameters a,b.\n" }{MPLTEXT 1 0 4 "# \n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 44 "ellrandpoint:=proc(a,b,n) local \+ i,j,x,y,r;\n" }{MPLTEXT 1 0 20 "r:=rand(n); j:=-1;\n" }{MPLTEXT 1 0 28 "for i to 100 while j<>1 do\n" }{MPLTEXT 1 0 46 " x:=r(); j:=numth eory[jacobi](x^3+a*x+b,n);\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 51 "if i=100 then ERROR(`probably not a prime`,n) fi;\n" }{MPLTEXT 1 0 40 "y:=modsqrt(x^3+a*x+b mod n,n); j:=r();\n" }{MPLTEXT 1 0 49 "if j >n/2 then [x,y,1]; else [x,-y mod n,1]; fi;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"aG6\"I\"bGF%I\"nGF%6'I\"iGF%I\" jGF%I\"xGF%I\"yGF%I\"rGF%F%F%C)>F--I%randGF%6#F'>F*!\"\"?(F)\"\"\"F6\" $+\"0F*F6C$>F+-F-F%>F*-&I*numtheoryG6$%*protectedGI(_syslibGF%6#I'jaco biGF%6$,(*$)F+\"\"$F6F6*&F$F6F+F6F6F&F6F'@$/F)F7-I&ERRORGFA6$I5probabl y~not~a~primeGF%F'>F,-I(modsqrtGF%6$-I$modGF%FEF'>F*F;@%2,$*&#F6\"\"#F 6F'F6F6F*7%F+F,F67%F+-FV6$,$F,F4F'F6F%F%F%" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 26 " 10. Putting all together" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "interface(echo=3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 ";" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 53 "# This simple Maple routine calculates the function\n" }{MPLTEXT 1 0 47 "# L(x,a,b)=exp(b*(ln(x))^a*(ln(ln(x)))^(1-a))\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 61 "L:=proc(x,a,b) evalf( exp(b*(ln(x))^a*(ln(ln(x)))^(1-a))) end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"xG6\"I\"aGF%I\"bGF%F%F%F%-I&evalfG%*protectedG6#-I$expG6$F* I(_syslibGF%6#*(F'\"\"\")-I#lnGF.6#F$F&F2)-F56#F4,&F2F2F&!\"\"F2F%F%F% " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 41 "# Calculation of running time estimates\n" }{MPLTEXT 1 0 1 "#" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "D2:=n->m(ln(n))*d(n)/ln(d(n) )*rep(n);\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operato rGF%I&arrowGF%F%**-I\"mGF%6#-I#lnGF%F#\"\"\"-I\"dGF%F#F/-F.6#F0!\"\"-I $repGF%F#F/F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "D3:=n- >m(ln(n))*ln(ln(n))*d(n)/ln(d(n))*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operatorGF%I&arrowGF%F%*,-I\"mGF%6#-I#l nGF%F#\"\"\"-F.F,F/-I\"dGF%F#F/-F.6#F1!\"\"-I$repGF%F#F/F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "aa:=n->e(n)*b(n)*ln(n)*rep(n );" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operatorGF%I&arr owGF%F%**-I\"eGF%F#\"\"\"-I\"bGF%F#F,-I#lnGF%F#F,-I$repGF%F#F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "bb:=n->ln(e(n)*ln(n))*b(n )/e(n)/ln(n)*m(e(n)*ln(n))*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f* 6#I\"nG6\"F%6$I)operatorGF%I&arrowGF%F%*.-I#lnGF%6#*&-I\"eGF%F#\"\"\"- F+F#F0F0-I\"bGF%F#F0F.!\"\"F1F4-I\"mGF%F,F0-I$repGF%F#F0F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "cc:=n->0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operatorGF%I&arrowGF%F%\"\"!F%F%F%" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "dd:=n->e(n)*b(n)^(1/2)*m(ln (n))*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operat orGF%I&arrowGF%F%**-I\"eGF%F#\"\"\")-I\"bGF%F##F,\"\"#F,-I\"mGF%6#-I#l nGF%F#F,-I$repGF%F#F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "ee:=n->e(n)*m(ln(n))*L(b(n),sqrt(2))*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operatorGF%I&arrowGF%F%**-I\"eGF%F#\"\" \"-I\"mGF%6#-I#lnGF%F#F,-I\"LGF%6$-I\"bGF%F#-I%sqrtGF%6#\"\"#F,-I$repG F%F#F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "D6:=n->e(n) *ln(n)*m(ln(n))*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F %6$I)operatorGF%I&arrowGF%F%**-I\"eGF%F#\"\"\"-I#lnGF%F#F,-I\"mGF%6#F- F,-I$repGF%F#F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "A: =n->m(h(DD)*ln(n))*ln(n)*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6# I\"nG6\"F%6$I)operatorGF%I&arrowGF%F%*(-I\"mGF%6#*&-I\"hGF%6#I#DDGF%\" \"\"-I#lnGF%F#F2F2F3F2-I$repGF%F#F2F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "B:=n->m(g(DD)*ln(n))*ln(n)*rep(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operatorGF%I&arrowGF%F%*(-I\"mGF%6#* &-I\"gGF%6#I#DDGF%\"\"\"-I#lnGF%F#F2F2F3F2-I$repGF%F#F2F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "m:=x->x*ln(x)*ln(ln(x));" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F %*(F$\"\"\"-I#lnGF%F#F*-F,6#F+F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "L:=(x,beta)->exp(beta*((ln(x)*ln(ln(x)))^(1/2)));" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"xG6\"I%betaGF%F%6$I)operatorGF%I& arrowGF%F%-I$expGF%6#*&F&\"\"\")*&-I#lnGF%6#F$F.-F26#F1F.#F.\"\"#F.F%F %F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "rep:=n->ln(n)/ln(b(n ));" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"F%6$I)operatorGF%I&ar rowGF%F%*&-I#lnGF%F#\"\"\"-F+6#-I\"bGF%F#!\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "h:=x->x^(1/2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%*$)F$#\"\"\"\"\" #F,F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "g:=x->x^(1/2)/ ln(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I &arrowGF%F%*&)F$#\"\"\"\"\"#F,-I#lnGF%F#!\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "DD:=d(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 " *$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "d:=x->(ln(x))^2; e:=x->(d(x))^(1/2) ; b:=x->ln(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)oper atorGF%I&arrowGF%F%*$)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"#\"\"\"F%F %F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&ar rowGF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%-I#lnG6$%*protec tedGI(_syslibGF%F#F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" }{MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\" \"\"-F%6#-F%6#F$F--F%6#*$)F$\"\"#F-!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$F-- F%6#F.F--F%6#*$)F$\"\"#F-!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*$) -I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/ -F'6#F&!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*$)-I#lnG6$%*protecte dGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#-F'6#F&F/" }} {PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG6\"6 #I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#*&F#F/F&F/F/-F'6#F3F/-F'6#F&! \"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*.)*$)-I#lnG6$%*protectedGI(_sys libG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/-F'6#F$!\"\")F&\"\"$F/-F'6#*(F#F/F1F 3F&F/F/-F'6#F6F/-F'6#F&F3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "d:=x->(ln(x))^2; e:=x->(d(x))^(1/2); b:=x->ln(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%*$)-I#lnG6$% *protectedGI(_syslibGF%F#\"\"#\"\"\"F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%*$)-I\"dGF%F##\" \"\"\"\"#F.F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)o peratorGF%I&arrowGF%F%-I#lnG6$%*protectedGI(_syslibGF%F#F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" } {MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()-I #lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#-F%6#F$F--F%6# *$)F$\"\"#F-!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protec tedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$F--F%6#F.F--F%6#*$)F$\"\"# F-!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*$)-I#lnG6$%*protectedGI(_ syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#F&!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nG F+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#-F'6#F&F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\" \"#F/F.F/)F&\"\"$F/-F'6#*&F#F/F&F/F/-F'6#F3F/-F'6#F&!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*.)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+ \"\"#\"\"\"#F/F.F/-F'6#F$!\"\")F&\"\"$F/-F'6#*(F#F/F1F3F&F/F/-F'6#F6F/ -F'6#F&F3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "d:=x->(ln(x))^ 2; e:=x->(d(x))^(1/2); b:=x->(ln(x))^2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%*$)-I#lnG6$%*protectedGI( _syslibGF%F#\"\"#\"\"\"F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\" xG6\"F%6$I)operatorGF%I&arrowGF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" } }{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF% F%*$)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"#\"\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" }{MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*prot ectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$F--F%6#F.F-)-F%6#*$)F$\" \"#F-F7!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protectedGI (_syslibG6\"6#I\"nGF)\"\"%\"\"\")-F%6#F$\"\"#F--F%6#F/F-)-F%6#*$)F$F1F -F1!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*$)-I#lnG6$%*protectedGI( _syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"%F/-F'6#F$!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nG F+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#F&F/-F'6#F3F/-F'6#F$!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nG F+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#*&F#F/F&F/F/-F'6#F3F/-F'6#F$!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG6 \"6#I\"nGF+\"\"#\"\"\"#F/F.F/)-F'6#F$F.!\"\")F&\"\"$F/-F'6#*(F#F/F2F4F &F/F/-F'6#F7F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "b:=x->(ln (x))^2; e:=x->(d(x))^(1/2);\n" }{MPLTEXT 1 0 43 "b:=x->ln(x)^(ln(ln(x) )*ln(ln(ln(x)))^(-2));" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F% 6$I)operatorGF%I&arrowGF%F%*$)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"# \"\"\"F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operat orGF%I&arrowGF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%)-I#lnG6$%*prot ectedGI(_syslibGF%F#*&-F+6#F*\"\"\")-F+6#F0\"\"#!\"\"F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" } {MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)-I #lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$F--F%6#F.F-- F%6#*$)F$\"\"#F-!\"\"-F%6#)F$*&F.F-)F0F6F7F7" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\") -F%6#F$\"\"#F--F%6#F/F--F%6#*$)F$F1F-!\"\"-F%6#)F$*&F/F-)F2F1F8F8" }} {PARA 11 "" 1 "" {XPPMATH 20 "**)*$)-I#lnG6$%*protectedGI(_syslibG6\"6 #I\"nGF+\"\"#\"\"\"#F/F.F/)F&*&-F'6#F&F/)-F'6#F3F.!\"\"F/F%F/-F'6#F1F8 " }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG 6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#F&F/-F'6#F3F/-F'6#)F&*&F3 F/)F5F.!\"\"F<" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protec tedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#*&F#F/F&F/F /-F'6#F3F/-F'6#)F&*&-F'6#F&F/)-F'6#F " 0 "" {MPLTEXT 1 0 63 "d:=x->(ln(x))^2/(ln(ln(x)))^2; e:=x->(d(x))^(1/2); b:=x->ln(x);" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F %*&)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"#\"\"\")-F,6#F+F0!\"\"F%F%F% " }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrow GF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%-I#lnG6$%*protectedGI(_sysl ibGF%F#F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2( n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(a a(n));\n" }{MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand (A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\") -F%6#F$\"\"#!\"\"-F%6#F/F--F%6#*&)F$F1F-F.F2F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"- F%6#F$!\"\"-F%6#F.F--F%6#*&)F$\"\"#F-)F.F7F0F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*&)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\" \")-F'6#F&F.!\"\"#F/F.F/)F&\"\"$F/F1F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*&)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\")-F'6#F&F .!\"\"#F/F.F/)F&\"\"$F/-F'6#F1F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)* $)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$ F/-F'6#*&F#F/F&F/F/-F'6#F3F/-F'6#F&!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*.)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/ -F'6#F$!\"\")F&\"\"$F/-F'6#*(F#F/F1F3F&F/F/-F'6#F6F/-F'6#F&F3" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "d:=x->(ln(x))^2/(ln(ln(x)))^ 2; e:=x->(d(x))^(1/2);\n" }{MPLTEXT 1 0 28 "b:=x->(ln(x))^3/ln(ln(n))^ 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arr owGF%F%*&)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"#\"\"\")-F,6#F+F0!\"\" F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I &arrowGF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%*&)-I#lnG6$%*pro tectedGI(_syslibGF%F#\"\"$\"\"\")-F,6#-F,6#I\"nGF%F0!\"\"F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" } {MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)-I #lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$!\"\"-F%6#F. F--F%6#*&)F$\"\"#F-)F.F7F0F0-F%6#*&)F$\"\"$F-)F.F=F0F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\" \"\"-F%6#-F%6#F$F--F%6#*&)F$\"\"#F-)F0F6!\"\"F8-F%6#*&)F$\"\"$F-)F0F=F 8F8" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)*&)-I#lnG6$%*protectedGI(_sysl ibG6\"6#I\"nGF+\"\"#\"\"\")-F'6#F&F.!\"\"#F/F.F/)F&\"\"&F/)F1\"\"$F3-F '6#*&)F&F8F/F7F3F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*&)-I#lnG6$%*pr otectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\")-F'6#F&F.!\"\"#F/F.F/)F&\"\" $F/F1F/-F'6#F1F/-F'6#*&F5F/)F1F6F3F3" }}{PARA 11 "" 1 "" {XPPMATH 20 " *,)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F& \"\"$F/-F'6#*&F#F/F&F/F/-F'6#F3F/-F'6#*&F1F/)-F'6#F&F2!\"\"F>" }} {PARA 11 "" 1 "" {XPPMATH 20 "*.)*$)-I#lnG6$%*protectedGI(_syslibG6\"6 #I\"nGF+\"\"#\"\"\"#F/F.F/-F'6#F$!\"\")F&\"\"$F/-F'6#*(F#F/F1F3F&F/F/- F'6#F6F/-F'6#*&F4F/)-F'6#F&F5F3F3" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "d:=x->(ln(x))^2/(ln(ln(x)))^2; e:=x->(d(x))^(1/2); b: =x->(ln(x))^2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)oper atorGF%I&arrowGF%F%*&)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"#\"\"\")-F ,6#F+F0!\"\"F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I) operatorGF%I&arrowGF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" }}{PARA 11 " " 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%*$)-I#lnG 6$%*protectedGI(_syslibGF%F#\"\"#\"\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n) );\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" }{MPLTEXT 1 0 16 "expand(D6( n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B( n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)-I#lnG6$%*protectedGI(_syslib G6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$!\"\"-F%6#F.F--F%6#*&)F$\"\"#F-)F.F7F0F 0-F%6#*$F6F-F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protected GI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#-F%6#F$F--F%6#*&)F$\"\"#F-)F0F6 !\"\"F8-F%6#*$F5F-F8" }}{PARA 11 "" 1 "" {XPPMATH 20 "*()*&)-I#lnG6$%* protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\")-F'6#F&F.!\"\"#F/F.F/)F&\" \"%F/-F'6#*$F%F/F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*&)-I#lnG6$%*pr otectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\")-F'6#F&F.!\"\"#F/F.F/)F&\"\" $F/F1F/-F'6#F1F/-F'6#*$F%F/F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)- I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/- F'6#*&F#F/F&F/F/-F'6#F3F/-F'6#F$!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)-F '6#F$F.!\"\")F&\"\"$F/-F'6#*(F#F/F2F4F&F/F/-F'6#F7F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "d:=x->(ln(x))^2/(ln(ln(x)))^2; e:=x->(d(x ))^(1/2);\n" }{MPLTEXT 1 0 43 "b:=x->ln(x)^(ln(ln(x))*ln(ln(ln(x)))^(- 2));" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&a rrowGF%F%*&)-I#lnG6$%*protectedGI(_syslibGF%F#\"\"#\"\"\")-F,6#F+F0!\" \"F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF %I&arrowGF%F%*$)-I\"dGF%F##\"\"\"\"\"#F.F%F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%)-I#lnG6$%*prote ctedGI(_syslibGF%F#*&-F+6#F*\"\"\")-F+6#F0\"\"#!\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(D2(n));\n" }{MPLTEXT 1 0 16 "expand(D3(n));\n" }{MPLTEXT 1 0 16 "expand(aa(n));\n" }{MPLTEXT 1 0 16 "expand(D6(n));\n" }{MPLTEXT 1 0 15 "expand(A(n));\n" }{MPLTEXT 1 0 13 "expand(B(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)-I#lnG6$%*prot ectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#F$!\"\"-F%6#F.F--F%6#*&)F$ \"\"#F-)F.F7F0F0-F%6#)F$*&F.F-)F1F7F0F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "**)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF)\"\"%\"\"\"-F%6#-F%6# F$F--F%6#*&)F$\"\"#F-)F0F6!\"\"F8-F%6#)F$*&F0F-)F.F6F8F8" }}{PARA 11 " " 1 "" {XPPMATH 20 "**)*&)-I#lnG6$%*protectedGI(_syslibG6\"6#I\"nGF+\" \"#\"\"\")-F'6#F&F.!\"\"#F/F.F/)F&*&F1F/)-F'6#F1F.F3F/F%F/-F'6#F5F3" } }{PARA 11 "" 1 "" {XPPMATH 20 "*,)*&)-I#lnG6$%*protectedGI(_syslibG6\" 6#I\"nGF+\"\"#\"\"\")-F'6#F&F.!\"\"#F/F.F/)F&\"\"$F/F1F/-F'6#F1F/-F'6# )F&*&F1F/)F7F.F3F3" }}{PARA 11 "" 1 "" {XPPMATH 20 "*,)*$)-I#lnG6$%*pr otectedGI(_syslibG6\"6#I\"nGF+\"\"#\"\"\"#F/F.F/)F&\"\"$F/-F'6#*&F#F/F &F/F/-F'6#F3F/-F'6#)F&*&-F'6#F&F/)-F'6#F " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 21 " 11. Testing a proof" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 47 "# The following procedure has as input a list\n" }{MPLTEXT 1 0 61 "# [n,a,b,x,y,s,n1,a1,b1,x1,y1,s1,..,nn], and checks whether\n" } {MPLTEXT 1 0 61 "# this list represents a \"partial proof\" of the pri mality\n" }{MPLTEXT 1 0 59 "# of n, i.e. a proof with elliptic curves \+ that if nn is a\n" }{MPLTEXT 1 0 64 "# prime then n is a prime, too. T he steps are to check whether\n" }{MPLTEXT 1 0 67 "# n_i is a prime if n_\{i+1\} is a prime. This consist of cheking\n" }{MPLTEXT 1 0 57 "# \+ that a_i, b_i are the parameters of an elliptic curve\n" }{MPLTEXT 1 0 60 "# modulo n_i, the point P=(x_i,y_i,1) is on this elliptic\n" } {MPLTEXT 1 0 66 "# curve, that Q=(m_i/n_\{i+1\})*P<>0 and n_\{i+1\}*Q= 0, the zero\n" }{MPLTEXT 1 0 60 "# of the elliptic curve. Here m_i, th e cardinality of the \n" }{MPLTEXT 1 0 32 "# elliptic curve is n_i+1+s _i.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 52 "pa rtialproof:=proc(PP) local i,n,a,b,P,Q,x,y,m,np;\n" }{MPLTEXT 1 0 45 " if not type(LL,list) then RETURN(false) fi;\n" }{MPLTEXT 1 0 45 "if no ps(PP) mod 6<>1 then RETURN(false) fi;\n" }{MPLTEXT 1 0 22 "for i to n ops(LL) do\n" }{MPLTEXT 1 0 55 " if not type(LL[i],nonnegint) then RE TURN(false) fi;\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 32 "for i by \+ 6 while i1 t hen RETURN(false); fi;\n" }{MPLTEXT 1 0 27 " a:=PP[i+1]; b:=PP[i+2]; \n" }{MPLTEXT 1 0 52 " if gcd(n,4*a^3+27*b^2)>1 then RETURN(false); f i;\n" }{MPLTEXT 1 0 27 " x:=PP[i+3]; y:=PP[i+4];\n" }{MPLTEXT 1 0 52 " if y^2-x^3-a*x-b mod n<>0 then RETURN(false) fi;\n" }{MPLTEXT 1 0 44 " P:=[x,y,1]; m:=n+1+PP[i+5]; np:=PP[i+6];\n" }{MPLTEXT 1 0 28 " \+ P:=ellmul(P,m/np,a,b,n);\n" }{MPLTEXT 1 0 38 " if P[3]<>1 then RETURN (false); fi;\n" }{MPLTEXT 1 0 26 " P:=ellmul(P,np,a,b,n);\n" } {MPLTEXT 1 0 38 " if P[3]<>0 then RETURN(false); fi;\n" }{MPLTEXT 1 0 14 "od; true; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I#PPG6\"6,I \"iGF%I\"nGF%I\"aGF%I\"bGF%I\"PGF%I\"QGF%I\"xGF%I\"yGF%I\"mGF%I#npGF%F %F%C'@$4-I%typeG%*protectedG6$I#LLGF%I%listGF6-I'RETURNGF66#I&falseGF6 @$0-I$modGF%6$-I%nopsGF6F#\"\"'\"\"\"F:?(F'FFFF-FD6#F8I%trueGF6@$4-F56 $&F86#F'I*nonnegintGF6F:?(F'FFFEF%2F'FCC1>F(&F$FP@$2FF-I$gcdGF%6$F(FEF :>F)&F$6#,&F'FFFFFF>F*&F$6#,&F'FF\"\"#FF@$2FF-FZ6$F(,&*&\"\"%FF)F)\"\" $FFFF*&\"#FFF)F*F^oFFFFF:>F-&F$6#,&F'FFFgoFF>F.&F$6#,&F'FFFeoFF@$0-FA6 $,**$)F.F^oFFFF*$)F-FgoFF!\"\"*&F)FFF-FFF\\qF*F\\qF(\"\"!F:>F+7%F-F.FF >F/,(F(FFFFFF&F$6#,&F'FF\"\"&FFFF>F0&F$6#,&F'FFFEFF>F+-I'ellmulGF%6'F+ *&F/FFF0F\\qF)F*F(@$0&F+6#FgoFFF:>F+-F]r6'F+F0F)F*F(@$0FbrF^qF:FJF%F%F %" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 47 " # The following procedure has as input a list\n" }{MPLTEXT 1 0 61 "# [ n,a,b,x,y,s,n1,a1,b1,x1,y1,s1,..,nn], and checks whether\n" }{MPLTEXT 1 0 59 "# this list represents a proof of the primality of n with\n" } {MPLTEXT 1 0 59 "# elliptic curves. First the primality of nn checked \+ with\n" }{MPLTEXT 1 0 61 "# trial division. Then the procedure partial proof is called\n" }{MPLTEXT 1 0 26 "# to complete the proof.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 29 "proof:=pro c(PP) local i,nn;\n" }{MPLTEXT 1 0 45 "if not type(LL,list) then RETUR N(false) fi;\n" }{MPLTEXT 1 0 45 "if nops(PP) mod 6<>1 then RETURN(fal se) fi;\n" }{MPLTEXT 1 0 60 "if not type(LL[nops(LL)],nonnegint) then \+ RETURN(false) fi;\n" }{MPLTEXT 1 0 19 "nn:=PP[nops(PP)];\n" }{MPLTEXT 1 0 41 "if type(nn,even) then RETURN(false) fi;\n" }{MPLTEXT 1 0 36 "f or i from 3 by 2 while i*i<=nn do\n" }{MPLTEXT 1 0 40 " if nn mod i=0 then RETURN(false) fi;\n" }{MPLTEXT 1 0 26 "od; partialproof(PP); end ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I#PPG6\"6$I\"iGF%I#nnGF%F%F%C)@ $4-I%typeG%*protectedG6$I#LLGF%I%listGF.-I'RETURNGF.6#I&falseGF.@$0-I$ modGF%6$-I%nopsGF.F#\"\"'\"\"\"F2@$4-F-6$&F06#-F<6#F0I*nonnegintGF.F2> F(&F$6#F;@$-F-6$F(I%evenGF.F2?(F'\"\"$\"\"#F%1*&F'F>F'F>F(@$/-F96$F(F' \"\"!F2-I-partialproofGF%F#F%F%F%" }}}}{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 16 "13. Az AKS-teszt" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "14. A szita m\303\263dszerek alapjai" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 25 "15. Sz\303\241mtest szit a" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "16. Vegyes probl" }{TEXT 205 8 "\303\251" }{TEXT 205 1 "m" } {TEXT 205 8 "\303\241" }{TEXT 205 1 "k" }}}{EXCHG {PARA 206 "> " 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 }