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

Generated by: LCOV version 1.11