Re: the minimal polynomial over the composite field

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

On Thu, Aug 29, 2019 at 10:26:56AM +0200, Bill Allombert wrote:
> On Tue, Aug 27, 2019 at 02:38:58PM +0900, macsyma wrote:
> > Thank you, Bill.
> > 
> > Your method uses galoisinit(), but at least for my purposes, 
> > the speed of it is not enough.
> > For example, the timing for only galoisinit(nfsplitting()) are
> > 
> > ? for(n=2,16,galoisinit(nfsplitting(x^n-2)));
> > time = 4,165 ms.
> > 
> > ? galoisinit(nfsplitting(x^17-2));
> > time = 33min, 16,082 ms.
> 
> Of course, that is why I said one need to adapt these method to
> nfsplitting(,,2).
> I have some code to help with this that I will post later.

You can force-update the branch bill-nfsplitting.
There is a new function galoissplittinginit, which is like
galoisinit(nfsplitting(...)) but using nfsplitting(,,2).
(it is not complete yet, only G[1..6] is filled, but it is sufficient
for galoisfixedfield).

Here your last example (20s instead of 33min)

G=galoissplittinginit(x^17-2);
\\  ***   last result computed in 19,276 ms.
cj=galoisconjclasses(G);
[subf,inc,fact]=galoisfixedfield(G,cj[8],2);
\\  ***   last result computed in 168 ms.
z17=nfisisom(subf,polcyclo(17,y))[1];
\\  ***   last result computed in 36 ms.
liftpol(subst(fact,y,Mod(z17,polcyclo(17,y))))
%6 =
[x^17+(-51272*y^15-12104*y^14-11016*y^13-60996*y^12-7616*y^11-12342*y^10-37128*y^9+12376*y^8-12410*y^7-17136*y^6+36244*y^5-13736*y^4-12648*y^3+26520*y^2-24752*y-12376),...

If it is still not fast enough for you, you need to compute the action of Galois
group of the polynomial on the p-adic roots (using an improved polgalois), and
use a suitable implementation of galoisfixedfield to compute the
cyclic subfields and the related factorization.

Cheers,
Bill.