Sz\303\241m\303\255t\303\263g\303\251pes sz\303\241melm\303\251let J\303\241rai Antal Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">1. A pr\303\255mek eloszl\303\241sa, szit\303\241l\303\241s</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263dszerek</Font></Text-field> restart; with(numtheory); N1FJJkdJZ2NkRzYiSSliaWdvbWVnYUdGJEkmY2ZyYWNHRiRJKWNmcmFjcG9sR0YkSStjeWNsb3RvbWljR0YkSSlkaXZpc29yc0dGJEkpZmFjdG9yRVFHRiRJKmZhY3RvcnNldEdGJEknZmVybWF0R0YkSSlpbWFndW5pdEdGJEkmaW5kZXhHRiRJL2ludGVncmFsX2Jhc2lzR0YkSSlpbnZjZnJhY0dGJEknaW52cGhpR0YkSSppc3NxcmZyZWVHRiRJJ2phY29iaUdGJEkqa3JvbmVja2VyR0YkSSdsYW1iZGFHRiRJKWxlZ2VuZHJlR0YkSSltY29tYmluZUdGJEkpbWVyc2VubmVHRiRJKG1pZ2NkZXhHRiRJKm1pbmtvd3NraUdGJEkobWlwb2x5c0dGJEklbWxvZ0dGJEknbW9iaXVzR0YkSSZtcm9vdEdGJEkmbXNxcnRHRiRJKW5lYXJlc3RwR0YkSSpudGhjb252ZXJHRiRJKW50aGRlbm9tR0YkSSludGhudW1lckdGJEknbnRocG93R0YkSSZvcmRlckclKnByb3RlY3RlZEdJKXBkZXhwYW5kR0YkSSRwaGlHRiRJI3BpR0YkSSpwcHJpbXJvb3RHRiRJKXByaW1yb290R0YkSShxdWFkcmVzR0YkSStyb290c3VuaXR5R0YkSSpzYWZlcHJpbWVHRiRJJnNpZ21hR0YkSSpzcTJmYWN0b3JHRiRJKHN1bTJzcXJHRiRJJHRhdUdGJEkldGh1ZUdGJA==
<Text-field style="Heading 2" layout="Heading 2">2.1. Pr<Font encoding="UTF-8">\303\263</Font>baoszt<Font encoding="UTF-8">\303\241s</Font>.</Text-field> # # 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=
<Text-field style="Heading 2" layout="Heading 2">2.2. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.3. Feladat.</Text-field> interface(verboseproc=2); IiIi print(ifactor); Zio2I0kibkc2IjYlSSRzb2xHRiVJInJHRiVJI3QxR0YlNiVJKXJlbWVtYmVyR0YlSSdzeXN0ZW1HJSpwcm90ZWN0ZWRHSWFvQ29weXJpZ2h0fihjKX4xOTkxfmJ5fnRoZX5Vbml2ZXJzaXR5fm9mfldhdGVybG9vLn5BbGx+cmlnaHRzfnJlc2VydmVkLkdGJUVccyoiLWVMd3QheioqKC1JIUdGJTYjIiIjIiIiLUYzNiMiJygpSCUpRjYtRjM2IyInPDJlRjYiLVNFbUJ4KSoqNClGMiIiJUY2LUYzNiMiIiRGNi1GMzYjIiImRjYtRjM2IyIjNkY2LUYzNiMiIzhGNi1GMzYjIiM8RjYtRjM2IyIjVEY2LUYzNiMiJGQiRjYtRjM2IyIkaiNGNiItK3dLOXgpKio0Rj9GNilGQUY1RjYpRkRGNUY2LUYzNiMiIihGNkZHRjZGSkY2Rk1GNi1GMzYjIiNCRjYtRjM2IyIkLChGNiItUyczZXIoKSoqMClGMkZpbkY2RmVuRjZGREY2RkdGNilGTUZDRjYtRjM2IyIjPkY2LUYzNiMiJG4iRjYiLl83Ly1OPyIqMilGMkY1RjYpRkFGQEY2KUZnbkY1RjYtRjM2IyIjSEY2LUYzNiMiI0pGNi1GMzYjIiNQRjYtRjM2IyIjVkY2LUYzNiMiI2BGNiIyIUd5bDstXSUqPSo4KUYyRkNGNkZlbkY2RkRGNkZKRjZGUEY2LUYzNiMiI2ZGNi1GMzYjIiNoRjYtRjM2IyIjbkY2LUYzNiMiI3JGNi1GMzYjIiN0RjYtRjM2IyIjekY2Ii1nJEgqNHgpKio0Rj9GNkZBRjZGREY2RmduRjZGR0Y2Rk1GNi1GMzYjIiNaRjYtRjM2IyIkXiJGNi1GMzYjIiRWJUY2Ii0zIW9VOy0qKiZGYHFGNi1GMzYjIi0sTmBxRjZGNiItKys7dXcpKiowRmJvRjZGQUY2KUZERkBGNkZHRjZGTUY2RmFxRjYtRjM2IyIkdCRGNkMqQCYyJSZuYXJnc0dGNllRMmFyZ3VtZW50fnJlcXVpcmVkRiUzMkY2Rlx0NC1JJXR5cGVHRi02JCYlJWFyZ3NHRjQuSSVuYW1lR0YtWVE/c2Vjb25kfmFyZ3VtZW50fm11c3R+YmV+YX5uYW1lRiVALS1GY3Q2JEYkLkkoaW50ZWdlckdGLUAnMiIiIUYkQyQ+RidGNj5GKEYkMkYkRmJ1QyQ+RichIiI+RigsJEYkRml1T0ZidS1GY3Q2JEYkLkkpZnJhY3Rpb25HRi1PKiYtJSlwcm9jbmFtZUc2JC1JI29wR0YtNiRGNkYkJkZmdDYjO0Y1Rml1RjYtRmR2NiQtRmd2NiRGNUYkRml2Rml1LUZjdDYkRiQ8Ji5JIipHRi0uSSVsaXN0R0YtLkkkc2V0R0YtLkkpcmVsYXRpb25HRi1PLUkkbWFwR0YtNiVGZHZGJEZpdjMtRmN0NiRGJEkiXkdGLS1GY3Q2JEZed0ZedU8pRmN2Rl53LUZjdDYkRiQtRjM2I0ZedU9GY3ZZUTJpbnZhbGlkfmFyZ3VtZW50c0YlQCQtSSlhc3NpZ25lZEdGLTYjJkk3aWZhY3Rvci9mcm9tX3NpZ25hdHVyZUdGJTYjRihPRmJ5PkYpLUklaWdjZEdGLTYkRigiJz8ycz8oRiVGNkY2RiUwRilGNkMlPkYnKiZGJ0Y2LUkxaWZhY3Rvci9pZmFjdDIzNUdGJTYjRilGNj5GKC1JJWlxdW9HRi02JEYoRik+RiktRmh5NiRGKUYoPkYpLUZoeTYkRigiaWdtTCM0KCpHXUtLVF8vJm86LTYtXFVMbk82M0svL2EyK0pnMSh5diUpKT0lPjc4Ij5fPSlSQlEjPlZXeXcnRypSJUdcPyRmNyFlQFp6SSgqeXllNTZjInkpKipvKilRTGhxdy0/PSh6dVQlZTw2KWZaQFEqWzIpMyM+d2QnKlw6RygqKXo9XV5WVi5oOU1rdWVMKHohWyQpKipIcTF4X3cnKVJkI1FlVnZhJT5WSiIpKWV6PiEqSGUlXHhQRFJtZi02MCYzT2xXYV1ySHooelgkW1ZxRkA3SHMsQSF6QW5yNic+QyVcJGZ3PnIsY0ciMzErN3NBZFFAQSh6Qz5Yek5sKCo0KVwwYUZjQCoqKXk7dTIoUiYpSFwuLipINyJ5Vi1Wb0VaPklBelElSDM+Iz0leSUpKSpRPz5sPycpZiFwcTFWa3BqKDRSPWNWeFEsJ28xYUssbnBYQlIsV1t0VUEpSCc0LUZoVVBYM3kmKjMoPmInKUdIV3NpVltfLnB0NT1icXlpIT1UUmJVYyM9QFcsUDleSGE7Ij8oRiVGNkY2RiVGXHpDJT5GJyomRidGNi1JMWlmYWN0b3IvaWZhY3Qxc3RHRiVGYnpGNkZjekZnekAlMEYoRjZDJEAlL0ZcdEY2QCUzL0kyX0Vudl9pZmFjdG9yX2Vhc3lHRiVJJXRydWVHRi0yIiNJLUknbGVuZ3RoR0YtRmR5QyQ+SS9pZmFjdG9yL2JvdHRvbUdGJUktaWZhY3Rvci9lYXN5R0YlPkYpLUkxaWZhY3Rvci9pZmFjdDB0aEdGJUZkeUMkPkZkXGxJLmlmYWN0b3IvbWl4ZWRHRiVGZlxsQyQ+RmRcbC1JJGNhdEdGLTYkSSlpZmFjdG9yL0dGJUZldD5GKS1GaFxsNiRGKCZGZnQ2IztGQ0ZcdEAlMEYpSSVGQUlMR0YtKiZGJ0Y2RilGNkZqXWxGJ0YlNiNGZFxsRiU= 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+QWxsfnJpZ2h0c35yZXNlcnZlZC5HRiVFXHMpIiciNHUjKigtSSFHRiU2IyIjPCIiIi1GNTYjIiNCRjgtRjU2IyIkLChGOCIpeGohZSgqLC1GNTYjIiNIRjgtRjU2IyIjSkY4LUY1NiMiI1BGOC1GNTYjIiNWRjgtRjU2IyIjYEY4IilGKXooRyoqRjRGOC1GNTYjIiNURjgtRjU2IyIkZCJGOC1GNTYjIiRqI0Y4RjdGNCImVFImKihGNEY4LUY1NiMiIz5GOC1GNTYjIiRuIkY4IikydldgKipGNEY4LUY1NiMiI1pGOC1GNTYjIiReIkY4LUY1NiMiJFYlRjgiLkBnUXghW1MqMEZSRjgtRjU2IyIjZkY4LUY1NiMiI2hGOC1GNTYjIiNuRjgtRjU2IyIjckY4LUY1NiMiI3RGOC1GNTYjIiN6RjgiJz5UUCooRjRGOEZqb0Y4LUY1NiMiJHQkRjhDJj5GKkY4PkYpRiQ/KEYnRjhGOCIiKDBGKUY4QyQ+RigtSSVpZ2NkR0YvNiRGKSY3KSIkQiQiJ1xddyIuKj1TdycqZTUiPWY7a2VCIVFTaylbb01vIioiam4qKVEpZlYiZjdzUiU+T0MlUWM1SGE9NCtXbyRRJnk8Sls1VSQiW3UqUVk3LC0mXE1FaTBKazAlPU1QImZ6Rm9VPHU0a2dBTmNudiwqcEwtZ04qKmZ3Km8iZlAqPkBKNDYzJ2VSTFUyQzM+WlE3V0BuOTpBIikpR0shPiopKTRGeiJqZmxcbT0sI0hSMSgpKip6cFY3QjVZRnhCXidmeF53bStsIyk9azhhOj8oPm93KVtOVFZkYUBcVG1CZXYhPm5VdiVlJyopZicqW3BDd1ViVzFBJXB1I2ZkNE5RbTonZmgzeHB3QW80J1EmKlEscUNsUE03T1tkK3cvSWJTVT9ocGgsOVVBYyQ9PldjRmBNPTtjJFxEJlJULGFhJVEkUW5rLmsmeSIqUiJIelojSC9rVm5nZnJwVU5rKT4kemw+Vl5fVzZjZEVxVCkzM047Im8pM3gmSGoncFV1X2FBOTpgYztdJG8ncHpJJkdHIjROOlUvd11NOzc3eiI2I0YnQCQwRihGOEMlPkYpLUklaXF1b0dGLzYkRilGKD8oRiVGOEY4RiUxJjcpRl5yIiRuJyIlajwiJSQ9JiImNjIjIiY+SCkiJ2BbV0ZlckYoQyU+RistSTJpZmFjdG9yL3doZWVsZmFjdEdGJTYkRigmNylGN0Y7RlRGZXAiJFIiIiQkRyIkaCdGZXI+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
<Text-field style="Heading 2" layout="Heading 2">2.4. A pr<Font encoding="UTF-8">\303\255</Font>moszt<Font encoding="UTF-8">\303\263</Font>k eloszl<Font encoding="UTF-8">\303\241</Font>s<Font encoding="UTF-8">\303\241</Font>r<Font encoding="UTF-8">\303\263</Font>l.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.5. A pr<Font encoding="UTF-8">\303\255</Font>moszt<Font encoding="UTF-8">\303\263</Font>k sz<Font encoding="UTF-8">\303\241</Font>m<Font encoding="UTF-8">\303\241</Font>nak hat<Font encoding="UTF-8">\303\241</Font>reloszl<Font encoding="UTF-8">\303\241</Font>sa.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.6. Fermat m<Font encoding="UTF-8">\303\263</Font>dszere.</Text-field> # # 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
<Text-field style="Heading 2" layout="Heading 2">2.7. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.8. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">2.9. Pollard \317\261 m\303\263</Font>dszere.</Text-field> 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==
<Text-field style="Heading 2" layout="Heading 2">2.10. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.11. Fermat t<Font encoding="UTF-8">\303\251</Font>tele.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.12. Euler t<Font encoding="UTF-8">\303\251</Font>tele.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.13. K<Font encoding="UTF-8">\303\255</Font>nai marad<Font encoding="UTF-8">\303\251</Font>kt<Font encoding="UTF-8">\303\251</Font>tel.</Text-field> chrem([1,2,2],[2,3,7]); IiNC
<Text-field style="Heading 2" layout="Heading 2">2.14. T<Font encoding="UTF-8">\303\251</Font>tel.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.15. Gyors hatv<Font encoding="UTF-8">\303\241</Font>nyoz<Font encoding="UTF-8">\303\241</Font>s.</Text-field> # # 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==
<Text-field style="Heading 2" layout="Heading 2">2.16. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.17. Pollard p-1 m<Font encoding="UTF-8">\303\263</Font>dszere.</Text-field> # # 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==
<Text-field style="Heading 2" layout="Heading 2">2.18. Feladat.</Text-field>
<Text-field style="Heading 2" layout="Heading 2">2.19. Pollard p-1 m<Font encoding="UTF-8">\303\263</Font>dszere, m<Font encoding="UTF-8">\303\241</Font>sodik l<Font encoding="UTF-8">\303\251</Font>pcs<Font encoding="UTF-8">\305\221.</Font></Text-field> # # 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=
<Text-field style="Heading 2" layout="Heading 2">2.20. Feladat.</Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\263dszerek</Font></Text-field> LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
<Text-field style="Heading 1" layout="Heading 1">4. Lucas-sorozatok</Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">5. Alkalmaz\303\241sok </Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">6. Sz\303\241mok \303\251s polinomok</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">7. Gyors Fourier-transzform\303\241ci\303\263</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">8. Elliptikus f\303\274ggv\303\251nyek</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251ken</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251kkel</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">12. Polinomfaktoriz\303\241l\303\241s</Font></Text-field>
<Text-field style="Heading 1" layout="Heading 1">13. Az AKS teszt</Text-field>
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">14. A szita m\303\263dszerek alapjai</Font></Text-field>
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn