Sz\303\241m\303\255t\303\263g\303\251pes sz\303\241melm\303\251let J\303\241rai Antal Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">1. A pr\303\255mek eloszl\303\241sa, szit\303\241l\303\241s</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263dszerek</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\263dszerek</Font></Text-field> LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1">4. Lucas-sorozatok</Text-field> restart; with(numtheory); N1FJJkdJZ2NkRzYiSSliaWdvbWVnYUdGJEkmY2ZyYWNHRiRJKWNmcmFjcG9sR0YkSStjeWNsb3RvbWljR0YkSSlkaXZpc29yc0dGJEkpZmFjdG9yRVFHRiRJKmZhY3RvcnNldEdGJEknZmVybWF0R0YkSSlpbWFndW5pdEdGJEkmaW5kZXhHRiRJL2ludGVncmFsX2Jhc2lzR0YkSSlpbnZjZnJhY0dGJEknaW52cGhpR0YkSSppc3NxcmZyZWVHRiRJJ2phY29iaUdGJEkqa3JvbmVja2VyR0YkSSdsYW1iZGFHRiRJKWxlZ2VuZHJlR0YkSSltY29tYmluZUdGJEkpbWVyc2VubmVHRiRJKG1pZ2NkZXhHRiRJKm1pbmtvd3NraUdGJEkobWlwb2x5c0dGJEklbWxvZ0dGJEknbW9iaXVzR0YkSSZtcm9vdEdGJEkmbXNxcnRHRiRJKW5lYXJlc3RwR0YkSSpudGhjb252ZXJHRiRJKW50aGRlbm9tR0YkSSludGhudW1lckdGJEknbnRocG93R0YkSSZvcmRlckclKnByb3RlY3RlZEdJKXBkZXhwYW5kR0YkSSRwaGlHRiRJI3BpR0YkSSpwcHJpbXJvb3RHRiRJKXByaW1yb290R0YkSShxdWFkcmVzR0YkSStyb290c3VuaXR5R0YkSSpzYWZlcHJpbWVHRiRJJnNpZ21hR0YkSSpzcTJmYWN0b3JHRiRJKHN1bTJzcXJHRiRJJHRhdUdGJEkldGh1ZUdGJA==
<Text-field style="Heading 2" layout="Heading 2">4.1. Defin<Font encoding="UTF-8">\303\255</Font>ci<Font encoding="UTF-8">\303\263</Font>.</Text-field> a:=-3; b:=2; for n to 10 do [(a^n-b^n)/(a-b),a^n+b^n]; od; ISIk IiIj NyQiIiIhIiI= NyQhIiIiIzg= NyQiIighIz4= NyQhIzgiIygq NyQiI2IhJDYj NyQhJEwiIiQkeg== NyQiJGolISVmPw== NyQhJWg3IiU8bw== NyQiJVJTISZyIj4= NyQhJjA7IiImdCsn
<Text-field style="Heading 2" layout="Heading 2">4.2. Megjegyz<Font encoding="UTF-8">\303\251</Font>s.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.3. P<Font encoding="UTF-8">\303\251</Font>lda.</Text-field> a:=(1+sqrt(5))/2; b:=(1-sqrt(5))/2; for n to 10 do [expand((a^n-b^n)/(a-b)),expand(a^n+b^n)]; od; LCYjIiIiIiIjRiQqJkYjRiQpIiImRiNGJEYk LCYjIiIiIiIjRiQqJkYjRiQpIiImRiNGJCEiIg== NyQiIiJGIw== NyQiIiIiIiQ= NyQiIiMiIiU= NyQiIiQiIig= NyQiIiYiIzY= NyQiIikiIz0= NyQiIzgiI0g= NyQiI0AiI1o= NyQiI00iI3c= NyQiI2IiJEIi
<Text-field style="Heading 2" layout="Heading 2">4.4. Rekurzi<Font encoding="UTF-8">\303\263</Font> sz<Font encoding="UTF-8">\303\241</Font>mol<Font encoding="UTF-8">\303\241</Font>shoz.</Text-field> # # This procedure calculate the Lucas sequence terms # [U[n],V[n],U[n+1],V[n+1]]. If the parameter N also given # then the calculations are done mod N. Here U[n]=a^n-b^n)/(a-b) # and V[n]=a^n+b^n, where a,b are the roots of x^2-Px+Q=0. # lucasUV:=proc(n,P,Q,N) local L,B,i,Qk; B:=convert(n,base,2); Qk:=1; if nargs=3 then L:=[0,2,1,P]; for i from nops(B) to 1 by -1 do if B[i]=0 then L:=[L[1]*L[2],L[2]^2-2*Qk,L[3]*L[2]-Qk,L[4]*L[2]-P*Qk]; Qk:=Qk^2; else L:=[L[3]*L[2]-Qk,L[4]*L[2]-P*Qk,L[3]*L[4],L[4]^2-2*Q*Qk]; Qk:=Qk^2*Q; fi; od; else L:=[0,2 mod N,1,P mod N]; for i from nops(B) to 1 by -1 do if B[i]=0 then L:=[L[1]*L[2] mod N,L[2]&^2-2*Qk mod N,\ L[3]*L[2]-Qk mod N,L[4]*L[2]-P*Qk mod N]; Qk:=Qk&^2 mod N; else L:=[L[3]*L[2]-Qk mod N,L[4]*L[2]-P*Qk mod N,\ L[3]*L[4] mod N,L[4]&^2-2*Q*Qk mod N]; Qk:=Qk&^2*Q mod N; fi; od; fi; L end; Zio2Jkkibkc2IkkiUEdGJUkiUUdGJUkiTkdGJTYmSSJMR0YlSSJCR0YlSSJpR0YlSSNRa0dGJUYlRiVDJj5GKy1JKGNvbnZlcnRHJSpwcm90ZWN0ZWRHNiVGJEklYmFzZUdGJSIiIz5GLSIiIkAlLyUmbmFyZ3NHIiIkQyQ+Rio3JiIiIUY1RjdGJj8oRiwtSSVub3BzR0YyNiNGKyEiIkY3SSV0cnVlR0YyQCUvJkYrNiNGLEY/QyQ+Rio3JiomJkYqNiNGN0Y3JkYqNiNGNUY3LCYqJClGUEY1RjdGNyomRjVGN0YtRjdGRCwmKiYmRio2I0Y7RjdGUEY3RjdGLUZELCYqJiZGKjYjIiIlRjdGUEY3RjcqJkYmRjdGLUY3RkQ+Ri0qJClGLUY1RjdDJD5GKjcmRlZGWiomRlhGN0ZmbkY3LCYqJClGZm5GNUY3RjcqKEY1RjdGJ0Y3Ri1GN0ZEPkYtKiZGXG9GN0YnRjdDJD5GKjcmRj8tSSRtb2RHRiU2JEY1RihGNy1GW3A2JEYmRig/KEYsRkFGREY3RkVAJUZHQyQ+Rio3Ji1GW3A2JEZNRigtRltwNiQsJi1JIyZeR0YlNiRGUEY1RjdGVUZERigtRltwNiRGVkYoLUZbcDYkRlpGKD5GLS1GW3A2JC1GanA2JEYtRjVGKEMkPkYqNyZGXHFGXnEtRltwNiRGYG9GKC1GW3A2JCwmLUZqcDYkRmZuRjVGN0Zkb0ZERig+Ri0tRltwNiQqJkZjcUY3RidGN0YoRipGJUYlRiU= # # This procedure calculate the Lucas sequence terms # [V[n],V[n+1]]. If the parameter N also given # then the calculations are done mod N. Here V[n]=a^n+b^n, # where a,b are the roots of x^2-Px+Q=0. # lucasV:=proc(n,P,Q,N) local L,B,i,Qk; B:=convert(n,base,2); Qk:=1; if nargs=3 then L:=[2,P]; for i from nops(B) to 1 by -1 do if B[i]=0 then L:=[L[1]^2-2*Qk,L[2]*L[1]-P*Qk]; Qk:=Qk^2; else L:=[L[2]*L[1]-P*Qk,L[2]^2-2*Q*Qk]; Qk:=Qk^2*Q; fi; od; else L:=[2 mod N,P mod N]; for i from nops(B) to 1 by -1 do if B[i]=0 then L:=[L[1]&^2-2*Qk mod N,L[2]*L[1]-P*Qk mod N]; Qk:=Qk&^2 mod N; else L:=[L[2]*L[1]-P*Qk mod N,L[2]&^2-2*Q*Qk mod N]; Qk:=Qk&^2*Q mod N; fi; od; fi; L end; Zio2Jkkibkc2IkkiUEdGJUkiUUdGJUkiTkdGJTYmSSJMR0YlSSJCR0YlSSJpR0YlSSNRa0dGJUYlRiVDJj5GKy1JKGNvbnZlcnRHJSpwcm90ZWN0ZWRHNiVGJEklYmFzZUdGJSIiIz5GLSIiIkAlLyUmbmFyZ3NHIiIkQyQ+Rio3JEY1RiY/KEYsLUklbm9wc0dGMjYjRishIiJGN0kldHJ1ZUdGMkAlLyZGKzYjRiwiIiFDJD5GKjckLCYqJCkmRio2I0Y3RjVGN0Y3KiZGNUY3Ri1GN0ZDLCYqJkZQRjcmRio2I0Y1RjdGNyomRiZGN0YtRjdGQz5GLSokKUYtRjVGN0MkPkYqNyRGUywmKiQpRlVGNUY3RjcqKEY1RjdGJ0Y3Ri1GN0ZDPkYtKiZGWkY3RidGN0MkPkYqNyQtSSRtb2RHRiU2JEY1RigtRmJvNiRGJkYoPyhGLEZARkNGN0ZEQCVGRkMkPkYqNyQtRmJvNiQsJi1JIyZeR0YlNiRGUEY1RjdGUkZDRigtRmJvNiRGU0YoPkYtLUZibzYkLUZfcDYkRi1GNUYoQyQ+Rio3JEZhcC1GYm82JCwmLUZfcDYkRlVGNUY3RltvRkNGKD5GLS1GYm82JComRmZwRjdGJ0Y3RihGKkYlRiVGJQ==
<Text-field style="Heading 2" layout="Heading 2">4.5. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.6. Megjegyz<Font encoding="UTF-8">\303\251</Font>s.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.7. Defin<Font encoding="UTF-8">\303\255</Font>ci<Font encoding="UTF-8">\303\263</Font>.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.8. T<Font encoding="UTF-8">\303\251</Font>tel.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.9. Feladat.</Text-field> # # This procedure do primality test for the odd number n # using the set S of all factors of n+1 and the Lucas # sequence corresponding to the roots of x^2-Px+1. # naiveplustest:=proc(n::posint,S::list(posint),P::integer) local D,q,L; D:=P^2-4; modp(D,4); if %=2 or %=3 then RETURN(FAIL) fi; igcd(2*D,n); if %<>1 then if %<n then RETURN(false) else RETURN(FAIL) fi; fi; if jacobi(D,n)<>-1 then RETURN(FAIL) fi; L:=lucasUV(n+1,P,1,n); if L[1]<>0 or L[2]<>2 then RETURN(false) fi; for q in S do L:=lucasUV((n+1)/q,P,1,n); if L[1]=0 and L[2]=2 then RETURN(FAIL) fi; od; true end; Zio2JSdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJTR0YmLUklbGlzdEdGKDYjRicnSSJQR0YmSShpbnRlZ2VyR0YoNiVJIkRHRiZJInFHRiZJIkxHRiZGJkYmQyw+RjIsJiokKUYvIiIjIiIiRjsiIiUhIiItSSVtb2RwR0YoNiRGMkY8QCQ1L0kiJUdGJkY6L0ZEIiIkLUknUkVUVVJOR0YoNiNJJUZBSUxHRigtSSVpZ2NkR0YoNiQsJComRjpGO0YyRjtGO0YlQCQwRkRGO0AlMkZERiUtRkg2I0kmZmFsc2VHRihGR0AkMC1fSSpudW10aGVvcnlHNiRGKEkoX3N5c2xpYkdGJkknamFjb2JpR0YmNiRGMkYlRj1GRz5GNC1JKGx1Y2FzVVZHRiY2JiwmRiVGO0Y7RjtGL0Y7RiVAJDUwJkY0NiNGOyIiITAmRjQ2I0Y6RjpGVD8mRjNGKkkldHJ1ZUdGKEMkPkY0LUZcbzYmKiZGXm9GO0YzRj1GL0Y7RiVAJDMvRmJvRmRvL0Zmb0Y6RkdGaW9GJkYmRiY= naiveplustest(7,[2],3); SSV0cnVlRyUqcHJvdGVjdGVkRw== # # This procedure do primality test for the odd number n # using the set S of all factors of n+1. Try all Lucas # sequences with Q=1 and P in interval II. # naiveplustests:=proc(n::posint,S::list(posint),II::range(integer)) local r,P; for P from op(1,II) to op(2,II) do r:=naiveplustest(n,S,P); if r<>FAIL then RETURN(r) fi; od; FAIL end; Zio2JSdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJTR0YmLUklbGlzdEdGKDYjRicnSSNJSUdGJi1JJnJhbmdlR0YoNiNJKGludGVnZXJHRig2JEkickdGJkkiUEdGJkYmRiZDJD8oRjYtSSNvcEdGKDYkIiIiRi9GPC1GOjYkIiIjRi9JJXRydWVHRihDJD5GNS1JLm5haXZlcGx1c3Rlc3RHRiY2JUYlRipGNkAkMEY1SSVGQUlMR0YoLUknUkVUVVJOR0YoNiNGNUZIRiZGJkYm naiveplustests(7,[2],1..2); naiveplustests(7,[2],1..3); SSVGQUlMRyUqcHJvdGVjdGVkRw== SSV0cnVlRyUqcHJvdGVjdGVkRw==
<Text-field style="Heading 2" layout="Heading 2">4.10. Lucas-t<Font encoding="UTF-8">\303\255</Font>pus<Font encoding="UTF-8">\303\272</Font> teszt.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.11. Feladat.</Text-field> # # This procedure do primality test for the odd number n # using a large enough set S of factors of n+1 and the Lucas # sequence corresponding to the roots of x^2-Px+1. # plustest:=proc(n::posint,S::list(posint),P::integer) local D,q,L; if n=1 then RETURN(false) fi; D:=P^2-4; modp(D,4); if %=2 or %=3 then RETURN(FAIL) fi; igcd(2*D,n); if %<>1 then if %<n then RETURN(false) else RETURN(FAIL) fi; fi; if jacobi(D,n)<>-1 then RETURN(FAIL) fi; L:=lucasUV(n+1,P,1,n); if L[1]<>0 or L[2]<>2 then RETURN(false) fi; for q in S do L:=lucasUV((n+1)/q,P,1,n); igcd(L[2]-2,L[1],n); if %<>1 then if %<n then RETURN(false) else RETURN(FAIL) fi; fi; od; true end; Zio2JSdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJTR0YmLUklbGlzdEdGKDYjRicnSSJQR0YmSShpbnRlZ2VyR0YoNiVJIkRHRiZJInFHRiZJIkxHRiZGJkYmQy1AJC9GJSIiIi1JJ1JFVFVSTkdGKDYjSSZmYWxzZUdGKD5GMiwmKiQpRi8iIiNGOEY4IiIlISIiLUklbW9kcEdGKDYkRjJGQkAkNS9JIiVHRiZGQS9GSiIiJC1GOjYjSSVGQUlMR0YoLUklaWdjZEdGKDYkLCQqJkZBRjhGMkY4RjhGJUAkMEZKRjhAJTJGSkYlRjlGTUAkMC1fSSpudW10aGVvcnlHNiRGKEkoX3N5c2xpYkdGJkknamFjb2JpR0YmNiRGMkYlRkNGTT5GNC1JKGx1Y2FzVVZHRiY2JiwmRiVGOEY4RjhGL0Y4RiVAJDUwJkY0NiNGOCIiITAmRjQ2I0ZBRkFGOT8mRjNGKkkldHJ1ZUdGKEMlPkY0LUZebzYmKiZGYG9GOEYzRkNGL0Y4RiUtRlE2JSwmRmhvRjhGQUZDRmRvRiVGVUZbcEYmRiZGJg== plustest(7,[2],3); SSV0cnVlRyUqcHJvdGVjdGVkRw== # # This procedure do primality test for the odd number n # using a large enough set S of factors of n+1. Try all Lucas # sequences with Q=1 and P in interval II. # plustests:=proc(n::posint,S::list(posint),II::range(integer)) local r,P; for P from op(1,II) to op(2,II) do r:=plustest(n,S,P); if r<>FAIL then RETURN(r) fi; od; FAIL end; Zio2JSdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJTR0YmLUklbGlzdEdGKDYjRicnSSNJSUdGJi1JJnJhbmdlR0YoNiNJKGludGVnZXJHRig2JEkickdGJkkiUEdGJkYmRiZDJD8oRjYtSSNvcEdGKDYkIiIiRi9GPC1GOjYkIiIjRi9JJXRydWVHRihDJD5GNS1JKXBsdXN0ZXN0R0YmNiVGJUYqRjZAJDBGNUklRkFJTEdGKC1JJ1JFVFVSTkdGKDYjRjVGSEYmRiZGJg== plustests(7,[2],1..2); plustests(7,[2],1..3); SSVGQUlMRyUqcHJvdGVjdGVkRw== SSV0cnVlRyUqcHJvdGVjdGVkRw==
<Text-field style="Heading 2" layout="Heading 2">4.12. Feladat.</Text-field> # # This procedure do primality test for the number h*2^n-1 # with n>1 and odd h<2^n using the Lucas sequence corresponding # to the roots of x^2-Px+1. # specplustest:=proc(h::posint,n::posint,P::integer) local D,L,N; if h>=2^n then error "first parameter is too large",h fi; if type(h,even) then error "first parameter have to be odd",h fi; if n<2 then error "second parameter is too small",h fi; N:=h*2^n-1; D:=P^2-4; modp(D,4); if %=2 or %=3 then RETURN(FAIL) fi; igcd(2*D,N); if %<>1 then if %<n then RETURN(false) else RETURN(FAIL) fi; fi; if jacobi(D,N)<>-1 then RETURN(FAIL) fi; L:=lucasUV(N+1,P,1,N); if L[1]<>0 or L[2]<>2 then RETURN(false) fi; L:=lucasUV((N+1)/2,P,1,N); if L[1]<>0 then RETURN(false) fi; if L[2]<>N-2 then if L[2]=2 then RETURN(FAIL) else RETURN(false) fi; fi; true end; Zio2JSdJImhHNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJuR0YmRicnSSJQR0YmSShpbnRlZ2VyR0YoNiVJIkRHRiZJIkxHRiZJIk5HRiZGJkYmQzJAJDEpIiIjRipGJVk2JFE9Zmlyc3R+cGFyYW1ldGVyfmlzfnRvb35sYXJnZUYmRiVAJC1JJXR5cGVHRig2JEYlSSVldmVuR0YoWTYkUT9maXJzdH5wYXJhbWV0ZXJ+aGF2ZX50b35iZX5vZGRGJkYlQCQyRipGNlk2JFE+c2Vjb25kfnBhcmFtZXRlcn5pc350b29+c21hbGxGJkYlPkYxLCYqJkYlIiIiRjVGSkZKRkohIiI+Ri8sJiokKUYsRjZGSkZKIiIlRkstSSVtb2RwR0YoNiRGL0ZQQCQ1L0kiJUdGJkY2L0ZXIiIkLUknUkVUVVJOR0YoNiNJJUZBSUxHRigtSSVpZ2NkR0YoNiQsJComRjZGSkYvRkpGSkYxQCQwRldGSkAlMkZXRiotRmVuNiNJJmZhbHNlR0YoRlpAJDAtX0kqbnVtdGhlb3J5RzYkRihJKF9zeXNsaWJHRiZJJ2phY29iaUdGJjYkRi9GMUZLRlo+RjAtSShsdWNhc1VWR0YmNiYsJkYxRkpGSkZKRixGSkYxQCQ1MCZGMDYjRkoiIiEwJkYwNiNGNkY2RmFvPkYwLUZfcDYmLCYqJiNGSkY2RkpGMUZKRkpGYHFGSkYsRkpGMUAkRmRwRmFvQCQwRmlwLCZGMUZKRjZGS0AlL0ZpcEY2RlpGYW9JJXRydWVHRihGJkYmRiY= specplustest(1,3,3); SSV0cnVlRyUqcHJvdGVjdGVkRw== # # This procedure do primality test for the number h*2^n-1 # with n>1 and odd h<2^n. Try all Lucas sequences with Q=1 # and P in interval II. # specplustests:=proc(h::posint,n::posint,II::range(integer)) local r,P; if h>=2^n then error "first parameter is too large",h fi; if type(h,even) then error "first parameter have to be odd",h fi; if n<2 then error "second parameter is too small",h fi; for P from op(1,II) to op(2,II) do r:=specplustest(h,n,P); if r<>FAIL then RETURN(r) fi; od; FAIL end; Zio2JSdJImhHNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJuR0YmRicnSSNJSUdGJi1JJnJhbmdlR0YoNiNJKGludGVnZXJHRig2JEkickdGJkkiUEdGJkYmRiZDJ0AkMSkiIiNGKkYlWTYkUT1maXJzdH5wYXJhbWV0ZXJ+aXN+dG9vfmxhcmdlRiZGJUAkLUkldHlwZUdGKDYkRiVJJWV2ZW5HRihZNiRRP2ZpcnN0fnBhcmFtZXRlcn5oYXZlfnRvfmJlfm9kZEYmRiVAJDJGKkY4WTYkUT5zZWNvbmR+cGFyYW1ldGVyfmlzfnRvb35zbWFsbEYmRiU/KEYzLUkjb3BHRig2JCIiIkYsRk0tRks2JEY4RixJJXRydWVHRihDJD5GMi1JLXNwZWNwbHVzdGVzdEdGJjYlRiVGKkYzQCQwRjJJJUZBSUxHRigtSSdSRVRVUk5HRig2I0YyRlhGJkYmRiY= specplustests(1,3,1..2); specplustests(1,3,1..3); SSVGQUlMRyUqcHJvdGVjdGVkRw== SSV0cnVlRyUqcHJvdGVjdGVkRw==
<Text-field style="Heading 2" layout="Heading 2">4.13. Sz<Font encoding="UTF-8">\303\241</Font>mtestek.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.14. T<Font encoding="UTF-8">\303\251</Font>tel.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.15. Riesel-teszt.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.16. K<Font encoding="UTF-8">\303\266</Font>vetkezm<Font encoding="UTF-8">\303\251</Font>ny.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.17. Feladat.</Text-field> # # This procedure calculate a^h+a^(-h) for a unit a=r+s*sqrt(D) # with norm 1. Here r,s rational numbers, D must be a square # free integer. All computations are done mod N. # rieselsetup:=proc(r,s,D,h,N) local P,a; a:=r+s*sqrt(D); P:=r+s*sqrt(D)+(r-s*sqrt(D))/(r^2-s^2*D); if not type(P,integer) then ERROR(a+1/a, `not an integer`) fi; lucasV(h,P,1,N)[1]; end; Zio2J0kickc2Ikkic0dGJUkiREdGJUkiaEdGJUkiTkdGJTYkSSJQR0YlSSJhR0YlRiVGJUMmPkYsLCZGJCIiIiomRiZGMC1JJXNxcnRHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiU2I0YnRjBGMD5GKywoRiRGMEYxRjAqJiwmRiRGMEYxISIiRjAsJiokKUYkIiIjRjBGMComKUYmRkBGMEYnRjBGPEY8RjBAJDQtSSV0eXBlR0Y1NiRGK0koaW50ZWdlckdGNS1JJkVSUk9SR0Y1NiQsJkYsRjAqJEYsRjxGMEkvbm90fmFufmludGVnZXJHRiUmLUknbHVjYXNWR0YlNiZGKEYrRjBGKTYjRjBGJUYlRiU=
<Text-field style="Heading 2" layout="Heading 2">4.18. Feladat.</Text-field> # # A procedure above for primality testing of h*2^n-1 # with n>1 and odd h<2^n for which h not divisible by 3. # rieselsqrt3:=proc(h::posint,n::posint) local i,v,N; if h>=2^n then error "first parameter is too large",h fi; if type(h,even) then error "first parameter have to be odd",h fi; if modp(h,3)=0 then error "first parameter is a multiple of 3",h fi; if n<2 then error "second parameter is too small",h fi; N:=h*2^n-1; if modp(N,3)=0 then return false fi; v:=rieselsetup(2,1,3,h,N); for i to n-2 do v:=v^2-2 mod N od; evalb(v=0); end; Zio2JCdJImhHNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJuR0YmRic2JUkiaUdGJkkidkdGJkkiTkdGJkYmRiZDK0AkMSkiIiNGKkYlWTYkUT1maXJzdH5wYXJhbWV0ZXJ+aXN+dG9vfmxhcmdlRiZGJUAkLUkldHlwZUdGKDYkRiVJJWV2ZW5HRihZNiRRP2ZpcnN0fnBhcmFtZXRlcn5oYXZlfnRvfmJlfm9kZEYmRiVAJC8tSSVtb2RwR0YoNiRGJSIiJCIiIVk2JFFDZmlyc3R+cGFyYW1ldGVyfmlzfmF+bXVsdGlwbGV+b2Z+M0YmRiVAJDJGKkYzWTYkUT5zZWNvbmR+cGFyYW1ldGVyfmlzfnRvb35zbWFsbEYmRiU+Ri4sJiomRiUiIiJGMkZRRlFGUSEiIkAkLy1GQjYkRi5GREZFT0kmZmFsc2VHRig+Ri0tSSxyaWVzZWxzZXR1cEdGJjYnRjNGUUZERiVGLj8oRixGUUZRLCZGKkZRRjNGUkkldHJ1ZUdGKD5GLS1JJG1vZEdGJjYkLCYqJClGLUYzRlFGUUYzRlJGLi1JJmV2YWxiR0YoNiMvRi1GRUYmRiZGJg== # # Some tests. # test:=proc() local h,n; for h in {1,5,7} do for n from 4 to 20 do print(isprime(h*2^n-1),rieselsqrt3(h,n)) od od end; Zio2IjYkSSJoR0YjSSJuR0YjRiNGIz8mRiU8JSIiIiIiJiIiKEkldHJ1ZUclKnByb3RlY3RlZEc/KEYmIiIlRikiIz9GLC1JJnByaW50R0YtNiQtSShpc3ByaW1lR0YjNiMsJiomRiVGKSkiIiNGJkYpRilGKSEiIi1JLHJpZXNlbHNxcnQzR0YjRiRGI0YjRiM= test(); NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj
<Text-field style="Heading 2" layout="Heading 2">4.19. Feladat.</Text-field> # # This procedure use iteration v<-v^2-2 starting with v=a^h+a^-h # where the quadratic unit a=r+s*sqrt(D) is given for the # primality testing of h*2^n-1. Here n>1 and h<2^n is odd. # riesel:=proc(h,n,r,s,D) local N,v,i; if h>=2^n then error "first parameter is too large",h fi; if type(h,even) then error "first parameter have to be odd",h fi; if n<2 then error "second parameter is too small",h fi; N:=h*2^n-1; v:=rieselsetup(r,s,D,h,N); for i to n-2 do v:=v^2-2 mod N od; evalb(v=0); end; Zio2J0kiaEc2IkkibkdGJUkickdGJUkic0dGJUkiREdGJTYlSSJOR0YlSSJ2R0YlSSJpR0YlRiVGJUMpQCQxKSIiI0YmRiRZNiRRPWZpcnN0fnBhcmFtZXRlcn5pc350b29+bGFyZ2VGJUYkQCQtSSV0eXBlRyUqcHJvdGVjdGVkRzYkRiRJJWV2ZW5HRjlZNiRRP2ZpcnN0fnBhcmFtZXRlcn5oYXZlfnRvfmJlfm9kZEYlRiRAJDJGJkYyWTYkUT5zZWNvbmR+cGFyYW1ldGVyfmlzfnRvb35zbWFsbEYlRiQ+RissJiomRiQiIiJGMUZHRkdGRyEiIj5GLC1JLHJpZXNlbHNldHVwR0YlNidGJ0YoRilGJEYrPyhGLUZHRkcsJkYmRkdGMkZISSV0cnVlR0Y5PkYsLUkkbW9kR0YlNiQsJiokKUYsRjJGR0ZHRjJGSEYrLUkmZXZhbGJHRjk2Iy9GLCIiIUYlRiVGJQ== # # Some tests. # test:=proc() local h,n; for h in {1,5,7} do for n from 4 to 20 do print(isprime(h*2^n-1),riesel(h,n,2,1,3)) od od end; Zio2IjYkSSJoR0YjSSJuR0YjRiNGIz8mRiU8JSIiIiIiJiIiKEkldHJ1ZUclKnByb3RlY3RlZEc/KEYmIiIlRikiIz9GLC1JJnByaW50R0YtNiQtSShpc3ByaW1lRzYkRi1JKF9zeXNsaWJHRiM2IywmKiZGJUYpKSIiI0YmRilGKUYpISIiLUkncmllc2VsR0YjNidGJUYmRjxGKSIiJEYjRiNGIw== test(); NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJXRydWVHJSpwcm90ZWN0ZWRHRiM= NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiRJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj
<Text-field style="Heading 2" layout="Heading 2">4.20. Feladat.</Text-field> # # This procedure find units having the form (k+l*sqrt(D))^2/r # with small integers k,l and r=k^2-l^2*D in the # quadratic extension of the rationals with sqrt(D). # D must be a square free integer. The numbers with |k|,|l|<=B # are tested. We remark that taking -r instead of r we get an # other unit. The list of all [k,l,r] is given back. # findunit:=proc(D,B) local k,l,r,a,b,n,L; L:=[]; for k from 0 to B do for l from -B to B do r:=k^2-l^2*D; if r<>0 then a:=(k^2+l^2*D)/r; b:=2*k*l/r; if D mod 4=1 then n:=a^2-a*b-b^2*(D-1)/4 else n:=a^2-D*b^2 fi; if n=1 and igcd(k,l,r)=1 then L:=[op(L),[k,l,r]] fi fi od od; L end; Zio2JEkiREc2IkkiQkdGJTYpSSJrR0YlSSJsR0YlSSJyR0YlSSJhR0YlSSJiR0YlSSJuR0YlSSJMR0YlRiVGJUMlPkYuNyI/KEYoIiIhIiIiRiZJJXRydWVHJSpwcm90ZWN0ZWRHPyhGKSwkRiYhIiJGNEYmRjVDJD5GKiwmKiQpRigiIiNGNEY0KiYpRilGP0Y0RiRGNEY5QCQwRipGM0MmPkYrKiYsJkY9RjRGQEY0RjRGKkY5PkYsLCQqKkY/RjRGKEY0RilGNEYqRjlGNEAlLy1JJG1vZEdGJTYkRiQiIiVGND5GLSwoKiQpRitGP0Y0RjQqJkYrRjRGLEY0RjkqKCNGNEZQRjQpRixGP0Y0LCZGJEY0RjRGOUY0Rjk+Ri0sJkZTRjQqJkYkRjRGWEY0RjlAJDMvRi1GNC8tSSVpZ2NkR0Y2NiVGKEYpRipGND5GLjckLUkjb3BHRjY2I0YuNyVGKEYpRipGLkYlRiVGJQ== for d in {2,3,5} do print(findunit(d,5)) od; N0s3JSIiISEiIiEiIzclRiQiIiJGJjclRighIiYhI1w3JUYoISIlISNKNyVGKCEiJCEjPDclRihGJiEiKDclRihGJUYlNyVGKEYkRig3JUYoRihGJTclRigiIiNGMzclRigiIiRGMTclRigiIiVGLjclRigiIiZGKzclRjhGKiEjWTclRjhGMCEjOTclRjhGJUY4NyVGOEYoRjg3JUY4RjpGQjclRjhGPkZANyVGOkYqISNUNyVGOkYtISNCNyVGOkYmRig3JUY6RiUiIig3JUY6RihGTTclRjpGOEYoNyVGOkY8Rko3JUY6Rj5GSDclRjxGKiEjTTclRjxGMEYmNyVGPEYlIiM5NyVGPEYoRlY3JUY8RjpGJjclRjxGPkZTNyVGPkYtRjM3JUY+RjBGTTclRj5GJiIjPDclRj5GJSIjQjclRj5GKEZpbjclRj5GOEZnbjclRj5GOkZNNyVGPkY8RjM= N0s3JSIiISEiIiEiJDclRiQiIiJGJjclRighIiYhI3U3JUYoISIlISNaNyVGKEYmISNFNyVGKCEiIyEjNjclRihGJUYyNyVGKEYkRig3JUYoRihGMjclRigiIiNGMzclRigiIiRGMDclRigiIiVGLjclRigiIiZGKzclRjhGKiEjcjclRjhGJiEjQjclRjhGJUYoNyVGOEYoRig3JUY4RjpGQjclRjhGPkZANyVGOkYqISNtNyVGOkYtISNSNyVGOkYyRiY3JUY6RiUiIic3JUY6RihGTTclRjpGOEYmNyVGOkY8Rko3JUY6Rj5GSDclRjxGKiEjZjclRjxGJkYzNyVGPEYlIiM4NyVGPEYoRlY3JUY8RjpGMzclRjxGPkZTNyVGPkYtRkI3JUY+RiZGMjclRj5GMkZWNyVGPkYlIiNBNyVGPkYoRmhuNyVGPkY4RlY3JUY+RjpGMjclRj5GPEZC NyU3JSIiISEiIiEiJjclRiQiIiJGJjclRihGJEYo
<Text-field style="Heading 2" layout="Heading 2">4.21. Lucas-Lehmer-teszt a Mersenne-sz<Font encoding="UTF-8">\303\241</Font>mokra.</Text-field> # # This procedure do Lucas-Lehmer-test for Mersenne # numbers M[n]=2^n-1. The exponents are taken from # the list L. The result is the sequence of the # for which M[n] is prime. # lucaslehmer:=proc(L::list(posint)) local n,M,i,vi,nL; nL:=[]; for n in L do vi:=4; M:=2^n-1; for i to n-2 do vi:=modp(vi&^2-2,M) od; if vi=0 then nL:=[op(nL),n] fi; od; nL end; Zio2IydJIkxHNiItSSVsaXN0RyUqcHJvdGVjdGVkRzYjSSdwb3NpbnRHRik2J0kibkdGJkkiTUdGJkkiaUdGJkkjdmlHRiZJI25MR0YmRiZGJkMlPkYxNyI/JkYtRiVJJXRydWVHRilDJj5GMCIiJT5GLiwmKSIiI0YtIiIiRj4hIiI/KEYvRj5GPiwmRi1GPkY9Rj9GNj5GMC1JJW1vZHBHRik2JCwmLUkjJl5HRiY2JEYwRj1GPkY9Rj9GLkAkL0YwIiIhPkYxNyQtSSNvcEdGKTYjRjFGLUYxRiZGJkYm Mersenne:=[2,3,5,7,13,17,19,31,67,127,257]; lucaslehmer(Mersenne); L:=[i$i=2..257]; lucaslehmer(L); Ny0iIiMiIiQiIiYiIigiIzgiIzwiIz4iI0oiI24iJEYiIiRkIw== NyoiIiQiIiYiIigiIzgiIzwiIz4iI0oiJEYi N1xbbCIiIyIiJCIiJSIiJiIiJyIiKCIiKSIiKiIjNSIjNiIjNyIjOCIjOSIjOiIjOyIjPCIjPSIjPiIjPyIjQCIjQSIjQiIjQyIjRCIjRSIjRiIjRyIjSCIjSSIjSiIjSyIjTCIjTSIjTiIjTyIjUCIjUSIjUiIjUyIjVCIjVSIjViIjVyIjWCIjWSIjWiIjWyIjXCIjXSIjXiIjXyIjYCIjYSIjYiIjYyIjZCIjZSIjZiIjZyIjaCIjaSIjaiIjayIjbCIjbSIjbiIjbyIjcCIjcSIjciIjcyIjdCIjdSIjdiIjdyIjeCIjeSIjeiIjISkiIyIpIiMjKSIjJCkiIyUpIiMmKSIjJykiIygpIiMpKSIjKikiIyEqIiMiKiIjIyoiIyQqIiMlKiIjJioiIycqIiMoKiIjKSoiIyoqIiQrIiIkLCIiJC0iIiQuIiIkLyIiJDAiIiQxIiIkMiIiJDMiIiQ0IiIkNSIiJDYiIiQ3IiIkOCIiJDkiIiQ6IiIkOyIiJDwiIiQ9IiIkPiIiJD8iIiRAIiIkQSIiJEIiIiRDIiIkRCIiJEUiIiRGIiIkRyIiJEgiIiRJIiIkSiIiJEsiIiRMIiIkTSIiJE4iIiRPIiIkUCIiJFEiIiRSIiIkUyIiJFQiIiRVIiIkViIiJFciIiRYIiIkWSIiJFoiIiRbIiIkXCIiJF0iIiReIiIkXyIiJGAiIiRhIiIkYiIiJGMiIiRkIiIkZSIiJGYiIiRnIiIkaCIiJGkiIiRqIiIkayIiJGwiIiRtIiIkbiIiJG8iIiRwIiIkcSIiJHIiIiRzIiIkdCIiJHUiIiR2IiIkdyIiJHgiIiR5IiIkeiIiJCE9IiQiPSIkIz0iJCQ9IiQlPSIkJj0iJCc9IiQoPSIkKT0iJCo9IiQhPiIkIj4iJCM+IiQkPiIkJT4iJCY+IiQnPiIkKD4iJCk+IiQqPiIkKyMiJCwjIiQtIyIkLiMiJC8jIiQwIyIkMSMiJDIjIiQzIyIkNCMiJDUjIiQ2IyIkNyMiJDgjIiQ5IyIkOiMiJDsjIiQ8IyIkPSMiJD4jIiQ/IyIkQCMiJEEjIiRCIyIkQyMiJEQjIiRFIyIkRiMiJEcjIiRIIyIkSSMiJEojIiRLIyIkTCMiJE0jIiROIyIkTyMiJFAjIiRRIyIkUiMiJFMjIiRUIyIkVSMiJFYjIiRXIyIkWCMiJFkjIiRaIyIkWyMiJFwjIiRdIyIkXiMiJF8jIiRgIyIkYSMiJGIjIiRjIyIkZCM= Ny0iIiQiIiYiIigiIzgiIzwiIz4iI0oiI2giIyopIiQyIiIkRiI=
<Text-field style="Heading 2" layout="Heading 2">4.22. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.23. Val<Font encoding="UTF-8">\303\263</Font>sz<Font encoding="UTF-8">\303\255</Font>n<Font encoding="UTF-8">\305\261</Font>s<Font encoding="UTF-8">\303\251</Font>gi teszt.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.24. Feladat.</Text-field> interface(verboseproc=2); IiIi print(`isprime`); Zio2I0kibkc2IjYmSSVidG9yR0YlSSNuckdGJUkicEdGJUkickdGJTYlSSlyZW1lbWJlckdGJUknc3lzdGVtRyUqcHJvdGVjdGVkR0lpcENvcHlyaWdodH4oYyl+MTk5M35HYXN0b25+R29ubmV0LH5XaXNzZW5zY2hhZnRsaWNoZXN+UmVjaG5lbix+RVRIflp1cmljaC5+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiVFXHMhQyRAJDQtSSV0eXBlR0YuNiRGJC5JKGludGVnZXJHRi5AJS1GNTYkRiQuSShudW1lcmljR0YuWVE8YXJndW1lbnR+bXVzdH5iZX5hbn5pbnRlZ2VyRiVPLi1JKGlzcHJpbWVHNiRGLkkoX3N5c2xpYkdGJUYjQC8yRiQiIiNJJmZhbHNlR0YuLUknbWVtYmVyR0YuNiRGJEkqaXNwcmltZS93R0ZFSSV0cnVlR0YuMC1JJWlnY2RHRi42JCJGcWd2SnQ5LUp2QyU9YiVSJ3pjMEJGJCIiIkZJMkYkIiYsLSJGTjAtRlE2JCJmYmw4cid5I2YiKkdYQ3gvdkBtcD9aMXFXa1hmSixqKmZBZyo+RE0neSRvaStiR0FBWykpSDd2Vz9zcElZJG8mZkRoJ2VuOzNFdlEhUk9PUGFSRkUtQ3REXFxpWy9peWsxOEpqSVAqKXBwPWQiKXlTayQqeWx0RTY4dXd2bUknSCd6dCQpSHMnUSNvKDREUUwqXGgpRyFvJz1yInB5NHY4NCY0dFpwITQ0UnAyRiQqUT9ValVYOmhPRiQqW21laWcjZicqXHQ9NCpSQmA1Ij1NQipbcHBcKUYkRlRGSTJGJCIoIjM9NUZOTy1JLGdtcF9pc3ByaW1lR0YuRiNGJUYlRiU=
<Text-field style="Heading 2" layout="Heading 2">4.25. Megjegyz<Font encoding="UTF-8">\303\251</Font>s.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.26. Williams p+1 m<Font encoding="UTF-8">\303\263</Font>dszere.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.27. Lemma.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">4.28. Feladat.</Text-field> # # This procedure is Williams' p+1 method for factorization of n. # P is the parameter for the Lucas sequence. Calculation of V's # goes up to V_k!. The result is the factor found; # gcd is calculated after m steps. # williams:=proc(n::posint,P::integer,k::posint,m::posint) local g,x,i,j; x:=P; for i from 2 by m to k do for j from i to i+m-1 while j<=k do x:=lucasV(j,x,1,n)[1]; od; g:=igcd(x-2,n); if g>1 then RETURN(g) fi; od; igcd(x-2,n) end; Zio2JidJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJQR0YmSShpbnRlZ2VyR0YoJ0kia0dGJkYnJ0kibUdGJkYnNiZJImdHRiZJInhHRiZJImlHRiZJImpHRiZGJkYmQyU+RjJGKj8oRjMiIiNGL0YtSSV0cnVlR0YoQyU/KEY0RjMiIiIsKEYzRjxGL0Y8RjwhIiIxRjRGLT5GMiYtSSdsdWNhc1ZHRiY2JkY0RjJGPEYlNiNGPD5GMS1JJWlnY2RHRig2JCwmRjJGPEY4Rj5GJUAkMkY8RjEtSSdSRVRVUk5HRig2I0YxRkdGJkYmRiY= williams(25852,3,10,1); williams(999863*999883*999907,3,1000,1); IiIl IicyKioqKg==
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">5. Alkalmaz\303\241sok </Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">6. Sz\303\241mok \303\251s polinomok</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">7. Gyors Fourier-transzform\303\241ci\303\263</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">8. Elliptikus f\303\274ggv\303\251nyek</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251ken</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251kkel</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">12. Polinomfaktoriz\303\241l\303\241s</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">13. A szita m\303\263dszerek alapjai</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1">14. Az AKS teszt</Text-field>
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn