Komputeralgebrai algoritmusokJ\303\241rai AntalEzek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak.1. T\303\266rt\303\251net2. Algebrai alapok3. Norm\303\241l form\303\241k, reprezent\303\241ci\303\2634. Aritmetika5. K\303\255nai marad\303\251kol\303\241s6. Newton-iter\303\241ci\303\263, Hensel-felemel\303\251srestart;E 6.1. P\303\251lda.`mod`:=mods; p:=97; u:=-272300; u0:=u mod p; u1:=(u-u0)/p mod p;
u2:=(u-(u0+u1*p))/p^2 mod p; u-(u0+u1*p+u2*p^2);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnE 6.2. P\303\251lda.p:=5; u:=14*x^2-11*x-15; u0:=u mod p; u1:=(u-u0)/p mod p;
u2:=(u-(u0+u1*p))/p^2 mod p; u-(u0+u1*p+u2*p^2);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnE 6.3. P\303\251lda.u:='u'; a:=36*x^4-180*x^3+93*x^2+330*x+121;
F:=a-u^2; Fp:=diff(F,u);a mod p;u0:=x^2-1; u[1]:=u0; d:=subs(u=u[1],Fp);u1:=-expand(subs(u=u[1],F)/p); u1:=Quo(u1,d,x) mod p;u[2]:=u0+5*u1; u2:=-expand(subs(u=u[2],F)/p^2); u2:=Quo(u2,d,x) mod p;u[3]:=u0+5*u1+5^2*u2; expand(subs(u=u[3],F));E 6.4. P\303\251lda.p:=5; `mod`:=mods;
a:=x^4+x^3*y^2-x^2*y^4+x^2*y*z+2*x^2*z-2*x^2-2*x*y^3*z+x*y^2*z-x*y^2-y^2*z^2+y*z^2-y*z+z^2-2*z+1 mod p;
a:=collect(a,[y,z],`distributed`); sort(a,[y,z],tdeg);
F:=a-u^2; Fp:=diff(F,u);subs(y=0,z=0,a); u[1]:=x^2-1;d:=subs(u=u[1],Fp) mod p;FF:=expand(subs(u=u[1],F)) mod p;
FF:=collect(%,[y,z],`distributed`);
sort(%,[y,z],tdeg);
u2:=0; u3:=-Quo(2*x^2-2,d,x) mod p;
du[2]:=u2*y+u3*z; u[2]:=u[1]+du[2];FF:=expand(subs(u=u[2],F)) mod p;
FF:=collect(%,[y,z],`distributed`);
sort(%,[y,z],tdeg);
u22:=-Quo(x^3-x,d,x) mod p; u23:=-Quo(x^2-1,d,x) mod p; u33:=-Quo(0,d,x) mod p;
du[3]:=u22*y^2+u23*y*z+u33*z^2; u[3]:=u[2]+du[3];FF:=expand(subs(u=u[3],F)) mod p;E 6.5. P\303\251lda.p:=5; m:=p; a:=x^3+10*x^2-432*x+5040; a mod p; u:=x; w:=x^2-2;
e:=expand(a-u*w);Gcdex(u,w,x,'s','t') mod p; s; t;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;E 6.6. P\303\251lda.p:=5; m:=p; a:=x^4+1; a mod p; u:=x^2+2; w:=x^2-2; expand(u*w) mod p;
e:=expand(a-u*w);Gcdex(u,w,x,'s','t') mod p; s; t;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;E 6.7. P\303\251lda.p:=5; m:=p; a:=expand((2*x+5)*(6*x^2-10*x+7)); a mod p; u:=2*x; w:=x^2+2;
e:=expand(a-u*w);Gcdex(u,w,x,'s','t') mod p; s; t;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); e:=expand(a-u*w); m:=m*p;E 6.8. P\303\251lda.p:=5; m:=p; a:=expand((2*x+5)*(6*x^2-10*x+7));
a mod p; u:=2*x; w:=x^2+2;
alpha:=lcoeff(a); mu:=lcoeff(u); nu:=lcoeff(w);
aa:=alpha*a; u:=alpha*u/mu mod m; w:=alpha*w/nu mod m;
e:=expand(aa-u*w);Gcdex(u,w,x,'s','t') mod p; s; t;c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); m:=m*p;
mu:=lcoeff(u); nu:=lcoeff(w);
u:=alpha*u/mu mod m; w:=alpha*w/nu mod m;
e:=expand(aa-u*w);c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;sigma:=Rem(sigma,w,x,'q') mod p; q; tau:=expand(tau+q*u) mod p;u:=expand(u+tau*m); w:=expand(w+sigma*m); m:=m*p;
mu:=lcoeff(u); nu:=lcoeff(w);
u:=alpha*u/mu mod m; w:=alpha*w/nu mod m;
e:=expand(aa-u*w);mu:=igcd(coeffs(u)); u:=u/mu;
nu:=igcd(coeffs(w)); w:=w/nu;A 6.1. Algoritmus. replace_lc:=proc(a,x,alpha) local aa,aalpha,t;
aa:=expand(a);
aalpha:=lcoeff(aa,x,'t');
aa:=expand(aa-aalpha*t+alpha*t);
end;UnivariateHensel:=proc(a,u1,w1,x,p,B,gamma)
local aa,alpha,e,u,uu,w,ww,m,s,t,q,c,sigma,tau;
aa:=expand(a); alpha:=lcoeff(aa); aa:=gamma*aa;
uu:=expand(u1); uu:=uu/lcoeff(uu)*gamma mod p;
ww:=expand(w1); ww:=ww/lcoeff(ww)*alpha mod p;
Gcdex(uu,ww,x,'s','t') mod p;
u:=replace_lc(uu,x,gamma); w:=replace_lc(ww,x,alpha);
e:=expand(aa-u*w); m:=p;
while e<>0 and m<2*B*gamma do
c:=e/m; sigma:=expand(s*c) mod p; tau:=expand(t*c) mod p;
sigma:=Rem(sigma,ww,x,'q') mod p;
tau:=expand(tau+q*uu) mod p;
u:=expand(u+tau*m); w:=expand(w+sigma*m);
e:=expand(aa-u*w); m:=m*p;
od;
if e=0 then
u:=u/igcd(coeffs(u)); w:=w/igcd(coeffs(w));
[u,w];
else FAIL fi;
end;LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnE 6.9. P\303\251lda.debug(UnivariateHensel); debug(replace_lc);UnivariateHensel(a,2*x,2*x^2-1,x,5,10000,2);LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnE 6.10. P\303\251lda.p:=5; l:=1; a:=x^2*y^4*z-x*y^9*z^2+x*y*z^3+2*x-y^6*z^4-2*y^5*z;
subs(y=1,z=1,a) mod p^l;u[1]:=x-2; w[1]:=x-1; expand(u[1]*w[1]) mod p^l;aa:=expand(subs(y=Y+1,z=Z+1,a)) mod p^l;collect(aa,[Y,Z],`distributed`): aa:=sort(%,[Y,Z],tdeg);aa:=subs(Y=y-1,Z=z-1,aa) mod p^l;
u[7]:=(x-2)+(-x+1)*(y-1)+(x-2)*(z-1)+x*(y-1)^2+(-x-2)*(y-1)*(z-1)+(-2)*(z-1)^2+(-x)*(y-1)^3+x*(y-1)^2*(z-1)+(-2)*(y-1)*(z-1)^2+(z-1)^3+x*(y-1)^4+(-x)*(y-1)^3*(z-1)+(y-1)*(z-1)^3+x*(y-1)^4*(z-1) mod p^l;
w[7]:=(x-1)+(-1)*(z-1)+(-1)*(y-1)^5+(-1)*(y-1)^5*(z-1) mod p^l;expand(u[7]) mod p^l; expand(w[7]) mod p^l; expand(aa-u[7]*w[7]) mod p^l;A 6.2. Algoritmus. MultivariateDiophant:=proc(a,c,E,d,p,k)
local sigma,r,nu,i,A,aa,b,cc,EE,e,monom,m,x,y,ee,cm,ds,alpha;
r:=nops(a); nu:=nops(E);
if nu>1 then
x:=op(1,E[nu]); alpha:=op(2,E[nu]);
A:=mul(a[i],i=1..r);
for i to r do b[i]:=A/a[i] od;
aa:=subs(E[nu],a);
cc:=subs(E[nu],c);
EE:=E[1..nu-1];
sigma:=MultivariateDiophant(aa,cc,EE,d,p,k);
e:=mods(expand(c-add(sigma[i]*b[i],i=1..r)),p^k);
monom:=1;
for m to d while e<>0 do
monom:=monom*(x-alpha);
ee:=diff(e,[x$m]);
cm:=subs(x=alpha,ee)/m!;
if cm<>0 then
ds:=MultivariateDiophant(aa,cm,EE,d,p,k);
for i to r do sigma[i]:=expand(sigma[i]+ds[i]*monom) od;
e:=mods(expand(e-add(ds[i]*monom*b[i],i=1..r)),p^k);
fi;
od;
else
x:=E[1];
sigma:=[0$i=1..r];
for m from 0 to d do
cm:=coeff(c,x,m);
if cm<>0 then
ds:=UnivariateDiophant(a,x,m,p,k);
for i to r do sigma[i]:=expand(sigma[i]+ds[i]*cm) od;
fi;
od;
fi;
map((x,y)->mods(x,y),sigma,p^k);
end;A 6.3. Algoritmus. UnivariateDiophant:=proc(a,x,m,p,k)
local i,sigma,r,s,R,q;
r:=nops(a);
if r>2 then
s:=MultiTermEEAlift(a,x,p,k); R:=[];
for i to r do R:=[op(R),mods(rem(x^m*s[i],a[i],x),p^k)] od;
else
s:=EEAlift(a[2],a[1],x,p,k);
q:=mods(quo(x^m*s[1],a[1],x),p^k);
R:=[mods(expand(x^m*s[1]-q*a[1]),p^k),
mods(expand(x^m*s[2]+q*a[2]),p^k)];
fi; R;
end;MultiTermEEAlift:=proc(a,x,p,k) local i,r,s,beta,sigma;
r:=nops(a); s:=[0$i=1..r];
s[r-1]:=a[r];
for i from r-2 by -1 to 1 do s[i]:=expand(a[i+1]*s[i+1]) od;
beta:=1;
for i to r-1 do
sigma:=MultivariateDiophant([s[i],a[i]],beta,[x],0,p,k);
beta:=sigma[1]; s[i]:=sigma[2];
od; s[r]:=beta;
s;
end;EEAlift:=proc(a,b,x,p,k) local ap,bp,s,t,sp,tp,i,m,e,c,q,sigma,tau;
ap:=mods(a,p); bp:=mods(b,p);
mods(Gcdex(ap,bp,x,'s','t'),p);
sp:=mods(s,p); tp:=mods(t,p); m:=p;
for i to k-1 do
e:=expand(1-s*a-t*b); c:=mods(e/m,p);
sigma:=mods(expand(sp*c),p); tau:=mods(expand(tp*c),p);
q:=mods(Quo(sigma,bp,x),p);
sigma:=mods(expand(sigma-q*bp),p);
tau:=mods(expand(tau+q*ap),p);
s:=expand(s+sigma*m); t:=expand(t+tau*m);
m:=m*p;
od; [s,t];
end;LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnA 6.4. Algoritmus. MultivariateHensel:=proc(a,E,p,l,u,lcU)
local nu,A,i,x,alpha,U,UU,n,monom,maxdeg,aa,e,ee,co,oco,t,xx,m,j,c,dU;
aa:=expand(a);
nu:=nops(E); A:=[0$i=1..nu]; n:=nops(u);
A[nu]:=aa; maxdeg:=-1;
for i from nu by -1 to 2 do
x:=op(1,E[i]); alpha:=op(2,E[i]);
A[i-1]:=subs(E[i],A[i]);
if degree(a,x)>maxdeg then maxdeg:=degree(a,x) fi;
od;
U:=u; xx:=E[1];
for i from 2 to nu do
UU:=U; monom:=1;
x:=op(1,E[i]); alpha:=op(2,E[i]);
for m to n do
if lcU[m]<>1 then
co:=mods(subs(E[i+1..nu],lcU[m]),p^l);
oco:=lcoeff(collect(U[m],xx),xx,'t');
U[m]:=expand(U[m]-oco*t+co*t);
fi;
od;
e:=expand(A[i]-mul(U[j],j=1..n));
for j to degree(A[i],x) while e<>0 do
monom:=monom*(x-alpha);
c:=subs(E[i],diff(e,[x$j]))/j!;
if c<>0 then
dU:=MultivariateDiophant(UU,c,E[1..i-1],maxdeg,p,l);
for m to n do U[m]:=mods(expand(U[m]+dU[m]*monom),p^l) od;
e:=mods(expand(A[i]-mul(U[m],m=1..n)),p^l);
fi;
od;
od;
if a=expand(mul(U[m],m=1..n)) then U else FAIL fi;
end; a; factor(a); collect(a,x); coeffs(%,x); gcd(%[1],%[2]);E:=[x,z=1,y=1]; subs(E[2..3],a);debug(MultivariateHensel);MultivariateHensel(a,E,5,2,[x-1,x+3],[1,y^4*z]);7. Legnagyobb k\303\266z\303\266s oszt\303\2638. Faktoriz\303\241l\303\241s9. Egyenletrendszerek10. Gr\303\266bner-b\303\241zisok11. Racion\303\241lis t\303\266rtf\303\274ggv\303\251nyek integr\303\241l\303\241sa12. A Risch-algoritmus.LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn