|Bill Allombert on Fri, 30 Aug 2019 22:13:15 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: the minimal polynomial over the composite field|
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,2); \\ *** last result computed in 168 ms. z17=nfisisom(subf,polcyclo(17,y)); \\ *** 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.