Re: the minimal polynomial over the composite field

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

On Wed, Aug 14, 2019 at 02:54:55PM +0900, macsyma wrote:
> Dear All,
> 
> As I mentioned in
> https://pari.math.u-bordeaux.fr/archives/pari-users-1908/msg00014.html ,
> I have the following (sub)goal:
> 
> "For a given irreducible g in Q[x], to find any one factor
>  (with the minimum positive degree) of g over the algebraic number field K
>  defined by polcyclo(p_1),...,polcyclo(p_m) where P={p_1,...,p_m}
>  is all of the odd prime factors of poldegree(g), in other words,
>  to find the minimal polynomial over K of an algebraic number defined by g."
> 
> Probably the simplest way to achieve this is to use 
> the factorization of g over the composite field,
> which is obviously expensive for getting one factor.
> So my current method is
> (step1) For each p in P, extract one factor g_i from factorized g
>         over the Q(zeta_p) using the factorization over a subfield of Q(zeta_p).
> (step2) Get the result as the GCD of all of g_i.
> 
> The code below is an implementation:
> 
> tst001(g) =
> {
>   my(P = select(r -> r - 2, factor(poldegree(g))[, 1]),
>      p, q, s, t, u, A = g, gi);
>   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, g)[1, 1]), u, t))[1, 1];
>     if(#variables(gi)>1, A = gcd(A, gi) /* or RgX_gcd_simple or polcompositum method */ ));
>   liftpol(A/pollead(A))
> };
> 
> An example:
> ? tst001(nfsplitting(x^15-2,120))
> %4 = x^15+((-15780*c5^3-15780*c5^2-25092)*c3+(-26520*c5^3-3740*c5^2-14480*c5-19786))
> 
> However, for large p in P, it still takes time to do nffactor.
> Please let me know if there is a better way than the above.

1) Whenever you can, use nfisincl rather than nffactor.
2) Since q is Galois over Q, instead of nfsubfields+nffactor, you should
use G=galoisinit(q); galoisfixedfield(G,...,2)
Cheers,
Bill