Re: the minimal polynomial over the composite field

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Aug 25, 2019 at 10:33:34AM +0900, macsyma wrote:
> > Do you assume g to be Galois ? It seems to me you should be able to know
> > whether the polynomial will factor or not by computing conductor of
> > cyclic subfields.
> 
> Could you inform me, with some example, 
> how the computation you proposed will improve performance ?

There are fast algorithms to compute fixed fields by subgroups of the
Galois group and the factorization over the fixed fields.

galoisfixedfield(,,2) is one them. You probably need the analogous for
nfsplitting(,,2). This replaces nffactor() by group theory computation
which are faster. 

For example if you take
P=nfsplitting(x^7-2);

\\(the following is PARI code to check for cyclic quotients.
\\It is probably better to use GAP)
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;
}

G=galoisinit(P);
S=galoissubgroups(G);
C=[H|H<-S,iscycquotient([G.gen,G.orders],H)];
L=[galoisfixedfield(G,H,1)|H<-C]
%4 =
[x,x^3+672280*x^2+18816310464*x+144627327488,x^2+3294172,x^6+2352980*x^4+230499803184*x^2+6200896666048]

You find that the cyclic subfields are
x,\
x^2+3294172,
x^3+672280*x^2+18816310464*x+144627327488,
x^6+2352980*x^4+230499803184*x^2+6200896666048

my(Q=bnfinit(a)); M=[rnfconductor(Q,H)[1]|H<-L]
%5 = [[Mat(1),[0]],[Mat(7),[0]],[Mat(7),[1]],[Mat(7),[1]]]

Using rnfconductor we find the conductors of these fields is 7.
(actually they are all the subfields of Q(\zeta_7)).
So the factorisation happens only over Q(\zeta_7), no need to
try Q(\zeta_3). Furthermore,

? [subf,inc,fact]=galoisfixedfield(G,C[4],2);
? fact
%8 =
[x^7-1/7*y,x^7+(-19/460077238208*y^5-10/103243*y^3-307775/34916*y),x^7+(165/920154476416*y^5+697/1651888*y^3+2885823/69832*y),x^7+1/7*y,x^7+(19/460077238208*y^5+10/103243*y^3+307775/34916*y),x^7+(-165/920154476416*y^5-697/1651888*y^3-2885823/69832*y)]

gives you directly the factorisation in term of the roots of subf.
z7=nfisisom(subf,polcyclo(7,y))[1];
liftpol(subst(fact,y,Mod(z7,polcyclo(7,y))))
%23 =
[x^7+(84*y^5+112*y^4+28*y^3+56*y^2+140*y+70),x^7+(28*y^5-28*y^4-56*y^3-112*y^2-84*y-42),x^7+(-56*y^5+56*y^4-84*y^3+28*y^2-28*y-14),x^7+(-84*y^5-112*y^4-28*y^3-56*y^2-140*y-70),x^7+(-28*y^5+28*y^4+56*y^3+112*y^2+84*y+42),x^7+(56*y^5-56*y^4+84*y^3-28*y^2+28*y+14)]

gives you the factorization in term of zeta_7.

Cheers,
Bill.