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

restart; with(numtheory);

N1FJJkdJZ2NkRzYiSSliaWdvbWVnYUdGJEkmY2ZyYWNHRiRJKWNmcmFjcG9sR0YkSStjeWNsb3RvbWljR0YkSSlkaXZpc29yc0dGJEkpZmFjdG9yRVFHRiRJKmZhY3RvcnNldEdGJEknZmVybWF0R0YkSSlpbWFndW5pdEdGJEkmaW5kZXhHRiRJL2ludGVncmFsX2Jhc2lzR0YkSSlpbnZjZnJhY0dGJEknaW52cGhpR0YkSSppc3NxcmZyZWVHRiRJJ2phY29iaUdGJEkqa3JvbmVja2VyR0YkSSdsYW1iZGFHRiRJKWxlZ2VuZHJlR0YkSSltY29tYmluZUdGJEkpbWVyc2VubmVHRiRJKG1pZ2NkZXhHRiRJKm1pbmtvd3NraUdGJEkobWlwb2x5c0dGJEklbWxvZ0dGJEknbW9iaXVzR0YkSSZtcm9vdEdGJEkmbXNxcnRHRiRJKW5lYXJlc3RwR0YkSSpudGhjb252ZXJHRiRJKW50aGRlbm9tR0YkSSludGhudW1lckdGJEknbnRocG93R0YkSSZvcmRlckclKnByb3RlY3RlZEdJKXBkZXhwYW5kR0YkSSRwaGlHRiRJI3BpR0YkSSpwcHJpbXJvb3RHRiRJKXByaW1yb290R0YkSShxdWFkcmVzR0YkSStyb290c3VuaXR5R0YkSSpzYWZlcHJpbWVHRiRJJnNpZ21hR0YkSSpzcTJmYWN0b3JHRiRJKHN1bTJzcXJHRiRJJHRhdUdGJEkldGh1ZUdGJA==

# # This procedure do Wilson's test. The return value # is a pair of lower two digits of (n-1)!+1 in base n. # wilsontest:=proc(n::posint) local i,r,m; r:=1; m:=n^2; for i from 2 to n-1 do r:=r*i mod m od; r:=r+1 mod m; [irem(r,n),iquo(r,n)] end;

Zio2IydJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEc2JUkiaUdGJkkickdGJkkibUdGJkYmRiZDJz5GKyIiIj5GLCokKUYlIiIjRi8/KEYqRjNGLywmRiVGL0YvISIiSSV0cnVlR0YoPkYrLUkkbW9kR0YmNiQqJkYrRi9GKkYvRiw+RistRjo2JCwmRitGL0YvRi9GLDckLUklaXJlbUdGKDYkRitGJS1JJWlxdW9HRihGREYmRiZGJg==

# # This procedure do Wilson's test and # look for Wilson numbers until a given # limit. # wilson:=proc(n) local i,r,p,w; p:=[]; w:=[]; for i from 2 to n do r:=wilsontest(i); if r[1]=0 then p:=[op(p),i]; if r[2]=0 then w:=[op(w),i] fi fi od; [w,p] end;

Zio2I0kibkc2IjYmSSJpR0YlSSJyR0YlSSJwR0YlSSJ3R0YlRiVGJUMmPkYpNyI+RipGLT8oRiciIiMiIiJGJEkldHJ1ZUclKnByb3RlY3RlZEdDJD5GKC1JK3dpbHNvbnRlc3RHRiU2I0YnQCQvJkYoNiNGMSIiIUMkPkYpNyQtSSNvcEdGMzYjRilGJ0AkLyZGKDYjRjBGPT5GKjckLUZCNiNGKkYnNyRGKkYpRiVGJUYl

wilson(1000);

NyQ3JSIiJiIjOCIkaiY3ZHUiIiMiIiRGJCIiKCIjNkYlIiM8IiM+IiNCIiNIIiNKIiNQIiNUIiNWIiNaIiNgIiNmIiNoIiNuIiNyIiN0IiN6IiMkKSIjKikiIygqIiQsIiIkLiIiJDIiIiQ0IiIkOCIiJEYiIiRKIiIkUCIiJFIiIiRcIiIkXiIiJGQiIiRqIiIkbiIiJHQiIiR6IiIkIj0iJCI+IiQkPiIkKD4iJCo+IiQ2IyIkQiMiJEYjIiRIIyIkTCMiJFIjIiRUIyIkXiMiJGQjIiRqIyIkcCMiJHIjIiR4IyIkIkciJCRHIiQkSCIkMiQiJDYkIiQ4JCIkPCQiJEokIiRQJCIkWiQiJFwkIiRgJCIkZiQiJG4kIiR0JCIkeiQiJCRRIiQqUSIkKFIiJCwlIiQ0JSIkPiUiJEAlIiRKJSIkTCUiJFIlIiRWJSIkXCUiJGQlIiRoJSIkaiUiJG4lIiR6JSIkKFsiJCJcIiQqXCIkLiYiJDQmIiRAJiIkQiYiJFQmIiRaJiIkZCZGJiIkcCYiJHImIiR4JiIkKGUiJCRmIiQqZiIkLCciJDInIiQ4JyIkPCciJD4nIiRKJyIkVCciJFYnIiRaJyIkYCciJGYnIiRoJyIkdCciJHgnIiQkbyIkInAiJCwoIiQ0KCIkPigiJEYoIiRMKCIkUigiJFYoIiReKCIkZCgiJGgoIiRwKCIkdCgiJCh5IiQoeiIkNCkiJDYpIiRAKSIkQikiJEYpIiRIKSIkUikiJGApIiRkKSIkZikiJGopIiR4KSIkIikpIiQkKSkiJCgpKSIkMioiJDYqIiQ+KiIkSCoiJFAqIiRUKiIkWioiJGAqIiRuKiIkcioiJHgqIiQkKSoiJCIqKiIkKCoq

n:=(2^28-9)/7; 3&^(n-1) mod n; 2&^(n-1)mod n;

IilAek1R

IiIi

IikqW0QtIg==

# # This recursive procedure calculates # the Jacobi symbol (n|m) for integers # m>2 and n, where m is odd. # jacobisymbol:=proc(n::integer,m::posint) local s; if type(m,even) then error "second argument must be odd" fi; if n=0 then RETURN(0) fi; if n=1 then RETURN(1) fi; if n<0 then if type((m-1)/2,odd) then RETURN(-jacobisymbol(-n,m)) else RETURN(jacobisymbol(-n,m)) fi fi; if type(n,even) then if type((irem(m,16)^2-1)/8,odd) then RETURN(-jacobisymbol(n/2,m)) else RETURN(jacobisymbol(n/2,m)) fi fi; if n>m then RETURN(jacobisymbol(irem(n,m),m)) fi; if type(irem((m-1)/2,2)*irem((n-1)/2,2),odd) then -jacobisymbol(m,n) else jacobisymbol(m,n) fi end;

Zio2JCdJIm5HNiJJKGludGVnZXJHJSpwcm90ZWN0ZWRHJ0kibUdGJkkncG9zaW50R0YoNiNJInNHRiZGJkYmQylAJC1JJXR5cGVHRig2JEYqSSVldmVuR0YoWVE8c2Vjb25kfmFyZ3VtZW50fm11c3R+YmV+b2RkRiZAJC9GJSIiIS1JJ1JFVFVSTkdGKDYjRjhAJC9GJSIiIi1GOjYjRj5AJDJGJUY4QCUtRjE2JCwmKiYjRj4iIiNGPkYqRj5GPkZIISIiSSRvZGRHRigtRjo2IywkLUktamFjb2Jpc3ltYm9sR0YmNiQsJEYlRkpGKkZKLUY6NiNGT0AkLUYxNiRGJUYzQCUtRjE2JCwmKiYjRj4iIilGPiktSSVpcmVtR0YoNiRGKiIjO0ZJRj5GPkZnbkZKRkstRjo2IywkLUZQNiQsJComRkhGPkYlRj5GPkYqRkotRjo2I0Zhb0AkMkYqRiUtRjo2Iy1GUDYkLUZbbzYkRiVGKkYqQCUtRjE2JComLUZbbzYkRkZGSUY+LUZbbzYkLCZGZG9GPkZIRkpGSUY+RkssJC1GUDYkRipGJUZKRmlwRiZGJkYm

debug(jacobisymbol); jacobisymbol(76,131);

SS1qYWNvYmlzeW1ib2xHNiI=

{--> enter jacobisymbol, args = 76, 131 {--> enter jacobisymbol, args = 38, 131 {--> enter jacobisymbol, args = 19, 131 {--> enter jacobisymbol, args = 131, 19 {--> enter jacobisymbol, args = 17, 19 {--> enter jacobisymbol, args = 19, 17 {--> enter jacobisymbol, args = 2, 17 {--> enter jacobisymbol, args = 1, 17 <-- exit jacobisymbol (now in jacobisymbol) = 1} <-- exit jacobisymbol (now in jacobisymbol) = 1} <-- exit jacobisymbol (now in jacobisymbol) = 1}

IiIi

<-- exit jacobisymbol (now in jacobisymbol) = 1} <-- exit jacobisymbol (now in jacobisymbol) = 1}

ISIi

<-- exit jacobisymbol (now in jacobisymbol) = 1} <-- exit jacobisymbol (now in jacobisymbol) = 1} <-- exit jacobisymbol (now at top level) = 1}

ISIi

interface(verboseproc=2);

IiIi

print(jacobi);

Zio2JCdJImFHNiItSSNPckdGJjYkSShpbnRlZ2VyRyUqcHJvdGVjdGVkRy1JJE5vdEdGJjYjSSljb25zdGFudEdGKydJImJHRiYtRig2JEkqbm9ubmVnaW50R0YrRiw2JUkjYjJHRiZJInFHRiZJInNHRiY2I0lhb0NvcHlyaWdodH4oYyl+MTk5Mn5ieX50aGV+VW5pdmVyc2l0eX5vZn5XYXRlcmxvby5+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiZGJkMkQCYwJSZuYXJnc0ciIiNZNiRRQmV4cGVjdGluZ34yfmFyZ3VtZW50cyx+YnV0fmdvdH4lMUYmRj40My1JJXR5cGVHRis2JEYlLkYqLUZGNiRGMS5GNE8tLiUpcHJvY25hbWVHNiMlJWFyZ3NHQCUzLy1JJWlyZW1HRis2JEYlRj8iIiEvLUZWNiRGMUY/RlhGWEMnPkY2RjE/KEYmIiIiRmluRiYvLUZWNiVGNiIiJS5GN0ZYPkY2RjdAJS8tRlY2JUY2Rj9GXm9GWEMkRl9vPkY4LUkramFjb2JpX2F1eEdGJjYkRj8tSSRhYnNHRis2I0YlPkY4RmluQCQzMkYlRlgvLUZWNiRGNkZdbyIiJD5GOCwkRjghIiIqJkY4RmluLUZnbzYkRmlvRjZGaW5GJkYmNiRGZ29GZ28=

print(legendre);

Zio2JCdJImFHNiItSSNPckdGJjYkSShpbnRlZ2VyRyUqcHJvdGVjdGVkRy1JJE5vdEdGJjYjSSljb25zdGFudEdGKydJInBHRiYtRig2JEkmcHJpbWVHRiZGLEYmNiNJaW5Db3B5cmlnaHR+KGMpfjE5OTR+Ynl+V2F0ZXJsb29+TWFwbGV+SW5jLn5BbGx+cmlnaHRzfnJlc2VydmVkLkdGJkYmQCcwJSZuYXJnc0ciIiNZNiRRQmV4cGVjdGluZ34yfmFyZ3VtZW50cyx+YnV0fmdvdH4lMUYmRjkzLUkldHlwZUdGKzYkRiUuRiotRkA2JEYxLkY0LSZJKm51bXRoZW9yeUc2JEYrSShfc3lzbGliR0YmNiMuSSdqYWNvYmlHRiY2JEYlRjFPLS4lKXByb2NuYW1lRzYjJSVhcmdzR0YmRiY2JEZNSSdqYWNvYmlHNiRGKy9JK21vZHVsZW5hbWVHRiZGSA==

n:=561; 5&^(n-1) mod n; 5&^((n-1)/2) mod n; jacobi(5,n);

IiRoJg==

IiIi

IiNu

IiIi

