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 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.10.0 lcov report (development 21061-8feaff2) Lines: 1338 1657 80.7 %
Date: 2017-09-24 06:24:57 Functions: 101 119 84.9 %
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. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : 
      18             : /*******************************************************************/
      19             : /**                                                               **/
      20             : /**           Isomorphisms between finite fields                  **/
      21             : /**                                                               **/
      22             : /*******************************************************************/
      23             : 
      24             : /* compute the reciprocical isomorphism of S mod T,p, i.e. V such that
      25             :    V(S)=X  mod T,p*/
      26             : 
      27             : GEN
      28        1225 : Flxq_ffisom_inv(GEN S,GEN T, ulong p)
      29             : {
      30        1225 :   pari_sp ltop = avma;
      31        1225 :   long n = get_Flx_degree(T);
      32        1225 :   GEN M = Flxq_matrix_pow(S,n,n,T,p);
      33        1225 :   GEN V = Flm_Flc_invimage(M, vecsmall_ei(n, 2), p);
      34        1225 :   return gerepileupto(ltop, Flv_to_Flx(V, get_Flx_var(T)));
      35             : }
      36             : 
      37             : GEN
      38         168 : FpXQ_ffisom_inv(GEN S,GEN T, GEN p)
      39             : {
      40         168 :   pari_sp ltop = avma;
      41         168 :   long n = get_FpX_degree(T);
      42         168 :   GEN V, M = FpXQ_matrix_pow(S,n,n,T,p);
      43         168 :   V = FpM_FpC_invimage(M, col_ei(n, 2), p);
      44         168 :   return gerepilecopy(ltop, RgV_to_RgX(V, get_FpX_var(T)));
      45             : }
      46             : 
      47             : /* Let M the matrix of the Frobenius automorphism of Fp[X]/(T).
      48             :  * Compute M^d
      49             :  * TODO: use left-right binary (tricky!)
      50             :  */
      51             : GEN
      52         315 : Flm_Frobenius_pow(GEN M, long d, GEN T, ulong p)
      53             : {
      54         315 :   pari_sp ltop=avma;
      55         315 :   long i,l = get_Flx_degree(T);
      56         315 :   GEN R, W = gel(M,2);
      57         315 :   for (i = 2; i <= d; ++i) W = Flm_Flc_mul(M,W,p);
      58         315 :   R=Flxq_matrix_pow(Flv_to_Flx(W,get_Flx_var(T)),l,l,T,p);
      59         315 :   return gerepileupto(ltop,R);
      60             : }
      61             : 
      62             : GEN
      63           0 : FpM_Frobenius_pow(GEN M, long d, GEN T, GEN p)
      64             : {
      65           0 :   pari_sp ltop=avma;
      66           0 :   long i,l = get_FpX_degree(T);
      67           0 :   GEN R, W = gel(M,2);
      68           0 :   for (i = 2; i <= d; ++i) W = FpM_FpC_mul(M,W,p);
      69           0 :   R=FpXQ_matrix_pow(RgV_to_RgX(W, get_FpX_var(T)),l,l,T,p);
      70           0 :   return gerepilecopy(ltop,R);
      71             : }
      72             : 
      73             : /* Essentially we want to compute
      74             :  * FqM_ker(MA-pol_x(v),U,l)
      75             :  * To avoid use of matrix in Fq we procede as follows:
      76             :  * We compute FpM_ker(U(MA),l) and then we recover
      77             :  * the eigen value by Galois action, see formula.
      78             :  */
      79             : 
      80             : static GEN
      81        3087 : Flx_Flm_Flc_eval(GEN U, GEN MA, GEN a, ulong p)
      82             : {
      83        3087 :   long i, l = lg(U);
      84        3087 :   GEN b = Flv_Fl_mul(a, uel(U, l-1), p);
      85       13454 :   for (i=l-2; i>=2; i--)
      86       10367 :     b = Flv_add(Flm_Flc_mul(MA, b, p), Flv_Fl_mul(a, uel(U, i), p), p);
      87        3087 :   return b;
      88             : }
      89             : 
      90             : static GEN
      91        2632 : Flx_intersect_ker(GEN P, GEN MA, GEN U, ulong p)
      92             : {
      93        2632 :   pari_sp ltop = avma;
      94        2632 :   long i, vp = get_Flx_var(P), vu = get_Flx_var(U), r = get_Flx_degree(U);
      95             :   GEN V, A, R;
      96             :   ulong ib0;
      97             :   pari_timer T;
      98        2632 :   if (DEBUGLEVEL>=4) timer_start(&T);
      99        2632 :   V = Flx_div(Flx_Fl_add(monomial_Flx(1, get_Flx_degree(P), vu), p-1, p), U, p);
     100             :   do
     101             :   {
     102        3087 :     A = Flx_Flm_Flc_eval(V, MA, random_Flv(lg(MA)-1, p), p);
     103        3087 :   } while (zv_equal0(A));
     104        2632 :   if (DEBUGLEVEL>=4) timer_printf(&T,"matrix polcyclo");
     105             :   /*The formula is
     106             :    * a_{r-1} = -\phi(a_0)/b_0
     107             :    * a_{i-1} = \phi(a_i)+b_ia_{r-1}  i=r-1 to 1
     108             :    * Where a_0=A[1] and b_i=U[i+2] */
     109        2632 :   ib0 = Fl_inv(Fl_neg(U[2], p), p);
     110        2632 :   R = cgetg(r+1,t_MAT);
     111        2632 :   gel(R,1) = A;
     112        2632 :   gel(R,r) = Flm_Flc_mul(MA, Flv_Fl_mul(A,ib0, p), p);
     113        5852 :   for(i=r-1; i>1; i--)
     114             :   {
     115        3220 :     gel(R,i) = Flm_Flc_mul(MA,gel(R,i+1),p);
     116        3220 :     Flv_add_inplace(gel(R,i), Flv_Fl_mul(gel(R,r), U[i+2], p), p);
     117             :   }
     118        2632 :   return gerepileupto(ltop, Flm_to_FlxX(Flm_transpose(R),vp,vu));
     119             : }
     120             : 
     121             : static GEN
     122          28 : FpX_FpM_FpC_eval(GEN U, GEN MA, GEN a, GEN p)
     123             : {
     124          28 :   long i, l = lg(U);
     125          28 :   GEN b = FpC_Fp_mul(a, gel(U, l-1), p);
     126          56 :   for (i=l-2; i>=2; i--)
     127          28 :     b = FpC_add(FpM_FpC_mul(MA, b, p), FpC_Fp_mul(a, gel(U, i), p), p);
     128          28 :   return b;
     129             : }
     130             : 
     131             : static GEN
     132          28 : FpX_intersect_ker(GEN P, GEN MA, GEN U, GEN l)
     133             : {
     134          28 :   pari_sp ltop = avma;
     135          28 :   long i, vp = get_FpX_var(P), vu = get_FpX_var(U), r = get_FpX_degree(U);
     136             :   GEN V, A, R, ib0;
     137             :   pari_timer T;
     138          28 :   if (DEBUGLEVEL>=4) timer_start(&T);
     139          28 :   V = FpX_div(FpX_Fp_sub(monomial(gen_1, get_FpX_degree(P), vu), gen_1, l), U, l);
     140             :   do
     141             :   {
     142          28 :     A = FpX_FpM_FpC_eval(V, MA, random_FpC(lg(MA)-1, l), l);
     143          28 :   } while (ZV_equal0(A));
     144          28 :   if (DEBUGLEVEL>=4) timer_printf(&T,"matrix polcyclo");
     145             :   /*The formula is
     146             :    * a_{r-1} = -\phi(a_0)/b_0
     147             :    * a_{i-1} = \phi(a_i)+b_ia_{r-1}  i=r-1 to 1
     148             :    * Where a_0=A[1] and b_i=U[i+2] */
     149          28 :   ib0 = Fp_inv(negi(gel(U,2)),l);
     150          28 :   R = cgetg(r+1,t_MAT);
     151          28 :   gel(R,1) = A;
     152          28 :   gel(R,r) = FpM_FpC_mul(MA, FpC_Fp_mul(A,ib0,l), l);
     153         252 :   for(i=r-1;i>1;i--)
     154         672 :     gel(R,i) = FpC_add(FpM_FpC_mul(MA,gel(R,i+1),l),
     155         448 :         FpC_Fp_mul(gel(R,r), gel(U,i+2), l),l);
     156          28 :   return gerepilecopy(ltop,RgM_to_RgXX(shallowtrans(R),vp,vu));
     157             : }
     158             : 
     159             : /* n must divide both the degree of P and Q.  Compute SP and SQ such
     160             :   that the subfield of FF_l[X]/(P) generated by SP and the subfield of
     161             :   FF_l[X]/(Q) generated by SQ are isomorphic of degree n.  P and Q do
     162             :   not need to be of the same variable.  if MA (resp. MB) is not NULL,
     163             :   must be the matrix of the Frobenius map in FF_l[X]/(P) (resp.
     164             :   FF_l[X]/(Q) ).  */
     165             : /* Note on the implementation choice:
     166             :  * We assume the prime p is very large
     167             :  * so we handle Frobenius as matrices.
     168             :  */
     169             : 
     170             : void
     171        5117 : Flx_ffintersect(GEN P, GEN Q, long n, ulong l,GEN *SP, GEN *SQ, GEN MA, GEN MB)
     172             : {
     173        5117 :   pari_sp ltop = avma;
     174        5117 :   long vp = get_Flx_var(P), vq =  get_Flx_var(Q);
     175        5117 :   long np = get_Flx_degree(P), nq = get_Flx_degree(Q), e;
     176             :   ulong pg;
     177             :   GEN A, B, Ap, Bp;
     178        5117 :   if (np<=0) pari_err_IRREDPOL("FpX_ffintersect", P);
     179        5117 :   if (nq<=0) pari_err_IRREDPOL("FpX_ffintersect", Q);
     180        5117 :   if (n<=0 || np%n || nq%n)
     181           0 :     pari_err_TYPE("FpX_ffintersect [bad degrees]",stoi(n));
     182        5117 :   e = u_lvalrem(n, l, &pg);
     183        5117 :   if(!MA) MA = Flx_matFrobenius(P,l);
     184        5117 :   if(!MB) MB = Flx_matFrobenius(Q,l);
     185        5117 :   A = Ap = pol0_Flx(vp);
     186        5117 :   B = Bp = pol0_Flx(vq);
     187        5117 :   if (pg > 1)
     188             :   {
     189             :     pari_timer T;
     190        3787 :     GEN ipg = utoipos(pg);
     191        3787 :     if (l%pg == 1)
     192             :     /* No need to use relative extension, so don't. (Well, now we don't
     193             :      * in the other case either, but this special case is more efficient) */
     194             :     {
     195             :       GEN L;
     196             :       ulong z, An, Bn;
     197        2471 :       z = Fl_neg(rootsof1_Fl(pg, l), l);
     198        2471 :       if (DEBUGLEVEL>=4) timer_start(&T);
     199        2471 :       A = Flm_ker(Flm_Fl_add(MA, z, l),l);
     200        2471 :       if (lg(A)!=2) pari_err_IRREDPOL("FpX_ffintersect",P);
     201        2471 :       A = Flv_to_Flx(gel(A,1),vp);
     202             : 
     203        2471 :       B = Flm_ker(Flm_Fl_add(MB, z, l),l);
     204        2471 :       if (lg(B)!=2) pari_err_IRREDPOL("FpX_ffintersect",Q);
     205        2471 :       B = Flv_to_Flx(gel(B,1),vq);
     206             : 
     207        2471 :       if (DEBUGLEVEL>=4) timer_printf(&T, "FpM_ker");
     208        2471 :       An = Flxq_powu(A,pg,P,l)[2];
     209        2471 :       Bn = Flxq_powu(B,pg,Q,l)[2];
     210        2471 :       if (!Bn) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     211        2471 :       z = Fl_div(An,Bn,l);
     212        2471 :       L = Fp_sqrtn(utoi(z),ipg,utoipos(l),NULL);
     213        2471 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     214        2471 :       if (DEBUGLEVEL>=4) timer_printf(&T, "Fp_sqrtn");
     215        2471 :       B = Flx_Fl_mul(B,itou(L),l);
     216             :     }
     217             :     else
     218             :     {
     219             :       GEN L, An, Bn, z, U;
     220        1316 :       U = gmael(Flx_factor(ZX_to_Flx(polcyclo(pg, fetch_var()),l),l),1,1);
     221        1316 :       A = Flx_intersect_ker(P, MA, U, l);
     222        1316 :       B = Flx_intersect_ker(Q, MB, U, l);
     223        1316 :       if (DEBUGLEVEL>=4) timer_start(&T);
     224        1316 :       An = gel(FlxYqq_pow(A,ipg,P,U,l),2);
     225        1316 :       Bn = gel(FlxYqq_pow(B,ipg,Q,U,l),2);
     226        1316 :       if (DEBUGLEVEL>=4) timer_printf(&T,"pows [P,Q]");
     227        1316 :       z = Flxq_div(An,Bn,U,l);
     228        1316 :       L = Flxq_sqrtn(z,ipg,U,l,NULL);
     229        1316 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     230        1316 :       if (DEBUGLEVEL>=4) timer_printf(&T,"FpXQ_sqrtn");
     231        1316 :       B = FlxqX_Flxq_mul(B,L,U,l);
     232        1316 :       A = FlxY_evalx(A,0,l);
     233        1316 :       B = FlxY_evalx(B,0,l);
     234        1316 :       (void)delete_var();
     235             :     }
     236             :   }
     237        5117 :   if (e)
     238             :   {
     239             :     GEN VP, VQ, Ay, By;
     240        1386 :     ulong lmun = l-1;
     241             :     long j;
     242        1386 :     MA = Flm_Fl_add(MA,lmun,l);
     243        1386 :     MB = Flm_Fl_add(MB,lmun,l);
     244        1386 :     Ay = pol1_Flx(vp);
     245        1386 :     By = pol1_Flx(vq);
     246        1386 :     VP = vecsmall_ei(np, 1);
     247        1386 :     VQ = np == nq? VP: vecsmall_ei(nq, 1); /* save memory */
     248        3024 :     for(j=0;j<e;j++)
     249             :     {
     250        1638 :       if (j)
     251             :       {
     252         252 :         Ay = Flxq_mul(Ay,Flxq_powu(Ap,lmun,P,l),P,l);
     253         252 :         VP = Flx_to_Flv(Ay,np);
     254             :       }
     255        1638 :       Ap = Flm_Flc_invimage(MA,VP,l);
     256        1638 :       Ap = Flv_to_Flx(Ap,vp);
     257             : 
     258        1638 :       if (j)
     259             :       {
     260         252 :         By = Flxq_mul(By,Flxq_powu(Bp,lmun,Q,l),Q,l);
     261         252 :         VQ = Flx_to_Flv(By,nq);
     262             :       }
     263        1638 :       Bp = Flm_Flc_invimage(MB,VQ,l);
     264        1638 :       Bp = Flv_to_Flx(Bp,vq);
     265             :     }
     266             :   }
     267        5117 :   *SP = Flx_add(A,Ap,l);
     268        5117 :   *SQ = Flx_add(B,Bp,l);
     269        5117 :   gerepileall(ltop,2,SP,SQ);
     270        5117 : }
     271             : 
     272             : /* Let l be a prime number, P, Q in ZZ[X].  P and Q are both
     273             :  * irreducible modulo l and degree(P) divides degree(Q).  Output a
     274             :  * monomorphism between FF_l[X]/(P) and FF_l[X]/(Q) as a polynomial R such
     275             :  * that Q | P(R) mod l.  If P and Q have the same degree, it is of course an
     276             :  * isomorphism.  */
     277             : GEN
     278        1225 : Flx_ffisom(GEN P,GEN Q,ulong l)
     279             : {
     280        1225 :   pari_sp av = avma;
     281             :   GEN SP, SQ, R;
     282        1225 :   Flx_ffintersect(P,Q,get_Flx_degree(P),l,&SP,&SQ,NULL,NULL);
     283        1225 :   R = Flxq_ffisom_inv(SP,P,l);
     284        1225 :   return gerepileupto(av, Flx_Flxq_eval(R,SQ,Q,l));
     285             : }
     286             : 
     287             : void
     288          21 : FpX_ffintersect(GEN P, GEN Q, long n, GEN l, GEN *SP, GEN *SQ, GEN MA, GEN MB)
     289             : {
     290          21 :   pari_sp ltop = avma;
     291             :   long vp, vq, np, nq, e;
     292             :   ulong pg;
     293             :   GEN A, B, Ap, Bp;
     294          21 :   if (lgefint(l)==3)
     295             :   {
     296           0 :     ulong pp = l[2];
     297           0 :     GEN Pp = ZX_to_Flx(P,pp), Qp = ZX_to_Flx(Q,pp);
     298           0 :     GEN MAp = MA ? ZM_to_Flm(MA, pp): NULL;
     299           0 :     GEN MBp = MB ? ZM_to_Flm(MB, pp): NULL;
     300           0 :     Flx_ffintersect(Pp, Qp, n, pp, SP, SQ, MAp, MBp);
     301           0 :     *SP = Flx_to_ZX(*SP); *SQ = Flx_to_ZX(*SQ);
     302           0 :     gerepileall(ltop,2,SP,SQ);
     303           0 :     return;
     304             :   }
     305          21 :   vp = get_FpX_var(P); np = get_FpX_degree(P);
     306          21 :   vq = get_FpX_var(Q); nq = get_FpX_degree(Q);
     307          21 :   if (np<=0) pari_err_IRREDPOL("FpX_ffintersect", P);
     308          21 :   if (nq<=0) pari_err_IRREDPOL("FpX_ffintersect", Q);
     309          21 :   if (n<=0 || np%n || nq%n)
     310           0 :     pari_err_TYPE("FpX_ffintersect [bad degrees]",stoi(n));
     311          21 :   e = u_pvalrem(n, l, &pg);
     312          21 :   if(!MA) MA = FpX_matFrobenius(P, l);
     313          21 :   if(!MB) MB = FpX_matFrobenius(Q, l);
     314          21 :   A = Ap = pol_0(vp);
     315          21 :   B = Bp = pol_0(vq);
     316          21 :   if (pg > 1)
     317             :   {
     318          21 :     GEN ipg = utoipos(pg);
     319             :     pari_timer T;
     320          21 :     if (umodiu(l,pg) == 1)
     321             :     /* No need to use relative extension, so don't. (Well, now we don't
     322             :      * in the other case either, but this special case is more efficient) */
     323             :     {
     324             :       GEN L, An, Bn, z;
     325           7 :       z = negi( rootsof1u_Fp(pg, l) );
     326           7 :       if (DEBUGLEVEL>=4) timer_start(&T);
     327           7 :       A = FpM_ker(RgM_Rg_add_shallow(MA, z),l);
     328           7 :       if (lg(A)!=2) pari_err_IRREDPOL("FpX_ffintersect",P);
     329           7 :       A = RgV_to_RgX(gel(A,1),vp);
     330             : 
     331           7 :       B = FpM_ker(RgM_Rg_add_shallow(MB, z),l);
     332           7 :       if (lg(B)!=2) pari_err_IRREDPOL("FpX_ffintersect",Q);
     333           7 :       B = RgV_to_RgX(gel(B,1),vq);
     334             : 
     335           7 :       if (DEBUGLEVEL>=4) timer_printf(&T, "FpM_ker");
     336           7 :       An = gel(FpXQ_pow(A,ipg,P,l),2);
     337           7 :       Bn = gel(FpXQ_pow(B,ipg,Q,l),2);
     338           7 :       if (!signe(Bn)) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     339           7 :       z = Fp_div(An,Bn,l);
     340           7 :       L = Fp_sqrtn(z,ipg,l,NULL);
     341           7 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     342           7 :       if (DEBUGLEVEL>=4) timer_printf(&T, "Fp_sqrtn");
     343           7 :       B = FpX_Fp_mul(B,L,l);
     344             :     }
     345             :     else
     346             :     {
     347             :       GEN L, An, Bn, z, U;
     348          14 :       U = gmael(FpX_factor(polcyclo(pg,fetch_var()),l),1,1);
     349          14 :       A = FpX_intersect_ker(P, MA, U, l);
     350          14 :       B = FpX_intersect_ker(Q, MB, U, l);
     351          14 :       if (DEBUGLEVEL>=4) timer_start(&T);
     352          14 :       An = gel(FpXYQQ_pow(A,ipg,P,U,l),2);
     353          14 :       Bn = gel(FpXYQQ_pow(B,ipg,Q,U,l),2);
     354          14 :       if (DEBUGLEVEL>=4) timer_printf(&T,"pows [P,Q]");
     355          14 :       if (!signe(Bn)) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     356          14 :       z = Fq_div(An,Bn,U,l);
     357          14 :       L = Fq_sqrtn(z,ipg,U,l,NULL);
     358          14 :       if (!L) pari_err_IRREDPOL("FpX_ffintersect", mkvec2(P,Q));
     359          14 :       if (DEBUGLEVEL>=4) timer_printf(&T,"FpXQ_sqrtn");
     360          14 :       B = FqX_Fq_mul(B,L,U,l);
     361          14 :       A = FpXY_evalx(A,gen_0,l);
     362          14 :       B = FpXY_evalx(B,gen_0,l);
     363          14 :       (void)delete_var();
     364             :     }
     365             :   }
     366          21 :   if (e)
     367             :   {
     368           0 :     GEN VP, VQ, Ay, By, lmun = subiu(l,1);
     369             :     long j;
     370           0 :     MA = RgM_Rg_add_shallow(MA,gen_m1);
     371           0 :     MB = RgM_Rg_add_shallow(MB,gen_m1);
     372           0 :     Ay = pol_1(vp);
     373           0 :     By = pol_1(vq);
     374           0 :     VP = col_ei(np, 1);
     375           0 :     VQ = np == nq? VP: col_ei(nq, 1); /* save memory */
     376           0 :     for(j=0;j<e;j++)
     377             :     {
     378           0 :       if (j)
     379             :       {
     380           0 :         Ay = FpXQ_mul(Ay,FpXQ_pow(Ap,lmun,P,l),P,l);
     381           0 :         VP = RgX_to_RgC(Ay,np);
     382             :       }
     383           0 :       Ap = FpM_FpC_invimage(MA,VP,l);
     384           0 :       Ap = RgV_to_RgX(Ap,vp);
     385             : 
     386           0 :       if (j)
     387             :       {
     388           0 :         By = FpXQ_mul(By,FpXQ_pow(Bp,lmun,Q,l),Q,l);
     389           0 :         VQ = RgX_to_RgC(By,nq);
     390             :       }
     391           0 :       Bp = FpM_FpC_invimage(MB,VQ,l);
     392           0 :       Bp = RgV_to_RgX(Bp,vq);
     393             :     }
     394             :   }
     395          21 :   *SP = FpX_add(A,Ap,l);
     396          21 :   *SQ = FpX_add(B,Bp,l);
     397          21 :   gerepileall(ltop,2,SP,SQ);
     398             : }
     399             : /* Let l be a prime number, P, Q in ZZ[X].  P and Q are both
     400             :  * irreducible modulo l and degree(P) divides degree(Q).  Output a
     401             :  * monomorphism between FF_l[X]/(P) and FF_l[X]/(Q) as a polynomial R such
     402             :  * that Q | P(R) mod l.  If P and Q have the same degree, it is of course an
     403             :  * isomorphism.  */
     404             : GEN
     405        1190 : FpX_ffisom(GEN P, GEN Q, GEN p)
     406             : {
     407        1190 :   pari_sp av = avma;
     408             :   GEN SP, SQ, R;
     409        1190 :   if (lgefint(p)==3)
     410             :   {
     411        1190 :     ulong pp = p[2];
     412        1190 :     GEN R = Flx_ffisom(ZX_to_Flx(P,pp), ZX_to_Flx(Q,pp), pp);
     413        1190 :     return gerepileupto(av, Flx_to_ZX(R));
     414             :   }
     415           0 :   FpX_ffintersect(P,Q,get_FpX_degree(P),p,&SP,&SQ,NULL,NULL);
     416           0 :   R = FpXQ_ffisom_inv(SP,P,p);
     417           0 :   return gerepileupto(av, FpX_FpXQ_eval(R,SQ,Q,p));
     418             : }
     419             : 
     420             : /* Let l be a prime number, P a ZX irreducible modulo l, MP the matrix of the
     421             :  * Frobenius automorphism of F_l[X]/(P).
     422             :  * Factor P over the subfield of F_l[X]/(P) of index d. */
     423             : static GEN
     424          21 : FpX_factorgalois(GEN P, GEN l, long d, long w, GEN MP)
     425             : {
     426          21 :   pari_sp ltop = avma;
     427             :   GEN R, V, Tl, z, M;
     428          21 :   long v = get_FpX_var(P), n = get_FpX_degree(P);
     429          21 :   long k, m = n/d;
     430             : 
     431             :   /* x - y */
     432          21 :   if (m == 1) return deg1pol_shallow(gen_1, deg1pol_shallow(subis(l,1), gen_0, w), v);
     433           0 :   M = FpM_Frobenius_pow(MP,d,P,l);
     434             : 
     435           0 :   Tl = leafcopy(P); setvarn(Tl,w);
     436           0 :   V = cgetg(m+1,t_VEC);
     437           0 :   gel(V,1) = pol_x(w);
     438           0 :   z = gel(M,2);
     439           0 :   gel(V,2) = RgV_to_RgX(z,w);
     440           0 :   for(k=3;k<=m;k++)
     441             :   {
     442           0 :     z = FpM_FpC_mul(M,z,l);
     443           0 :     gel(V,k) = RgV_to_RgX(z,w);
     444             :   }
     445           0 :   R = FqV_roots_to_pol(V,Tl,l,v);
     446           0 :   return gerepileupto(ltop,R);
     447             : }
     448             : /* same: P is an Flx, MP an Flm */
     449             : static GEN
     450        3892 : Flx_factorgalois(GEN P, ulong l, long d, long w, GEN MP)
     451             : {
     452        3892 :   pari_sp ltop = avma;
     453             :   GEN R, V, Tl, z, M;
     454        3892 :   long k, n = get_Flx_degree(P), m = n/d;
     455        3892 :   long v = get_Flx_var(P);
     456             : 
     457        3892 :   if (m == 1) {
     458        3577 :     R = polx_Flx(v);
     459        3577 :     gel(R,2) = z = polx_Flx(w); z[3] = l - 1; /* - y */
     460        3577 :     gel(R,3) = pol1_Flx(w);
     461        3577 :     return R; /* x - y */
     462             :   }
     463         315 :   M = Flm_Frobenius_pow(MP,d,P,l);
     464             : 
     465         315 :   Tl = leafcopy(P); setvarn(Tl,w);
     466         315 :   V = cgetg(m+1,t_VEC);
     467         315 :   gel(V,1) = polx_Flx(w);
     468         315 :   z = gel(M,2);
     469         315 :   gel(V,2) = Flv_to_Flx(z,w);
     470         315 :   for(k=3;k<=m;k++)
     471             :   {
     472           0 :     z = Flm_Flc_mul(M,z,l);
     473           0 :     gel(V,k) = Flv_to_Flx(z,w);
     474             :   }
     475         315 :   R = FlxqV_roots_to_pol(V,Tl,l,v);
     476         315 :   return gerepileupto(ltop,R);
     477             : }
     478             : 
     479             : GEN
     480       28987 : Flx_factorff_irred(GEN P, GEN Q, ulong p)
     481             : {
     482       28987 :   pari_sp ltop = avma, av;
     483             :   GEN SP, SQ, MP, MQ, M, FP, FQ, E, V, IR, res;
     484       28987 :   long np = get_Flx_degree(P), nq = get_Flx_degree(Q), d = cgcd(np,nq);
     485       28987 :   long i, vp = get_Flx_var(P), vq = get_Flx_var(Q);
     486       28987 :   if (d==1) retmkcol(Flx_to_FlxX(P, vq));
     487        3892 :   FQ = Flx_matFrobenius(Q,p);
     488        3892 :   av = avma;
     489        3892 :   FP = Flx_matFrobenius(P,p);
     490        3892 :   Flx_ffintersect(P,Q,d,p,&SP,&SQ, FP, FQ);
     491        3892 :   E = Flx_factorgalois(P,p,d,vq, FP);
     492        3892 :   E = FlxX_to_Flm(E,np);
     493        3892 :   MP= Flxq_matrix_pow(SP,np,d,P,p);
     494        3892 :   IR= gel(Flm_indexrank(MP,p),1);
     495        3892 :   E = rowpermute(E, IR);
     496        3892 :   M = rowpermute(MP,IR);
     497        3892 :   M = Flm_inv(M,p);
     498        3892 :   MQ= Flxq_matrix_pow(SQ,nq,d,Q,p);
     499        3892 :   M = Flm_mul(MQ,M,p);
     500        3892 :   M = Flm_mul(M,E,p);
     501        3892 :   M = gerepileupto(av,M);
     502        3892 :   V = cgetg(d+1,t_VEC);
     503        3892 :   gel(V,1) = M;
     504       14007 :   for(i=2;i<=d;i++)
     505       10115 :     gel(V,i) = Flm_mul(FQ,gel(V,i-1),p);
     506        3892 :   res = cgetg(d+1,t_COL);
     507       17899 :   for(i=1;i<=d;i++)
     508       14007 :     gel(res,i) = Flm_to_FlxX(gel(V,i),vp,vq);
     509        3892 :   return gerepileupto(ltop,res);
     510             : }
     511             : 
     512             : /* P,Q irreducible over F_p. Factor P over FF_p[X] / Q  [factors are ordered as
     513             :  * a Frobenius cycle] */
     514             : GEN
     515         406 : FpX_factorff_irred(GEN P, GEN Q, GEN p)
     516             : {
     517         406 :   pari_sp ltop = avma, av;
     518             :   GEN res;
     519         406 :   long np = get_FpX_degree(P), nq = get_FpX_degree(Q), d = cgcd(np,nq);
     520         406 :   if (d==1) return mkcolcopy(P);
     521             : 
     522         406 :   if (lgefint(p)==3)
     523             :   {
     524         385 :     ulong pp = p[2];
     525         385 :     GEN F = Flx_factorff_irred(ZX_to_Flx(P,pp), ZX_to_Flx(Q,pp), pp);
     526         385 :     long i, lF = lg(F);
     527         385 :     res = cgetg(lF, t_COL);
     528        2268 :     for(i=1; i<lF; i++)
     529        1883 :       gel(res,i) = FlxX_to_ZXX(gel(F,i));
     530             :   }
     531             :   else
     532             :   {
     533             :     GEN SP, SQ, MP, MQ, M, FP, FQ, E, V, IR;
     534          21 :     long i, vp = get_FpX_var(P), vq = get_FpX_var(Q);
     535          21 :     FQ = FpX_matFrobenius(Q,p);
     536          21 :     av = avma;
     537          21 :     FP = FpX_matFrobenius(P,p);
     538          21 :     FpX_ffintersect(P,Q,d,p,&SP,&SQ,FP,FQ);
     539             : 
     540          21 :     E = FpX_factorgalois(P,p,d,vq,FP);
     541          21 :     E = RgXX_to_RgM(E,np);
     542          21 :     MP= FpXQ_matrix_pow(SP,np,d,P,p);
     543          21 :     IR= gel(FpM_indexrank(MP,p),1);
     544          21 :     E = rowpermute(E, IR);
     545          21 :     M = rowpermute(MP,IR);
     546          21 :     M = FpM_inv(M,p);
     547          21 :     MQ= FpXQ_matrix_pow(SQ,nq,d,Q,p);
     548          21 :     M = FpM_mul(MQ,M,p);
     549          21 :     M = FpM_mul(M,E,p);
     550          21 :     M = gerepileupto(av,M);
     551          21 :     V = cgetg(d+1,t_VEC);
     552          21 :     gel(V,1) = M;
     553         287 :     for(i=2;i<=d;i++)
     554         266 :       gel(V,i) = FpM_mul(FQ,gel(V,i-1),p);
     555          21 :     res = cgetg(d+1,t_COL);
     556         308 :     for(i=1;i<=d;i++)
     557         287 :       gel(res,i) = RgM_to_RgXX(gel(V,i),vp,vq);
     558             :   }
     559         406 :   return gerepilecopy(ltop,res);
     560             : }
     561             : 
     562             : /* not memory-clean, as Flx_factorff_i, returning only linear factors */
     563             : static GEN
     564       23849 : Flx_rootsff_i(GEN P, GEN T, ulong p)
     565             : {
     566       23849 :   GEN V, F = gel(Flx_factor(P,p), 1);
     567       23849 :   long i, lfact = 1, nmax = lgpol(P), n = lg(F), dT = get_Flx_degree(T);
     568             : 
     569       23849 :   V = cgetg(nmax,t_COL);
     570       51331 :   for(i=1;i<n;i++)
     571             :   {
     572       27482 :     GEN R, Fi = gel(F,i);
     573       27482 :     long di = degpol(Fi), j, r;
     574       27482 :     if (dT % di) continue;
     575       25795 :     R = Flx_factorff_irred(gel(F,i),T,p);
     576       25795 :     r = lg(R);
     577       55384 :     for (j=1; j<r; j++,lfact++)
     578       29589 :       gel(V,lfact) = Flx_neg(gmael(R,j, 2), p);
     579             :   }
     580       23849 :   setlg(V,lfact);
     581       23849 :   gen_sort_inplace(V, (void*) &cmp_Flx, &cmp_nodata, NULL);
     582       23849 :   return V;
     583             : }
     584             : GEN
     585           0 : Flx_rootsff(GEN P, GEN T, ulong p)
     586             : {
     587           0 :   pari_sp av = avma;
     588           0 :   return gerepilecopy(av, Flx_rootsff_i(P, T, p));
     589             : }
     590             : 
     591             : /* dummy implementation */
     592             : static GEN
     593       15043 : F2x_rootsff_i(GEN P, GEN T)
     594             : {
     595       15043 :   return FlxC_to_F2xC(Flx_rootsff_i(F2x_to_Flx(P), F2x_to_Flx(T), 2UL));
     596             : }
     597             : 
     598             : /* not memory-clean, as FpX_factorff_i, returning only linear factors */
     599             : static GEN
     600           0 : FpX_rootsff_i(GEN P, GEN T, GEN p)
     601             : {
     602             :   GEN V, F;
     603             :   long i, lfact, nmax, n, dT;
     604           0 :   if (lgefint(p)==3)
     605             :   {
     606           0 :     ulong pp = p[2];
     607           0 :     GEN V = Flx_rootsff_i(ZX_to_Flx(P,pp), ZXT_to_FlxT(T,pp), pp);
     608           0 :     return FlxC_to_ZXC(V);
     609             :   }
     610           0 :   F = gel(FpX_factor(P,p), 1);
     611           0 :   lfact = 1; nmax = lgpol(P); n = lg(F); dT = get_FpX_degree(T);
     612             : 
     613           0 :   V = cgetg(nmax,t_COL);
     614           0 :   for(i=1;i<n;i++)
     615             :   {
     616           0 :     GEN R, Fi = gel(F,i);
     617           0 :     long di = degpol(Fi), j, r;
     618           0 :     if (dT % di) continue;
     619           0 :     R = FpX_factorff_irred(gel(F,i),T,p);
     620           0 :     r = lg(R);
     621           0 :     for (j=1; j<r; j++,lfact++)
     622           0 :       gel(V,lfact) = Fq_to_FpXQ(Fq_neg(gmael(R,j, 2), T, p), T, p);
     623             :   }
     624           0 :   setlg(V,lfact);
     625           0 :   gen_sort_inplace(V, (void*) &cmp_RgX, &cmp_nodata, NULL);
     626           0 :   return V;
     627             : }
     628             : GEN
     629           0 : FpX_rootsff(GEN P, GEN T, GEN p)
     630             : {
     631           0 :   pari_sp av = avma;
     632           0 :   return gerepilecopy(av, FpX_rootsff_i(P, T, p));
     633             : }
     634             : 
     635             : static GEN
     636         875 : Flx_factorff_i(GEN P, GEN T, ulong p)
     637             : {
     638         875 :   GEN V, E, F = Flx_factor(P, p);
     639         875 :   long i, lfact = 1, nmax = lgpol(P), n = lgcols(F);
     640             : 
     641         875 :   V = cgetg(nmax,t_VEC);
     642         875 :   E = cgetg(nmax,t_VECSMALL);
     643        3682 :   for(i=1;i<n;i++)
     644             :   {
     645        2807 :     GEN R = Flx_factorff_irred(gmael(F,1,i),T,p), e = gmael(F,2,i);
     646        2807 :     long j, r = lg(R);
     647       10437 :     for (j=1; j<r; j++,lfact++)
     648             :     {
     649        7630 :       gel(V,lfact) = gel(R,j);
     650        7630 :       gel(E,lfact) = e;
     651             :     }
     652             :   }
     653         875 :   setlg(V,lfact);
     654         875 :   setlg(E,lfact); return sort_factor_pol(mkvec2(V,E), cmp_Flx);
     655             : }
     656             : 
     657             : static long
     658         280 : simpleff_to_nbfact(GEN F, long dT)
     659             : {
     660         280 :   long i, n = lg(F), k = 0;
     661        2625 :   for (i = 1; i < n; i++)
     662        2345 :     k += cgcd(uel(F,i), dT);
     663         280 :   return k;
     664             : }
     665             : 
     666             : static long
     667         280 : Flx_nbfactff(GEN P, GEN T, ulong p)
     668             : {
     669         280 :   pari_sp av = avma;
     670         280 :   GEN F = gel(Flx_factcantor(P, p, 1), 1);
     671         280 :   long s = simpleff_to_nbfact(F, get_Flx_degree(T));
     672         280 :   avma = av; return s;
     673             : }
     674             : 
     675             : /* dummy implementation */
     676             : static GEN
     677         259 : F2x_factorff_i(GEN P, GEN T)
     678             : {
     679         259 :   GEN M = Flx_factorff_i(F2x_to_Flx(P), F2x_to_Flx(T), 2);
     680         259 :   return mkvec2(FlxXC_to_F2xXC(gel(M,1)), gel(M,2));
     681             : }
     682             : 
     683             : /* not memory-clean */
     684             : static GEN
     685          21 : FpX_factorff_i(GEN P, GEN T, GEN p)
     686             : {
     687          21 :   GEN V, E, F = FpX_factor(P,p);
     688          21 :   long i, lfact = 1, nmax = lgpol(P), n = lgcols(F);
     689             : 
     690          21 :   V = cgetg(nmax,t_VEC);
     691          21 :   E = cgetg(nmax,t_VECSMALL);
     692          42 :   for(i=1;i<n;i++)
     693             :   {
     694          21 :     GEN R = FpX_factorff_irred(gmael(F,1,i),T,p), e = gmael(F,2,i);
     695          21 :     long j, r = lg(R);
     696         308 :     for (j=1; j<r; j++,lfact++)
     697             :     {
     698         287 :       gel(V,lfact) = gel(R,j);
     699         287 :       gel(E,lfact) = e;
     700             :     }
     701             :   }
     702          21 :   setlg(V,lfact);
     703          21 :   setlg(E,lfact); return sort_factor_pol(mkvec2(V,E), cmp_RgX);
     704             : }
     705             : 
     706             : static long
     707           0 : FpX_nbfactff(GEN P, GEN T, GEN p)
     708             : {
     709           0 :   pari_sp av = avma;
     710           0 :   GEN F = gel(FpX_factcantor(P, p, 1), 1);
     711           0 :   long s = simpleff_to_nbfact(F, get_FpX_degree(T));
     712           0 :   avma = av; return s;
     713             : }
     714             : 
     715             : GEN
     716           0 : FpX_factorff(GEN P, GEN T, GEN p)
     717             : {
     718           0 :   pari_sp av = avma;
     719           0 :   return gerepilecopy(av, FpX_factorff_i(P, T, p));
     720             : }
     721             : 
     722             : /***********************************************************************/
     723             : /**                                                                   **/
     724             : /**               Factorisation over finite fields                    **/
     725             : /**                                                                   **/
     726             : /***********************************************************************/
     727             : 
     728             : static GEN
     729        9114 : to_Fq(GEN x, GEN T, GEN p)
     730             : {
     731        9114 :   long i, lx, tx = typ(x);
     732             :   GEN y;
     733             : 
     734        9114 :   if (tx == t_INT)
     735        4557 :     y = mkintmod(x,p);
     736             :   else
     737             :   {
     738        4557 :     if (tx != t_POL) pari_err_TYPE("to_Fq",x);
     739        4557 :     lx = lg(x);
     740        4557 :     y = cgetg(lx,t_POL); y[1] = x[1];
     741        4557 :     for (i=2; i<lx; i++) gel(y,i) = mkintmod(gel(x,i), p);
     742             :   }
     743        9114 :   return mkpolmod(y, T);
     744             : }
     745             : 
     746             : static GEN
     747        4522 : to_Fq_pol(GEN x, GEN T, GEN p)
     748             : {
     749        4522 :   long i, lx = lg(x);
     750        4522 :   for (i=2; i<lx; i++) gel(x,i) = to_Fq(gel(x,i),T,p);
     751        4522 :   return x;
     752             : }
     753             : 
     754             : static GEN
     755         392 : to_Fq_fact(GEN P, GEN E, GEN T, GEN p, pari_sp av)
     756             : {
     757             :   GEN y, u, v;
     758         392 :   long j, l = lg(P), nbf = lg(P);
     759             : 
     760         392 :   u = cgetg(nbf,t_COL);
     761         392 :   v = cgetg(nbf,t_COL);
     762        4914 :   for (j=1; j<l; j++)
     763             :   {
     764        4522 :     gel(u,j) = simplify_shallow(gel(P,j)); /* may contain pols of degree 0 */
     765        4522 :     gel(v,j) = utoi(uel(E,j));
     766             :   }
     767         392 :   y = gerepilecopy(av, mkmat2(u, v));
     768         392 :   u = gel(y,1);
     769         392 :   p = icopy(p);
     770         392 :   T = FpX_to_mod(T, p);
     771         392 :   for (j=1; j<nbf; j++) gel(u,j) = to_Fq_pol(gel(u,j), T,p);
     772         392 :   return y;
     773             : }
     774             : static GEN
     775          28 : to_FqC(GEN P, GEN T, GEN p, pari_sp av)
     776             : {
     777             :   GEN u;
     778          28 :   long j, l = lg(P), nbf = lg(P);
     779             : 
     780          28 :   u = cgetg(nbf,t_COL);
     781          77 :   for (j=1; j<l; j++)
     782          49 :     gel(u,j) = simplify_shallow(gel(P,j)); /* may contain pols of degree 0 */
     783          28 :   u = gerepilecopy(av, u);
     784          28 :   p = icopy(p);
     785          28 :   T = FpX_to_mod(T, p);
     786          28 :   for (j=1; j<nbf; j++) gel(u,j) = to_Fq(gel(u,j), T,p);
     787          28 :   return u;
     788             : }
     789             : 
     790             : static GEN
     791       10509 : FlxqXQ_halfFrobenius_i(GEN a, GEN xp, GEN Xp, GEN S, GEN T, ulong p)
     792             : {
     793       10509 :   GEN ap2 = FlxqXQ_powu(a, p>>1, S, T, p);
     794       10509 :   GEN V = FlxqXQ_autsum(mkvec3(xp, Xp, ap2), get_Flx_degree(T), S, T, p);
     795       10509 :   return gel(V,3);
     796             : }
     797             : 
     798             : GEN
     799         271 : FlxqXQ_halfFrobenius(GEN a, GEN S, GEN T, ulong p)
     800             : {
     801         271 :   long vT = get_Flx_var(T);
     802             :   GEN xp, Xp;
     803         271 :   T = Flx_get_red(T, p);
     804         271 :   S = FlxqX_get_red(S, T, p);
     805         271 :   xp = Flx_Frobenius(T, p);
     806         271 :   Xp = FlxqXQ_powu(polx_FlxX(get_FlxqX_var(S), vT), p, S, T, p);
     807         271 :   return FlxqXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
     808             : }
     809             : 
     810             : static GEN
     811        1113 : FpXQXQ_halfFrobenius_i(GEN a, GEN xp, GEN Xp, GEN S, GEN T, GEN p)
     812             : {
     813        1113 :   GEN ap2 = FpXQXQ_pow(a, shifti(p,-1), S, T, p);
     814        1113 :   GEN V = FpXQXQ_autsum(mkvec3(xp, Xp, ap2), get_FpX_degree(T), S, T, p);
     815        1113 :   return gel(V, 3);
     816             : }
     817             : 
     818             : GEN
     819         138 : FpXQXQ_halfFrobenius(GEN a, GEN S, GEN T, GEN p)
     820             : {
     821         138 :   pari_sp av = avma;
     822             :   GEN z;
     823         138 :   if (lgefint(p)==3)
     824             :   {
     825          66 :     ulong pp = p[2];
     826          66 :     long v = get_FpX_var(T);
     827          66 :     GEN Tp = ZXT_to_FlxT(T,pp), Sp = ZXXT_to_FlxXT(S, pp, v);
     828          66 :     z = FlxX_to_ZXX(FlxqXQ_halfFrobenius(ZXX_to_FlxX(a,pp,v),Sp,Tp,pp));
     829             :   }
     830             :   else
     831             :   {
     832             :     GEN xp, Xp;
     833          72 :     T = FpX_get_red(T, p);
     834          72 :     S = FpXQX_get_red(S, T, p);
     835          72 :     xp = FpX_Frobenius(T, p);
     836          72 :     Xp = FpXQXQ_pow(pol_x(get_FpXQX_var(S)), p, S, T, p);
     837          72 :     z = FpXQXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
     838             :   }
     839         138 :   return gerepilecopy(av, z);
     840             : }
     841             : 
     842             : static GEN
     843       60587 : FlxqXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T, ulong p)
     844             : {
     845       60587 :   ulong dT = get_Flx_degree(T), df = get_FlxqX_degree(f);
     846       60587 :   GEN q = powuu(p,dT);
     847       60587 :   if (expi(q) >= expu(dT)*(long)usqrt(df))
     848       60566 :     return gel(FlxqXQ_autpow(mkvec2(xp, Xp), dT, f, T, p), 2);
     849             :   else
     850          21 :     return FlxqXQ_pow(pol_x(get_FlxqX_var(f)), q, f, T, p);
     851             : }
     852             : 
     853             : GEN
     854        2117 : FlxqX_Frobenius(GEN S, GEN T, ulong p)
     855             : {
     856        2117 :   pari_sp av = avma;
     857        2117 :   GEN X  = polx_FlxX(get_FlxqX_var(S), get_Flx_var(T));
     858        2117 :   GEN xp = Flx_Frobenius(T, p);
     859        2117 :   GEN Xp = FlxqXQ_powu(X, p, S, T, p);
     860        2117 :   GEN Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
     861        2117 :   return gerepilecopy(av, Xq);
     862             : }
     863             : 
     864             : static GEN
     865         166 : FpXQXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T, GEN p)
     866             : {
     867         166 :   ulong dT = get_FpX_degree(T), df = get_FpXQX_degree(f);
     868         166 :   GEN q = powiu(p, dT);
     869         166 :   if (expi(q) >= expu(dT)*(long)usqrt(df))
     870         166 :     return gel(FpXQXQ_autpow(mkvec2(xp, Xp), dT, f, T, p), 2);
     871             :   else
     872           0 :     return FpXQXQ_pow(pol_x(get_FpXQX_var(f)), q, f, T, p);
     873             : }
     874             : 
     875             : GEN
     876         130 : FpXQX_Frobenius(GEN S, GEN T, GEN p)
     877             : {
     878         130 :   pari_sp av = avma;
     879         130 :   GEN X  = pol_x(get_FpXQX_var(S));
     880         130 :   GEN xp = FpX_Frobenius(T, p);
     881         130 :   GEN Xp = FpXQXQ_pow(X, p, S, T, p);
     882         130 :   GEN Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
     883         130 :   return gerepilecopy(av, Xq);
     884             : }
     885             : 
     886             : static GEN
     887       70770 : F2xqXQ_Frobenius(GEN xp, GEN Xp, GEN f, GEN T)
     888             : {
     889       70770 :   ulong dT = get_F2x_degree(T), df = get_F2xqX_degree(f);
     890       70770 :   if (dT >= expu(dT)*usqrt(df))
     891       70763 :     return gel(F2xqXQ_autpow(mkvec2(xp, Xp), dT, f, T), 2);
     892             :   else
     893           7 :     return F2xqXQ_pow(pol_x(get_F2xqX_var(f)), int2n(dT), f, T);
     894             : }
     895             : 
     896             : static GEN
     897        1721 : FlxqX_split_part(GEN f, GEN T, ulong p)
     898             : {
     899        1721 :   long n = degpol(f);
     900        1721 :   GEN z, Xq, X = polx_FlxX(varn(f),get_Flx_var(T));
     901        1721 :   if (n <= 1) return f;
     902        1721 :   f = FlxqX_red(f, T, p);
     903        1721 :   Xq = FlxqX_Frobenius(f, T, p);
     904        1721 :   z = FlxX_sub(Xq, X , p);
     905        1721 :   return FlxqX_gcd(z, f, T, p);
     906             : }
     907             : 
     908             : GEN
     909         854 : FpXQX_split_part(GEN f, GEN T, GEN p)
     910             : {
     911         854 :   if(lgefint(p)==3)
     912             :   {
     913         846 :     ulong pp=p[2];
     914         846 :     GEN Tp = ZXT_to_FlxT(T, pp);
     915         846 :     GEN z = FlxqX_split_part(ZXX_to_FlxX(f, pp, get_Flx_var(T)), Tp, pp);
     916         846 :     return FlxX_to_ZXX(z);
     917             :   } else
     918             :   {
     919           8 :     long n = degpol(f);
     920           8 :     GEN z, X = pol_x(varn(f));
     921           8 :     if (n <= 1) return f;
     922           8 :     f = FpXQX_red(f, T, p);
     923           8 :     z = FpXQX_Frobenius(f, T, p);
     924           8 :     z = FpXX_sub(z, X , p);
     925           8 :     return FpXQX_gcd(z, f, T, p);
     926             :   }
     927             : }
     928             : 
     929             : long
     930         826 : FpXQX_nbroots(GEN f, GEN T, GEN p)
     931             : {
     932         826 :   pari_sp av = avma;
     933         826 :   GEN z = FpXQX_split_part(f, T, p);
     934         826 :   avma = av; return degpol(z);
     935             : }
     936             : 
     937             : long
     938       82971 : FqX_nbroots(GEN f, GEN T, GEN p)
     939       82971 : { return T ? FpXQX_nbroots(f, T, p): FpX_nbroots(f, p); }
     940             : 
     941             : long
     942         875 : FlxqX_nbroots(GEN f, GEN T, ulong p)
     943             : {
     944         875 :   pari_sp av = avma;
     945         875 :   GEN z = FlxqX_split_part(f, T, p);
     946         875 :   avma = av; return degpol(z);
     947             : }
     948             : 
     949             : static GEN
     950           0 : FlxqX_Berlekamp_ker_i(GEN Xq, GEN S, GEN T, ulong p)
     951             : {
     952           0 :   long j, N = get_FlxqX_degree(S);
     953           0 :   GEN Q  = FlxqXQ_matrix_pow(Xq,N,N,S,T,p);
     954           0 :   for (j=1; j<=N; j++)
     955           0 :     gcoeff(Q,j,j) = Flx_Fl_add(gcoeff(Q,j,j), p-1, p);
     956           0 :   return FlxqM_ker(Q,T,p);
     957             : }
     958             : 
     959             : static GEN
     960           0 : FpXQX_Berlekamp_ker_i(GEN Xq, GEN S, GEN T, GEN p)
     961             : {
     962           0 :   long j,N = get_FpXQX_degree(S);
     963           0 :   GEN Q  = FpXQXQ_matrix_pow(Xq,N,N,S,T,p);
     964           0 :   for (j=1; j<=N; j++)
     965           0 :     gcoeff(Q,j,j) = Fq_sub(gcoeff(Q,j,j), gen_1, T, p);
     966           0 :   return FqM_ker(Q,T,p);
     967             : }
     968             : 
     969             : static long
     970        2117 : isabsolutepol(GEN f)
     971             : {
     972        2117 :   long i, l = lg(f);
     973        2442 :   for(i=2; i<l; i++)
     974             :   {
     975        2421 :     GEN c = gel(f,i);
     976        2421 :     if (typ(c) == t_POL && degpol(c) > 0) return 0;
     977             :   }
     978          21 :   return 1;
     979             : }
     980             : 
     981             : #define set_irred(i) { if ((i)>ir) swap(t[i],t[ir]); ir++;}
     982             : 
     983             : static long
     984           0 : FlxqX_split_Berlekamp(GEN *t, GEN xp, GEN T, ulong p)
     985             : {
     986           0 :   GEN u = *t, a,b,vker,pol;
     987           0 :   long vu = varn(u), vT = get_Flx_var(T), dT = get_Flx_degree(T);
     988             :   long d, i, ir, L, la, lb;
     989             :   GEN S, X, Xp, Xq;
     990           0 :   if (degpol(u)==1) return 1;
     991           0 :   T = Flx_get_red(T, p);
     992           0 :   S = FlxqX_get_red(u, T, p);
     993           0 :   X  = polx_FlxX(get_FlxqX_var(S),get_Flx_var(T));
     994           0 :   Xp = FlxqXQ_powu(X, p, S, T, p);
     995           0 :   Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
     996           0 :   vker = FlxqX_Berlekamp_ker_i(Xq, S, T, p);
     997           0 :   vker = Flm_to_FlxV(vker,u[1]);
     998           0 :   d = lg(vker)-1;
     999           0 :   ir = 0;
    1000             :   /* t[i] irreducible for i < ir, still to be treated for i < L */
    1001           0 :   for (L=1; L<d; )
    1002             :   {
    1003           0 :     pol= scalarpol(random_Flx(dT,vT,p),vu);
    1004           0 :     for (i=2; i<=d; i++)
    1005           0 :       pol = FlxX_add(pol, FlxqX_Flxq_mul(gel(vker,i),
    1006             :                                          random_Flx(dT,vT,p), T, p), p);
    1007           0 :     pol = FlxqX_red(pol,T,p);
    1008           0 :     for (i=ir; i<L && L<d; i++)
    1009             :     {
    1010           0 :       a = t[i]; la = degpol(a);
    1011           0 :       if (la == 1) { set_irred(i); }
    1012             :       else
    1013             :       {
    1014           0 :         pari_sp av = avma;
    1015           0 :         GEN S = FlxqX_get_red(a, T, p);
    1016           0 :         b = FlxqX_rem(pol, S, T,p);
    1017           0 :         if (degpol(b)<=0) { avma=av; continue; }
    1018           0 :         b = FlxqXQ_halfFrobenius_i(b, xp, FlxqX_rem(Xp, S, T, p), S, T, p);
    1019           0 :         if (degpol(b)<=0) { avma=av; continue; }
    1020           0 :         gel(b,2) = Flxq_sub(gel(b,2), gen_1,T,p);
    1021           0 :         b = FlxqX_gcd(a,b, T,p); lb = degpol(b);
    1022           0 :         if (lb && lb < la)
    1023             :         {
    1024           0 :           b = FlxqX_normalize(b, T,p);
    1025           0 :           t[L] = FlxqX_div(a,b,T,p);
    1026           0 :           t[i]= b; L++;
    1027             :         }
    1028           0 :         else avma = av;
    1029             :       }
    1030             :     }
    1031             :   }
    1032           0 :   return d;
    1033             : }
    1034             : 
    1035             : 
    1036             : static long
    1037           0 : FpXQX_split_Berlekamp(GEN *t, GEN T, GEN p)
    1038             : {
    1039           0 :   GEN u = *t, a, b, vker, pol;
    1040             :   GEN X, xp, Xp, Xq, S;
    1041           0 :   long vu = varn(u), vT = get_FpX_var(T), dT = get_FpX_degree(T);
    1042             :   long d, i, ir, L, la, lb;
    1043           0 :   if (degpol(u)==1) return 1;
    1044           0 :   T = FpX_get_red(T, p);
    1045           0 :   xp = FpX_Frobenius(T, p);
    1046           0 :   S = FpXQX_get_red(u, T, p);
    1047           0 :   X  = pol_x(get_FpXQX_var(S));
    1048           0 :   Xp = FpXQXQ_pow(X, p, S, T, p);
    1049           0 :   Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
    1050           0 :   vker = FpXQX_Berlekamp_ker_i(Xq, S, T, p);
    1051           0 :   vker = RgM_to_RgXV(vker,vu);
    1052           0 :   d = lg(vker)-1;
    1053           0 :   ir = 0;
    1054             :   /* t[i] irreducible for i < ir, still to be treated for i < L */
    1055           0 :   for (L=1; L<d; )
    1056             :   {
    1057           0 :     pol= scalarpol(random_FpX(dT,vT,p),vu);
    1058           0 :     for (i=2; i<=d; i++)
    1059           0 :       pol = FqX_add(pol, FqX_Fq_mul(gel(vker,i),
    1060             :                                     random_FpX(dT,vT,p), T, p), T, p);
    1061           0 :     pol = FpXQX_red(pol,T,p);
    1062           0 :     for (i=ir; i<L && L<d; i++)
    1063             :     {
    1064           0 :       a = t[i]; la = degpol(a);
    1065           0 :       if (la == 1) { set_irred(i); }
    1066             :       else
    1067             :       {
    1068           0 :         pari_sp av = avma;
    1069           0 :         GEN S = FpXQX_get_red(a, T, p);
    1070           0 :         b = FqX_rem(pol, S, T,p);
    1071           0 :         if (degpol(b)<=0) { avma=av; continue; }
    1072           0 :         b = FpXQXQ_halfFrobenius_i(b, xp, FpXQX_rem(Xp, S, T, p), S, T, p);
    1073           0 :         if (degpol(b)<=0) { avma=av; continue; }
    1074           0 :         gel(b,2) = Fq_sub(gel(b,2), gen_1,T,p);
    1075           0 :         b = FqX_gcd(a,b, T,p); lb = degpol(b);
    1076           0 :         if (lb && lb < la)
    1077             :         {
    1078           0 :           b = FpXQX_normalize(b, T,p);
    1079           0 :           t[L] = FqX_div(a,b,T,p);
    1080           0 :           t[i]= b; L++;
    1081             :         }
    1082           0 :         else avma = av;
    1083             :       }
    1084             :     }
    1085             :   }
    1086           0 :   return d;
    1087             : }
    1088             : 
    1089             : static GEN
    1090         126 : FqX_frobinv_inplace(GEN F, GEN T, GEN p)
    1091             : {
    1092         126 :   if (T)
    1093             :   {
    1094         105 :     GEN frobinv = powiu(p, get_FpX_degree(T)-1);
    1095         105 :     long i, l = lg(F);
    1096         105 :     for (i=2; i<l; i++) gel(F,i) = Fq_pow(gel(F,i), frobinv, T,p);
    1097             :   }
    1098         126 :   return F;
    1099             : }
    1100             : static GEN
    1101          63 : FqX_frob_deflate(GEN f, GEN T, GEN p)
    1102          63 : { return FqX_frobinv_inplace(RgX_deflate(f, itos(p)), T, p); }
    1103             : 
    1104             : static GEN
    1105       11158 : F2xqX_quad_roots(GEN P, GEN T)
    1106             : {
    1107       11158 :   GEN b= gel(P,3), c = gel(P,2);
    1108       11158 :   if (lgpol(b))
    1109             :   {
    1110       10199 :     GEN z, d = F2xq_div(c, F2xq_sqr(b,T),T);
    1111       10199 :     if (F2xq_trace(d,T))
    1112        1001 :       return cgetg(1, t_COL);
    1113        9198 :     z = F2xq_mul(b, F2xq_Artin_Schreier(d, T), T);
    1114        9198 :     return mkcol2(z, F2x_add(b, z));
    1115             :   }
    1116             :   else
    1117         959 :     return mkcol(F2xq_sqrt(c, T));
    1118             : }
    1119             : 
    1120             : /* Assume p>2 and x monic */
    1121             : static GEN
    1122       13120 : FlxqX_quad_roots(GEN x, GEN T, ulong p)
    1123             : {
    1124       13120 :   GEN s, D, nb, b = gel(x,3), c = gel(x,2);
    1125       13120 :   D = Flx_sub(Flxq_sqr(b,T,p), Flx_mulu(c,4,p), p);
    1126       13120 :   nb = Flx_neg(b,p);
    1127       13120 :   if (lgpol(D)==0)
    1128           7 :     return mkcol(Flx_halve(nb, p));
    1129       13113 :   s = Flxq_sqrt(D,T,p);
    1130       13113 :   if (!s) return cgetg(1, t_COL);
    1131       12679 :   s = Flx_halve(Flx_add(s,nb,p),p);
    1132       12679 :   return mkcol2(s, Flx_sub(nb,s,p));
    1133             : }
    1134             : 
    1135             : static GEN
    1136         635 : FpXQX_quad_roots(GEN x, GEN T, GEN p)
    1137             : {
    1138         635 :   GEN s, D, nb, b = gel(x,3), c = gel(x,2);
    1139         635 :   if (absequaliu(p, 2))
    1140             :   {
    1141           0 :     GEN f2 = ZXX_to_F2xX(x, get_FpX_var(T));
    1142           0 :     s = F2xqX_quad_roots(f2, ZX_to_F2x(get_FpX_mod(T)));
    1143           0 :     return F2xC_to_ZXC(s);
    1144             :   }
    1145         635 :   D = Fq_sub(Fq_sqr(b,T,p), Fq_Fp_mul(c,utoi(4),T,p), T,p);
    1146         635 :   nb = Fq_neg(b,T,p);
    1147         635 :   if (signe(D)==0)
    1148           0 :     return mkcol(Fq_to_FpXQ(Fq_halve(nb,T, p),T,p));
    1149         635 :   s = Fq_sqrt(D,T,p);
    1150         635 :   if (!s) return cgetg(1, t_COL);
    1151         621 :   s = Fq_halve(Fq_add(s,nb,T,p),T, p);
    1152         621 :   return mkcol2(Fq_to_FpXQ(s,T,p), Fq_to_FpXQ(Fq_sub(nb,s,T,p),T,p));
    1153             : }
    1154             : 
    1155             : static GEN
    1156        9128 : F2xqX_Frobenius_deflate(GEN S, GEN T)
    1157             : {
    1158        9128 :   GEN F = RgX_deflate(S, 2);
    1159        9128 :   long i, l = lg(F);
    1160       30093 :   for (i=2; i<l; i++)
    1161       20965 :     gel(F,i) = F2xq_sqrt(gel(F,i), T);
    1162        9128 :   return F;
    1163             : }
    1164             : 
    1165             : static GEN
    1166       15302 : F2xX_to_F2x(GEN x)
    1167             : {
    1168       15302 :   long l=nbits2lg(lgpol(x));
    1169       15302 :   GEN z=cgetg(l,t_VECSMALL);
    1170             :   long i,j,k;
    1171       15302 :   z[1]=x[1];
    1172       55111 :   for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
    1173             :   {
    1174       39809 :     if (j==BITS_IN_LONG)
    1175             :     {
    1176       15313 :       j=0; k++; z[k]=0;
    1177             :     }
    1178       39809 :     if (lgpol(gel(x,i)))
    1179       28175 :       z[k]|=1UL<<j;
    1180             :   }
    1181       15302 :   return F2x_renormalize(z,l);
    1182             : }
    1183             : 
    1184             : static GEN
    1185      205093 : F2xqX_easyroots(GEN f, GEN T)
    1186             : {
    1187      205093 :   if (F2xY_degreex(f) <= 0) return F2x_rootsff_i(F2xX_to_F2x(f), T);
    1188      190050 :   if (degpol(f)==1) return mkcol(constant_coeff(f));
    1189      154749 :   if (degpol(f)==2) return F2xqX_quad_roots(f,T);
    1190      143829 :   return NULL;
    1191             : }
    1192             : 
    1193             : /* Adapted from Shoup NTL */
    1194             : static GEN
    1195       71442 : F2xqX_factor_squarefree(GEN f, GEN T)
    1196             : {
    1197       71442 :   pari_sp av = avma;
    1198             :   GEN r, t, v, tv;
    1199       71442 :   long q, n = degpol(f);
    1200       71442 :   GEN u = const_vec(n+1, pol1_F2xX(varn(f), get_F2x_var(T)));
    1201       80570 :   for(q = 1;;q *= 2)
    1202             :   {
    1203       80570 :     r = F2xqX_gcd(f, F2xX_deriv(f), T);
    1204       80570 :     if (degpol(r) == 0)
    1205             :     {
    1206       69811 :       gel(u, q) = F2xqX_normalize(f, T);
    1207       69811 :       break;
    1208             :     }
    1209       10759 :     t = F2xqX_div(f, r, T);
    1210       10759 :     if (degpol(t) > 0)
    1211             :     {
    1212             :       long j;
    1213       13797 :       for(j = 1;;j++)
    1214             :       {
    1215       13797 :         v = F2xqX_gcd(r, t, T);
    1216       13797 :         tv = F2xqX_div(t, v, T);
    1217       13797 :         if (degpol(tv) > 0)
    1218       11571 :           gel(u, j*q) = F2xqX_normalize(tv, T);
    1219       13797 :         if (degpol(v) <= 0) break;
    1220        3850 :         r = F2xqX_div(r, v, T);
    1221        3850 :         t = v;
    1222        3850 :       }
    1223        9947 :       if (degpol(r) == 0) break;
    1224             :     }
    1225        9128 :     f = F2xqX_Frobenius_deflate(r, T);
    1226        9128 :   }
    1227       71442 :   return gerepilecopy(av, u);
    1228             : }
    1229             : 
    1230             : static void
    1231       50190 : F2xqX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, GEN V, long idx)
    1232             : {
    1233             :   pari_sp btop;
    1234       50190 :   long n = degpol(Sp);
    1235             :   GEN S, f, ff;
    1236       50190 :   long dT = get_F2x_degree(T);
    1237       50190 :   GEN R = F2xqX_easyroots(Sp, T);
    1238       50190 :   if (R)
    1239             :   {
    1240       48062 :     long i, l = lg(R)-1;
    1241      106645 :     for (i=0; i<l; i++)
    1242       58583 :       gel(V, idx+i) = gel(R,1+i);
    1243       98252 :     return;
    1244             :   }
    1245        2128 :   S = F2xqX_get_red(Sp, T);
    1246        2128 :   Xp = F2xqX_rem(Xp, S, T);
    1247        2128 :   btop = avma;
    1248             :   while (1)
    1249             :   {
    1250        2688 :     GEN a = random_F2xqX(degpol(Sp), varn(Sp), T);
    1251        2688 :     GEN R = gel(F2xqXQ_auttrace(mkvec3(xp, Xp, a), dT, S, T), 3);
    1252        2688 :     f = F2xqX_gcd(R, Sp, T);
    1253        2688 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1254         560 :     avma = btop;
    1255         560 :   }
    1256        2128 :   f = gerepileupto(btop, F2xqX_normalize(f, T));
    1257        2128 :   ff = F2xqX_div(Sp, f, T);
    1258        2128 :   F2xqX_roots_edf(f, xp, Xp, T, V, idx);
    1259        2128 :   F2xqX_roots_edf(ff,xp, Xp, T, V, idx+degpol(f));
    1260             : }
    1261             : 
    1262             : static GEN
    1263       81109 : F2xqX_roots_ddf(GEN f, GEN xp, GEN T)
    1264             : {
    1265             :   GEN X, Xp, Xq, g, V;
    1266             :   long n;
    1267       81109 :   GEN R = F2xqX_easyroots(f, T);
    1268       81109 :   if (R) return R;
    1269       70497 :   X  = pol_x(varn(f));
    1270       70497 :   Xp = F2xqXQ_sqr(X, f, T);
    1271       70497 :   Xq = F2xqXQ_Frobenius(xp, Xp, f, T);
    1272       70497 :   g = F2xqX_gcd(F2xX_add(Xq, X), f, T);
    1273       70497 :   n = degpol(g);
    1274       70497 :   if (n==0) return cgetg(1, t_COL);
    1275       45934 :   g = F2xqX_normalize(g, T);
    1276       45934 :   V = cgetg(n+1,t_COL);
    1277       45934 :   F2xqX_roots_edf(g, xp, Xp, T, V, 1);
    1278       45934 :   return V;
    1279             : }
    1280             : static GEN
    1281       73801 : F2xqX_roots_i(GEN S, GEN T)
    1282             : {
    1283             :   GEN M;
    1284       73801 :   S = F2xqX_red(S, T);
    1285       73801 :   if (!signe(S)) pari_err_ROOTS0("F2xqX_roots");
    1286       73801 :   if (degpol(S)==0) return cgetg(1, t_COL);
    1287       73794 :   S = F2xqX_normalize(S, T);
    1288       73794 :   M = F2xqX_easyroots(S, T);
    1289       73794 :   if (!M)
    1290             :   {
    1291       71204 :     GEN xp = F2x_Frobenius(T);
    1292       71204 :     GEN F, V = F2xqX_factor_squarefree(S, T);
    1293       71204 :     long i, j, l = lg(V);
    1294       71204 :     F = cgetg(l, t_VEC);
    1295      570395 :     for (i=1, j=1; i < l; i++)
    1296      499191 :       if (degpol(gel(V,i)))
    1297       81109 :         gel(F, j++) = F2xqX_roots_ddf(gel(V,i), xp, T);
    1298       71204 :     setlg(F,j); M = shallowconcat1(F);
    1299             :   }
    1300       73794 :   gen_sort_inplace(M, (void*) &cmp_Flx, &cmp_nodata, NULL);
    1301       73794 :   return M;
    1302             : }
    1303             : 
    1304             : static GEN
    1305      174733 : FlxqX_easyroots(GEN f, GEN T, ulong p)
    1306             : {
    1307      174733 :   if (FlxY_degreex(f) <= 0) return Flx_rootsff_i(FlxX_to_Flx(f), T, p);
    1308      165927 :   if (degpol(f)==1) return mkcol(Flx_neg(constant_coeff(f), p));
    1309      138057 :   if (degpol(f)==2) return FlxqX_quad_roots(f,T,p);
    1310      125118 :   return NULL;
    1311             : }
    1312             : 
    1313             : static GEN
    1314         469 : FlxqX_invFrobenius(GEN xp, GEN T, ulong p)
    1315             : {
    1316         469 :   return Flxq_autpow(xp, get_Flx_degree(T)-1, T, p);
    1317             : }
    1318             : 
    1319             : static GEN
    1320         469 : FlxqX_Frobenius_deflate(GEN S, GEN ixp, GEN T, ulong p)
    1321             : {
    1322         469 :   GEN F = RgX_deflate(S, p);
    1323         469 :   long i, l = lg(F);
    1324         469 :   if (typ(ixp)==t_INT)
    1325           0 :     for (i=2; i<l; i++)
    1326           0 :       gel(F,i) = Flxq_pow(gel(F,i), ixp, T, p);
    1327             :   else
    1328             :   {
    1329         469 :     long n = brent_kung_optpow(get_Flx_degree(T)-1, l-2, 1);
    1330         469 :     GEN V = Flxq_powers(ixp, n, T, p);
    1331        1463 :     for (i=2; i<l; i++)
    1332         994 :       gel(F,i) = Flx_FlxqV_eval(gel(F,i), V, T, p);
    1333             :   }
    1334         469 :   return F;
    1335             : }
    1336             : 
    1337             : /* Adapted from Shoup NTL */
    1338             : static GEN
    1339       58841 : FlxqX_factor_squarefree(GEN f, GEN xp, GEN T, ulong p)
    1340             : {
    1341       58841 :   pari_sp av = avma;
    1342             :   GEN r, t, v, tv;
    1343       58841 :   long q, n = degpol(f);
    1344       58841 :   GEN u = const_vec(n+1, pol1_FlxX(varn(f),get_Flx_var(T)));
    1345       58841 :   GEN ixp = NULL;
    1346       59310 :   for(q = 1;;q *= p)
    1347             :   {
    1348       59310 :     r = FlxqX_gcd(f, FlxX_deriv(f, p), T, p);
    1349       59310 :     if (degpol(r) == 0)
    1350             :     {
    1351       54753 :       gel(u, q) = FlxqX_normalize(f, T, p);
    1352       54753 :       break;
    1353             :     }
    1354        4557 :     t = FlxqX_div(f, r, T, p);
    1355        4557 :     if (degpol(t) > 0)
    1356             :     {
    1357             :       long j;
    1358        8687 :       for(j = 1;;j++)
    1359             :       {
    1360        8687 :         v = FlxqX_gcd(r, t, T, p);
    1361        8687 :         tv = FlxqX_div(t, v, T, p);
    1362        8687 :         if (degpol(tv) > 0)
    1363        8463 :           gel(u, j*q) = FlxqX_normalize(tv, T, p);
    1364        8687 :         if (degpol(v) <= 0) break;
    1365        4214 :         r = FlxqX_div(r, v, T, p);
    1366        4214 :         t = v;
    1367        4214 :       }
    1368        4473 :       if (degpol(r) == 0) break;
    1369             :     }
    1370         469 :     if (!ixp) ixp = FlxqX_invFrobenius(xp, T, p);
    1371         469 :     f = FlxqX_Frobenius_deflate(r, ixp, T, p);
    1372         469 :   }
    1373       58841 :   return gerepilecopy(av, u);
    1374             : }
    1375             : 
    1376             : static GEN
    1377        8426 : FlxqX_roots_split(GEN Sp, GEN xp, GEN Xp, GEN S, GEN T, ulong p)
    1378             : {
    1379        8426 :   pari_sp btop = avma;
    1380        8426 :   long n = degpol(Sp);
    1381             :   GEN f;
    1382        8426 :   long vT = get_Flx_var(T), dT = get_Flx_degree(T);
    1383             :   pari_timer ti;
    1384        8426 :   if (DEBUGLEVEL >= 7) timer_start(&ti);
    1385             :   while (1)
    1386             :   {
    1387       10238 :     GEN a = deg1pol(pol1_Flx(vT), random_Flx(dT, vT, p), varn(Sp));
    1388       10238 :     GEN R = FlxqXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
    1389       10238 :     if (DEBUGLEVEL >= 7) timer_printf(&ti, "FlxqXQ_halfFrobenius");
    1390       10238 :     f = FlxqX_gcd(FlxX_Flx_sub(R, pol1_Flx(vT), p), Sp, T, p);
    1391       10238 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1392        1812 :     avma = btop;
    1393        1812 :   }
    1394        8426 :   return gerepileupto(btop, FlxqX_normalize(f, T, p));
    1395             : }
    1396             : 
    1397             : static void
    1398       50799 : FlxqX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, ulong p, GEN V, long idx)
    1399             : {
    1400             :   GEN S, f, ff;
    1401       50799 :   GEN R = FlxqX_easyroots(Sp, T, p);
    1402       50799 :   if (R)
    1403             :   {
    1404       42602 :     long i, l = lg(R)-1;
    1405       98252 :     for (i=0; i<l; i++)
    1406       55650 :       gel(V, idx+i) = gel(R,1+i);
    1407       93401 :     return;
    1408             :   }
    1409        8197 :   S  = FlxqX_get_red(Sp, T, p);
    1410        8197 :   Xp = FlxqX_rem(Xp, S, T, p);
    1411        8197 :   f  = FlxqX_roots_split(Sp, xp, Xp, S, T, p);
    1412        8197 :   ff = FlxqX_div(Sp, f, T, p);
    1413        8197 :   FlxqX_roots_edf(f, xp, Xp, T, p, V, idx);
    1414        8197 :   FlxqX_roots_edf(ff,xp, Xp, T, p, V, idx+degpol(f));
    1415             : }
    1416             : 
    1417             : static GEN
    1418       63007 : FlxqX_roots_ddf(GEN f, GEN xp, GEN T, ulong p)
    1419             : {
    1420             :   GEN X, Xp, Xq, g, V;
    1421             :   long n;
    1422       63007 :   GEN R = FlxqX_easyroots(f, T, p);
    1423       63007 :   if (R) return R;
    1424       58261 :   X  = pol_x(varn(f));
    1425       58261 :   Xp = FlxqXQ_powu(X, p, f, T, p);
    1426       58261 :   Xq = FlxqXQ_Frobenius(xp, Xp, f, T, p);
    1427       58261 :   g = FlxqX_gcd(FlxX_sub(Xq, X, p), f, T, p);
    1428       58261 :   n = degpol(g);
    1429       58261 :   if (n==0) return cgetg(1, t_COL);
    1430       34405 :   g = FlxqX_normalize(g, T, p);
    1431       34405 :   V = cgetg(n+1,t_COL);
    1432       34405 :   FlxqX_roots_edf(g, xp, Xp, T, p, V, 1);
    1433       34405 :   return V;
    1434             : }
    1435             : 
    1436             : /* do not handle p==2 */
    1437             : static GEN
    1438       60934 : FlxqX_roots_i(GEN S, GEN T, ulong p)
    1439             : {
    1440             :   GEN M;
    1441       60934 :   S = FlxqX_red(S, T, p);
    1442       60934 :   if (!signe(S)) pari_err_ROOTS0("FlxqX_roots");
    1443       60934 :   if (degpol(S)==0) return cgetg(1, t_COL);
    1444       60927 :   S = FlxqX_normalize(S, T, p);
    1445       60927 :   M = FlxqX_easyroots(S, T, p);
    1446       60927 :   if (!M)
    1447             :   {
    1448       58660 :     GEN xp = Flx_Frobenius(T, p);
    1449       58660 :     GEN F, V = FlxqX_factor_squarefree(S, xp, T, p);
    1450       58660 :     long i, j, l = lg(V);
    1451       58660 :     F = cgetg(l, t_VEC);
    1452      436681 :     for (i=1, j=1; i < l; i++)
    1453      378021 :       if (degpol(gel(V,i)))
    1454       63007 :         gel(F, j++) = FlxqX_roots_ddf(gel(V,i), xp, T, p);
    1455       58660 :     setlg(F,j); M = shallowconcat1(F);
    1456             :   }
    1457       60927 :   gen_sort_inplace(M, (void*) &cmp_Flx, &cmp_nodata, NULL);
    1458       60927 :   return M;
    1459             : }
    1460             : 
    1461             : static GEN
    1462        2024 : FpXQX_easyroots(GEN f, GEN T, GEN p)
    1463             : {
    1464        2024 :   if (isabsolutepol(f)) return FpX_rootsff_i(simplify_shallow(f), T, p);
    1465        2024 :   if (degpol(f)==1) return mkcol(Fq_to_FpXQ(Fq_neg(constant_coeff(f),T,p),T,p));
    1466        1551 :   if (degpol(f)==2) return FpXQX_quad_roots(f,T,p);
    1467         959 :   return NULL;
    1468             : }
    1469             : 
    1470             : /* Adapted from Shoup NTL */
    1471             : static GEN
    1472          36 : FpXQX_factor_Yun(GEN f, GEN T, GEN p)
    1473             : {
    1474          36 :   pari_sp av = avma;
    1475             :   GEN r, t, v, tv;
    1476          36 :   long j, n = degpol(f);
    1477          36 :   GEN u = const_vec(n+1, pol_1(varn(f)));
    1478          36 :   r = FpXQX_gcd(f, FpXX_deriv(f, p), T, p);
    1479          36 :   t = FpXQX_div(f, r, T, p);
    1480          36 :   for (j = 1;;j++)
    1481             :   {
    1482          36 :     v = FpXQX_gcd(r, t, T, p);
    1483          36 :     tv = FpXQX_div(t, v, T, p);
    1484          36 :     if (degpol(tv) > 0)
    1485          36 :       gel(u, j) = FpXQX_normalize(tv, T, p);
    1486          36 :     if (degpol(v) <= 0) break;
    1487           0 :     r = FpXQX_div(r, v, T, p);
    1488           0 :     t = v;
    1489           0 :   }
    1490          36 :   setlg(u, j+1); return gerepilecopy(av, u);
    1491             : }
    1492             : 
    1493             : static GEN
    1494         954 : FpXQX_roots_split(GEN Sp, GEN xp, GEN Xp, GEN S, GEN T, GEN p)
    1495             : {
    1496         954 :   pari_sp btop = avma;
    1497         954 :   long n = degpol(Sp);
    1498             :   GEN f;
    1499         954 :   long vT = get_FpX_var(T), dT = get_FpX_degree(T);
    1500             :   pari_timer ti;
    1501         954 :   if (DEBUGLEVEL >= 7) timer_start(&ti);
    1502             :   while (1)
    1503             :   {
    1504        1041 :     GEN a = deg1pol(pol_1(vT), random_FpX(dT, vT, p), varn(Sp));
    1505        1041 :     GEN R = FpXQXQ_halfFrobenius_i(a, xp, Xp, S, T, p);
    1506        1041 :     if (DEBUGLEVEL >= 7) timer_printf(&ti, "FpXQXQ_halfFrobenius");
    1507        1041 :     f = FpXQX_gcd(FqX_Fq_sub(R, pol_1(vT), T, p), Sp, T, p);
    1508        1041 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1509          87 :     avma = btop;
    1510          87 :   }
    1511         954 :   return gerepileupto(btop, FpXQX_normalize(f, T, p));
    1512             : }
    1513             : 
    1514             : static void
    1515        1876 : FpXQX_roots_edf(GEN Sp, GEN xp, GEN Xp, GEN T, GEN p, GEN V, long idx)
    1516             : {
    1517             :   GEN S, f, ff;
    1518        1876 :   GEN R = FpXQX_easyroots(Sp, T, p);
    1519        1876 :   if (R)
    1520             :   {
    1521         945 :     long i, l = lg(R)-1;
    1522        2373 :     for (i=0; i<l; i++)
    1523        1428 :       gel(V, idx+i) = gel(R,1+i);
    1524        2821 :     return;
    1525             :   }
    1526         931 :   S  = FpXQX_get_red(Sp, T, p);
    1527         931 :   Xp = FpXQX_rem(Xp, S, T, p);
    1528         931 :   f  = FpXQX_roots_split(Sp, xp, Xp, S, T, p);
    1529         931 :   ff = FpXQX_div(Sp, f, T, p);
    1530         931 :   FpXQX_roots_edf(f, xp, Xp, T, p, V, idx);
    1531         931 :   FpXQX_roots_edf(ff,xp, Xp, T, p, V, idx+degpol(f));
    1532             : }
    1533             : 
    1534             : static GEN
    1535          14 : FpXQX_roots_ddf(GEN f, GEN xp, GEN T, GEN p)
    1536             : {
    1537             :   GEN X, Xp, Xq, g, V;
    1538             :   long n;
    1539          14 :   GEN R = FpXQX_easyroots(f, T, p);
    1540          14 :   if (R) return R;
    1541          14 :   X  = pol_x(varn(f));
    1542          14 :   Xp = FpXQXQ_pow(X, p, f, T, p);
    1543          14 :   Xq = FpXQXQ_Frobenius(xp, Xp, f, T, p);
    1544          14 :   g = FpXQX_gcd(FpXX_sub(Xq, X, p), f, T, p);
    1545          14 :   n = degpol(g);
    1546          14 :   if (n==0) return cgetg(1, t_COL);
    1547          14 :   g = FpXQX_normalize(g, T, p);
    1548          14 :   V = cgetg(n+1,t_COL);
    1549          14 :   FpXQX_roots_edf(g, xp, Xp, T, p, V, 1);
    1550          14 :   return V;
    1551             : }
    1552             : 
    1553             : /* do not handle small p */
    1554             : static GEN
    1555       17153 : FpXQX_roots_i(GEN S, GEN T, GEN p)
    1556             : {
    1557             :   GEN F, M;
    1558       17153 :   if (lgefint(p)==3)
    1559             :   {
    1560       17019 :     ulong pp = p[2];
    1561       17019 :     if (pp == 2)
    1562             :     {
    1563        2331 :       GEN V = F2xqX_roots_i(ZXX_to_F2xX(S,get_FpX_var(T)), ZX_to_F2x(get_FpX_mod(T)));
    1564        2331 :       return F2xC_to_ZXC(V);
    1565             :     }
    1566             :     else
    1567             :     {
    1568       14688 :       GEN V = FlxqX_roots_i(ZXX_to_FlxX(S,pp,get_FpX_var(T)), ZXT_to_FlxT(T,pp), pp);
    1569       14688 :       return FlxC_to_ZXC(V);
    1570             :     }
    1571             :   }
    1572         134 :   S = FpXQX_red(S, T, p);
    1573         134 :   if (!signe(S)) pari_err_ROOTS0("FpXQX_roots");
    1574         134 :   if (degpol(S)==0) return cgetg(1, t_COL);
    1575         134 :   S = FpXQX_normalize(S, T, p);
    1576         134 :   M = FpXQX_easyroots(S, T, p);
    1577         134 :   if (!M)
    1578             :   {
    1579          14 :     GEN xp = FpX_Frobenius(T, p);
    1580          14 :     GEN V = FpXQX_factor_Yun(S, T, p);
    1581          14 :     long i, j, l = lg(V);
    1582          14 :     F = cgetg(l, t_VEC);
    1583          28 :     for (i=1, j=1; i < l; i++)
    1584          14 :       if (degpol(gel(V,i)))
    1585          14 :         gel(F, j++) = FpXQX_roots_ddf(gel(V,i), xp, T, p);
    1586          14 :     setlg(F,j); M = shallowconcat1(F);
    1587             :   }
    1588         134 :   gen_sort_inplace(M, (void*) &cmp_RgX, &cmp_nodata, NULL);
    1589         134 :   return M;
    1590             : }
    1591             : 
    1592             : GEN
    1593       71470 : F2xqX_roots(GEN x, GEN T)
    1594             : {
    1595       71470 :   pari_sp av = avma;
    1596       71470 :   return gerepilecopy(av, F2xqX_roots_i(x, T));
    1597             : }
    1598             : 
    1599             : GEN
    1600       46246 : FlxqX_roots(GEN x, GEN T, ulong p)
    1601             : {
    1602       46246 :   pari_sp av = avma;
    1603       46246 :   if (p==2)
    1604             :   {
    1605           0 :     GEN V = F2xqX_roots_i(FlxX_to_F2xX(x), Flx_to_F2x(get_Flx_mod(T)));
    1606           0 :     return gerepileupto(av, F2xC_to_FlxC(V));
    1607             :   }
    1608       46246 :   return gerepilecopy(av, FlxqX_roots_i(x, T, p));
    1609             : }
    1610             : 
    1611             : GEN
    1612       17125 : FpXQX_roots(GEN x, GEN T, GEN p)
    1613             : {
    1614       17125 :   pari_sp av = avma;
    1615       17125 :   return gerepilecopy(av, FpXQX_roots_i(x, T, p));
    1616             : }
    1617             : 
    1618             : static GEN
    1619         441 : FE_concat(GEN F, GEN E, long l)
    1620             : {
    1621         441 :   setlg(E,l); E = shallowconcat1(E);
    1622         441 :   setlg(F,l); F = shallowconcat1(F); return mkvec2(F,E);
    1623             : }
    1624             : 
    1625             : static GEN
    1626         238 : F2xqX_factor_2(GEN f, GEN T)
    1627             : {
    1628         238 :   long v = varn(f), vT = get_F2x_var(T);
    1629         238 :   GEN r = F2xqX_quad_roots(f, T);
    1630         238 :   switch(lg(r)-1)
    1631             :   {
    1632             :   case 0:
    1633          14 :     return mkvec2(mkcolcopy(f), mkvecsmall(1));
    1634             :   case 1:
    1635         217 :     return mkvec2(mkcol(deg1pol_shallow(pol1_F2x(vT), gel(r,1), v)), mkvecsmall(2));
    1636             :   default: /* 2 */
    1637             :     {
    1638           7 :       GEN f1 = deg1pol_shallow(pol1_F2x(vT), gel(r,1), v);
    1639           7 :       GEN f2 = deg1pol_shallow(pol1_F2x(vT), gel(r,2), v);
    1640           7 :       GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
    1641           7 :       sort_factor_pol(mkvec2(t, E), cmp_Flx);
    1642           7 :       return mkvec2(t, E);
    1643             :     }
    1644             :   }
    1645             : }
    1646             : 
    1647             : static GEN
    1648         181 : FlxqX_factor_2(GEN f, GEN T, ulong p)
    1649             : {
    1650         181 :   long v = varn(f), vT = get_Flx_var(T);
    1651         181 :   GEN r = FlxqX_quad_roots(f, T, p);
    1652         181 :   switch(lg(r)-1)
    1653             :   {
    1654             :   case 0:
    1655          35 :     return mkvec2(mkcolcopy(f), mkvecsmall(1));
    1656             :   case 1:
    1657          14 :     return mkvec2(mkcol(deg1pol_shallow(pol1_Flx(vT),
    1658           7 :                         Flx_neg(gel(r,1), p), v)), mkvecsmall(2));
    1659             :   default: /* 2 */
    1660             :     {
    1661         139 :       GEN f1 = deg1pol_shallow(pol1_Flx(vT), Flx_neg(gel(r,1), p), v);
    1662         139 :       GEN f2 = deg1pol_shallow(pol1_Flx(vT), Flx_neg(gel(r,2), p), v);
    1663         139 :       GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
    1664         139 :       sort_factor_pol(mkvec2(t, E), cmp_Flx);
    1665         139 :       return mkvec2(t, E);
    1666             :     }
    1667             :   }
    1668             : }
    1669             : 
    1670             : static GEN
    1671          43 : FpXQX_factor_2(GEN f, GEN T, GEN p)
    1672             : {
    1673          43 :   long v = varn(f);
    1674          43 :   GEN r = FpXQX_quad_roots(f, T, p);
    1675          43 :   switch(lg(r)-1)
    1676             :   {
    1677             :   case 0:
    1678          14 :     return mkvec2(mkcolcopy(f), mkvecsmall(1));
    1679             :   case 1:
    1680           0 :     return mkvec2(mkcol(deg1pol_shallow(gen_1, Fq_neg(gel(r,1), T, p), v)),
    1681             :         mkvecsmall(2));
    1682             :   default: /* 2 */
    1683             :     {
    1684          29 :       GEN f1 = deg1pol_shallow(gen_1, Fq_neg(gel(r,1), T, p), v);
    1685          29 :       GEN f2 = deg1pol_shallow(gen_1, Fq_neg(gel(r,2), T, p), v);
    1686          29 :       GEN t = mkcol2(f1, f2), E = mkvecsmall2(1, 1);
    1687          29 :       sort_factor_pol(mkvec2(t, E), cmp_RgX);
    1688          29 :       return mkvec2(t, E);
    1689             :     }
    1690             :   }
    1691             : }
    1692             : 
    1693             : static GEN
    1694         273 : F2xqX_ddf(GEN S, GEN Xq, GEN T)
    1695             : {
    1696         273 :   pari_sp av = avma;
    1697             :   GEN b, g, h, F, f, Sr, xq;
    1698             :   long i, j, n, v, vT, dT, bo, ro;
    1699             :   long B, l, m;
    1700             :   pari_timer ti;
    1701         273 :   n = get_F2xqX_degree(S); v = get_F2xqX_var(S);
    1702         273 :   vT = get_F2x_var(T); dT = get_F2x_degree(T);
    1703         273 :   if (n == 0) return cgetg(1, t_VEC);
    1704         273 :   if (n == 1) return mkvec(get_F2xqX_mod(S));
    1705          84 :   B = n/2;
    1706          84 :   l = usqrt(B);
    1707          84 :   m = (B+l-1)/l;
    1708          84 :   S = F2xqX_get_red(S, T);
    1709          84 :   b = cgetg(l+2, t_VEC);
    1710          84 :   gel(b, 1) = polx_F2xX(v, vT);
    1711          84 :   gel(b, 2) = Xq;
    1712          84 :   bo = brent_kung_optpow(n, l-1, 1);
    1713          84 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    1714          84 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    1715          84 :   if (dT <= ro)
    1716           0 :     for (i = 3; i <= l+1; i++)
    1717           0 :       gel(b, i) = F2xqXQ_pow(gel(b, i-1), int2n(dT), S, T);
    1718             :   else
    1719             :   {
    1720          84 :     xq = F2xqXQ_powers(gel(b, 2), bo, S, T);
    1721          84 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: xq baby");
    1722          84 :     for (i = 3; i <= l+1; i++)
    1723           0 :       gel(b, i) = F2xqX_F2xqXQV_eval(gel(b, i-1), xq, S, T);
    1724             :   }
    1725          84 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: baby");
    1726          84 :   xq = F2xqXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T);
    1727          84 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: xq giant");
    1728          84 :   g = cgetg(m+1, t_VEC);
    1729          84 :   gel(g, 1) = gel(xq, 2);
    1730         105 :   for(i = 2; i <= m; i++)
    1731          21 :     gel(g, i) = F2xqX_F2xqXQV_eval(gel(g, i-1), xq, S, T);
    1732          84 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: giant");
    1733          84 :   h = cgetg(m+1, t_VEC);
    1734         189 :   for (j = 1; j <= m; j++)
    1735             :   {
    1736         105 :     pari_sp av = avma;
    1737         105 :     GEN gj = gel(g, j);
    1738         105 :     GEN e = F2xX_add(gj, gel(b, 1));
    1739         105 :     for (i = 2; i <= l; i++)
    1740           0 :       e = F2xqXQ_mul(e, F2xX_add(gj, gel(b, i)), S, T);
    1741         105 :     gel(h, j) = gerepileupto(av, e);
    1742             :   }
    1743          84 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: diff");
    1744          84 :   Sr = get_F2xqX_mod(S);
    1745          84 :   F = cgetg(m+1, t_VEC);
    1746         189 :   for (j = 1; j <= m; j++)
    1747             :   {
    1748         105 :     gel(F, j) = F2xqX_gcd(Sr, gel(h, j), T);
    1749         105 :     Sr = F2xqX_div(Sr, gel(F,j), T);
    1750             :   }
    1751          84 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: F");
    1752          84 :   f = const_vec(n, pol1_F2xX(v, vT));
    1753         189 :   for (j = 1; j <= m; j++)
    1754             :   {
    1755         105 :     GEN e = gel(F, j);
    1756         105 :     for (i=l-1; i >= 0; i--)
    1757             :     {
    1758         105 :       GEN u = F2xqX_gcd(e, F2xX_add(gel(g, j), gel(b, i+1)), T);
    1759         105 :       if (degpol(u))
    1760             :       {
    1761          77 :         gel(f, l*j-i) = u;
    1762          77 :         e = F2xqX_div(e, u, T);
    1763             :       }
    1764         105 :       if (!degpol(e)) break;
    1765             :     }
    1766             :   }
    1767          84 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"F2xqX_ddf: f");
    1768          84 :   if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
    1769          84 :   return gerepilecopy(av, f);
    1770             : }
    1771             : 
    1772             : static void
    1773         168 : F2xqX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Sq, long d, GEN T, GEN V, long idx)
    1774             : {
    1775         168 :   long v = varn(Sp), n = degpol(Sp), r = n/d;
    1776             :   GEN S, f, ff;
    1777         168 :   long dT = get_F2x_degree(T);
    1778         336 :   if (r==1) { gel(V, idx) = Sp; return; }
    1779          63 :   S = F2xqX_get_red(Sp, T);
    1780          63 :   Xp = F2xqX_rem(Xp, S, T);
    1781          63 :   Sq = F2xqXQV_red(Sq, S, T);
    1782             :   while (1)
    1783             :   {
    1784         119 :     pari_sp btop = avma;
    1785             :     long l;
    1786         119 :     GEN w0 = random_F2xqX(n, v, T), g = w0;
    1787         147 :     for (l=1; l<d; l++) /* sum_{0<i<d} w^(q^i), result in (F_q)^r */
    1788          28 :       g = F2xX_add(w0, F2xqX_F2xqXQV_eval(g, Sq, S, T));
    1789         119 :     w0 = g;
    1790         672 :     for (l=1; l<dT; l++) /* sum_{0<i<k} w^(2^i), result in (F_2)^r */
    1791         553 :       g = F2xX_add(w0, F2xqXQ_sqr(g,S,T));
    1792         119 :     f = F2xqX_gcd(g, Sp, T);
    1793         119 :     if (degpol(f) > 0 && degpol(f) < n) break;
    1794          56 :     avma = btop;
    1795          56 :   }
    1796          63 :   f = F2xqX_normalize(f, T);
    1797          63 :   ff = F2xqX_div(Sp, f , T);
    1798          63 :   F2xqX_edf_simple(f, xp, Xp, Sq, d, T, V, idx);
    1799          63 :   F2xqX_edf_simple(ff, xp, Xp, Sq, d, T, V, idx+degpol(f)/d);
    1800             : }
    1801             : 
    1802             : static GEN
    1803         273 : F2xqX_factor_Shoup(GEN S, GEN xp, GEN T)
    1804             : {
    1805         273 :   long i, n, s = 0;
    1806             :   GEN X, Xp, Xq, Sq, D, V;
    1807         273 :   long vT = get_F2x_var(T);
    1808             :   pari_timer ti;
    1809         273 :   n = get_F2xqX_degree(S);
    1810         273 :   S = F2xqX_get_red(S, T);
    1811         273 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    1812         273 :   X  = polx_F2xX(get_F2xqX_var(S), vT);
    1813         273 :   Xp = F2xqXQ_sqr(X, S, T);
    1814         273 :   Xq = F2xqXQ_Frobenius(xp, Xp, S, T);
    1815         273 :   Sq = F2xqXQ_powers(Xq, n-1, S, T);
    1816         273 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_Frobenius");
    1817         273 :   D = F2xqX_ddf(S, Xq, T);
    1818         273 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_ddf");
    1819         735 :   for (i = 1; i <= n; i++)
    1820         462 :     s += degpol(gel(D,i))/i;
    1821         273 :   V = cgetg(s+1, t_COL);
    1822         735 :   for (i = 1, s = 1; i <= n; i++)
    1823             :   {
    1824         462 :     GEN Di = gel(D,i);
    1825         462 :     long ni = degpol(Di), ri = ni/i;
    1826         462 :     if (ni == 0) continue;
    1827         308 :     Di = F2xqX_normalize(Di, T);
    1828         308 :     if (ni == i) { gel(V, s++) = Di; continue; }
    1829          42 :     F2xqX_edf_simple(Di, xp, Xp, Sq, i, T, V, s);
    1830          42 :     if (DEBUGLEVEL>=6) timer_printf(&ti,"F2xqX_edf(%ld)",i);
    1831          42 :     s += ri;
    1832             :   }
    1833         273 :   return V;
    1834             : }
    1835             : 
    1836             : static GEN
    1837         784 : F2xqX_factor_Cantor(GEN f, GEN T)
    1838             : {
    1839             :   GEN xp, E, F, V;
    1840             :   long i, j, l;
    1841         784 :   T = F2x_get_red(T);
    1842         784 :   f = F2xqX_normalize(f, T);
    1843         784 :   switch(degpol(f))
    1844             :   {
    1845          14 :     case -1: retmkmat2(mkcol(f), mkvecsmall(1));
    1846          14 :     case 0: return trivial_fact();
    1847          21 :     case 1: retmkmat2(mkcol(f), mkvecsmall(1));
    1848         238 :     case 2: return F2xqX_factor_2(f, T);
    1849             :   }
    1850         497 :   if (F2xY_degreex(f) <= 0) return F2x_factorff_i(F2xX_to_F2x(f), T);
    1851         238 :   xp = F2x_Frobenius(T);
    1852         238 :   V = F2xqX_factor_squarefree(f, T);
    1853         238 :   l = lg(V);
    1854         238 :   F = cgetg(l, t_VEC);
    1855         238 :   E = cgetg(l, t_VEC);
    1856        1393 :   for (i=1, j=1; i < l; i++)
    1857        1155 :     if (degpol(gel(V,i)))
    1858             :     {
    1859         273 :       GEN Fj = F2xqX_factor_Shoup(gel(V,i), xp, T);
    1860         273 :       gel(F, j) = Fj;
    1861         273 :       gel(E, j) = const_vecsmall(lg(Fj)-1, i);
    1862         273 :       j++;
    1863             :     }
    1864         238 :   return sort_factor_pol(FE_concat(F,E,j), cmp_Flx);
    1865             : }
    1866             : 
    1867             : static GEN
    1868           0 : FlxqX_Berlekamp_i(GEN f, GEN T, ulong p)
    1869             : {
    1870           0 :   long lfact, d = degpol(f), j, k, lV;
    1871             :   GEN E, t, V, xp;
    1872           0 :   switch(d)
    1873             :   {
    1874           0 :     case -1: retmkmat2(mkcolcopy(f), mkvecsmall(1));
    1875           0 :     case 0: return trivial_fact();
    1876             :   }
    1877           0 :   T = Flx_get_red(T, p);
    1878           0 :   f = FlxqX_normalize(f, T, p);
    1879           0 :   if (FlxY_degreex(f) <= 0) return Flx_factorff_i(FlxX_to_Flx(f), T, p);
    1880           0 :   if (degpol(f)==2) return FlxqX_factor_2(f, T, p);
    1881           0 :   xp = Flx_Frobenius(T, p);
    1882           0 :   V = FlxqX_factor_squarefree(f, xp, T, p); lV = lg(V);
    1883             : 
    1884             :   /* to hold factors and exponents */
    1885           0 :   t = cgetg(d+1,t_VEC);
    1886           0 :   E = cgetg(d+1, t_VECSMALL);
    1887           0 :   lfact = 1;
    1888           0 :   for (k=1; k<lV ; k++)
    1889             :   {
    1890           0 :     if (degpol(gel(V,k))==0) continue;
    1891           0 :     gel(t,lfact) = FlxqX_normalize(gel(V, k), T,p);
    1892           0 :     d = FlxqX_split_Berlekamp(&gel(t,lfact), xp, T, p);
    1893           0 :     for (j = 0; j < d; j++) E[lfact+j] = k;
    1894           0 :     lfact += d;
    1895             :   }
    1896           0 :   setlg(t, lfact);
    1897           0 :   setlg(E, lfact);
    1898           0 :   return sort_factor_pol(mkvec2(t, E), cmp_Flx);
    1899             : }
    1900             : 
    1901             : static GEN
    1902           0 : FpXQX_Berlekamp_i(GEN f, GEN T, GEN p)
    1903             : {
    1904           0 :   long lfact, d = degpol(f), j, k, lV;
    1905             :   GEN E, t, V;
    1906           0 :   switch(d)
    1907             :   {
    1908           0 :     case -1: retmkmat2(mkcolcopy(f), mkvecsmall(1));
    1909           0 :     case 0: return trivial_fact();
    1910             :   }
    1911           0 :   T = FpX_get_red(T, p);
    1912           0 :   f = FpXQX_normalize(f, T, p);
    1913           0 :   if (isabsolutepol(f)) return FpX_factorff_i(simplify_shallow(f), T, p);
    1914           0 :   if (degpol(f)==2) return FpXQX_factor_2(f, T, p);
    1915           0 :   V = FpXQX_factor_Yun(f, T, p); lV = lg(V);
    1916             : 
    1917             :   /* to hold factors and exponents */
    1918           0 :   t = cgetg(d+1,t_VEC);
    1919           0 :   E = cgetg(d+1, t_VECSMALL);
    1920           0 :   lfact = 1;
    1921           0 :   for (k=1; k<lV ; k++)
    1922             :   {
    1923           0 :     if (degpol(gel(V,k))==0) continue;
    1924           0 :     gel(t,lfact) = FpXQX_normalize(gel(V, k), T,p);
    1925           0 :     d = FpXQX_split_Berlekamp(&gel(t,lfact), T, p);
    1926           0 :     for (j = 0; j < d; j++) E[lfact+j] = k;
    1927           0 :     lfact += d;
    1928             :   }
    1929           0 :   setlg(t, lfact);
    1930           0 :   setlg(E, lfact);
    1931           0 :   return sort_factor_pol(mkvec2(t, E), cmp_RgX);
    1932             : }
    1933             : 
    1934             : static GEN
    1935         341 : FlxqX_ddf(GEN S, GEN Xq, GEN T, ulong p)
    1936             : {
    1937         341 :   pari_sp av = avma;
    1938             :   GEN b, g, h, F, f, Sr, xq, q;
    1939             :   long i, j, n, v, vT, bo, ro;
    1940             :   long B, l, m;
    1941             :   pari_timer ti;
    1942         341 :   n = get_FlxqX_degree(S); v = get_FlxqX_var(S);
    1943         341 :   vT = get_Flx_var(T);
    1944         341 :   if (n == 0) return cgetg(1, t_VEC);
    1945         341 :   if (n == 1) return mkvec(get_FlxqX_mod(S));
    1946         264 :   B = n/2;
    1947         264 :   l = usqrt(B);
    1948         264 :   m = (B+l-1)/l;
    1949         264 :   S = FlxqX_get_red(S, T, p);
    1950         264 :   b = cgetg(l+2, t_VEC);
    1951         264 :   gel(b, 1) = polx_FlxX(v, vT);
    1952         264 :   gel(b, 2) = Xq;
    1953         264 :   bo = brent_kung_optpow(n, l-1, 1);
    1954         264 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    1955         264 :   q = powuu(p, get_Flx_degree(T));
    1956         264 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    1957         264 :   if (expi(q) <= ro)
    1958           0 :     for (i = 3; i <= l+1; i++)
    1959           0 :       gel(b, i) = FlxqXQ_pow(gel(b, i-1), q, S, T, p);
    1960             :   else
    1961             :   {
    1962         264 :     xq = FlxqXQ_powers(gel(b, 2), bo, S, T, p);
    1963         264 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: xq baby");
    1964         464 :     for (i = 3; i <= l+1; i++)
    1965         200 :       gel(b, i) = FlxqX_FlxqXQV_eval(gel(b, i-1), xq, S, T, p);
    1966             :   }
    1967         264 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: baby");
    1968         264 :   xq = FlxqXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T, p);
    1969         264 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: xq giant");
    1970         264 :   g = cgetg(m+1, t_VEC);
    1971         264 :   gel(g, 1) = gel(xq, 2);
    1972         637 :   for(i = 2; i <= m; i++)
    1973         373 :     gel(g, i) = FlxqX_FlxqXQV_eval(gel(g, i-1), xq, S, T, p);
    1974         264 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: giant");
    1975         264 :   h = cgetg(m+1, t_VEC);
    1976         901 :   for (j = 1; j <= m; j++)
    1977             :   {
    1978         637 :     pari_sp av = avma;
    1979         637 :     GEN gj = gel(g, j);
    1980         637 :     GEN e = FlxX_sub(gj, gel(b, 1), p);
    1981        1430 :     for (i = 2; i <= l; i++)
    1982         793 :       e = FlxqXQ_mul(e, FlxX_sub(gj, gel(b, i), p), S, T, p);
    1983         637 :     gel(h, j) = gerepileupto(av, e);
    1984             :   }
    1985         264 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: diff");
    1986         264 :   Sr = get_FlxqX_mod(S);
    1987         264 :   F = cgetg(m+1, t_VEC);
    1988         901 :   for (j = 1; j <= m; j++)
    1989             :   {
    1990         637 :     gel(F, j) = FlxqX_gcd(Sr, gel(h, j), T, p);
    1991         637 :     Sr = FlxqX_div(Sr, gel(F,j), T, p);
    1992             :   }
    1993         264 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: F");
    1994         264 :   f = const_vec(n, pol1_FlxX(v, vT));
    1995         901 :   for (j = 1; j <= m; j++)
    1996             :   {
    1997         637 :     GEN e = gel(F, j);
    1998         774 :     for (i=l-1; i >= 0; i--)
    1999             :     {
    2000         774 :       GEN u = FlxqX_gcd(e, FlxX_sub(gel(g, j), gel(b, i+1), p), T, p);
    2001         774 :       if (degpol(u))
    2002             :       {
    2003         236 :         gel(f, l*j-i) = u;
    2004         236 :         e = FlxqX_div(e, u, T, p);
    2005             :       }
    2006         774 :       if (!degpol(e)) break;
    2007             :     }
    2008             :   }
    2009         264 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_ddf: f");
    2010         264 :   if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
    2011         264 :   return gerepilecopy(av, f);
    2012             : }
    2013             : 
    2014             : static void
    2015         229 : FlxqX_edf_rec(GEN S, GEN xp, GEN Xp, GEN hp, GEN t, long d, GEN T, ulong p, GEN V, long idx)
    2016             : {
    2017         229 :   GEN Sp = get_FlxqX_mod(S);
    2018             :   GEN u1, u2, f1, f2;
    2019             :   GEN h;
    2020         229 :   h = FlxqX_get_red(hp, T, p);
    2021         229 :   t = FlxqX_rem(t, S, T, p);
    2022         229 :   Xp = FlxqX_rem(Xp, h, T, p);
    2023         229 :   u1 = FlxqX_roots_split(hp, xp, Xp, h, T, p);
    2024         229 :   f1 = FlxqX_gcd(FlxqX_FlxqXQ_eval(u1, t, S, T, p), Sp, T, p);
    2025         229 :   f1 = FlxqX_normalize(f1, T, p);
    2026         229 :   u2 = FlxqX_div(hp, u1, T, p);
    2027         229 :   f2 = FlxqX_div(Sp, f1, T, p);
    2028         229 :   if (degpol(u1)==1)
    2029         167 :     gel(V, idx) = f1;
    2030             :   else
    2031          62 :     FlxqX_edf_rec(FlxqX_get_red(f1, T, p), xp, Xp, u1, t, d, T, p, V, idx);
    2032         229 :   idx += degpol(f1)/d;
    2033         229 :   if (degpol(u2)==1)
    2034         180 :     gel(V, idx) = f2;
    2035             :   else
    2036          49 :     FlxqX_edf_rec(FlxqX_get_red(f2, T, p), xp, Xp, u2, t, d, T, p, V, idx);
    2037         229 : }
    2038             : 
    2039             : static void
    2040         118 : FlxqX_edf(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, ulong p, GEN V, long idx)
    2041             : {
    2042         118 :   long n = degpol(Sp), r = n/d, vS = varn(Sp), vT = get_Flx_var(T);
    2043             :   GEN S, h, t;
    2044             :   pari_timer ti;
    2045         236 :   if (r==1) { gel(V, idx) = Sp; return; }
    2046         118 :   S = FlxqX_get_red(Sp, T, p);
    2047         118 :   Xp = FlxqX_rem(Xp, S, T, p);
    2048         118 :   Xq = FlxqX_rem(Xq, S, T, p);
    2049         118 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2050             :   do
    2051             :   {
    2052         139 :     GEN g = random_FlxqX(n, vS, T, p);
    2053         139 :     t = gel(FlxqXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2054         139 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_edf: FlxqXQ_auttrace");
    2055         139 :     h = FlxqXQ_minpoly(t, S, T, p);
    2056         139 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FlxqX_edf: FlxqXQ_minpoly");
    2057         139 :   } while (degpol(h) != r);
    2058         118 :   Xp = FlxqXQ_powu(polx_FlxX(vS, vT), p, h, T, p);
    2059         118 :   FlxqX_edf_rec(S, xp, Xp, h, t, d, T, p, V, idx);
    2060             : }
    2061             : 
    2062             : static void
    2063           0 : FlxqX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, ulong p, GEN V, long idx)
    2064             : {
    2065           0 :   long v = varn(Sp), n = degpol(Sp), r = n/d;
    2066             :   GEN S, f, ff;
    2067           0 :   long vT = get_Flx_var(T), dT = get_Flx_degree(T);
    2068           0 :   if (r==1) { gel(V, idx) = Sp; return; }
    2069           0 :   S = FlxqX_get_red(Sp, T, p);
    2070           0 :   Xp = FlxqX_rem(Xp, S, T, p);
    2071           0 :   Xq = FlxqX_rem(Xq, S, T, p);
    2072             :   while (1)
    2073             :   {
    2074           0 :     pari_sp btop = avma;
    2075             :     long i;
    2076           0 :     GEN g = random_FlxqX(n, v, T, p);
    2077           0 :     GEN t = gel(FlxqXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2078           0 :     if (lgpol(t) == 0) continue;
    2079           0 :     for(i=1; i<=10; i++)
    2080             :     {
    2081           0 :       pari_sp btop2 = avma;
    2082           0 :       GEN r = random_Flx(dT, vT, p);
    2083           0 :       GEN R = FlxqXQ_halfFrobenius_i(FlxX_Flx_add(t, r, p), xp, Xp, S, T, p);
    2084           0 :       f = FlxqX_gcd(FlxX_Flx_sub(R, pol1_Flx(vT), p), Sp, T, p);
    2085           0 :       if (degpol(f) > 0 && degpol(f) < n) break;
    2086           0 :       avma = btop2;
    2087             :     }
    2088           0 :     if (degpol(f) > 0 && degpol(f) < n) break;
    2089           0 :     avma = btop;
    2090           0 :   }
    2091           0 :   f = FlxqX_normalize(f, T, p);
    2092           0 :   ff = FlxqX_div(Sp, f , T, p);
    2093           0 :   FlxqX_edf_simple(f, xp, Xp, Xq, d, T, p, V, idx);
    2094           0 :   FlxqX_edf_simple(ff, xp, Xp, Xq, d, T, p, V, idx+degpol(f)/d);
    2095             : }
    2096             : 
    2097             : static GEN
    2098         209 : FlxqX_factor_Shoup(GEN S, GEN xp, GEN T, ulong p)
    2099             : {
    2100         209 :   long i, n, s = 0;
    2101             :   GEN X, Xp, Xq, D, V;
    2102         209 :   long dT = get_Flx_degree(T), vT = get_Flx_var(T);
    2103         209 :   long e = expi(powuu(p, dT));
    2104             :   pari_timer ti;
    2105         209 :   n = get_FlxqX_degree(S);
    2106         209 :   S = FlxqX_get_red(S, T, p);
    2107         209 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    2108         209 :   X  = polx_FlxX(get_FlxqX_var(S), vT);
    2109         209 :   Xp = FlxqXQ_powu(X, p, S, T, p);
    2110         209 :   Xq = FlxqXQ_Frobenius(xp, Xp, S, T, p);
    2111         209 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_Frobenius");
    2112         209 :   D = FlxqX_ddf(S, Xq, T, p);
    2113         209 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_ddf");
    2114         756 :   for (i = 1; i <= n; i++)
    2115         547 :     s += degpol(gel(D,i))/i;
    2116         209 :   V = cgetg(s+1, t_COL);
    2117         756 :   for (i = 1, s = 1; i <= n; i++)
    2118             :   {
    2119         547 :     GEN Di = gel(D,i);
    2120         547 :     long ni = degpol(Di), ri = ni/i;
    2121         547 :     if (ni == 0) continue;
    2122         230 :     Di = FlxqX_normalize(Di, T, p);
    2123         230 :     if (ni == i) { gel(V, s++) = Di; continue; }
    2124         118 :     if (ri <= e*expu(e))
    2125         118 :       FlxqX_edf(Di, xp, Xp, Xq, i, T, p, V, s);
    2126             :     else
    2127           0 :       FlxqX_edf_simple(Di, xp, Xp, Xq, i, T, p, V, s);
    2128         118 :     if (DEBUGLEVEL>=6) timer_printf(&ti,"FlxqX_edf(%ld)",i);
    2129         118 :     s += ri;
    2130             :   }
    2131         209 :   return V;
    2132             : }
    2133             : 
    2134             : static GEN
    2135        1041 : FlxqX_factor_Cantor(GEN f, GEN T, ulong p)
    2136             : {
    2137             :   GEN xp, E, F, V;
    2138             :   long i, j, l;
    2139        1041 :   T = Flx_get_red(T, p);
    2140        1041 :   f = FlxqX_normalize(f, T, p);
    2141        1041 :   switch(degpol(f))
    2142             :   {
    2143          21 :     case -1: retmkmat2(mkcol(f), mkvecsmall(1));
    2144          21 :     case 0: return trivial_fact();
    2145          21 :     case 1: retmkmat2(mkcol(f), mkvecsmall(1));
    2146         181 :     case 2: return FlxqX_factor_2(f, T, p);
    2147             :   }
    2148         797 :   if (FlxY_degreex(f) <= 0) return Flx_factorff_i(FlxX_to_Flx(f), T, p);
    2149         181 :   xp = Flx_Frobenius(T, p);
    2150         181 :   V = FlxqX_factor_squarefree(f, xp, get_Flx_mod(T), p);
    2151         181 :   l = lg(V);
    2152         181 :   F = cgetg(l, t_VEC);
    2153         181 :   E = cgetg(l, t_VEC);
    2154        1133 :   for (i=1, j=1; i < l; i++)
    2155         952 :     if (degpol(gel(V,i)))
    2156             :     {
    2157         209 :       GEN Fj = FlxqX_factor_Shoup(gel(V,i), xp, T, p);
    2158         209 :       gel(F, j) = Fj;
    2159         209 :       gel(E, j) = const_vecsmall(lg(Fj)-1, i);
    2160         209 :       j++;
    2161             :     }
    2162         181 :   return sort_factor_pol(FE_concat(F,E,j), cmp_Flx);
    2163             : }
    2164             : 
    2165             : long
    2166         132 : FlxqX_nbfact_Frobenius(GEN S, GEN Xq, GEN T, ulong p)
    2167             : {
    2168         132 :   pari_sp av = avma;
    2169         132 :   GEN u = get_FlxqX_mod(S);
    2170             :   long s;
    2171         132 :   if (FlxY_degreex(u) <= 0)
    2172           0 :     s = Flx_nbfactff(FlxX_to_Flx(u), T, p);
    2173             :   else
    2174         132 :     s = ddf_to_nbfact(FlxqX_ddf(S, Xq, T, p));
    2175         132 :   avma = av; return s;
    2176             : }
    2177             : 
    2178             : long
    2179         280 : FlxqX_nbfact(GEN S, GEN T, ulong p)
    2180             : {
    2181         280 :   pari_sp av = avma;
    2182         280 :   GEN u = get_FlxqX_mod(S);
    2183             :   long s;
    2184         280 :   if (FlxY_degreex(u) <= 0)
    2185         280 :     s = Flx_nbfactff(FlxX_to_Flx(u), T, p);
    2186             :   else
    2187           0 :     s = ddf_to_nbfact(FlxqX_ddf(S, FlxqX_Frobenius(S, T, p), T, p));
    2188         280 :   avma = av; return s;
    2189             : }
    2190             : 
    2191             : GEN
    2192         103 : FlxqX_factor(GEN x, GEN T, ulong p)
    2193             : {
    2194         103 :   pari_sp av = avma;
    2195         103 :   return gerepilecopy(av, FlxqX_factor_Cantor(x, T, p));
    2196             : }
    2197             : 
    2198             : GEN
    2199          77 : F2xqX_factor(GEN x, GEN T)
    2200             : {
    2201          77 :   pari_sp av = avma;
    2202          77 :   return gerepilecopy(av, F2xqX_factor_Cantor(x, T));
    2203             : }
    2204             : 
    2205             : static GEN
    2206          72 : FpXQX_ddf(GEN S, GEN Xq, GEN T, GEN p)
    2207             : {
    2208          72 :   pari_sp av = avma;
    2209             :   GEN b, g, h, F, f, Sr, xq, q;
    2210             :   long i, j, n, v, bo, ro;
    2211             :   long B, l, m;
    2212             :   pari_timer ti;
    2213          72 :   n = get_FpXQX_degree(S); v = get_FpXQX_var(S);
    2214          72 :   if (n == 0) return cgetg(1, t_VEC);
    2215          72 :   if (n == 1) return mkvec(get_FpXQX_mod(S));
    2216          72 :   B = n/2;
    2217          72 :   l = usqrt(B);
    2218          72 :   m = (B+l-1)/l;
    2219          72 :   S = FpXQX_get_red(S, T, p);
    2220          72 :   b = cgetg(l+2, t_VEC);
    2221          72 :   gel(b, 1) = pol_x(v);
    2222          72 :   gel(b, 2) = Xq;
    2223          72 :   bo = brent_kung_optpow(n, l-1, 1);
    2224          72 :   ro = l<=1 ? 0: (bo-1)/(l-1) + ((n-1)/bo);
    2225          72 :   q = powiu(p, get_FpX_degree(T));
    2226          72 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2227          72 :   if (expi(q) <= ro)
    2228           0 :     for (i = 3; i <= l+1; i++)
    2229           0 :       gel(b, i) = FpXQXQ_pow(gel(b, i-1), q, S, T, p);
    2230             :   else
    2231             :   {
    2232          72 :     xq = FpXQXQ_powers(gel(b, 2), bo, S, T, p);
    2233          72 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: xq baby");
    2234         180 :     for (i = 3; i <= l+1; i++)
    2235         108 :       gel(b, i) = FpXQX_FpXQXQV_eval(gel(b, i-1), xq, S, T, p);
    2236             :   }
    2237          72 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: baby");
    2238          72 :   xq = FpXQXQ_powers(gel(b, l+1), brent_kung_optpow(n, m-1, 1), S, T, p);
    2239          72 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: xq giant");
    2240          72 :   g = cgetg(m+1, t_VEC);
    2241          72 :   gel(g, 1) = gel(xq, 2);
    2242         238 :   for(i = 2; i <= m; i++)
    2243         166 :     gel(g, i) = FpXQX_FpXQXQV_eval(gel(g, i-1), xq, S, T, p);
    2244          72 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: giant");
    2245          72 :   h = cgetg(m+1, t_VEC);
    2246         310 :   for (j = 1; j <= m; j++)
    2247             :   {
    2248         238 :     pari_sp av = avma;
    2249         238 :     GEN gj = gel(g, j);
    2250         238 :     GEN e = FpXX_sub(gj, gel(b, 1), p);
    2251         733 :     for (i = 2; i <= l; i++)
    2252         495 :       e = FpXQXQ_mul(e, FpXX_sub(gj, gel(b, i), p), S, T, p);
    2253         238 :     gel(h, j) = gerepileupto(av, e);
    2254             :   }
    2255          72 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: diff");
    2256          72 :   Sr = get_FpXQX_mod(S);
    2257          72 :   F = cgetg(m+1, t_VEC);
    2258         310 :   for (j = 1; j <= m; j++)
    2259             :   {
    2260         238 :     gel(F, j) = FpXQX_gcd(Sr, gel(h, j), T, p);
    2261         238 :     Sr = FpXQX_div(Sr, gel(F,j), T, p);
    2262             :   }
    2263          72 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: F");
    2264          72 :   f = const_vec(n, pol_1(v));
    2265         310 :   for (j = 1; j <= m; j++)
    2266             :   {
    2267         238 :     GEN e = gel(F, j);
    2268         311 :     for (i=l-1; i >= 0; i--)
    2269             :     {
    2270         311 :       GEN u = FpXQX_gcd(e, FpXX_sub(gel(g, j), gel(b, i+1), p), T, p);
    2271         311 :       if (degpol(u))
    2272             :       {
    2273          86 :         gel(f, l*j-i) = u;
    2274          86 :         e = FpXQX_div(e, u, T, p);
    2275             :       }
    2276         311 :       if (!degpol(e)) break;
    2277             :     }
    2278             :   }
    2279          72 :   if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_ddf: f");
    2280          72 :   if (degpol(Sr)) gel(f, degpol(Sr)) = Sr;
    2281          72 :   return gerepilecopy(av, f);
    2282             : }
    2283             : 
    2284             : static void
    2285          23 : FpXQX_edf_rec(GEN S, GEN xp, GEN Xp, GEN hp, GEN t, long d, GEN T, GEN p, GEN V, long idx)
    2286             : {
    2287          23 :   GEN Sp = get_FpXQX_mod(S);
    2288             :   GEN u1, u2, f1, f2;
    2289             :   GEN h;
    2290          23 :   h = FpXQX_get_red(hp, T, p);
    2291          23 :   t = FpXQX_rem(t, S, T, p);
    2292          23 :   Xp = FpXQX_rem(Xp, h, T, p);
    2293          23 :   u1 = FpXQX_roots_split(hp, xp, Xp, h, T, p);
    2294          23 :   f1 = FpXQX_gcd(FpXQX_FpXQXQ_eval(u1, t, S, T, p), Sp, T, p);
    2295          23 :   f1 = FpXQX_normalize(f1, T, p);
    2296          23 :   u2 = FpXQX_div(hp, u1, T, p);
    2297          23 :   f2 = FpXQX_div(Sp, f1, T, p);
    2298          23 :   if (degpol(u1)==1)
    2299          16 :     gel(V, idx) = f1;
    2300             :   else
    2301           7 :     FpXQX_edf_rec(FpXQX_get_red(f1, T, p), xp, Xp, u1, t, d, T, p, V, idx);
    2302          23 :   idx += degpol(f1)/d;
    2303          23 :   if (degpol(u2)==1)
    2304          15 :     gel(V, idx) = f2;
    2305             :   else
    2306           8 :     FpXQX_edf_rec(FpXQX_get_red(f2, T, p), xp, Xp, u2, t, d, T, p, V, idx);
    2307          23 : }
    2308             : 
    2309             : static void
    2310           8 : FpXQX_edf(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, GEN p, GEN V, long idx)
    2311             : {
    2312           8 :   long n = degpol(Sp), r = n/d, vS = varn(Sp);
    2313             :   GEN S, h, t;
    2314             :   pari_timer ti;
    2315          16 :   if (r==1) { gel(V, idx) = Sp; return; }
    2316           8 :   S = FpXQX_get_red(Sp, T, p);
    2317           8 :   Xp = FpXQX_rem(Xp, S, T, p);
    2318           8 :   Xq = FpXQX_rem(Xq, S, T, p);
    2319           8 :   if (DEBUGLEVEL>=7) timer_start(&ti);
    2320             :   do
    2321             :   {
    2322           8 :     GEN g = random_FpXQX(n, vS, T, p);
    2323           8 :     t = gel(FpXQXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2324           8 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_edf: FpXQXQ_auttrace");
    2325           8 :     h = FpXQXQ_minpoly(t, S, T, p);
    2326           8 :     if (DEBUGLEVEL>=7) timer_printf(&ti,"FpXQX_edf: FpXQXQ_minpoly");
    2327           8 :   } while (degpol(h) != r);
    2328           8 :   Xp = FpXQXQ_pow(pol_x(vS), p, h, T, p);
    2329           8 :   FpXQX_edf_rec(S, xp, Xp, h, t, d, T, p, V, idx);
    2330             : }
    2331             : 
    2332             : static void
    2333           0 : FpXQX_edf_simple(GEN Sp, GEN xp, GEN Xp, GEN Xq, long d, GEN T, GEN p, GEN V, long idx)
    2334             : {
    2335           0 :   long v = varn(Sp), n = degpol(Sp), r = n/d;
    2336             :   GEN S, f, ff;
    2337           0 :   long vT = get_FpX_var(T), dT = get_FpX_degree(T);
    2338           0 :   if (r==1) { gel(V, idx) = Sp; return; }
    2339           0 :   S = FpXQX_get_red(Sp, T, p);
    2340           0 :   Xp = FpXQX_rem(Xp, S, T, p);
    2341           0 :   Xq = FpXQX_rem(Xq, S, T, p);
    2342             :   while (1)
    2343             :   {
    2344           0 :     pari_sp btop = avma;
    2345             :     long i;
    2346           0 :     GEN g = random_FpXQX(n, v, T, p);
    2347           0 :     GEN t = gel(FpXQXQ_auttrace(mkvec2(Xq, g), d, S, T, p), 2);
    2348           0 :     if (lgpol(t) == 0) continue;
    2349           0 :     for(i=1; i<=10; i++)
    2350             :     {
    2351           0 :       pari_sp btop2 = avma;
    2352           0 :       GEN r = random_FpX(dT, vT, p);
    2353           0 :       GEN R = FpXQXQ_halfFrobenius_i(FqX_Fq_add(t, r, T, p), xp, Xp, S, T, p);
    2354           0 :       f = FpXQX_gcd(FqX_Fq_add(R, gen_m1, T, p), Sp, T, p);
    2355           0 :       if (degpol(f) > 0 && degpol(f) < n) break;
    2356           0 :       avma = btop2;
    2357             :     }
    2358           0 :     if (degpol(f) > 0 && degpol(f) < n) break;
    2359           0 :     avma = btop;
    2360           0 :   }
    2361           0 :   f = FpXQX_normalize(f, T, p);
    2362           0 :   ff = FpXQX_div(Sp, f , T, p);
    2363           0 :   FpXQX_edf_simple(f,  xp, Xp, Xq, d, T, p, V, idx);
    2364           0 :   FpXQX_edf_simple(ff, xp, Xp, Xq, d, T, p, V, idx+degpol(f)/d);
    2365             : }
    2366             : 
    2367             : static GEN
    2368          22 : FpXQX_factor_Shoup(GEN S, GEN xp, GEN T, GEN p)
    2369             : {
    2370          22 :   long i, n, s = 0;
    2371             :   GEN X, Xp, Xq, D, V;
    2372          22 :   long dT = get_FpX_degree(T);
    2373          22 :   long e = expi(powiu(p, dT));
    2374             :   pari_timer ti;
    2375          22 :   n = get_FpXQX_degree(S);
    2376          22 :   S = FpXQX_get_red(S, T, p);
    2377          22 :   if (DEBUGLEVEL>=6) timer_start(&ti);
    2378          22 :   X  = pol_x(get_FpXQX_var(S));
    2379          22 :   Xp = FpXQXQ_pow(X, p, S, T, p);
    2380          22 :   Xq = FpXQXQ_Frobenius(xp, Xp, S, T, p);
    2381          22 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_Frobenius");
    2382          22 :   D = FpXQX_ddf(S, Xq, T, p);
    2383          22 :   if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_ddf");
    2384         140 :   for (i = 1; i <= n; i++)
    2385         118 :     s += degpol(gel(D,i))/i;
    2386          22 :   V = cgetg(s+1, t_COL);
    2387         140 :   for (i = 1, s = 1; i <= n; i++)
    2388             :   {
    2389         118 :     GEN Di = gel(D,i);
    2390         118 :     long ni = degpol(Di), ri = ni/i;
    2391         118 :     if (ni == 0) continue;
    2392          50 :     Di = FpXQX_normalize(Di, T, p);
    2393          50 :     if (ni == i) { gel(V, s++) = Di; continue; }
    2394           8 :     if (ri <= e*expu(e))
    2395           8 :       FpXQX_edf(Di, xp, Xp, Xq, i, T, p, V, s);
    2396             :     else
    2397           0 :       FpXQX_edf_simple(Di, xp, Xp, Xq, i, T, p, V, s);
    2398           8 :     if (DEBUGLEVEL>=6) timer_printf(&ti,"FpXQX_edf(%ld)",i);
    2399           8 :     s += ri;
    2400             :   }
    2401          22 :   return V;
    2402             : }
    2403             : 
    2404             : static GEN
    2405         135 : FpXQX_factor_Cantor(GEN f, GEN T, GEN p)
    2406             : {
    2407             :   GEN xp, E, F, V;
    2408             :   long i, j, l;
    2409         135 :   T = FpX_get_red(T, p);
    2410         135 :   f = FpXQX_normalize(f, T, p);
    2411         135 :   switch(degpol(f))
    2412             :   {
    2413          14 :     case -1: retmkmat2(mkcol(f), mkvecsmall(1));
    2414          14 :     case 0: return trivial_fact();
    2415          21 :     case 1: retmkmat2(mkcol(f), mkvecsmall(1));
    2416          43 :     case 2: return FpXQX_factor_2(f, T, p);
    2417             :   }
    2418          43 :   if (isabsolutepol(f)) return FpX_factorff_i(simplify_shallow(f), T, p);
    2419          22 :   xp = FpX_Frobenius(T, p);
    2420          22 :   V = FpXQX_factor_Yun(f, T, p);
    2421          22 :   l = lg(V);
    2422          22 :   F = cgetg(l, t_VEC);
    2423          22 :   E = cgetg(l, t_VEC);
    2424          44 :   for (i=1, j=1; i < l; i++)
    2425          22 :     if (degpol(gel(V,i)))
    2426             :     {
    2427          22 :       GEN Fj = FpXQX_factor_Shoup(gel(V,i), xp, T, p);
    2428          22 :       gel(F, j) = Fj;
    2429          22 :       gel(E, j) = const_vecsmall(lg(Fj)-1, i);
    2430          22 :       j++;
    2431             :     }
    2432          22 :   return sort_factor_pol(FE_concat(F,E,j), cmp_RgX);
    2433             : }
    2434             : 
    2435             : long
    2436          50 : FpXQX_nbfact_Frobenius(GEN S, GEN Xq, GEN T, GEN p)
    2437             : {
    2438          50 :   pari_sp av = avma;
    2439          50 :   GEN u = get_FpXQX_mod(S);
    2440             :   long s;
    2441          50 :   if (lgefint(p)==3)
    2442             :   {
    2443           0 :     ulong pp = p[2];
    2444           0 :     long vT = get_FpX_var(T);
    2445           0 :     GEN Sp = ZXXT_to_FlxXT(S,pp,vT), Xqp = ZXX_to_FlxX(Xq,pp,vT);
    2446           0 :     s = FlxqX_nbfact_Frobenius(Sp, Xqp, ZXT_to_FlxT(T,pp), pp);
    2447             :   }
    2448          50 :   else if (isabsolutepol(u))
    2449           0 :     s = FpX_nbfactff(simplify_shallow(u), T, p);
    2450             :   else
    2451          50 :     s = ddf_to_nbfact(FpXQX_ddf(S, Xq, T, p));
    2452          50 :   avma = av; return s;
    2453             : }
    2454             : 
    2455             : long
    2456           0 : FpXQX_nbfact(GEN S, GEN T, GEN p)
    2457             : {
    2458           0 :   pari_sp av = avma;
    2459           0 :   GEN u = get_FpXQX_mod(S);
    2460             :   long s;
    2461           0 :   if (lgefint(p)==3)
    2462             :   {
    2463           0 :     ulong pp = p[2];
    2464           0 :     long vT = get_FpX_var(T);
    2465           0 :     s = FlxqX_nbfact(ZXXT_to_FlxXT(S,pp,vT), ZXT_to_FlxT(T,pp), pp);
    2466             :   }
    2467           0 :   else if (isabsolutepol(u))
    2468           0 :     s = FpX_nbfactff(simplify_shallow(u), T, p);
    2469             :   else
    2470           0 :     s = ddf_to_nbfact(FpXQX_ddf(S, FpXQX_Frobenius(S, T, p), T, p));
    2471           0 :   avma = av; return s;
    2472             : }
    2473             : 
    2474             : long
    2475           0 : FqX_nbfact(GEN u, GEN T, GEN p)
    2476             : {
    2477           0 :   return T ? FpXQX_nbfact(u, T, p): FpX_nbfact(u, p);
    2478             : }
    2479             : 
    2480             : 
    2481             : static GEN
    2482           0 : FpXQX_factor_Berlekamp_i(GEN f, GEN T, GEN p)
    2483             : {
    2484           0 :   if (lgefint(p)==3)
    2485             :   {
    2486           0 :     ulong pp = p[2];
    2487             :     GEN M;
    2488           0 :     long vT = get_FpX_var(T);
    2489           0 :     if (pp==2)
    2490             :     {
    2491           0 :       M = F2xqX_factor_Cantor(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    2492           0 :       return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
    2493             :     }
    2494           0 :     M = FlxqX_Berlekamp_i(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    2495           0 :     return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
    2496             :   }
    2497           0 :   return FpXQX_Berlekamp_i(f, T, p);
    2498             : }
    2499             : 
    2500             : GEN
    2501           0 : FpXQX_factor_Berlekamp(GEN x, GEN T, GEN p)
    2502             : {
    2503           0 :   pari_sp av = avma;
    2504           0 :   return gerepilecopy(av, FpXQX_factor_Berlekamp_i(x, T, p));
    2505             : }
    2506             : 
    2507             : static GEN
    2508        1780 : FpXQX_factor_i(GEN f, GEN T, GEN p)
    2509             : {
    2510        1780 :   if (lgefint(p)==3)
    2511             :   {
    2512        1645 :     ulong pp = p[2];
    2513             :     GEN M;
    2514        1645 :     long vT = get_FpX_var(T);
    2515        1645 :     if (pp==2)
    2516             :     {
    2517         707 :       M = F2xqX_factor_Cantor(ZXX_to_F2xX(f, vT),  ZX_to_F2x(get_FpX_mod(T)));
    2518         707 :       return mkvec2(F2xXC_to_ZXXC(gel(M,1)), gel(M,2));
    2519             :     }
    2520         938 :     M = FlxqX_factor_Cantor(ZXX_to_FlxX(f, pp, vT),  ZXT_to_FlxT(T, pp), pp);
    2521         938 :     return mkvec2(FlxXC_to_ZXXC(gel(M,1)), gel(M,2));
    2522             :   }
    2523         135 :   return FpXQX_factor_Cantor(f, T, p);
    2524             : }
    2525             : 
    2526             : GEN
    2527        1388 : FpXQX_factor(GEN x, GEN T, GEN p)
    2528             : {
    2529        1388 :   pari_sp av = avma;
    2530        1388 :   return gerepilecopy(av, FpXQX_factor_i(x, T, p));
    2531             : }
    2532             : 
    2533             : long
    2534         168 : FqX_ispower(GEN f, ulong k, GEN T, GEN p, GEN *pt)
    2535             : {
    2536         168 :   pari_sp av = avma;
    2537             :   long v, w;
    2538             :   ulong pp;
    2539             :   GEN lc, F;
    2540             : 
    2541         168 :   if (degpol(f) % k) return 0;
    2542         168 :   lc = leading_coeff(f);
    2543         168 :   lc = Fq_sqrtn(lc, stoi(k), T, p, NULL);
    2544         168 :   if (!lc) { av = avma; return 0; }
    2545         168 :   pp = itou_or_0(p);
    2546         168 :   f = FqX_normalize(f, T, p);
    2547         168 :   v = pp? u_lvalrem(k,pp,&k): 0;
    2548         168 :   if (v)
    2549             :   {
    2550             :     long i;
    2551          63 :     w = u_lval(RgX_deflate_order(f), pp);
    2552          63 :     if (w < v) { avma = av; return 0; }
    2553             :     /* deflate as much as possible using frobenius, unless k reduced to 1 */
    2554          56 :     if (k == 1) w = v;
    2555          56 :     f = RgX_deflate(f, upowuu(pp,w));
    2556          56 :     if (T) for (i = 0; i < w; i++) f = FqX_frobinv_inplace(f, T, p);
    2557          56 :     w -= v;
    2558             :   }
    2559             :   else
    2560         105 :     w = 0;
    2561             :   /* k coprime to p; true f we're testing is f^(p^w) */
    2562         161 :   if (k == 1)
    2563          28 :     F = f;
    2564             :   else
    2565             :   {
    2566         133 :     ulong pow = upowuu(pp,w);
    2567         133 :     F = pt? pol_1(varn(f)): NULL;
    2568         441 :     while (degpol(f) > 0)
    2569             :     {
    2570         196 :       GEN gk, g, df = FqX_deriv(f, T, p);
    2571             :       long v;
    2572         196 :       if (!signe(df)) { pow *= pp; f = FqX_frob_deflate(f, T, p); continue; }
    2573         133 :       g = FqX_div(f, FqX_normalize(FqX_gcd(f,df,T,p),T,p), T,p);
    2574             :       /* g | f is squarefree,monic; remove (g^k)^oo from f */
    2575         133 :       gk = FqX_powu(g, k, T,p);
    2576         133 :       v = 0;
    2577         329 :       for(v = 0;; v++)
    2578             :       {
    2579         329 :         GEN q = FqX_divrem(f, gk, T,p, ONLY_DIVIDES);
    2580         329 :         if (!q) break;
    2581         196 :         f = q;
    2582         196 :       }
    2583             :       /* some factor from g remains in f ? */
    2584         133 :       if (!v || degpol(FqX_gcd(f,g,T,p))) { avma = av; return 0; }
    2585         112 :       if (F) F = FqX_mul(F, FqX_powu(g, v*pow, T,p), T,p);
    2586             :     }
    2587             :   }
    2588         140 :   if (pt) *pt = gerepileupto(av, FqX_Fq_mul(F, lc, T,p));
    2589         140 :   return 1;
    2590             : }
    2591             : 
    2592             : static void
    2593         420 : ffcheck(pari_sp *av, GEN *f, GEN *T, GEN p)
    2594             : {
    2595             :   long v;
    2596         420 :   if (typ(*T)!=t_POL) pari_err_TYPE("factorff",*T);
    2597         420 :   if (typ(*f)!=t_POL) pari_err_TYPE("factorff",*f);
    2598         420 :   if (typ(p)!=t_INT) pari_err_TYPE("factorff",p);
    2599         420 :   v = varn(*T);
    2600         420 :   if (varncmp(v, varn(*f)) <= 0)
    2601           0 :     pari_err_PRIORITY("factorff", *T, "<=", varn(*f));
    2602         420 :   *T = RgX_to_FpX(*T, p); *av = avma;
    2603         420 :   *f = RgX_to_FqX(*f, *T,p);
    2604         420 : }
    2605             : GEN
    2606         581 : factorff(GEN f, GEN p, GEN T)
    2607             : {
    2608             :   pari_sp av;
    2609             :   GEN z;
    2610         581 :   if (!p || !T)
    2611             :   {
    2612             :     long pa, t;
    2613         189 :     if (typ(f) != t_POL) pari_err_TYPE("factorff",f);
    2614         189 :     T = p = NULL;
    2615         189 :     t = RgX_type(f, &p, &T, &pa);
    2616         189 :     if (t != t_FFELT) pari_err_TYPE("factorff",f);
    2617         189 :     return FFX_factor(f,T);
    2618             :   }
    2619         392 :   ffcheck(&av, &f, &T, p); z = FpXQX_factor_i(f, T, p);
    2620         392 :   return to_Fq_fact(gel(z,1),gel(z,2), T,p, av);
    2621             : }
    2622             : GEN
    2623      103390 : polrootsff(GEN f, GEN p, GEN T)
    2624             : {
    2625             :   pari_sp av;
    2626             :   GEN z;
    2627      103390 :   if (!p || !T)
    2628             :   {
    2629             :     long pa, t;
    2630      103362 :     if (typ(f) != t_POL) pari_err_TYPE("polrootsff",f);
    2631      103362 :     T = p = NULL;
    2632      103362 :     t = RgX_type(f, &p, &T, &pa);
    2633      103362 :     if (t != t_FFELT) pari_err_TYPE("polrootsff",f);
    2634      103362 :     return FFX_roots(f,T);
    2635             :   }
    2636          28 :   ffcheck(&av, &f, &T, p); z = FpXQX_roots_i(f, T, p);
    2637          28 :   return to_FqC(z, T,p, av);
    2638             : }
    2639             : 
    2640             : long
    2641         483 : FlxqX_is_squarefree(GEN P, GEN T, ulong p)
    2642             : {
    2643         483 :   pari_sp av = avma;
    2644         483 :   GEN z = FlxqX_gcd(P, FlxX_deriv(P, p), T, p);
    2645         483 :   avma = av;
    2646         483 :   return degpol(z)==0;
    2647             : }
    2648             : 
    2649             : long
    2650      242977 : FqX_is_squarefree(GEN P, GEN T, GEN p)
    2651             : {
    2652      242977 :   pari_sp av = avma;
    2653      242977 :   GEN z = FqX_gcd(P, FqX_deriv(P, T, p), T, p);
    2654      242977 :   avma = av;
    2655      242977 :   return degpol(z)==0;
    2656             : }
    2657             : 
    2658             : /* See also: Isomorphisms between finite field and relative
    2659             :  * factorization in polarit3.c */

Generated by: LCOV version 1.11