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 23724-b3bdf5af3) Lines: 1585 1903 83.3 %
Date: 2019-03-25 05:45:24 Functions: 126 149 84.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13