{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 3 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 2 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 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "List Item" -1 14 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Wa rning" -1 7 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier" 1 12 255 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Fixed Width" -1 17 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "He ading 1" -1 3 1 {CSTYLE "" -1 -1 "MS Serif" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 2" -1 204 1 {CSTYLE "" -1 -1 "Times " 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 36 2 0 2 2 -1 1 } {CSTYLE "Equation Label" -1 200 "Courier" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Text" -1 201 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Page Number" -1 33 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Maple Input" -1 0 "Courier" 1 12 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Output" -1 20 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 0 0 0 1 }{CSTYLE "Dictionary Hyperlink" -1 45 "MS Serif" 1 12 147 0 15 1 2 2 1 2 2 2 0 0 0 1 }{CSTYLE "2D Input" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 202 "Courier" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "MS Serif" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }{PSTYLE "" -1 205 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 206 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 207 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 208 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 209 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 210 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 211 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 212 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 213 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 214 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 215 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 216 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 217 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 218 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 219 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "" -1 220 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" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 64 "3. Egyszer\305\261 p r\303\255mtesztel\303\251si m\303\263dszerek" }}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 18 "4. \+ Lucas-sorozatok" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 23 "5. Alkalmaz \303\241sok " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "6. Sz\303\241mok \303\251s polinomok" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 45 "7. Gyors F ourier-transzform\303\241ci\303\263" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 38 "8. Elliptikus f\303\274ggv\30 3\251nyek" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "9. Sz\303\241mol\3 03\241s elliptikus g\303\266rb\303\251ken" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 65 "10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\30 3\251kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 64 "# This routine randomly choose an elliptic \"c urve\" modulo n,\n" }{MPLTEXT 1 0 53 "# where gcd(n,6)=1. The coordina tes x,y are choosen\n" }{MPLTEXT 1 0 55 "# randomly, the parameter a t oo, 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:=proc(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\"bGF%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)F4F'F4FFF$>F,-F=6$,&*&\"\"%F4)F)FEF 4F4*&\"#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 \"curve\" modulo n, where gcd(n,6)=1.\n" }{MPLTEXT 1 0 61 "# P and Q are the points to add and a,b are the par ameters.\n" }{MPLTEXT 1 0 66 "# The return value is the sum of the poi nts or a divisor d of n.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 36 "elladd:=proc(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) f i;\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 1 F,-I'igcdexGF%6%,&FAFCFD!\"\"F).F+@$32FCF ,2F,F)OF,>F+-I$modGF%6$*&,&&F$6#\"\"#FC&F&FZFLFCF+FCF)-FU6$,(*$)F+FenF CFCFAFLFDFLF)7%I\"%GF%-FU6$,&*&F+FC,&FAFCF]oFLFCFCFYFLF)FCF%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 65 "# Doub ling on an elliptic \"curve\" 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 return value is the double of the point P or\n" }{MPLTEXT 1 0 21 "# a divisor 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;F8F;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 divisor 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 binary 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:=c onvert(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 " if type(Q,integer) then return Q f i;\n" }{MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 11 "od; Q; end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"PG6\"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+F 4F4!\"\"FHF4I%trueGF>C%>F--I'elldouGF%6&F-F'F(F)@$-I%typeGF>6$F-I(inte gerGF>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 49 "# This program compute k*P on an elliptic curve\n" }{MPLTEXT 1 0 64 "# with \+ parameters a,b mod n, where k=k(s,B) is the product of \n" }{MPLTEXT 1 0 53 "# all prime-powers p^ep for which p<=s and p^ep<=B.\n" } {MPLTEXT 1 0 50 "# B is roughly the bound for the prime factor we\n" } {MPLTEXT 1 0 66 "# try to found. Usually s is some hundred and B is so me million.\n" }{MPLTEXT 1 0 51 "# If a divisor d of n found then d is given back.\n" }{MPLTEXT 1 0 31 "# We suppose that gcd(n,6)=1.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 44 "elltry:=pr oc(P,s,B,a,b,n) local lB,p,ep,Q;\n" }{MPLTEXT 1 0 25 "Q:=P; lB:=evalf( ln(B));\n" }{MPLTEXT 1 0 22 "for p from 2 to s do\n" }{MPLTEXT 1 0 22 " if isprime(p) then\n" }{MPLTEXT 1 0 33 " ep:=floor(lB/evalf(ln(p )));\n" }{MPLTEXT 1 0 30 " Q:=ellmul(Q,p^ep,a,b,n);\n" }{MPLTEXT 1 0 42 " if type(Q,integer) then return Q fi;\n" }{MPLTEXT 1 0 7 " f i;\n" }{MPLTEXT 1 0 11 "od; Q; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f *6(I\"PG6\"I\"sGF%I\"BGF%I\"aGF%I\"bGF%I\"nGF%6&I#lBGF%I\"pGF%I#epGF%I \"QGF%F%F%C&>F/F$>F,-I&evalfG%*protectedG6#-I#lnGF%6#F'?(F-\"\"#\"\"\" F&I%trueGF5@$-I(isprimeGF%6#F-C%>F.-I&floorGF%6#*&F,F<-F46#-F8FA!\"\"> F/-I'ellmulGF%6'F/)F-F.F(F)F*@$-I%typeGF56$F/I(integerGF5OF/F/F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 52 "# T his program try to split an integer n with the \n" }{MPLTEXT 1 0 58 "# elliptic curve method. The parameters are chosen to be\n" }{MPLTEXT 1 0 39 "# optimal to find prime factors below\n" }{MPLTEXT 1 0 50 "# P with probability 1-p. Better to remove first\n" }{MPLTEXT 1 0 55 "# s mall prime divisors. A factor found is given back.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 46 "ellsplit:=proc(n,P,p) loc al d,B,s,K,i,a,b,Q;\n" }{MPLTEXT 1 0 36 "if isprime(n) then RETURN([n] ) fi;\n" }{MPLTEXT 1 0 26 "B:=ceil(P+2.*sqrt(P)+1);\n" }{MPLTEXT 1 0 41 "s:=evalf(exp(sqrt(ln(P)*ln(ln(P))/2)));\n" }{MPLTEXT 1 0 20 "s:=ce il(max(3,s));\n" }{MPLTEXT 1 0 27 "K:=ceil(max(3,-s*ln(p)));\n" } {MPLTEXT 1 0 16 "for i to K do;\n" }{MPLTEXT 1 0 18 " d:=ellrand(n); \n" }{MPLTEXT 1 0 37 " if type(d,integer) then break fi;\n" }{MPLTEXT 1 0 39 " Q:=[d[1],d[2],1]; a:=d[3]; b:=d[4];\n" }{MPLTEXT 1 0 27 " \+ d:=elltry(Q,s,B,a,b,n);\n" }{MPLTEXT 1 0 37 " if type(d,integer) then break fi;\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 41 "if type(d,inte ger) then d else 1 fi; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"nG 6\"I\"PGF%I\"pGF%6*I\"dGF%I\"BGF%I\"sGF%I\"KGF%I\"iGF%I\"aGF%I\"bGF%I \"QGF%F%F%C)@$-I(isprimeGF%6#F$-I'RETURNG%*protectedG6#7#F$>F*-I%ceilG F%6#,(F&\"\"\"*&$\"\"#\"\"!F@-I%sqrtGF%6#F&F@F@F@F@>F+-I&evalfGF86#-I$ expGF%6#-FF6#,$*(#F@FCF@-I#lnGF%FGF@-FU6#FTF@F@>F+-F=6#-I$maxGF86$\"\" $F+>F,-F=6#-Ffn6$Fhn,$*&F+F@-FU6#F'F@!\"\"?(F-F@F@F,I%trueGF8C)>F)-I(e llrandGF%F5@$-I%typeGF86$F)I(integerGF8[>F07%&F)6#F@&F)6#FCF@>F.&F)6#F hn>F/&F)6#\"\"%>F)-I'elltryGF%6(F0F+F*F.F/F$Fio@%FjoF)F@F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "ellsplit(1001,20,0.001);" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#8" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "10.1. K" }{TEXT 206 39 "\303\266tegelt v\303\251grehajt\303\241 " }{TEXT 206 2 "s." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 66 "# Batch modular inver se modulo n for all L[i] or a divisor of n.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 44 "batchmodinv:=proc(L,n) local i,l ,d,LL,LLL;\n" }{MPLTEXT 1 0 19 "if nops(L)=1 then\n" }{MPLTEXT 1 0 26 " d:=igcdex(L[1],n,'l');\n" }{MPLTEXT 1 0 28 " if 1F *-I'igcdexGF%6%&F$6#F3F&.F)@$2F3F*OF*7#F)C,>F+7\">F(F3?(F%F3F3F%1F(F/C $@%/F(F/>F+7$-I#opGF16#F+-I$modGF%6$&F$6#F(F&>F+7$FK-FO6$*&FQF3&F$6#,& F(F3F3F3F3F&>F(,&F(F3\"\"#F3>F+-I,modinvbatchGF%6$F+F&@$-I%typeGF16$F+ I(integerGF1OF+FD>F,FBFC?(F%F3F3F%FEC$@%FH>F,7$-FL6#F,&F+6#,&*&#F3FgnF 3F(F3F3F^p!\"\">F,7%Fho-FO6$*&FXF3FjoF3F&-FO6$*&FQF3FjoF3F&FenF,F%F%F% " }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 11 "10.2. Szorz" }{TEXT 206 8 "\303\241" }{TEXT 206 4 "s eg" }{TEXT 206 15 "\303\251szekkel" }{TEXT 206 1 "." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{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 61 "# x is the first coordinate of the point to double and a, b\n" }{MPLTEXT 1 0 68 "# are the parameters. The return value is either a list, the first\n" } {MPLTEXT 1 0 62 "# coordinate of the double of the point or a divisor \+ d of n.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 35 "ellxdou:=proc(x,a,b,n) local l,d;\n" }{MPLTEXT 1 0 33 "d:=igcdex(4 *(x^3+a*x+b),n,'l');\n" }{MPLTEXT 1 0 52 "if 1F +-I'igcdexGF%6%,(*&\"\"%\"\"\")F$\"\"$F4F4*(F3F4F&F4F$F4F4*&F3F4F'F4F4 F(.F*@%2F4F+F+7#-I$modGF%6$*&F*F4,&*$),&*$)F$\"\"#F4F4F&!\"\"FGF4F4*( \"\")F4F'F4F$F4FHF4F(F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 50 "# Calculation of the triple of first coordin ates\n" }{MPLTEXT 1 0 54 "# [x,x_2i,x_2i+1] if t=0 or [x,x_2i+1,x_2i+2 ] if t=1\n" }{MPLTEXT 1 0 54 "# from the triple of first coordinates [ x,x_i,x_i+1]\n" }{MPLTEXT 1 0 65 "# on an elliptic \"curve\" modulo n, where gcd(n,6)=1, and a, b\n" }{MPLTEXT 1 0 53 "# are the parameters. The return value is this list\n" }{MPLTEXT 1 0 24 "# or a divisor d o f n.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 56 "e llnextx:=proc(L,t,a,b,n) local l,d,x,xi,xip,xii,xiip;\n" }{MPLTEXT 1 0 31 "x:=L[1]; xi:=L[2]; xip:=L[3];\n" }{MPLTEXT 1 0 13 "if t=0 then\n " }{MPLTEXT 1 0 37 " d:=igcdex(4*(xi^3+a*xi+b),n,'l');\n" }{MPLTEXT 1 0 28 " if 1F-&F$6#\"\"\">F.&F$6#\"\"#>F/&F$6#\" \"$@%/F&\"\"!C(>F,-I'igcdexGF%6%,(*&\"\"%F6)F.F>F6F6*(FIF6F'F6F.F6F6*& FIF6F(F6F6F).F+@$2F6F,OF,>F0-I$modGF%6$*&F+F6,&*$),&*$)F.F:F6F6F'!\"\" F:F6F6*(\"\")F6F(F6F.F6FfnF6F)>F,-FE6%*&F-F6),&F.F6F/FfnF:F6F)FMFN>F1- FS6$*&F+F6,&*$),&F'F6*&F.F6F/F6FfnF:F6F6*(FIF6F(F6,&F.F6F/F6F6FfnF6F)C (FinFN>F0F`o>F,-FE6%,(*&FIF6)F/F>F6F6*(FIF6F'F6F/F6F6FLF6F)FMFN>F1-FS6 $*&F+F6,&*$),&*$)F/F:F6F6F'FfnF:F6F6*(FhnF6F(F6F/F6FfnF6F)7%F-F0F1F%F% F%" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "10.3. Projekt" }{TEXT 206 8 "\303\255" }{TEXT 206 11 "v reprezent" }{TEXT 206 8 "\303\241" } {TEXT 206 2 "ci" }{TEXT 206 8 "\303\263" }{TEXT 206 1 "." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 65 "# Doubling on an elliptic \"curve\" modulo n, where g cd(n,6)=1.\n" }{MPLTEXT 1 0 60 "# x, z are the coordinates of the poin t to double and a, b\n" }{MPLTEXT 1 0 55 "# are the parameters. The re turn value is a list, the\n" }{MPLTEXT 1 0 43 "# coordinates of the do uble of the point.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 27 "ellxzdou:=proc(x,z,a,b,n)\n" }{MPLTEXT 1 0 63 "[(x^2- a*z^2)^2-8*b*x*z^3 mod n,4*z*(x^3+a*x*z^2+b*z^3) mod n]\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"xG6\"I\"zGF%I\"aGF %I\"bGF%I\"nGF%F%F%F%7$-I$modGF%6$,&*$),&*$)F$\"\"#\"\"\"F5*&F'F5)F&F4 F5!\"\"F4F5F5**\"\")F5F(F5F$F5)F&\"\"$F5F8F)-F,6$,$*(\"\"%F5F&F5,(*$)F $F \+ " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 44 "# Calculation of the tri ple of coordinates\n" }{MPLTEXT 1 0 46 "# [[x,z],[x_2i,z_2i],[x_2i+1,z _2i+1]] if t=0\n" }{MPLTEXT 1 0 53 "# or [[x,z],[x_2i+1,z_2i+1],[x_2i+ 2,z_2i+2]] if t=1\n" }{MPLTEXT 1 0 66 "# from the triple of coordinate s [[x,z],[x_i,z_i],[x_i+1,z_i+1]]\n" }{MPLTEXT 1 0 66 "# on an ellipti c \"curve\" modulo n, where igcd(n,6)=1, and a, b\n" }{MPLTEXT 1 0 54 "# are the parameters. The return value is this list.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 75 "ellnextxz:=proc(L,t,a ,b,n) local l,d,x,z,xi,zi,xip,zip,xii,zii,xiip,ziip;\n" }{MPLTEXT 1 0 25 "x:=L[1][1]; z:=L[1][2];\n" }{MPLTEXT 1 0 55 "xi:=L[2][1]; zi:=L[2] [2]; xip:=L[3][1]; zip:=L[3][2];\n" }{MPLTEXT 1 0 13 "if t=0 then\n" } {MPLTEXT 1 0 43 " xii:=(xi^2-a*zi^2)^2-8*b*xi*zi^3 mod n;\n" } {MPLTEXT 1 0 44 " zii:=4*zi*(xi^3+a*xi*zi^2+b*zi^3) mod n;\n" } {MPLTEXT 1 0 67 " xiip:=z*((xi*xip-a*zi*zip)^2-4*b*zi*zip*(xi*zip+xip *zi)) mod n;\n" }{MPLTEXT 1 0 36 " ziip:=x*(xip*zi-xi*zip)^2 mod n;\n " }{MPLTEXT 1 0 6 "else\n" }{MPLTEXT 1 0 66 " xii:=z*((xi*xip-a*zi*zi p)^2-4*b*zi*zip*(xi*zip+xip*zi)) mod n;\n" }{MPLTEXT 1 0 35 " zii:=x* (xip*zi-xi*zip)^2 mod n;\n" }{MPLTEXT 1 0 48 " xiip:=(xip^2-a*zip^2)^ 2-8*b*xip*zip^3 mod n;\n" }{MPLTEXT 1 0 50 " ziip:=4*zip*(xip^3+a*xip *zip^2+b*zip^3) mod n;\n" }{MPLTEXT 1 0 38 "fi; [[x,z],[xii,zii],[xiip ,ziip]] end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6'I\"LG6\"I\"tGF%I\"aG F%I\"bGF%I\"nGF%6.I\"lGF%I\"dGF%I\"xGF%I\"zGF%I#xiGF%I#ziGF%I$xipGF%I$ zipGF%I$xiiGF%I$ziiGF%I%xiipGF%I%ziipGF%F%F%C*>F-&&F$6#\"\"\"F;>F.&F:6 #\"\"#>F/&&F$F?F;>F0&FCF?>F1&&F$6#\"\"$F;>F2&FHF?@%/F&\"\"!C&>F3-I$mod GF%6$,&*$),&*$)F/F@FF4-FS6$,$*(\"\"%FF5-FS6$*&F.F<,&*$),&*&F/FF6-FS6$*&F-F<),&FcpF< FbpFgnF@FF3Fgo>F4Fep>F5-FS6$,&*$),&*$)F1F@FF6-FS6$,$*(F`oF " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 52 "# This progra m compute k*P, k>=0 or a divisor of n\n" }{MPLTEXT 1 0 64 "# for a lis t of elliptic \"curve\" modulo n, where gcd(n,6)=1.\n" }{MPLTEXT 1 0 43 "# It use the left-to-right binary method,\n" }{MPLTEXT 1 0 48 "# p rojective representation, and backtracking.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 62 "batchellmuls:=proc(L,k,n) local \+ LL,LLL,LLLL,a,b,i,j,P,B,d,l;\n" }{MPLTEXT 1 0 34 "if k=0 then return L fi; LL:=[];\n" }{MPLTEXT 1 0 21 "for i to nops(L) do\n" }{MPLTEXT 1 0 27 " a:=L[i][2]; b:=L[i][3];\n" }{MPLTEXT 1 0 33 " P:=ellxzdou(L[i ][1],1,a,b,n);\n" }{MPLTEXT 1 0 51 " P:=[[L[i][1],1],[L[i][1],1],P,L[ i][2],L[i][3]];\n" }{MPLTEXT 1 0 19 " LL:=[op(LL),P];\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 23 "B:=convert(k,base,2);\n" }{MPLTEXT 1 0 36 "for j from nops(B)-1 to 1 by -1 do\n" }{MPLTEXT 1 0 20 " LLL:=LL; LL:=[];\n" }{MPLTEXT 1 0 25 " for i to nops(LLL) do\n" }{MPLTEXT 1 0 50 " P:=LLL[i][1..3]; a:=LLL[i][4]; b:=LLL[i][5];\n" }{MPLTEXT 1 0 33 " P:=ellnextxz(P,B[j],a,b,n);\n" }{MPLTEXT 1 0 31 " LL:=[op (LL),[op(P),a,b]];\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 14 "od; \+ LLL:=[];\n" }{MPLTEXT 1 0 53 "for i to nops(LL) do LLL:=[op(LLL),LL[i] [2][2]] od;\n" }{MPLTEXT 1 0 26 "LLL:=batchmodinv(LLL,n);\n" }{MPLTEXT 1 0 27 "if type(LLL,integer) then\n" }{MPLTEXT 1 0 40 " if LLLF)7\"?(F.\"\"\"F<-I%nopsG%*protectedG6#F$I%trueGF?C'>F,&&F$6# F.6#\"\"#>F-&FE6#\"\"$>F0-I)ellxzdouGF%6'&FE6#FF07'7$FQFF)7$-I#opGF?6#F)F0>F1-I(convertGF?6%F&I%baseGF%FH?(F/,&-F>6#F1F< FF*F)F9?(F.F6#F*FAC'>F0&&F*FF6#;FF,&Fgo6#\" \"%>F-&Fgo6#\"\"&>F0-I*ellnextxzGF%6'F0&F16#F/F,F-F'>F)7$FX7%-FY6#F0F, F->F*F:?(F.FFZFA>F*7$-FYFco&&&F)FFFGFG>F*-I,batchmodinvGF%6$F*F' @%-I%typeGF?6$F*I(integerGF?C&@$2F*F'OF*F9?(F.FF2-I'ig cdexGF%6%&F0FGF'.F3@%2FF07%FUFU7$-I$modGF%6$*&F3F<&F0F RFF2-Fgr6%&FirFGF'Fjr@%F\\s@%F^sF_s[C$>&FirFR -Fes6$*(F3FF^tF&&F0FKFR-Fes6$*&F3F&F]uFGF<@$/F2F'F`s>F)7$FX7%FdtF,F->F+F)C$>F+F:?(F.FF0-Fe s6$*&&FdqFRFF,&FeqF\\p>F-&FeqF`p>F+7$-FY6#F+7%F0F,F-F+F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 59 "# \+ This procedure is elliptic curve method with projective\n" }{MPLTEXT 1 0 62 "# representation for factorization of n. It use K \"curves\"\n " }{MPLTEXT 1 0 59 "# parallel and only after all step of a multiplica tion is\n" }{MPLTEXT 1 0 43 "# done an igcd operation. If no success, \n" }{MPLTEXT 1 0 66 "# backtracking is used for each curves separatel y. Unsuccessful\n" }{MPLTEXT 1 0 50 "# curves are \"killed\" from the list of curves.\n" }{MPLTEXT 1 0 56 "# The prime powers up to P are c onsidered so that they\n" }{MPLTEXT 1 0 57 "# are not less then the bo und B. The result is the list\n" }{MPLTEXT 1 0 58 "# of triples [x,a,b ], where x is the first coordinate of\n" }{MPLTEXT 1 0 57 "# the multi ple and a,b are the parameters of the curve.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 47 "batchellsplit:=proc(n,K,P,B) lo cal e,d,p,L,i;\n" }{MPLTEXT 1 0 8 "L:=[];\n" }{MPLTEXT 1 0 15 "for i t o K do\n" }{MPLTEXT 1 0 55 " p:=ellrand(n); if type(p,integer) then r eturn p fi;\n" }{MPLTEXT 1 0 32 " L:=[op(L),[p[1],p[3],p[4]]];\n" } {MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 39 "p:=2; e:=1; while 2^ep*B and e>1 do e:=e-1 od;\n" }{MPLTEXT 1 0 29 " L:=batchellmul s(L,p^e,n);\n" }{MPLTEXT 1 0 40 " if type(L,integer) then return L fi ;\n" }{MPLTEXT 1 0 20 " p:=nextprime(p);\n" }{MPLTEXT 1 0 11 "od; L; \+ end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"nG6\"I\"KGF%I\"PGF%I\"BGF %6'I\"eGF%I\"dGF%I\"pGF%I\"LGF%I\"iGF%F%F%C)>F-7\"?(F.\"\"\"F3F&I%true G%*protectedGC%>F,-I(ellrandGF%6#F$@$-I%typeGF56$F,I(integerGF5OF,>F-7 $-I#opGF56#F-7%&F,6#F3&F,6#\"\"$&F,6#\"\"%>F,\"\"#>F*F3?(F%F3F3F%2)FPF *F(>F*,&F*F3F3F3?(F%F3F3F%1F,F'C&?(F%F3F3F%32*&F,F3F(F3)F,F*2F3F*>F*,& F*F3F3!\"\">F--I-batchellmulsGF%6%F-FhnF$@$-F=6$F-F?OF->F,-I*nextprime G6$F5I(_syslibGF%6#F,F-F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "10.4. M" }{TEXT 206 8 "\303\241" }{TEXT 206 7 "sodik l" }{TEXT 206 8 "\303\251" }{TEXT 206 3 "pcs" }{TEXT 206 8 "\305\221" }{TEXT 206 1 "." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 81 "This is a calculation of the distribution function F \+ of the size of the largest\n" }{TEXT 201 33 "prime factor of a random \+ number. " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "F2:=x->1+ln(x);" }}{PARA 205 "" 1 "" {XPPMATH 20 "f* 6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%,&\"\"\"F*-I#lnG6$%*protectedGI (_syslibGF%F#F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "F3 :=x->F2(1/2)-int(F2(t/(1-t))/t,t=x..1/2);" }}{PARA 206 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%,&-I#F2GF%6##\" \"\"\"\"#F.-I$intGF%6$*&-F+6#*&I\"tGF%F.,&F.F.F7!\"\"F9F.F7F9/F7;F$F-F 9F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "F4:=x->F3(1/3)-i nt(F3(t/(1-t))/t,t=x..1/3);" }}{PARA 207 "" 1 "" {XPPMATH 20 "f*6#I\"x G6\"F%6$I)operatorGF%I&arrowGF%F%,&-I#F3GF%6##\"\"\"\"\"$F.-I$intGF%6$ *&-F+6#*&I\"tGF%F.,&F.F.F7!\"\"F9F.F7F9/F7;F$F-F9F%F%F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 75 "The nex t line would be the definition between 1/5 and 1/4, but too slow; \n" }{TEXT 201 34 "instead we will use approximation." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "F5:=x->F4( 1/4)-int(F4(t/(1-t))/t,t=x..1/4);" }}{PARA 208 "" 1 "" {XPPMATH 20 "f* 6#I\"xG6\"F%6$I)operatorGF%I&arrowGF%F%,&-I#F4GF%6##\"\"\"\"\"%F.-I$in tGF%6$*&-F+6#*&I\"tGF%F.,&F.F.F7!\"\"F9F.F7F9/F7;F$F-F9F%F%F%" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "evalf(F4(0.25));" }}{PARA 209 "" 1 "" {XPPMATH 20 "$\")a#4\"\\!#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "Order:=10; series(F4(x),x=1/4);" }}{PARA 210 "" 1 "" {XPPMATH 20 "\"#5" }}{PARA 211 "" 1 "" {XPPMATH 20 "+9,&I\"xG6\"\"\"\" #F&\"\"%!\"\",0F&F&-I#lnG6$%*protectedGI(_syslibGF%6#\"\"$F)*&#F&\"\"# F&)-F,6#F4F4F&F)-I&dilogGF-6##F1F4F)*&F6F&F+F&F&*&#F&\"#7F&)I#PiGF.F4F &F)-I$intGF-6$*&,(F&F&F6F)-FC6$*&,&F&F&-F,6#*&I\"tGF%F&,&F&F&FNF)F)F&F &FNF)/FN;FMF3F)F&FNF)/FN;F'#F&F1F)\"\"!,.F(F&*&F(F&F+F&F)*&F4F&F5F&F)* &F(F&F8F&F)*(F(F&F6F&F+F&F&*&FTF&F@F&F)F&,0#\"\")F1F&*&#\"#KF1F&F6F&F) *&FhnF&F+F&F&*&F(F&F5F&F&*&FhnF&F8F&F&*(FhnF&F6F&F+F&F)*&#F4F1F&F@F&F& F4,0#\"$?$\"#FF&*&#\"%C5FeoF&F6F&F&*&#\"#kF1F&F+F&F)*&FjnF&F5F&F)*&Fjo F&F8F&F)*(FjoF&F6F&F+F&F&*&#\"#;\"\"*F&F@F&F)F1,0#\"%gT\"#\")F)*&#\"&3 5\"FfpF&F6F&F)*&F[pF&F+F&F&*&F[oF&F5F&F&*&F[pF&F8F&F&*(F[pF&F6F&F+F&F) *&#FapF1F&F@F&F&F(,0*&#\"&Ob'\"$N\"F&F6F&F&#\"%orFeoF&*&#Fho\"\"&F&F+F &F)*&#\"$7&FiqF&F5F&F)*&FhqF&F8F&F)*(FhqF&F6F&F+F&F&*&#\"$c#\"#:F&F@F& F)Fiq,0#\"'o2!)\"$H(F)*&#\"(_zR'\"%XOF&F6F&F)*&#\"%[?F1F&F+F&F&*&#FhoF 1F&F5F&F&*&F\\sF&F8F&F&*(F\\sF&F6F&F+F&F)*&#F\\rFbpF&F@F&F&\"\"',0#\"* G@*\\N\"&Xl(F&*&#\"*C9Z!\\FhsF&F6F&F&*&#\"&%Q;\"\"(F&F+F&F)*&#\"%#>)F_ tF&F5F&F)*&F]tF&F8F&F)*(F]tF&F6F&F+F&F&*&#\"%'4%\"#@F&F@F&F)F_t,0#\"+W \")fA9FhsF)*&#\"+k/F1=FhsF&F6F&F)*&FbtF&F+F&F&*&FgtF&F5F&F&*&FbtF&F8F& F&*(FbtF&F6F&F+F&F)*&F\\sF&F@F&F&Fhn,0#\"-s)>r7b\"\"(:n1#F&*&#\"-Wt\\D 4=FguF&F6F&F&*&#\"'W@EFbpF&F+F&F)*&#\"'s58FbpF&F5F&F)*&F\\vF&F8F&F)*(F \\vF&F6F&F+F&F&*&#FcqFeoF&F@F&F)Fbp-I\"OGF.6#F&\"#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "F4s:=evalf(%);" }}{PARA 212 "" 1 "" {XPPMATH 20 "+9,&I\"xG6\"\"\"\"$\"+++++D!#5!\"\"$\"*OD4\"\\!#6\"\"!$\" *`NV%>!\"*F&$\"+N'HU)GF1\"\"#$\"+4YP%y\"!\")\"\"$$!+:>&oY)F7\"\"%$\"+> 1ErS!\"(\"\"&$!+SHil;!\"'\"\"'$\"+-qJ_oFB\"\"($!+pgy9F!\"&\"\")$\"+aLG !3\"!\"%\"\"*-I\"OG%*protectedG6#F&\"#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "F4p:=convert(F4s,polynom); F4as:=subs(x=t/(1-t),F4p)/ t;" }}{PARA 213 "" 1 "" {XPPMATH 20 ",6$\"+*GY(pV!#6!\"\"*&$\"*`NV%>! \"*\"\"\"I\"xG6\"F+F+*&$\"+N'HU)GF*F+),&F,F+$\"+++++D!#5F&\"\"#F+F+*&$ \"+4YP%y\"!\")F+)F2\"\"$F+F+*&$\"+:>&oY)F:F+)F2\"\"%F+F&*&$\"+>1ErS!\" (F+)F2\"\"&F+F+*&$\"+SHil;!\"'F+)F2\"\"'F+F&*&$\"+-qJ_oFKF+)F2\"\"(F+F +*&$\"+pgy9F!\"&F+)F2\"\")F+F&*&$\"+aLG!3\"!\"%F+)F2\"\"*F+F+" }} {PARA 214 "" 1 "" {XPPMATH 20 "*&,6$\"+*GY(pV!#6!\"\"*($\"*`NV%>!\"*\" \"\"I\"tG6\"F,,&F,F,F-F'F'F,*&$\"+N'HU)GF+F,),&*&F-F,F/F'F,$\"+++++D!# 5F'\"\"#F,F,*&$\"+4YP%y\"!\")F,)F4\"\"$F,F,*&$\"+:>&oY)F=F,)F4\"\"%F,F '*&$\"+>1ErS!\"(F,)F4\"\"&F,F,*&$\"+SHil;!\"'F,)F4\"\"'F,F'*&$\"+-qJ_o FNF,)F4\"\"(F,F,*&$\"+pgy9F!\"&F,)F4\"\")F,F'*&$\"+aLG!3\"!\"%F,)F4\" \"*F,F,F,F-F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "F5a:=y->F4 (1/4)-int(F4as,t=y..1/4);" }}{PARA 215 "" 1 "" {XPPMATH 20 "f*6#I\"yG6 \"F%6$I)operatorGF%I&arrowGF%F%,&-I#F4GF%6##\"\"\"\"\"%F.-I$intG6$%*pr otectedGI(_syslibGF%6$I%F4asGF%/I\"tGF%;F$F-!\"\"F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evalf(F5a(0.20));" }}{PARA 216 "" 1 "" {XPPMATH 20 "$\")EKYN!#6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "F:=proc(x) if x>1. then 1. elif x>=1/2. then F2(x) elif x>=1/3. \+ \n" }{MPLTEXT 1 0 61 "then F3(x) elif x>=1/4. then F4(x) elif x>=1/5. \+ then F5a(x)\n" }{MPLTEXT 1 0 16 "else 0. fi; end;" }}{PARA 217 "" 1 "" {XPPMATH 20 "f*6#I\"xG6\"F%F%F%@-2$\"\"\"\"\"!F$F(1*&F)F)$\"\"#F*!\" \"F$-I#F2GF%F#1*&F)F)$\"\"$F*F/F$-I#F3GF%F#1*&F)F)$\"\"%F*F/F$-I#F4GF% F#1*&F)F)$\"\"&F*F/F$-I$F5aGF%F#$F*F*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "F(0.22);" }}{PARA 218 "" 1 "" {XPPMATH 20 ",0$\"+A@ /j**!#5\"\"\"-I#lnG6$%*protectedGI(_syslibG6\"6#\"\"$!\"\"*&#F&\"\"#F& )-F(6#F2F2F&F/-I&dilogGF)6##F.F2F/*&F4F&F'F&F&*&#F&\"#7F&)I#PiGF*F2F&F /-I$intGF)6$*&,(F&F&F4F/-FA6$*&,&F&F&-F(6#*&I\"tGF,F&,&F&F&FLF/F/F&F&F LF//FL;FKF1F/F&FLF//FL;#F&\"\"%#F&F.F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evalf(%);" }}{PARA 219 "" 1 "" {XPPMATH 20 "$\"*cP^@\" !#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 72 "Now the definition of F is finished. We start to count probabi lity ENI\n" }{TEXT 201 71 "and ENII to does not succed with working N \+ elliptic curves, and using\n" }{TEXT 201 63 "step I or step II also. W e have to give the following bounds:\n" }{TEXT 201 74 "B0 is the bound for prime powers; B1 is the bound for primes in step I; \n" }{TEXT 201 77 "B2 is the bound for primes in step II; finally, B is the bound for factors;\n" }{TEXT 201 48 "the conditions B0>=B1 and B2>>B1 are s upposed.\n" }{TEXT 201 78 "The probabilities to does not succeed with \+ one elliptic curve is also given,\n" }{TEXT 201 78 "these are EI and E II, respectively. Two additional probabilities also given:\n" }{TEXT 201 76 "E0 is an upper bound for probability that error is caused by t oo small B0,\n" }{TEXT 201 78 "and E1 is an upper bound the probabilit y that error is cause by too small B0\n" }{TEXT 201 78 "with respect t o B1. These shoud have to keep below 1-EI or 1-EII, depending\n" } {TEXT 201 57 "on whether we plane to use step I only or step II, too. \n" }{TEXT 201 75 "Upper bounds for work also given back: these are ca lculated for one curve\n" }{TEXT 201 65 "as the number of additions on the curve, and are the following:\n" }{TEXT 201 45 "W0 for part of st ep I depending only on B0;\n" }{TEXT 201 47 "W1 for part of step I dep ending mainly on B1;\n" }{TEXT 201 42 "W2 for step II and depending ma inly on B2." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "with(numtheory);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7QI&GIgcdG6\"I)bigomegaGF$I&cfracGF$I)cfracpolGF$I+cyclotomicGF$I)div isorsGF$I)factorEQGF$I*factorsetGF$I'fermatGF$I)imagunitGF$I&indexGF$I /integral_basisGF$I)invcfracGF$I'invphiGF$I*issqrfreeGF$I'jacobiGF$I*k roneckerGF$I'lambdaGF$I)legendreGF$I)mcombineGF$I)mersenneGF$I(migcdex GF$I*minkowskiGF$I(mipolysGF$I%mlogGF$I'mobiusGF$I&mrootGF$I&msqrtGF$I )nearestpGF$I*nthconverGF$I)nthdenomGF$I)nthnumerGF$I'nthpowGF$I&order G%*protectedGI)pdexpandGF$I$phiGF$I#piGF$I*pprimrootGF$I)primrootGF$I( quadresGF$I+rootsunityGF$I*safeprimeGF$I&sigmaGF$I*sq2factorGF$I(sum2s qrGF$I$tauGF$I%thueGF$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "B 0:=10.^5; B1:=10.^4; B2:=10.^6; B:=10.^20; N:=32;" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"'++5\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"&++\"\" \"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"(+++\"\"\"!" }}{PARA 11 "" 1 " " {XPPMATH 20 "$\"+++++5\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#K" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "E0:=proc() evalf(pi(floor(s qrt(B0)))/B0); end; E0();" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F# -I&evalfG%*protectedG6#*&-_I*numtheoryG6$F&I(_syslibGF#I#piGF#6#-I&flo orGF,6#-I%sqrtGF,6#I#B0GF#\"\"\"F6!\"\"F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+++++l!#8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "W0:=proc() 2*floor(log[2.](B0))*pi(floor(sqrt(B0)))*N; end; W0();" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F#,$**\"\"#\"\"\"-I&floorG6$ %*protectedGI(_syslibGF#6#-&I$logGF*6#$F&\"\"!6#I#B0GF#F'-_I*numtheory GF*I#piGF#6#-F)6#-I%sqrtGF*F4F'I\"NGF#F'F'F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"&gl'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "E1:= proc() local s,p; p:=nextprime(floor(sqrt(B0))); s:=0.;\n" }{MPLTEXT 1 0 54 "while pF&-I*nextpri meG6$%*protectedGI(_syslibGF#6#-I&floorGF+6#-I%sqrtGF+6#I#B0GF#>F%$\" \"!F8?(F#\"\"\"F:F#2F&I#B1GF#C$>F%,&F%F:*$)F&\"\"#!\"\"F:>F&-F*6#F&F%F #F#F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "E1();" }}{PARA 11 " " 1 "" {XPPMATH 20 "$\"+GN>*\\%!#8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "W1:=proc() local s,p; p:=nextprime(floor(sqrt(B0))); \+ s:=0;\n" }{MPLTEXT 1 0 70 "while pF&-I*nextprimeG6$%*protectedGI(_syslibGF#6#-I&floo rGF+6#-I%sqrtGF+6#I#B0GF#>F%\"\"!?(F#\"\"\"F9F#2F&I#B1GF#C$>F%,&F%F9-F 06#-&I$logGF+6#$\"\"#F76#F&F9>F&-F*FG,$*(FFF9I\"NGF#F9F%F9F9F#F#F#" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "W1();" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'o.&)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "EI: =proc() evalf(1.-F(log[B](B1))); end;\n" }{MPLTEXT 1 0 45 "EI(); 1-EI( ); ENI:=proc() EI()^N; end; ENI();" }}{PARA 11 "" 1 "" {XPPMATH 20 "f* 6\"F#F#F#-I&evalfG%*protectedG6#,&$\"\"\"\"\"!F*-I\"FGF#6#-&I$logG6$F& I(_syslibGF#6#I\"BGF#6#I#B1GF#!\"\"F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+wOX'***!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"(Cja$! #5" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F#)-I#EIGF#F#I\"NGF#F#F#F #" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+;#Rr))*!#5" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 65 "EII:=proc() evalf(1.-exp(gamma)*log[B](B1)*F (log[B](B2))); end;\n" }{MPLTEXT 1 0 50 "EII(); 1-EII(); ENII:=proc() \+ EII()^N; end; ENII();" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F#-I&e valfG%*protectedG6#,&$\"\"\"\"\"!F**(-I$expG6$F&I(_syslibGF#6#I&gammaG F&F*-&I$logGF/6#I\"BGF#6#I#B1GF#F*-I\"FGF#6#-F46#I#B2GF#F*!\"\"F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+$yad\"**!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\")<_C%)!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F# )-I$EIIGF#F#I\"NGF#F#F#F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+!o\\#Gw !#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "W2:=proc() ceil(pi(f loor(B2))-pi(floor(B1)))*N; end; W2();" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6\"F#F#F#*&-I%ceilG6$%*protectedGI(_syslibGF#6#,&-_I*numtheoryGF'I #piGF#6#-I&floorGF'6#I#B2GF#\"\"\"-F-6#-F26#I#B1GF#!\"\"F5I\"NGF#F5F#F #F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(3EZ#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "N:=64; B0:=10.^6; B1:=10.^5; B2:=10.^7; B:=10.^25 ;\n" }{MPLTEXT 1 0 58 "E0(); E1(); EI(); 1-EI(); ENI(); EII(); 1-EII() ; ENII();\n" }{MPLTEXT 1 0 17 "W0(); W1(); W2();" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#k" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"(+++\"\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "$\"'++5\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\")+++5\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+++++5 \"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"++++!o\"!#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+>%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "# \n" }{MPLTEXT 1 0 66 "# This procedure is the second step of elliptic \+ curve method for\n" }{MPLTEXT 1 0 68 "# factorization. The list of \"c urves\" is L, the table of doubles\n" }{MPLTEXT 1 0 63 "# has size N a nd primes greater then m but not greater then M\n" }{MPLTEXT 1 0 65 "# are considered. The result is the last list or a factor of n.\n" } {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 65 "batchellsp lit2:=proc(L,n::posint,N::posint,m::posint,M::posint)\n" }{MPLTEXT 1 0 39 "local y,i,j,E,P,PP,p,pp,d,LL,LLL,a,b;\n" }{MPLTEXT 1 0 9 "LL:=[] ;\n" }{MPLTEXT 1 0 21 "for i to nops(L) do\n" }{MPLTEXT 1 0 12 " p:=L [i];\n" }{MPLTEXT 1 0 24 " y:=msqrt(L[i][1],n);\n" }{MPLTEXT 1 0 27 " if y=FAIL then next fi;\n" }{MPLTEXT 1 0 47 " LL:=[op(LL),[L[i][1], y,1,L[i][2],L[i][3]]];\n" }{MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 29 "E: =Array(1..nops(LL),1..N);\n" }{MPLTEXT 1 0 22 "for i to nops(LL) do\n" }{MPLTEXT 1 0 19 " P:=LL[i][1..3];\n" }{MPLTEXT 1 0 29 " a:=LL[i][4 ]; b:=LL[i][5];\n" }{MPLTEXT 1 0 24 " PP:=elldou(P,a,b,n);\n" } {MPLTEXT 1 0 42 " if type(PP,integer) then return PP fi;\n" }{MPLTEXT 1 0 15 " E[i,1]:=PP;\n" }{MPLTEXT 1 0 24 " for j from 2 to N do\n" }{MPLTEXT 1 0 36 " PP:=elladd(E[i,j-1],PP,a,b,n);\n" }{MPLTEXT 1 0 44 " if type(PP,integer) then return PP fi;\n" }{MPLTEXT 1 0 17 " \+ E[i,1]:=PP;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 5 "od;\n" } {MPLTEXT 1 0 18 "p:=nextprime(m);\n" }{MPLTEXT 1 0 22 "for i to nops(L L) do\n" }{MPLTEXT 1 0 19 " P:=LL[i][1..3];\n" }{MPLTEXT 1 0 29 " a: =LL[i][4]; b:=LL[i][5];\n" }{MPLTEXT 1 0 26 " PP:=ellmul(P,p,a,b,n); \n" }{MPLTEXT 1 0 42 " if type(PP,integer) then return PP fi;\n" } {MPLTEXT 1 0 25 " LLL[i]:=[op(PP),a,b];\n" }{MPLTEXT 1 0 5 "od;\n" } {MPLTEXT 1 0 19 "pp:=nextprime(p);\n" }{MPLTEXT 1 0 15 "while ppF:7\"?(F2\"\"\"FB-I%nopsGF)6#F$I%trueG F)C&>F7&F$6#F2>F1-I&msqrtGF%6$&FI6#FBF'@$/F1I%FAILGF)\\>F:7$-I#opGF)6# F:7'FOF1FB&FI6#\"\"#&FI6#\"\"$>F4-I&ArrayGF)6$;FB-FDFY;FBF+?(F2FBFBF`o FFC)>F5&&F:FJ6#;FBFjn>F<&Ffo6#\"\"%>F=&Ffo6#\"\"&>F6-I'elldouGF%6&F5F< F=F'@$-I%typeGF)6$F6I(integerGF)OF6>&F46$F2FBF6?(F3FgnFBF+FFC%>F6-I'el laddGF%6'&F46$F2,&F3FBFB!\"\"F6FF7-I*nextprimeG6$F)I(_sysl ibGF%6#F-?(F2FBFBF`oFFC(FdoFioF]p>F6-I'ellmulGF%6'F5F7F&F;FJ7 %-FX6#F6FF8-Fjq6#F7?(F%FBFBF%2F8F/C&>F9,&F8FBF7Fgq>F7F8@%1F9,$*&Fg nFBF+FBFB?(F2FBFBF`oFFC(>F6&FerFgoFioF]p>F6-Fbq6'F6&F46$F2,$*&#FBFgnFB F9FBFBFF6-Fbr6'F5F9FF6-Fb q6'F6FisF " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 220 "> " 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 }