Re: the minimal polynomial over the composite field

[macsyma <macsyma@yahoo.co.jp>]

Thank you for your continuous improvement.
The following is a comparison of the first half of the method 
you have taught me and tst002 (using nffactor).

install(quotient_group,GG);
install(group_quotient,GG);
iscycquotient(G,H)=
{
  if(!galoisisnormal(G,H),return(0));
  my(Q=quotient_group(group_quotient(G,H),G));
  my(A=galoisisabelian(Q,2));
  !(A===0) && #A<=1;
};

{for(n=2,25,
G=galoissplittinginit(x^n-2);
S=galoissubgroups(G);
C=[H|H<-S,iscycquotient([G.gen,G.orders],H)];
L=[galoisfixedfield(G,H,1)|H<-C];
my(Q=bnfinit(a));
M=[rnfconductor(Q,H)[1]|H<-L])};

/* time = 1min, 47,883 ms. */

install(RgX_gcd_simple,GG);
tst002(fx) =
{
  my(A = gx = nfsplitting(fx), P, p, q, s, t, u, gi);
  P = select(r -> r - 2, factor(poldegree(gx))[, 1]);
  for(i = 1, #P,
    q = polcyclo(p = P[i], u = eval(concat("c", p)));
    [s, t] = nfsubfields(q)[-2..-2][1];
    gi = nffactor(q, subst(liftpol(nffactor(s, gx)[1, 1]), u, t))[1, 1];
    A = if(#variables(A) == 1, gi, if(#variables(gi) == 1, A, RgX_gcd_simple(A, gi))));
  liftpol(A/pollead(A))
};

for(n=2,25,tst002(x^n-2));

/* time = 1min, 4,412 ms. */

Factoring by galoisfixedfield(,,2) is attractive, 
but it seems time-consuming to put together preparations for that.

> Also your example x^n-2 are very sparse which make computation
> faster compared to generic example.
How about 2*(1+x)^n-x^n (dense and having an isomorphic splitting field) ? 

macsyma