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; Zio2J0kickc2Ikkic0dGJUkiREdGJUkiaEdGJUkiTkdGJTYkSSJQR0YlSSJhR0YlRiVGJUMmPkYsLCZGJCIiIiomRiZGMC1JJXNxcnRHRiU2I0YnRjBGMD5GKywoRiRGMEYxRjAqJiwmRiRGMEYxISIiRjAsJiokKUYkIiIjRjBGMComKUYmRj1GMEYnRjBGOUY5RjBAJDQtSSV0eXBlRyUqcHJvdGVjdGVkRzYkRitJKGludGVnZXJHRkQtSSZFUlJPUkdGRDYkLCZGLEYwKiRGLEY5RjBJL25vdH5hbn5pbnRlZ2VyR0YlJi1JJ2x1Y2FzVkdGJTYmRihGK0YwRik2I0YwRiVGJUYl
<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/KEYmIiIlRikiIz9GLC1JJnByaW50R0YtNiQtSShpc3ByaW1lRzYkRi1JKF9zeXNsaWJHRiM2IywmKiZGJUYpKSIiI0YmRilGKUYpISIiLUkscmllc2Vsc3FydDNHRiNGJEYjRiNGIw== 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; Zio2J0kiaEc2IkkibkdGJUkickdGJUkic0dGJUkiREc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYlSSJOR0YlSSJ2R0YlSSJpR0YlRiVGJUMpQCQxKSIiI0YmRiRZNiRRPWZpcnN0fnBhcmFtZXRlcn5pc350b29+bGFyZ2VGJUYkQCQtSSV0eXBlR0YrNiRGJEklZXZlbkdGK1k2JFE/Zmlyc3R+cGFyYW1ldGVyfmhhdmV+dG9+YmV+b2RkRiVGJEAkMkYmRjVZNiRRPnNlY29uZH5wYXJhbWV0ZXJ+aXN+dG9vfnNtYWxsRiVGJD5GLiwmKiZGJCIiIkY0RklGSUZJISIiPkYvLUkscmllc2Vsc2V0dXBHRiU2J0YnRihGKUYkRi4/KEYwRklGSSwmRiZGSUY1RkpJJXRydWVHRis+Ri8tSSRtb2RHRiU2JCwmKiQpRi9GNUZJRklGNUZKRi4tSSZldmFsYkdGKzYjL0YvIiIhRiVGJUYl # # 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+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiVGJUMkQCQ0LUkldHlwZUdGLjYkRiQuSShpbnRlZ2VyR0YuQCUtRjQ2JEYkLkkobnVtZXJpY0dGLllRPGFyZ3VtZW50fm11c3R+YmV+YW5+aW50ZWdlckYlTy4tSShpc3ByaW1lRzYkRi5JKF9zeXNsaWJHRiVGI0AvMkYkIiIjSSZmYWxzZUdGLi1JJ21lbWJlckdGLjYkRiRJKmlzcHJpbWUvd0dGJUkldHJ1ZUdGLjAtSSVpZ2NkR0YuNiQiRnFndkp0OS1KdkMlPWIlUid6YzBCRiQiIiJGSDJGJCImLC0iRk0wLUZQNiQiZmJsOHIneSNmIipHWEN4L3ZAbXA/WjFxV2tYZkosaipmQWcqPkRNJ3kkb2krYkdBQVspKUg3dlc/c3BJWSRvJmZEaCdlbjszRXZRIVJPT1BhUkZFLUN0RFxcaVsvaXlrMThKaklQKilwcD1kIil5U2skKnlsdEU2OHV3dm1JJ0gnenQkKUhzJ1Ejbyg0RFFMKlxoKUchbyc9ciJweTR2ODQmNHRacCE0NFJwMkYkKlE/VWpVWDpoT0YkKlttZWlnI2YnKlx0PTQqUkJgNSI9TUIqW3BwXClGJEZTRkgyRiQiKCIzPTVGTU8tSSxnbXBfaXNwcmltZUdGLkYjRiVGJUYl # # This is a commented version of the Maple # function isprime. The details of the procedure are # given. # # The input is the positive integer n to test. # # After typecheking the number is tested whether contained in a list # of primes below 100 called isprime/w. If yes, it is a prime. # The second step to check whether it has a gcd>1 with the # product of these primes. If yes, it is composite. Now any input # less then 10201 is a prime. The next step to try whether our # number has a gcd>1 with the product of primes larger then 100 but # less then 1000. If yes, the number is composite. After this, any number # below 1009^2 is a prime. # # The next step is some kind of probabilistic test. First, # the gcd with (2*3*5*7)^25 is removed from n-1 to # obtain a residue r. Then btor;=2^r mod n calculated and # then the `cyclotest` is called four times with # bases 2,3,5 and 7, modulus n, with btor and the residue r. # If the cyclotest proves a composite number then false returned. # # The last step is some kind of Lucas test testing that # for some D=p^2-4*q where q=1 for which (D|n)=-1 we have # [V(k+1),V(k)] mod n=[2,p]. # > > isprime=proc(n) > local btor,nr,p,r; > options remember,system,`Copyright 1993 by Waterloo Maple Software`; > if not type(n,integer) then > if type(n,numeric) then ERROR(`argument must be an integer`) > else RETURN('isprime(n)') > fi > fi; > if n < 2 then false > elif has(`isprime/w`,n) then true > elif igcd(2305567963945518424753102147331756070,n) <> 1 then false > elif n < 10201 then true > elif igcd(8496969489233418110532339909187349965926062586648932736611545426342203893270769390909069477309509137509786917118668028861499333825097682386722983737962963066757674131126736578936440788157186969893730633113066478620448624949257324022627395437363639038752608166758661255956834630697220447512298848222228550062683786342519960225996301315945644470064720696621750477244528915927867113,n) <> 1 then > false > elif n < 1018081 then true > else > nr := igcd(408410100000,n-1); > nr := igcd(nr^5,n-1); > r := iquo(n-1,nr); > btor := modp(power(2,r),n); > if `isprime/cyclotest`(n,btor,2,r) = false or > irem(nr,3) = 0 and `isprime/cyclotest`(n,btor,3,r) = false or > irem(nr,5) = 0 and `isprime/cyclotest`(n,btor,5,r) = false or > irem(nr,7) = 0 and `isprime/cyclotest`(n,btor,7,r) = false then > RETURN(false) > fi; > for p from 3 while numtheory[jacobi](p^2-4,n) <> -1 do od; > evalb(`isprime/TraceModQF`(p,n+1,n) = [2,p]) > fi > end; L0koaXNwcmltZUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2ImYqNiNJIm5HRic2JkklYnRvckdGJ0kjbnJHRidJInBHRidJInJHRic2JUkpcmVtZW1iZXJHRidJJ3N5c3RlbUdGJUlKQ29weXJpZ2h0fjE5OTN+Ynl+V2F0ZXJsb29+TWFwbGV+U29mdHdhcmVHRidGJ0MkQCQ0LUkldHlwZUdGJTYkRipJKGludGVnZXJHRiVAJS1GODYkRipJKG51bWVyaWNHRiUtSSZFUlJPUkdGJTYjSTxhcmd1bWVudH5tdXN0fmJlfmFufmludGVnZXJHRictSSdSRVRVUk5HRiU2Iy4tRiNGKUAvMkYqIiIjSSZmYWxzZUdGJS1JJGhhc0dGJTYkSSppc3ByaW1lL3dHRidGKkkldHJ1ZUdGJTAtSSVpZ2NkR0YlNiQiRnFndkp0OS1KdkMlPWIlUid6YzBCRioiIiJGSzJGKiImLC0iRlAwLUZTNiQiZmJsOHIneSNmIipHWEN4L3ZAbXA/WjFxV2tYZkosaipmQWcqPkRNJ3kkb2krYkdBQVspKUg3dlc/c3BJWSRvJmZEaCdlbjszRXZRIVJPT1BhUkZFLUN0RFxcaVsvaXlrMThKaklQKilwcD1kIil5U2skKnlsdEU2OHV3dm1JJ0gnenQkKUhzJ1Ejbyg0RFFMKlxoKUchbyc9ciJweTR2ODQmNHRacCE0NFJwMkYkKlE/VWpVWDpoT0YkKlttZWlnI2YnKlx0PTQqUkJgNSI9TUIqW3BwXClGKkZWRksyRioiKCIzPTVGUEMpPkYtLUZTNiQiLSsrNTUlMyUsJkYqRlZGViEiIj5GLS1GUzYkKiQpRi0iIiZGVkZebz5GLy1JJWlxdW9HRiU2JEZeb0YtPkYsLUklbW9kcEdGJTYkLUkmcG93ZXJHRic2JEZKRi9GKkAkNTU1Ly1JMmlzcHJpbWUvY3ljbG90ZXN0R0YnNiZGKkYsRkpGL0ZLMy8tSSVpcmVtR0YlNiRGLSIiJCIiIS8tRmdwNiZGKkYsRl5xRi9GSzMvLUZccTYkRi1GZW9GX3EvLUZncDYmRipGLEZlb0YvRkszLy1GXHE2JEYtIiIoRl9xLy1GZ3A2JkYqRixGXnJGL0ZLLUZENiNGSz8oRi5GXnFGVkYnMC0mSSpudW10aGVvcnlHRic2I0knamFjb2JpR0YnNiQsJiokKUYuRkpGVkZWIiIlRl9vRipGX29GJy1JJmV2YWxiR0YlNiMvLUkzaXNwcmltZS9UcmFjZU1vZFFGR0YnNiVGLiwmRipGVkZWRlZGKjckRkpGLkYnRidGJw== > > # # This is the initial list of primes. # > > isprime/w=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; LyomSShpc3ByaW1lRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSJ3R0YoISIiNzsiIiMiIiQiIiYiIigiIzYiIzgiIzwiIz4iI0IiI0giI0oiI1AiI1QiI1YiI1oiI2AiI2YiI2giI24iI3IiI3QiI3oiIyQpIiMqKSIjKCo= > > # # This is the probabilistic primality test some # with refinements. # # The input parameters are the number n to test, # a residue r of n-1 from which the gcd with # (2*3*5*7)^25 is removed, btor=2^r mod n and # one of the numbers 2, 3, 5 and 7. # # The test run only with the base 2. At most # The last 25 step of the test is done, but # for i=3,5,7 also possible to check something # similar to the probabilistic test: if x^3 mod n=1 # and n is a prime then in the case x mod n<>1 # the congruence x^2+x+1 mod n=0 have to be satisfied. # This gives some additional information if 3|n-1. # Similar trick works for 5|n-1, 7|n-1, etc. # > > isprime/cyclotest=proc(n,btor,i,r) > local nr,k,t,s,x; > options `Copyright 1993 by Waterloo Maple Software`; > nr := iquo(n-1,r); > for k from 0 while irem(nr,i,'t') = 0 do nr := t od; > x := modp(power(btor,nr),n); > if x = 1 then RETURN(FAIL) fi; > to k do > s := `isprime/sumxtor`(x,i,n); > if s[1] = 0 then RETURN(FAIL) elif s[2] = 1 then RETURN(false) fi; > x := s[2] > od; > false > end; LyomSShpc3ByaW1lRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSpjeWNsb3Rlc3RHRighIiJmKjYmSSJuR0YoSSVidG9yR0YoSSJpR0YoSSJyR0YoNidJI25yR0YoSSJrR0YoSSJ0R0YoSSJzR0YoSSJ4R0YoNiNJSkNvcHlyaWdodH4xOTkzfmJ5fldhdGVybG9vfk1hcGxlflNvZnR3YXJlR0YoRihDKD5GMy1JJWlxdW9HRiY2JCwmRi5GKUYpRitGMT8oRjQiIiFGKUYoLy1JJWlyZW1HRiY2JUYzRjAuRjVGQT5GM0Y1PkY3LUklbW9kcEdGJjYkLUkmcG93ZXJHRig2JEYvRjNGLkAkL0Y3RiktSSdSRVRVUk5HRiY2I0klRkFJTEdGJj8oRihGKUYpRjRJJXRydWVHRiZDJT5GNi1JMGlzcHJpbWUvc3VteHRvckdGKDYlRjdGMEYuQCYvJkY2NiNGKUZBRlEvJkY2NiMiIiNGKS1GUjYjSSZmYWxzZUdGJj5GN0Zbb0Zgb0YoRihGKA== > > # # This procedure calculates the pair # [(1+x+..+x^(r-1) mod n, x^r mod n]. # # For r<6 direct calculation used. # Otherwise r is written as a*r1+b # with r1~sqrt(r) and the pair is # recursively calculated. # > > isprime/sumxtor=proc(x,r,n) > local i1,i2,i3,r1,r2,r3,s,xj; > options `Copyright 1993 by Waterloo Maple Software`; > if r < 1 then ERROR(`r is too small`) > elif r = 1 then [1,x] > elif r < 6 then > s := x+1; > xj := modp(x^2,n); > to r-2 do s := s+xj; xj := modp(xj*x,n) od; > [modp(s,n),xj] > else > i1 := isqrt(r); > i2 := iquo(r,i1,'i3'); > if i3 = 0 then > r2 := procname(x,i2,n); > r1 := procname(r2[2],i1,n); > [modp(r2[1]*r1[1],n),r1[2]] > else > r3 := procname(x,i3,n); > r2 := procname(x,i2,n); > r1 := procname(r2[2],i1,n); > [modp(r3[1]+r3[2]*modp(r2[1]*r1[1],n),n),modp(r3[2]*r1[2],n)] > fi > fi > end; LyomSShpc3ByaW1lRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSShzdW14dG9yR0YoISIiZio2JUkieEdGKEkickdGKEkibkdGKDYqSSNpMUdGKEkjaTJHRihJI2kzR0YoSSNyMUdGKEkjcjJHRihJI3IzR0YoSSJzR0YoSSN4akdGKDYjSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQCkyRi9GKS1JJkVSUk9SR0YmNiNJL3J+aXN+dG9vfnNtYWxsR0YoL0YvRik3JEYpRi4yRi8iIidDJj5GOCwmRi5GKUYpRik+RjktSSVtb2RwR0YmNiQqJClGLiIiI0YpRjA/KEYoRilGKSwmRi9GKUZPRitJJXRydWVHRiZDJD5GOCwmRjhGKUY5Rik+RjktRks2JComRjlGKUYuRilGMDckLUZLNiRGOEYwRjlDJT5GMi1JJmlzcXJ0R0YmNiNGLz5GMy1JJWlxdW9HRiY2JUYvRjIuRjRAJS9GNCIiIUMlPkY2LSUpcHJvY25hbWVHNiVGLkYzRjA+RjUtRmdvNiUmRjY2I0ZPRjJGMDckLUZLNiQqJiZGNjYjRilGKSZGNUZjcEYpRjAmRjVGXXBDJj5GNy1GZ282JUYuRjRGMEZlb0ZpbzckLUZLNiQsJiZGN0ZjcEYpKiYmRjdGXXBGKUZfcEYpRilGMC1GSzYkKiZGYHFGKUZlcEYpRjBGKEYoRig= > > # # This subroutine calculate the Lucas sequence # terms [V(k),V(k-1)] modulo n. # # The input parameters are the modulus n, # p (and q=1 supposed) and k. # # First, the binary form of k-1 is calculated. # Then starting from [V(1),V(0)], the result # is calculated by the recursion of the V's. # > > isprime/TraceModQF=proc(p,k,n) > local i,kk,trc,v; > options `Copyright 1993 by Waterloo Maple Software`; > kk := k; > for i while 1 < kk do kk := iquo(kk+1,2,v[i]) od; > trc := [p,2]; > for i from i-1 by -1 to 1 do > if v[i] = 1 then trc := modp([trc[1]^2-2,trc[1]*trc[2]-p],n) > else trc := modp([trc[1]*trc[2]-p,trc[2]^2-2],n) > fi > od; > trc > end; LyomSShpc3ByaW1lRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSStUcmFjZU1vZFFGR0YoISIiZio2JUkicEdGKEkia0dGKEkibkdGKDYmSSJpR0YoSSNra0dGKEkkdHJjR0YoSSJ2R0YoNiNJSkNvcHlyaWdodH4xOTkzfmJ5fldhdGVybG9vfk1hcGxlflNvZnR3YXJlR0YoRihDJz5GM0YvPyhGMkYpRilGKDJGKUYzPkYzLUklaXF1b0dGJjYlLCZGM0YpRilGKSIiIyZGNTYjRjI+RjQ3JEYuRkE/KEYyLCZGMkYpRilGK0YrRilJJXRydWVHRiZAJS9GQkYpPkY0LUklbW9kcEdGJjYkNyQsJiokKSZGNDYjRilGQUYpRilGQUYrLCYqJkZTRikmRjQ2I0ZBRilGKUYuRitGMD5GNC1GTTYkNyRGVSwmKiQpRldGQUYpRilGQUYrRjBGNEYoRihGKA== > > >
<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">13. Az AKS-teszt</Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">14. A szita m\303\263dszerek alapjai</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">15. Sz\303\241mtest szita</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1">16. Vegyes probl<Font encoding="UTF-8">\303\251</Font>m<Font encoding="UTF-8">\303\241</Font>k</Text-field>
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn