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.16.2 lcov report (development 29115-f22e516b23) Lines: 1614 1946 82.9 %
Date: 2024-03-28 08:06:56 Functions: 127 153 83.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14