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;

# # This is a simple factorization # procedure using trial division. # The result is a sequence of pairs # [p,e] where the p's are the prime # factors and the e's are the exponents. # The factors are anyway in increasing order. # Only primes <= P are tried, hence the # last "factor" may composite, if # it is greater then P^2; # trialdiv:=proc(n::posint,P::posint) local L,p,i,d,nn; L:=[]; nn:=n; if type(nn,even) and 2<=P then for i from 0 while type(nn,even) do nn:=nn/2; od; L:=[[2,i]]; fi; if nn mod 3=0 and 3<=P then for i from 0 while nn mod 3=0 do nn:=nn/3; od; L:=[op(L),[3,i]]; fi; d:=2; p:=5; while p<=P and nn>=p^2 do if nn mod p=0 then for i from 0 while nn mod p=0 do nn:=nn/p; od; L:=[op(L),[p,i]]; fi; p:=p+d; d:=6-d; od; if nn>1 then L:=[op(L),[nn,1]] fi; L; end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJQR0YmRic2J0kiTEdGJkkicEdGJkkiaUdGJkkiZEdGJkkjbm5HRiZGJkYmQys+Riw3Ij5GMEYlQCQzLUkldHlwZUdGKDYkRjBJJWV2ZW5HRigxIiIjRipDJD8oRi4iIiEiIiJGJkY3PkYwLCQqJiNGQEY8RkBGMEZARkA+Riw3IzckRjxGLkAkMy8tSSRtb2RHRiY2JEYwIiIkRj8xRk5GKkMkPyhGLkY/RkBGJkZKPkYwLCQqJiNGQEZORkBGMEZARkA+Riw3JC1JI29wR0YoNiNGLDckRk5GLj5GL0Y8PkYtIiImPyhGJkZARkBGJjMxRi1GKjEqJClGLUY8RkBGMEMlQCQvLUZMNiRGMEYtRj9DJD8oRi5GP0ZARiZGYW8+RjAqJkYwRkBGLSEiIj5GLDckRlg3JEYtRi4+Ri0sJkYtRkBGL0ZAPkYvLCYiIidGQEYvRmhvQCQyRkBGMD5GLDckRlg3JEYwRkBGLEYmRiZGJg==

trialdiv(2^32+1,1000);

NyQ3JCIkVCciIiI3JCIoPC9xJ0Yl

# # This is a simple primality testing # procedure using trial division. # The result is true if n is prime, else false. # trialprime:=proc(n::posint) local L,p,i,d,nn; if n=1 then RETURN(false) fi; if n=2 or n=3 or n=5 then RETURN(true) fi; if type(n,even) then RETURN(false) fi; if n mod 3=0 then RETURN(false) fi; d:=2; p:=5; while n>=p^2 do if n mod p=0 then RETURN(false) fi; p:=p+d; d:=6-d; od; true; end;

Zio2IydJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEc2J0kiTEdGJkkicEdGJkkiaUdGJkkiZEdGJkkjbm5HRiZGJkYmQypAJC9GJSIiIi1JJ1JFVFVSTkdGKDYjSSZmYWxzZUdGKEAkNTUvRiUiIiMvRiUiIiQvRiUiIiYtRjQ2I0kldHJ1ZUdGKEAkLUkldHlwZUdGKDYkRiVJJWV2ZW5HRihGM0AkLy1JJG1vZEdGJjYkRiVGPSIiIUYzPkYtRjs+RitGPz8oRiZGMkYyRiYxKiQpRitGO0YyRiVDJUAkLy1GSzYkRiVGK0ZNRjM+RissJkYrRjJGLUYyPkYtLCYiIidGMkYtISIiRkJGJkYmRiY=

trialprime(2^32+1);

SSZmYWxzZUclKnByb3RlY3RlZEc=

interface(verboseproc=2);

IiIi

print(ifactor);

Zio2I0kibkc2IjYlSSRzb2xHRiVJInJHRiVJI3QxR0YlNiVJKXJlbWVtYmVyR0YlSSdzeXN0ZW1HJSpwcm90ZWN0ZWRHSWFvQ29weXJpZ2h0fihjKX4xOTkxfmJ5fnRoZX5Vbml2ZXJzaXR5fm9mfldhdGVybG9vLn5BbGx+cmlnaHRzfnJlc2VydmVkLkdGJUVccyoiLWckSCo0eCkqKjQpLUkhR0YlNiMiIiMiIiUiIiItRjQ2IyIiJEY4LUY0NiMiIiZGOC1GNDYjIiIoRjgtRjQ2IyIjNkY4LUY0NiMiIzxGOC1GNDYjIiNaRjgtRjQ2IyIkXiJGOC1GNDYjIiRWJUY4Ii0rd0s5eCkqKjRGMkY4KUY5RjZGOClGPEY2RjhGP0Y4RkJGOC1GNDYjIiM4RjhGRUY4LUY0NiMiI0JGOC1GNDYjIiQsKEY4IjIhR3lsOy1dJSo9KjgpRjNGO0Y4RlNGOEY8RjhGVUY4LUY0NiMiI1RGOC1GNDYjIiNmRjgtRjQ2IyIjaEY4LUY0NiMiI25GOC1GNDYjIiNyRjgtRjQ2IyIjdEY4LUY0NiMiI3pGOCIuXzcvLU4/IioyKUYzRjZGOClGOUY3RjgpRj9GNkY4LUY0NiMiI0hGOC1GNDYjIiNKRjgtRjQ2IyIjUEY4LUY0NiMiI1ZGOC1GNDYjIiNgRjgiLWVMd3QheioqKEYzRjgtRjQ2IyInKClIJSlGOC1GNDYjIic8MmVGOCItMyFvVTstKiomRmpuRjgtRjQ2IyItLE5gcUY2RjgiLVMnM2VyKCkqKjApRjNGQUY4RlNGOEY8RjhGQkY4KUZFRjtGOC1GNDYjIiM+RjgtRjQ2IyIkbiJGOCItU0VtQngpKio0RjJGOEY5RjhGPEY4RkJGOEZVRjhGRUY4RltvRjgtRjQ2IyIkZCJGOC1GNDYjIiRqI0Y4Ii0rKzt1dykqKjBGY3JGOEY5RjgpRjxGN0Y4RkJGOEZFRjhGXm9GOC1GNDYjIiR0JEY4QypAJjIlJm5hcmdzR0Y4WVEyYXJndW1lbnR+cmVxdWlyZWRGJTMyRjhGXHQ0LUkldHlwZUdGLTYkJiUlYXJnc0dGNS5JJW5hbWVHRi1ZUT9zZWNvbmR+YXJndW1lbnR+bXVzdH5iZX5hfm5hbWVGJUAtLUZjdDYkRiQuSShpbnRlZ2VyR0YtQCcyIiIhRiRDJD5GJ0Y4PkYoRiQyRiRGYnVDJD5GJyEiIj5GKCwkRiRGaXVPRmJ1LUZjdDYkRiQuSSlmcmFjdGlvbkdGLU8qJi0lKXByb2NuYW1lRzYkLUkjb3BHRi02JEY4RiQmRmZ0NiM7RjZGaXVGOC1GZHY2JC1GZ3Y2JEY2RiRGaXZGaXUtRmN0NiRGJDwmLkkiKkdGLS5JJWxpc3RHRi0uSSRzZXRHRi0uSSlyZWxhdGlvbkdGLU8tSSRtYXBHRi02JUZkdkYkRml2My1GY3Q2JEYkSSJeR0YtLUZjdDYkRl53Rl51TylGY3ZGXnctRmN0NiRGJC1GNDYjRl51T0ZjdllRMmludmFsaWR+YXJndW1lbnRzRiVAJC1JKWFzc2lnbmVkR0YtNiMmSTdpZmFjdG9yL2Zyb21fc2lnbmF0dXJlR0YlNiNGKE9GYnk+RiktSSVpZ2NkR0YtNiRGKCInPzJzPyhGJUY4RjhGJTBGKUY4QyU+RicqJkYnRjgtSTFpZmFjdG9yL2lmYWN0MjM1R0YlNiNGKUY4PkYoLUklaXF1b0dGLTYkRihGKT5GKS1GaHk2JEYpRig+RiktRmh5NiRGKCJpZ21MIzQoKkddS0tUXy8mbzotNi1cVUxuTzYzSy8vYTIrSmcxKHl2JSkpPSU+NzgiPl89KVJCUSM+Vld5dydHKlIlR1w/JGY3IWVAWnpJKCp5eWU1NmMieSkqKm8qKVFMaHF3LT89KHp1VCVlPDYpZlpAUSpbMikzIz53ZCcqXDpHKCopej1dXlZWLmg5TWt1ZUwoeiFbJCkqKkhxMXhfdycpUmQjUWVWdmElPlZKIikpZXo+ISpIZSVceFBEUm1mLTYwJjNPbFdhXXJIeih6WCRbVnFGQDdIcyxBIXpBbnI2Jz5DJVwkZnc+cixjRyIzMSs3c0FkUUBBKHpDPlh6TmwoKjQpXDBhRmNAKiopeTt1MihSJilIXC4uKkg3InlWLVZvRVo+SUF6USVIMz4jPSV5JSkpKlE/Pmw/JylmIXBxMVZrcGooNFI9Y1Z4USwnbzFhSyxucFhCUixXW3RVQSlIJzQtRmhVUFgzeSYqMyg+YicpR0hXc2lWW18ucHQ1PWJxeWkhPVRSYlVjIz1AVyxQOV5IYTsiPyhGJUY4RjhGJUZcekMlPkYnKiZGJ0Y4LUkxaWZhY3Rvci9pZmFjdDFzdEdGJUZiekY4RmN6Rmd6QCUwRihGOEMkQCUvRlx0RjhAJTMvSTJfRW52X2lmYWN0b3JfZWFzeUdGJUkldHJ1ZUdGLTIiI0ktSSdsZW5ndGhHRi1GZHlDJD5JL2lmYWN0b3IvYm90dG9tR0YlSS1pZmFjdG9yL2Vhc3lHRiU+RiktSTFpZmFjdG9yL2lmYWN0MHRoR0YlRmR5QyQ+RmRcbEkuaWZhY3Rvci9taXhlZEdGJUZmXGxDJD5GZFxsLUkkY2F0R0YtNiRJKWlmYWN0b3IvR0YlRmV0PkYpLUZoXGw2JEYoJkZmdDYjO0Y7Rlx0QCUwRilJJUZBSUxHRi0qJkYnRjhGKUY4RmpdbEYnRiU2I0ZkXGxGJQ==

print(`ifactor/ifact235`);

Zio2I0kibkc2IjYjSSJxR0YlNiVJKXJlbWVtYmVyR0YlSSdzeXN0ZW1HJSpwcm90ZWN0ZWRHSWFvQ29weXJpZ2h0fihjKX4xOTkxfmJ5fnRoZX5Vbml2ZXJzaXR5fm9mfldhdGVybG9vLn5BbGx+cmlnaHRzfnJlc2VydmVkLkdGJUVcc0IiIiJGLiIiIy1JIUdGJTYjRi8iIiQtRjE2I0YzIiRfIyooKUYwRi9GLilGNEYvRi4tRjE2IyIiKEYuIiImLUYxNiNGPSIlU0UqKilGMCIiJUYuRjRGLkY+Ri4tRjE2IyIjNkYuRkMqJEY4Ri4iIzUqJkYwRi5GPkYuIiIpKiQpRjBGM0YuIiIqKiRGOUYuIiM6KiZGNEYuRj5GLiIjISoqKEYwRi5GOUYuRj5GLiIlP3oqKkZCRi5GOUYuRj5GLkZERi4iJFMjKihGQkYuRjRGLkY+Ri4iJz8ycyouRkJGLkY5Ri5GPkYuRjpGLkZERi4tRjE2IyIjOEYuIiM/KiZGOEYuRj5GLiImP1YkKixGQkYuRjRGLkY+Ri5GREYuRllGLiIjPSomRjBGLkY5Ri4iI0kqKEYwRi5GNEYuRj5GLiIkIT0qKEY4Ri5GOUYuRj5GLiIlIW8lKipGTEYuRjlGLkY+Ri5GWUYuIiVTXSoqRkJGLkY5Ri5GPkYuRjpGLiIjUyomRkxGLkY+Ri4iJD8oKihGQkYuRjlGLkY+Ri4iI1gqJkY5Ri5GPkYuIiQ/IiooRkxGLkY0Ri5GPkYuIiNPKiZGOEYuRjlGLiIjaiomRjlGLkY6Ri4iJGckKihGTEYuRjlGLkY+Ri4iI2cqKEY4Ri5GNEYuRj5GLiImU2EmKixGQkYuRjlGLkY+Ri5GOkYuRkRGLiIlIW8iKipGQkYuRjRGLkY+Ri5GOkYuIiYhWz0qLEZCRi5GNEYuRj5GLkY6Ri5GREYuQC8vRiRGLkYuLy1JJWlyZW1HRis2JUYkRmVuLkYnIiIhKiYtSTFpZmFjdG9yL2lmYWN0MjM1R0koX3N5c2xpYkdGJUYmRi5GWUYuLy1GXnE2JUYkRkZGYHFGYXEqJkZjcUYuRkRGLi8tRl5xNiVGJEY8RmBxRmFxKiZGY3FGLkY6Ri4vLUZecTYlRiRGL0ZgcUZhcSomRjBGLkZjcUYuLy1GXnE2JUYkRjNGYHFGYXEqJkY0Ri5GY3FGLkY+RiVGJUYl

print(`ifactor/ifact0th`);

Zio2I0kibkc2IjYkSSRzb2xHRiVJInBHRiU2I0lhb0NvcHlyaWdodH4oYyl+MTk5MX5ieX50aGV+VW5pdmVyc2l0eX5vZn5XYXRlcmxvby5+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiVGJUMsQCQyRiQiKCJvP0hPLUkhR0YlRiNAJC1JKGlzcHJpbWVHRiVGI0YvPkYnLUkuaWZhY3Rvci9wb3dlckdGJTYkRiQuRihAJDBGJ0klRkFJTEclKnByb3RlY3RlZEdPKS1JMWlmYWN0b3IvaWZhY3QwdGhHSShfc3lzbGliR0YlNiNGJ0YoPkYnLUkvaWZhY3Rvci9wb2xscDFHRiU2JEYkIiYuSSJAJC9GJ0kqX3RyeWFnYWluR0YlPkYnLUZGNiRGJCImL0kiQCRGSj5GJ0Y8QCQvRidGPD5GJy1JMWlmYWN0b3IvcHAxMDAwMDBHRiVGI0AkRlNDJD5GJy1JL2lmYWN0b3IvYm90dG9tR0YlNiMlJWFyZ3NHQCQ0LUkldHlwZUdGPTYkRicuSShpbnRlZ2VyR0Y9T0YnKiYtRkE2JComRiQiIiJGJyEiIiZGZ242IzsiIiMlJm5hcmdzR0Zkby1GQTYkRidGZm9GZG9GJUYlRiU=

print(`ifactor/ifact1st`);

Zio2I0kibkc2IjYnSSJpR0YlSSNpZ0dGJUkickdGJUkkc29sR0YlSSN0MUdGJTYlSSlyZW1lbWJlckdGJUknc3lzdGVtRyUqcHJvdGVjdGVkR0lhb0NvcHlyaWdodH4oYyl+MTk5MX5ieX50aGV+VW5pdmVyc2l0eX5vZn5XYXRlcmxvby5+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiVFXHMpIiciNHUjKigtSSFHRiU2IyIjPCIiIi1GNTYjIiNCRjgtRjU2IyIkLChGOCIpeGohZSgqLC1GNTYjIiNIRjgtRjU2IyIjSkY4LUY1NiMiI1BGOC1GNTYjIiNWRjgtRjU2IyIjYEY4IilGKXooRyoqRjRGOC1GNTYjIiNURjgtRjU2IyIkZCJGOC1GNTYjIiRqI0Y4Ii5AZ1F4IVtTKjBGUkY4LUY1NiMiI2ZGOC1GNTYjIiNoRjgtRjU2IyIjbkY4LUY1NiMiI3JGOC1GNTYjIiN0RjgtRjU2IyIjekY4RjdGNCImVFImKihGNEY4LUY1NiMiIz5GOC1GNTYjIiRuIkY4IikydldgKipGNEY4LUY1NiMiI1pGOC1GNTYjIiReIkY4LUY1NiMiJFYlRjgiJz5UUCooRjRGOEZnbkY4LUY1NiMiJHQkRjhDJj5GKkY4PkYpRiQ/KEYnRjhGOCIiKDBGKUY4QyQ+RigtSSVpZ2NkR0YvNiRGKSY3KSIkQiQiJ1xddyIuKj1TdycqZTUiPWY7a2VCIVFTaylbb01vIioiam4qKVEpZlYiZjdzUiU+T0MlUWM1SGE9NCtXbyRRJnk8Sls1VSQiW3UqUVk3LC0mXE1FaTBKazAlPU1QImZ6Rm9VPHU0a2dBTmNudiwqcEwtZ04qKmZ3Km8iZlAqPkBKNDYzJ2VSTFUyQzM+WlE3V0BuOTpBIikpR0shPiopKTRGeiJqZmxcbT0sI0hSMSgpKip6cFY3QjVZRnhCXidmeF53bStsIyk9azhhOj8oPm93KVtOVFZkYUBcVG1CZXYhPm5VdiVlJyopZicqW3BDd1ViVzFBJXB1I2ZkNE5RbTonZmgzeHB3QW80J1EmKlEscUNsUE03T1tkK3cvSWJTVT9ocGgsOVVBYyQ9PldjRmBNPTtjJFxEJlJULGFhJVEkUW5rLmsmeSIqUiJIelojSC9rVm5nZnJwVU5rKT4kemw+Vl5fVzZjZEVxVCkzM047Im8pM3gmSGoncFV1X2FBOTpgYztdJG8ncHpJJkdHIjROOlUvd11NOzc3eiI2I0YnQCQwRihGOEMlPkYpLUklaXF1b0dGLzYkRilGKD8oRiVGOEY4RiUxJjcpRl5yIiRuJyIlajwiJSQ9JiImNjIjIiY+SCkiJ2BbV0ZlckYoQyU+RistSTJpZmFjdG9yL3doZWVsZmFjdEdGJTYkRigmNylGN0Y7RlRGYm8iJFIiIiQkRyIkaCdGZXI+RioqJkYqRjgtRjU2I0YrRjg+RigtRltzNiRGKEYrPkYqKiZGKkY4LUY1NiNGKEY4T0YqRiVGJUYl

print(`ifactor/wheelfact`);

Zio2JEkibkc2Ikkic0dGJTYlSSJpR0YlSSNpaUdGJUkjdDFHRiU2I0lhb0NvcHlyaWdodH4oYyl+MTk5MX5ieX50aGV+VW5pdmVyc2l0eX5vZn5XYXRlcmxvby5+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiVGJT8oRigsJiomIiNJIiIiLUklaXF1b0clKnByb3RlY3RlZEc2JEYmRjBGMUYxIiM6RjFGMEYlSSV0cnVlR0Y0QyQ+RioqJClGKCIiI0YxQCQwLUklaWdjZEdGNDYkRiQqKiwmRipGMSIiJSEiIkYxLCZGKkYxIiM7RkVGMSwmRipGMSIja0ZFRjEsJkYqRjEiJCc+RkVGMUYxPyhGKSwmRihGMSIjOUZFRjxGJUY3QCQwLUZANiRGKUYkRjFPRilGJUYlRiU=

print(`ifactor/pollp1`);

Zio2JEkibkc2Ikklc2VlZEdGJTYpSSdwcmltZXNHRiVJL2ZhY3Rvcml6YXRpb25zR0YlSSJ3R0YlSSJpR0YlSSN0MUdGJUklcGFpckdGJUkiZEdGJTYjSWFvQ29weXJpZ2h0fihjKX4xOTkwfmJ5fnRoZX5Vbml2ZXJzaXR5fm9mfldhdGVybG9vLn5BbGx+cmlnaHRzfnJlc2VydmVkLkdGJUYlQyc+Rig3ViIkNyYiK0QxUyxGIiwoKjNEcGAiIi82eSVlQT4/IyIueDhGRUFKJCItOGx2IVF0JiIuUD5WOmYqKSoiLlBcOUs1ISoqIi84MDdNJGVuIyIwZml0X2NNQCMiMHJqR05qKj1OIjBQMmxURmAtJyIwcE5ZOGUhZnEiMXJKYWQtJ285IiIxPnc7UU0jej4iIjFgM05BRz0sVCIySCEqW3BAaiQ0PSIyKj5cQkxUdHk6IjI4VCRvYClwVDAkIjJ4RlY1YidHRksiMipHW2ZRQks+ISoiMiRmPkJqeiNmWyoiM0glW0glcCZ5JjRBIjMkKlxHZip6blU8IyIzQDI+Ij1BJj1RTiIzKlslKUdZWCoqUj4lIjNkTUpuISo9V3NkIjNCN3ctKVtrY3cmIjM4ZWo7JFIvLE4nIjRIMSRSZDEnM0s7IiI0YEpyZ0thRlhGIiIzeFknR1ckWyxVJyoiNCIpPiUzY2EhXCYqPSIiNExOcU8jSDVtSTwiNGhQITMnbypmX0NCIjRabCgqPVwyeiRcPCI0aFpaJz0pND0kekIiNGo9LU5pKzVqIVIiNExrYW9IJHAuK1ciNFQ9SFBAKHlOJ1skIjQyOEpJRCYzYl5TIjQ4SGI4Pj9DSDEoIjRkJ0duKnlRL2klKioiNEBTIzMhRyQqPi8hKSoiNUo6S1FKWDtrLDkiNXQtKltqY3FhXiU9IjVITiFvSCI+UjN4PyI1KillWyEpUSh5QmlLIyI1cChHJXlfWUFIR0ciNVY5cTspSCtVelAjIjUuK0EvK09GaytIIjhcI0hrb1JIODclSEsnPkYpN1Y3IzckIiIjIiIqNyY3JCIiJCIiJzckIiImIiIlNyQiIihGZm83JCIjNkZmbzcnNyRGYHAiIiI3JEZicEZlcDckIiM4RmZvNyQiI0pGZm83JCIlSDdGZXA3KDckIiM8RmZvNyQiIz5GZm83JCIjQkZmbzckIiNQRmVwNyQiI1RGZXA3JCIkaiNGZXA3KDckIiNIRmZvNyQiI1ZGZXA3JCIjWkZlcDckIiNgRmVwNyQiIyQpRmVwNyQiJFYlRmVwNyg3JCIjZkZlcDckIiNoRmVwNyQiI25GZXA3JCIjckZlcDckIiQyIkZlcDckIiQ4JEZlcDcoNyQiI3RGZXA3JCIjekZlcDckIiMqKUZlcDckIiMoKkZlcDckIiQ4IkZlcDckIiVmPEZlcDcoNyQiJCwiRmVwNyQiJC4iRmVwNyQiJDQiRmVwNyQiJEYiRmVwNyQiJCg+RmVwNyQiJFwkRmVwNyg3JCIkSiJGZXA3JCIkUCJGZXA3JCIkUiJGZXA3JCIkXCJGZXA3JCIkJD5GZXA3JCIkdCRGZXA3KDckIiReIkZlcDckIiRkIkZlcDckIiRqIkZlcDckIiRuIkZlcDckIiRGI0ZlcDckIiU2OkZlcDcoNyQiJHQiRmVwNyQiJHoiRmVwNyQiJCI9RmVwNyQiJCI+RmVwNyQiJGQjRmVwNyQiJXo3RmVwNyg3JCIkKj5GZXA3JCIkNiNGZXA3JCIkQiNGZXA3JCIkSCNGZXA3JCIkKFtGZXA3JCIkeCZGZXA3KDckIiRMI0ZlcDckIiRSI0ZlcDckIiRUI0ZlcDckIiReI0ZlcDckIiRuJEZlcDckIiRyJkZlcDcoNyQiJHAjRmVwNyQiJHIjRmVwNyQiJHgjRmVwNyQiJCJHRmVwNyQiJGYkRmVwNyQiJGomRmVwNyg3JCIkJEdGZXA3JCIkJEhGZXA3JCIkMiRGZXA3JCIkNiRGZXA3JCIkUCRGZXA3JCIkXCVGZXA3KDckIiQ8JEZlcDckIiRKJEZlcDckIiRaJEZlcDckIiR6JEZlcDckIiRSJUZlcDckIiR4J0ZlcDcoNyQiJGAkRmVwNyQiJCRRRmVwNyQiJCpRRmVwNyQiJChSRmVwNyQiJHAmRmVwNyQiJUI6RmVwNyg3JCIkLCVGZXA3JCIkNCVGZXA3JCIkPiVGZXA3JCIkQCVGZXA3JCIkKmZGZXA3JCIkNipGZXA3KDckIiRKJUZlcDckIiRMJUZlcDckIiRkJUZlcDckIiRoJUZlcDckIiQ8J0ZlcDckIiVmN0ZlcDcoNyQiJGolRmVwNyQiJG4lRmVwNyQiJHolRmVwNyQiJCJcRmVwNyQiJHQoRmVwNyQiJEApRmVwNyg3JCIkKlxGZXA3JCIkLiZGZXA3JCIkNCZGZXA3JCIkQCZGZXA3JCIkLChGZXA3JCIlTD5GZXA3KDckIiRCJkZlcDckIiRUJkZlcDckIiRaJkZlcDckIiRkJkZlcDckIiQiKSlGZXA3JCIlXDdGZXA3KDckIiQoZUZlcDckIiQkZkZlcDckIiQsJ0ZlcDckIiQyJ0ZlcDckIiRIKkZlcDckIiV0PUZlcDcoNyQiJDgnRmVwNyQiJD4nRmVwNyQiJEonRmVwNyQiJFQnRmVwNyQiJHIqRmVwNyQiJWY5RmVwNyg3JCIkVidGZXA3JCIkWidGZXA3JCIkYCdGZXA3JCIkZidGZXA3JCIlODVGZXA3JCIlXj5GZXA3KDckIiRoJ0ZlcDckIiR0J0ZlcDckIiQkb0ZlcDckIiQicEZlcDckIiUiNCJGZXA3JCIlSj1GZXA3KDckIiQ0KEZlcDckIiQ+KEZlcDckIiRGKEZlcDckIiRMKEZlcDckIiVqNUZlcDckIiUqKj5GZXA3KDckIiRSKEZlcDckIiRWKEZlcDckIiReKEZlcDckIiRkKEZlcDckIiQkKSpGZXA3JCIlej1GZXA3KDckIiRoKEZlcDckIiRwKEZlcDckIiQoeUZlcDckIiQoekZlcDckIiRuKkZlcDckIiUqeSJGZXA3KDckIiQ0KUZlcDckIiQ2KUZlcDckIiRCKUZlcDckIiRGKUZlcDckIiUyOEZlcDckIiUkKj5GZXA3KDckIiRIKUZlcDckIiRSKUZlcDckIiRgKUZlcDckIiRkKUZlcDckIiVGOEZlcDckIiUqKT1GZXA3KDckIiRmKUZlcDckIiRqKUZlcDckIiR4KUZlcDckIiQkKSlGZXA3JCIlIkgiRmVwNyQiJSw4RmVwNyg3JCIkKCkpRmVwNyQiJDIqRmVwNyQiJD4qRmVwNyQiJFAqRmVwNyQiJSQ0IkZlcDckIiVyOkZlcDcoNyQiJFQqRmVwNyQiJFoqRmVwNyQiJGAqRmVwNyQiJHgqRmVwNyQiJUA4RmVwNyQiJXo6RmVwNyg3JCIkIioqRmVwNyQiJCgqKkZlcDckIiU0NUZlcDckIiU+NUZlcDckIiVCN0ZlcDckIiVyPUZlcDcoNyQiJUA1RmVwNyQiJUo1RmVwNyQiJUw1RmVwNyQiJVw1RmVwNyQiJTw2RmVwNyQiJXQ4RmVwNyg3JCIlUjVGZXA3JCIlXjVGZXA3JCIlaDVGZXA3JCIlcDVGZXA3JCIlUDdGZXA3JCIlYDpGZXA3KDckIiUoMyJGZXA3JCIlKDQiRmVwNyQiJS42RmVwNyQiJUI2RmVwNyQiJTQ5RmVwNyQiJXg9RmVwNyg3JCIlNDZGZXA3JCIlSDZGZXA3JCIlXjZGZXA3JCIlajZGZXA3JCIlIlEiRmVwNyQiJSw+RmVwNyg3JCIlYDZGZXA3JCIlcjZGZXA3JCIlIj0iRmVwNyQiJSg9IkZlcDckIiUqRyJGZXA3JCIlSDlGZXA3KDckIiUkPiJGZXA3JCIlLDdGZXA3JCIlODdGZXA3JCIlPDdGZXA3JCIlJEciRmVwNyQiJSRcIkZlcDcoNyQiJUo3RmVwNyQiJXg3RmVwNyQiJShIIkZlcDckIiUuOEZlcDckIiVWOkZlcDckIiVCPEZlcDcoNyQiJT44RmVwNyQiJWg4RmVwNyQiJW44RmVwNyQiJUw5RmVwNyQiJT47RmVwNyQiJVo8RmVwNyg3JCIlKlIiRmVwNyQiJUI5RmVwNyQiJUY5RmVwNyQiJWA5RmVwNyQiJSRbIkZlcDckIiUsO0ZlcDcoNyQiJVI5RmVwNyQiJVo5RmVwNyQiJV45RmVwNyQiJSpcIkZlcDckIiVqO0ZlcDckIiVoPUZlcDcoNyQiJXI5RmVwNyQiJSJbIkZlcDckIiUoWyJGZXA3JCIlKGYiRmVwNyQiJUo+RmVwNyQiJVo9RmVwNyg3JCIlKlsiRmVwNyQiJUo6RmVwNyQiJVw6RmVwNyQiJW47RmVwNyQiJXo+RmVwNyQiJSR5IkZlcDcoNyQiJWY6RmVwNyQiJW46RmVwNyQiJSRlIkZlcDckIiUkcCJGZXA3JCIlQj1GZXA3JCIlXD5GZXA3KDckIiUyO0ZlcDckIiU0O0ZlcDckIiU4O0ZlcDckIiUoKj5GZXA3JCIlKCk+RmVwNyQiJTQ8RmVwNyg3JCIlQDtGZXA3JCIlRjtGZXA3JCIlUDtGZXA3JCIlQDxGZXA3JCIleDxGZXA3JCIlLD1GZXA3KDckIiVkO0ZlcDckIiVwO0ZlcDckIiUocCJGZXA3JCIlYDxGZXA3JCIlKHkiRmVwNyQiJXQ+RmVwNyk3JCIlKnAiRmVwNyQiJTI+RmVwNyQiJUw8RmVwNyQiJW49RmVwNyQiJTg+RmVwNyQiJTY9RmVwNyQiJVQ8RmVwPkYqRiY/KEYrRmVwRmVwLUklbm9wc0clKnByb3RlY3RlZEc2I0YoSSV0cnVlR0ZgaW1DJD5GLC1JJW1vZHBHRmBpbTYkLUkmcG93ZXJHRiU2JEYqJkYoNiNGK0YkQCUwLUklaWdjZEdGYGltNiQsJkYsRmVwRmVwISIiRiRGZXBDJkAkMEYsRmVwT0Zfam0+Ri4mRilGXGptPyZGLUYuRmJpbT8oRiVGZXBGZXAmRi02I0Zmb0ZiaW1DJD5GKi1GZmltNiQtRmlpbTYkRiomRi02I0ZlcEYkQCYvRipGZXBAJDJGZXBGK08tJSlwcm9jbmFtZUc2JEYkLUZmaW02JC1GaWltNiRGJkZkW25GJDAtRmBqbTYkLCZGKkZlcEZlcEZjam1GJEZlcE9GY1xuT0kqX3RyeWFnYWluR0YlPkYqRixJJUZBSUxHRmBpbUYlRiVGJQ==

print(`ifactor/pp100000`);

Zio2I0kibkc2IjYkSSJpR0YlSSJ0R0YlNiNJYW9Db3B5cmlnaHR+KGMpfjE5OTB+Ynl+dGhlflVuaXZlcnNpdHl+b2Z+V2F0ZXJsb28ufkFsbH5yaWdodHN+cmVzZXJ2ZWQuR0YlRiVDJD8oRiciJStTIiUrZyImK1MqSSV0cnVlRyUqcHJvdGVjdGVkR0MkPkYoLUklaWdjZEdGMTYkKEkmX3BycHJHRiVGJ0YkQCQwRigiIiJAJTBGKEYkLUknUkVUVVJOR0YxNiNGKC1GPzYjLUkyaWZhY3Rvci93aGVlbGZhY3RHSShfc3lzbGliR0YlNiRGJCwmRidGO0Y7RjtJJUZBSUxHRjFGJUYlRiU=

print(`ifactor/easy`);

Zio2I0kibkc2IkYlNiNJYW9Db3B5cmlnaHR+KGMpfjE5OTB+Ynl+dGhlflVuaXZlcnNpdHl+b2Z+V2F0ZXJsb28ufkFsbH5yaWdodHN+cmVzZXJ2ZWQuR0YlRiUtJkkwdG9vbHMvZ2VuZ2xvYmFsR0YlNiMiIiI2Iy1JJGNhdEclKnByb3RlY3RlZEc2JkkhR0YlLkkjX2NHRiUtSSdsZW5ndGhHRjBGIy5JIl9HRiVGJUYlRiU=

print(`ifactor/ifact235`);

Zio2I0kibkc2IjYjSSJxR0YlNiVJKXJlbWVtYmVyR0YlSSdzeXN0ZW1HJSpwcm90ZWN0ZWRHSWFvQ29weXJpZ2h0fihjKX4xOTkxfmJ5fnRoZX5Vbml2ZXJzaXR5fm9mfldhdGVybG9vLn5BbGx+cmlnaHRzfnJlc2VydmVkLkdGJUVcc0IiIiJGLiIiIy1JIUdGJTYjRi8iIiQtRjE2I0YzIiRfIyooKUYwRi9GLilGNEYvRi4tRjE2IyIiKEYuIiImLUYxNiNGPSIlU0UqKilGMCIiJUYuRjRGLkY+Ri4tRjE2IyIjNkYuRkMqJEY4Ri4iIzUqJkYwRi5GPkYuIiIpKiQpRjBGM0YuIiIqKiRGOUYuIiM6KiZGNEYuRj5GLiIjISoqKEYwRi5GOUYuRj5GLiIlP3oqKkZCRi5GOUYuRj5GLkZERi4iJFMjKihGQkYuRjRGLkY+Ri4iJz8ycyouRkJGLkY5Ri5GPkYuRjpGLkZERi4tRjE2IyIjOEYuIiM/KiZGOEYuRj5GLiImP1YkKixGQkYuRjRGLkY+Ri5GREYuRllGLiIjPSomRjBGLkY5Ri4iI0kqKEYwRi5GNEYuRj5GLiIkIT0qKEY4Ri5GOUYuRj5GLiIlIW8lKipGTEYuRjlGLkY+Ri5GWUYuIiVTXSoqRkJGLkY5Ri5GPkYuRjpGLiIjUyomRkxGLkY+Ri4iJD8oKihGQkYuRjlGLkY+Ri4iI1gqJkY5Ri5GPkYuIiQ/IiooRkxGLkY0Ri5GPkYuIiNPKiZGOEYuRjlGLiIjaiomRjlGLkY6Ri4iJGckKihGTEYuRjlGLkY+Ri4iI2cqKEY4Ri5GNEYuRj5GLiImU2EmKixGQkYuRjlGLkY+Ri5GOkYuRkRGLiIlIW8iKipGQkYuRjRGLkY+Ri5GOkYuIiYhWz0qLEZCRi5GNEYuRj5GLkY6Ri5GREYuQC8vRiRGLkYuLy1JJWlyZW1HRis2JUYkRmVuLkYnIiIhKiYtSTFpZmFjdG9yL2lmYWN0MjM1R0koX3N5c2xpYkdGJUYmRi5GWUYuLy1GXnE2JUYkRkZGYHFGYXEqJkZjcUYuRkRGLi8tRl5xNiVGJEY8RmBxRmFxKiZGY3FGLkY6Ri4vLUZecTYlRiRGL0ZgcUZhcSomRjBGLkZjcUYuLy1GXnE2JUYkRjNGYHFGYXEqJkY0Ri5GY3FGLkY+RiVGJUYl

interface(echo=3);

IiIk

read("../../../tmp/ifactor");

# # This is a commented version of the Maple procedure # ifactor for analysis of the methods. # # The input parameter n in general a positive integer. # # After a parameter cheking other cases: negative # integer, rational numbers, etc. are treated. # # The first step is remove factors 2, 3, 5,7, 11, 13. # gcd(n,2^4*3^2*5*7*11*13) calculated until became 1. # If it is greater then 1, then this gcd is factored by # the small routine ifactor/ifact235. # # The second step is remove somewhat larger prime factors below # from 17 to 1699. This also happens with the gcd trick. Until the # gcd is larger then 1, the routine ifactor/ifact1st find these # factors from the gcd. # # If the remainder still greater then 1, then the procedure # corresponding to the second parameter is loaded until the name # `ifactor/bottom` and the procedure ifactor/ifact0th called # with passing thierd and further parameters. # This procedure use `ifactor/bottom`. # # If no second parameter is passed, then the `ifactor/morrbril` # procedure loaded and the procedure ifactor/ifact0th called. # > > ifactor=proc(n) > local sol,r; > global `ifactor/bottom`; > options remember,system,`Copyright 1993 by Waterloo Maple Software`; > if nargs < 1 or 1 < nargs and not type(args[2],name) then > ERROR(`invalid arguments`) > fi; > if type(n,integer) then > if 0 < n then sol := 1; r := n > elif n < 0 then sol := -1; r := -n > else RETURN(0) > fi > elif type(n,fraction) then RETURN(ifactor(op(1,n))/ifactor(op(2,n))) > elif type(n,{`*`,set,list,relation}) then RETURN(map(ifactor,n)) > elif type(n,`^`) and type(op(2,n),integer) then > RETURN(ifactor(op(1,n))^op(2,n)) > elif type(n,``(integer)) then RETURN(ifactor(op(1,n))) > else ERROR(`invalid arguments`) > fi; > igcd(r,720720); > while % <> 1 do > sol := sol*`ifactor/ifact235`(%); r := iquo(r,%%); igcd(%%%,r) > od; > igcd(r,1165429511437014421182564255394118062787055181073690352484362724429288655197089578084537426127020962982242734844013923456967013254066860138774356183909763696443067069059862065192038988478418219082943879223019472668430243781122990303492985397077416788992156275405498099765357945192479722213857227212000608128560171197659349424196117167227902201722912212770434834579779297150544465360850511025966392537774945829901979588813143194547543583825739867652770670299983480797335874643414610343435150187989728154996577619208807489382147598111758441747971820027670613338896899878156111058787897307947215801259320492843992867678444319238233981852191131219418884757870660310007540404320811366733424902110215685045241323250289709233); > while % <> 1 do > sol := sol*`ifactor/ifact1st`(%); r := iquo(r,%%); igcd(%%%,r) > od; > if r <> 1 then > if nargs = 1 then > `ifactor/bottom` := readlib('`ifactor/morrbril`'); > `ifactor/ifact0th`(r) > else > `ifactor/bottom` := readlib(`ifactor/`.args[2]); > `ifactor/ifact0th`(r,args[3 .. nargs]) > fi; > if % <> FAIL then sol*% else FAIL fi > else sol > fi > end;

L0koaWZhY3Rvckc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2ImYqNiNJIm5HRic2JEkkc29sR0YnSSJyR0YnNiVJKXJlbWVtYmVyR0YnSSdzeXN0ZW1HRiVJSkNvcHlyaWdodH4xOTkzfmJ5fldhdGVybG9vfk1hcGxlflNvZnR3YXJlR0YnRidDKUAkNTIlJm5hcmdzRyIiIjMyRjdGNjQtSSV0eXBlR0YlNiQmJSVhcmdzRzYjIiIjSSVuYW1lR0YlLUkmRVJST1JHRiU2I0kyaW52YWxpZH5hcmd1bWVudHNHRidALS1GPDYkRipJKGludGVnZXJHRiVAJzIiIiFGKkMkPkYsRjc+Ri1GKjJGKkZNQyQ+RiwhIiI+Ri0sJEYqRlQtSSdSRVRVUk5HRiU2I0ZNLUY8NiRGKkkpZnJhY3Rpb25HRiUtRlg2IyomLUYjNiMtSSNvcEdGJTYkRjdGKkY3LUYjNiMtRl1vNiRGQUYqRlQtRjw2JEYqPCZJIipHRiVJJHNldEdGJUkpcmVsYXRpb25HRiVJJWxpc3RHRiUtRlg2Iy1JJG1hcEdGJTYkRiNGKjMtRjw2JEYqSSJeR0YlLUY8NiRGYW9GSi1GWDYjKUZqbkZhby1GPDYkRiotSSFHRic2I0ZKLUZYNiNGam5GQy1JJWlnY2RHRiU2JEYtIic/MnM/KEYnRjdGN0YnMEkiJUdGJ0Y3QyU+RiwqJkYsRjctSTFpZmFjdG9yL2lmYWN0MjM1R0YmNiNGZXFGNz5GLS1JJWlxdW9HRiU2JEYtSSMlJUdGJy1GYHE2JEkkJSUlR0YnRi0tRmBxNiRGLSJpZ21MIzQoKkddS0tUXy8mbzotNi1cVUxuTzYzSy8vYTIrSmcxKHl2JSkpPSU+NzgiPl89KVJCUSM+Vld5dydHKlIlR1w/JGY3IWVAWnpJKCp5eWU1NmMieSkqKm8qKVFMaHF3LT89KHp1VCVlPDYpZlpAUSpbMikzIz53ZCcqXDpHKCopej1dXlZWLmg5TWt1ZUwoeiFbJCkqKkhxMXhfdycpUmQjUWVWdmElPlZKIikpZXo+ISpIZSVceFBEUm1mLTYwJjNPbFdhXXJIeih6WCRbVnFGQDdIcyxBIXpBbnI2Jz5DJVwkZnc+cixjRyIzMSs3c0FkUUBBKHpDPlh6TmwoKjQpXDBhRmNAKiopeTt1MihSJilIXC4uKkg3InlWLVZvRVo+SUF6USVIMz4jPSV5JSkpKlE/Pmw/JylmIXBxMVZrcGooNFI9Y1Z4USwnbzFhSyxucFhCUixXW3RVQSlIJzQtRmhVUFgzeSYqMyg+YicpR0hXc2lWW18ucHQ1PWJxeWkhPVRSYlVjIz1AVyxQOV5IYTsiPyhGJ0Y3RjdGJ0ZkcUMlPkYsKiZGLEY3LUkxaWZhY3Rvci9pZmFjdDFzdEdGJkZbckY3RlxyRmFyQCUwRi1GN0MkQCUvRjZGN0MkPkkvaWZhY3Rvci9ib3R0b21HRictSShyZWFkbGliR0YlNiMuSTFpZmFjdG9yL21vcnJicmlsR0YnLUkxaWZhY3Rvci9pZmFjdDB0aEdGJjYjRi1DJD5GZHMtRmZzNiMtSSIuR0YnNiRJKWlmYWN0b3IvR0YnRj4tRlt0NiRGLSZGPzYjOyIiJEY2QCUwRmVxSSVGQUlMR0YlKiZGLEY3RmVxRjdGXXVGLEYnNiNGZHNGJw==

> > # # This small routine find the factors of # a positive integer known to have the # gcd of 2^4*3^2*5*7*11*13 and the number # to factor. The factorization is given back. # > > ifactor/ifact235=proc(n) > local q; > options remember,system,`Copyright 1993 by Waterloo Maple Software`; > if n = 1 then 1 > elif irem(n,13,'q') = 0 then `ifactor/ifact235`(q)*``(13) > elif irem(n,11,'q') = 0 then `ifactor/ifact235`(q)*``(11) > elif irem(n,7,'q') = 0 then `ifactor/ifact235`(q)*``(7) > elif irem(n,2,'q') = 0 then ``(2)*`ifactor/ifact235`(q) > elif irem(n,3,'q') = 0 then ``(3)*`ifactor/ifact235`(q) > else ``(5) > fi > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSlpZmFjdDIzNUdGKCEiImYqNiNJIm5HRig2I0kicUdGKDYlSSlyZW1lbWJlckdGKEknc3lzdGVtR0YmSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQC8vRi5GKUYpLy1JJWlyZW1HRiY2JUYuIiM4LkYwIiIhKiYtSTFpZmFjdG9yL2lmYWN0MjM1R0YnRi9GKS1JIUdGKDYjRjtGKS8tRjk2JUYuIiM2RjxGPSomRj9GKS1GQjYjRkdGKS8tRjk2JUYuIiIoRjxGPSomRj9GKS1GQjYjRk5GKS8tRjk2JUYuIiIjRjxGPSomLUZCNiNGVUYpRj9GKS8tRjk2JUYuIiIkRjxGPSomLUZCNiNGZm5GKUY/RiktRkI2IyIiJkYoRihGKA==

> > # # This routine find the factors from 17 to 1699. The # input is a positive integer containing only factors # between 17 and 1699. # # The routine divides first the factors into # smaller groups 17--19, 23--37, 41--67, # 71--137, 139-281, 283--659, 661--1699 using the gcd trick. # Then, depending on the gcd obtained, a search routine # ifactor/wheelfact is started. The search limit is # choosen supposing two factors find: 17*19, 23*29, 41*43, # 71*73, 139*149, 283*293, 661*673. # > > ifactor/ifact1st=proc(n) > local i,ig,r,sol; > options remember,system,`Copyright 1993 by Waterloo Maple Software`; > sol := 1; > r := n; > for i to 7 while r <> 1 do > ig := igcd(r,(323,765049,1058967640189,9168346848864403802358641659, > 342104831177853836844000918542910563842436194397212591435983889,7927098891903228881221514672144123847190824074233395860811093121199375916897659993560023369901756756352260640974174268277959137341840564310562263449502011246389,179121216345076044215350912828530796966835016565315142254527442696632957708868116350808841702657561144525143196579319864354269715960674364042924779291399178564036467383384545401413952549356161834532756441918356224214016169612042405530047600574836123437652470013895386096822766977086159615663835095759274694220644554276246948965989658475426719075582366414921545743413548876681972015541364188265006676517759651237727461023124369799987063929201186649 > )[i]); > if ig <> 1 then > r := iquo(r,ig); > while [323,667,1763,5183,20711,82919,444853][i] <= ig do > `ifactor/wheelfact`(ig,[17,23,41,71,139,283,661][i]); > sol := sol*``(%); > ig := iquo(ig,%%) > od; > sol := sol*``(ig) > fi > od; > sol > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSlpZmFjdDFzdEdGKCEiImYqNiNJIm5HRig2JkkiaUdGKEkjaWdHRihJInJHRihJJHNvbEdGKDYlSSlyZW1lbWJlckdGKEknc3lzdGVtR0YmSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQyY+RjNGKT5GMkYuPyhGMEYpRikiIigwRjJGKUMkPkYxLUklaWdjZEdGJjYkRjImNikiJEIkIidcXXciLio9U3cnKmU1Ij1mO2tlQiFRU2spW29NbyIqImpuKilRKWZWImY3c1IlPk9DJVFjNUhhPTQrV28kUSZ5PEpbNVUkIlt1KlFZNywtJlxNRWkwSmswJT1NUCJmekZvVTx1NGtnQU5jbnYsKnBMLWdOKipmdypvImZQKj5ASjQ2MydlUkxVMkMzPlpRN1dAbjk6QSIpKUdLIT4qKSk0RnoiamZsXG09LCNIUjEoKSoqenBWN0I1WUZ4Ql4nZnhed20rbCMpPWs4YTo/KD5vdylbTlRWZGFAXFRtQmV2IT5uVXYlZScqKWYnKltwQ3dVYlcxQSVwdSNmZDROUW06J2ZoM3hwd0FvNCdRJipRLHFDbFBNN09bZCt3L0liU1U/aHBoLDlVQWMkPT5XY0ZgTT07YyRcRCZSVCxhYSVRJFFuay5rJnkiKlIiSHpaI0gva1ZuZ2ZycFVOayk+JHpsPlZeX1c2Y2RFcVQpMzNOOyJvKTN4JkhqJ3BVdV9hQTk6YGM7XSRvJ3B6SSZHRyI0TjpVL3ddTTs3N3oiNiNGMEAkMEYxRilDJT5GMi1JJWlxdW9HRiY2JEYyRjE/KEYoRilGKUYoMSY3KUZFIiRuJyIlajwiJSQ9JiImNjIjIiY+SCkiJ2BbV0ZMRjFDJS1JMmlmYWN0b3Ivd2hlZWxmYWN0R0YnNiRGMSY3KSIjPCIjQiIjVCIjciIkUiIiJCRHIiRoJ0ZMPkYzKiZGM0YpLUkhR0YoNiNJIiVHRihGKT5GMS1GUjYkRjFJIyUlR0YoPkYzKiZGM0YpLUZobzYjRjFGKUYzRihGKEYo

> > # # This routine find the prime factors with searcing. # The input is a positive integer known to have only factor # between 17 and 1699. # # The "large searching" here goes using gcd too, using # intervals with length 30. The find gcd's larger then 1 # finally factored by a smaller search trying odd numbers. # > > ifactor/wheelfact=proc(n,s) > local i,ii; > options `Copyright 1993 by Waterloo Maple Software`; > for i from 30*iquo(s,30)+15 by 30 do > i^2; > if igcd(n,(%-4)*(%-16)*(%-64)*(%-196)) <> 1 then > for ii from i-14 by 2 do > if igcd(ii,n) <> 1 then RETURN(ii) fi > od > fi > od > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSp3aGVlbGZhY3RHRighIiJmKjYkSSJuR0YoSSJzR0YoNiRJImlHRihJI2lpR0YoNiNJSkNvcHlyaWdodH4xOTkzfmJ5fldhdGVybG9vfk1hcGxlflNvZnR3YXJlR0YoRig/KEYxLCYqJiIjSUYpLUklaXF1b0dGJjYkRi9GOEYpRikiIzpGKUY4RihJJXRydWVHRiZDJCokKUYxIiIjRilAJDAtSSVpZ2NkR0YmNiRGLioqLCZJIiVHRihGKSIiJUYrRiksJkZJRikiIztGK0YpLCZGSUYpIiNrRitGKSwmRklGKSIkJz5GK0YpRik/KEYyLCZGMUYpIiM5RitGQUYoRj1AJDAtRkU2JEYyRi5GKS1JJ1JFVFVSTkdGJjYjRjJGKEYoRig=

> > # # This is the general end-factoring routine. # The input is a positive integer containing no # factor below 1700. # # If the number is less then 1709^2, then it is # a prime and simple returned. Otherwise the number is # tested and if it is found to be prime, returned. # # The second step is to try whether the numbers is # a power using the routine ifactor/power. # # The thierd step is to try Pollard's p-1 method. # If there are chanches then tried again. # After the second failer or if no chances # another version called ifactor/pp100000 # called to find factors p for which p-1 # has only factors below 100000. # # The last try is the procedure ifactor/bottom, # which depends on the second input parameter. # # Finally, if no factor is found, then the # routine returns with fail. Otherwise if is called # for the factors found and returns with the product. # > > ifactor/ifact0th=proc(n) > local sol,p; > options `Copyright 1993 by Waterloo Maple Software`; > if n < 2920681 then RETURN(``(n)) fi; > if isprime(n) then RETURN(``(n)) fi; > sol := `ifactor/power`(n,'p'); > if sol <> FAIL then RETURN(`ifactor/ifact0th`(sol)^p) fi; > sol := `ifactor/pollp1`(n,13003); > if sol = _tryagain then sol := `ifactor/pollp1`(n,13004) fi; > if sol = _tryagain then sol := FAIL fi; > if sol = FAIL then sol := `ifactor/pp100000`(n) fi; > if sol = FAIL then > sol := `ifactor/bottom`(args); > if not type(sol,integer) then RETURN(sol) fi > fi; > `ifactor/ifact0th`(n/sol,args[2 .. nargs])* > `ifactor/ifact0th`(sol,args[2 .. nargs]) > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSlpZmFjdDB0aEdGKCEiImYqNiNJIm5HRig2JEkkc29sR0YoSSJwR0YoNiNJSkNvcHlyaWdodH4xOTkzfmJ5fldhdGVybG9vfk1hcGxlflNvZnR3YXJlR0YoRihDLEAkMkYuIigibz9ILUknUkVUVVJOR0YmNiMtSSFHRihGLUAkLUkoaXNwcmltZUdGKEYtRjg+RjAtSS5pZmFjdG9yL3Bvd2VyR0YoNiRGLi5GMUAkMEYwSSVGQUlMR0YmLUY5NiMpLUkxaWZhY3Rvci9pZmFjdDB0aEdGJzYjRjBGMT5GMC1JL2lmYWN0b3IvcG9sbHAxR0YnNiRGLiImLkkiQCQvRjBJKl90cnlhZ2FpbkdGKD5GMC1GUDYkRi4iJi9JIkAkRlQ+RjBGR0AkL0YwRkc+RjAtSTFpZmFjdG9yL3BwMTAwMDAwR0YnRi1AJEZnbkMkPkYwLUkvaWZhY3Rvci9ib3R0b21HRig2IyUlYXJnc0dAJDQtSSV0eXBlR0YmNiRGMEkoaW50ZWdlckdGJi1GOUZNKiYtRkw2JComRi5GKUYwRismRmFvNiM7IiIjJSZuYXJnc0dGKS1GTDYkRjBGXXBGKUYoRihGKA==

> > # # This small procedure check whether the input # positive number is a prime power. It is known # that there are no too small factors. The factor # is given back and the exponent in the parameter # 'p'. # > > ifactor/power:=proc(n,p) > local i,r; > options `Copyright 1993 by Waterloo Maple Software`; > r := isqrt(n); > if r^2 = n then p := 2; RETURN(r) fi; > for i from 3 by 2 to iquo(length(n)+2,3) do > if not isprime(i) then next fi; > r := readlib('iroot')(n,i); > if r^i = n then p := i; RETURN(r) fi > od; > FAIL > end; Error, invalid left hand side of assignment

> > # # This procedure try to find factors of the input # positive integer n using Pollard's p-1 method. # The second parameter is the base to find the # factors. # # The base is in a cycle powered gradually to 2^9, # 3^6*5^4*7^2*11^2, 7*11*13^2*31^2*1229, # 17^2*19^2*23^2*37*41*263, 29^2*43*47*53*83*443, # ... 1699*1733*1741*1811*1867*1907*1913. # After each step the gcd of the power-1 and n # is calculated. If the power was not 1, then # this gcd is returned. If the power was 1, # i.e. more factor steps in, then the power # calculation is repeated in smaller steps. # If this separates the factors, then a factor # is given back. Otherwise we try again. # > > ifactor/pollp1=proc(n,seed) > local d,i,k,primes,w; > options `Copyright 1993 by Waterloo Maple Software`; > primes := [512,2701400625,15369250897,22019225847811,3312226271377, > 573380756513,9895915431937,9901032144937,26758334120513, > 221345652736259,351896335286371,602532741650737,705905813463569, > 1146860257543171,1197923438167619,4101182822350853,18093632169489029, > 15787341332349199,30541698536834113,32272865510432777, > 90193223385948289,94859279632319593,220957856942948429, > 217426779959284993,353818522181190721,419399945462884489, > 577244189067313457,576566448802761223,635010439316635813, > 1163208606573930629,1274527543260713153,964201483442864677, > 1189549054560841981,1730661029236703533,2324525996860803761, > 1749379074918976547,2379318098186474761,3906310006235021863, > 4400036932968546433,3486357872137291841,4051550852530311307, > 7062924201913552913,9946204387896728657,9800419932800824021, > 14016416453138321531,18451547056634890273,20770839191296803529, > 23262237873880485889,28282922465278428769,23779420029816701443, > 29006427360004220003,63229412132939686429249]; > seed; > for i to nops(primes) do > modp(power(%,primes[i]),n); > if igcd(%-1,n) <> 1 then > if % <> 1 then RETURN(igcd(%-1,n)) fi; > w := %%; > d := numtheory[factorset](primes[i]); > for k in d do > w := modp(power(w,k),n); > if w = 1 then > if 1 < i then RETURN(procname(n,modp(power(seed,k),n))) > fi > elif igcd(w-1,n) <> 1 then RETURN(igcd(w-1,n)) > fi > od; > RETURN(_tryagain) > fi > od; > FAIL > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSdwb2xscDFHRighIiJmKjYkSSJuR0YoSSVzZWVkR0YoNidJImRHRihJImlHRihJImtHRihJJ3ByaW1lc0dGKEkid0dGKDYjSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQyY+RjQ3ViIkNyYiK0QxUyxGIiwoKjNEcGAiIi82eSVlQT4/IyIueDhGRUFKJCItOGx2IVF0JiIuUD5WOmYqKSoiLlBcOUs1ISoqIi84MDdNJGVuIyIwZml0X2NNQCMiMHJqR05qKj1OIjBQMmxURmAtJyIwcE5ZOGUhZnEiMXJKYWQtJ285IiIxPnc7UU0jej4iIjFgM05BRz0sVCIySCEqW3BAaiQ0PSIyKj5cQkxUdHk6IjI4VCRvYClwVDAkIjJ4RlY1YidHRksiMipHW2ZRQks+ISoiMiRmPkJqeiNmWyoiM0glW0glcCZ5JjRBIjMkKlxHZip6blU8IyIzQDI+Ij1BJj1RTiIzKlslKUdZWCoqUj4lIjNkTUpuISo9V3NkIjNCN3ctKVtrY3cmIjM4ZWo7JFIvLE4nIjRIMSRSZDEnM0s7IiI0YEpyZ0thRlhGIiIzeFknR1ckWyxVJyoiNCIpPiUzY2EhXCYqPSIiNExOcU8jSDVtSTwiNGhQITMnbypmX0NCIjRabCgqPVwyeiRcPCI0aFpaJz0pND0kekIiNGo9LU5pKzVqIVIiNExrYW9IJHAuK1ciNFQ9SFBAKHlOJ1skIjQyOEpJRCYzYl5TIjQ4SGI4Pj9DSDEoIjRkJ0duKnlRL2klKioiNEBTIzMhRyQqPi8hKSoiNUo6S1FKWDtrLDkiNXQtKltqY3FhXiU9IjVITiFvSCI+UjN4PyI1KillWyEpUSh5QmlLIyI1cChHJXlfWUFIR0ciNVY5cTspSCtVelAjIjUuK0EvK09GaytIIjhcI0hrb1JIODclSEsnRi8/KEYyRilGKS1JJW5vcHNHRiY2I0Y0SSV0cnVlR0YmQyQtSSVtb2RwR0YmNiQtSSZwb3dlckdGKDYkSSIlR0YoJkY0NiNGMkYuQCQwLUklaWdjZEdGJjYkLCZGZXBGKUYpRitGLkYpQydAJDBGZXBGKS1JJ1JFVFVSTkdGJjYjRmpwPkY1SSMlJUdGKD5GMS0mSSpudW10aGVvcnlHRig2I0kqZmFjdG9yc2V0R0YoNiNGZnA/JkYzRjFGXXBDJD5GNS1GYHA2JC1GY3A2JEY1RjNGLkAmL0Y1RilAJDJGKUYyLUZicTYjLSUpcHJvY25hbWVHNiRGLi1GYHA2JC1GY3A2JEYvRjNGLjAtRltxNiQsJkY1RilGKUYrRi5GKS1GYnE2I0Zicy1GYnE2I0kqX3RyeWFnYWluR0YoSSVGQUlMR0YmRihGKEYo

> > # # This procedure is a conterpart of the # procedure above. Using the huge integers # _prpr4000, _prpr10000, ... , _prpr94000 # which are products of primes from 4000 to 10000, # from 10000 to 16000, etc. for which p-1 # is not smooth, with the gcd method and using # ifactor/wheelfract find these factors too. # > > ifactor/pp100000=proc(n) > local i; > options `Copyright 1993 by Waterloo Maple Software`; > for i from 4000 by 6000 to 94000 do > igcd(_prpr.i,n); > if % <> 1 then > if % <> n then RETURN(%) > else RETURN(`ifactor/wheelfact`(n,i+1)) > fi > fi > od; > FAIL > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSlwcDEwMDAwMEdGKCEiImYqNiNJIm5HRig2I0kiaUdGKDYjSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQyQ/KEYwIiUrUyIlK2ciJitTKkkldHJ1ZUdGJkMkLUklaWdjZEdGJjYkLUkiLkdGKDYkSSZfcHJwckdGKEYwRi5AJDBJIiVHRihGKUAlMEZDRi4tSSdSRVRVUk5HRiY2I0ZDLUZHNiMtSTJpZmFjdG9yL3doZWVsZmFjdEdGJzYkRi4sJkYwRilGKUYpSSVGQUlMR0YmRihGKEYo

> > # # The smallest constant used in ifactor/pp100000, # as an example. # > > _prpr4000:=9965058060504894463265688289961456357240997208361983661053484670734\ > 839012679433390148012701298284489624410640732766266494846161655447276888937196670540674723972052729080367786436138015687952564246043526647401039910701757660785727431053299423;

Ilx6QiUqSGA1VkZkeWd3diwyIipSNVNabV9WZ0NrRCZ6bzohUWhWJ3luLjNIRjBzUnN1MWFxbT5QKikpb0ZaYWxoaCVbXG1pd0syazVXaSpbJUcpSCxGLFssUkwlekUsUlt0cVlbYDVtJCk+TzNzKjRDZGpYaCoqRylvbEtZJSpbXWchZV0nKio=

> > # # In the `easy` case no more further effort done. # > > ifactor/easy=proc(n) > options `Copyright 1993 by Waterloo Maple Software`; > _c.(length(n)) > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSVlYXN5R0YoISIiZio2I0kibkdGKEYoNiNJSkNvcHlyaWdodH4xOTkzfmJ5fldhdGVybG9vfk1hcGxlflNvZnR3YXJlR0YoRigtSSIuR0YoNiRJI19jR0YoLUknbGVuZ3RoR0YmRi1GKEYoRig=

> # # This is the default procedure for # factorization of complicated cases. # It use a variation of the Morrison--Brillhard # algorithm with continued fractions (??). # > > ifactor/morrbril=proc(n) > local i,j,A0,A1,Q0,Q1,PQ,iPQ,iPQc,g,r0,r1,qn,p,X,primes; > global _sq,_X2,_XX2,_Nprimes4,_Heap4,_Prpri; > options `Copyright 1993 by Waterloo Maple Software`; > _sq := '_sq'; > PQ := []; > iPQ := 1; > iPQc := 1; > userinfo(1,ifactor,`ifactor final stage:`,n, > lprint(`Using a variation of the Morrison-Brillhart algorithm`)); > g := isqrt(n); > if n < g^2 then g := g-1 fi; > X := isqrt(isqrt(isqrt(isqrt(10^(isqrt(iquo(599*length(n),4))-11))))); > _X2 := min(X^2,20*X); > _XX2 := X*_X2; > userinfo(9,ifactor,'n' = n,'X' = X,'_X2' = _X2); > primes[1] := 2; > for _Nprimes4 while primes[_Nprimes4] < X do > primes[_Nprimes4]; > do nextprime(%); if modp(power(n,1/2*%-1/2),%) = 1 then break fi od; > primes[_Nprimes4+1] := % > od; > p := 1; > while p <= _Nprimes4 do p := 2*p od; > p := p-1; > for i from _Nprimes4-1 by -1 to 0 do > 1; > j := 2*i+1; > while j < _Nprimes4 do %%*_Heap4[j]; j := 2*j od; > if p < j then primes[j-p] else primes[j-p+_Nprimes4] fi; > _Heap4[i] := %%%*% > od; > _Prpri := 1440*_Heap4[0]; > A0 := 0; > A1 := 1; > Q1 := n; > Q0 := 1; > r1 := g; > do > qn := iquo(2*g-r1,Q0,'r0'); > A0 := modp(qn*A1+A0,n); > Q1 := Q1+qn*(r0-r1); > if [qn,A0,r1] = PQ then RETURN(readlib(`ifactor/pollard`)(n)) > elif iPQc = iPQ then iPQ := 2*iPQ; PQ := [qn,A0,r1]; iPQc := 1 > else iPQc := iPQc+1 > fi; > analyze_resid(A0,-Q1,n); > if % <> FAIL then RETURN(%) fi; > qn := iquo(2*g-r0,Q1,'r1'); > A1 := modp(qn*A0+A1,n); > Q0 := Q0+qn*(r1-r0); > analyze_resid(A1,Q0,n); > if % <> FAIL then RETURN(%) fi > od > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSltb3JyYnJpbEdGKCEiImYqNiNJIm5HRig2MkkiaUdGKEkiakdGKEkjQTBHRihJI0ExR0YoSSNRMEdGKEkjUTFHRihJI1BRR0YoSSRpUFFHRihJJWlQUWNHRihJImdHRihJI3IwR0YoSSNyMUdGKEkjcW5HRihJInBHRihJIlhHRihJJ3ByaW1lc0dGKDYjSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQzo+SSRfc3FHRiguRkQ+RjY3Ij5GN0YpPkY4RiktSSl1c2VyaW5mb0dGJjYnRilGJEk1aWZhY3Rvcn5maW5hbH5zdGFnZTpHRihGLi1JJ2xwcmludEdGJjYjSVZVc2luZ35hfnZhcmlhdGlvbn5vZn50aGV+TW9ycmlzb24tQnJpbGxoYXJ0fmFsZ29yaXRobUdGKD5GOS1JJmlzcXJ0R0YmRi1AJDJGLiokKUY5IiIjRik+RjksJkY5RilGKUYrPkY+LUZUNiMtRlQ2Iy1GVDYjLUZUNiMpIiM1LCYtRlQ2Iy1JJWlxdW9HRiY2JCwkKiYiJCpmRiktSSdsZW5ndGhHRiZGLUYpRikiIiVGKSIjNkYrPkkkX1gyR0YoLUkkbWluR0YmNiQqJClGPkZZRiksJComIiM/RilGPkYpRik+SSVfWFgyR0YoKiZGPkYpRl9wRiktRks2JyIiKkYkLy5GLkYuLy5GPkY+Ly5GX3BGX3A+JkY/NiNGKUZZPyhJKl9OcHJpbWVzNEdGKEYpRilGKDImRj82I0ZocUY+QyVGanE/KEYoRilGKUYoSSV0cnVlR0YmQyQtSSpuZXh0cHJpbWVHRig2I0kiJUdGKEAkLy1JJW1vZHBHRiY2JC1JJnBvd2VyR0YoNiRGLiwmKiYjRilGWUYpRmNyRilGKUZec0YrRmNyRilbPiZGPzYjLCZGaHFGKUYpRilGY3I+Rj1GKT8oRihGKUYpRigxRj1GaHE+Rj0sJComRllGKUY9RilGKT5GPSwmRj1GKUYpRis/KEYwLCZGaHFGKUYpRitGKyIiIUZeckMnRik+RjEsJiomRllGKUYwRilGKUYpRik/KEYoRilGKUYoMkYxRmhxQyQqJkkjJSVHRihGKSZJJ19IZWFwNEdGKDYjRjFGKT5GMSwkKiZGWUYpRjFGKUYpQCUyRj1GMSZGPzYjLCZGMUYpRj1GKyZGPzYjLChGMUYpRj1GK0ZocUYpPiZGaXQ2I0YwKiZJJCUlJUdGKEYpRmNyRik+SSdfUHJwcmlHRigsJComIiVTOUYpJkZpdDYjRl50RilGKT5GMkZedD5GM0YpPkY1Ri4+RjRGKT5GO0Y5PyhGKEYpRilGKEZeckMtPkY8LUZlbzYlLCYqJkZZRilGOUYpRilGO0YrRjQuRjo+RjItRmdyNiQsJiomRjxGKUYzRilGKUYyRilGLj5GNSwmRjVGKSomRjxGKSwmRjpGKUY7RitGKUYpQCcvNyVGPEYyRjtGNi1JJ1JFVFVSTkdGJjYjLS1JKHJlYWRsaWJHRiY2I0kwaWZhY3Rvci9wb2xsYXJkR0YoRi0vRjhGN0MlPkY3LCQqJkZZRilGN0YpRik+RjZGandGST5GOCwmRjhGKUYpRiktSS5hbmFseXplX3Jlc2lkR0YoNiVGMiwkRjVGK0YuQCQwRmNySSVGQUlMR0YmLUZceEZicj5GPC1GZW82JSwmRl13RilGOkYrRjUuRjs+RjMtRmdyNiQsJiomRjxGKUYyRilGKUYzRilGLj5GNCwmRjRGKSomRjxGKSwmRjtGKUY6RitGKUYpLUZceTYlRjNGNEYuRl95Rig2KEZERl9wRmlwRmhxRml0Rlx2Rig=

> > # # This subroutine works for the Morrison--Brillhard # algorithm. # > > analyze_resid=proc(a,a2,n) > local lrgpr,resid,base,g; > global _sq; > options `Copyright 1993 by Waterloo Maple Software`; > abs(a2); > igcd(%,_Prpri); > while % <> 1 do > iquo(%%,%); if _XX2 < % then RETURN(FAIL) fi; igcd(%,%%) > od; > if _X2 < %% then RETURN(FAIL) fi; > lrgpr := %%; > base := a; > resid := a2; > do > igcd(resid,_Heap4[0]); > g := igcd(iquo(resid,%),%); > while g <> 1 do > resid := iquo(resid,g^2); > base := modp(base/g,n); > igcd(g,resid); > g := igcd(%,iquo(resid,%)) > od; > if resid = 1 then > if base <> 1 and base <> n-1 then RETURN(igcd(base-1,n)) > else userinfo(9,ifactor,`Bad luck (+-1)^2=1`); RETURN(FAIL) > fi > fi; > if lrgpr = 1 then lrgpr := lrgst_factor(resid) fi; > userinfo(9,ifactor,`*** factorable residue ***`,base,resid,lrgpr); > if assigned(_sq[lrgpr]) then > userinfo(9,ifactor,`----- collision at`,lrgpr); > resid := resid*_sq[lrgpr][2]/lrgpr^2; > base := modp(base*_sq[lrgpr][1]/lrgpr,n); > lrgpr := 1 > else _sq[lrgpr] := [base,resid]; RETURN(FAIL) > fi > od > end;

L0kuYW5hbHl6ZV9yZXNpZEc2ImYqNiVJImFHRiRJI2EyR0YkSSJuR0YkNiZJJmxyZ3ByR0YkSSZyZXNpZEdGJEklYmFzZUdGJEkiZ0dGJDYjSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGJEYkQyotSSRhYnNHJSpwcm90ZWN0ZWRHNiNGKC1JJWlnY2RHRjQ2JEkiJUdGJEknX1BycHJpR0YkPyhGJCIiIkY8RiQwRjlGPEMlLUklaXF1b0dGNDYkSSMlJUdGJEY5QCQySSVfWFgyR0YkRjktSSdSRVRVUk5HRjQ2I0klRkFJTEdGNC1GNzYkRjlGQkAkMkkkX1gyR0YkRkJGRj5GK0ZCPkYtRic+RixGKD8oRiRGPEY8RiRJJXRydWVHRjRDKS1GNzYkRiwmSSdfSGVhcDRHRiQ2IyIiIT5GLi1GNzYkLUZANiRGLEY5Rjk/KEYkRjxGPEYkMEYuRjxDJj5GLC1GQDYkRiwqJClGLiIiI0Y8PkYtLUklbW9kcEdGNDYkKiZGLUY8Ri4hIiJGKS1GNzYkRi5GLD5GLi1GNzYkRjlGaG5AJC9GLEY8QCUzMEYtRjwwRi0sJkYpRjxGPEZoby1GRzYjLUY3NiQsJkYtRjxGPEZob0YpQyQtSSl1c2VyaW5mb0dGNDYlIiIqSShpZmFjdG9yRzYkRjRJKF9zeXNsaWJHRiRJM0JhZH5sdWNrfigrLTEpXjI9MUdGJEZGQCQvRitGPD5GKy1JLWxyZ3N0X2ZhY3RvckdGJDYjRiwtRlxxNihGXnFGX3FJOyoqKn5mYWN0b3JhYmxlfnJlc2lkdWV+KioqR0YkRi1GLEYrQCUtSSlhc3NpZ25lZEdGNDYjJkkkX3NxR0YkNiNGK0MmLUZccTYmRl5xRl9xSTMtLS0tLX5jb2xsaXNpb25+YXRHRiRGKz5GLCooRixGPCZGYHI2I0Zib0Y8KUYrRmJvRmhvPkYtLUZlbzYkKihGLUY8JkZgcjYjRjxGPEYrRmhvRik+RitGPEMkPkZgcjckRi1GLEZGRiQ2I0ZhckYk

> > # # This is D. Shanks' undocumented square-free factorization. # > > ifactor/squfof=proc(a) > local l,p,q,r,s,w; > options `Copyright 1993 by Waterloo Maple Software`; > p := isqrt(a); > if a < p^2 then p := p-1 fi; > q := a-p^2; > s := p; > if q = 0 then RETURN(p) elif q = 1 then RETURN(squfof(2*a)) fi; > l := 2*isqrt(2*s); > do > if q <= l then w[q/igcd(q,2)] := 1 fi; > p := s-modp(s+p,q); > q := (a-p^2)/q; > r := isqrt(q); > if q = r^2 and w[r] <> 1 then break fi; > if q <= l then w[q/igcd(q,2)] := 1 fi; > p := s-modp(s+p,q); > q := (a-p^2)/q > od; > p := p+r*iquo(s-p,r); > q := (a-p^2)/r; > do > s-modp(s+%%,%); if % = %%% then RETURN(%%/igcd(%%,2)) fi; (a-%^2)/%% > od > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSSdzcXVmb2ZHRighIiJmKjYjSSJhR0YoNihJImxHRihJInBHRihJInFHRihJInJHRihJInNHRihJIndHRig2I0lKQ29weXJpZ2h0fjE5OTN+Ynl+V2F0ZXJsb29+TWFwbGV+U29mdHdhcmVHRihGKEMsPkYxLUkmaXNxcnRHRiZGLUAkMkYuKiQpRjEiIiNGKT5GMSwmRjFGKUYpRis+RjIsJkYuRilGPkYrPkY0RjFAJi9GMiIiIS1JJ1JFVFVSTkdGJjYjRjEvRjJGKS1GSjYjLUYqNiMsJComRkBGKUYuRilGKT5GMCwkKiZGQEYpLUY7NiMsJComRkBGKUY0RilGKUYpRik/KEYoRilGKUYoSSV0cnVlR0YmQypAJDFGMkYwPiZGNTYjKiZGMkYpLUklaWdjZEdGJjYkRjJGQEYrRik+RjEsJkY0RiktSSVtb2RwR0YmNiQsJkY0RilGMUYpRjJGKz5GMiomRkRGKUYyRis+RjMtRjs2I0YyQCQzL0YyKiQpRjNGQEYpMCZGNTYjRjNGKVtGZ25GYG9GZm8+RjEsJkYxRikqJkYzRiktSSVpcXVvR0YmNiQsJkY0RilGMUYrRjNGKUYpPkYyKiZGREYpRjNGKz8oRihGKUYpRihGZW5DJSwmRjRGKS1GY282JCwmRjRGKUkjJSVHRihGKUkiJUdGKEYrQCQvRmRxSSQlJSVHRigtRko2IyomRmNxRiktRl5vNiRGY3FGQEYrKiYsJkYuRikqJClGZHFGQEYpRitGKUZjcUYrRihGKEYo

> > # # This is J. M. Pollard's rho method. # > > ifactor/pollard=proc(n,ex) > local EX; > options `Copyright 1993 by Waterloo Maple Software`; > if nargs = 1 then EX := 2 > elif nargs <> 2 or not type(ex,integer) or ex < 2 then > ERROR(`invalid arguments`) > else EX := ex > fi; > 2; > modp(power(%,EX)+1,n); > do > modp(power(%%,EX)+1,n); > modp(power(power(%%,EX)+1,EX)+1,n); > if 1 < igcd(%%-%,n) then > igcd(%%-%,n); if % = n then RETURN(FAIL) else RETURN(%) fi > fi > od; > FAIL > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSShwb2xsYXJkR0YoISIiZio2JEkibkdGKEkjZXhHRig2I0kjRVhHRig2I0lKQ29weXJpZ2h0fjE5OTN+Ynl+V2F0ZXJsb29+TWFwbGV+U29mdHdhcmVHRihGKEMnQCcvJSZuYXJnc0dGKT5GMSIiIzU1MEY3Rjk0LUkldHlwZUdGJjYkRi9JKGludGVnZXJHRiYyRi9GOS1JJkVSUk9SR0YmNiNJMmludmFsaWR+YXJndW1lbnRzR0YoPkYxRi9GOS1JJW1vZHBHRiY2JCwmLUkmcG93ZXJHRig2JEkiJUdGKEYxRilGKUYpRi4/KEYoRilGKUYoSSV0cnVlR0YmQyUtRkk2JCwmLUZNNiRJIyUlR0YoRjFGKUYpRilGLi1GSTYkLCYtRk02JEZVRjFGKUYpRilGLkAkMkYpLUklaWdjZEdGJjYkLCZGWEYpRk9GK0YuQyRGam5AJS9GT0YuLUknUkVUVVJOR0YmNiNJJUZBSUxHRiYtRmJvNiNGT0Zkb0YoRihGKA==

> > # # This is Lenstra's elliptic curve method. # > > ifactor/lenstra=proc(n) > local i,s,prime,f,A,X,Z,rgen,sp,a,r,curves,B1,kg,kgg; > options `Copyright 1993 by Waterloo Maple Software`; > if nargs < 1 or 3 < nargs then ERROR(`wrong number of arguments.`) fi; > if nargs < 3 then B1 := 1000000 else B1 := args[3] fi; > if nargs < 2 then curves := 30 else curves := args[2] fi; > if modp(n,2) = 0 then RETURN(2) fi; > if modp(n,3) = 0 then RETURN(3) fi; > s := evalf(1/2*sqrt(5)-1/2,30); > A := array(1 .. curves); > X := array(1 .. curves); > Z := array(1 .. curves,[1 $ curves]); > rgen := rand(1 .. n-1); > for i to curves do > a := 0; > while modp(a*(a^2-1)*(9*a^2-1),n) = 0 do > r := rgen(); > kg := r^2+6; > kgg := igcd(kg,n); > if kgg <> 1 then RETURN(kgg) fi; > a := modp(6*r/kg,n) > od; > A[i] := modp(1/16*(-3*a^4-6*a^2+1)/a^3+1/2,n); > X[i] := modp(3/4*a,n) > od; > prime := 2; > while prime <= B1 do > sp := round(s*prime); > `ifactor/lenstra/mulpp`(1,n,A,sp,prime,B1,X,Z); > f := Z[1]; > for i from 2 to curves do > `ifactor/lenstra/mulpp`(i,n,A,sp,prime,B1,X,Z); > f := modp(f*Z[i],n) > od; > f := igcd(f,n); > if f <> 1 then RETURN(f) fi; > prime := nextprime(prime) > od; > FAIL > end;

LyomSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSShsZW5zdHJhR0YoISIiZio2I0kibkdGKDYxSSJpR0YoSSJzR0YoSSZwcmltZUdGKEkiZkdGKEkiQUdGKEkiWEdGKEkiWkdGKEklcmdlbkdGKEkjc3BHRihJImFHRihJInJHRihJJ2N1cnZlc0dGKEkjQjFHRihJI2tnR0YoSSRrZ2dHRig2I0lKQ29weXJpZ2h0fjE5OTN+Ynl+V2F0ZXJsb29+TWFwbGV+U29mdHdhcmVHRihGKEMwQCQ1MiUmbmFyZ3NHRikyIiIkRkUtSSZFUlJPUkdGJjYjSTt3cm9uZ35udW1iZXJ+b2Z+YXJndW1lbnRzLkdGKEAlMkZFRkc+RjwiKCsrKyI+RjwmJSVhcmdzRzYjRkdAJTJGRSIiIz5GOyIjST5GOyZGUjYjRlZAJC8tSSVtb2RwR0YmNiRGLkZWIiIhLUknUkVUVVJOR0YmRmVuQCQvLUZpbjYkRi5GR0Zbby1GXW9GUz5GMS1JJmV2YWxmR0YmNiQsJiomI0YpRlZGKS1JJXNxcnRHRig2IyIiJkYpRilGaW9GK0ZYPkY0LUkmYXJyYXlHRiY2IztGKUY7PkY1Rl9wPkY2LUZgcDYkRmJwNyMtSSIkR0YmNiRGKUY7PkY3LUklcmFuZEdGKDYjO0YpLCZGLkYpRilGKz8oRjBGKUYpRjtJJXRydWVHRiZDJj5GOUZbbz8oRihGKUYpRigvLUZpbjYkKihGOUYpLCYqJClGOUZWRilGKUYpRitGKSwmKiYiIipGKUZcckYpRilGKUYrRilGLkZbb0MnPkY6LUY3Rig+Rj0sJiokKUY6RlZGKUYpIiInRik+Rj4tSSVpZ2NkR0YmNiRGPUYuQCQwRj5GKS1GXW82I0Y+PkY5LUZpbjYkLCQqKEZnckYpRjpGKUY9RitGKUYuPiZGNDYjRjAtRmluNiQsJiooI0YpIiM7RiksKComRkdGKSlGOSIiJUYpRisqJkZnckYpRlxyRilGK0YpRilGKSlGOUZHRitGKUZpb0YpRi4+JkY1RmdzLUZpbjYkLCQqJiNGR0ZhdEYpRjlGKUYpRi4+RjJGVj8oRihGKUYpRigxRjJGPEMpPkY4LUkmcm91bmRHRig2IyomRjFGKUYyRiktSTZpZmFjdG9yL2xlbnN0cmEvbXVscHBHRig2KkYpRi5GNEY4RjJGPEY1RjY+RjMmRjY2I0YpPyhGMEZWRilGO0ZicUMkLUZldTYqRjBGLkY0RjhGMkY8RjVGNj5GMy1GaW42JComRjNGKSZGNkZnc0YpRi4+RjMtRmpyNiRGM0YuQCQwRjNGKS1GXW82I0YzPkYyLUkqbmV4dHByaW1lR0YoNiNGMkklRkFJTEdGJkYoRihGKA==

> > # # This subroutine the multiplications on a given # elliptic curve. # > > ifactor/lenstra/mulpp=proc(i,n,A,mm,nn,B1,X,Z) > local pow,ax,az; > options `Copyright 1993 by Waterloo Maple Software`; > ax := X[i]; > az := Z[i]; > pow := nn; > while pow <= B1 do > `ifactor/lenstra/ellmul`(n,A[i],mm,nn,ax,az,'ax','az'); pow := pow*nn > od; > X[i] := ax; > Z[i] := az > end;

LyooSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSShsZW5zdHJhR0YoISIiSSZtdWxwcEdGKEYrZio2KkkiaUdGKEkibkdGKEkiQUdGKEkjbW1HRihJI25uR0YoSSNCMUdGKEkiWEdGKEkiWkdGKDYlSSRwb3dHRihJI2F4R0YoSSNhekdGKDYjSUpDb3B5cmlnaHR+MTk5M35ieX5XYXRlcmxvb35NYXBsZX5Tb2Z0d2FyZUdGKEYoQyg+RjkmRjU2I0YvPkY6JkY2RkA+RjhGMz8oRihGKUYpRigxRjhGNEMkLUk3aWZhY3Rvci9sZW5zdHJhL2VsbG11bEdGKDYqRjAmRjFGQEYyRjNGOUY6LkY5LkY6PkY4KiZGOEYpRjNGKT5GP0Y5PkZCRjpGKEYoRig=

> > # # This procedure do some multiplications # on an elliptic curve. # > > ifactor/lenstra/ellmul=proc(n,A,mm,nn,px,pz,aax,aaz) > local ax,az,bx,bz,cx,cz,tmpx,tmpz,d,e,t1,t2; > options `Copyright 1993 by Waterloo Maple Software`; > cx := px; > cz := pz; > e := mm; > d := nn-mm; > if e < d then > `ifactor/lenstra/elldoub`(n,A,px,pz,'bx','bz'); > ax := px; > az := pz; > d := d-e > else > `ifactor/lenstra/elldoub`(n,A,px,pz,'ax','az'); > bx := px; > bz := pz; > e := e-d > fi; > while e <> 0 do > if e < d then > tmpx := bx; > tmpz := bz; > t1 := modp((ax-az)*(bx+bz),n); > t2 := modp((ax+az)*(bx-bz),n); > bx := modp(cz*modp((t1+t2)^2,n),n); > bz := modp(cx*modp((t1-t2)^2,n),n); > d := d-e > else > tmpx := ax; > tmpz := az; > t1 := modp((ax-az)*(bx+bz),n); > t2 := modp((ax+az)*(bx-bz),n); > ax := modp(cz*modp((t1+t2)^2,n),n); > az := modp(cx*modp((t1-t2)^2,n),n); > e := e-d > fi; > cx := tmpx; > cz := tmpz > od; > aax := ax; > aaz := az > end;

LyooSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSShsZW5zdHJhR0YoISIiSSdlbGxtdWxHRihGK2YqNipJIm5HRihJIkFHRihJI21tR0YoSSNubkdGKEkjcHhHRihJI3B6R0YoSSRhYXhHRihJJGFhekdGKDYuSSNheEdGKEkjYXpHRihJI2J4R0YoSSNiekdGKEkjY3hHRihJI2N6R0YoSSV0bXB4R0YoSSV0bXB6R0YoSSJkR0YoSSJlR0YoSSN0MUdGKEkjdDJHRig2I0lKQ29weXJpZ2h0fjE5OTN+Ynl+V2F0ZXJsb29+TWFwbGV+U29mdHdhcmVHRihGKEMqPkY8RjM+Rj1GND5GQUYxPkZALCZGMkYpRjFGK0AlMkZBRkBDJi1JOGlmYWN0b3IvbGVuc3RyYS9lbGxkb3ViR0YoNihGL0YwRjNGNC5GOi5GOz5GOEYzPkY5RjQ+RkAsJkZARilGQUYrQyYtRlA2KEYvRjBGM0Y0LkY4LkY5PkY6RjM+RjtGND5GQSwmRkFGKUZARis/KEYoRilGKUYoMEZBIiIhQyVAJUZNQyk+Rj5GOj5GP0Y7PkZCLUklbW9kcEdGJjYkKiYsJkY4RilGOUYrRiksJkY6RilGO0YpRilGLz5GQy1GZW82JComLCZGOEYpRjlGKUYpLCZGOkYpRjtGK0YpRi8+RjotRmVvNiQqJkY9RiktRmVvNiQqJCksJkZCRilGQ0YpIiIjRilGL0YpRi8+RjstRmVvNiQqJkY8RiktRmVvNiQqJCksJkZCRilGQ0YrRmlwRilGL0YpRi9GVkMpPkY+Rjg+Rj9GOUZjb0Zqbz5GOEZhcD5GOUZbcUZpbj5GPEY+PkY9Rj8+RjVGOD5GNkY5RihGKEYo

> > # # This procedure do a doubling on the elliptic curve. # > > ifactor/lenstra/elldoub=proc(n,A,ax,az,cx,cz) > local t1,t2; > options `Copyright 1993 by Waterloo Maple Software`; > t1 := modp((ax+az)^2,n); > t2 := modp((ax-az)^2,n); > cx := modp(t1*t2,n); > cz := modp((t1-t2)*modp(A*(t1-t2)+t2,n),n) > end;

LyooSShpZmFjdG9yRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiIiIiSShsZW5zdHJhR0YoISIiSShlbGxkb3ViR0YoRitmKjYoSSJuR0YoSSJBR0YoSSNheEdGKEkjYXpHRihJI2N4R0YoSSNjekdGKDYkSSN0MUdGKEkjdDJHRig2I0lKQ29weXJpZ2h0fjE5OTN+Ynl+V2F0ZXJsb29+TWFwbGV+U29mdHdhcmVHRihGKEMmPkY2LUklbW9kcEdGJjYkKiQpLCZGMUYpRjJGKSIiI0YpRi8+RjctRj02JCokKSwmRjFGKUYyRitGQkYpRi8+RjMtRj02JComRjZGKUY3RilGLz5GNC1GPTYkKiYsJkY2RilGN0YrRiktRj02JCwmKiZGMEYpRlFGKUYpRjdGKUYvRilGL0YoRihGKA==

> > >

# # This procedure prepare the sieve table S for # Fermat's factorization procedure. Parameter n is the # integer to factor and m is the vector of moduli. # preparefermatsieve:=proc(n,S,m) local i,j,k,x2,x2n; x2:=table; x2n:=table; for i to nops(m) do for j from 0 to m[i]-1 do S[i,j]:=0; od; for j from 0 to m[i]-1 do x2[j]:=j^2 mod m[i]; x2n[j]:=j^2-n mod m[i]; od; for j from 0 to m[i]-1 do for k from 0 to m[i]-1 do if x2n[j]=x2[k] then S[i,j]:=1 fi; od; od; od; end;

Zio2JUkibkc2IkkiU0dGJUkibUdGJTYnSSJpR0YlSSJqR0YlSSJrR0YlSSN4MkdGJUkkeDJuR0YlRiVGJUMlPkYsSSZ0YWJsZUclKnByb3RlY3RlZEc+Ri1GMD8oRikiIiJGNC1JJW5vcHNHRjE2I0YnSSV0cnVlR0YxQyU/KEYqIiIhRjQsJiZGJzYjRilGNEY0ISIiRjg+JkYmNiRGKUYqRjs/KEYqRjtGNEY8RjhDJD4mRiw2I0YqLUkkbW9kR0YlNiQqJClGKiIiI0Y0Rj0+JkYtRkctRkk2JCwmRktGNEYkRj9GPT8oRipGO0Y0RjxGOD8oRitGO0Y0RjxGOEAkL0ZPJkYsNiNGKz5GQUY0RiVGJUYl

# # This procedure do factorization with # Fermat's method. Parameter n is # the odd number to factor and m is the list of moduli. # Returns with u where u is the largest # factor of n less then or equal to sqrt(n). # fermatfactorization:=proc(n::posint,m::list(posint)) local k,x,y,i,S,r,f; if type(n,even) then error "first argument must be odd" fi; S:=table(); preparefermatsieve(n,S,m); r:=nops(m); k:=array(1..r); x:=isqrt(n); for i to r do k[i]:=-x mod m[i]; od; while true do f:=true; for i to r do if S[i,k[i]]<>1 then f:=false; break; fi; od; if f then y:=isqrt(x^2-n); if y^2=x^2-n then RETURN(x-y) fi; fi; x:=x+1; for i to r do k[i]:=k[i]-1 mod m[i]; od; od; end;

Zio2JCdJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJtR0YmLUklbGlzdEdGKDYjRic2KUkia0dGJkkieEdGJkkieUdGJkkiaUdGJkkiU0dGJkkickdGJkkiZkdGJkYmRiZDKkAkLUkldHlwZUdGKDYkRiVJJWV2ZW5HRihZUTtmaXJzdH5hcmd1bWVudH5tdXN0fmJlfm9kZEYmPkYzLUkmdGFibGVHRihGJi1JM3ByZXBhcmVmZXJtYXRzaWV2ZUdGJjYlRiVGM0YqPkY0LUklbm9wc0dGKDYjRio+Ri8tSSZhcnJheUdGKDYjOyIiIkY0PkYwLUkmaXNxcnRHRig2I0YlPyhGMkZNRk1GNEkldHJ1ZUdGKD4mRi82I0YyLUkkbW9kR0YmNiQsJEYwISIiJkYqRlY/KEYmRk1GTUYmRlNDJz5GNUZTPyhGMkZNRk1GNEZTQCQwJkYzNiRGMkZVRk1DJD5GNUkmZmFsc2VHRihbQCRGNUMkPkYxLUZQNiMsJiokKUYwIiIjRk1GTUYlRmVuQCQvKiQpRjFGW3BGTUZoby1JJ1JFVFVSTkdGKDYjLCZGMEZNRjFGZW4+RjAsJkYwRk1GTUZNPyhGMkZNRk1GNEZTPkZVLUZYNiQsJkZVRk1GTUZlbkZmbkYmRiZGJg==

debug(fermatfactorization); fermatfactorization(13*17,[3,5,7,8,11]);

STRmZXJtYXRmYWN0b3JpemF0aW9uRzYi

{--> enter fermatfactorization, args = 221, [3, 5, 7, 8, 11]

PTYiSSZmYWxzZUclKnByb3RlY3RlZEdFXFtsIQ==

IiIm

PTYiNiM7IiIiIiImRVxbbCE=

IiM6

IiIh

IiIh

IiIn

IiIi

IiIo

SSV0cnVlRyUqcHJvdGVjdGVkRw==

IiIj

<-- exit fermatfactorization (now at top level) = 13}

IiM4

undebug(fermatfactorization); fermatfactorization(11111,[3,5,7,8,11]);

STRmZXJtYXRmYWN0b3JpemF0aW9uRzYi

IiNU

interface(echo=3);

IiIi

# # This procedure do factorization with addition and # substraction. Returns with the largest factor of # odd number n less then or equal to sqrt(n). # addsubfactor:=proc(n) local xp,yp,r; if type(n,even) then error "argument must be odd" fi; isqrt(n); xp:=2*%+1; r:=%%^2-n; yp:=1; while true do while r>0 do r:=r-yp; yp:=yp+2 od; if r=0 then return (xp-yp)/2 fi; r:=r+xp; xp:=xp+2; od; end;

Zio2I0kibkc2IjYlSSN4cEdGJUkjeXBHRiVJInJHRiVGJUYlQyhAJC1JJXR5cGVHJSpwcm90ZWN0ZWRHNiRGJEklZXZlbkdGLllRNWFyZ3VtZW50fm11c3R+YmV+b2RkRiUtSSZpc3FydEdGLkYjPkYnLCYqJiIiIyIiIkkiJUdGJUY5RjlGOUY5PkYpLCYqJClJIyUlR0YlRjhGOUY5RiQhIiI+RihGOT8oRiVGOUY5RiVJJXRydWVHRi5DJj8oRiVGOUY5RiUyIiIhRilDJD5GKSwmRilGOUYoRkA+RigsJkYoRjlGOEY5QCQvRilGR08sJiomI0Y5RjhGOUYnRjlGOSomRlJGOUYoRjlGQD5GKSwmRilGOUYnRjk+RicsJkYnRjlGOEY5RiVGJUYl

debug(addsubfactor); addsubfactor(111);

SS1hZGRzdWJmYWN0b3JHNiI=

{--> enter addsubfactor, args = 111

IiM2

IiNC

IiM1

IiIi

IiIq

IiIk

IiIn

IiIm

IiIi

IiIo

ISIn

IiIq

IiM8

IiNE

IiIp

IiM2

ISIk

IiM4

IiNB

IiNG

IiIq

IiM6

ISIn

IiM8

IiNA

IiNI

IiIl

IiM+

ISM6

IiNA

IiM5

IiNK

ISIo

IiNC

IiND

IiNM

IiIi

IiNE

ISND

IiNG

IiIq

IiNO

ISM9

IiNI

IiM8

IiNQ

ISM3

IiNK

IiNE

IiNS

ISIn

IiNM

IiNM

IiNU

IiIh

IiNO

<-- exit addsubfactor (now at top level) = 3}

IiIk

undebug(addsubfactor); addsubfactor(6463); addsubfactor(999863*999883);

IiNC

IidqKSoqKg==

Az n sz\303\241m has\303\255t\303\241sa az x->x^2+c f\303\274ggv\303\251ny felhaszn\303\241l\303\241s\303\241val; g egy iter\303\241ci\303\263csoport m\303\251rete \303\251s legfeljebb maxgs csoport fog v\303\251grehajt\303\263dni. pollardrhosplit:=proc(n::posint,c::posint,g::posint,maxgs::posint) local x,xx,xp,xo,xpo,i,j,k,ko,l,lo; x:=1+c mod n; xp:=1; i:=0; k:=1; l:=1; xx:=1; while igcd(xx,n)=1 and i<maxgs do xo:=x; xpo:=xp; ko:=k; lo:=l; j:=0; xx:=1; while j<g do xx:=xx*(xp-x) mod n; k:=k-1; if k=0 then xp:=x; k:=l; l:=2*l; fi; x:=x^2+c mod n; j:=j+1; od; i:=i+1; od; if igcd(xx,n)<n then return(igcd(xx,n)) fi; x:=xo; xp:=xpo; k:=ko; l:=lo; j:=0; while igcd(xp-x,n)=1 and j<g do k:=k-1; if k=0 then xp:=x; k:=l; l:=2*l; fi; x:=x^2+c mod n; j:=j+1; od; igcd(xp-x,n); end;

Zio2JidJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJjR0YmRicnSSJnR0YmRicnSSZtYXhnc0dGJkYnNi1JInhHRiZJI3h4R0YmSSN4cEdGJkkjeG9HRiZJJHhwb0dGJkkiaUdGJkkiakdGJkkia0dGJkkja29HRiZJImxHRiZJI2xvR0YmRiZGJkMxPkYwLUkkbW9kR0YmNiQsJiIiIkZBRipGQUYlPkYyRkE+RjUiIiE+RjdGQT5GOUZBPkYxRkE/KEYmRkFGQUYmMy8tSSVpZ2NkR0YoNiRGMUYlRkEyRjVGLkMqPkYzRjA+RjRGMj5GOEY3PkY6Rjk+RjZGREZHPyhGJkZBRkFGJjJGNkYsQyc+RjEtRj42JComRjFGQSwmRjJGQUYwISIiRkFGJT5GNywmRjdGQUZBRmduQCQvRjdGREMlPkYyRjA+RjdGOT5GOSwkKiYiIiNGQUY5RkFGQT5GMC1GPjYkLCYqJClGMEZib0ZBRkFGKkZBRiU+RjYsJkY2RkFGQUZBPkY1LCZGNUZBRkFGQUAkMkZLRiVPRks+RjBGMz5GMkY0PkY3Rjg+RjlGOkZUPyhGJkZBRkFGJjMvLUZMNiRGZm5GJUZBRlZDJkZobkZqbkZjb0Zpb0ZncEYmRiZGJg==

pollardrhosplit(999863*999883,1,2^4,2^5);

IidqKSoqKg==

chrem([1,2,2],[2,3,7]);

IiNC

# # Calculation of modular power of a # with the left-to-right binary method. # left2right:=proc(a,e::posint,mult::procedure) local b,x,n; b:=convert(e,base,2); x:=a; for n from nops(b)-1 by -1 to 1 do x:=mult(x,x); if b[n]>0 then x:=mult(x,a); fi; od; x; end;

Zio2JUkiYUc2IidJImVHRiVJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSVtdWx0R0YlSSpwcm9jZWR1cmVHRik2JUkiYkdGJUkieEdGJUkibkdGJUYlRiVDJj5GLi1JKGNvbnZlcnRHRik2JUYnSSViYXNlR0YlIiIjPkYvRiQ/KEYwLCYtSSVub3BzR0YpNiNGLiIiIkY+ISIiRj9GPkkldHJ1ZUdGKUMkPkYvLUYrNiRGL0YvQCQyIiIhJkYuNiNGMD5GLy1GKzYkRi9GJEYvRiVGJUYl

debug(left2right); left2right(2,11,(x,y)->x*y);

SStsZWZ0MnJpZ2h0RzYi

{--> enter left2right, args = 2, 11, proc (x, y) options operator, arrow; x*y end proc

NyYiIiJGIyIiIUYj

IiIj

IiIl

IiM7

IiNL

IiVDNQ==

IiVbPw==

IiVbPw==

<-- exit left2right (now at top level) = 2048}

IiVbPw==

# # Calculation of a modular power # with the left-to-right 2^m-ary method. # fastexp:=proc(a,e::posint,m::posint,mult::procedure) local i,j,k,P,x,b,aa,n; b:=convert(e,base,2); n:=nops(b)-1; x:=a; P:=[a]; aa:=mult(a,a); for j from 2 to 2^(m-1) do P:=[op(P),mult(P[nops(P)],aa)]; od; while true do if n=0 then return(x) fi; if b[n]=0 then x:=mult(x,x); n:=n-1; next; fi; i:=1; j:=1; k:=0; x:=mult(x,x); n:=n-1; while n>0 and k+j<m do if b[n]=0 then k:=k+1; n:=n-1; else k:=k+1; j:=j+k; i:=i*2^k; while k>0 do x:=mult(x,x); k:=k-1; od; n:=n-1; fi; od; x:=mult(x,P[i]); while k>0 do x:=mult(x,x); k:=k-1; od; od; end;

Zio2JkkiYUc2IidJImVHRiVJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJtR0YlRignSSVtdWx0R0YlSSpwcm9jZWR1cmVHRik2KkkiaUdGJUkiakdGJUkia0dGJUkiUEdGJUkieEdGJUkiYkdGJUkjYWFHRiVJIm5HRiVGJUYlQyk+RjUtSShjb252ZXJ0R0YpNiVGJ0klYmFzZUdGJSIiIz5GNywmLUklbm9wc0dGKTYjRjUiIiJGRCEiIj5GNEYkPkYzNyNGJD5GNi1GLTYkRiRGJD8oRjFGPkZEKUY+LCZGK0ZERkRGRUkldHJ1ZUdGKT5GMzckLUkjb3BHRik2I0YzLUYtNiQmRjM2Iy1GQkZURjY/KEYlRkRGREYlRk9DLEAkL0Y3IiIhT0Y0QCQvJkY1NiNGN0ZobkMlPkY0LUYtNiRGNEY0PkY3LCZGN0ZERkRGRVw+RjBGRD5GMUZEPkYyRmhuRl9vRmJvPyhGJUZERkRGJTMyRmhuRjcyLCZGMkZERjFGREYrQCVGW29DJD5GMiwmRjJGREZERkRGYm9DJ0ZfcD5GMUZccD5GMComRjBGRClGPkYyRkQ/KEYlRkRGREYlMkZobkYyQyRGX28+RjIsJkYyRkRGREZFRmJvPkY0LUYtNiRGNCZGMzYjRjBGZnBGJUYlRiU=

debug(fastexp); fastexp(2,11,1,(x,y)->x*y);

SShmYXN0ZXhwRzYi

{--> enter fastexp, args = 2, 11, 1, proc (x, y) options operator, arrow; x*y end proc

NyYiIiJGIyIiIUYj

IiIk

IiIj

NyMiIiM=

IiIl

IiIl

IiIj

IiIi

IiIi

IiIh

IiM7

IiIi

IiNL

IiIi

IiIi

IiIh

IiVDNQ==

IiIh

IiVbPw==

<-- exit fastexp (now at top level) = 2048}

IiVbPw==

debug(fastexp); fastexp(2,11,2,(x,y)->x*y);

SShmYXN0ZXhwRzYi

{--> enter fastexp, args = 2, 11, 2, proc (x, y) options operator, arrow; x*y end proc

NyYiIiJGIyIiIUYj

IiIk

IiIj

NyMiIiM=

IiIl

NyQiIiMiIik=

IiIl

IiIj

IiIi

IiIi

IiIh

IiM7

IiIi

IiIi

IiIj

IiIj

IiRjIw==

IiIh

IiIh

IiVbPw==

<-- exit fastexp (now at top level) = 2048}

IiVbPw==

# # This procedure is Pollard's p-1 method for # factorization. The base is a, and powers of # primes up to P are considered so that they # are not less then the bound B. # The result is the power x of a mod n, where # n isthe number to factorize, so the factor is gcd(x-1,n). # pollardpsplit:=proc(n,a,B,P) local e,d,p,x; x:=a mod n; if igcd(x-1,n)>1 or P<2 then return(x) fi; if P<2 then return(x) fi; e:=1; while 2^e<B do e:=e+1 od; x:=x&^(2^e) mod n; if igcd(x-1,n)>1 or P=2 then return(x) fi; while 3^e>3*B and e>1 do e:=e-1 od; x:=x&^(3^e) mod n; d:=2; p:=5; while true do if igcd(x-1,n)>1 or P<p then return(x) fi; while p^e>p*B and e>1 do e:=e-1 od; x:=x&^(p^e) mod n; p:=p+d; d:=6-d; od; x; end;

Zio2Jkkibkc2IkkiYUdGJUkiQkdGJUkiUEdGJTYmSSJlR0YlSSJkR0YlSSJwR0YlSSJ4R0YlRiVGJUMvPkYtLUkkbW9kR0YlNiRGJkYkQCQ1MiIiIi1JJWlnY2RHJSpwcm90ZWN0ZWRHNiQsJkYtRjZGNiEiIkYkMkYoIiIjT0YtQCRGPUY/PkYqRjY/KEYlRjZGNkYlMilGPkYqRic+RiosJkYqRjZGNkY2PkYtLUYxNiQtSSMmXkdGJTYkRi1GREYkQCQ1RjUvRihGPkY/PyhGJUY2RjZGJTMyLCQqJiIiJEY2RidGNkY2KUZVRioyRjZGKj5GKiwmRipGNkY2Rjw+Ri0tRjE2JC1GSzYkRi1GVkYkPkYrRj4+RiwiIiY/KEYlRjZGNkYlSSV0cnVlR0Y5QydAJDVGNTJGKEYsRj8/KEYlRjZGNkYlMzIqJkYsRjZGJ0Y2KUYsRipGV0ZYPkYtLUYxNiQtRks2JEYtRmZvRiQ+RiwsJkYsRjZGK0Y2PkYrLCYiIidGNkYrRjxGLUYlRiVGJQ==

pollardpsplit(25852,2,100,100);

IiZDTCM=

igcd(%-1,25852);

IiQiRw==

pollardpsplit(999863*999917*999961,23,2000,1000);

IjI6allRLiJIRDs=

igcd(%-1,999863*999917*999961);

Iic8KioqKg==

# # This procedure is the second step of Pollard's p-1 method for # factorization. The base is a, and primes from list P # are considered. The result is the power x of a mod n, where # n is the number to factorize, so the factor is gcd(x-1,n). # pollardp2split:=proc(n::posint,a::posint,N::posint,m::posint,M::posint) local x,i,j,E,aa,p,pp,d; E:=Array(1..N); aa:=a*a mod n; E[1]:=aa; for j from 2 to N do E[j]:=E[j-1]*aa od; p:=ithprime(m); x:=a&^p mod n; for i from m+1 to M while gcd(x-1,n)=1 do pp:=nextprime(p); d:=pp-p; p:=pp; if d<=2*N then x:=x*E[d/2] mod n; else x:=x*(a&^d) mod n; fi; od; x; end;

Zio2JydJIm5HNiJJJ3Bvc2ludEclKnByb3RlY3RlZEcnSSJhR0YmRicnSSJOR0YmRicnSSJtR0YmRicnSSJNR0YmRic2KkkieEdGJkkiaUdGJkkiakdGJkkiRUdGJkkjYWFHRiZJInBHRiZJI3BwR0YmSSJkR0YmRiZGJkMqPkY1LUkmQXJyYXlHRig2IzsiIiJGLD5GNi1JJG1vZEdGJjYkKiZGKkZARipGQEYlPiZGNTYjRkBGNj8oRjQiIiNGQEYsSSV0cnVlR0YoPiZGNTYjRjQqJiZGNTYjLCZGNEZARkAhIiJGQEY2RkA+RjctSSlpdGhwcmltZUdGJjYjRi4+RjItRkM2JC1JIyZeR0YmNiRGKkY3RiU/KEYzLCZGLkZARkBGQEZARjAvLUkkZ2NkR0YmNiQsJkYyRkBGQEZTRiVGQEMmPkY4LUkqbmV4dHByaW1lR0YmNiNGNz5GOSwmRjhGQEY3RlM+RjdGOEAlMUY5LCQqJkZKRkBGLEZARkA+RjItRkM2JComRjJGQCZGNTYjLCQqJiNGQEZKRkBGOUZARkBGQEYlPkYyLUZDNiQqJkYyRkAtRmZuNiRGKkY5RkBGJUYyRiZGJkYm

pollardpsplit(8174912477117*23528569104401,3,1000,1000);

IjxGKXpyQmB4XzMnKnpYbTk=

igcd(%-1,8174912477117*23528569104401);

IiIi

pollardp2split(8174912477117*23528569104401,%%,100,100,10000);

IjptWUQiZi5XPj5NYDlS

igcd(%-1,8174912477117*23528569104401);

Ii8sVzVwJkdOIw==

ifactor(%-1);

Ki4pLUkhRzYiNiMiIiMiIiUiIiIpLUYlNiMiIiZGKEYqLUYlNiMiI25GKi1GJTYjIiQyIkYqLUYlNiMiJCo+RiotRiU2IyImSjclRio=

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn