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;

Zio2I0kibkc2IjYlSSJpR0YlSSJyR0YlSSJtR0YlRiVGJUMnPkYoIiIiPkYpKiQpRiQiIiNGLD8oRidGMEYsLCZGJEYsRiwhIiJJJXRydWVHJSpwcm90ZWN0ZWRHPkYoLUkkbW9kR0YlNiQqJkYoRixGJ0YsRik+RigtRjg2JCwmRihGLEYsRixGKTckLUklaXJlbUdGNTYkRihGJC1JJWlxdW9HRjVGQkYlRiVGJQ==

# # 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 procedure do Fermat's test for the number n with base a. # If the result is false, the number is composite, if FAIL, # then may be prime. # fermattest:=proc(n::posint,a::posint) if type(n,even) then error "first argument must be odd",n fi; if n<3 then error "first argument is too small",n fi; if n<=a then error "second argument is too large",a fi; if modp(a&^(n-1),n)<>1 then RETURN(false) fi; FAIL end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJhR0YmRidGJkYmRiZDJ0AkLUkldHlwZUdGKDYkRiVJJWV2ZW5HRihZNiRRO2ZpcnN0fmFyZ3VtZW50fm11c3R+YmV+b2RkRiZGJUAkMkYlIiIkWTYkUTxmaXJzdH5hcmd1bWVudH5pc350b29+c21hbGxGJkYlQCQxRiVGKlk2JFE9c2Vjb25kfmFyZ3VtZW50fmlzfnRvb35sYXJnZUYmRipAJDAtSSVtb2RwR0YoNiQtSSMmXkdGJjYkRiosJkYlIiIiRkghIiJGJUZILUknUkVUVVJOR0YoNiNJJmZhbHNlR0YoSSVGQUlMR0YoRiZGJkYm

n:=(2^28-9)/7; fermattest(n,3); fermattest(n,2);

IilAek1R

SSVGQUlMRyUqcHJvdGVjdGVkRw==

SSZmYWxzZUclKnByb3RlY3RlZEc=

# # This procedure look for pseudoprimes until a given limit n # in bases in the list L. # pseudoprime:=proc(n::posint,L::list(posint)) local pp,i,a,t; pp:=[]; for i from max(3,op(L))+1 to n do if type(i,even) then next fi; for a in L do t:=fermattest(i,a); if not t then break fi od; if t=FAIL then if not isprime(i) then pp:=[op(pp),i] fi fi od; pp end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJMR0YmLUklbGlzdEdGKDYjRic2JkkjcHBHRiZJImlHRiZJImFHRiZJInRHRiZGJkYmQyU+Ri83Ij8oRjAsJi1JJG1heEdGKDYkIiIkLUkjb3BHRig2I0YqIiIiRj9GP0Y/RiVJJXRydWVHRihDJUAkLUkldHlwZUdGKDYkRjBJJWV2ZW5HRihcPyZGMUYqRkBDJD5GMi1JK2Zlcm1hdHRlc3RHRiY2JEYwRjFAJDRGMltAJC9GMkklRkFJTEdGKEAkNC1JKGlzcHJpbWVHNiRGKEkoX3N5c2xpYkdGJjYjRjA+Ri83JC1GPTYjRi9GMEYvRiZGJkYm

pseudoprime(10000,[2]);

NzgiJFQkIiRoJiIkWCciJTA2IiUoUSIiJUg8IiUwPiIlWj8iJWxDIiUsRiIlQEciJXhLIiVMUyIlcFYiJXJWIiUibyUiJWhhIiUsbSIlZHoiJUAkKSIlIlspIiU2Kik=

# # This procedure look for Carmichael # numbers until a given limit n. # carmichael:=proc(n) local L,i,a,t; L:=[]; for i from 2 to n do if type(i,even) then next fi; if isprime(i) then next fi; for a from 2 to i-1 do if igcd(i,a)=1 then t:=fermattest(i,a); if not t then break fi fi od; if t=FAIL then L:=[op(L),i] fi od; L end;

Zio2I0kibkc2IjYmSSJMR0YlSSJpR0YlSSJhR0YlSSJ0R0YlRiVGJUMlPkYnNyI/KEYoIiIjIiIiRiRJJXRydWVHJSpwcm90ZWN0ZWRHQyZAJC1JJXR5cGVHRjI2JEYoSSVldmVuR0YyXEAkLUkoaXNwcmltZUc2JEYySShfc3lzbGliR0YlNiNGKEY5PyhGKUYvRjAsJkYoRjBGMCEiIkYxQCQvLUklaWdjZEdGMjYkRihGKUYwQyQ+RiotSStmZXJtYXR0ZXN0R0YlRkdAJDRGKltAJC9GKkklRkFJTEdGMj5GJzckLUkjb3BHRjI2I0YnRihGJ0YlRiVGJQ==

carmichael(10000);

NykiJGgmIiUwNiIlSDwiJWxDIiVARyIlLG0iJTYqKQ==

# # Much larger speed can be obtained using that a number n is # Carmichael number if and only if it is squre free, has at least # three prime factors and p-1 divides n-1 for every prime factor # p of n. #

# # 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

# # What is this? # jacobiproba:=proc(a,b,p,n) local i,j,L; for i from 0 to n-1 do L:=[]; for j from 0 to p-1 do L:=[op(L),jacobi(a,b+(i*p+j)*a)]; od; print(L); od; end;

Zio2JkkiYUc2IkkiYkdGJUkicEdGJUkibkdGJTYlSSJpR0YlSSJqR0YlSSJMR0YlRiVGJT8oRioiIiEiIiIsJkYoRi9GLyEiIkkldHJ1ZUclKnByb3RlY3RlZEdDJT5GLDciPyhGK0YuRi8sJkYnRi9GL0YxRjI+Riw3JC1JI29wR0YzNiNGLC1fSSpudW10aGVvcnlHNiRGM0koX3N5c2xpYkdGJUknamFjb2JpR0YlNiRGJCwmRiZGLyomLCYqJkYqRi9GJ0YvRi9GK0YvRi9GJEYvRi8tSSZwcmludEdGM0Y9RiVGJUYl

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

# # This procedure do the Soloway-Strassen probabilistic test. # The first parameter is the integer to test, the second # the number of rounds. if the result is false, the number # is composite, if FAIL, then probably prime. # solowaystrassen:=proc(n::posint,m::posint) local i,b,rnd; if type(n,even) then error "first argument must be odd",n fi; if n<5 then error "first argument is too small",n fi; rnd:=rand(2..n-2); for i to m do b:=rnd(); if igcd(b,n)>1 then RETURN(false) fi; if modp(b&^((n-1)/2),n)<>modp(jacobi(b,n),n) then RETURN(false) fi od; FAIL end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJtR0YmRic2JUkiaUdGJkkiYkdGJkkkcm5kR0YmRiZGJkMnQCQtSSV0eXBlR0YoNiRGJUklZXZlbkdGKFk2JFE7Zmlyc3R+YXJndW1lbnR+bXVzdH5iZX5vZGRGJkYlQCQyRiUiIiZZNiRRPGZpcnN0fmFyZ3VtZW50fmlzfnRvb35zbWFsbEYmRiU+Ri4tSSVyYW5kR0YmNiM7IiIjLCZGJSIiIkZDISIiPyhGLEZFRkVGKkkldHJ1ZUdGKEMlPkYtLUYuRiZAJDJGRS1JJWlnY2RHRig2JEYtRiUtSSdSRVRVUk5HRig2I0kmZmFsc2VHRihAJDAtSSVtb2RwR0YoNiQtSSMmXkdGJjYkRi0sJiomI0ZFRkNGRUYlRkVGRUZpbkZGRiUtRlg2JC1fSSpudW10aGVvcnlHNiRGKEkoX3N5c2xpYkdGJkknamFjb2JpR0YmRlBGJUZRSSVGQUlMR0YoRiZGJkYm

debug(solowaystrassen); solowaystrassen(5,2);

STBzb2xvd2F5c3RyYXNzZW5HNiI=

{--> enter solowaystrassen, args = 5, 2

Zio2IkYjRiNGIywmLWYqRiNGIzYjSShidWlsdGluR0YjRiMiJCRSRiNGI0YjSSVGQUlMRyUqcHJvdGVjdGVkRzYlIiInIiIjIiIiRi9GLkYvRiNGI0Yj

IiIj

IiIj

SSVGQUlMRyUqcHJvdGVjdGVkRw==

<-- exit solowaystrassen (now at top level) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

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 Miller's deterministic test # based on GRH. The parameter is the integer to test. # millertest:=proc(n::posint) local i,b,t; if n=1 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 type(n,even) then RETURN(false) fi; if n=9 then RETURN(false) fi; b:=floor(2.0002*ln(n)^2); for i from 2 to b do if not millerrabin(n,i) then RETURN(false) fi; od; true end;

Zio2IydJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEc2JUkiaUdGJkkiYkdGJkkidEdGJkYmRiZDKUAkL0YlIiIiLUknUkVUVVJOR0YoNiNJJmZhbHNlR0YoQCQ1NTU1NS9GJSIiIy9GJSIiJC9GJSIiJi9GJSIiKC9GJSIjNi9GJSIjOC1GMjYjSSV0cnVlR0YoQCQtSSV0eXBlR0YoNiRGJUklZXZlbkdGKEYxQCQvRiUiIipGMT5GKy1JJmZsb29yRzYkRihJKF9zeXNsaWJHRiY2IyomJCImLSsjISIlRjAqJCktSSNsbkdGVTYjRiVGPEYwRjA/KEYqRjxGMEYrRklAJDQtSSxtaWxsZXJyYWJpbkdGJjYkRiVGKkYxRklGJkYmRiY=

millertest(17);

SSV0cnVlRyUqcHJvdGVjdGVkRw==

# # 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

# # This procedure do Lucas' test # for the number n using the set S of # factors of n-1 and base a # lucastest:=proc(n,a,S) local p; if n<=a then ERROR(`second parameter is too large`,a) fi; if igcd(a,n)>1 then RETURN(false) fi; if modp(a&^(n-1),n)<>1 then RETURN(false) fi; for p in S do if modp(a&^((n-1)/p),n)=1 then RETURN(FAIL) fi od; true end;

Zio2JUkibkc2IkkiYUdGJUkiU0dGJTYjSSJwR0YlRiVGJUMnQCQxRiRGJi1JJkVSUk9SRyUqcHJvdGVjdGVkRzYkST5zZWNvbmR+cGFyYW1ldGVyfmlzfnRvb35sYXJnZUdGJUYmQCQyIiIiLUklaWdjZEdGLzYkRiZGJC1JJ1JFVFVSTkdGLzYjSSZmYWxzZUdGL0AkMC1JJW1vZHBHRi82JC1JIyZeR0YlNiRGJiwmRiRGNEY0ISIiRiRGNEY4PyZGKUYnSSV0cnVlR0YvQCQvLUY/NiQtRkI2JEYmKiZGREY0RilGRUYkRjQtRjk2I0klRkFJTEdGL0ZHRiVGJUYl

# # This procedure do Lucas' test # for numbers n*k^m+1 with small # n,k,m and base a. # speclucas:=proc(n,k,m,a) local S,N,p; S:=factorset(n); if m>0 then S:=S union factorset(k) fi; N:=n*k^m+1; if N<=a then ERROR(`last parameter is too large`,a) fi; if igcd(a,N)>1 then RETURN(false) fi; if modp(a&^(N-1),N)<>1 then RETURN(false) fi; for p in S do if modp(a&^((N-1)/p),N)=1 then RETURN(FAIL) fi od; true end;

Zio2Jkkibkc2Ikkia0dGJUkibUdGJUkiYUdGJTYlSSJTR0YlSSJOR0YlSSJwR0YlRiVGJUMqPkYqLV9JKm51bXRoZW9yeUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJUkqZmFjdG9yc2V0R0YlNiNGJEAkMiIiIUYnPkYqLUkmdW5pb25HRjM2JEYqLUYwNiNGJj5GKywmKiZGJCIiIilGJkYnRkNGQ0ZDRkNAJDFGK0YoLUkmRVJST1JHRjM2JEk8bGFzdH5wYXJhbWV0ZXJ+aXN+dG9vfmxhcmdlR0YlRihAJDJGQy1JJWlnY2RHRjM2JEYoRistSSdSRVRVUk5HRjM2I0kmZmFsc2VHRjNAJDAtSSVtb2RwR0YzNiQtSSMmXkdGJTYkRigsJkYrRkNGQyEiIkYrRkNGUD8mRixGKkkldHJ1ZUdGM0AkLy1GVzYkLUZaNiRGKComRmZuRkNGLEZnbkYrRkMtRlE2I0klRkFJTEdGM0ZpbkYlRiVGJQ==

# # This procedure try to find a large prime using Lucas' test. # The search goes for n,n+1,n+2,... between numbers n*k^m+1. # largewithlucas:=proc(n::posint,k::posint,m::posint) local i,a,aa,f; if k<2 then ERROR(`second parameter is too small`,k) fi; for i from n do f:=FAIL; for a from 2 while f=FAIL do f:=speclucas(i,k,m,a); aa:=a; od; print(i*k^m+1,aa,f); od; end;

Zio2JSdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJrR0YmRicnSSJtR0YmRic2JkkiaUdGJkkiYUdGJkkjYWFHRiZJImZHRiZGJkYmQyRAJDJGKiIiIy1JJkVSUk9SR0YoNiRJPnNlY29uZH5wYXJhbWV0ZXJ+aXN+dG9vfnNtYWxsR0YmRio/KEYuRiUiIiJGJkkldHJ1ZUdGKEMlPkYxSSVGQUlMR0YoPyhGL0Y1RjtGJi9GMUY/QyQ+RjEtSSpzcGVjbHVjYXNHRiY2JkYuRipGLEYvPkYwRi8tSSZwcmludEdGKDYlLCYqJkYuRjspRipGLEY7RjtGO0Y7RjBGMUYmRiZGJg==

debug(largewithlucas); debug(speclucas); largewithlucas(1,2,16);

SS9sYXJnZXdpdGhsdWNhc0c2Ig==

SSpzcGVjbHVjYXNHNiI=

{--> enter largewithlucas, args = 1, 2, 16

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 1, 2, 16, 2

PCI=

PCMiIiM=

IiZQYic=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIj

{--> enter speclucas, args = 1, 2, 16, 3

PCI=

PCMiIiM=

IiZQYic=

IiIj

SSV0cnVlRyUqcHJvdGVjdGVkRw==

<-- exit speclucas (now in largewithlucas) = true}

SSV0cnVlRyUqcHJvdGVjdGVkRw==

IiIk

NiUiJlBiJyIiJEkldHJ1ZUclKnByb3RlY3RlZEc=

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 2, 2, 16, 2

PCMiIiM=

PCMiIiM=

Iid0NTg=

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ3Q1OCIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 3, 2, 16, 2

PCMiIiQ=

PCQiIiMiIiQ=

Iic0bT4=

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJzRtPiIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 4, 2, 16, 2

PCMiIiM=

PCMiIiM=

IidYQEU=

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ1hARSIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 5, 2, 16, 2

PCMiIiY=

PCQiIiMiIiY=

Iicib0Yk

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJyJvRiQiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 6, 2, 16, 2

PCQiIiMiIiQ=

PCQiIiMiIiQ=

Iic8S1I=

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJzxLUiIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 7, 2, 16, 2

PCMiIig=

PCQiIiMiIig=

IidgKGUl

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ2AoZSUiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 8, 2, 16, 2

PCMiIiM=

PCMiIiM=

IicqR0Mm

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJypHQyYiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 9, 2, 16, 2

PCMiIiQ=

PCQiIiMiIiQ=

IidEKSpl

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ0QpKmUiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 10, 2, 16, 2

PCQiIiMiIiY=

PCQiIiMiIiY=

IidoYGw=

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ2hgbCIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 11, 2, 16, 2

PCMiIzY=

PCQiIiMiIzY=

IicoKjNz

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJygqM3MiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 12, 2, 16, 2

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIj

{--> enter speclucas, args = 12, 2, 16, 3

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIk

{--> enter speclucas, args = 12, 2, 16, 4

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIl

{--> enter speclucas, args = 12, 2, 16, 5

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

IiIk

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIm

{--> enter speclucas, args = 12, 2, 16, 6

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIn

{--> enter speclucas, args = 12, 2, 16, 7

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIo

{--> enter speclucas, args = 12, 2, 16, 8

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIp

{--> enter speclucas, args = 12, 2, 16, 9

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

<-- exit speclucas (now in largewithlucas) = FAIL}

SSVGQUlMRyUqcHJvdGVjdGVkRw==

IiIq

{--> enter speclucas, args = 12, 2, 16, 10

PCQiIiMiIiQ=

PCQiIiMiIiQ=

IidMa3k=

IiIj

IiIk

SSV0cnVlRyUqcHJvdGVjdGVkRw==

<-- exit speclucas (now in largewithlucas) = true}

SSV0cnVlRyUqcHJvdGVjdGVkRw==

IiM1

NiUiJ0xreSIjNUkldHJ1ZUclKnByb3RlY3RlZEc=

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 13, 2, 16, 2

PCMiIzg=

PCQiIiMiIzg=

IidwPiYp

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ3A+JikiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 14, 2, 16, 2

PCQiIiMiIig=

PCQiIiMiIig=

IicwdiIq

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJzB2IioiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 15, 2, 16, 2

PCQiIiQiIiY=

PCUiIiMiIiQiIiY=

IidUSSkq

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ1RJKSoiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 16, 2, 16, 2

PCMiIiM=

PCMiIiM=

Iih4Jls1

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKHgmWzUiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 17, 2, 16, 2

PCMiIzw=

PCQiIiMiIzw=

Iig4VDYi

<-- exit speclucas (now in largewithlucas) = false}

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKDhUNiIiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

SSVGQUlMRyUqcHJvdGVjdGVkRw==

{--> enter speclucas, args = 18, 2, 16, 2

PCQiIiMiIiQ=

<-- ERROR in speclucas (now in largewithlucas) = interrupted} <-- ERROR in largewithlucas (now at top level) = interrupted} Warning, computation interrupted

# # This procedure do the Pepin test # for the Fermat number 2^(2^m)+1. # pepin:=proc(m::nonnegint) local N; if m=0 then RETURN(true) fi; N:=2^(2^m)+1; if modp(3&^((N-1)/2),N)=N-1 then RETURN(true) fi; false end;

Zio2IydJIm1HNiJJKm5vbm5lZ2ludEclKnByb3RlY3RlZEc2I0kiTkdGJkYmRiZDJkAkL0YlIiIhLUknUkVUVVJOR0YoNiNJJXRydWVHRig+RiosJikiIiMpRjZGJSIiIkY4RjhAJC8tSSVtb2RwR0YoNiQtSSMmXkdGJjYkIiIkLCYqJiNGOEY2RjhGKkY4RjhGRCEiIkYqLCZGKkY4RjhGRUYvSSZmYWxzZUdGKEYmRiZGJg==

pepin(4); pepin(5);

SSV0cnVlRyUqcHJvdGVjdGVkRw==

SSZmYWxzZUclKnByb3RlY3RlZEc=

# # This procedure do the Lehmer-Pocklington test # for the number n using the subset S of factors of # n-1 and base a. Returns with the reduced set S. # LPtest:=proc(n,S,a) local p,newS; if n<=a then ERROR(`last parameter is too large`,a) fi; if igcd(a,n)>1 then RETURN(false) fi; if modp(a&^(n-1),n)<>1 then RETURN(false) fi; newS:=S; for p in S do if igcd(modp(a&^((n-1)/p),n)-1,n)=1 then newS:=newS minus {p} fi od; newS; end;

Zio2JUkibkc2IkkiU0dGJUkiYUdGJTYkSSJwR0YlSSVuZXdTR0YlRiVGJUMoQCQxRiRGJy1JJkVSUk9SRyUqcHJvdGVjdGVkRzYkSTxsYXN0fnBhcmFtZXRlcn5pc350b29+bGFyZ2VHRiVGJ0AkMiIiIi1JJWlnY2RHRjA2JEYnRiQtSSdSRVRVUk5HRjA2I0kmZmFsc2VHRjBAJDAtSSVtb2RwR0YwNiQtSSMmXkdGJTYkRicsJkYkRjVGNSEiIkYkRjVGOT5GKkYmPyZGKUYmSSV0cnVlR0YwQCQvLUY3NiQsJi1GQDYkLUZDNiRGJyomRkVGNUYpRkZGJEY1RjVGRkYkRjU+RiotSSZtaW51c0dGMDYkRio8I0YpRipGJUYlRiU=

# # This procedure try to find a large prime using # Lehmer-Pocklington test. The search goes for n,n+1,... between # numbers n*k^m+1. # largewithLP:=proc(n,k,m) local i,a,aa,S,S0; if k<2 then ERROR(`second parameter is too small`,k) fi; S0:=factorset(k); for i from n do if n<=k^m then S:=S0 else S:=S0 union factorset(i) fi; for a from 2 while S<>{} and S<>false do S:=LPtest(i*k^m+1,S,a); aa:=a; od; if S=false then print(i*k^m+1,aa,false) else print(i*k^m+1,aa,true) fi od; end;

Zio2JUkibkc2Ikkia0dGJUkibUdGJTYnSSJpR0YlSSJhR0YlSSNhYUdGJUkiU0dGJUkjUzBHRiVGJUYlQyVAJDJGJiIiIy1JJkVSUk9SRyUqcHJvdGVjdGVkRzYkST5zZWNvbmR+cGFyYW1ldGVyfmlzfnRvb35zbWFsbEdGJUYmPkYtLV9JKm51bXRoZW9yeUc2JEY0SShfc3lzbGliR0YlSSpmYWN0b3JzZXRHRiU2I0YmPyhGKUYkIiIiRiVJJXRydWVHRjRDJUAlMUYkKUYmRic+RixGLT5GLC1JJnVuaW9uR0Y0NiRGLS1GOTYjRik/KEYqRjFGQEYlMzBGLDwiMEYsSSZmYWxzZUdGNEMkPkYsLUknTFB0ZXN0R0YlNiUsJiomRilGQEZFRkBGQEZARkBGLEYqPkYrRipAJS9GLEZSLUkmcHJpbnRHRjQ2JUZYRitGUi1GaG42JUZYRitGQUYlRiVGJQ==

debug(largewithLP); largewithLP(1,2,16);

SSxsYXJnZXdpdGhMUEc2Ig==

{--> enter largewithLP, args = 1, 2, 16

PCMiIiM=

PCMiIiM=

PCMiIiM=

IiIj

PCI=

IiIk

NiUiJlBiJyIiJEkldHJ1ZUclKnByb3RlY3RlZEc=

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ3Q1OCIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJzRtPiIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ1hARSIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJyJvRiQiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJzxLUiIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ2AoZSUiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJypHQyYiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ0QpKmUiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ2hgbCIiI0kmZmFsc2VHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJygqM3MiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

PCMiIiM=

IiIj

PCMiIiM=

IiIk

PCMiIiM=

IiIl

PCI=

IiIm

NiUiJ0xreSIiJkkldHJ1ZUclKnByb3RlY3RlZEc=

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ3A+JikiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJzB2IioiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiJ1RJKSoiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKHgmWzUiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKDhUNiIiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

PCMiIiM=

IiIj

PCMiIiM=

IiIk

PCMiIiM=

IiIl

PCMiIiM=

IiIm

PCMiIiM=

IiIn

PCMiIiM=

IiIo

PCMiIiM=

IiIp

PCMiIiM=

IiIq

PCMiIiM=

IiM1

PCMiIiM=

IiM2

PCMiIiM=

IiM3

PCMiIiM=

IiM4

PCMiIiM=

IiM5

PCMiIiM=

IiM6

PCMiIiM=

IiM7

PCMiIiM=

IiM8

PCMiIiM=

IiM9

PCI=

IiM+

NiUiKFwnejYiIz5JJXRydWVHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKCY9WDciIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKEAySiIiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

PCMiIiM=

IiIj

PCMiIiM=

IiIk

PCMiIiM=

IiIl

PCI=

IiIm

NiUiKGRpUCIiIiZJJXRydWVHJSpwcm90ZWN0ZWRH

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKCR6VDkiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKEh0XSIiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKGxHZCIiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKCwlUTsiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

SSZmYWxzZUclKnByb3RlY3RlZEc=

IiIj

NiUiKFBScSIiIiNJJmZhbHNlRyUqcHJvdGVjdGVkRw==

PCMiIiM=

PCMiIiM=

IiIj

PCMiIiM=

IiIk

PCMiIiM=

<-- ERROR in largewithLP (now at top level) = interrupted} Warning, computation interrupted

# # This procedure try to find factors of n having the form # a*k+b from k=1 until K or the square root of n. # Note that LPtest capable to prove that factors n have # the form f*k+1, where f is the factorised part of n-1, # and a test treated later capable to prove that # factors have the form f*k+1 or f*k-1, where f is the # factorised part of n+1. # tryfactors:=proc(a::posint,b::integer,n::posint,K::posint) local nn,i,f; if a=1 then error "first parameter is too small",a fi; if b<=1-a then error "second parameter is too small",b fi; f:=[]; nn:=n; for i to K while (i*a+b)^2<=nn do if modp(nn,i*a+b)=0 then f:=[op(f),i*a+b]; nn:=nn/(i*a+b); i:=i-1; fi; od; f end;

Zio2JidJImFHNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJiR0YmSShpbnRlZ2VyR0YoJ0kibkdGJkYnJ0kiS0dGJkYnNiVJI25uR0YmSSJpR0YmSSJmR0YmRiZGJkMoQCQvRiUiIiJZNiRRPWZpcnN0fnBhcmFtZXRlcn5pc350b29+c21hbGxGJkYlQCQxRiosJkY3RjdGJSEiIlk2JFE+c2Vjb25kfnBhcmFtZXRlcn5pc350b29+c21hbGxGJkYqPkYzNyI+RjFGLT8oRjJGN0Y3Ri8xKiQpLCYqJkYlRjdGMkY3RjdGKkY3IiIjRjdGMUAkLy1JJW1vZHBHRig2JEYxRkkiIiFDJT5GMzckLUkjb3BHRig2I0YzRkk+RjEqJkYxRjdGSUY+PkYyLCZGMkY3RjdGPkYzRiZGJkYm

# # This procedure do the Proth test for the number n=h*2^m+1. # proth:=proc(h::posint,m::posint) local a,b,n; n:=h*2^m+1; if h>=2^m then error "first parmeter is too large",h fi; if not type(h,odd) then error "first parameter must be odd",h fi; if m=1 or m=2 then return true fi; if m=3 then if h=5 then return true else return false fi fi; # 2 is not a quadratic residue mod n, we start with 3 # (2*a|n)=(a|n), hence enough to try odd bases a for a from 3 by 2 do b:=2&^m mod a; b:=h*b+1 mod a; # by quadratic reciprocity, (a|n)=(n|a)=(b|a) b:=modp(2&^m,a); b:=modp(h*b+1,a); if jacobi(b,a)=0 then return false fi; if jacobi(b,a)=-1 then if modp(a&^((n-1)/2),n)=n-1 then return true else return false fi; fi; od end;

Zio2JCdJImhHNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJtR0YmRic2JUkiYUdGJkkiYkdGJkkibkdGJkYmRiZDKD5GLiwmKiZGJSIiIikiIiNGKkYzRjNGM0YzQCQxRjRGJVk2JFE8Zmlyc3R+cGFybWV0ZXJ+aXN+dG9vfmxhcmdlRiZGJUAkNC1JJXR5cGVHRig2JEYlSSRvZGRHRihZNiRRPGZpcnN0fnBhcmFtZXRlcn5tdXN0fmJlfm9kZEYmRiVAJDUvRipGMy9GKkY1T0kldHJ1ZUdGKEAkL0YqIiIkQCUvRiUiIiZGSE9JJmZhbHNlR0YoPyhGLEZMRjVGJkZJQyg+Ri0tSSRtb2RHRiY2JC1JIyZeR0YmNiRGNUYqRiw+Ri0tRlY2JCwmKiZGJUYzRi1GM0YzRjNGM0YsPkYtLUklbW9kcEdGKEZXPkYtLUZcb0ZnbkAkLy1fSSpudW10aGVvcnlHNiRGKEkoX3N5c2xpYkdGJkknamFjb2JpR0YmNiRGLUYsIiIhRlBAJC9GYW8hIiJAJS8tRlxvNiQtRlk2JEYsLCYqJiNGM0Y1RjNGLkYzRjNGZHBGW3BGLiwmRi5GM0YzRltwRkhGUEYmRiZGJg==

proth(11,5);

SSV0cnVlRyUqcHJvdGVjdGVkRw==

ifactor(11*2^5+1);

LUkhRzYiNiMiJGAk

# # This test may be used if n-1=FR, where the factors # of F are known, and there is given a bound B such that # R has no primedivisor less then B, and FB>sqrt(N). First # we have to use the Lehmer - Pocklington test with # the set of divisors of F. After this the second step is # to find an appropriate base a to R. # PLtestsecondstep:=proc(n,F,a) local p,newS; if n<=a then ERROR(`last parameter is too large`,a) fi; if igcd(a,n)>1 then RETURN(false) fi; if modp(a&^(n-1),n)<>1 then RETURN(false) fi; if igcd(modp(a&^F-1,n),n)=1 then RETURN(true) fi; FAIL end;

Zio2JUkibkc2IkkiRkdGJUkiYUdGJTYkSSJwR0YlSSVuZXdTR0YlRiVGJUMnQCQxRiRGJy1JJkVSUk9SRyUqcHJvdGVjdGVkRzYkSTxsYXN0fnBhcmFtZXRlcn5pc350b29+bGFyZ2VHRiVGJ0AkMiIiIi1JJWlnY2RHRjA2JEYnRiQtSSdSRVRVUk5HRjA2I0kmZmFsc2VHRjBAJDAtSSVtb2RwR0YwNiQtSSMmXkdGJTYkRicsJkYkRjVGNSEiIkYkRjVGOUAkLy1GNzYkLUZANiQsJi1GQzYkRidGJkY1RjVGRkYkRiRGNS1GOjYjSSV0cnVlR0YwSSVGQUlMR0YwRiVGJUYl

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn