Code coverage tests

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

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

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

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

Generated by: LCOV version 1.13