Thomas D. Dean on Sat, 10 Aug 2019 00:01:08 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: gcd 

On 8/9/19 7:55 AM, Bill Allombert wrote:

On Fri, Aug 09, 2019 at 12:05:51PM +0900, macsyma wrote:

PARI is not well suited to compute gcd of multivariate polynomials.


Even with the following simple method, the correct result can be obtained,
so I posted in the hope that some modification will make gcd() work well.

while(Q=P%(R=Q),P=R);liftpol(R/pollead(R))
%4 = x^35+((-2814705810*c7^5-12865509020*c7^4-2956013550*c7^3+6832839580*c7^2-3002993630*c7-7609289760)*c5^3+(-11072532380*c7^5-12027706250*c7^4-2118210780*c7^3-1424986990*c7^2-3002993630*c7+1673794090)*c5^2+(-1236699170*c7^5-11980726170*c7^4-11980726170*c7^3-1236699170*c7^2-2932502040)*c5+(-9449209994*c7^5-18890856012*c7^4-9081390038*c7^3-7779009056*c7^2-15991519880*c7-9462010960))


Well, you can also obtain this result with my method:

p7=c7^6+c7^5+c7^4+c7^3+c7^2+c7+1;
p5=c5^4+c5^3+c5^2+c5+1;
P7=subst(p7,c7,t);
P5=subst(p5,c5,t);
[R,C7,C5,k]=polcompositum(P7,P5,3);
PP=subst(liftall(P),c5,C5)*Mod(1,R);
QQ=subst(liftall(Q),c7,C7)*Mod(1,R);
R=gcd(PP/content(PP),QQ/content(QQ));
liftall(subst(liftall(R),t,(k*c7+c5)*Mod(1,p7)*Mod(1,p5)))/pollead(R)



I get very different looking answers for both alternate methods.


GP/PARI CALCULATOR Version 2.11.2 (released)
amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
compiled: Aug  8 2019, gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)
threading engine: single
(readline v7.0 enabled, extended help enabled)

? P7=subst(c7^6+c7^5+c7^4+c7^3+c7^2+c7+1,c7,t);
? P5=subst(c5^4+c5^3+c5^2+c5+1,c5,t);
? [R,C7,C5,k]=polcompositum(P7,P5,3);
? PP=subst(liftall(P),c5,C5)*Mod(1,R);
? QQ=subst(liftall(Q),c7,C7)*Mod(1,R);
? gcd(PP/content(PP),QQ/content(QQ))
%6 = Mod(1, t^24 + 2*t^23 + 8*t^22 + 14*t^21 + 35*t^20 + 50*t^19 + 95*t^18 + 129*t^17 + 166*t^16 + 250*t^15 - 20*t^14 + 20*t^13 - 66*t^12 + 466*t^11 + 1866*t^10 + 1011*t^9 + 1096*t^8 + 240*t^7 - 688*t^6 - 597*t^5 + 88*t^4 + 97*t^3 + 9*t^2 - 2*t + 1) 

? p7=c7^6+c7^5+c7^4+c7^3+c7^2+c7+1;
? p5=c5^4+c5^3+c5^2+c5+1;
? P7=subst(p7,c7,t);
? P5=subst(p5,c5,t);
? [R,C7,C5,k]=polcompositum(P7,P5,3);
? PP=subst(liftall(P),c5,C5)*Mod(1,R);
? QQ=subst(liftall(Q),c7,C7)*Mod(1,R);
? R=gcd(PP/content(PP),QQ/content(QQ));
? liftall(subst(liftall(R),t,(k*c7+c5)*Mod(1,p7)*Mod(1,p5)))/pollead(R)
%16 = Mod(1, t^24 + 2*t^23 + 8*t^22 + 14*t^21 + 35*t^20 + 50*t^19 + 95*t^18 + 129*t^17 + 166*t^16 + 250*t^15 - 20*t^14 + 20*t^13 - 66*t^12 + 466*t^11 + 1866*t^10 + 1011*t^9 + 1096*t^8 + 240*t^7 - 688*t^6 - 597*t^5 + 88*t^4 + 97*t^3 + 9*t^2 - 2*t + 1)