millerrabin:=proc(n::posint,b::posint) local j,e,r,bb; if n<9 then ERROR(`first parameter is too small`,n) fi; if type(n,even) then ERROR(`first parameter is even`,n) fi; if b<2 then ERROR(`second parameter is too small`,b) fi; if n<=b then ERROR(`second parameter is too large`,b) fi; e:=0; r:=n-1; while type(r,even) do e:=e+1; r:=r/2 od; bb:=modp(b&^r,n); if bb=1 then RETURN(FAIL) fi; for j to e while bb<>n-1 do bb:=modp(bb&^2,n) od; if j=e+1 then RETURN(false) fi; FAIL; end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJiR0YmRic2JkkiakdGJkkiZUdGJkkickdGJkkjYmJHRiZGJkYmQy5AJDJGJSIiKi1JJkVSUk9SR0YoNiRJPWZpcnN0fnBhcmFtZXRlcn5pc350b29+c21hbGxHRiZGJUAkLUkldHlwZUdGKDYkRiVJJWV2ZW5HRigtRjU2JEk4Zmlyc3R+cGFyYW1ldGVyfmlzfmV2ZW5HRiZGJUAkMkYqIiIjLUY1NiRJPnNlY29uZH5wYXJhbWV0ZXJ+aXN+dG9vfnNtYWxsR0YmRipAJDFGJUYqLUY1NiRJPnNlY29uZH5wYXJhbWV0ZXJ+aXN+dG9vfmxhcmdlR0YmRio+Ri0iIiE+Ri4sJkYlIiIiRk8hIiI/KEYmRk9GT0YmLUY6NiRGLkY8QyQ+Ri0sJkYtRk9GT0ZPPkYuLCQqJiNGT0ZCRk9GLkZPRk8+Ri8tSSVtb2RwR0YoNiQtSSMmXkdGJjYkRipGLkYlQCQvRi9GTy1JJ1JFVFVSTkdGKDYjSSVGQUlMR0YoPyhGLEZPRk9GLTBGL0ZOPkYvLUZnbjYkLUZqbjYkRi9GQkYlQCQvRixGVi1GX282I0kmZmFsc2VHRihGYW9GJkYmRiY=

rabin:=proc(n::posint,m::posint) local i,j,b,e,r,rnd; if n<9 then ERROR(`first parameter is too small`,n) fi; if type(n,even) then ERROR(`first parameter is even`,n) fi; rnd:=rand(2..n-1); e:=0; r:=n-1; while type(r,even) do e:=e+1; r:=r/2 od; for i to m do b:=rnd(); if 1<gcd(b,n) then RETURN(false) fi; modp(b&^r,n); if %=1 then next fi; for j to e while %<>n-1 do modp(%&^2,n) od; if j=e+1 then RETURN(false) fi; od; FAIL end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJtR0YmRic2KEkiaUdGJkkiakdGJkkiYkdGJkkiZUdGJkkickdGJkkkcm5kR0YmRiZGJkMqQCQyRiUiIiotSSZFUlJPUkdGKDYkST1maXJzdH5wYXJhbWV0ZXJ+aXN+dG9vfnNtYWxsR0YmRiVAJC1JJXR5cGVHRig2JEYlSSVldmVuR0YoLUY3NiRJOGZpcnN0fnBhcmFtZXRlcn5pc35ldmVuR0YmRiU+RjEtSSVyYW5kR0YmNiM7IiIjLCZGJSIiIkZJISIiPkYvIiIhPkYwRkg/KEYmRklGSUYmLUY8NiRGMEY+QyQ+Ri8sJkYvRklGSUZJPkYwLCQqJiNGSUZHRklGMEZJRkk/KEYsRklGSUYqSSV0cnVlR0YoQyg+Ri4tRjFGJkAkMkZJLUkkZ2NkR0YmNiRGLkYlLUknUkVUVVJOR0YoNiNJJmZhbHNlR0YoLUklbW9kcEdGKDYkLUkjJl5HRiY2JEYuRjBGJUAkL0kiJUdGJkZJXD8oRi1GSUZJRi8wRmhvRkgtRmFvNiQtRmRvNiRGaG9GR0YlQCQvRi1GU0Zcb0klRkFJTEdGKEYmRiZGJg==

trueisprime:=proc(n::posint) local f; if n<2 then RETURN(false) fi; if n=2 or n=3 or n=5 or n=7 or n=11 or n=13 then RETURN(true) fi; if 1<gcd(n,30030) then RETURN(false) fi; if n<289 then RETURN(true) fi; if 1<gcd(n,247110827) then RETURN(false) fi; f:=millerrabin(n,2); if f=false then RETURN(f) fi; f:=millerrabin(n,3); if f=false then RETURN(f) fi; if n<1373653 then RETURN(true) fi; f:=millerrabin(n,5); if f=false then RETURN(f) fi; if n< 5326001 then RETURN(true) fi; f:=millerrabin(n,7); if f=false then RETURN(f) fi; if n<3215031751 then RETURN(true) fi; f:=millerrabin(n,11); if f=false then RETURN(f) fi; if n<2152302898747 then RETURN(true) fi; f:=millerrabin(n,13); if f=false then RETURN(f) fi; if n<3474749660383 then RETURN(true) fi; f:=millerrabin(n,17); if f=false then RETURN(f) fi; if n<341550071728321 then RETURN(true) fi; FAIL end;

Zio2IydJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEc2I0kiZkdGJkYmRiZDPEAkMkYlIiIjLUknUkVUVVJOR0YoNiNJJmZhbHNlR0YoQCQ1NTU1NS9GJUYuL0YlIiIkL0YlIiImL0YlIiIoL0YlIiM2L0YlIiM4LUYwNiNJJXRydWVHRihAJDIiIiItSSRnY2RHRiY2JEYlIiZJKyRGL0AkMkYlIiQqR0ZEQCQyRkktRks2JEYlIipGMzZaI0YvPkYqLUksbWlsbGVycmFiaW5HRiY2JEYlRi5AJC9GKkYyLUYwRik+RiotRlg2JEYlRjtGWkAkMkYlIihgT1AiRkQ+RiotRlg2JEYlRj1GWkAkMkYlIigsZ0smRkQ+RiotRlg2JEYlRj9GWkAkMkYlIitePC46S0ZEPkYqLUZYNiRGJUZBRlpAJDJGJSIuWigpKkdJX0BGRD5GKi1GWDYkRiVGQ0ZaQCQyRiUiLiRRZydcWlokRkQ+RiotRlg2JEYlIiM8RlpAJDJGJSIwQCRHPDJdOk1GREklRkFJTEdGKEYmRiZGJg==

# # This procedure do Lucas' test # for the number n on the naive way # using base a # naivelucastest:=proc(n,a) local m; if igcd(a,n)>1 then RETURN(false) fi; if modp(a&^(n-1),n)<>1 then RETURN(false) fi; for m from 2 to n-2 do if modp(a&^m,n)=1 then RETURN(false) fi od; true end;

Zio2JEkibkc2IkkiYUdGJTYjSSJtR0YlRiVGJUMmQCQyIiIiLUklaWdjZEclKnByb3RlY3RlZEc2JEYmRiQtSSdSRVRVUk5HRi82I0kmZmFsc2VHRi9AJDAtSSVtb2RwR0YvNiQtSSMmXkdGJTYkRiYsJkYkRixGLCEiIkYkRixGMT8oRigiIiNGLCwmRiRGLEZARj5JJXRydWVHRi9AJC8tRjg2JC1GOzYkRiZGKEYkRixGMUZCRiVGJUYl

proth:=proc(h::posint,m::posint) local a,b,n,ad; n:=h*2^m+1; if h>=2^m or not type(h,odd) then return FAIL fi; if m=1 or m=2 then return true fi; # 2 is not a quadratic residue mod n, we start with 3 a:=3; b:=2&^m mod a; b:=h*b+1 mod a; # by quadratic reciprocity, (a|n)=(n|a)=(b|a) if jacobi(b,a)=0 then return false fi; if jacobi(b,a)=-1 then if a&^((n-1)/2) mod n=n-1 then return true else return false fi; fi; # we shall use the quasi-prime sequence 5,7,11,13,17,19,23,25,.. # a random base would give only two trials in mean, # and this looks even better a:=5; ad:=2; while true do b:=2&^m mod a; b:=h*b+1 mod a; if jacobi(b,a)=0 then return false fi; if jacobi(b,a)=-1 then if a&^((n-1)/2) mod n=n-1 then return true else return false fi; fi; a:=a+ad; ad:=6-ad; od; end;

Zio2JCdJImhHNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJtR0YmRic2JkkiYUdGJkkiYkdGJkkibkdGJkkjYWRHRiZGJkYmQy0+Ri4sJiomRiUiIiIpIiIjRipGNEY0RjRGNEAkNTFGNUYlNC1JJXR5cGVHRig2JEYlSSRvZGRHRihPSSVGQUlMR0YoQCQ1L0YqRjQvRipGNk9JJXRydWVHRig+RiwiIiQ+Ri0tSSRtb2RHRiY2JC1JIyZeR0YmNiRGNkYqRiw+Ri0tRks2JCwmKiZGJUY0Ri1GNEY0RjRGNEYsQCQvLV9JKm51bXRoZW9yeUc2JEYoSShfc3lzbGliR0YmSSdqYWNvYmlHRiY2JEYtRiwiIiFPSSZmYWxzZUdGKEAkL0ZXISIiQCUvLUZLNiQtRk42JEYsLCYqJiNGNEY2RjRGLkY0RjRGZm9GXW9GLiwmRi5GNEY0Rl1vRkVGaW4+RiwiIiY+Ri9GNj8oRiZGNEY0RiZGRkMoRklGUEZVRltvPkYsLCZGLEY0Ri9GND5GLywmIiInRjRGL0Zdb0YmRiZGJg==

proth(11,5);

SSV0cnVlRyUqcHJvdGVjdGVkRw==

ifactor(11*2^5+1);

LUkhRzYiNiMiJGAk

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn