Sz\303\241m\303\255t\303\263g\303\251pes sz\303\241melm\303\251letJ\303\241rai AntalEzek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak1. A pr\303\255mek eloszl\303\241sa, szit\303\241l\303\241s2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263dszerek3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\303\263dszerekLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn4. Lucas-sorozatok5. Alkalmaz\303\241sok restart; with(numtheory);5.1. Fermat-sz\303\241mok.5.2. Feladat.5.3. Feladat.interface(verboseproc=2);print(fermat);5.4. Mersenne-sz\303\241mok.mersennes:=[2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937,21701,23209,44497,86243,110503,132049,216091,756839,859833,1257787,1398269,2976221,3021377,6972593,13466917,20996011,24036583,25964951,30402457,32582657,37156667,42643801,43112609];5.5. Feladat.5.6. Feladat.interface(verboseproc=2);print(mersenne);5.7. h*2^m+-1 alak\303\272 pr\303\255mek keres\303\251se.5.8. Feladat.5.9. Feladat.5.10. Ikerpr\303\255mek.5.11. Feladat.5.12. Feladat.5.13. Sophie Germain pr\303\255mek.5.14. Ikerpr\303\255m, amely Sophie Germain pr\303\255m is.5.15. n^2+1 es n^4+1 alak\303\272 pr\303\255mek.5.16. Egy\303\251b speci\303\241lis alak\303\272 pr\303\255mek.5.17. K\303\241tai egy probl\303\251m\303\241ja.5.18. P\303\251lda.#
# 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;trialdiv(2^107-2^54+1,1000);n0:=%[3][1];modp(3&^(n0-1),n0);trialdiv(n0-1,1000);n1:=%[5][1];modp(3&^(n1-1),n1);trialdiv(n1,100000);n2:=%[2][1];modp(3&^(n2-1),n2);trialdiv(n2-1,1000);n3:=%[4][1];modp(3&^(n3-1),n3);trialdiv(n3,10000);n4:=%[2][1];modp(3&^(n4-1),n4);trialdiv(n4-1,1000);trialdiv(2^107+2^54+1,1000);n5:=%[1][1];modp(3&^(n5-1),n5);trialdiv(2^107+2^54+1,1000000);n6:=%[2][1];modp(3&^(n6-1),n6);5.19. Feladat.5.20. Pr\303\255msz\303\241mk\303\263dol\303\241s.5.21. Feladat.p:=safeprime(1563456788814256178886765661555261342987645321345665432123456788772091275121098761232122333321233434123432123344454321234320948725467845467788859812342365); log[2.](p);
q:=safeprime(29841524475159001676561453467890987651234254321456490998767626788182514325678909987236514234154232396587874778993377722004988376667882767156363888377626677728888); log[2.](q);
n:=p*q;
e:=2876354132453678909987653432123409887635423125;
igcdex(e,(p-1)*(q-1),'d'); d; d*e mod (p-1)*(q-1);5.22. Feladat.M:="Mint v\303\255z alatti, elmer\303\274lt harangok
hint\303\241znak-e hajnalonk\303\251nt \303\241gyadn\303\241l
a tizennyolc \303\251ves iskol\303\241sok
kiket felakasztatt\303\241l";
convert(M,'bytes');
m:=sum(%[i]*256^(i-1),i=1..nops(%));
c:=m&^e mod n;c&^d mod n; convert(%,base,256); convert(%,'bytes');6. Sz\303\241mok \303\251s polinomok7. Gyors Fourier-transzform\303\241ci\303\2638. Elliptikus f\303\274ggv\303\251nyek9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303\251ken10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\303\251kkel11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel12. Polinomfaktoriz\303\241l\303\241s13. Az AKS teszt14. A szita m\303\263dszerek alapjaiLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn