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 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\274rb\303\251kkel11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel12. Polinomfaktoriz\303\241l\303\241s13. Az AKS-teszt14. A szita m\303\263dszerek alapjairestart; with(numtheory);14.1. Dixon v\303\251letlen n\303\251gyzet m\303\263dszere.n:=nextprime(7*10^2)*prevprime(14*10^2);B:=20; F:=[];
for j from 2 while j<B do
if isprime(j) then F:=[op(F),j]; fi;
od;
F; nops(F);rnd:=rand(2..n-2); rnd(); ifactors(%^2 mod n);R:=[];
while nops(R)<nops(F)+5 do
x:=rnd();
y:=ifactors(modp(x^2,n))[2];
if y[nops(y)][1]>=B then next else R:=[op(R),[x,y]] fi;
od:R;Rc:=[[21475, [[3, 2], [5, 1], [17, 2], [19, 1]]], [855183, [[2, 4], [3, 4], [5, 1], [7, 2]]], [164912, [[3, 1], [5, 2], [11, 1], [13, 1], [19, 1]]], [728436, [[2, 1], [3, 2], [11, 1], [13, 1], [17, 1]]], [362222, [[3, 2], [19, 1]]], [297430, [[5, 1], [19, 4]]], [744161, [[3, 3], [5, 1], [11, 1], [13, 1], [19, 1]]], [495370, [[2, 8], [3, 6], [5, 1]]], [577106, [[2, 1], [11, 1], [13, 2], [19, 1]]], [699549, [[7, 4]]], [689811, [[5, 4], [13, 1], [17, 1]]], [695704, [[3, 2], [5, 1], [11, 4]]], [315384, [[2, 4], [3, 1], [5, 1], [11, 1], [13, 1], [19, 1]]]];with(linalg);RM:=matrix(nops(R),nops(F),0);for i to nops(Rc) do
v:=Rc[i][2];
for j to nops(v) do
vv:=v[j];
for k to nops(F) do if vv[1]=F[k] then RM[i,k]:=vv[2] fi od;
od;
od:print(RM);x:=Rc[10][1]; y:=7^2; x^2-y^2 mod n;igcd(n,x-y);RM:=addrow(RM,4,9,1);RM:=addrow(RM,3,7,1): RM:=addrow(RM,3,13,1);RM:=addrow(RM,2,1,1): RM:=addrow(RM,2,6,1): RM:=addrow(RM,2,7,1):
RM:=addrow(RM,2,8,1): RM:=addrow(RM,2,12,1):RM:=addrow(RM,2,13,1);RM:=addrow(RM,1,5,1): RM:=addrow(RM,1,9,1);x:=Rc[5][1]*(Rc[1][1]*Rc[2][1]) mod n;y:=2^2*3^4*5*7*17*19 mod n;x^2-y^2 mod n;igcd(n,x-y);interface(echo=3);read("../../old/factor/factor");#
# This procedure set up the factor base.
# The factor base is a list which
# always start with -1, has length N,
# and contains in incerasing order
# the primes p for which (n|p)=1.
#
setfactorbase:=proc(n,N) local F,p;
F:=[-1]; p:=2;
while nops(F)<N do
if jacobi(n,p)=1 then F:=[op(F),p]; fi;
p:=nextprime(p);
od; F; end;#
# The following procedure is a naive way to
# look for a full over a given factor base F
# starting with -1. Simple the number x
# is trial divided with
# the members of the factor base up to
# the end of the factor base. The result
# is a list with two members. The first
# is the unfactored part, the other a list.
# The members of this list are two-member lists
# containing index into the factor base and
# exponent of the given factor base member
# in the factorization.
#
trialfull:=proc(x,F) local y,p,e,L,i;
L:=[]; y:=x;
if y<0 then L:=[[1,1]]; y:=-y; fi;
for i from 2 to nops(F) while y>1 do
p:=F[i];
if y mod p = 0 then e:=0;
while y mod p = 0 do e:=e+1; y:=y/p; od;
L:=[op(L),[i,e]];
fi;
od; [y,L]; end;#
# The following procedure is a naive way to
# find full's for a given composite
# number n over a factor base F
# starting with -1. Simple the numbers
# around sqrt(n) trial divided with
# the members of the factor base until
# N full factorizations have been found.
#
trialfulls:=proc(n,F,N) local x,i,R,L;
R:={}; x:=floor(evalf(sqrt(n)));
L:=trialfull(x^2-n,F);
if L[1]=1 then R:={[x,L[2]]} fi;
i:=1;
while nops(R)<N do
L:=trialfull((x+i)^2-n,F);
if L[1]=1 then R:=R union {[x+i,L[2]]} fi;
if i>0 then i:=-i else i:=-i+1; fi;
od; R; end;n; F:=setfactorbase(n,10);trialfulls(n,F,11);14.2. L\303\241nct\303\266rtek.14.3. Kvadratikus irracion\303\241lis sz\303\241mok l\303\241nct\303\266rt alakja.14.4. Faktoriz\303\241l\303\241s l\303\241nct\303\266rtekkel.14.5. N\303\251gyzetes szita.n:=nextprime(7*10^5)*prevprime(14*10^5);n mod 8; n:=23*n; n mod 8;m:=2000; B:=50; T:=2.; b:=ceil(sqrt(n));
F:=[[2,floor(0.5+2.*log[2.](2)),1]];
for j from 3 while j<B do
if isprime(j)=false then next fi;
if jacobi(n,j)=1 then
F:=[op(F),[j,floor(0.5+j/(j-1)*log[2.](j)),msqrt(n,j)]];
fi;
od;
F; nops(F);S:= rtable(0..2*m,0);p:=F[1][1]; lp:=F[1][2]; x:=modp(m-b+F[1][3],p);
while x<=2*m do S[x]:=S[x]+lp; x:=x+p; od:for j from 2 to nops(F) do
ppp:=F[j]; p:=ppp[1]; lp:=ppp[2];
x:=modp(m-b+ppp[3],p);
while x<=2*m do S[x]:=S[x]+lp; x:=x+p; od:
x:=modp(m-b-ppp[3],p);
while x<=2*m do S[x]:=S[x]+lp; x:=x+p; od:
od:R:=[]; TT:=floor(log[2.](2*m*b)/T);for j from 0 to 2*m do if S[j]>=TT then R:=[op(R),j-m] fi od:R;map(y->ifactors((y+b)^2-n),R);14.6. T\303\266bbpolinomos n\303\251gyzetes szita.n:=nextprime(7*10^7)*prevprime(14*10^7);n mod 8; n:=37*n; n mod 8;m:=10000; B:=100; T:=1.5;
F:=[[2,floor(0.5+2.*log[2.](2)),1]];
for j from 3 while j<B do
if isprime(j)=false then next fi;
if jacobi(n,j)=1 then
F:=[op(F),[j,floor(0.5+j/(j-1)*log[2.](j)),msqrt(n,j)]];
fi;
od;
F; nops(F);dd:=floor((2*n/m^2)^(1/4.)): if type(dd,odd) then dd:=dd+1; fi:
dd:=dd..dd;if abs(op(1,dd)-(2*n/m^2)^(1/4.))<abs(op(2,dd)-(2*n/m^2)^(1/4.)) then
d:=prevprime(op(1,dd));
while modp(d,4)<>3 or jacobi(d,n)<>1 do
d:=prevprime(d);
od;
dd:=d..op(2,dd);
else
d:=nextprime(op(2,dd));
while modp(d,4)<>3 or jacobi(d,n)<>1 do
d:=nextprime(d);
od;
dd:=op(1,dd)..d;
fi:
d; dd;a:=d^2; h0:=n&^((d-3)/4) mod d;h1:=n*h0 mod d; (n-h1^2)/d; h2:=%*h0*((d+1)/2) mod d;b:=mods(h1+h2*d,a); b^2-n mod a; c:=(b^2-n)/a;S:= rtable(0..2*m,0); p:=F[1][1]; lp:=F[1][2]; x:=modp(m+(-b+F[1][3])/a,p);
while x<=2*m do S[x]:=S[x]+lp; x:=x+p; od:for j from 2 to nops(F) do
ppp:=F[j]; p:=ppp[1]; lp:=ppp[2];
x:=modp(m+(-b+ppp[3])/a,p);
while x<=2*m do S[x]:=S[x]+lp; x:=x+p; od:
x:=modp(m+(-b-ppp[3])/a,p);
while x<=2*m do S[x]:=S[x]+lp; x:=x+p; od:
od:R:=[]; TT:=floor(log[2.](a*m^2/2.)/T); for j from 0 to 2*m do if S[j]>=TT then R:=[op(R),j-m] fi od:R;map(y->ifactors(a*y^2+2*b*y+c),R);15. Sz\303\241mtest szita16. Vegyes probl\303\251m\303\241kLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn