Bill Allombert on Sun, 11 Aug 2019 16:30:37 +0200

 Re: gcd

```On Sun, Aug 11, 2019 at 11:32:49AM +0900, macsyma wrote:
> However, it seems slow for P, Q in
> http://macsyma.starfree.jp/temp/PQ23.gp
>
> {p11=polcyclo(11,c11);
> p23=polcyclo(23,c23);
> P11=subst(p11,c11,t);
> P23=subst(p23,c23,t);
> [R,C11,C23,k]=polcompositum(P11,P23,3);
> PP=subst(liftall(P),c11,C11)*Mod(1,R);
> QQ=subst(liftall(Q),c23,C23)*Mod(1,R);
> R=gcd(PP/content(PP),QQ/content(QQ));
> time = 11,949 ms.

Note that your polynomials P and Q do not depend on c11 (and neither
does the result), so you do not need to do a compositum at all.
Just do:

p23=polcyclo(23,c23);
PP=liftall(P)*Mod(1,p23);
QQ=liftall(Q)*Mod(1,p23);
liftall(gcd(PP/content(PP),QQ/content(QQ)))

%2 = x^23+(-2124694*c23^21-489808*c23^20-423016*c23^19-3194470*c23^18-472604*c23^17-486772*c23^16-2778446*c23^15-288420*c23^14-490268*c23^13-1470942*c23^12+490314*c23^11-490360*c23^10-692208*c23^9+1797818*c23^8-493856*c23^7-508024*c23^6+2213842*c23^5-557612*c23^4-490820*c23^3+1144066*c23^2-980628*c23-490314)
***   last result computed in 4 ms.

Cheers,
Bill.

```

• References:
• Re: gcd
• From: macsyma <macsyma@yahoo.co.jp>