Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - FpXQX_factor.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.14.0 lcov report (development 27775-aca467eab2) Lines: 1606 1926 83.4 %
Date: 2022-07-03 07:33:15 Functions: 126 149 84.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2016  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : #include "pari.h"
      16             : #include "paripriv.h"
      17             : 
      18             : #define DEBUGLEVEL DEBUGLEVEL_factorff
      19             : 
      20             : /*******************************************************************/
      21             : /**                                                               **/
      22             : /**           Isomorphisms between finite fields                  **/
      23             : /**                                                               **/
      24             : /*******************************************************************/
      25             : static void
      26          14 : err_Flxq(const char *s, GEN P, ulong l)
      27             : {
      28          14 :   if (!uisprime(l)) pari_err_PRIME(s, utoi(l));
      29          14 :   pari_err_IRREDPOL(s, Flx_to_ZX(get_Flx_mod(P)));
      30           0 : }
      31             : static void
      32           0 : err_FpXQ(const char *s, GEN P, GEN l)
      33             : {
      34           0 :   if (!BPSW_psp(l)) pari_err_PRIME(s, l);
      35           0 :   pari_err_IRREDPOL(s, get_FpX_mod(P));
      36           0 : }
      37             : 
      38             : /* compute the reciprocical isomorphism of S mod T,p, i.e. V such that
      39             :    V(S)=X  mod T,p*/
      40             : GEN
      41        2862 : Flxq_ffisom_inv(GEN S,GEN T, ulong p)
      42             : {
      43        2862 :   pari_sp ltop = avma;
      44        2862 :   long n = get_Flx_degree(T);
      45        2862 :   GEN M = Flxq_matrix_pow(S,n,n,T,p);
      46        2862 :   GEN V = Flm_Flc_invimage(M, vecsmall_ei(n, 2), p);
      47        2862 :   if (!V) err_Flxq("Flxq_ffisom_inv", T, p);
      48        2862 :   return gerepileupto(ltop, Flv_to_Flx(V, get_Flx_var(T)));
      49             : }
      50             : 
      51             : GEN
      52         588 : FpXQ_ffisom_inv(GEN S,GEN T, GEN p)
      53             : {
      54         588 :   pari_sp ltop = avma;
      55         588 :   long n = get_FpX_degree(T);
      56         588 :   GEN M = FpXQ_matrix_pow(S,n,n,T,p);
      57         588 :   GEN V = FpM_FpC_invimage(M, col_ei(n, 2), p);
      58         588 :   if (!V) err_FpXQ("Flxq_ffisom_inv", T, p);
      59         588 :   return gerepilecopy(ltop, RgV_to_RgX(V, get_FpX_var(T)));
      60             : }
      61             : 
      62             : /* Let M the matrix of the Frobenius automorphism of Fp[X]/(T). Compute M^d
      63             :  * TODO: use left-right binary (tricky!) */
      64             : GEN
      65         399 : Flm_Frobenius_pow(GEN M, long d, GEN T, ulong p)
      66             : {
      67         399 :   pari_sp ltop=avma;
      68         399 :   long i,l = get_Flx_degree(T);
      69         399 :   GEN R, W = gel(M,2);
      70        1337 :   for (i = 2; i <= d; ++i) W = Flm_Flc_mul(M,W,p);
      71         399 :   R=Flxq_matrix_pow(Flv_to_Flx(W,get_Flx_var(T)),l,l,T,p);
      72         399 :   return gerepileupto(ltop,R);
      73             : }
      74             : 
      75             : GEN
      76          35 : FpM_Frobenius_pow(GEN M, long d, GEN T, GEN p)
      77             : {
      78          35 :   pari_sp ltop=avma;
      79          35 :   long i,l = get_FpX_degree(T);
      80          35 :   GEN R, W = gel(M,2);
      81         147 :   for (i = 2; i <= d; ++i) W = FpM_FpC_mul(M,W,p);
      82          35 :   R=FpXQ_matrix_pow(RgV_to_RgX(W, get_FpX_var(T)),l,l,T,p);
      83          35 :   return gerepilecopy(ltop,R);
      84             : }
      85             : 
      86             : /* Essentially we want to compute FqM_ker(MA-pol_x(v),U,l)
      87             :  * To avoid use of matrix in Fq we compute FpM_ker(U(MA),l) then recover the
      88             :  * eigenvalue by Galois action */
      89             : static GEN
      90       40691 : Flx_Flm_Flc_eval(GEN U, GEN MA, GEN a, ulong p)
      91             : {
      92       40691 :   long i, l = lg(U);
      93       40691 :   GEN b = Flv_Fl_mul(a, uel(U, l-1), p);
      94      165151 :   for (i=l-2; i>=2; i--)
      95      124461 :     b = Flv_add(Flm_Flc_mul(MA, b, p), Flv_Fl_mul(a, uel(U, i), p), p);
      96       40690 :   return b;
      97             : }
      98             : 
      99             : static GEN
     100       39538 : Flx_intersect_ker(GEN P, GEN MA, GEN U, ulong p)
     101             : {
     102       39538 :   pari_sp ltop = avma;
     103       39538 :   long i, vp = get_Flx_var(P), vu = get_Flx_var(U), r = get_Flx_degree(U);
     104             :   GEN V, A, R;
     105             :   ulong ib0;
     106             :   pari_timer T;
     107       39538 :   if (DEBUGLEVEL>=4) timer_start(&T);
     108       39538 :   V = Flx_div(Flx_Fl_add(monomial_Flx(1, get_Flx_degree(P), vu), p-1, p), U, p);
     109             :   do
     110             :   {
     111       40690 :     A = Flx_Flm_Flc_eval(V, MA, random_Flv(lg(MA)-1, p), p);
     112       40690 :   } while (zv_equal0(A));
     113       39537 :   if (DEBUGLEVEL>=4) timer_printf(&T,"matrix polcyclo");
     114             :   /*The formula is
     115             :    * a_{r-1} = -\phi(a_0)/b_0
     116             :    * a_{i-1} = \phi(a_i)+b_ia_{r-1}  i=r-1 to 1
     117             :    * Where a_0=A[1] and b_i=U[i+2] */
     118       39537 :   ib0 = Fl_inv(Fl_neg(U[2], p), p);
     119       39537 :   R = cgetg(r+1,t_MAT);
     120       39537 :   gel(R,1) = A;
     121       39537 :   gel(R,r) = Flm_Flc_mul(MA, Flv_Fl_mul(A,ib0, p), p);
     122       45389 :   for(i=r-1; i>1; i--)
     123             :   {
     124        5852 :     gel(R,i) = Flm_Flc_mul(MA,gel(R,i+1),p);
     125        5852 :     Flv_add_inplace(gel(R,i), Flv_Fl_mul(gel(R,r), U[i+2], p), p);
     126             :   }
     127       39537 :   return gerepileupto(ltop, Flm_to_FlxX(Flm_transpose(R),vp,vu));
     128             : }
     129             : 
     130             : static GEN
     131         182 : FpX_FpM_FpC_eval(GEN U, GEN MA, GEN a, GEN p)
     132             : {
     133         182 :   long i, l = lg(U);
     134         182 :   GEN b = FpC_Fp_mul(a, gel(U, l-1), p);
     135         966 :   for (i=l-2; i>=2; i--)
     136         784 :     b = FpC_add(FpM_FpC_mul(MA, b, p), FpC_Fp_mul(a, gel(U, i), p), p);
     137         182 :   return b;
     138             : }
     139             : 
     140             : static GEN
     141         182 : FpX_intersect_ker(GEN P, GEN MA, GEN U, GEN l)
     142             : {
     143         182 :   pari_sp ltop = avma;
     144         182 :   long i, vp = get_FpX_var(P), vu = get_FpX_var(U), r = get_FpX_degree(U);
     145             :   GEN V, A, R, ib0;
     146             :   pari_timer T;
     147         182 :   if (DEBUGLEVEL>=4) timer_start(&T);
     148         182 :   V = FpX_div(FpX_Fp_sub(pol_xn(get_FpX_degree(P), vu), gen_1, l), U, l);
     149             :   do
     150             :   {
     151         182 :     A = FpX_FpM_FpC_eval(V, MA, random_FpC(lg(MA)-1, l), l);
     152         182 :   } while (ZV_equal0(A));
     153         182 :   if (DEBUGLEVEL>=4) timer_printf(&T,"matrix polcyclo");
     154             :   /*The formula is
     155             :    * a_{r-1} = -\phi(a_0)/b_0
     156             :    * a_{i-1} = \phi(a_i)+b_ia_{r-1}  i=r-1 to 1
     157             :    * Where a_0=A[1] and b_i=U[i+2] */
     158         182 :   ib0 = Fp_inv(negi(gel(U,2)),l);
     159         182 :   R = cgetg(r+1,t_MAT);
     160         182 :   gel(R,1) = A;
     161         182 :   gel(R,r) = FpM_FpC_mul(MA, FpC_Fp_mul(A,ib0,l), l);
     162         518 :   for(i=r-1;i>1;i--)
     163         336 :     gel(R,i) = FpC_add(FpM_FpC_mul(MA,gel(R,i+1),l),
     164         336 :         FpC_Fp_mul(gel(R,r), gel(U,i+2), l),l);
     165         182 :   return gerepilecopy(ltop,RgM_to_RgXX(shallowtrans(R),vp,vu));
     166             : }
     167             : 
     168             : /* n must divide both the degree of P and Q.  Compute SP and SQ such
     169             :  * that the subfield of FF_l[X]/(P) generated by SP and the subfield of
     170             :  * FF_l[X]/(Q) generated by SQ are isomorphic of degree n.  P and Q do
     171             :  * not need to be of the same variable; if MA, resp. MB, is not NULL, must be
     172             :  * the matrix of the Frobenius map in FF_l[X]/(P), resp. FF_l[X]/(Q).
     173             :  * Implementation choice:  we assume the prime p is large so we handle
     174             :  * Frobenius as matrices. */
     175             : void
     176       42733 : Flx_ffintersect(GEN P, GEN Q, long n, ulong l,GEN *SP, GEN *SQ, GEN MA, GEN MB)
     177             : {
     178       42733 :   pari_sp ltop = avma;
     179       42733 :   long vp = get_Flx_var(P), vq =  get_Flx_var(Q);
     180       42733 :   long np = get_Flx_degree(P), nq = get_Flx_degree(Q), e;
     181             :   ulong pg;
     182             :   GEN A, B, Ap, Bp;
     183       42734 :   if (np<=0) pari_err_IRREDPOL("FpX_ffintersect", P);
     184       42734 :   if (nq<=0) pari_err_IRREDPOL("FpX_ffintersect", Q);
     185       42734 :   if (n<=0 || np%n || nq%n)
     186           0 :     pari_err_TYPE("FpX_ffintersect [bad degrees]",stoi(n));
     187       42734 :   e = u_lvalrem(n, l, &pg);
     188       42734 :   if(!MA) MA = Flx_matFrobenius(P,l);
     189       42734 :   if(!MB) MB = Flx_matFrobenius(Q,l);
     190       42734 :   A = Ap = pol0_Flx(vp);
     191       42733 :   B = Bp = pol0_Flx(vq);
     192       42733 :   if (pg > 1)
     193             :   {
     194             :     pari_timer T;
     195       39788 :     GEN ipg = utoipos(pg);
     196       39787 :     if (l%pg == 1)
     197             :     { /* more efficient special case */
     198             :       ulong L, z, An, Bn;
     199       20019 :       z = Fl_neg(rootsof1_Fl(pg, l), l);
     200       20019 :       if (DEBUGLEVEL>=4) timer_start(&T);
     201       20019 :       A = Flm_ker(Flm_Fl_add(MA, z, l),l);
     202       20020 :       if (lg(A)!=2) err_Flxq("FpX_ffintersect",P,l);
     203       20020 :       A = Flv_to_Flx(gel(A,1),vp);
     204             : 
     205       20020 :       B = Flm_ker(Flm_Fl_add(MB, z, l),l);
     206       20020 :       if (lg(B)!=2) err_Flxq("FpX_ffintersect",Q,l);
     207       20013 :       B = Flv_to_Flx(gel(B,1),vq);
     208             : 
     209       20013 :       if (DEBUGLEVEL>=4) timer_printf(&T, "FpM_ker");
     210       20013 :       An = Flxq_powu(A,pg,P,l)[2];
     211       20013 :       Bn = Flxq_powu(B,pg,Q,l)[2];
     212       20013 :       if (!Bn) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     213       20013 :       z = Fl_div(An,Bn,l);
     214       20013 :       L = Fl_sqrtn(z, pg, l, NULL);
     215       20013 :       if (L==ULONG_MAX) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     216       20013 :       if (DEBUGLEVEL>=4) timer_printf(&T, "Fp_sqrtn");
     217       20013 :       B = Flx_Fl_mul(B,L,l);
     218             :     }
     219             :     else
     220             :     {
     221             :       GEN L, An, Bn, z, U;
     222       19768 :       U = gmael(Flx_factor(ZX_to_Flx(polcyclo(pg, fetch_var()),l),l),1,1);
     223       19769 :       A = Flx_intersect_ker(P, MA, U, l);
     224       19769 :       B = Flx_intersect_ker(Q, MB, U, l);
     225       19769 :       if (DEBUGLEVEL>=4) timer_start(&T);
     226       19769 :       An = gel(FlxYqq_pow(A,ipg,P,U,l),2);
     227       19769 :       Bn = gel(FlxYqq_pow(B,ipg,Q,U,l),2);
     228       19769 :       if (DEBUGLEVEL>=4) timer_printf(&T,"pows [P,Q]");
     229       19769 :       z = Flxq_div(An,Bn,U,l);
     230       19768 :       L = Flxq_sqrtn(z,ipg,U,l,NULL);
     231       19769 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     232       19769 :       if (DEBUGLEVEL>=4) timer_printf(&T,"FpXQ_sqrtn");
     233       19769 :       B = FlxqX_Flxq_mul(B,L,U,l);
     234       19769 :       A = FlxY_evalx(A,0,l);
     235       19768 :       B = FlxY_evalx(B,0,l);
     236       19769 :       (void)delete_var();
     237             :     }
     238             :   }
     239       42726 :   if (e)
     240             :   {
     241             :     GEN VP, VQ, Ay, By;
     242        3008 :     ulong lmun = l-1;
     243             :     long j;
     244        3008 :     MA = Flm_Fl_add(MA,lmun,l);
     245        3008 :     MB = Flm_Fl_add(MB,lmun,l);
     246        3008 :     Ay = pol1_Flx(vp);
     247        3008 :     By = pol1_Flx(vq);
     248        3008 :     VP = vecsmall_ei(np, 1);
     249        3008 :     VQ = np == nq? VP: vecsmall_ei(nq, 1); /* save memory */
     250        6413 :     for(j=0;j<e;j++)
     251             :     {
     252        3412 :       if (j)
     253             :       {
     254         404 :         Ay = Flxq_mul(Ay,Flxq_powu(Ap,lmun,P,l),P,l);
     255         404 :         VP = Flx_to_Flv(Ay,np);
     256             :       }
     257        3412 :       Ap = Flm_Flc_invimage(MA,VP,l);
     258        3412 :       if (!Ap) err_Flxq("FpX_ffintersect",P,l);
     259        3412 :       Ap = Flv_to_Flx(Ap,vp);
     260             : 
     261        3412 :       if (j)
     262             :       {
     263         404 :         By = Flxq_mul(By,Flxq_powu(Bp,lmun,Q,l),Q,l);
     264         404 :         VQ = Flx_to_Flv(By,nq);
     265             :       }
     266        3412 :       Bp = Flm_Flc_invimage(MB,VQ,l);
     267        3412 :       if (!Bp) err_Flxq("FpX_ffintersect",Q,l);
     268        3405 :       Bp = Flv_to_Flx(Bp,vq);
     269             :     }
     270             :   }
     271       42719 :   *SP = Flx_add(A,Ap,l);
     272       42718 :   *SQ = Flx_add(B,Bp,l);
     273       42717 :   gerepileall(ltop,2,SP,SQ);
     274       42720 : }
     275             : 
     276             : /* Let l be a prime number, P, Q in Z[X]; both are irreducible modulo l and
     277             :  * degree(P) divides degree(Q).  Output a monomorphism between F_l[X]/(P) and
     278             :  * F_l[X]/(Q) as a polynomial R such that Q | P(R) mod l.  If P and Q have the
     279             :  * same degree, it is of course an isomorphism.  */
     280             : GEN
     281        2862 : Flx_ffisom(GEN P,GEN Q,ulong l)
     282             : {
     283        2862 :   pari_sp av = avma;
     284             :   GEN SP, SQ, R;
     285        2862 :   Flx_ffintersect(P,Q,get_Flx_degree(P),l,&SP,&SQ,NULL,NULL);
     286        2862 :   R = Flxq_ffisom_inv(SP,P,l);
     287        2862 :   return gerepileupto(av, Flx_Flxq_eval(R,SQ,Q,l));
     288             : }
     289             : 
     290             : void
     291         308 : FpX_ffintersect(GEN P, GEN Q, long n, GEN l, GEN *SP, GEN *SQ, GEN MA, GEN MB)
     292             : {
     293         308 :   pari_sp ltop = avma;
     294             :   long vp, vq, np, nq, e;
     295             :   ulong pg;
     296             :   GEN A, B, Ap, Bp;
     297         308 :   if (lgefint(l)==3)
     298             :   {
     299           0 :     ulong pp = l[2];
     300           0 :     GEN Pp = ZX_to_Flx(P,pp), Qp = ZX_to_Flx(Q,pp);
     301           0 :     GEN MAp = MA ? ZM_to_Flm(MA, pp): NULL;
     302           0 :     GEN MBp = MB ? ZM_to_Flm(MB, pp): NULL;
     303           0 :     Flx_ffintersect(Pp, Qp, n, pp, SP, SQ, MAp, MBp);
     304           0 :     *SP = Flx_to_ZX(*SP); *SQ = Flx_to_ZX(*SQ);
     305           0 :     gerepileall(ltop,2,SP,SQ);
     306           0 :     return;
     307             :   }
     308         308 :   vp = get_FpX_var(P); np = get_FpX_degree(P);
     309         308 :   vq = get_FpX_var(Q); nq = get_FpX_degree(Q);
     310         308 :   if (np<=0) pari_err_IRREDPOL("FpX_ffintersect", P);
     311         308 :   if (nq<=0) pari_err_IRREDPOL("FpX_ffintersect", Q);
     312         308 :   if (n<=0 || np%n || nq%n)
     313           0 :     pari_err_TYPE("FpX_ffintersect [bad degrees]",stoi(n));
     314         308 :   e = u_pvalrem(n, l, &pg);
     315         308 :   if(!MA) MA = FpX_matFrobenius(P, l);
     316         308 :   if(!MB) MB = FpX_matFrobenius(Q, l);
     317         308 :   A = Ap = pol_0(vp);
     318         308 :   B = Bp = pol_0(vq);
     319         308 :   if (pg > 1)
     320             :   {
     321         308 :     GEN ipg = utoipos(pg);
     322             :     pari_timer T;
     323         308 :     if (umodiu(l,pg) == 1)
     324             :     /* No need to use relative extension, so don't. (Well, now we don't
     325             :      * in the other case either, but this special case is more efficient) */
     326             :     {
     327             :       GEN L, An, Bn, z;
     328         217 :       z = negi( rootsof1u_Fp(pg, l) );
     329         217 :       if (DEBUGLEVEL>=4) timer_start(&T);
     330         217 :       A = FpM_ker(RgM_Rg_add_shallow(MA, z),l);
     331         217 :       if (lg(A)!=2) err_FpXQ("FpX_ffintersect",P,l);
     332         217 :       A = RgV_to_RgX(gel(A,1),vp);
     333             : 
     334         217 :       B = FpM_ker(RgM_Rg_add_shallow(MB, z),l);
     335         217 :       if (lg(B)!=2) err_FpXQ("FpX_ffintersect",Q,l);
     336         217 :       B = RgV_to_RgX(gel(B,1),vq);
     337             : 
     338         217 :       if (DEBUGLEVEL>=4) timer_printf(&T, "FpM_ker");
     339         217 :       An = gel(FpXQ_pow(A,ipg,P,l),2);
     340         217 :       Bn = gel(FpXQ_pow(B,ipg,Q,l),2);
     341         217 :       if (!signe(Bn)) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     342         217 :       z = Fp_div(An,Bn,l);
     343         217 :       L = Fp_sqrtn(z,ipg,l,NULL);
     344         217 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     345         217 :       if (DEBUGLEVEL>=4) timer_printf(&T, "Fp_sqrtn");
     346         217 :       B = FpX_Fp_mul(B,L,l);
     347             :     }
     348             :     else
     349             :     {
     350             :       GEN L, An, Bn, z, U;
     351          91 :       U = gmael(FpX_factor(polcyclo(pg,fetch_var()),l),1,1);
     352          91 :       A = FpX_intersect_ker(P, MA, U, l);
     353          91 :       B = FpX_intersect_ker(Q, MB, U, l);
     354          91 :       if (DEBUGLEVEL>=4) timer_start(&T);
     355          91 :       An = gel(FpXYQQ_pow(A,ipg,P,U,l),2);
     356          91 :       Bn = gel(FpXYQQ_pow(B,ipg,Q,U,l),2);
     357          91 :       if (DEBUGLEVEL>=4) timer_printf(&T,"pows [P,Q]");
     358          91 :       if (!signe(Bn)) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     359          91 :       z = Fq_div(An,Bn,U,l);
     360          91 :       L = Fq_sqrtn(z,ipg,U,l,NULL);
     361          91 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     362          91 :       if (DEBUGLEVEL>=4) timer_printf(&T,"FpXQ_sqrtn");
     363          91 :       B = FqX_Fq_mul(B,L,U,l);
     364          91 :       A = FpXY_evalx(A,gen_0,l);
     365          91 :       B = FpXY_evalx(B,gen_0,l);
     366          91 :       (void)delete_var();
     367             :     }
     368             :   }
     369         308 :   if (e)
     370             :   {
     371           0 :     GEN VP, VQ, Ay, By, lmun = subiu(l,1);
     372             :     long j;
     373           0 :     MA = RgM_Rg_add_shallow(MA,gen_m1);
     374           0 :     MB = RgM_Rg_add_shallow(MB,gen_m1);
     375           0 :     Ay = pol_1(vp);
     376           0 :     By = pol_1(vq);
     377           0 :     VP = col_ei(np, 1);
     378           0 :     VQ = np == nq? VP: col_ei(nq, 1); /* save memory */
     379           0 :     for(j=0;j<e;j++)
     380             :     {
     381           0 :       if (j)
     382             :       {
     383           0 :         Ay = FpXQ_mul(Ay,FpXQ_pow(Ap,lmun,P,l),P,l);
     384           0 :         VP = RgX_to_RgC(Ay,np);
     385             :       }
     386           0 :       Ap = FpM_FpC_invimage(MA,VP,l);
     387           0 :       if (!Ap) err_FpXQ("FpX_ffintersect",P,l);
     388           0 :       Ap = RgV_to_RgX(Ap,vp);
     389             : 
     390           0 :       if (j)
     391             :       {
     392           0 :         By = FpXQ_mul(By,FpXQ_pow(Bp,lmun,Q,l),Q,l);
     393           0 :         VQ = RgX_to_RgC(By,nq);
     394             :       }
     395           0 :       Bp = FpM_FpC_invimage(MB,VQ,l);
     396           0 :       if (!Bp) err_FpXQ("FpX_ffintersect",Q,l);
     397           0 :       Bp = RgV_to_RgX(Bp,vq);
     398             :     }
     399             :   }
     400         308 :   *SP = FpX_add(A,Ap,l);
     401         308 :   *SQ = FpX_add(B,Bp,l);
     402         308 :   gerepileall(ltop,2,SP,SQ);
     403             : }
     404             : /* Let l be a prime number, P, Q in Z[X]; both are irreducible modulo l and
     405             :  * degree(P) divides degree(Q).  Output a monomorphism between F_l[X]/(P) and
     406             :  * F_l[X]/(Q) as a polynomial R such that Q | P(R) mod l.  If P and Q have the
     407             :  * same degree, it is of course an isomorphism.  */
     408             : GEN
     409        2820 : FpX_ffisom(GEN P, GEN Q, GEN p)
     410             : {
     411        2820 :   pari_sp av = avma;
     412             :   GEN SP, SQ, R;
     413        2820 :   if (lgefint(p)==3)
     414             :   {
     415        2820 :     ulong pp = p[2];
     416        2820 :     GEN R = Flx_ffisom(ZX_to_Flx(P,pp), ZX_to_Flx(Q,pp), pp);
     417        2820 :     return gerepileupto(av, Flx_to_ZX(R));
     418             :   }
     419           0 :   FpX_ffintersect(P,Q,get_FpX_degree(P),p,&SP,&SQ,NULL,NULL);
     420           0 :   R = FpXQ_ffisom_inv(SP,P,p);
     421           0 :   return gerepileupto(av, FpX_FpXQ_eval(R,SQ,Q,p));
     422             : }
     423             : 
     424             : /* Let l be a prime number, P a ZX irreducible modulo l, MP the matrix of the
     425             :  * Frobenius automorphism of F_l[X]/(P).
     426             :  * Factor P over the subfield of F_l[X]/(P) of index d. */
     427             : static GEN
     428         308 : FpX_factorgalois(GEN P, GEN l, long d, long w, GEN MP)
     429             : {
     430         308 :   pari_sp ltop = avma;
     431             :   GEN R, V, Tl, z, M;
     432         308 :   long v = get_FpX_var(P), n = get_FpX_degree(P);
     433         308 :   long k, m = n/d;
     434             : 
     435             :   /* x - y */
     436         308 :   if (m == 1) return deg1pol_shallow(gen_1, deg1pol_shallow(subis(l,1), gen_0, w), v);
     437          35 :   M = FpM_Frobenius_pow(MP,d,P,l);
     438             : 
     439          35 :   Tl = leafcopy(P); setvarn(Tl,w);
     440          35 :   V = cgetg(m+1,t_VEC);
     441          35 :   gel(V,1) = pol_x(w);
     442          35 :   z = gel(M,2);
     443          35 :   gel(V,2) = RgV_to_RgX(z,w);
     444          77 :   for(k=3;k<=m;k++)
     445             :   {
     446          42 :     z = FpM_FpC_mul(M,z,l);
     447          42 :     gel(V,k) = RgV_to_RgX(z,w);
     448             :   }
     449          35 :   R = FqV_roots_to_pol(V,Tl,l,v);
     450          35 :   return gerepileupto(ltop,R);
     451             : }
     452             : /* same: P is an Flx, MP an Flm */
     453             : static GEN
     454       39858 : Flx_factorgalois(GEN P, ulong l, long d, long w, GEN MP)
     455             : {
     456       39858 :   pari_sp ltop = avma;
     457             :   GEN R, V, Tl, z, M;
     458       39858 :   long k, n = get_Flx_degree(P), m = n/d;
     459       39858 :   long v = get_Flx_var(P);
     460             : 
     461       39858 :   if (m == 1) {
     462       39459 :     R = polx_Flx(v);
     463       39459 :     gel(R,2) = z = polx_Flx(w); z[3] = l - 1; /* - y */
     464       39459 :     gel(R,3) = pol1_Flx(w);
     465       39459 :     return R; /* x - y */
     466             :   }
     467         399 :   M = Flm_Frobenius_pow(MP,d,P,l);
     468             : 
     469         399 :   Tl = leafcopy(P); Tl[1] = w;
     470         399 :   V = cgetg(m+1,t_VEC);
     471         399 :   gel(V,1) = polx_Flx(w);
     472         399 :   z = gel(M,2);
     473         399 :   gel(V,2) = Flv_to_Flx(z,w);
     474         700 :   for(k=3;k<=m;k++)
     475             :   {
     476         301 :     z = Flm_Flc_mul(M,z,l);
     477         301 :     gel(V,k) = Flv_to_Flx(z,w);
     478             :   }
     479         399 :   R = FlxqV_roots_to_pol(V,Tl,l,v);
     480         399 :   return gerepileupto(ltop,R);
     481             : }
     482             : 
     483             : GEN
     484      108157 : Flx_factorff_irred(GEN P, GEN Q, ulong p)
     485             : {
     486      108157 :   pari_sp ltop = avma, av;
     487             :   GEN SP, SQ, MP, MQ, M, FP, FQ, E, V, IR, res;
     488      108157 :   long np = get_Flx_degree(P), nq = get_Flx_degree(Q), d = ugcd(np,nq);
     489      108156 :   long i, vp = get_Flx_var(P), vq = get_Flx_var(Q);
     490      108156 :   if (d==1) retmkcol(Flx_to_FlxX(P, vq));
     491       39871 :   FQ = Flx_matFrobenius(Q,p);
     492       39871 :   av = avma;
     493       39871 :   FP = Flx_matFrobenius(P,p);
     494       39871 :   Flx_ffintersect(P,Q,d,p,&SP,&SQ, FP, FQ);
     495       39858 :   E = Flx_factorgalois(P,p,d,vq, FP);
     496       39858 :   E = FlxX_to_Flm(E,np);
     497       39856 :   MP= Flxq_matrix_pow(SP,np,d,P,p);
     498       39857 :   IR= gel(Flm_indexrank(MP,p),1);
     499       39857 :   E = rowpermute(E, IR);
     500       39858 :   M = rowpermute(MP,IR);
     501       39858 :   M = Flm_inv(M,p);
     502       39857 :   MQ= Flxq_matrix_pow(SQ,nq,d,Q,p);
     503       39855 :   M = Flm_mul(MQ,M,p);
     504       39856 :   M = Flm_mul(M,E,p);
     505       39855 :   M = gerepileupto(av,M);
     506       39858 :   V = cgetg(d+1,t_VEC);
     507       39857 :   gel(V,1) = M;
     508      174758 :   for(i=2;i<=d;i++)
     509      134900 :     gel(V,i) = Flm_mul(FQ,gel(V,i-1),p);
     510       39858 :   res = cgetg(d+1,t_COL);
     511      214606 :   for(i=1;i<=d;i++)
     512      174752 :     gel(res,i) = Flm_to_FlxX(gel(V,i),vp,vq);
     513       39854 :   return gerepileupto(ltop,res);
     514             : }
     515             : 
     516             : /* P,Q irreducible over F_p. Factor P over FF_p[X] / Q  [factors are ordered as
     517             :  * a Frobenius cycle] */
     518             : GEN
     519       32830 : FpX_factorff_irred(GEN P, GEN Q, GEN p)
     520             : {
     521       32830 :   pari_sp ltop = avma, av;
     522             :   GEN res;
     523       32830 :   long np = get_FpX_degree(P), nq = get_FpX_degree(Q), d = ugcd(np,nq);
     524       32830 :   if (d==1) return mkcolcopy(P);
     525             : 
     526       32788 :   if (lgefint(p)==3)
     527             :   {
     528       32480 :     ulong pp = p[2];
     529       32480 :     GEN F = Flx_factorff_irred(ZX_to_Flx(P,pp), ZX_to_Flx(Q,pp), pp);
     530       32480 :     long i, lF = lg(F);
     531       32480 :     res = cgetg(lF, t_COL);
     532      182655 :     for(i=1; i<lF; i++)
     533      150175 :       gel(res,i) = FlxX_to_ZXX(gel(F,i));
     534             :   }
     535             :   else
     536             :   {
     537             :     GEN SP, SQ, MP, MQ, M, FP, FQ, E, V, IR;
     538         308 :     long i, vp = get_FpX_var(P), vq = get_FpX_var(Q);
     539         308 :     FQ = FpX_matFrobenius(Q,p);
     540         308 :     av = avma;
     541         308 :     FP = FpX_matFrobenius(P,p);
     542         308 :     FpX_ffintersect(P,Q,d,p,&SP,&SQ,FP,FQ);
     543             : 
     544         308 :     E = FpX_factorgalois(P,p,d,vq,FP);
     545         308 :     E = RgXX_to_RgM(E,np);
     546         308 :     MP= FpXQ_matrix_pow(SP,np,d,P,p);
     547         308 :     IR= gel(FpM_indexrank(MP,p),1);
     548         308 :     E = rowpermute(E, IR);
     549         308 :     M = rowpermute(MP,IR);
     550         308 :     M = FpM_inv(M,p);
     551         308 :     MQ= FpXQ_matrix_pow(SQ,nq,d,Q,p);
     552         308 :     M = FpM_mul(MQ,M,p);
     553         308 :     M = FpM_mul(M,E,p);
     554         308 :     M = gerepileupto(av,M);
     555         308 :     V = cgetg(d+1,t_VEC);
     556         308 :     gel(V,1) = M;
     557        1022 :     for(i=2;i<=d;i++)
     558         714 :       gel(V,i) = FpM_mul(FQ,gel(V,i-1),p);
     559         308 :     res = cgetg(d+1,t_COL);
     560        1330 :     for(i=1;i<=d;i++)
     561        1022 :       gel(res,i) = RgM_to_RgXX(gel(V,i),vp,vq);
     562             :   }
     563       32788 :   return gerepilecopy(ltop,res);
     564             : }
     565             : 
     566             : /* not memory-clean, as Flx_factorff_i, returning only linear factors */
     567             : static GEN
     568       27286 : Flx_rootsff_i(GEN P, GEN T, ulong p)
     569             : {
     570       27286 :   GEN V, F = gel(Flx_factor(P,p), 1);
     571       27286 :   long i, lfact = 1, nmax = lgpol(P), n = lg(F), dT = get_Flx_degree(T);
     572             : 
     573       27286 :   V = cgetg(nmax,t_COL);
     574       58310 :   for(i=1;i<n;i++)
     575             :   {
     576       31024 :     GEN R, Fi = gel(F,i);
     577       31024 :     long di = degpol(Fi), j, r;
     578       31024 :     if (dT % di) continue;
     579       29309 :     R = Flx_factorff_irred(gel(F,i),T,p);
     580       29309 :     r = lg(R);
     581       73073 :     for (j=1; j<r; j++,lfact++)
     582       43764 :       gel(V,lfact) = Flx_neg(gmael(R,j, 2), p);
     583             :   }
     584       27286 :   setlg(V,lfact);
     585       27286 :   gen_sort_inplace(V, (void*) &cmp_Flx, &cmp_nodata, NULL);
     586       27286 :   return V;
     587             : }
     588             : GEN
     589           0 : Flx_rootsff(GEN P, GEN T, ulong p)
     590             : {
     591           0 :   pari_sp av = avma;
     592           0 :   return gerepilecopy(av, Flx_rootsff_i(P, T, p));
     593             : }
     594             : 
     595             : /* dummy implementation */
     596             : static GEN
     597       16478 : F2x_rootsff_i(GEN P, GEN T)
     598             : {
     599       16478 :   return FlxC_to_F2xC(Flx_rootsff_i(F2x_to_Flx(P), F2x_to_Flx(T), 2UL));
     600             : }
     601             : 
     602             : /* not memory-clean, as FpX_factorff_i, returning only linear factors */
     603             : static GEN
     604         294 : FpX_rootsff_i(GEN P, GEN T, GEN p)
     605             : {
     606             :   GEN V, F;
     607             :   long i, lfact, nmax, n, dT;
     608         294 :   if (lgefint(p)==3)
     609             :   {
     610           0 :     ulong pp = p[2];
     611           0 :     GEN V = Flx_rootsff_i(ZX_to_Flx(P,pp), ZXT_to_FlxT(T,pp), pp);
     612           0 :     return FlxC_to_ZXC(V);
     613             :   }
     614         294 :   F = gel(FpX_factor(P,p), 1);
     615         294 :   lfact = 1; nmax = lgpol(P); n = lg(F); dT = get_FpX_degree(T);
     616             : 
     617         294 :   V = cgetg(nmax,t_COL);
     618         588 :   for(i=1;i<n;i++)
     619             :   {
     620         294 :     GEN R, Fi = gel(F,i);
     621         294 :     long di = degpol(Fi), j, r;
     622         294 :     if (dT % di) continue;
     623         294 :     R = FpX_factorff_irred(gel(F,i),T,p);
     624         294 :     r = lg(R);
     625        1190 :     for (j=1; j<r; j++,lfact++)
     626         896 :       gel(V,lfact) = Fq_to_FpXQ(Fq_neg(gmael(R,j, 2), T, p), T, p);
     627             :   }
     628         294 :   setlg(V,lfact);
     629         294 :   gen_sort_inplace(V, (void*) &cmp_RgX, &cmp_nodata, NULL);
     630         294 :   return V;
     631             : }
     632             : GEN
     633           0 : FpX_rootsff(GEN P, GEN T, GEN p)
     634             : {
     635           0 :   pari_sp av = avma;
     636           0 :   return gerepilecopy(av, FpX_rootsff_i(P, T, p));
     637             : }
     638             : 
     639             : static GEN
     640       11843 : Flx_factorff_i(GEN P, GEN T, ulong p)
     641             : {
     642       11843 :   GEN V, E, F = Flx_factor(P, p);
     643       11844 :   long i, lfact = 1, nmax = lgpol(P), n = lgcols(F);
     644             : 
     645       11844 :   V = cgetg(nmax,t_VEC);
     646       11844 :   E = cgetg(nmax,t_VECSMALL);
     647       58198 :   for(i=1;i<n;i++)
     648             :   {
     649       46368 :     GEN R = Flx_factorff_irred(gmael(F,1,i),T,p), e = gmael(F,2,i);
     650       46353 :     long j, r = lg(R);
     651       95458 :     for (j=1; j<r; j++,lfact++)
     652             :     {
     653       49105 :       gel(V,lfact) = gel(R,j);
     654       49105 :       gel(E,lfact) = e;
     655             :     }
     656             :   }
     657       11830 :   setlg(V,lfact);
     658       11830 :   setlg(E,lfact); return sort_factor_pol(mkvec2(V,E), cmp_Flx);
     659             : }
     660             : 
     661             : static long
     662        7084 : simpleff_to_nbfact(GEN F, long dT)
     663             : {
     664        7084 :   long i, l = lg(F), k = 0;
     665       90146 :   for (i = 1; i < l; i++) k += ugcd(uel(F,i), dT);
     666        7084 :   return k;
     667             : }
     668             : 
     669             : static long
     670        7084 : Flx_nbfactff(GEN P, GEN T, ulong p)
     671             : {
     672        7084 :   pari_sp av = avma;
     673        7084 :   GEN F = gel(Flx_degfact(P, p), 1);
     674        7084 :   long s = simpleff_to_nbfact(F, get_Flx_degree(T));
     675        7084 :   return gc_long(av,s);
     676             : }
     677             : 
     678             : /* dummy implementation */
     679             : static GEN
     680         462 : F2x_factorff_i(GEN P, GEN T)
     681             : {
     682         462 :   GEN M = Flx_factorff_i(F2x_to_Flx(P), F2x_to_Flx(T), 2);
     683         455 :   return mkvec2(FlxXC_to_F2xXC(gel(M,1)), gel(M,2));
     684             : }
     685             : 
     686             : /* not memory-clean */
     687             : static GEN
     688          56 : FpX_factorff_i(GEN P, GEN T, GEN p)
     689             : {
     690          56 :   GEN V, E, F = FpX_factor(P,p);
     691          56 :   long i, lfact = 1, nmax = lgpol(P), n = lgcols(F);
     692             : 
     693          56 :   V = cgetg(nmax,t_VEC);
     694          56 :   E = cgetg(nmax,t_VECSMALL);
     695         112 :   for(i=1;i<n;i++)
     696             :   {
     697          56 :     GEN R = FpX_factorff_irred(gmael(F,1,i),T,p), e = gmael(F,2,i);
     698          56 :     long j, r = lg(R);
     699         224 :     for (j=1; j<r; j++,lfact++)
     700             :     {
     701         168 :       gel(V,lfact) = gel(R,j);
     702         168 :       gel(E,lfact) = e;
     703             :     }
     704             :   }
     705          56 :   setlg(V,lfact);
     706          56 :   setlg(E,lfact); return sort_factor_pol(mkvec2(V,E), cmp_RgX);
     707             : }
     708             : 
     709             : static long
     710           0 : FpX_nbfactff(GEN P, GEN T, GEN p)
     711             : {
     712           0 :   pari_sp av = avma;
     713           0 :   GEN F = gel(FpX_degfact(P, p), 1);
     714           0 :   long s = simpleff_to_nbfact(F, get_FpX_degree(T));
     715           0 :   return gc_long(av,s);
     716             : }
     717             : 
     718             : GEN
     719           0 : FpX_factorff(GEN P, GEN T, GEN p)
     720             : {
     721           0 :   pari_sp av = avma;
     722           0 :   return gerepilecopy(av, FpX_factorff_i(P, T, p));
     723             : }
     724             : 
     725             : /***********************************************************************/
     726             : /**                                                                   **/
     727             : /**               Factorisation over finite fields                    **/
     728             : /**                                                                   **/
     729             : /***********************************************************************/
     730             : 
     731             : static GEN
     732       10968 : FlxqXQ_halfFrobenius_i(GEN a, GEN xp, GEN Xp, GEN S, GEN T, ulong p)
     733             : {
     734       10968 :   GEN ap2 = FlxqXQ_powu(a, p>>1, S, T, p);
     735       10968 :   GEN V = FlxqXQ_autsum(mkvec3(xp, Xp, ap2), get_Flx_degree(T), S, T, p);
     736       10968 :   return gel(V,3);
     737             : }
     738             : 
     739             : GEN
     740         292 : FlxqXQ_halfFrobenius(GEN a, GEN S, GEN T, ulong p)
     741             : {
     742         292 :   long vT = get_Flx_var(T);
     743             :   GEN xp, Xp;
     744         292 :   T = Flx_get_red(T, p);
     745         292 :   S = FlxqX_get_red(S, T, p);
     746         292 :   xp = Flx_Frobenius(T, p);
     747         292 :   Xp = FlxqXQ_powu(polx_FlxX(get_FlxqX_var(S), vT), p, S, T, p);
     748         292 :   return FlxqXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
     749             : }
     750             : 
     751             : static GEN
     752        1120 : FpXQXQ_halfFrobenius_i(GEN a, GEN xp, GEN Xp, GEN S, GEN T, GEN p)
     753             : {
     754        1120 :   GEN ap2 = FpXQXQ_pow(a, shifti(p,-1), S, T, p);
     755        1120 :   GEN V = FpXQXQ_autsum(mkvec3(xp, Xp, ap2), get_FpX_degree(T), S, T, p);
     756        1120 :   return gel(V, 3);
     757             : }
     758             : 
     759             : GEN
     760         145 : FpXQXQ_halfFrobenius(GEN a, GEN S, GEN T, GEN p)
     761             : {
     762         145 :   pari_sp av = avma;
     763             :   GEN z;
     764         145 :   if (lgefint(p)==3)
     765             :   {
     766          73 :     ulong pp = p[2];
     767          73 :     long v = get_FpX_var(T);
     768          73 :     GEN Tp = ZXT_to_FlxT(T,pp), Sp = ZXXT_to_FlxXT(S, pp, v);
     769          73 :     z = FlxX_to_ZXX(FlxqXQ_halfFrobenius(ZXX_to_FlxX(a,pp,v),Sp,Tp,pp));
     770             :   }
     771             :   else
     772             :   {
     773             :     GEN xp, Xp;
     774          72 :     T = FpX_get_red(T, p);
     775          72 :     S = FpXQX_get_red(S, T, p);
     776          72 :     xp = FpX_Frobenius(T, p);
     777          72 :     Xp = FpXQXQ_pow(pol_x(get_FpXQX_var(S)), p, S, T, p);
     778          72 :     z = FpXQXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
     779             :   }
     780         145 :   return gerepilecopy(av, z);
     781             : }
     782             : 
     783             : static GEN
     784       63693 : FlxqXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T, ulong p)
     785             : {
     786       63693 :   ulong dT = get_Flx_degree(T), df = get_FlxqX_degree(f);
     787       63693 :   GEN q = powuu(p,dT);
     788       63693 :   if (expi(q) >= expu(dT)*(long)usqrt(df))
     789       63651 :     return gel(FlxqXQ_autpow(mkvec2(xp, Xp), dT, f, T, p), 2);
     790             :   else
     791          42 :     return FlxqXQ_pow(pol_x(get_FlxqX_var(f)), q, f, T, p);
     792             : }
     793             : 
     794             : GEN
     795        5092 : FlxqX_Frobenius(GEN S, GEN T, ulong p)
     796             : {
     797        5092 :   pari_sp av = avma;
     798        5092 :   GEN X  = polx_FlxX(get_FlxqX_var(S), get_Flx_var(T));
     799        5092 :   GEN xp = Flx_Frobenius(T, p);
     800        5092 :   GEN Xp = FlxqXQ_powu(X, p, S, T, p);
     801        5092 :   GEN Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
     802        5092 :   return gerepilecopy(av, Xq);
     803             : }
     804             : 
     805             : static GEN
     806         231 : FpXQXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T, GEN p)
     807             : {
     808         231 :   ulong dT = get_FpX_degree(T), df = get_FpXQX_degree(f);
     809         231 :   GEN q = powiu(p, dT);
     810         231 :   if (expi(q) >= expu(dT)*(long)usqrt(df))
     811         231 :     return gel(FpXQXQ_autpow(mkvec2(xp, Xp), dT, f, T, p), 2);
     812             :   else
     813           0 :     return FpXQXQ_pow(pol_x(get_FpXQX_var(f)), q, f, T, p);
     814             : }
     815             : 
     816             : GEN
     817         179 : FpXQX_Frobenius(GEN S, GEN T, GEN p)
     818             : {
     819         179 :   pari_sp av = avma;
     820         179 :   GEN X  = pol_x(get_FpXQX_var(S));
     821         179 :   GEN xp = FpX_Frobenius(T, p);
     822         179 :   GEN Xp = FpXQXQ_pow(X, p, S, T, p);
     823         179 :   GEN Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
     824         179 :   return gerepilecopy(av, Xq);
     825             : }
     826             : 
     827             : static GEN
     828       70693 : F2xqXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T)
     829             : {
     830       70693 :   ulong dT = get_F2x_degree(T), df = get_F2xqX_degree(f);
     831       70693 :   if (dT >= expu(dT)*usqrt(df))
     832       70686 :     return gel(F2xqXQ_autpow(mkvec2(xp, Xp), dT, f, T), 2);
     833             :   else
     834             :   {
     835           7 :     long v = get_F2xqX_var(f), vT = get_F2x_var(T);
     836           7 :     return F2xqXQ_pow(polx_F2xX(v,vT), int2n(dT), f, T);
     837             :   }
     838             : }
     839             : 
     840             : static GEN
     841        4514 : FlxqX_split_part(GEN f, GEN T, ulong p)
     842             : {
     843        4514 :   long n = degpol(f);
     844        4514 :   GEN z, Xq, X = polx_FlxX(varn(f),get_Flx_var(T));
     845        4514 :   if (n <= 1) return f;
     846        4514 :   f = FlxqX_red(f, T, p);
     847        4514 :   Xq = FlxqX_Frobenius(f, T, p);
     848        4514 :   z = FlxX_sub(Xq, X , p);
     849        4514 :   return FlxqX_gcd(z, f, T, p);
     850             : }
     851             : 
     852             : GEN
     853         938 : FpXQX_split_part(GEN f, GEN T, GEN p)
     854             : {
     855         938 :   if(lgefint(p)==3)
     856             :   {
     857         930 :     ulong pp=p[2];
     858         930 :     GEN Tp = ZXT_to_FlxT(T, pp);
     859         930 :     GEN z = FlxqX_split_part(ZXX_to_FlxX(f, pp, get_Flx_var(T)), Tp, pp);
     860         930 :     return FlxX_to_ZXX(z);
     861             :   } else
     862             :   {
     863           8 :     long n = degpol(f);
     864           8 :     GEN z, X = pol_x(varn(f));
     865           8 :     if (n <= 1) return f;
     866           8 :     f = FpXQX_red(f, T, p);
     867           8 :     z = FpXQX_Frobenius(f, T, p);
     868           8 :     z = FpXX_sub(z, X , p);
     869           8 :     return FpXQX_gcd(z, f, T, p);
     870             :   }
     871             : }
     872             : 
     873             : long
     874         882 : FpXQX_nbroots(GEN f, GEN T, GEN p)
     875             : {
     876         882 :   pari_sp av = avma;
     877         882 :   GEN z = FpXQX_split_part(f, T, p);
     878         882 :   return gc_long(av, degpol(z));
     879             : }
     880             : 
     881             : long
     882       83223 : FqX_nbroots(GEN f, GEN T, GEN p)
     883       83223 : { return T ? FpXQX_nbroots(f, T, p): FpX_nbroots(f, p); }
     884             : 
     885             : long
     886        3584 : FlxqX_nbroots(GEN f, GEN T, ulong p)
     887             : {
     888        3584 :   pari_sp av = avma;
     889        3584 :   GEN z = FlxqX_split_part(f, T, p);
     890        3584 :   return gc_long(av, degpol(z));
     891             : }
     892             : 
     893             : static GEN
     894           0 : FlxqX_Berlekamp_ker_i(GEN Xq, GEN S, GEN T, ulong p)
     895             : {
     896           0 :   long j, N = get_FlxqX_degree(S);
     897           0 :   GEN Q  = FlxqXQ_matrix_pow(Xq,N,N,S,T,p);
     898           0 :   for (j=1; j<=N; j++)
     899           0 :     gcoeff(Q,j,j) = Flx_Fl_add(gcoeff(Q,j,j), p-1, p);
     900           0 :   return FlxqM_ker(Q,T,p);
     901             : }
     902             : 
     903             : static GEN
     904           0 : FpXQX_Berlekamp_ker_i(GEN Xq, GEN S, GEN T, GEN p)
     905             : {
     906           0 :   long j,N = get_FpXQX_degree(S);
     907           0 :   GEN Q  = FpXQXQ_matrix_pow(Xq,N,N,S,T,p);
     908           0 :   for (j=1; j<=N; j++)
     909           0 :     gcoeff(Q,j,j) = Fq_sub(gcoeff(Q,j,j), gen_1, T, p);
     910           0 :   return FqM_ker(Q,T,p);
     911             : }
     912             : 
     913             : static long
     914        2388 : isabsolutepol(GEN f)
     915             : {
     916        2388 :   long i, l = lg(f);
     917        4159 :   for(i=2; i<l; i++)
     918             :   {
     919        3809 :     GEN c = gel(f,i);
     920        3809 :     if (typ(c) == t_POL && degpol(c) > 0) return 0;
     921             :   }
     922         350 :   return 1;
     923             : }
     924             : 
     925             : #define set_irred(i) { if ((i)>ir) swap(t[i],t[ir]); ir++;}
     926             : 
     927             : static long
     928           0 : FlxqX_split_Berlekamp(GEN *t, GEN xp, GEN T, ulong p)
     929             : {
     930           0 :   GEN u = *t, a,b,vker,pol;
     931           0 :   long vu = varn(u), vT = get_Flx_var(T), dT = get_Flx_degree(T);
     932             :   long d, i, ir, L, la, lb;
     933             :   GEN S, X, Xp, Xq;
     934           0 :   if (degpol(u)==1) return 1;
     935           0 :   T = Flx_get_red(T, p);
     936           0 :   S = FlxqX_get_red(u, T, p);
     937           0 :   X  = polx_FlxX(get_FlxqX_var(S),get_Flx_var(T));
     938           0 :   Xp = FlxqXQ_powu(X, p, S, T, p);
     939           0 :   Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
     940           0 :   vker = FlxqX_Berlekamp_ker_i(Xq, S, T, p);
     941           0 :   vker = Flm_to_FlxV(vker,u[1]);
     942           0 :   d = lg(vker)-1;
     943           0 :   ir = 0;
     944             :   /* t[i] irreducible for i < ir, still to be treated for i < L */
     945           0 :   for (L=1; L<d; )
     946             :   {
     947           0 :     pol= scalarpol(random_Flx(dT,vT,p),vu);
     948           0 :     for (i=2; i<=d; i++)
     949           0 :       pol = FlxX_add(pol, FlxqX_Flxq_mul(gel(vker,i),
     950             :                                          random_Flx(dT,vT,p), T, p), p);
     951           0 :     pol = FlxqX_red(pol,T,p);
     952           0 :     for (i=ir; i<L && L<d; i++)
     953             :     {
     954           0 :       a = t[i]; la = degpol(a);
     955           0 :       if (la == 1) { set_irred(i); }
     956             :       else
     957             :       {
     958           0 :         pari_sp av = avma;
     959           0 :         GEN S = FlxqX_get_red(a, T, p);
     960           0 :         b = FlxqX_rem(pol, S, T,p);
     961           0 :         if (degpol(b)<=0) { set_avma(av); continue; }
     962           0 :         b = FlxqXQ_halfFrobenius_i(b, xp, FlxqX_rem(Xp, S, T, p), S, T, p);
     963           0 :         if (degpol(b)<=0) { set_avma(av); continue; }
     964           0 :         gel(b,2) = Flxq_sub(gel(b,2), gen_1,T,p);
     965           0 :         b = FlxqX_gcd(a,b, T,p); lb = degpol(b);
     966           0 :         if (lb && lb < la)
     967             :         {
     968           0 :           b = FlxqX_normalize(b, T,p);
     969           0 :           t[L] = FlxqX_div(a,b,T,p);
     970           0 :           t[i]= b; L++;
     971             :         }
     972           0 :         else set_avma(av);
     973             :       }
     974             :     }
     975             :   }
     976           0 :   return d;
     977             : }
     978             : 
     979             : static long
     980           0 : FpXQX_split_Berlekamp(GEN *t, GEN T, GEN p)
     981             : {
     982           0 :   GEN u = *t, a, b, vker, pol;
     983             :   GEN X, xp, Xp, Xq, S;
     984           0 :   long vu = varn(u), vT = get_FpX_var(T), dT = get_FpX_degree(T);
     985             :   long d, i, ir, L, la, lb;
     986           0 :   if (degpol(u)==1) return 1;
     987           0 :   T = FpX_get_red(T, p);
     988           0 :   xp = FpX_Frobenius(T, p);
     989           0 :   S = FpXQX_get_red(u, T, p);
     990           0 :   X  = pol_x(get_FpXQX_var(S));
     991           0 :   Xp = FpXQXQ_pow(X, p, S, T, p);
     992           0 :   Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
     993           0 :   vker = FpXQX_Berlekamp_ker_i(Xq, S, T, p);
     994           0 :   vker = RgM_to_RgXV(vker,vu);
     995           0 :   d = lg(vker)-1;
     996           0 :   ir = 0;
     997             :   /* t[i] irreducible for i < ir, still to be treated for i < L */
     998           0 :   for (L=1; L<d; )
     999             :   {
    1000           0 :     pol= scalarpol(random_FpX(dT,vT,p),vu);
    1001           0 :     for (i=2; i<=d; i++)
    1002           0 :       pol = FqX_add(pol, FqX_Fq_mul(gel(vker,i),
    1003             :                                     random_FpX(dT,vT,p), T, p), T, p);
    1004           0 :     pol = FpXQX_red(pol,T,p);
    1005           0 :     for (i=ir; i<L && L<d; i++)
    1006             :     {
    1007           0 :       a = t[i]; la = degpol(a);
    1008           0 :       if (la == 1) { set_irred(i); }
    1009             :       else
    1010             :       {
    1011           0 :         pari_sp av = avma;
    1012           0 :         GEN S = FpXQX_get_red(a, T, p);
    1013           0 :         b = FqX_rem(pol, S, T,p);
    1014           0 :         if (degpol(b)<=0) { set_avma(av); continue; }
    1015           0 :         b = FpXQXQ_halfFrobenius_i(b, xp, FpXQX_rem(Xp, S, T, p), S, T, p);
    1016           0 :         if (degpol(b)<=0) { set_avma(av); continue; }
    1017           0 :         gel(b,2) = Fq_sub(gel(b,2), gen_1,T,p);
    1018           0 :         b = FqX_gcd(a,b, T,p); lb = degpol(b);
    1019           0 :         if (lb && lb < la)
    1020             :         {
    1021           0 :           b = FpXQX_normalize(b, T,p);
    1022           0 :           t[L] = FqX_div(a,b,T,p);
    1023           0 :           t[i]= b; L++;
    1024             :         }
    1025           0 :         else set_avma(av);
    1026             :       }
    1027             :     }
    1028             :   }
    1029           0 :   return d;
    1030             : }
    1031             : 
    1032             : static GEN
    1033       11410 : F2xqX_quad_roots(GEN P, GEN T)
    1034             : {
    1035       11410 :   GEN b= gel(P,3), c = gel(P,2);
    1036       11410 :   if (lgpol(b))
    1037             :   {
    1038       10185 :     GEN z, d = F2xq_div(c, F2xq_sqr(b,T),T);
    1039       10185 :     if (F2xq_trace(d,T))
    1040        1015 :       return cgetg(1, t_COL);
    1041        9170 :     z = F2xq_mul(b, F2xq_Artin_Schreier(d, T), T);
    1042        9170 :     return mkcol2(z, F2x_add(b, z));
    1043             :   }
    1044             :   else
    1045        1225 :     return mkcol(F2xq_sqrt(c, T));
    1046             : }
    1047             : 
    1048             : /* Assume p>2 and x monic */
    1049             : static GEN
    1050       13839 : FlxqX_quad_roots(GEN x, GEN T, ulong p)
    1051             : {
    1052       13839 :   GEN s, D, nb, b = gel(x,3), c = gel(x,2);
    1053       13839 :   D = Flx_sub(Flxq_sqr(b,T,p), Flx_mulu(c,4,p), p);
    1054       13839 :   nb = Flx_neg(b,p);
    1055       13839 :   if (lgpol(D)==0)
    1056          42 :     return mkcol(Flx_halve(nb, p));
    1057       13797 :   s = Flxq_sqrt(D,T,p);
    1058       13797 :   if (!s) return cgetg(1, t_COL);
    1059       13335 :   s = Flx_halve(Flx_add(s,nb,p),p);
    1060       13335 :   return mkcol2(s, Flx_sub(nb,s,p));
    1061             : }
    1062             : 
    1063             : static GEN
    1064         677 : FpXQX_quad_roots(GEN x, GEN T, GEN p)
    1065             : {
    1066         677 :   GEN s, D, nb, b = gel(x,3), c = gel(x,2);
    1067         677 :   if (absequaliu(p, 2))
    1068             :   {
    1069           0 :     GEN f2 = ZXX_to_F2xX(x, get_FpX_var(T));
    1070           0 :     s = F2xqX_quad_roots(f2, ZX_to_F2x(get_FpX_mod(T)));
    1071           0 :     return F2xC_to_ZXC(s);
    1072             :   }
    1073         677 :   D = Fq_sub(Fq_sqr(b,T,p), Fq_Fp_mul(c,utoi(4),T,p), T,p);
    1074         677 :   nb = Fq_neg(b,T,p);
    1075         677 :   if (signe(D)==0)
    1076           0 :     return mkcol(Fq_to_FpXQ(Fq_halve(nb,T, p),T,p));
    1077         677 :   s = Fq_sqrt(D,T,p);
    1078         677 :   if (!s) return cgetg(1, t_COL);
    1079         663 :   s = Fq_halve(Fq_add(s,nb,T,p),T, p);
    1080         663 :   return mkcol2(Fq_to_FpXQ(s,T,p), Fq_to_FpXQ(Fq_sub(nb,s,T,p),T,p));
    1081             : }
    1082             : 
    1083             : static GEN
    1084        9296 : F2xqX_Frobenius_deflate(GEN S, GEN T)
    1085             : {
    1086        9296 :   GEN F = RgX_deflate(S, 2);
    1087        9296 :   long i, l = lg(F);
    1088       33278 :   for (i=2; i<l; i++)
    1089       23982 :     gel(F,i) = F2xq_sqrt(gel(F,i), T);
    1090        9296 :   return F;
    1091             : }
    1092             : 
    1093             : static GEN
    1094       16940 : F2xX_to_F2x(GEN x)
    1095             : {
    1096       16940 :   long l=nbits2lg(lgpol(x));
    1097       16940 :   GEN z=cgetg(l,t_VECSMALL);
    1098             :   long i,j,k;
    1099       16940 :   z[1]=x[1];
    1100       64099 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
    1101             :   {
    1102       47159 :     if (j==BITS_IN_LONG)
    1103             :     {
    1104       16967 :       j=0; k++; z[k]=0;
    1105             :     }
    1106       47159 :     if (lgpol(gel(x,i)))
    1107       34230 :       z[k]|=1UL<<j;
    1108             :   }
    1109       16940 :   return F2x_renormalize(z,l);
    1110             : }
    1111             : 
    1112             : static GEN
    1113      206241 : F2xqX_easyroots(GEN f, GEN T)
    1114             : {
    1115      206241 :   if (F2xY_degreex(f) <= 0) return F2x_rootsff_i(F2xX_to_F2x(f), T);
    1116      189763 :   if (degpol(f)==1) return mkcol(constant_coeff(f));
    1117      154455 :   if (degpol(f)==2) return F2xqX_quad_roots(f,T);
    1118      143528 :   return NULL;
    1119             : }
    1120             : 
    1121             : /* Adapted from Shoup NTL */
    1122             : GEN
    1123       71428 : F2xqX_factor_squarefree(GEN f, GEN T)
    1124             : {
    1125       71428 :   pari_sp av = avma;
    1126             :   GEN r, t, v, tv;
    1127       71428 :   long i, q, n = degpol(f);
    1128       71428 :   GEN u = const_vec(n+1, pol1_F2xX(varn(f), get_F2x_var(T)));
    1129       71428 :   for(q = 1;;q *= 2)
    1130             :   {
    1131       80724 :     r = F2xqX_gcd(f, F2xX_deriv(f), T);
    1132       80724 :     if (degpol(r) == 0)
    1133             :     {
    1134       69727 :       gel(u, q) = F2xqX_normalize(f, T);
    1135       69727 :       break;
    1136             :     }
    1137       10997 :     t = F2xqX_div(f, r, T);
    1138       10997 :     if (degpol(t) > 0)
    1139             :     {
    1140             :       long j;
    1141       10080 :       for(j = 1;;j++)
    1142             :       {
    1143       15036 :         v = F2xqX_gcd(r, t, T);
    1144       15036 :         tv = F2xqX_div(t, v, T);
    1145       15036 :         if (degpol(tv) > 0)
    1146       11746 :           gel(u, j*q) = F2xqX_normalize(tv, T);
    1147       15036 :         if (degpol(v) <= 0) break;
    1148        4956 :         r = F2xqX_div(r, v, T);
    1149        4956 :         t = v;
    1150             :       }
    1151       10080 :       if (degpol(r) == 0) break;
    1152             :     }
    1153        9296 :     f = F2xqX_Frobenius_deflate(r, T);
    1154             :   }
    1155      417963 :   for (i = n; i; i--)
    1156      417963 :     if (degpol(gel(u,i))) break;
    1157       71428 :   setlg(u,i+1); return gerepilecopy(av, u);
    1158             : }
    1159             : 
    1160             : long
    1161          56 : F2xqX_ispower(GEN f, long k, GEN T, GEN *pt_r)
    1162             : {
    1163          56 :   pari_sp av = avma;
    1164             :   GEN lc, F;
    1165          56 :   long i, l, n = degpol(f);
    1166          56 :   if (n % k) return 0;
    1167          56 :   lc = F2xq_sqrtn(leading_coeff(f), stoi(k), T, NULL);
    1168          56 :   if (!lc) return gc_long(av,0);
    1169          56 :   F = F2xqX_factor_squarefree(f, T); l = lg(F)-1;
    1170        2030 :   for(i=1; i<=l; i++)
    1171        1981 :     if (i%k && degpol(gel(F,i))) return gc_long(av,0);
    1172          49 :   if (pt_r)
    1173             :   {
    1174          49 :     long v = varn(f);
    1175          49 :     GEN r = scalarpol(lc, v), s = pol1_F2xX(v, T[1]);
    1176        2023 :     for(i=l; i>=1; i--)
    1177             :     {
    1178        1974 :       if (i%k) continue;
    1179         406 :       s = F2xqX_mul(s, gel(F,i), T);
    1180         406 :       r = F2xqX_mul(r, s, T);
    1181             :     }
    1182          49 :     *pt_r = gerepileupto(av, r);
    1183           0 :   } else set_avma(av);
    1184          49 :   return 1;
    1185             : }
    1186             : 
    1187             : static void
    1188       50078 : F2xqX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, GEN V, long idx)
    1189             : {
    1190             :   pari_sp btop;
    1191       50078 :   long n = degpol(Sp);
    1192             :   GEN S, f, ff;
    1193       50078 :   long dT = get_F2x_degree(T);
    1194       50078 :   GEN R = F2xqX_easyroots(Sp, T);
    1195       50078 :   if (R)
    1196             :   {
    1197       47943 :     long i, l = lg(R)-1;
    1198      106365 :     for (i=0; i<l; i++)
    1199       58422 :       gel(V, idx+i) = gel(R,1+i);
    1200       47943 :     return;
    1201             :   }
    1202        2135 :   S = F2xqX_get_red(Sp, T);
    1203        2135 :   Xp = F2xqX_rem(Xp, S, T);
    1204        2135 :   btop = avma;
    1205             :   while (1)
    1206         511 :   {
    1207        2646 :     GEN a = random_F2xqX(degpol(Sp), varn(Sp), T);
    1208        2646 :     GEN R = gel(F2xqXQ_auttrace(mkvec3(xp, Xp, a), dT, S, T), 3);
    1209        2646 :     f = F2xqX_gcd(R, Sp, T);
    1210        2646 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1211         511 :     set_avma(btop);
    1212             :   }
    1213        2135 :   f = gerepileupto(btop, F2xqX_normalize(f, T));
    1214        2135 :   ff = F2xqX_div(Sp, f, T);
    1215        2135 :   F2xqX_roots_edf(f, xp, Xp, T, V, idx);
    1216        2135 :   F2xqX_roots_edf(ff,xp, Xp, T, V, idx+degpol(f));
    1217             : }
    1218             : 
    1219             : static GEN
    1220       80976 : F2xqX_roots_ddf(GEN f, GEN xp, GEN T)
    1221             : {
    1222             :   GEN X, Xp, Xq, g, V;
    1223             :   long n;
    1224       80976 :   GEN R = F2xqX_easyroots(f, T);
    1225       80976 :   if (R) return R;
    1226       70336 :   X  = pol_x(varn(f));
    1227       70336 :   Xp = F2xqXQ_sqr(X, f, T);
    1228       70336 :   Xq = F2xqXQ_Frobenius(xp, Xp, f, T);
    1229       70336 :   g = F2xqX_gcd(F2xX_add(Xq, X), f, T);
    1230       70336 :   n = degpol(g);
    1231       70336 :   if (n==0) return cgetg(1, t_COL);
    1232       45808 :   g = F2xqX_normalize(g, T);
    1233       45808 :   V = cgetg(n+1,t_COL);
    1234       45808 :   F2xqX_roots_edf(g, xp, Xp, T, V, 1);
    1235       45808 :   return V;
    1236             : }
    1237             : static GEN
    1238       75194 : F2xqX_roots_i(GEN S, GEN T)
    1239             : {
    1240             :   GEN M;
    1241       75194 :   S = F2xqX_red(S, T);
    1242       75194 :   if (!signe(S)) pari_err_ROOTS0("F2xqX_roots");
    1243       75194 :   if (degpol(S)==0) return cgetg(1, t_COL);
    1244       75187 :   S = F2xqX_normalize(S, T);
    1245       75187 :   M = F2xqX_easyroots(S, T);
    1246       75187 :   if (!M)
    1247             :   {
    1248       71057 :     GEN xp = F2x_Frobenius(T);
    1249       71057 :     GEN F, V = F2xqX_factor_squarefree(S, T);
    1250       71057 :     long i, j, l = lg(V);
    1251       71057 :     F = cgetg(l, t_VEC);
    1252      154945 :     for (i=1, j=1; i < l; i++)
    1253       83888 :       if (degpol(gel(V,i)))
    1254       80976 :         gel(F, j++) = F2xqX_roots_ddf(gel(V,i), xp, T);
    1255       71057 :     setlg(F,j); M = shallowconcat1(F);
    1256             :   }
    1257       75187 :   gen_sort_inplace(M, (void*) &cmp_Flx, &cmp_nodata, NULL);
    1258       75187 :   return M;
    1259             : }
    1260             : 
    1261             : static GEN
    1262      177013 : FlxqX_easyroots(GEN f, GEN T, ulong p)
    1263             : {
    1264      177013 :   if (FlxY_degreex(f) <= 0) return Flx_rootsff_i(FlxX_to_Flx(f), T, p);
    1265      166205 :   if (degpol(f)==1) return mkcol(Flx_neg(constant_coeff(f), p));
    1266      138277 :   if (degpol(f)==2) return FlxqX_quad_roots(f,T,p);
    1267      125235 :   return NULL;
    1268             : }
    1269             : 
    1270             : static GEN
    1271         581 : FlxqX_invFrobenius(GEN xp, GEN T, ulong p)
    1272             : {
    1273         581 :   return Flxq_autpow(xp, get_Flx_degree(T)-1, T, p);
    1274             : }
    1275             : 
    1276             : static GEN
    1277         644 : FlxqX_Frobenius_deflate(GEN S, GEN ixp, GEN T, ulong p)
    1278             : {
    1279         644 :   GEN F = RgX_deflate(S, p);
    1280         644 :   long i, l = lg(F);
    1281         644 :   if (typ(ixp)==t_INT)
    1282           0 :     for (i=2; i<l; i++)
    1283           0 :       gel(F,i) = Flxq_pow(gel(F,i), ixp, T, p);
    1284             :   else
    1285             :   {
    1286         644 :     long n = brent_kung_optpow(get_Flx_degree(T)-1, l-2, 1);
    1287         644 :     GEN V = Flxq_powers(ixp, n, T, p);
    1288        5747 :     for (i=2; i<l; i++)
    1289        5103 :       gel(F,i) = Flx_FlxqV_eval(gel(F,i), V, T, p);
    1290             :   }
    1291         644 :   return F;
    1292             : }
    1293             : 
    1294             : /* Adapted from Shoup NTL */
    1295             : static GEN
    1296       59098 : FlxqX_factor_squarefree_i(GEN f, GEN xp, GEN T, ulong p)
    1297             : {
    1298       59098 :   pari_sp av = avma;
    1299             :   GEN r, t, v, tv;
    1300       59098 :   long i, q, n = degpol(f);
    1301       59098 :   GEN u = const_vec(n+1, pol1_FlxX(varn(f),get_Flx_var(T)));
    1302       59098 :   GEN ixp = NULL;
    1303       59098 :   for(q = 1;;q *= p)
    1304             :   {
    1305       59742 :     r = FlxqX_gcd(f, FlxX_deriv(f, p), T, p);
    1306       59742 :     if (degpol(r) == 0)
    1307             :     {
    1308       54912 :       gel(u, q) = FlxqX_normalize(f, T, p);
    1309       54912 :       break;
    1310             :     }
    1311        4830 :     t = FlxqX_div(f, r, T, p);
    1312        4830 :     if (degpol(t) > 0)
    1313             :     {
    1314             :       long j;
    1315        4613 :       for(j = 1;;j++)
    1316             :       {
    1317        9933 :         v = FlxqX_gcd(r, t, T, p);
    1318        9933 :         tv = FlxqX_div(t, v, T, p);
    1319        9933 :         if (degpol(tv) > 0)
    1320        8701 :           gel(u, j*q) = FlxqX_normalize(tv, T, p);
    1321        9933 :         if (degpol(v) <= 0) break;
    1322        5320 :         r = FlxqX_div(r, v, T, p);
    1323        5320 :         t = v;
    1324             :       }
    1325        4613 :       if (degpol(r) == 0) break;
    1326             :     }
    1327         644 :     if (!xp)   xp = Flx_Frobenius(T, p);
    1328         644 :     if (!ixp) ixp = FlxqX_invFrobenius(xp, T, p);
    1329         644 :     f = FlxqX_Frobenius_deflate(r, ixp, T, p);
    1330             :   }
    1331      321312 :   for (i = n; i; i--)
    1332      321312 :     if (degpol(gel(u,i))) break;
    1333       59098 :   setlg(u,i+1); return gerepilecopy(av, u);
    1334             : }
    1335             : 
    1336             : GEN
    1337          42 : FlxqX_factor_squarefree(GEN f, GEN T, ulong p)
    1338             : {
    1339          42 :   return FlxqX_factor_squarefree_i(f, NULL, T, p);
    1340             : }
    1341             : 
    1342             : long
    1343          98 : FlxqX_ispower(GEN f, ulong k, GEN T, ulong p, GEN *pt_r)
    1344             : {
    1345          98 :   pari_sp av = avma;
    1346             :   GEN lc, F;
    1347          98 :   long i, l, n = degpol(f), v = varn(f);
    1348          98 :   if (n % k) return 0;
    1349          98 :   lc = Flxq_sqrtn(leading_coeff(f), stoi(k), T, p, NULL);
    1350          98 :   if (!lc) return gc_long(av,0);
    1351          98 :   F = FlxqX_factor_squarefree_i(f, NULL, T, p); l = lg(F)-1;
    1352        3521 :   for(i=1; i<=l; i++)
    1353        3437 :     if (i%k && degpol(gel(F,i))) return gc_long(av,0);
    1354          84 :   if (pt_r)
    1355             :   {
    1356          84 :     GEN r = scalarpol(lc, v), s = pol1_FlxX(v, T[1]);
    1357        3507 :     for(i=l; i>=1; i--)
    1358             :     {
    1359        3423 :       if (i%k) continue;
    1360         700 :       s = FlxqX_mul(s, gel(F,i), T, p);
    1361         700 :       r = FlxqX_mul(r, s, T, p);
    1362             :     }
    1363          84 :     *pt_r = gerepileupto(av, r);
    1364           0 :   } else set_avma(av);
    1365          84 :   return 1;
    1366             : }
    1367             : 
    1368             : static GEN
    1369        8547 : FlxqX_roots_split(GEN Sp, GEN xp, GEN Xp, GEN S, GEN T, ulong p)
    1370             : {
    1371        8547 :   pari_sp btop = avma;
    1372        8547 :   long n = degpol(Sp);
    1373             :   GEN f;
    1374        8547 :   long vT = get_Flx_var(T), dT = get_Flx_degree(T);
    1375             :   pari_timer ti;
    1376        8547 :   if (DEBUGLEVEL >= 7) timer_start(&ti);
    1377             :   while (1)
    1378        1765 :   {
    1379       10312 :     GEN a = deg1pol(pol1_Flx(vT), random_Flx(dT, vT, p), varn(Sp));
    1380       10312 :     GEN R = FlxqXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
    1381       10312 :     if (DEBUGLEVEL >= 7) timer_printf(&ti, "FlxqXQ_halfFrobenius");
    1382       10312 :     f = FlxqX_gcd(FlxX_Flx_sub(R, pol1_Flx(vT), p), Sp, T, p);
    1383       10312 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1384        1765 :     set_avma(btop);
    1385             :   }
    1386        8547 :   return gerepileupto(btop, FlxqX_normalize(f, T, p));
    1387             : }
    1388             : 
    1389             : static void
    1390       50871 : FlxqX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, ulong p, GEN V, long idx)
    1391             : {
    1392             :   GEN S, f, ff;
    1393       50871 :   GEN R = FlxqX_easyroots(Sp, T, p);
    1394       50871 :   if (R)
    1395             :   {
    1396       42665 :     long i, l = lg(R)-1;
    1397       98425 :     for (i=0; i<l; i++)
    1398       55760 :       gel(V, idx+i) = gel(R,1+i);
    1399       42665 :     return;
    1400             :   }
    1401        8206 :   S  = FlxqX_get_red(Sp, T, p);
    1402        8206 :   Xp = FlxqX_rem(Xp, S, T, p);
    1403        8206 :   f  = FlxqX_roots_split(Sp, xp, Xp, S, T, p);
    1404        8206 :   ff = FlxqX_div(Sp, f, T, p);
    1405        8206 :   FlxqX_roots_edf(f, xp, Xp, T, p, V, idx);
    1406        8206 :   FlxqX_roots_edf(ff,xp, Xp, T, p, V, idx+degpol(f));
    1407             : }
    1408             : 
    1409             : static GEN
    1410       63061 : FlxqX_roots_ddf(GEN f, GEN xp, GEN T, ulong p)
    1411             : {
    1412             :   GEN X, Xp, Xq, g, V;
    1413             :   long n;
    1414       63061 :   GEN R = FlxqX_easyroots(f, T, p);
    1415       63061 :   if (R) return R;
    1416       58315 :   X  = pol_x(varn(f));
    1417       58315 :   Xp = FlxqXQ_powu(X, p, f, T, p);
    1418       58315 :   Xq = FlxqXQ_Frobenius(xp, Xp, f, T, p);
    1419       58315 :   g = FlxqX_gcd(FlxX_sub(Xq, X, p), f, T, p);
    1420       58315 :   n = degpol(g);
    1421       58315 :   if (n==0) return cgetg(1, t_COL);
    1422       34459 :   g = FlxqX_normalize(g, T, p);
    1423       34459 :   V = cgetg(n+1,t_COL);
    1424       34459 :   FlxqX_roots_edf(g, xp, Xp, T, p, V, 1);
    1425       34459 :   return V;
    1426             : }
    1427             : 
    1428             : /* do not handle p==2 */
    1429             : static GEN
    1430       63088 : FlxqX_roots_i(GEN S, GEN T, ulong p)
    1431             : {
    1432             :   GEN M;
    1433       63088 :   S = FlxqX_red(S, T, p);
    1434       63088 :   if (!signe(S)) pari_err_ROOTS0("FlxqX_roots");
    1435       63088 :   if (degpol(S)==0) return cgetg(1, t_COL);
    1436       63081 :   S = FlxqX_normalize(S, T, p);
    1437       63081 :   M = FlxqX_easyroots(S, T, p);
    1438       63081 :   if (!M)
    1439             :   {
    1440       58714 :     GEN xp = Flx_Frobenius(T, p);
    1441       58714 :     GEN F, V = FlxqX_factor_squarefree_i(S, xp, T, p);
    1442       58714 :     long i, j, l = lg(V);
    1443       58714 :     F = cgetg(l, t_VEC);
    1444      122412 :     for (i=1, j=1; i < l; i++)
    1445       63698 :       if (degpol(gel(V,i)))
    1446       63061 :         gel(F, j++) = FlxqX_roots_ddf(gel(V,i), xp, T, p);
    1447       58714 :     setlg(F,j); M = shallowconcat1(F);
    1448             :   }
    1449       63081 :   gen_sort_inplace(M, (void*) &cmp_Flx, &cmp_nodata, NULL);
    1450       63081 :   return M;
    1451             : }
    1452             : 
    1453             : static GEN
    1454        2310 : FpXQX_easyroots(GEN f, GEN T, GEN p)
    1455             : {
    1456        2310 :   if (isabsolutepol(f)) return FpX_rootsff_i(simplify_shallow(f), T, p);
    1457        2016 :   if (degpol(f)==1) return mkcol(Fq_to_FpXQ(Fq_neg(constant_coeff(f),T,p),T,p));
    1458        1597 :   if (degpol(f)==2) return FpXQX_quad_roots(f,T,p);
    1459         963 :   return NULL;
    1460             : }
    1461             : 
    1462             : /* Adapted from Shoup NTL */
    1463             : static GEN
    1464         157 : FpXQX_factor_Yun(GEN f, GEN T, GEN p)
    1465             : {
    1466         157 :   pari_sp av = avma;
    1467             :   GEN r, t, v, tv;
    1468         157 :   long j, n = degpol(f);
    1469         157 :   GEN u = const_vec(n+1, pol_1(varn(f)));
    1470         157 :   r = FpXQX_gcd(f, FpXX_deriv(f, p), T, p);
    1471         157 :   t = FpXQX_div(f, r, T, p);
    1472         157 :   for (j = 1;;j++)
    1473             :   {
    1474        1599 :     v = FpXQX_gcd(r, t, T, p);
    1475        1599 :     tv = FpXQX_div(t, v, T, p);
    1476        1599 :     if (degpol(tv) > 0)
    1477         199 :       gel(u, j) = FpXQX_normalize(tv, T, p);
    1478        1599 :     if (degpol(v) <= 0) break;
    1479        1442 :     r = FpXQX_div(r, v, T, p);
    1480        1442 :     t = v;
    1481             :   }
    1482         157 :   setlg(u, j+1); return gerepilecopy(av, u);
    1483             : }
    1484             : 
    1485             : GEN
    1486           7 : FpXQX_factor_squarefree(GEN f, GEN T, GEN p)
    1487             : {
    1488           7 :   if (lgefint(p)==3)
    1489             :   {
    1490           0 :     pari_sp av = avma;
    1491           0 :     ulong pp = p[2];
    1492             :     GEN M;
    1493           0 :     long vT = get_FpX_var(T);
    1494           0 :     if (pp==2)
    1495             :     {
    1496           0 :       M = F2xqX_factor_squarefree(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    1497           0 :       return gerepileupto(av, F2xXC_to_ZXXC(M));
    1498             :     }
    1499           0 :     M = FlxqX_factor_squarefree(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    1500           0 :     return gerepileupto(av, FlxXC_to_ZXXC(M));
    1501             :   }
    1502           7 :   return FpXQX_factor_Yun(f, T, p);
    1503             : }
    1504             : 
    1505             : long
    1506          98 : FpXQX_ispower(GEN f, ulong k, GEN T, GEN p, GEN *pt_r)
    1507             : {
    1508          98 :   pari_sp av = avma;
    1509             :   GEN lc, F;
    1510          98 :   long i, l, n = degpol(f), v = varn(f);
    1511          98 :   if (n % k) return 0;
    1512          98 :   if (lgefint(p)==3)
    1513             :   {
    1514          42 :     ulong pp = p[2];
    1515          42 :     GEN fp = ZXX_to_FlxX(f, pp, varn(T));
    1516          42 :     if (!FlxqX_ispower(fp, k, ZX_to_Flx(T,pp), pp, pt_r)) return gc_long(av,0);
    1517          35 :     if (pt_r) *pt_r = gerepileupto(av, FlxX_to_ZXX(*pt_r));
    1518           0 :     else set_avma(av);
    1519          35 :     return 1;
    1520             :   }
    1521          56 :   lc = FpXQ_sqrtn(leading_coeff(f), stoi(k), T, p, NULL);
    1522          56 :   if (!lc) return gc_long(av,0);
    1523          56 :   F = FpXQX_factor_Yun(f, T, p); l = lg(F)-1;
    1524        1533 :   for(i=1; i <= l; i++)
    1525        1484 :     if (i%k && degpol(gel(F,i))) return gc_long(av,0);
    1526          49 :   if (pt_r)
    1527             :   {
    1528          49 :     GEN r = scalarpol(lc, v), s = pol_1(v);
    1529        1526 :     for(i=l; i>=1; i--)
    1530             :     {
    1531        1477 :       if (i%k) continue;
    1532         308 :       s = FpXQX_mul(s, gel(F,i), T, p);
    1533         308 :       r = FpXQX_mul(r, s, T, p);
    1534             :     }
    1535          49 :     *pt_r = gerepileupto(av, r);
    1536           0 :   } else set_avma(av);
    1537          49 :   return 1;
    1538             : }
    1539             : 
    1540             : long
    1541         210 : FqX_ispower(GEN f, ulong k, GEN T, GEN p, GEN *pt_r)
    1542         210 : { return T ? FpXQX_ispower(f, k, T, p, pt_r): FpX_ispower(f, k, p, pt_r); }
    1543             : 
    1544             : static GEN
    1545         926 : FpXQX_roots_split(GEN Sp, GEN xp, GEN Xp, GEN S, GEN T, GEN p)
    1546             : {
    1547         926 :   pari_sp btop = avma;
    1548         926 :   long n = degpol(Sp);
    1549             :   GEN f;
    1550         926 :   long vT = get_FpX_var(T), dT = get_FpX_degree(T);
    1551             :   pari_timer ti;
    1552         926 :   if (DEBUGLEVEL >= 7) timer_start(&ti);
    1553             :   while (1)
    1554         122 :   {
    1555        1048 :     GEN a = deg1pol(pol_1(vT), random_FpX(dT, vT, p), varn(Sp));
    1556        1048 :     GEN R = FpXQXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
    1557        1048 :     if (DEBUGLEVEL >= 7) timer_printf(&ti, "FpXQXQ_halfFrobenius");
    1558        1048 :     f = FpXQX_gcd(FqX_Fq_sub(R, pol_1(vT), T, p), Sp, T, p);
    1559        1048 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1560         122 :     set_avma(btop);
    1561             :   }
    1562         926 :   return gerepileupto(btop, FpXQX_normalize(f, T, p));
    1563             : }
    1564             : 
    1565             : static void
    1566        1836 : FpXQX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, GEN p, GEN V, long idx)
    1567             : {
    1568             :   GEN S, f, ff;
    1569        1836 :   GEN R = FpXQX_easyroots(Sp, T, p);
    1570        1836 :   if (R)
    1571             :   {
    1572         933 :     long i, l = lg(R)-1;
    1573        2391 :     for (i=0; i<l; i++)
    1574        1458 :       gel(V, idx+i) = gel(R,1+i);
    1575         933 :     return;
    1576             :   }
    1577         903 :   S  = FpXQX_get_red(Sp, T, p);
    1578         903 :   Xp = FpXQX_rem(Xp, S, T, p);
    1579         903 :   f  = FpXQX_roots_split(Sp, xp, Xp, S, T, p);
    1580         903 :   ff = FpXQX_div(Sp, f, T, p);
    1581         903 :   FpXQX_roots_edf(f, xp, Xp, T, p, V, idx);
    1582         903 :   FpXQX_roots_edf(ff,xp, Xp, T, p, V, idx+degpol(f));
    1583             : }
    1584             : 
    1585             : static GEN
    1586          30 : FpXQX_roots_ddf(GEN f, GEN xp, GEN T, GEN p)
    1587             : {
    1588             :   GEN X, Xp, Xq, g, V;
    1589             :   long n;
    1590          30 :   GEN R = FpXQX_easyroots(f, T, p);
    1591          30 :   if (R) return R;
    1592          30 :   X  = pol_x(varn(f));
    1593          30 :   Xp = FpXQXQ_pow(X, p, f, T, p);
    1594          30 :   Xq = FpXQXQ_Frobenius(xp, Xp, f, T, p);
    1595          30 :   g = FpXQX_gcd(FpXX_sub(Xq, X, p), f, T, p);
    1596          30 :   n = degpol(g);
    1597          30 :   if (n==0) return cgetg(1, t_COL);
    1598          30 :   g = FpXQX_normalize(g, T, p);
    1599          30 :   V = cgetg(n+1,t_COL);
    1600          30 :   FpXQX_roots_edf(g, xp, Xp, T, p, V, 1);
    1601          30 :   return V;
    1602             : }
    1603             : 
    1604             : /* do not handle small p */
    1605             : static GEN
    1606       20919 : FpXQX_roots_i(GEN S, GEN T, GEN p)
    1607             : {
    1608             :   GEN F, M;
    1609       20919 :   if (lgefint(p)==3)
    1610             :   {
    1611       20475 :     ulong pp = p[2];
    1612       20475 :     if (pp == 2)
    1613             :     {
    1614        3710 :       GEN V = F2xqX_roots_i(ZXX_to_F2xX(S,get_FpX_var(T)), ZX_to_F2x(get_FpX_mod(T)));
    1615        3710 :       return F2xC_to_ZXC(V);
    1616             :     }
    1617             :     else
    1618             :     {
    1619       16765 :       GEN V = FlxqX_roots_i(ZXX_to_FlxX(S,pp,get_FpX_var(T)), ZXT_to_FlxT(T,pp), pp);
    1620       16765 :       return FlxC_to_ZXC(V);
    1621             :     }
    1622             :   }
    1623         444 :   S = FpXQX_red(S, T, p);
    1624         444 :   if (!signe(S)) pari_err_ROOTS0("FpXQX_roots");
    1625         444 :   if (degpol(S)==0) return cgetg(1, t_COL);
    1626         444 :   S = FpXQX_normalize(S, T, p);
    1627         444 :   M = FpXQX_easyroots(S, T, p);
    1628         444 :   if (!M)
    1629             :   {
    1630          30 :     GEN xp = FpX_Frobenius(T, p);
    1631          30 :     GEN V = FpXQX_factor_Yun(S, T, p);
    1632          30 :     long i, j, l = lg(V);
    1633          30 :     F = cgetg(l, t_VEC);
    1634          60 :     for (i=1, j=1; i < l; i++)
    1635          30 :       if (degpol(gel(V,i)))
    1636          30 :         gel(F, j++) = FpXQX_roots_ddf(gel(V,i), xp, T, p);
    1637          30 :     setlg(F,j); M = shallowconcat1(F);
    1638             :   }
    1639         444 :   gen_sort_inplace(M, (void*) &cmp_RgX, &cmp_nodata, NULL);
    1640         444 :   return M;
    1641             : }
    1642             : 
    1643             : GEN
    1644       71484 : F2xqX_roots(GEN x, GEN T)
    1645             : {
    1646       71484 :   pari_sp av = avma;
    1647       71484 :   return gerepilecopy(av, F2xqX_roots_i(x, T));
    1648             : }
    1649             : 
    1650             : GEN
    1651       46323 : FlxqX_roots(GEN x, GEN T, ulong p)
    1652             : {
    1653       46323 :   pari_sp av = avma;
    1654       46323 :   if (p==2)
    1655             :   {
    1656           0 :     GEN V = F2xqX_roots_i(FlxX_to_F2xX(x), Flx_to_F2x(get_Flx_mod(T)));
    1657           0 :     return gerepileupto(av, F2xC_to_FlxC(V));
    1658             :   }
    1659       46323 :   return gerepilecopy(av, FlxqX_roots_i(x, T, p));
    1660             : }
    1661             : 
    1662             : GEN
    1663       20919 : FpXQX_roots(GEN x, GEN T, GEN p)
    1664             : {
    1665       20919 :   pari_sp av = avma;
    1666       20919 :   return gerepilecopy(av, FpXQX_roots_i(x, T, p));
    1667             : }
    1668             : 
    1669             : static GEN
    1670         539 : FE_concat(GEN F, GEN E, long l)
    1671             : {
    1672         539 :   setlg(E,l); E = shallowconcat1(E);
    1673         539 :   setlg(F,l); F = shallowconcat1(F); return mkvec2(F,E);
    1674             : }
    1675             : 
    1676             : static GEN
    1677         483 : F2xqX_factor_2(GEN f, GEN T)
    1678             : {
    1679         483 :   long v = varn(f), vT = get_F2x_var(T);
    1680         483 :   GEN r = F2xqX_quad_roots(f, T);
    1681         483 :   switch(lg(r)-1)
    1682             :   {
    1683          14 :   case 0:
    1684          14 :     return mkvec2(mkcolcopy(f), mkvecsmall(1));
    1685         462 :   case 1:
    1686         462 :     return mkvec2(mkcol(deg1pol_shallow(pol1_F2x(vT), gel(r,1), v)), mkvecsmall(2));
    1687           7 :   default: /* 2 */
    1688             :     {
    1689           7 :       GEN f1 = deg1pol_shallow(pol1_F2x(vT), gel(r,1), v);
    1690           7 :       GEN f2 = deg1pol_shallow(pol1_F2x(vT), gel(r,2), v);
    1691           7 :       GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
    1692           7 :       sort_factor_pol(mkvec2(t, E), cmp_Flx);
    1693           7 :       return mkvec2(t, E);
    1694             :     }
    1695             :   }
    1696             : }
    1697             : 
    1698             : static GEN
    1699         797 : FlxqX_factor_2(GEN f, GEN T, ulong p)
    1700             : {
    1701         797 :   long v = varn(f), vT = get_Flx_var(T);
    1702         797 :   GEN r = FlxqX_quad_roots(f, T, p);
    1703         797 :   switch(lg(r)-1)
    1704             :   {
    1705          56 :   case 0:
    1706          56 :     return mkvec2(mkcolcopy(f), mkvecsmall(1));
    1707          42 :   case 1:
    1708          84 :     return mkvec2(mkcol(deg1pol_shallow(pol1_Flx(vT),
    1709          42 :                         Flx_neg(gel(r,1), p), v)), mkvecsmall(2));
    1710         699 :   default: /* 2 */
    1711             :     {
    1712         699 :       GEN f1 = deg1pol_shallow(pol1_Flx(vT), Flx_neg(gel(r,1), p), v);
    1713         699 :       GEN f2 = deg1pol_shallow(pol1_Flx(vT), Flx_neg(gel(r,2), p), v);
    1714         699 :       GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
    1715         699 :       sort_factor_pol(mkvec2(t, E), cmp_Flx);
    1716         699 :       return mkvec2(t, E);
    1717             :     }
    1718             :   }
    1719             : }
    1720             : 
    1721             : static GEN
    1722          43 : FpXQX_factor_2(GEN f, GEN T, GEN p)
    1723             : {
    1724          43 :   long v = varn(f);
    1725          43 :   GEN r = FpXQX_quad_roots(f, T, p);
    1726          43 :   switch(lg(r)-1)
    1727             :   {
    1728          14 :   case 0:
    1729          14 :     return mkvec2(mkcolcopy(f), mkvecsmall(1));
    1730           0 :   case 1:
    1731           0 :     return mkvec2(mkcol(deg1pol_shallow(gen_1, Fq_neg(gel(r,1), T, p), v)),
    1732             :         mkvecsmall(2));
    1733          29 :   default: /* 2 */
    1734             :     {
    1735          29 :       GEN f1 = deg1pol_shallow(gen_1, Fq_neg(gel(r,1), T, p), v);
    1736          29 :       GEN f2 = deg1pol_shallow(gen_1, Fq_neg(gel(r,2), T, p), v);
    1737          29 :       GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
    1738          29 :       sort_factor_pol(mkvec2(t, E), cmp_RgX);
    1739          29 :       return mkvec2(t, E);
    1740             :     }
    1741             :   }
    1742             : }
    1743             : 
    1744             : static GEN
    1745         357 : F2xqX_ddf_Shoup(GEN S, GEN Xq, GEN T)
    1746             : {
    1747         357 :   pari_sp av = avma;
    1748             :   GEN b, g, h, F, f, Sr, xq;
    1749             :   long i, j, n, v, vT, dT, bo, ro;
    1750             :   long B, l, m;
    1751             :   pari_timer ti;
    1752         357 :   n = get_F2xqX_degree(S); v = get_F2xqX_var(S);
    1753         357 :   vT = get_F2x_var(T); dT = get_F2x_degree(T);
    1754         357 :   if (n == 0) return cgetg(1, t_VEC);
    1755         357 :   if (n == 1) return mkvec(get_F2xqX_mod(S));
    1756         119 :   B = n/2;
    1757         119 :   l = usqrt(B);
    1758         119 :   m = (B+l-1)/l;
    1759         119 :   S = F2xqX_get_red(S, T);
    1760         119 :   b = cgetg(l+2, t_VEC);
    1761         119 :   gel(b, 1) = polx_F2xX(v, vT);
    1762         119 :   gel(b, 2) = Xq;
    1763         119 :   bo = brent_kung_optpow(n, l-1, 1);
    1764         119 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    1765         119 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    1766         119 :   if (dT <= ro)
    1767           0 :     for (i = 3; i <= l+1; i++)
    1768           0 :       gel(b, i) = F2xqXQ_pow(gel(b, i-1), int2n(dT), S, T);
    1769             :   else
    1770             :   {
    1771         119 :     xq = F2xqXQ_powers(gel(b, 2), bo, S, T);
    1772         119 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: xq baby");
    1773         119 :     for (i = 3; i <= l+1; i++)
    1774           0 :       gel(b, i) = F2xqX_F2xqXQV_eval(gel(b, i-1), xq, S, T);
    1775             :   }
    1776         119 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: baby");
    1777         119 :   xq = F2xqXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T);
    1778         119 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: xq giant");
    1779         119 :   g = cgetg(m+1, t_VEC);
    1780         119 :   gel(g, 1) = gel(xq, 2);
    1781         147 :   for(i = 2; i <= m; i++)
    1782          28 :     gel(g, i) = F2xqX_F2xqXQV_eval(gel(g, i-1), xq, S, T);
    1783         119 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: giant");
    1784         119 :   h = cgetg(m+1, t_VEC);
    1785         266 :   for (j = 1; j <= m; j++)
    1786             :   {
    1787         147 :     pari_sp av = avma;
    1788         147 :     GEN gj = gel(g, j);
    1789         147 :     GEN e = F2xX_add(gj, gel(b, 1));
    1790         147 :     for (i = 2; i <= l; i++)
    1791           0 :       e = F2xqXQ_mul(e, F2xX_add(gj, gel(b, i)), S, T);
    1792         147 :     gel(h, j) = gerepileupto(av, e);
    1793             :   }
    1794         119 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: diff");
    1795         119 :   Sr = get_F2xqX_mod(S);
    1796         119 :   F = cgetg(m+1, t_VEC);
    1797         266 :   for (j = 1; j <= m; j++)
    1798             :   {
    1799         147 :     GEN u = F2xqX_gcd(Sr, gel(h,j), T);
    1800         147 :     if (degpol(u))
    1801             :     {
    1802          91 :       u = F2xqX_normalize(u, T);
    1803          91 :       Sr = F2xqX_div(Sr, u, T);
    1804             :     }
    1805         147 :     gel(F,j) = u;
    1806             :   }
    1807         119 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: F");
    1808         119 :   f = const_vec(n, pol1_F2xX(v, vT));
    1809         266 :   for (j = 1; j <= m; j++)
    1810             :   {
    1811         147 :     GEN e = gel(F, j);
    1812         147 :     for (i=l-1; i >= 0; i--)
    1813             :     {
    1814         147 :       GEN u = F2xqX_gcd(e, F2xX_add(gel(g, j), gel(b, i+1)), T);
    1815         147 :       if (degpol(u))
    1816             :       {
    1817          91 :         gel(f, l*j-i) = u = F2xqX_normalize(u, T);
    1818          91 :         e = F2xqX_div(e, u, T);
    1819             :       }
    1820         147 :       if (!degpol(e)) break;
    1821             :     }
    1822             :   }
    1823         119 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf_Shoup: f");
    1824         119 :   if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
    1825         119 :   return gerepilecopy(av, f);
    1826             : }
    1827             : 
    1828             : static GEN
    1829          91 : F2xqX_ddf_i(GEN f, GEN T, GEN X, GEN xp)
    1830             : {
    1831             :   GEN Xp, Xq;
    1832          91 :   if (!get_F2xqX_degree(f)) return cgetg(1,t_VEC);
    1833          42 :   f = F2xqX_get_red(f, T);
    1834          42 :   Xp = F2xqXQ_sqr(X, f, T);
    1835          42 :   Xq = F2xqXQ_Frobenius(xp, Xp, f, T);
    1836          42 :   return F2xqX_ddf_Shoup(f, Xq, T);
    1837             : }
    1838             : static void
    1839          42 : F2xqX_ddf_init(GEN *S, GEN *T, GEN *xp, GEN *X)
    1840             : {
    1841          42 :   *T = F2x_get_red(*T);
    1842          42 :   *S = F2xqX_normalize(get_F2xqX_mod(*S), *T);
    1843          42 :   *xp = F2x_Frobenius(*T);
    1844          42 :   *X  = polx_F2xX(get_F2xqX_var(*S), get_F2x_var(*T));
    1845          42 : }
    1846             : GEN
    1847          42 : F2xqX_degfact(GEN S, GEN T)
    1848             : {
    1849             :   GEN xp, X, V;
    1850             :   long i, l;
    1851          42 :   F2xqX_ddf_init(&S,&T,&xp,&X);
    1852          42 :   V = F2xqX_factor_squarefree(S, T); l = lg(V);
    1853         133 :   for (i=1; i < l; i++) gel(V,i) = F2xqX_ddf_i(gel(V,i), T, X, xp);
    1854          42 :   return vddf_to_simplefact(V, degpol(S));
    1855             : }
    1856             : GEN
    1857           0 : F2xqX_ddf(GEN S, GEN T)
    1858             : {
    1859             :   GEN xp, X;
    1860           0 :   F2xqX_ddf_init(&S,&T,&xp,&X);
    1861           0 :   return ddf_to_ddf2( F2xqX_ddf_i(S, T, X, xp) );
    1862             : }
    1863             : 
    1864             : static void
    1865         168 : F2xqX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Sq, long d, GEN T, GEN V, long idx)
    1866             : {
    1867         168 :   long v = varn(Sp), n = degpol(Sp), r = n/d;
    1868             :   GEN S, f, ff;
    1869         168 :   long dT = get_F2x_degree(T);
    1870         168 :   if (r==1) { gel(V, idx) = Sp; return; }
    1871          63 :   S = F2xqX_get_red(Sp, T);
    1872          63 :   Xp = F2xqX_rem(Xp, S, T);
    1873          63 :   Sq = F2xqXQV_red(Sq, S, T);
    1874             :   while (1)
    1875          28 :   {
    1876          91 :     pari_sp btop = avma;
    1877             :     long l;
    1878          91 :     GEN w0 = random_F2xqX(n, v, T), g = w0;
    1879         112 :     for (l=1; l<d; l++) /* sum_{0<i<d} w^(q^i), result in (F_q)^r */
    1880          21 :       g = F2xX_add(w0, F2xqX_F2xqXQV_eval(g, Sq, S, T));
    1881          91 :     w0 = g;
    1882         532 :     for (l=1; l<dT; l++) /* sum_{0<i<k} w^(2^i), result in (F_2)^r */
    1883         441 :       g = F2xX_add(w0, F2xqXQ_sqr(g,S,T));
    1884          91 :     f = F2xqX_gcd(g, Sp, T);
    1885          91 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1886          28 :     set_avma(btop);
    1887             :   }
    1888          63 :   f = F2xqX_normalize(f, T);
    1889          63 :   ff = F2xqX_div(Sp, f , T);
    1890          63 :   F2xqX_edf_simple(f, xp, Xp, Sq, d, T, V, idx);
    1891          63 :   F2xqX_edf_simple(ff, xp, Xp, Sq, d, T, V, idx+degpol(f)/d);
    1892             : }
    1893             : 
    1894             : static GEN
    1895         315 : F2xqX_factor_Shoup(GEN S, GEN xp, GEN T)
    1896             : {
    1897         315 :   long i, n, s = 0;
    1898             :   GEN X, Xp, Xq, Sq, D, V;
    1899         315 :   long vT = get_F2x_var(T);
    1900             :   pari_timer ti;
    1901         315 :   n = get_F2xqX_degree(S);
    1902         315 :   S = F2xqX_get_red(S, T);
    1903         315 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    1904         315 :   X  = polx_F2xX(get_F2xqX_var(S), vT);
    1905         315 :   Xp = F2xqXQ_sqr(X, S, T);
    1906         315 :   Xq = F2xqXQ_Frobenius(xp, Xp, S, T);
    1907         315 :   Sq = F2xqXQ_powers(Xq, n-1, S, T);
    1908         315 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_Frobenius");
    1909         315 :   D = F2xqX_ddf_Shoup(S, Xq, T);
    1910         315 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_ddf_Shoup");
    1911         315 :   s = ddf_to_nbfact(D);
    1912         315 :   V = cgetg(s+1, t_COL);
    1913         847 :   for (i = 1, s = 1; i <= n; i++)
    1914             :   {
    1915         532 :     GEN Di = gel(D,i);
    1916         532 :     long ni = degpol(Di), ri = ni/i;
    1917         532 :     if (ni == 0) continue;
    1918         350 :     Di = F2xqX_normalize(Di, T);
    1919         350 :     if (ni == i) { gel(V, s++) = Di; continue; }
    1920          42 :     F2xqX_edf_simple(Di, xp, Xp, Sq, i, T, V, s);
    1921          42 :     if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_edf(%ld)",i);
    1922          42 :     s += ri;
    1923             :   }
    1924         315 :   return V;
    1925             : }
    1926             : 
    1927             : static GEN
    1928        1267 : F2xqX_factor_Cantor(GEN f, GEN T)
    1929             : {
    1930             :   GEN xp, E, F, V;
    1931             :   long i, j, l;
    1932        1267 :   T = F2x_get_red(T);
    1933        1267 :   f = F2xqX_normalize(f, T);
    1934        1267 :   switch(degpol(f))
    1935             :   {
    1936          14 :     case -1: retmkmat2(mkcol(f), mkvecsmall(1));
    1937          14 :     case 0: return trivial_fact();
    1938          21 :     case 1: retmkmat2(mkcol(f), mkvecsmall(1));
    1939         483 :     case 2: return F2xqX_factor_2(f, T);
    1940             :   }
    1941         735 :   if (F2xY_degreex(f) <= 0) return F2x_factorff_i(F2xX_to_F2x(f), T);
    1942         273 :   xp = F2x_Frobenius(T);
    1943         273 :   V = F2xqX_factor_squarefree(f, T);
    1944         273 :   l = lg(V);
    1945         273 :   F = cgetg(l, t_VEC);
    1946         273 :   E = cgetg(l, t_VEC);
    1947         987 :   for (i=1, j=1; i < l; i++)
    1948         714 :     if (degpol(gel(V,i)))
    1949             :     {
    1950         315 :       GEN Fj = F2xqX_factor_Shoup(gel(V,i), xp, T);
    1951         315 :       gel(F, j) = Fj;
    1952         315 :       gel(E, j) = const_vecsmall(lg(Fj)-1, i);
    1953         315 :       j++;
    1954             :     }
    1955         273 :   return sort_factor_pol(FE_concat(F,E,j), cmp_Flx);
    1956             : }
    1957             : 
    1958             : static GEN
    1959           0 : FlxqX_Berlekamp_i(GEN f, GEN T, ulong p)
    1960             : {
    1961           0 :   long lfact, d = degpol(f), j, k, lV;
    1962             :   GEN E, t, V, xp;
    1963           0 :   switch(d)
    1964             :   {
    1965           0 :     case -1: retmkmat2(mkcolcopy(f), mkvecsmall(1));
    1966           0 :     case 0: return trivial_fact();
    1967             :   }
    1968           0 :   T = Flx_get_red(T, p);
    1969           0 :   f = FlxqX_normalize(f, T, p);
    1970           0 :   if (FlxY_degreex(f) <= 0) return Flx_factorff_i(FlxX_to_Flx(f), T, p);
    1971           0 :   if (degpol(f)==2) return FlxqX_factor_2(f, T, p);
    1972           0 :   xp = Flx_Frobenius(T, p);
    1973           0 :   V = FlxqX_factor_squarefree_i(f, xp, T, p); lV = lg(V);
    1974             : 
    1975             :   /* to hold factors and exponents */
    1976           0 :   t = cgetg(d+1,t_VEC);
    1977           0 :   E = cgetg(d+1, t_VECSMALL);
    1978           0 :   lfact = 1;
    1979           0 :   for (k=1; k<lV ; k++)
    1980             :   {
    1981           0 :     if (degpol(gel(V,k))==0) continue;
    1982           0 :     gel(t,lfact) = FlxqX_normalize(gel(V, k), T,p);
    1983           0 :     d = FlxqX_split_Berlekamp(&gel(t,lfact), xp, T, p);
    1984           0 :     for (j = 0; j < d; j++) E[lfact+j] = k;
    1985           0 :     lfact += d;
    1986             :   }
    1987           0 :   setlg(t, lfact);
    1988           0 :   setlg(E, lfact);
    1989           0 :   return sort_factor_pol(mkvec2(t, E), cmp_Flx);
    1990             : }
    1991             : 
    1992             : static GEN
    1993           0 : FpXQX_Berlekamp_i(GEN f, GEN T, GEN p)
    1994             : {
    1995           0 :   long lfact, d = degpol(f), j, k, lV;
    1996             :   GEN E, t, V;
    1997           0 :   switch(d)
    1998             :   {
    1999           0 :     case -1: retmkmat2(mkcolcopy(f), mkvecsmall(1));
    2000           0 :     case 0: return trivial_fact();
    2001             :   }
    2002           0 :   T = FpX_get_red(T, p);
    2003           0 :   f = FpXQX_normalize(f, T, p);
    2004           0 :   if (isabsolutepol(f)) return FpX_factorff_i(simplify_shallow(f), T, p);
    2005           0 :   if (degpol(f)==2) return FpXQX_factor_2(f, T, p);
    2006           0 :   V = FpXQX_factor_Yun(f, T, p); lV = lg(V);
    2007             : 
    2008             :   /* to hold factors and exponents */
    2009           0 :   t = cgetg(d+1,t_VEC);
    2010           0 :   E = cgetg(d+1, t_VECSMALL);
    2011           0 :   lfact = 1;
    2012           0 :   for (k=1; k<lV ; k++)
    2013             :   {
    2014           0 :     if (degpol(gel(V,k))==0) continue;
    2015           0 :     gel(t,lfact) = FpXQX_normalize(gel(V, k), T,p);
    2016           0 :     d = FpXQX_split_Berlekamp(&gel(t,lfact), T, p);
    2017           0 :     for (j = 0; j < d; j++) E[lfact+j] = k;
    2018           0 :     lfact += d;
    2019             :   }
    2020           0 :   setlg(t, lfact);
    2021           0 :   setlg(E, lfact);
    2022           0 :   return sort_factor_pol(mkvec2(t, E), cmp_RgX);
    2023             : }
    2024             : 
    2025             : long
    2026         132 : FlxqX_ddf_degree(GEN S, GEN XP, GEN T, ulong p)
    2027             : {
    2028         132 :   pari_sp av = avma;
    2029             :   GEN X, b, g, xq, q;
    2030             :   long i, j, n, v, B, l, m, bo, ro;
    2031             :   pari_timer ti;
    2032             :   hashtable h;
    2033             : 
    2034         132 :   n = get_FlxqX_degree(S); v = get_FlxqX_var(S);
    2035         132 :   X = polx_FlxX(v,get_Flx_var(T));
    2036         132 :   if (gequal(X,XP)) return 1;
    2037         132 :   B = n/2;
    2038         132 :   l = usqrt(B);
    2039         132 :   m = (B+l-1)/l;
    2040         132 :   T = Flx_get_red(T, p);
    2041         132 :   S = FlxqX_get_red(S, T, p);
    2042         132 :   hash_init_GEN(&h, l+2, gequal, 1);
    2043         132 :   hash_insert_long(&h, X,  0);
    2044         132 :   hash_insert_long(&h, XP, 1);
    2045         132 :   bo = brent_kung_optpow(n, l-1, 1);
    2046         132 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    2047         132 :   q = powuu(p, get_Flx_degree(T));
    2048         132 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2049         132 :   b = XP;
    2050         132 :   if (expi(q) > ro)
    2051             :   {
    2052         132 :     xq = FlxqXQ_powers(b, brent_kung_optpow(n, l-1, 1),  S, T, p);
    2053         132 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_degree: xq baby");
    2054           0 :   } else xq = NULL;
    2055         312 :   for (i = 3; i <= l+1; i++)
    2056             :   {
    2057         200 :     b = xq ? FlxqX_FlxqXQV_eval(b, xq, S, T, p)
    2058         200 :            : FlxqXQ_pow(b, q, S, T, p);
    2059         200 :     if (gequal(b,X)) return gc_long(av,i-1);
    2060         180 :     hash_insert_long(&h, b, i-1);
    2061             :   }
    2062         112 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_degree: baby");
    2063         112 :   g = b;
    2064         112 :   xq = FlxqXQ_powers(g, brent_kung_optpow(n, m, 1),  S, T, p);
    2065         112 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_degree: xq giant");
    2066         280 :   for(i = 2; i <= m+1; i++)
    2067             :   {
    2068         252 :     g = FlxqX_FlxqXQV_eval(g, xq, S, T, p);
    2069         252 :     if (hash_haskey_long(&h, g, &j)) return gc_long(av, l*i-j);
    2070             :   }
    2071          28 :   return gc_long(av,n);
    2072             : }
    2073             : 
    2074             : static GEN
    2075         475 : FlxqX_ddf_Shoup(GEN S, GEN Xq, GEN T, ulong p)
    2076             : {
    2077         475 :   pari_sp av = avma;
    2078             :   GEN b, g, h, F, f, Sr, xq, q;
    2079             :   long i, j, n, v, vT, bo, ro;
    2080             :   long B, l, m;
    2081             :   pari_timer ti;
    2082         475 :   n = get_FlxqX_degree(S); v = get_FlxqX_var(S);
    2083         475 :   vT = get_Flx_var(T);
    2084         475 :   if (n == 0) return cgetg(1, t_VEC);
    2085         475 :   if (n == 1) return mkvec(get_FlxqX_mod(S));
    2086         356 :   B = n/2;
    2087         356 :   l = usqrt(B);
    2088         356 :   m = (B+l-1)/l;
    2089         356 :   S = FlxqX_get_red(S, T, p);
    2090         356 :   b = cgetg(l+2, t_VEC);
    2091         356 :   gel(b, 1) = polx_FlxX(v, vT);
    2092         356 :   gel(b, 2) = Xq;
    2093         356 :   bo = brent_kung_optpow(n, l-1, 1);
    2094         356 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    2095         356 :   q = powuu(p, get_Flx_degree(T));
    2096         356 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2097         356 :   if (expi(q) <= ro)
    2098          21 :     for (i = 3; i <= l+1; i++)
    2099          14 :       gel(b, i) = FlxqXQ_pow(gel(b, i-1), q, S, T, p);
    2100             :   else
    2101             :   {
    2102         349 :     xq = FlxqXQ_powers(gel(b, 2), bo, S, T, p);
    2103         349 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: xq baby");
    2104         349 :     for (i = 3; i <= l+1; i++)
    2105           0 :       gel(b, i) = FlxqX_FlxqXQV_eval(gel(b, i-1), xq, S, T, p);
    2106             :   }
    2107         356 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: baby");
    2108         356 :   xq = FlxqXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T, p);
    2109         356 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: xq giant");
    2110         356 :   g = cgetg(m+1, t_VEC);
    2111         356 :   gel(g, 1) = gel(xq, 2);
    2112         732 :   for(i = 2; i <= m; i++)
    2113         376 :     gel(g, i) = FlxqX_FlxqXQV_eval(gel(g, i-1), xq, S, T, p);
    2114         356 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: giant");
    2115         356 :   h = cgetg(m+1, t_VEC);
    2116        1088 :   for (j = 1; j <= m; j++)
    2117             :   {
    2118         732 :     pari_sp av = avma;
    2119         732 :     GEN gj = gel(g, j);
    2120         732 :     GEN e = FlxX_sub(gj, gel(b, 1), p);
    2121         802 :     for (i = 2; i <= l; i++)
    2122          70 :       e = FlxqXQ_mul(e, FlxX_sub(gj, gel(b, i), p), S, T, p);
    2123         732 :     gel(h, j) = gerepileupto(av, e);
    2124             :   }
    2125         356 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: diff");
    2126         356 :   Sr = get_FlxqX_mod(S);
    2127         356 :   F = cgetg(m+1, t_VEC);
    2128        1088 :   for (j = 1; j <= m; j++)
    2129             :   {
    2130         732 :     GEN u = FlxqX_gcd(Sr, gel(h, j), T, p);
    2131         732 :     if (degpol(u))
    2132             :     {
    2133         279 :       u = FlxqX_normalize(u, T, p);
    2134         279 :       Sr = FlxqX_div(Sr, u, T, p);
    2135             :     }
    2136         732 :     gel(F,j) = u;
    2137             :   }
    2138         356 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: F");
    2139         356 :   f = const_vec(n, pol1_FlxX(v, vT));
    2140        1088 :   for (j = 1; j <= m; j++)
    2141             :   {
    2142         732 :     GEN e = gel(F, j);
    2143         732 :     for (i=l-1; i >= 0; i--)
    2144             :     {
    2145         732 :       GEN u = FlxqX_gcd(e, FlxX_sub(gel(g, j), gel(b, i+1), p), T, p);
    2146         732 :       if (degpol(u))
    2147             :       {
    2148         279 :         gel(f, l*j-i) = u = FlxqX_normalize(u, T, p);
    2149         279 :         e = FlxqX_div(e, u, T, p);
    2150             :       }
    2151         732 :       if (!degpol(e)) break;
    2152             :     }
    2153             :   }
    2154         356 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf_Shoup: f");
    2155         356 :   if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
    2156         356 :   return gerepilecopy(av, f);
    2157             : }
    2158             : 
    2159             : static GEN
    2160          42 : FlxqX_ddf_i(GEN f, GEN T, ulong p)
    2161             : {
    2162             :   GEN Xq;
    2163          42 :   if (!get_FlxqX_degree(f)) return cgetg(1, t_VEC);
    2164          42 :   f = FlxqX_get_red(f, T, p);
    2165          42 :   Xq = FlxqX_Frobenius(f, T, p);
    2166          42 :   return FlxqX_ddf_Shoup(f, Xq, T, p);
    2167             : }
    2168             : GEN
    2169           0 : FlxqX_ddf(GEN S, GEN T, ulong p)
    2170             : {
    2171           0 :   T = Flx_get_red(T, p);
    2172           0 :   S = FlxqX_normalize(get_FlxqX_mod(S), T, p);
    2173           0 :   return ddf_to_ddf2( FlxqX_ddf_i(S, T, p) );
    2174             : }
    2175             : GEN
    2176          42 : FlxqX_degfact(GEN S, GEN T, ulong p)
    2177             : {
    2178             :   GEN V;
    2179             :   long i, l;
    2180          42 :   T = Flx_get_red(T, p);
    2181          42 :   S = FlxqX_normalize(get_FlxqX_mod(S), T, p);
    2182          42 :   V = FlxqX_factor_squarefree(S, T, p); l = lg(V);
    2183          84 :   for (i=1; i < l; i++) gel(V,i) = FlxqX_ddf_i(gel(V,i), T, p);
    2184          42 :   return vddf_to_simplefact(V, degpol(S));
    2185             : }
    2186             : 
    2187             : static void
    2188         341 : FlxqX_edf_rec(GEN S, GEN xp, GEN Xp, GEN hp, GEN t, long d, GEN T, ulong p, GEN V, long idx)
    2189             : {
    2190         341 :   GEN Sp = get_FlxqX_mod(S);
    2191             :   GEN u1, u2, f1, f2;
    2192             :   GEN h;
    2193         341 :   h = FlxqX_get_red(hp, T, p);
    2194         341 :   t = FlxqX_rem(t, S, T, p);
    2195         341 :   Xp = FlxqX_rem(Xp, h, T, p);
    2196         341 :   u1 = FlxqX_roots_split(hp, xp, Xp, h, T, p);
    2197         341 :   f1 = FlxqX_gcd(FlxqX_FlxqXQ_eval(u1, t, S, T, p), Sp, T, p);
    2198         341 :   f1 = FlxqX_normalize(f1, T, p);
    2199         341 :   u2 = FlxqX_div(hp, u1, T, p);
    2200         341 :   f2 = FlxqX_div(Sp, f1, T, p);
    2201         341 :   if (degpol(u1)==1)
    2202         233 :     gel(V, idx) = f1;
    2203             :   else
    2204         108 :     FlxqX_edf_rec(FlxqX_get_red(f1, T, p), xp, Xp, u1, t, d, T, p, V, idx);
    2205         341 :   idx += degpol(f1)/d;
    2206         341 :   if (degpol(u2)==1)
    2207         240 :     gel(V, idx) = f2;
    2208             :   else
    2209         101 :     FlxqX_edf_rec(FlxqX_get_red(f2, T, p), xp, Xp, u2, t, d, T, p, V, idx);
    2210         341 : }
    2211             : 
    2212             : static void
    2213         132 : FlxqX_edf(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, ulong p, GEN V, long idx)
    2214             : {
    2215         132 :   long n = degpol(Sp), r = n/d, vS = varn(Sp), vT = get_Flx_var(T);
    2216             :   GEN S, h, t;
    2217             :   pari_timer ti;
    2218         132 :   if (r==1) { gel(V, idx) = Sp; return; }
    2219         132 :   S = FlxqX_get_red(Sp, T, p);
    2220         132 :   Xp = FlxqX_rem(Xp, S, T, p);
    2221         132 :   Xq = FlxqX_rem(Xq, S, T, p);
    2222         132 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2223             :   do
    2224             :   {
    2225         155 :     GEN g = random_FlxqX(n, vS, T, p);
    2226         155 :     t = gel(FlxqXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2227         155 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_edf: FlxqXQ_auttrace");
    2228         155 :     h = FlxqXQ_minpoly(t, S, T, p);
    2229         155 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_edf: FlxqXQ_minpoly");
    2230         155 :   } while (degpol(h) != r);
    2231         132 :   Xp = FlxqXQ_powu(polx_FlxX(vS, vT), p, h, T, p);
    2232         132 :   FlxqX_edf_rec(S, xp, Xp, h, t, d, T, p, V, idx);
    2233             : }
    2234             : 
    2235             : static void
    2236         357 : FlxqX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, ulong p, GEN V, long idx)
    2237             : {
    2238         357 :   long v = varn(Sp), n = degpol(Sp), r = n/d;
    2239             :   GEN S, f, ff;
    2240         357 :   long vT = get_Flx_var(T), dT = get_Flx_degree(T);
    2241         357 :   if (r==1) { gel(V, idx) = Sp; return; }
    2242         175 :   S = FlxqX_get_red(Sp, T, p);
    2243         175 :   Xp = FlxqX_rem(Xp, S, T, p);
    2244         175 :   Xq = FlxqX_rem(Xq, S, T, p);
    2245             :   while (1)
    2246           7 :   {
    2247         182 :     pari_sp btop = avma;
    2248             :     long i;
    2249         182 :     GEN g = random_FlxqX(n, v, T, p);
    2250         182 :     GEN t = gel(FlxqXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2251         182 :     if (lgpol(t) == 0) continue;
    2252         371 :     for(i=1; i<=10; i++)
    2253             :     {
    2254         364 :       pari_sp btop2 = avma;
    2255         364 :       GEN r = random_Flx(dT, vT, p);
    2256         364 :       GEN R = FlxqXQ_halfFrobenius_i(FlxX_Flx_add(t, r, p), xp, Xp, S, T, p);
    2257         364 :       f = FlxqX_gcd(FlxX_Flx_sub(R, pol1_Flx(vT), p), Sp, T, p);
    2258         364 :       if (degpol(f) > 0 && degpol(f) < n) break;
    2259         189 :       set_avma(btop2);
    2260             :     }
    2261         182 :     if (degpol(f) > 0 && degpol(f) < n) break;
    2262           7 :     set_avma(btop);
    2263             :   }
    2264         175 :   f = FlxqX_normalize(f, T, p);
    2265         175 :   ff = FlxqX_div(Sp, f , T, p);
    2266         175 :   FlxqX_edf_simple(f, xp, Xp, Xq, d, T, p, V, idx);
    2267         175 :   FlxqX_edf_simple(ff, xp, Xp, Xq, d, T, p, V, idx+degpol(f)/d);
    2268             : }
    2269             : 
    2270             : static GEN
    2271         286 : FlxqX_factor_Shoup(GEN S, GEN xp, GEN T, ulong p)
    2272             : {
    2273         286 :   long i, n, s = 0;
    2274             :   GEN X, Xp, Xq, D, V;
    2275         286 :   long dT = get_Flx_degree(T), vT = get_Flx_var(T);
    2276         286 :   long e = expi(powuu(p, dT));
    2277             :   pari_timer ti;
    2278         286 :   n = get_FlxqX_degree(S);
    2279         286 :   S = FlxqX_get_red(S, T, p);
    2280         286 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    2281         286 :   X  = polx_FlxX(get_FlxqX_var(S), vT);
    2282         286 :   Xp = FlxqXQ_powu(X, p, S, T, p);
    2283         286 :   Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
    2284         286 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_Frobenius");
    2285         286 :   D = FlxqX_ddf_Shoup(S, Xq, T, p);
    2286         286 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_ddf_Shoup");
    2287         286 :   s = ddf_to_nbfact(D);
    2288         286 :   V = cgetg(s+1, t_COL);
    2289        1239 :   for (i = 1, s = 1; i <= n; i++)
    2290             :   {
    2291         953 :     GEN Di = gel(D,i);
    2292         953 :     long ni = degpol(Di), ri = ni/i;
    2293         953 :     if (ni == 0) continue;
    2294         307 :     Di = FlxqX_normalize(Di, T, p);
    2295         307 :     if (ni == i) { gel(V, s++) = Di; continue; }
    2296         139 :     if (ri <= e*expu(e))
    2297         132 :       FlxqX_edf(Di, xp, Xp, Xq, i, T, p, V, s);
    2298             :     else
    2299           7 :       FlxqX_edf_simple(Di, xp, Xp, Xq, i, T, p, V, s);
    2300         139 :     if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_edf(%ld)",i);
    2301         139 :     s += ri;
    2302             :   }
    2303         286 :   return V;
    2304             : }
    2305             : 
    2306             : static GEN
    2307       12485 : FlxqX_factor_Cantor(GEN f, GEN T, ulong p)
    2308             : {
    2309             :   GEN xp, E, F, V;
    2310             :   long i, j, l;
    2311       12485 :   T = Flx_get_red(T, p);
    2312       12485 :   f = FlxqX_normalize(f, T, p);
    2313       12486 :   switch(degpol(f))
    2314             :   {
    2315          21 :     case -1: retmkmat2(mkcol(f), mkvecsmall(1));
    2316          21 :     case 0: return trivial_fact();
    2317          21 :     case 1: retmkmat2(mkcol(f), mkvecsmall(1));
    2318         797 :     case 2: return FlxqX_factor_2(f, T, p);
    2319             :   }
    2320       11625 :   if (FlxY_degreex(f) <= 0) return Flx_factorff_i(FlxX_to_Flx(f), T, p);
    2321         244 :   xp = Flx_Frobenius(T, p);
    2322         244 :   V = FlxqX_factor_squarefree_i(f, xp, get_Flx_mod(T), p);
    2323         244 :   l = lg(V);
    2324         244 :   F = cgetg(l, t_VEC);
    2325         244 :   E = cgetg(l, t_VEC);
    2326         796 :   for (i=1, j=1; i < l; i++)
    2327         552 :     if (degpol(gel(V,i)))
    2328             :     {
    2329         286 :       GEN Fj = FlxqX_factor_Shoup(gel(V,i), xp, T, p);
    2330         286 :       gel(F, j) = Fj;
    2331         286 :       gel(E, j) = const_vecsmall(lg(Fj)-1, i);
    2332         286 :       j++;
    2333             :     }
    2334         244 :   return sort_factor_pol(FE_concat(F,E,j), cmp_Flx);
    2335             : }
    2336             : 
    2337             : /* T must be squarefree mod p*/
    2338             : GEN
    2339         147 : FlxqX_nbfact_by_degree(GEN f, long *nb, GEN T, ulong p)
    2340             : {
    2341             :   GEN Xq, D;
    2342             :   pari_timer ti;
    2343         147 :   long i, s, n = get_FlxqX_degree(f);
    2344         147 :   GEN V = const_vecsmall(n, 0);
    2345         147 :   pari_sp av = avma;
    2346         147 :   T = Flx_get_red(T, p);
    2347         147 :   f = FlxqX_get_red(f, T, p);
    2348         147 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    2349         147 :   Xq = FlxqX_Frobenius(f, T, p);
    2350         147 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_Frobenius");
    2351         147 :   D = FlxqX_ddf_Shoup(f, Xq, T, p);
    2352         147 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_ddf_Shoup");
    2353         945 :   for (i = 1, s = 0; i <= n; i++)
    2354             :   {
    2355         798 :     V[i] = degpol(gel(D,i))/i;
    2356         798 :     s += V[i];
    2357             :   }
    2358         147 :   *nb = s;
    2359         147 :   set_avma(av); return V;
    2360             : }
    2361             : 
    2362             : long
    2363           0 : FlxqX_nbfact_Frobenius(GEN S, GEN Xq, GEN T, ulong p)
    2364             : {
    2365           0 :   pari_sp av = avma;
    2366           0 :   GEN u = get_FlxqX_mod(S);
    2367             :   long s;
    2368           0 :   if (FlxY_degreex(u) <= 0)
    2369           0 :     s = Flx_nbfactff(FlxX_to_Flx(u), T, p);
    2370             :   else
    2371           0 :     s = ddf_to_nbfact(FlxqX_ddf_Shoup(S, Xq, T, p));
    2372           0 :   return gc_long(av,s);
    2373             : }
    2374             : 
    2375             : long
    2376        7084 : FlxqX_nbfact(GEN S, GEN T, ulong p)
    2377             : {
    2378        7084 :   pari_sp av = avma;
    2379        7084 :   GEN u = get_FlxqX_mod(S);
    2380             :   long s;
    2381        7084 :   if (FlxY_degreex(u) <= 0)
    2382        7084 :     s = Flx_nbfactff(FlxX_to_Flx(u), T, p);
    2383             :   else
    2384           0 :     s = ddf_to_nbfact(FlxqX_ddf_Shoup(S, FlxqX_Frobenius(S, T, p), T, p));
    2385        7084 :   return gc_long(av,s);
    2386             : }
    2387             : 
    2388             : GEN
    2389         187 : FlxqX_factor(GEN x, GEN T, ulong p)
    2390             : {
    2391         187 :   pari_sp av = avma;
    2392         187 :   return gerepilecopy(av, FlxqX_factor_Cantor(x, T, p));
    2393             : }
    2394             : 
    2395             : GEN
    2396         133 : F2xqX_factor(GEN x, GEN T)
    2397             : {
    2398         133 :   pari_sp av = avma;
    2399         133 :   return gerepilecopy(av, F2xqX_factor_Cantor(x, T));
    2400             : }
    2401             : 
    2402             : long
    2403          50 : FpXQX_ddf_degree(GEN S, GEN XP, GEN T, GEN p)
    2404             : {
    2405          50 :   pari_sp av = avma;
    2406             :   GEN X, b, g, xq, q;
    2407             :   long i, j, n, v, B, l, m, bo, ro;
    2408             :   pari_timer ti;
    2409             :   hashtable h;
    2410             : 
    2411          50 :   n = get_FpXQX_degree(S); v = get_FpXQX_var(S);
    2412          50 :   X = pol_x(v);
    2413          50 :   if (gequal(X,XP)) return 1;
    2414          50 :   B = n/2;
    2415          50 :   l = usqrt(B);
    2416          50 :   m = (B+l-1)/l;
    2417          50 :   T = FpX_get_red(T, p);
    2418          50 :   S = FpXQX_get_red(S, T, p);
    2419          50 :   hash_init_GEN(&h, l+2, gequal, 1);
    2420          50 :   hash_insert_long(&h, X,  0);
    2421          50 :   hash_insert_long(&h, simplify_shallow(XP), 1);
    2422          50 :   bo = brent_kung_optpow(n, l-1, 1);
    2423          50 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    2424          50 :   q = powiu(p, get_FpX_degree(T));
    2425          50 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2426          50 :   b = XP;
    2427          50 :   if (expi(q) > ro)
    2428             :   {
    2429          50 :     xq = FpXQXQ_powers(b, brent_kung_optpow(n, l-1, 1),  S, T, p);
    2430          50 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_degree: xq baby");
    2431           0 :   } else xq = NULL;
    2432         143 :   for (i = 3; i <= l+1; i++)
    2433             :   {
    2434         101 :     b = xq ? FpXQX_FpXQXQV_eval(b, xq, S, T, p)
    2435         101 :            : FpXQXQ_pow(b, q, S, T, p);
    2436         101 :     if (gequal(b,X)) return gc_long(av,i-1);
    2437          93 :     hash_insert_long(&h, simplify_shallow(b), i-1);
    2438             :   }
    2439          42 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_degree: baby");
    2440          42 :   g = b;
    2441          42 :   xq = FpXQXQ_powers(g, brent_kung_optpow(n, m, 1),  S, T, p);
    2442          42 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_degree: xq giant");
    2443         105 :   for(i = 2; i <= m+1; i++)
    2444             :   {
    2445         105 :     g = FpXQX_FpXQXQV_eval(g, xq, S, T, p);
    2446         105 :     if (hash_haskey_long(&h, simplify_shallow(g), &j)) return gc_long(av,l*i-j);
    2447             :   }
    2448           0 :   return gc_long(av,n);
    2449             : }
    2450             : 
    2451             : static GEN
    2452          71 : FpXQX_ddf_Shoup(GEN S, GEN Xq, GEN T, GEN p)
    2453             : {
    2454          71 :   pari_sp av = avma;
    2455             :   GEN b, g, h, F, f, Sr, xq, q;
    2456             :   long i, j, n, v, bo, ro;
    2457             :   long B, l, m;
    2458             :   pari_timer ti;
    2459          71 :   n = get_FpXQX_degree(S); v = get_FpXQX_var(S);
    2460          71 :   if (n == 0) return cgetg(1, t_VEC);
    2461          71 :   if (n == 1) return mkvec(get_FpXQX_mod(S));
    2462          64 :   B = n/2;
    2463          64 :   l = usqrt(B);
    2464          64 :   m = (B+l-1)/l;
    2465          64 :   S = FpXQX_get_red(S, T, p);
    2466          64 :   b = cgetg(l+2, t_VEC);
    2467          64 :   gel(b, 1) = pol_x(v);
    2468          64 :   gel(b, 2) = Xq;
    2469          64 :   bo = brent_kung_optpow(n, l-1, 1);
    2470          64 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    2471          64 :   q = powiu(p, get_FpX_degree(T));
    2472          64 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2473          64 :   if (expi(q) <= ro)
    2474           0 :     for (i = 3; i <= l+1; i++)
    2475           0 :       gel(b, i) = FpXQXQ_pow(gel(b, i-1), q, S, T, p);
    2476             :   else
    2477             :   {
    2478          64 :     xq = FpXQXQ_powers(gel(b, 2), bo, S, T, p);
    2479          64 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: xq baby");
    2480          85 :     for (i = 3; i <= l+1; i++)
    2481          21 :       gel(b, i) = FpXQX_FpXQXQV_eval(gel(b, i-1), xq, S, T, p);
    2482             :   }
    2483          64 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: baby");
    2484          64 :   xq = FpXQXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T, p);
    2485          64 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: xq giant");
    2486          64 :   g = cgetg(m+1, t_VEC);
    2487          64 :   gel(g, 1) = gel(xq, 2);
    2488         108 :   for(i = 2; i <= m; i++)
    2489          44 :     gel(g, i) = FpXQX_FpXQXQV_eval(gel(g, i-1), xq, S, T, p);
    2490          64 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: giant");
    2491          64 :   h = cgetg(m+1, t_VEC);
    2492         172 :   for (j = 1; j <= m; j++)
    2493             :   {
    2494         108 :     pari_sp av = avma;
    2495         108 :     GEN gj = gel(g, j);
    2496         108 :     GEN e = FpXX_sub(gj, gel(b, 1), p);
    2497         171 :     for (i = 2; i <= l; i++)
    2498          63 :       e = FpXQXQ_mul(e, FpXX_sub(gj, gel(b, i), p), S, T, p);
    2499         108 :     gel(h, j) = gerepileupto(av, e);
    2500             :   }
    2501          64 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: diff");
    2502          64 :   Sr = get_FpXQX_mod(S);
    2503          64 :   F = cgetg(m+1, t_VEC);
    2504         172 :   for (j = 1; j <= m; j++)
    2505             :   {
    2506         108 :     GEN u = FpXQX_gcd(Sr, gel(h,j), T, p);
    2507         108 :     if (degpol(u))
    2508             :     {
    2509          78 :       u = FpXQX_normalize(u, T, p);
    2510          78 :       Sr = FpXQX_div(Sr, u, T, p);
    2511             :     }
    2512         108 :     gel(F,j) = u;
    2513             :   }
    2514          64 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: F");
    2515          64 :   f = const_vec(n, pol_1(v));
    2516         172 :   for (j = 1; j <= m; j++)
    2517             :   {
    2518         108 :     GEN e = gel(F, j);
    2519         150 :     for (i=l-1; i >= 0; i--)
    2520             :     {
    2521         150 :       GEN u = FpXQX_gcd(e, FpXX_sub(gel(g, j), gel(b, i+1), p), T, p);
    2522         150 :       if (degpol(u))
    2523             :       {
    2524          99 :         gel(f, l*j-i) = u = FpXQX_normalize(u, T, p);
    2525          99 :         e = FpXQX_div(e, u, T, p);
    2526             :       }
    2527         150 :       if (!degpol(e)) break;
    2528             :     }
    2529             :   }
    2530          64 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf_Shoup: f");
    2531          64 :   if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
    2532          64 :   return gerepilecopy(av, f);
    2533             : }
    2534             : 
    2535             : static GEN
    2536          49 : FpXQX_ddf_i(GEN f, GEN T, GEN p)
    2537             : {
    2538             :   GEN Xq;
    2539          49 :   if (!get_FpXQX_degree(f)) return cgetg(1,t_VEC);
    2540          49 :   f = FpXQX_get_red(f, T, p);
    2541          49 :   Xq = FpXQX_Frobenius(f, T, p);
    2542          49 :   return FpXQX_ddf_Shoup(f, Xq, T, p);
    2543             : }
    2544             : 
    2545             : static GEN
    2546           7 : FpXQX_ddf_raw(GEN f, GEN T, GEN p)
    2547             : {
    2548           7 :   if (lgefint(p)==3)
    2549             :   {
    2550           0 :     ulong pp = p[2];
    2551             :     GEN M;
    2552           0 :     long vT = get_FpX_var(T);
    2553           0 :     if (pp==2)
    2554             :     {
    2555           0 :       M = F2xqX_ddf(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    2556           0 :       return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
    2557             :     }
    2558           0 :     M = FlxqX_ddf(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    2559           0 :     return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
    2560             :   }
    2561           7 :   T = FpX_get_red(T, p);
    2562           7 :   f = FpXQX_normalize(get_FpXQX_mod(f), T, p);
    2563           7 :   return ddf_to_ddf2( FpXQX_ddf_i(f, T, p) );
    2564             : }
    2565             : 
    2566             : GEN
    2567           7 : FpXQX_ddf(GEN x, GEN T, GEN p)
    2568           7 : { pari_sp av = avma; return gerepilecopy(av, FpXQX_ddf_raw(x,T,p)); }
    2569             : 
    2570             : static GEN
    2571          42 : FpXQX_degfact_raw(GEN f, GEN T, GEN p)
    2572             : {
    2573             :   GEN V;
    2574             :   long i,l;
    2575          42 :   if (lgefint(p)==3)
    2576             :   {
    2577           0 :     ulong pp = p[2];
    2578           0 :     long vT = get_FpX_var(T);
    2579           0 :     if (pp==2)
    2580           0 :       return F2xqX_degfact(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    2581             :     else
    2582           0 :       return FlxqX_degfact(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    2583             :   }
    2584          42 :   T = FpX_get_red(T, p);
    2585          42 :   f = FpXQX_normalize(get_FpXQX_mod(f), T, p);
    2586          42 :   V = FpXQX_factor_Yun(f, T, p); l = lg(V);
    2587          84 :   for (i=1; i < l; i++) gel(V,i) = FpXQX_ddf_i(gel(V,i), T, p);
    2588          42 :   return vddf_to_simplefact(V, degpol(f));
    2589             : }
    2590             : 
    2591             : GEN
    2592          42 : FpXQX_degfact(GEN x, GEN T, GEN p)
    2593          42 : { pari_sp av = avma; return gerepilecopy(av, FpXQX_degfact_raw(x,T,p)); }
    2594             : 
    2595             : static void
    2596          23 : FpXQX_edf_rec(GEN S, GEN xp, GEN Xp, GEN hp, GEN t, long d, GEN T, GEN p, GEN V, long idx)
    2597             : {
    2598          23 :   GEN Sp = get_FpXQX_mod(S);
    2599             :   GEN u1, u2, f1, f2;
    2600             :   GEN h;
    2601          23 :   h = FpXQX_get_red(hp, T, p);
    2602          23 :   t = FpXQX_rem(t, S, T, p);
    2603          23 :   Xp = FpXQX_rem(Xp, h, T, p);
    2604          23 :   u1 = FpXQX_roots_split(hp, xp, Xp, h, T, p);
    2605          23 :   f1 = FpXQX_gcd(FpXQX_FpXQXQ_eval(u1, t, S, T, p), Sp, T, p);
    2606          23 :   f1 = FpXQX_normalize(f1, T, p);
    2607          23 :   u2 = FpXQX_div(hp, u1, T, p);
    2608          23 :   f2 = FpXQX_div(Sp, f1, T, p);
    2609          23 :   if (degpol(u1)==1)
    2610          23 :     gel(V, idx) = f1;
    2611             :   else
    2612           0 :     FpXQX_edf_rec(FpXQX_get_red(f1, T, p), xp, Xp, u1, t, d, T, p, V, idx);
    2613          23 :   idx += degpol(f1)/d;
    2614          23 :   if (degpol(u2)==1)
    2615           8 :     gel(V, idx) = f2;
    2616             :   else
    2617          15 :     FpXQX_edf_rec(FpXQX_get_red(f2, T, p), xp, Xp, u2, t, d, T, p, V, idx);
    2618          23 : }
    2619             : 
    2620             : static void
    2621           8 : FpXQX_edf(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, GEN p, GEN V, long idx)
    2622             : {
    2623           8 :   long n = degpol(Sp), r = n/d, vS = varn(Sp);
    2624             :   GEN S, h, t;
    2625             :   pari_timer ti;
    2626           8 :   if (r==1) { gel(V, idx) = Sp; return; }
    2627           8 :   S = FpXQX_get_red(Sp, T, p);
    2628           8 :   Xp = FpXQX_rem(Xp, S, T, p);
    2629           8 :   Xq = FpXQX_rem(Xq, S, T, p);
    2630           8 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2631             :   do
    2632             :   {
    2633           8 :     GEN g = random_FpXQX(n, vS, T, p);
    2634           8 :     t = gel(FpXQXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2635           8 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_edf: FpXQXQ_auttrace");
    2636           8 :     h = FpXQXQ_minpoly(t, S, T, p);
    2637           8 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_edf: FpXQXQ_minpoly");
    2638           8 :   } while (degpol(h) != r);
    2639           8 :   Xp = FpXQXQ_pow(pol_x(vS), p, h, T, p);
    2640           8 :   FpXQX_edf_rec(S, xp, Xp, h, t, d, T, p, V, idx);
    2641             : }
    2642             : 
    2643             : static void
    2644           0 : FpXQX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, GEN p, GEN V, long idx)
    2645             : {
    2646           0 :   long v = varn(Sp), n = degpol(Sp), r = n/d;
    2647             :   GEN S, f, ff;
    2648           0 :   long vT = get_FpX_var(T), dT = get_FpX_degree(T);
    2649           0 :   if (r==1) { gel(V, idx) = Sp; return; }
    2650           0 :   S = FpXQX_get_red(Sp, T, p);
    2651           0 :   Xp = FpXQX_rem(Xp, S, T, p);
    2652           0 :   Xq = FpXQX_rem(Xq, S, T, p);
    2653             :   while (1)
    2654           0 :   {
    2655           0 :     pari_sp btop = avma;
    2656             :     long i;
    2657           0 :     GEN g = random_FpXQX(n, v, T, p);
    2658           0 :     GEN t = gel(FpXQXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2659           0 :     if (lgpol(t) == 0) continue;
    2660           0 :     for(i=1; i<=10; i++)
    2661             :     {
    2662           0 :       pari_sp btop2 = avma;
    2663           0 :       GEN r = random_FpX(dT, vT, p);
    2664           0 :       GEN R = FpXQXQ_halfFrobenius_i(FqX_Fq_add(t, r, T, p), xp, Xp, S, T, p);
    2665           0 :       f = FpXQX_gcd(FqX_Fq_add(R, gen_m1, T, p), Sp, T, p);
    2666           0 :       if (degpol(f) > 0 && degpol(f) < n) break;
    2667           0 :       set_avma(btop2);
    2668             :     }
    2669           0 :     if (degpol(f) > 0 && degpol(f) < n) break;
    2670           0 :     set_avma(btop);
    2671             :   }
    2672           0 :   f = FpXQX_normalize(f, T, p);
    2673           0 :   ff = FpXQX_div(Sp, f , T, p);
    2674           0 :   FpXQX_edf_simple(f,  xp, Xp, Xq, d, T, p, V, idx);
    2675           0 :   FpXQX_edf_simple(ff, xp, Xp, Xq, d, T, p, V, idx+degpol(f)/d);
    2676             : }
    2677             : 
    2678             : static GEN
    2679          22 : FpXQX_factor_Shoup(GEN S, GEN xp, GEN T, GEN p)
    2680             : {
    2681          22 :   long i, n, s = 0, dT = get_FpX_degree(T), e = expi(powiu(p, dT));
    2682             :   GEN X, Xp, Xq, D, V;
    2683             :   pari_timer ti;
    2684          22 :   n = get_FpXQX_degree(S);
    2685          22 :   S = FpXQX_get_red(S, T, p);
    2686          22 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    2687          22 :   X  = pol_x(get_FpXQX_var(S));
    2688          22 :   Xp = FpXQXQ_pow(X, p, S, T, p);
    2689          22 :   Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
    2690          22 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_Frobenius");
    2691          22 :   D = FpXQX_ddf_Shoup(S, Xq, T, p);
    2692          22 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_ddf_Shoup");
    2693          22 :   s = ddf_to_nbfact(D);
    2694          22 :   V = cgetg(s+1, t_COL);
    2695         140 :   for (i = 1, s = 1; i <= n; i++)
    2696             :   {
    2697         118 :     GEN Di = gel(D,i);
    2698         118 :     long ni = degpol(Di), ri = ni/i;
    2699         118 :     if (ni == 0) continue;
    2700          50 :     Di = FpXQX_normalize(Di, T, p);
    2701          50 :     if (ni == i) { gel(V, s++) = Di; continue; }
    2702           8 :     if (ri <= e*expu(e))
    2703           8 :       FpXQX_edf(Di, xp, Xp, Xq, i, T, p, V, s);
    2704             :     else
    2705           0 :       FpXQX_edf_simple(Di, xp, Xp, Xq, i, T, p, V, s);
    2706           8 :     if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_edf(%ld)",i);
    2707           8 :     s += ri;
    2708             :   }
    2709          22 :   return V;
    2710             : }
    2711             : 
    2712             : static GEN
    2713         170 : FpXQX_factor_Cantor(GEN f, GEN T, GEN p)
    2714             : {
    2715             :   GEN xp, E, F, V;
    2716             :   long i, j, l;
    2717         170 :   T = FpX_get_red(T, p);
    2718         170 :   f = FpXQX_normalize(f, T, p);
    2719         170 :   switch(degpol(f))
    2720             :   {
    2721          14 :     case -1: retmkmat2(mkcol(f), mkvecsmall(1));
    2722          14 :     case 0: return trivial_fact();
    2723          21 :     case 1: retmkmat2(mkcol(f), mkvecsmall(1));
    2724          43 :     case 2: return FpXQX_factor_2(f, T, p);
    2725             :   }
    2726          78 :   if (isabsolutepol(f)) return FpX_factorff_i(simplify_shallow(f), T, p);
    2727          22 :   xp = FpX_Frobenius(T, p);
    2728          22 :   V = FpXQX_factor_Yun(f, T, p);
    2729          22 :   l = lg(V);
    2730          22 :   F = cgetg(l, t_VEC);
    2731          22 :   E = cgetg(l, t_VEC);
    2732          44 :   for (i=1, j=1; i < l; i++)
    2733          22 :     if (degpol(gel(V,i)))
    2734             :     {
    2735          22 :       GEN Fj = FpXQX_factor_Shoup(gel(V,i), xp, T, p);
    2736          22 :       gel(E,j) = const_vecsmall(lg(Fj)-1, i);
    2737          22 :       gel(F,j) = Fj; j++;
    2738             :     }
    2739          22 :   return sort_factor_pol(FE_concat(F,E,j), cmp_RgX);
    2740             : }
    2741             : 
    2742             : long
    2743           0 : FpXQX_nbfact_Frobenius(GEN S, GEN Xq, GEN T, GEN p)
    2744             : {
    2745           0 :   pari_sp av = avma;
    2746           0 :   GEN u = get_FpXQX_mod(S);
    2747             :   long s;
    2748           0 :   if (lgefint(p)==3)
    2749             :   {
    2750           0 :     ulong pp = p[2];
    2751           0 :     long vT = get_FpX_var(T);
    2752           0 :     GEN Sp = ZXXT_to_FlxXT(S,pp,vT), Xqp = ZXX_to_FlxX(Xq,pp,vT);
    2753           0 :     s = FlxqX_nbfact_Frobenius(Sp, Xqp, ZXT_to_FlxT(T,pp), pp);
    2754             :   }
    2755           0 :   else if (isabsolutepol(u))
    2756           0 :     s = FpX_nbfactff(simplify_shallow(u), T, p);
    2757             :   else
    2758           0 :     s = ddf_to_nbfact(FpXQX_ddf_Shoup(S, Xq, T, p));
    2759           0 :   return gc_long(av,s);
    2760             : }
    2761             : 
    2762             : long
    2763           0 : FpXQX_nbfact(GEN S, GEN T, GEN p)
    2764             : {
    2765           0 :   pari_sp av = avma;
    2766           0 :   GEN u = get_FpXQX_mod(S);
    2767             :   long s;
    2768           0 :   if (lgefint(p)==3)
    2769             :   {
    2770           0 :     ulong pp = p[2];
    2771           0 :     long vT = get_FpX_var(T);
    2772           0 :     s = FlxqX_nbfact(ZXXT_to_FlxXT(S,pp,vT), ZXT_to_FlxT(T,pp), pp);
    2773             :   }
    2774           0 :   else if (isabsolutepol(u))
    2775           0 :     s = FpX_nbfactff(simplify_shallow(u), T, p);
    2776             :   else
    2777           0 :     s = ddf_to_nbfact(FpXQX_ddf_Shoup(S, FpXQX_Frobenius(S, T, p), T, p));
    2778           0 :   return gc_long(av,s);
    2779             : }
    2780             : long
    2781           0 : FqX_nbfact(GEN u, GEN T, GEN p)
    2782           0 : { return T ? FpXQX_nbfact(u, T, p): FpX_nbfact(u, p); }
    2783             : 
    2784             : static GEN
    2785           0 : FpXQX_factor_Berlekamp_i(GEN f, GEN T, GEN p)
    2786             : {
    2787           0 :   if (lgefint(p)==3)
    2788             :   {
    2789           0 :     ulong pp = p[2];
    2790             :     GEN M;
    2791           0 :     long vT = get_FpX_var(T);
    2792           0 :     if (pp==2)
    2793             :     {
    2794           0 :       M = F2xqX_factor_Cantor(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    2795           0 :       return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
    2796             :     }
    2797           0 :     M = FlxqX_Berlekamp_i(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    2798           0 :     return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
    2799             :   }
    2800           0 :   return FpXQX_Berlekamp_i(f, T, p);
    2801             : }
    2802             : GEN
    2803           0 : FpXQX_factor_Berlekamp(GEN x, GEN T, GEN p)
    2804           0 : { pari_sp av = avma; return gerepilecopy(av, FpXQX_factor_Berlekamp_i(x,T,p)); }
    2805             : 
    2806             : static GEN
    2807       13602 : FpXQX_factor_i(GEN f, GEN T, GEN p)
    2808             : {
    2809       13602 :   if (lgefint(p)==3)
    2810             :   {
    2811       13432 :     ulong pp = p[2];
    2812             :     GEN M;
    2813       13432 :     long vT = get_FpX_var(T);
    2814       13432 :     if (pp==2)
    2815             :     {
    2816        1134 :       M = F2xqX_factor_Cantor(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    2817        1127 :       return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
    2818             :     }
    2819       12298 :     M = FlxqX_factor_Cantor(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    2820       12292 :     return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
    2821             :   }
    2822         170 :   return FpXQX_factor_Cantor(f, T, p);
    2823             : }
    2824             : GEN
    2825       13602 : FpXQX_factor(GEN x, GEN T, GEN p)
    2826       13602 : { pari_sp av = avma; return gerepilecopy(av, FpXQX_factor_i(x,T,p)); }
    2827             : 
    2828             : long
    2829       10591 : FlxqX_is_squarefree(GEN P, GEN T, ulong p)
    2830             : {
    2831       10591 :   pari_sp av = avma;
    2832       10591 :   GEN z = FlxqX_gcd(P, FlxX_deriv(P, p), T, p);
    2833       10591 :   return gc_long(av, degpol(z)==0);
    2834             : }
    2835             : 
    2836             : long
    2837      252973 : FqX_is_squarefree(GEN P, GEN T, GEN p)
    2838             : {
    2839      252973 :   pari_sp av = avma;
    2840      252973 :   GEN z = FqX_gcd(P, FqX_deriv(P, T, p), T, p);
    2841      252973 :   return gc_long(av, degpol(z)==0);
    2842             : }
    2843             : 
    2844             : /* as RgX_to_FpXQ(FqX_to_FFX), leaving alone t_FFELT */
    2845             : static GEN
    2846         350 : RgX_to_FFX(GEN x, GEN ff)
    2847             : {
    2848             :   long i, lx;
    2849         350 :   GEN p = FF_p_i(ff), T = FF_mod(ff), y =  cgetg_copy(x,&lx);
    2850         350 :   y[1] = x[1]; if (degpol(T) == 1) T = NULL;
    2851        1120 :   for (i = 2; i < lx; i++)
    2852             :   {
    2853         770 :     GEN c = gel(x,i);
    2854         770 :     gel(y,i) = typ(c) == t_FFELT? c: Fq_to_FF(Rg_to_Fq(c,T,p), ff);
    2855             :   }
    2856         350 :   return y;
    2857             : }
    2858             : 
    2859             : #define code(t1,t2) ((t1 << 6) | t2)
    2860             : /* Check types and replace F by a monic normalized FpX having the same roots
    2861             :  * Don't bother to make constant polynomials monic */
    2862             : static GEN
    2863      167951 : factmod_init(GEN f, GEN *pD, GEN *pT, GEN *pp)
    2864             : {
    2865      167951 :   const char *s = "factormod";
    2866      167951 :   GEN T, p, D = *pD;
    2867      167951 :   if (typ(f) != t_POL) pari_err_TYPE(s,f);
    2868      167951 :   if (!D)
    2869             :   {
    2870      103439 :     long pa, t = RgX_type(f, pp, pT, &pa);
    2871      103439 :     if (t == t_FFELT) return f;
    2872           0 :     *pD = gen_0;
    2873           0 :     if (t != t_INTMOD && t != code(t_POLMOD,t_INTMOD)) pari_err_TYPE(s,f);
    2874           0 :     return RgX_to_FqX(f, *pT, *pp);
    2875             :   }
    2876       64512 :   if (typ(D) == t_FFELT) { *pD = NULL; *pT = D; return RgX_to_FFX(f,D); }
    2877       64162 :   if (!ff_parse_Tp(D, &T, &p, 1)) pari_err_TYPE(s,D);
    2878       64148 :   if (T && varncmp(varn(T), varn(f)) <= 0)
    2879           0 :     pari_err_PRIORITY(s, T, "<=", varn(f));
    2880       64148 :   *pT = T; *pp = p; return RgX_to_FqX(f, T, p);
    2881             : }
    2882             : #undef code
    2883             : 
    2884             : int
    2885       64841 : ff_parse_Tp(GEN Tp, GEN *T, GEN *p, long red)
    2886             : {
    2887       64841 :   long t = typ(Tp);
    2888       64841 :   *T = *p = NULL;
    2889       64841 :   if (t == t_INT) { *p = Tp; return cmpiu(*p, 1) > 0; }
    2890         462 :   if (t != t_VEC || lg(Tp) != 3) return 0;
    2891         455 :   *T = gel(Tp,1);
    2892         455 :   *p = gel(Tp,2);
    2893         455 :   if (typ(*p) != t_INT)
    2894             :   {
    2895         420 :     if (typ(*T) != t_INT) return 0;
    2896         420 :     swap(*T, *p); /* support both [T,p] and [p,T] */
    2897             :   }
    2898         455 :   if (red) *T = RgX_to_FpX(*T, *p);
    2899         455 :   return cmpiu(*p, 1) > 0 && typ(*T) == t_POL && RgX_is_ZX(*T);
    2900             : }
    2901             : 
    2902             : static GEN
    2903        4851 : to_Fq(GEN x, GEN T, GEN p)
    2904             : {
    2905        4851 :   long i, lx, tx = typ(x);
    2906             :   GEN y;
    2907             : 
    2908        4851 :   if (tx == t_INT)
    2909         273 :     y = mkintmod(x,p);
    2910             :   else
    2911             :   {
    2912        4578 :     if (tx != t_POL) pari_err_TYPE("to_Fq",x);
    2913        4578 :     y = cgetg_copy(x,&lx); y[1] = x[1];
    2914      134204 :     for (i=2; i<lx; i++) gel(y,i) = mkintmod(gel(x,i), p);
    2915             :   }
    2916        4851 :   return mkpolmod(y, T);
    2917             : }
    2918             : static GEN
    2919         252 : to_Fq_pol(GEN x, GEN T, GEN p)
    2920             : {
    2921         252 :   long i, lx = lg(x);
    2922         252 :   if (lx == 2)
    2923             :   {
    2924          21 :     GEN y = cgetg(3,t_POL); y[1]=x[1];
    2925          21 :     gel(y,2) = mkintmod(gen_0,p); return y;
    2926             :   }
    2927         749 :   for (i = 2; i < lx; i++) gel(x,i) = to_Fq(gel(x,i),T,p);
    2928         231 :   return x;
    2929             : }
    2930             : static GEN
    2931         189 : to_Fq_fact(GEN fa, GEN T, GEN p)
    2932             : {
    2933         189 :   GEN P = gel(fa,1);
    2934         189 :   long j, l = lg(P);
    2935         189 :   p = icopy(p); T = FpX_to_mod(T, p);
    2936         441 :   for (j=1; j<l; j++) gel(P,j) = to_Fq_pol(gel(P,j), T,p);
    2937         189 :   return fa;
    2938             : }
    2939             : static GEN
    2940         224 : to_FqC(GEN P, GEN T, GEN p)
    2941             : {
    2942         224 :   long j, l = lg(P);
    2943         224 :   p = icopy(p); T = FpX_to_mod(T, p);
    2944        4557 :   for (j=1; j<l; j++) gel(P,j) = to_Fq(gel(P,j), T,p);
    2945         224 :   return P;
    2946             : }
    2947             : 
    2948             : GEN
    2949         910 : factmod(GEN f, GEN D)
    2950             : {
    2951             :   pari_sp av;
    2952             :   GEN y, F, P, E, T, p;
    2953         910 :   f = factmod_init(f, &D, &T,&p);
    2954         903 :   if (!D) return FFX_factor(f, T);
    2955         686 :   av = avma;
    2956         686 :   F = FqX_factor(f, T, p); P = gel(F,1); E = gel(F,2);
    2957         672 :   if (!T)
    2958             :   {
    2959         483 :     y = cgetg(3, t_MAT);
    2960         483 :     gel(y,1) = FpXC_to_mod(P, p);
    2961         483 :     gel(y,2) = Flc_to_ZC(E); return gerepileupto(av, y);
    2962             :   }
    2963         189 :   F = gerepilecopy(av, mkmat2(simplify_shallow(P), Flc_to_ZC(E)));
    2964         189 :   return to_Fq_fact(F, T, p);
    2965             : }
    2966             : GEN
    2967       63301 : simplefactmod(GEN f, GEN D)
    2968             : {
    2969       63301 :   pari_sp av = avma;
    2970             :   GEN T, p;
    2971       63301 :   f = factmod_init(f, &D, &T,&p);
    2972       63301 :   if (lg(f) <= 3) { set_avma(av); return trivial_fact(); }
    2973       63238 :   f = D? FqX_degfact(f, T, p): FFX_degfact(f, T);
    2974       63238 :   return gerepileupto(av, Flm_to_ZM(f));
    2975             : }
    2976             : static GEN
    2977          14 : sqf_to_fact(GEN f)
    2978             : {
    2979          14 :   long i, j, l = lg(f);
    2980          14 :   GEN P = cgetg(l, t_COL), E = cgetg(l, t_COL);
    2981          35 :   for (i = j = 1; i < l; i++)
    2982          21 :     if (degpol(gel(f,i)))
    2983             :     {
    2984          21 :       gel(P,j) = gel(f,i);
    2985          21 :       gel(E,j) = utoi(i); j++;
    2986             :     }
    2987          14 :   setlg(P,j);
    2988          14 :   setlg(E,j); return mkvec2(P,E);
    2989             : }
    2990             : 
    2991             : GEN
    2992          35 : factormodSQF(GEN f, GEN D)
    2993             : {
    2994          35 :   pari_sp av = avma;
    2995             :   GEN F, T, p;
    2996          35 :   f = factmod_init(f, &D, &T,&p);
    2997          35 :   if (lg(f) <= 3) { set_avma(av); return trivial_fact(); }
    2998          14 :   if (!D)
    2999           7 :     F = sqf_to_fact(FFX_factor_squarefree(f, T));
    3000             :   else
    3001             :   {
    3002           7 :     F = sqf_to_fact(FqX_factor_squarefree(f,T,p));
    3003           7 :     gel(F,1) = FqXC_to_mod(gel(F,1), T,p);
    3004             :   }
    3005          14 :   settyp(F,t_MAT); return gerepilecopy(av, F);
    3006             : }
    3007             : GEN
    3008          28 : factormodDDF(GEN f, GEN D)
    3009             : {
    3010          28 :   pari_sp av = avma;
    3011             :   GEN F, T, p;
    3012          28 :   f = factmod_init(f, &D, &T,&p);
    3013          28 :   if (lg(f) <= 3) { set_avma(av); return trivial_fact(); }
    3014          14 :   if (!D) return FFX_ddf(f, T);
    3015           7 :   F = FqX_ddf(f,T,p);
    3016           7 :   gel(F,1) = FqXC_to_mod(gel(F,1), T,p);
    3017           7 :   gel(F,2) = Flc_to_ZC(gel(F,2));
    3018           7 :   settyp(F, t_MAT); return gerepilecopy(av, F);
    3019             : }
    3020             : 
    3021             : GEN
    3022       63777 : factormod0(GEN f, GEN p, long flag)
    3023             : {
    3024       63777 :   if (flag == 0) return factmod(f,p);
    3025       63301 :   if (flag != 1) pari_err_FLAG("factormod");
    3026       63301 :   return simplefactmod(f,p);
    3027             : }
    3028             : GEN
    3029      103677 : polrootsmod(GEN f, GEN D)
    3030             : {
    3031             :   pari_sp av;
    3032             :   GEN y, T, p;
    3033      103677 :   f = factmod_init(f, &D, &T,&p);
    3034      103670 :   if (!D) return FFX_roots(f, T);
    3035         308 :   av = avma; y = FqX_roots(f, T, p);
    3036         280 :   if (!T) return gerepileupto(av, FpC_to_mod(y,p));
    3037         224 :   y = gerepilecopy(av, simplify_shallow(y));
    3038         224 :   return to_FqC(y, T, p);
    3039             : }
    3040             : 
    3041             : GEN /* OBSOLETE */
    3042           0 : rootmod0(GEN f, GEN p, long flag) { (void)flag; return polrootsmod(f,p); }
    3043             : GEN /* OBSOLETE */
    3044           0 : factorff(GEN f, GEN p, GEN T)
    3045             : {
    3046           0 :   pari_sp av = avma;
    3047           0 :   GEN D = (p && T)? mkvec2(T,p): NULL;
    3048           0 :   return gerepileupto(av, factmod(f,D));
    3049             : }
    3050             : GEN /* OBSOLETE */
    3051           0 : polrootsff(GEN f, GEN p, GEN T)
    3052             : {
    3053           0 :   pari_sp av = avma;
    3054           0 :   GEN D = (p && T)? mkvec2(T,p): NULL;
    3055           0 :   return gerepileupto(av, polrootsmod(f, D));
    3056             : }

Generated by: LCOV version 1.13