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 - FlxX.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.18.1 lcov report (development 30401-87099e65a6) Lines: 1198 1484 80.7 %
Date: 2025-07-18 09:23:12 Functions: 150 198 75.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2019  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             : /***********************************************************************/
      19             : /**                                                                   **/
      20             : /**                               FlxX                                **/
      21             : /**                                                                   **/
      22             : /***********************************************************************/
      23             : 
      24             : /* FlxX are t_POL with Flx coefficients.
      25             :  * Normally the variable ordering should be respected.*/
      26             : 
      27             : /*Similar to normalizepol, in place*/
      28             : /*FlxX_renormalize=zxX_renormalize */
      29             : GEN
      30    17723426 : FlxX_renormalize(GEN /*in place*/ x, long lx)
      31             : {
      32             :   long i;
      33    22554186 :   for (i = lx-1; i>1; i--)
      34    21775037 :     if (lgpol(gel(x,i))) break;
      35    17723447 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
      36    17723985 :   setlg(x, i+1); setsigne(x, i!=1); return x;
      37             : }
      38             : 
      39             : GEN
      40      758614 : pol1_FlxX(long v, long sv)
      41             : {
      42      758614 :   GEN z = cgetg(3, t_POL);
      43      758613 :   z[1] = evalsigne(1) | evalvarn(v);
      44      758613 :   gel(z,2) = pol1_Flx(sv); return z;
      45             : }
      46             : 
      47             : GEN
      48      690500 : polx_FlxX(long v, long sv)
      49             : {
      50      690500 :   GEN z = cgetg(4, t_POL);
      51      690500 :   z[1] = evalsigne(1) | evalvarn(v);
      52      690500 :   gel(z,2) = pol0_Flx(sv);
      53      690500 :   gel(z,3) = pol1_Flx(sv); return z;
      54             : }
      55             : 
      56             : long
      57     3079378 : FlxY_degreex(GEN b)
      58             : {
      59     3079378 :   long deg = 0, i;
      60     3079378 :   if (!signe(b)) return -1;
      61    11040763 :   for (i = 2; i < lg(b); ++i)
      62     7961352 :     deg = maxss(deg, degpol(gel(b, i)));
      63     3079411 :   return deg;
      64             : }
      65             : 
      66             : /*Lift coefficient of B to constant Flx, to give a FlxY*/
      67             : GEN
      68        2510 : Fly_to_FlxY(GEN B, long sv)
      69             : {
      70        2510 :   long lb=lg(B);
      71             :   long i;
      72        2510 :   GEN b=cgetg(lb,t_POL);
      73        2510 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
      74       65381 :   for (i=2; i<lb; i++)
      75       62876 :     gel(b,i) = Fl_to_Flx(B[i], sv);
      76        2505 :   return FlxX_renormalize(b, lb);
      77             : }
      78             : 
      79             : GEN
      80     2874917 : zxX_to_FlxX(GEN B, ulong p)
      81             : {
      82     2874917 :   long i, lb = lg(B);
      83     2874917 :   GEN b = cgetg(lb,t_POL);
      84     9384175 :   for (i=2; i<lb; i++)
      85     6514479 :     gel(b,i) = zx_to_Flx(gel(B,i), p);
      86     2869696 :   b[1] = B[1]; return FlxX_renormalize(b, lb);
      87             : }
      88             : 
      89             : GEN
      90     2771507 : FlxX_to_ZXX(GEN B)
      91             : {
      92     2771507 :   long i, lb = lg(B);
      93     2771507 :   GEN b = cgetg(lb,t_POL);
      94     8889418 :   for (i=2; i<lb; i++)
      95             :   {
      96     6118719 :     GEN c = gel(B,i);
      97     6118719 :     switch(lgpol(c))
      98             :     {
      99      267559 :       case 0:  c = gen_0; break;
     100      796735 :       case 1:  c = utoi(c[2]); break;
     101     5054502 :       default: c = Flx_to_ZX(c); break;
     102             :     }
     103     6117872 :     gel(b,i) = c;
     104             :   }
     105     2770699 :   b[1] = B[1]; return b;
     106             : }
     107             : 
     108             : /* Note: v is used _only_ for the t_INT. It must match
     109             :  * the variable of any t_POL coefficients. */
     110             : GEN
     111     4692416 : ZXX_to_FlxX(GEN B, ulong p, long v)
     112             : {
     113     4692416 :   long lb=lg(B);
     114             :   long i;
     115     4692416 :   GEN b=cgetg(lb,t_POL);
     116     4692487 :   b[1]=evalsigne(1)|(((ulong)B[1])&VARNBITS);
     117    21555190 :   for (i=2; i<lb; i++)
     118    16863766 :     switch (typ(gel(B,i)))
     119             :     {
     120     7105482 :     case t_INT:
     121     7105482 :       gel(b,i) = Z_to_Flx(gel(B,i), p, evalvarn(v));
     122     7105404 :       break;
     123     9759683 :     case t_POL:
     124     9759683 :       gel(b,i) = ZX_to_Flx(gel(B,i), p);
     125     9758698 :       break;
     126             :     }
     127     4691424 :   return FlxX_renormalize(b, lb);
     128             : }
     129             : 
     130             : GEN
     131           0 : ZXXV_to_FlxXV(GEN x, ulong p, long v)
     132           0 : { pari_APPLY_type(t_VEC, ZXX_to_FlxX(gel(x,i), p, v)) }
     133             : 
     134             : GEN
     135         512 : ZXXT_to_FlxXT(GEN x, ulong p, long v)
     136             : {
     137         512 :   if (typ(x) == t_POL)
     138         491 :     return ZXX_to_FlxX(x, p, v);
     139             :   else
     140          63 :     pari_APPLY_type(t_VEC, ZXXT_to_FlxXT(gel(x,i), p, v))
     141             : }
     142             : 
     143             : GEN
     144      319858 : FlxX_to_FlxC(GEN x, long N, long sv)
     145             : {
     146             :   long i, l;
     147             :   GEN z;
     148      319858 :   l = lg(x)-1; x++;
     149      319858 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     150      319858 :   z = cgetg(N+1,t_COL);
     151     2417645 :   for (i=1; i<l ; i++) gel(z,i) = gel(x,i);
     152     3486844 :   for (   ; i<=N; i++) gel(z,i) = pol0_Flx(sv);
     153      319858 :   return z;
     154             : }
     155             : 
     156             : /* matrix whose entries are given by the coeffs of the polynomial v in
     157             :  * two variables (considered as degree n polynomials) */
     158             : GEN
     159       57625 : FlxX_to_Flm(GEN v, long n)
     160             : {
     161       57625 :   long j, N = lg(v)-1;
     162       57625 :   GEN y = cgetg(N, t_MAT);
     163       57625 :   v++;
     164      198629 :   for (j=1; j<N; j++) gel(y,j) = Flx_to_Flv(gel(v,j), n);
     165       57621 :   return y;
     166             : }
     167             : 
     168             : GEN
     169      375398 : FlxX_to_Flx(GEN f)
     170             : {
     171      375398 :   long i, l = lg(f);
     172      375398 :   GEN V = cgetg(l, t_VECSMALL);
     173      375398 :   V[1] = ((ulong)f[1])&VARNBITS;
     174     3548462 :   for(i=2; i<l; i++)
     175     3173064 :     V[i] = lgpol(gel(f,i)) ? mael(f,i,2): 0L;
     176      375398 :   return V;
     177             : }
     178             : 
     179             : GEN
     180      221464 : Flm_to_FlxX(GEN x, long v,long w)
     181             : {
     182      221464 :   long j, lx = lg(x);
     183      221464 :   GEN y = cgetg(lx+1, t_POL);
     184      221465 :   y[1]=evalsigne(1) | v;
     185      221465 :   y++;
     186      814303 :   for (j=1; j<lx; j++) gel(y,j) = Flv_to_Flx(gel(x,j), w);
     187      221447 :   return FlxX_renormalize(--y, lx+1);
     188             : }
     189             : 
     190             : /* P(X,Y) --> P(Y,X), n is the degree in Y */
     191             : GEN
     192      181764 : FlxX_swap(GEN x, long n, long ws)
     193             : {
     194      181764 :   long j, lx = lg(x), ly = n+3;
     195      181764 :   GEN y = cgetg(ly, t_POL);
     196      181766 :   y[1] = x[1];
     197     1168694 :   for (j=2; j<ly; j++)
     198             :   {
     199             :     long k;
     200      986932 :     GEN p1 = cgetg(lx, t_VECSMALL);
     201      986928 :     p1[1] = ws;
     202    11225495 :     for (k=2; k<lx; k++)
     203    10238567 :       if (j<lg(gel(x,k)))
     204     7199154 :         p1[k] = mael(x,k,j);
     205             :       else
     206     3039413 :         p1[k] = 0;
     207      986928 :     gel(y,j) = Flx_renormalize(p1,lx);
     208             :   }
     209      181762 :   return FlxX_renormalize(y,ly);
     210             : }
     211             : 
     212             : static GEN
     213     4359697 : zxX_to_Kronecker_spec(GEN P, long lp, long n)
     214             : { /* P(X) = sum Pi(Y) * X^i, return P( Y^(2n-1) ) */
     215     4359697 :   long i, j, k, l, N = (n<<1) + 1;
     216     4359697 :   GEN y = cgetg((N-2)*lp + 2, t_VECSMALL) + 2;
     217    28820283 :   for (k=i=0; i<lp; i++)
     218             :   {
     219    28783781 :     GEN c = gel(P,i);
     220    28783781 :     l = lg(c);
     221    28783781 :     if (l-3 >= n)
     222           0 :       pari_err_BUG("zxX_to_Kronecker, P is not reduced mod Q");
     223   168688535 :     for (j=2; j < l; j++) y[k++] = c[j];
     224    28783863 :     if (i == lp-1) break;
     225   219122392 :     for (   ; j < N; j++) y[k++] = 0;
     226             :   }
     227     4359754 :   y -= 2;
     228     4359754 :   y[1] = 0; setlg(y, k+2); return y;
     229             : }
     230             : 
     231             : GEN
     232     3773438 : zxX_to_Kronecker(GEN P, GEN Q)
     233             : {
     234     3773438 :   GEN z = zxX_to_Kronecker_spec(P+2, lg(P)-2, degpol(Q));
     235     3773455 :   z[1] = P[1]; return z;
     236             : }
     237             : 
     238             : GEN
     239      348538 : FlxX_add(GEN x, GEN y, ulong p)
     240             : {
     241             :   long i,lz;
     242             :   GEN z;
     243      348538 :   long lx=lg(x);
     244      348538 :   long ly=lg(y);
     245      348538 :   if (ly>lx) swapspec(x,y, lx,ly);
     246      348538 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
     247     3922261 :   for (i=2; i<ly; i++) gel(z,i) = Flx_add(gel(x,i), gel(y,i), p);
     248     2148285 :   for (   ; i<lx; i++) gel(z,i) = Flx_copy(gel(x,i));
     249      348518 :   return FlxX_renormalize(z, lz);
     250             : }
     251             : 
     252             : GEN
     253         245 : FlxY_Flx_add(GEN y, GEN x, ulong p)
     254             : {
     255         245 :   long i, lz = lg(y);
     256             :   GEN z;
     257         245 :   if (signe(y) == 0) return scalarpol(x, varn(y));
     258         245 :   z = cgetg(lz,t_POL); z[1] = y[1];
     259         245 :   gel(z,2) = Flx_add(gel(y,2), x, p);
     260         245 :   if (lz == 3) z = FlxX_renormalize(z,lz);
     261             :   else
     262        1071 :     for(i=3;i<lz;i++) gel(z,i) = Flx_copy(gel(y,i));
     263         245 :   return z;
     264             : }
     265             : 
     266             : GEN
     267       11662 : FlxY_Flx_sub(GEN y, GEN x, ulong p)
     268             : {
     269       11662 :   long i, lz = lg(y);
     270             :   GEN z;
     271       11662 :   if (signe(y) == 0) return scalarpol(x, varn(y));
     272       11662 :   z = cgetg(lz,t_POL); z[1] = y[1];
     273       11662 :   gel(z,2) = Flx_sub(gel(y,2), x, p);
     274       11662 :   if (lz == 3) z = FlxX_renormalize(z,lz);
     275             :   else
     276       84532 :     for(i=3;i<lz;i++) gel(z,i) = Flx_copy(gel(y,i));
     277       11662 :   return z;
     278             : }
     279             : 
     280             : GEN
     281        2657 : FlxX_neg(GEN x, ulong p)
     282             : {
     283        2657 :   long i, lx=lg(x);
     284        2657 :   GEN z = cgetg(lx, t_POL);
     285        2657 :   z[1]=x[1];
     286       45554 :   for (i=2; i<lx; i++) gel(z,i) = Flx_neg(gel(x,i), p);
     287        2657 :   return z;
     288             : }
     289             : 
     290             : GEN
     291         761 : FlxX_Fl_mul(GEN x, ulong y, ulong p)
     292             : {
     293         761 :   long i, lx=lg(x);
     294         761 :   GEN z = cgetg(lx, t_POL);
     295         761 :   z[1]=x[1];
     296        3667 :   for (i=2; i<lx; i++) gel(z,i) = Flx_Fl_mul(gel(x,i), y, p);
     297         761 :   return FlxX_renormalize(z, lx);
     298             : }
     299             : 
     300             : GEN
     301           0 : FlxX_triple(GEN x, ulong p)
     302             : {
     303           0 :   long i, lx=lg(x);
     304           0 :   GEN z = cgetg(lx, t_POL);
     305           0 :   z[1]=x[1];
     306           0 :   for (i=2; i<lx; i++) gel(z,i) = Flx_triple(gel(x,i), p);
     307           0 :   return FlxX_renormalize(z, lx);
     308             : }
     309             : 
     310             : GEN
     311         761 : FlxX_double(GEN x, ulong p)
     312             : {
     313         761 :   long i, lx=lg(x);
     314         761 :   GEN z = cgetg(lx, t_POL);
     315         761 :   z[1]=x[1];
     316        6088 :   for (i=2; i<lx; i++) gel(z,i) = Flx_double(gel(x,i), p);
     317         761 :   return FlxX_renormalize(z, lx);
     318             : }
     319             : 
     320             : GEN
     321       84664 : FlxX_deriv(GEN z, ulong p)
     322             : {
     323       84664 :   long i,l = lg(z)-1;
     324             :   GEN x;
     325       84664 :   if (l < 2) l = 2;
     326       84664 :   x = cgetg(l, t_POL); x[1] = z[1];
     327      914734 :   for (i=2; i<l; i++) gel(x,i) = Flx_mulu(gel(z,i+1), (ulong) i-1, p);
     328       84659 :   return FlxX_renormalize(x,l);
     329             : }
     330             : 
     331             : GEN
     332           0 : FlxX_translate1(GEN P, long p, long n)
     333             : {
     334             :   GEN Q;
     335           0 :   long i, l, ws, lP = lgpol(P);
     336           0 :   if (!lP) return gcopy(P);
     337           0 :   ws = mael(P,2,1);
     338           0 :   Q = FlxX_swap(P, n, ws);
     339           0 :   l = lg(Q);
     340           0 :   for (i=2; i<l; i++) gel(Q, i) = Flx_translate1(gel(Q, i), p);
     341           0 :   return FlxX_swap(Q, lP, ws);
     342             : }
     343             : 
     344             : GEN
     345           0 : zlxX_translate1(GEN P, long p, long e, long n)
     346             : {
     347             :   GEN Q;
     348           0 :   long i, l, ws, lP = lgpol(P);
     349           0 :   if (!lP) return gcopy(P);
     350           0 :   ws = mael(P,2,1);
     351           0 :   Q = FlxX_swap(P, n, ws);
     352           0 :   l = lg(Q);
     353           0 :   for (i=2; i<l; i++) gel(Q, i) = zlx_translate1(gel(Q, i), p, e);
     354           0 :   return FlxX_swap(Q, lP, ws);
     355             : }
     356             : 
     357             : static GEN
     358      110317 : FlxX_subspec(GEN x, GEN y, ulong p, long lx, long ly)
     359             : {
     360             :   long i,lz;
     361             :   GEN z;
     362             : 
     363      110317 :   if (ly <= lx)
     364             :   {
     365      110317 :     lz = lx+2; z = cgetg(lz, t_POL);
     366     3346614 :     for (i=0; i<ly; i++) gel(z,i+2) = Flx_sub(gel(x,i),gel(y,i),p);
     367      112124 :     for (   ; i<lx; i++) gel(z,i+2) = Flx_copy(gel(x,i));
     368             :   }
     369             :   else
     370             :   {
     371           0 :     lz = ly+2; z = cgetg(lz, t_POL);
     372           0 :     for (i=0; i<lx; i++) gel(z,i+2) = Flx_sub(gel(x,i),gel(y,i),p);
     373           0 :     for (   ; i<ly; i++) gel(z,i+2) = Flx_neg(gel(y,i),p);
     374             :   }
     375      110317 :   z[1] = 0; return FlxX_renormalize(z, lz);
     376             : }
     377             : 
     378             : GEN
     379      623880 : FlxX_sub(GEN x, GEN y, ulong p)
     380             : {
     381             :   long lx,ly,i,lz;
     382             :   GEN z;
     383      623880 :   lx = lg(x); ly = lg(y);
     384      623880 :   lz=maxss(lx,ly);
     385      623880 :   z = cgetg(lz,t_POL);
     386      623879 :   if (lx >= ly)
     387             :   {
     388      109985 :     z[1] = x[1];
     389      635507 :     for (i=2; i<ly; i++) gel(z,i) = Flx_sub(gel(x,i),gel(y,i),p);
     390      388611 :     for (   ; i<lx; i++) gel(z,i) = Flx_copy(gel(x,i));
     391      109985 :     if (lx==ly) z = FlxX_renormalize(z, lz);
     392             :   }
     393             :   else
     394             :   {
     395      513894 :     z[1] = y[1];
     396     1294771 :     for (i=2; i<lx; i++) gel(z,i) = Flx_sub(gel(x,i),gel(y,i),p);
     397     1381459 :     for (   ; i<ly; i++) gel(z,i) = Flx_neg(gel(y,i),p);
     398             :   }
     399      623852 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lz)); z = pol_0(varn(x)); }
     400      623863 :   return z;
     401             : }
     402             : 
     403             : GEN
     404           0 : FlxY_Flx_mul_pre(GEN P, GEN U, ulong p, ulong pi)
     405             : {
     406           0 :   long i, lP = lg(P);
     407           0 :   GEN res = cgetg(lP,t_POL);
     408           0 :   res[1] = P[1];
     409           0 :   for(i=2; i<lP; i++) gel(res,i) = Flx_mul_pre(U,gel(P,i), p, pi);
     410           0 :   return FlxX_renormalize(res, lP);
     411             : }
     412             : 
     413             : GEN
     414           0 : FlxY_Flx_mul(GEN P, GEN U, ulong p)
     415           0 : { return FlxY_Flx_mul_pre(P, U, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     416             : 
     417             : GEN
     418        7500 : FlxY_Flx_div_pre(GEN x, GEN y, ulong p, ulong pi)
     419             : {
     420             :   long i, l;
     421             :   GEN z;
     422        7500 :   if (degpol(y) == 0)
     423             :   {
     424        5556 :     ulong t = uel(y,2);
     425        5556 :     if (t == 1) return x;
     426           0 :     t = Fl_inv(t, p);
     427           0 :     z = cgetg_copy(x, &l); z[1] = x[1];
     428           0 :     for (i=2; i<l; i++) gel(z,i) = Flx_Fl_mul_pre(gel(x,i),t,p,pi);
     429             :   }
     430             :   else
     431             :   {
     432        1944 :     y = Flx_get_red_pre(y, p, pi);
     433        1945 :     z = cgetg_copy(x, &l); z[1] = x[1];
     434        3890 :     for (i=2; i<l; i++) gel(z,i) = Flx_div_pre(gel(x,i),y,p,pi);
     435             :   }
     436        1945 :   return z;
     437             : }
     438             : GEN
     439           0 : FlxY_Flx_div(GEN P, GEN U, ulong p)
     440           0 : { return FlxY_Flx_div_pre(P, U, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     441             : 
     442             : GEN
     443    14274905 : FlxY_evalx_pre(GEN Q, ulong x, ulong p, ulong pi)
     444             : {
     445    14274905 :   long i, lb = lg(Q);
     446             :   GEN z;
     447    14274905 :   z = cgetg(lb,t_VECSMALL); z[1] = evalvarn(varn(Q));
     448   115807970 :   for (i=2; i<lb; i++) z[i] = Flx_eval_pre(gel(Q,i), x, p, pi);
     449    14278209 :   return Flx_renormalize(z, lb);
     450             : }
     451             : GEN
     452         231 : FlxY_evalx(GEN Q, ulong x, ulong p)
     453         231 : { return FlxY_evalx_pre(Q, x, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     454             : 
     455             : GEN
     456           0 : FlxY_Flx_translate(GEN P, GEN c, ulong p)
     457             : {
     458           0 :   pari_sp av = avma;
     459           0 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
     460             :   GEN Q;
     461             :   long i, k, n;
     462             : 
     463           0 :   if (!signe(P) || gequal0(c)) return RgX_copy(P);
     464           0 :   Q = leafcopy(P); n = degpol(P);
     465           0 :   for (i=1; i<=n; i++)
     466             :   {
     467           0 :     for (k=n-i; k<n; k++)
     468           0 :       gel(Q,2+k) = Flx_add(gel(Q,2+k), Flx_mul_pre(gel(Q,2+k+1), c, p, pi), p);
     469           0 :     if (gc_needed(av,2))
     470             :     {
     471           0 :       if(DEBUGMEM>1)
     472           0 :         pari_warn(warnmem,"FlxY_Flx_translate, i = %ld/%ld", i,n);
     473           0 :       Q = gc_GEN(av, Q);
     474             :     }
     475             :   }
     476           0 :   return gc_GEN(av, Q);
     477             : }
     478             : 
     479             : /* allow pi = 0 */
     480             : GEN
     481    10977206 : FlxY_evalx_powers_pre(GEN pol, GEN ypowers, ulong p, ulong pi)
     482             : {
     483    10977206 :   long i, len = lg(pol);
     484    10977206 :   GEN res = cgetg(len, t_VECSMALL);
     485    10973637 :   res[1] = pol[1] & VARNBITS;
     486    37280921 :   for (i = 2; i < len; ++i)
     487    26288469 :     res[i] = Flx_eval_powers_pre(gel(pol, i), ypowers, p, pi);
     488    10992452 :   return Flx_renormalize(res, len);
     489             : }
     490             : 
     491             : /* allow pi = 0 */
     492             : ulong
     493     7367069 : FlxY_eval_powers_pre(GEN pol, GEN ypowers, GEN xpowers, ulong p, ulong pi)
     494             : {
     495     7367069 :   pari_sp av = avma;
     496     7367069 :   GEN t = FlxY_evalx_powers_pre(pol, ypowers, p, pi);
     497     7363176 :   return gc_ulong(av, Flx_eval_powers_pre(t, xpowers, p, pi));
     498             : }
     499             : 
     500             : GEN
     501      136362 : FlxY_FlxqV_evalx_pre(GEN P, GEN x, GEN T, ulong p, ulong pi)
     502             : {
     503      136362 :   long i, lP = lg(P);
     504      136362 :   GEN res = cgetg(lP,t_POL);
     505      136362 :   res[1] = P[1];
     506      930268 :   for(i=2; i<lP; i++)
     507      793906 :     gel(res,i) = Flx_FlxqV_eval_pre(gel(P,i), x, T, p, pi);
     508      136362 :   return FlxX_renormalize(res, lP);
     509             : }
     510             : GEN
     511           0 : FlxY_FlxqV_evalx(GEN P, GEN x, GEN T, ulong p)
     512           0 : { return FlxY_FlxqV_evalx_pre(P, x, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     513             : 
     514             : GEN
     515           0 : FlxY_Flxq_evalx_pre(GEN P, GEN x, GEN T, ulong p, ulong pi)
     516             : {
     517           0 :   pari_sp av = avma;
     518           0 :   long n = brent_kung_optpow(get_Flx_degree(T)-1,lgpol(P),1);
     519           0 :   GEN xp = Flxq_powers_pre(x, n, T, p, pi);
     520           0 :   return gc_upto(av, FlxY_FlxqV_evalx_pre(P, xp, T, p, pi));
     521             : }
     522             : GEN
     523           0 : FlxY_Flxq_evalx(GEN P, GEN x, GEN T, ulong p)
     524           0 : { return FlxY_Flxq_evalx_pre(P, x, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     525             : 
     526             : GEN
     527       71618 : FlxX_shift(GEN a, long n, long vs)
     528             : {
     529       71618 :   long i, l = lg(a);
     530             :   GEN  b;
     531       71618 :   if (l == 2 || !n) return a;
     532       64625 :   l += n;
     533       64625 :   if (n < 0)
     534             :   {
     535       35772 :     if (l <= 2) return pol_0(varn(a));
     536       29402 :     b = cgetg(l, t_POL); b[1] = a[1];
     537       29402 :     a -= n;
     538      612626 :     for (i=2; i<l; i++) gel(b,i) = gel(a,i);
     539             :   } else {
     540       28853 :     b = cgetg(l, t_POL); b[1] = a[1];
     541       28856 :     a -= n; n += 2;
     542      507079 :     for (i=2; i<n; i++) gel(b,i) = pol0_Flx(vs);
     543      365774 :     for (   ; i<l; i++) gel(b,i) = gel(a,i);
     544             :   }
     545       58245 :   return b;
     546             : }
     547             : 
     548             : GEN
     549       13195 : FlxX_blocks(GEN P, long n, long m, long vs)
     550             : {
     551       13195 :   GEN z = cgetg(m+1,t_VEC);
     552       13195 :   long i,j, k=2, l = lg(P);
     553       39585 :   for(i=1; i<=m; i++)
     554             :   {
     555       26390 :     GEN zi = cgetg(n+2,t_POL);
     556       26389 :     zi[1] = P[1];
     557       26389 :     gel(z,i) = zi;
     558      160427 :     for(j=2; j<n+2; j++)
     559      134091 :       gel(zi, j) = k==l ? pol0_Flx(vs) : gel(P,k++);
     560       26336 :     zi = FlxX_renormalize(zi, n+2);
     561             :   }
     562       13195 :   return z;
     563             : }
     564             : 
     565             : static GEN
     566      235489 : FlxX_recipspec(GEN x, long l, long n, long vs)
     567             : {
     568             :   long i;
     569      235489 :   GEN z = cgetg(n+2,t_POL);
     570      235489 :   z[1] = 0; z += 2;
     571     5279911 :   for(i=0; i<l; i++)
     572     5044423 :     gel(z,n-i-1) = Flx_copy(gel(x,i));
     573      242330 :   for(   ; i<n; i++)
     574        6842 :     gel(z,n-i-1) = pol0_Flx(vs);
     575      235488 :   return FlxX_renormalize(z-2,n+2);
     576             : }
     577             : 
     578             : GEN
     579        2432 : FlxX_invLaplace(GEN x, ulong p)
     580             : {
     581        2432 :   long i, d = degpol(x);
     582             :   GEN y;
     583             :   ulong t;
     584        2432 :   if (d <= 1) return gcopy(x);
     585        2425 :   t = Fl_inv(factorial_Fl(d, p), p);
     586        2425 :   y = cgetg(d+3, t_POL);
     587        2425 :   y[1] = x[1];
     588       47537 :   for (i=d; i>=2; i--)
     589             :   {
     590       45112 :     gel(y,i+2) = Flx_Fl_mul(gel(x,i+2), t, p);
     591       45116 :     t = Fl_mul(t, i, p);
     592             :   }
     593        2425 :   gel(y,3) = Flx_copy(gel(x,3));
     594        2425 :   gel(y,2) = Flx_copy(gel(x,2));
     595        2425 :   return FlxX_renormalize(y, d+3);
     596             : }
     597             : 
     598             : GEN
     599        1216 : FlxX_Laplace(GEN x, ulong p)
     600             : {
     601        1216 :   long i, d = degpol(x);
     602        1216 :   ulong t = 1;
     603             :   GEN y;
     604        1216 :   if (d <= 1) return gcopy(x);
     605        1216 :   y = cgetg(d+3, t_POL);
     606        1216 :   y[1] = x[1];
     607        1216 :   gel(y,2) = Flx_copy(gel(x,2));
     608        1216 :   gel(y,3) = Flx_copy(gel(x,3));
     609       23850 :   for (i=2; i<=d; i++)
     610             :   {
     611       22634 :     t = Fl_mul(t, i%p, p);
     612       22634 :     gel(y,i+2) = Flx_Fl_mul(gel(x,i+2), t, p);
     613             :   }
     614        1216 :   return FlxX_renormalize(y, d+3);
     615             : }
     616             : 
     617             : /***********************************************************************/
     618             : /**                                                                   **/
     619             : /**                               FlxXV                               **/
     620             : /**                                                                   **/
     621             : /***********************************************************************/
     622             : 
     623             : GEN
     624           0 : FlxXC_sub(GEN x, GEN y, ulong p)
     625           0 : { pari_APPLY_same(FlxX_sub(gel(x, i), gel(y,i), p)) }
     626             : 
     627             : static GEN
     628      138362 : FlxXV_to_FlxM_lg(GEN x, long m, long n, long sv)
     629             : {
     630             :   long i;
     631      138362 :   GEN y = cgetg(n+1, t_MAT);
     632      458220 :   for (i=1; i<=n; i++) gel(y,i) = FlxX_to_FlxC(gel(x,i), m, sv);
     633      138362 :   return y;
     634             : }
     635             : 
     636             : GEN
     637           0 : FlxXV_to_FlxM(GEN v, long n, long sv)
     638           0 : { return FlxXV_to_FlxM_lg(v, n, lg(v)-1, sv); }
     639             : 
     640             : GEN
     641       12607 : FlxXC_to_ZXXC(GEN x)
     642       62885 : { pari_APPLY_type(t_COL, FlxX_to_ZXX(gel(x,i))) }
     643             : 
     644             : GEN
     645           0 : FlxXM_to_ZXXM(GEN x)
     646           0 : { pari_APPLY_same(FlxXC_to_ZXXC(gel(x,i))) }
     647             : 
     648             : /***********************************************************************/
     649             : /**                                                                   **/
     650             : /**                               FlxqX                               **/
     651             : /**                                                                   **/
     652             : /***********************************************************************/
     653             : 
     654             : static GEN
     655     3614359 : get_FlxqX_red(GEN T, GEN *B)
     656             : {
     657     3614359 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
     658      141827 :   *B = gel(T,1); return gel(T,2);
     659             : }
     660             : 
     661             : GEN
     662      162564 : RgX_to_FlxqX(GEN x, GEN T, ulong p)
     663             : {
     664      162564 :   long i, l = lg(x);
     665      162564 :   GEN z = cgetg(l, t_POL); z[1] = x[1];
     666     2376267 :   for (i = 2; i < l; i++)
     667     2213707 :     gel(z,i) = Rg_to_Flxq(gel(x,i), T, p);
     668      162560 :   return FlxX_renormalize(z, l);
     669             : }
     670             : 
     671             : /* FlxqX are t_POL with Flxq coefficients.
     672             :  * Normally the variable ordering should be respected.*/
     673             : 
     674             : GEN
     675         590 : random_FlxqX(long d1, long v, GEN T, ulong p)
     676             : {
     677         590 :   long dT = get_Flx_degree(T), vT = get_Flx_var(T);
     678         590 :   long i, d = d1+2;
     679         590 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
     680        3124 :   for (i=2; i<d; i++) gel(y,i) = random_Flx(dT, vT, p);
     681         590 :   return FlxX_renormalize(y,d);
     682             : }
     683             : 
     684             : /*Not stack clean*/
     685             : GEN
     686     2356838 : Kronecker_to_FlxqX_pre(GEN z, GEN T, ulong p, ulong pi)
     687             : {
     688     2356838 :   long i,j,lx,l, N = (get_Flx_degree(T)<<1) + 1;
     689     2356837 :   GEN x, t = cgetg(N,t_VECSMALL);
     690     2356834 :   t[1] = get_Flx_var(T);
     691     2356834 :   l = lg(z); lx = (l-2) / (N-2);
     692     2356834 :   x = cgetg(lx+3,t_POL);
     693     2356834 :   x[1] = z[1];
     694    28859944 :   for (i=2; i<lx+2; i++)
     695             :   {
     696   370679391 :     for (j=2; j<N; j++) t[j] = z[j];
     697    26503106 :     z += (N-2);
     698    26503106 :     gel(x,i) = Flx_rem_pre(Flx_renormalize(t,N), T,p,pi);
     699             :   }
     700     2356838 :   N = (l-2) % (N-2) + 2;
     701     7565875 :   for (j=2; j<N; j++) t[j] = z[j];
     702     2356838 :   gel(x,i) = Flx_rem_pre(Flx_renormalize(t,N), T,p,pi);
     703     2356805 :   return FlxX_renormalize(x, i+1);
     704             : }
     705             : GEN
     706           0 : Kronecker_to_FlxqX(GEN z, GEN T, ulong p)
     707           0 : { return Kronecker_to_FlxqX_pre(z, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     708             : 
     709             : GEN
     710     1264504 : FlxqX_red_pre(GEN z, GEN T, ulong p, ulong pi)
     711             : {
     712             :   GEN res;
     713     1264504 :   long i, l = lg(z);
     714     1264504 :   res = cgetg(l,t_POL); res[1] = z[1];
     715    13066969 :   for(i=2;i<l;i++) gel(res,i) = Flx_rem_pre(gel(z,i),T,p,pi);
     716     1264497 :   return FlxX_renormalize(res,l);
     717             : }
     718             : GEN
     719           0 : FlxqX_red(GEN z, GEN T, ulong p)
     720           0 : { return FlxqX_red_pre(z, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     721             : 
     722             : static GEN
     723      293138 : FlxqX_mulspec(GEN x, GEN y, GEN T, ulong p, ulong pi, long lx, long ly)
     724             : {
     725      293138 :   pari_sp av = avma;
     726             :   GEN z,kx,ky;
     727      293138 :   long dT =  get_Flx_degree(T);
     728      293138 :   kx= zxX_to_Kronecker_spec(x,lx,dT);
     729      293138 :   ky= zxX_to_Kronecker_spec(y,ly,dT);
     730      293138 :   z = Flx_mul_pre(ky, kx, p, pi);
     731      293138 :   z = Kronecker_to_FlxqX_pre(z,T,p,pi);
     732      293138 :   return gc_upto(av, z);
     733             : }
     734             : 
     735             : GEN
     736     1709725 : FlxqX_mul_pre(GEN x, GEN y, GEN T, ulong p, ulong pi)
     737             : {
     738     1709725 :   pari_sp av = avma;
     739     1709725 :   GEN z, kx, ky, Tm = get_Flx_mod(T);
     740     1709724 :   kx= zxX_to_Kronecker(x, Tm);
     741     1709749 :   ky= zxX_to_Kronecker(y, Tm);
     742     1709753 :   z = Flx_mul_pre(ky, kx, p, pi);
     743     1709722 :   z = Kronecker_to_FlxqX_pre(z, T, p, pi);
     744     1709694 :   return gc_upto(av, z);
     745             : }
     746             : GEN
     747       63586 : FlxqX_mul(GEN x, GEN y, GEN T, ulong p)
     748       63586 : { return FlxqX_mul_pre(x, y, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     749             : 
     750             : GEN
     751      353990 : FlxqX_sqr_pre(GEN x, GEN T, ulong p, ulong pi)
     752             : {
     753      353990 :   pari_sp av = avma;
     754             :   GEN z,kx;
     755      353990 :   kx= zxX_to_Kronecker(x,get_Flx_mod(T));
     756      353990 :   z = Flx_sqr_pre(kx, p, pi);
     757      353990 :   z = Kronecker_to_FlxqX_pre(z,T,p,pi);
     758      353989 :   return gc_upto(av, z);
     759             : }
     760             : GEN
     761        1218 : FlxqX_sqr(GEN x, GEN T, ulong p)
     762        1218 : { return FlxqX_sqr_pre(x, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     763             : 
     764             : GEN
     765      155141 : FlxqX_Flxq_mul_pre(GEN P, GEN U, GEN T, ulong p, ulong pi)
     766             : {
     767      155141 :   long i, lP = lg(P);
     768      155141 :   GEN res = cgetg(lP,t_POL);
     769      155141 :   res[1] = P[1];
     770      554378 :   for(i=2; i<lP; i++) gel(res,i) = Flxq_mul_pre(U,gel(P,i), T,p,pi);
     771      155139 :   return FlxX_renormalize(res, lP);
     772             : }
     773             : GEN
     774           0 : FlxqX_Flxq_mul(GEN P, GEN U, GEN T, ulong p)
     775           0 : { return FlxqX_Flxq_mul_pre(P, U, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     776             : 
     777             : GEN
     778      664299 : FlxqX_Flxq_mul_to_monic_pre(GEN P, GEN U, GEN T, ulong p, ulong pi)
     779             : {
     780      664299 :   long i, lP = lg(P);
     781      664299 :   GEN res = cgetg(lP,t_POL);
     782      664290 :   res[1] = P[1];
     783     3550732 :   for(i=2; i<lP-1; i++) gel(res,i) = Flxq_mul_pre(U,gel(P,i), T,p,pi);
     784      663822 :   gel(res,lP-1) = pol1_Flx(get_Flx_var(T));
     785      664309 :   return FlxX_renormalize(res, lP);
     786             : }
     787             : GEN
     788           0 : FlxqX_Flxq_mul_to_monic(GEN P, GEN U, GEN T, ulong p)
     789             : {
     790           0 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
     791           0 :   return FlxqX_Flxq_mul_to_monic_pre(P, U, T, p, pi);
     792             : }
     793             : 
     794             : GEN
     795      190188 : FlxqX_normalize_pre(GEN z, GEN T, ulong p, ulong pi)
     796             : {
     797      190188 :   GEN p1 = leading_coeff(z);
     798      190188 :   if (!lgpol(z) || (!degpol(p1) && p1[1] == 1)) return z;
     799      190167 :   return FlxqX_Flxq_mul_to_monic_pre(z, Flxq_inv_pre(p1,T,p,pi), T,p,pi);
     800             : }
     801             : GEN
     802         133 : FlxqX_normalize(GEN z, GEN T, ulong p)
     803         133 : { return FlxqX_normalize_pre(z, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     804             : 
     805             : struct _FlxqXQ {
     806             :   GEN T, S;
     807             :   ulong p, pi;
     808             : };
     809             : 
     810      538529 : static GEN _FlxqX_mul(void *data,GEN a,GEN b)
     811             : {
     812      538529 :   struct _FlxqXQ *d=(struct _FlxqXQ*)data;
     813      538529 :   return FlxqX_mul_pre(a,b,d->T,d->p,d->pi);
     814             : }
     815       10283 : static GEN _FlxqX_sqr(void *data,GEN a)
     816             : {
     817       10283 :   struct _FlxqXQ *d=(struct _FlxqXQ*)data;
     818       10283 :   return FlxqX_sqr_pre(a,d->T,d->p,d->pi);
     819             : }
     820             : 
     821             : GEN
     822       10248 : FlxqX_powu_pre(GEN V, ulong n, GEN T, ulong p, ulong pi)
     823             : {
     824       10248 :   struct _FlxqXQ d; d.p = p; d.pi = pi; d.T = T;
     825       10248 :   return gen_powu(V, n, (void*)&d, &_FlxqX_sqr, &_FlxqX_mul);
     826             : }
     827             : GEN
     828           0 : FlxqX_powu(GEN V, ulong n, GEN T, ulong p)
     829           0 : { return FlxqX_powu_pre(V, n, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
     830             : 
     831             : /* x and y in Z[Y][X]. Assume T irreducible mod p */
     832             : static GEN
     833     3162404 : FlxqX_divrem_basecase(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *pr)
     834             : {
     835     3162404 :   long vx = varn(x), dx = degpol(x), dy = degpol(y), dz, i, j, sx, lr;
     836             :   pari_sp av0, av;
     837             :   GEN z, p1, rem, lead;
     838             : 
     839     3162402 :   if (!signe(y)) pari_err_INV("FlxqX_divrem",y);
     840     3162415 :   if (dx < dy)
     841             :   {
     842       21612 :     if (pr)
     843             :     {
     844       21360 :       av0 = avma; x = FlxqX_red_pre(x, T, p, pi);
     845       21360 :       if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
     846       21360 :       if (pr == ONLY_REM) return x;
     847       21360 :       *pr = x;
     848             :     }
     849       21612 :     return pol_0(vx);
     850             :   }
     851     3140803 :   lead = leading_coeff(y);
     852     3140808 :   if (!dy) /* y is constant */
     853             :   {
     854      330730 :     if (pr && pr != ONLY_DIVIDES)
     855             :     {
     856      326055 :       if (pr == ONLY_REM) return pol_0(vx);
     857      133822 :       *pr = pol_0(vx);
     858             :     }
     859      138497 :     if (Flx_equal1(lead)) return gcopy(x);
     860      134298 :     av0 = avma; x = FlxqX_Flxq_mul_pre(x,Flxq_inv(lead,T,p),T,p,pi);
     861      134300 :     return gc_upto(av0,x);
     862             :   }
     863     2810078 :   av0 = avma; dz = dx-dy;
     864     2810078 :   lead = Flx_equal1(lead)? NULL: gclone(Flxq_inv_pre(lead,T,p,pi));
     865     2810104 :   set_avma(av0);
     866     2810102 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
     867     2810101 :   x += 2; y += 2; z += 2;
     868             : 
     869     2810101 :   p1 = gel(x,dx); av = avma;
     870     2810101 :   gel(z,dz) = lead? gc_upto(av, Flxq_mul_pre(p1,lead, T,p,pi)): gcopy(p1);
     871     6478303 :   for (i=dx-1; i>=dy; i--)
     872             :   {
     873     3668243 :     av = avma; p1 = gel(x,i);
     874    11940148 :     for (j=i-dy+1; j<=i && j<=dz; j++)
     875     8272078 :       p1 = Flx_sub(p1, Flx_mul_pre(gel(z,j),gel(y,i-j),p,pi),p);
     876     3668070 :     if (lead) p1 = Flx_mul_pre(p1, lead,p,pi);
     877     3668070 :     gel(z,i-dy) = gc_leaf(av, Flx_rem_pre(p1,T,p,pi));
     878             :   }
     879     2810060 :   if (!pr) { guncloneNULL(lead); return z-2; }
     880             : 
     881     2616004 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     882     2937126 :   for (sx=0; ; i--)
     883             :   {
     884     2937126 :     p1 = gel(x,i);
     885     8684650 :     for (j=0; j<=i && j<=dz; j++)
     886     5747763 :       p1 = Flx_sub(p1, Flx_mul_pre(gel(z,j),gel(y,i-j),p,pi),p);
     887     2936887 :     p1 = Flx_rem_pre(p1, T,p,pi); if (lgpol(p1)) { sx = 1; break; }
     888      395366 :     if (!i) break;
     889      321076 :     set_avma(av);
     890             :   }
     891     2615909 :   if (pr == ONLY_DIVIDES)
     892             :   {
     893           0 :     guncloneNULL(lead);
     894           0 :     if (sx) return gc_NULL(av0);
     895           0 :     return gc_const((pari_sp)rem, z-2);
     896             :   }
     897     2615909 :   lr=i+3; rem -= lr; av = (pari_sp)rem;
     898     2615909 :   rem[0] = evaltyp(t_POL) | _evallg(lr);
     899     2615909 :   rem[1] = z[-1];
     900     2615909 :   rem += 2; gel(rem,i) = gc_leaf(av, p1);
     901    16341801 :   for (i--; i>=0; i--)
     902             :   {
     903    13725758 :     av = avma; p1 = gel(x,i);
     904    44865566 :     for (j=0; j<=i && j<=dz; j++)
     905    31145061 :       p1 = Flx_sub(p1, Flx_mul_pre(gel(z,j),gel(y,i-j),p,pi), p);
     906    13720505 :     gel(rem,i) = gc_leaf(av, Flx_rem_pre(p1, T,p,pi));
     907             :   }
     908     2616043 :   rem -= 2;
     909     2616043 :   guncloneNULL(lead);
     910     2616061 :   if (!sx) (void)FlxX_renormalize(rem, lr);
     911     2616067 :   if (pr == ONLY_REM) return gc_upto(av0,rem);
     912     1221227 :   *pr = rem; return z-2;
     913             : }
     914             : 
     915             : static GEN
     916        1419 : FlxqX_invBarrett_basecase(GEN T, GEN Q, ulong p, ulong pi)
     917             : {
     918        1419 :   long i, l=lg(T)-1, lr = l-1, k;
     919        1419 :   long sv=Q[1];
     920        1419 :   GEN r=cgetg(lr,t_POL); r[1]=T[1];
     921        1419 :   gel(r,2) = pol1_Flx(sv);
     922       16396 :   for (i=3;i<lr;i++)
     923             :   {
     924       14977 :     pari_sp ltop=avma;
     925       14977 :     GEN u = Flx_neg(gel(T,l-i+2),p);
     926      108758 :     for (k=3;k<i;k++)
     927       93781 :       u = Flx_sub(u, Flxq_mul_pre(gel(T,l-i+k), gel(r,k), Q, p, pi), p);
     928       14977 :     gel(r,i) = gc_upto(ltop, u);
     929             :   }
     930        1419 :   r = FlxX_renormalize(r,lr);
     931        1419 :   return r;
     932             : }
     933             : 
     934             : /* Return new lgpol */
     935             : static long
     936      328043 : FlxX_lgrenormalizespec(GEN x, long lx)
     937             : {
     938             :   long i;
     939      359738 :   for (i = lx-1; i>=0; i--)
     940      359738 :     if (lgpol(gel(x,i))) break;
     941      328043 :   return i+1;
     942             : }
     943             : 
     944             : static GEN
     945        6711 : FlxqX_invBarrett_Newton(GEN S, GEN T, ulong p, ulong pi)
     946             : {
     947        6711 :   pari_sp av = avma;
     948        6711 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
     949        6711 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
     950        6711 :   long dT = get_Flx_degree(T), vT = get_Flx_var(T);
     951        6711 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
     952      273213 :   for (i=0;i<l;i++) gel(x,i) = pol0_Flx(vT);
     953        6711 :   q = FlxX_recipspec(S+2,l+1,l+1,dT);
     954        6711 :   lQ = lgpol(q); q+=2;
     955             :   /* We work on _spec_ FlxX's, all the l[xzq] below are lgpol's */
     956             : 
     957             :   /* initialize */
     958        6711 :   gel(x,0) = Flxq_inv_pre(gel(q,0),T, p, pi);
     959        6711 :   if (lQ>1 && degpol(gel(q,1)) >= dT)
     960           0 :     gel(q,1) = Flx_rem_pre(gel(q,1), T, p, pi);
     961        6711 :   if (lQ>1 && lgpol(gel(q,1)))
     962        5686 :   {
     963        5686 :     GEN u = gel(q, 1);
     964        5686 :     if (!Flx_equal1(gel(x,0)))
     965           7 :       u = Flxq_mul_pre(u, Flxq_sqr_pre(gel(x,0), T,p,pi), T,p,pi);
     966        5686 :     gel(x,1) = Flx_neg(u, p); lx = 2;
     967             :   }
     968             :   else
     969        1025 :     lx = 1;
     970        6711 :   nold = 1;
     971       43278 :   for (; mask > 1; )
     972             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
     973       36567 :     long i, lnew, nnew = nold << 1;
     974             : 
     975       36567 :     if (mask & 1) nnew--;
     976       36567 :     mask >>= 1;
     977             : 
     978       36567 :     lnew = nnew + 1;
     979       36567 :     lq = FlxX_lgrenormalizespec(q, minss(lQ,lnew));
     980       36567 :     z = FlxqX_mulspec(x, q, T,p,pi, lx, lq); /* FIXME: high product */
     981       36567 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
     982       36567 :     z += 2;
     983             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
     984       74746 :     for (i = nold; i < lz; i++) if (lgpol(gel(z,i))) break;
     985       36567 :     nold = nnew;
     986       36567 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
     987             : 
     988             :     /* z + i represents (x*q - 1) / t^i */
     989       35664 :     lz = FlxX_lgrenormalizespec (z+i, lz-i);
     990       35664 :     z = FlxqX_mulspec(x, z+i, T,p,pi, lx, lz); /* FIXME: low product */
     991       35664 :     lz = lgpol(z); z += 2;
     992       35664 :     if (lz > lnew-i) lz = FlxX_lgrenormalizespec(z, lnew-i);
     993             : 
     994       35664 :     lx = lz+ i;
     995       35664 :     y  = x + i; /* x -= z * t^i, in place */
     996      278801 :     for (i = 0; i < lz; i++) gel(y,i) = Flx_neg(gel(z,i), p);
     997             :   }
     998        6711 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
     999        6711 :   return gc_GEN(av, x);
    1000             : }
    1001             : 
    1002             : GEN
    1003        8130 : FlxqX_invBarrett_pre(GEN T, GEN Q, ulong p, ulong pi)
    1004             : {
    1005        8130 :   pari_sp ltop=avma;
    1006        8130 :   long l=lg(T), v = varn(T);
    1007             :   GEN r;
    1008        8130 :   GEN c = gel(T,l-1);
    1009        8130 :   if (l<5) return pol_0(v);
    1010        8130 :   if (l<=FlxqX_INVBARRETT_LIMIT)
    1011             :   {
    1012        1419 :     if (!Flx_equal1(c))
    1013             :     {
    1014           0 :       GEN ci = Flxq_inv_pre(c,Q,p,pi);
    1015           0 :       T = FlxqX_Flxq_mul_pre(T, ci, Q, p, pi);
    1016           0 :       r = FlxqX_invBarrett_basecase(T,Q,p,pi);
    1017           0 :       r = FlxqX_Flxq_mul_pre(r,ci,Q,p,pi);
    1018             :     } else
    1019        1419 :       r = FlxqX_invBarrett_basecase(T,Q,p,pi);
    1020             :   } else
    1021        6711 :     r = FlxqX_invBarrett_Newton(T,Q,p,pi);
    1022        8130 :   return gc_upto(ltop, r);
    1023             : }
    1024             : GEN
    1025          76 : FlxqX_invBarrett(GEN T, GEN Q, ulong p)
    1026          76 : { return FlxqX_invBarrett_pre(T, Q, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1027             : 
    1028             : GEN
    1029      491659 : FlxqX_get_red_pre(GEN S, GEN T, ulong p, ulong pi)
    1030             : {
    1031      491659 :   if (typ(S)==t_POL && lg(S)>FlxqX_BARRETT_LIMIT)
    1032        6674 :     retmkvec2(FlxqX_invBarrett_pre(S, T, p, pi), S);
    1033      484985 :   return S;
    1034             : }
    1035             : GEN
    1036         371 : FlxqX_get_red(GEN S, GEN T, ulong p)
    1037             : {
    1038         371 :   if (typ(S)==t_POL && lg(S)>FlxqX_BARRETT_LIMIT)
    1039          76 :     retmkvec2(FlxqX_invBarrett(S, T, p), S);
    1040         295 :   return S;
    1041             : }
    1042             : 
    1043             : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
    1044             :  *  * and mg is the Barrett inverse of S. */
    1045             : static GEN
    1046      110590 : FlxqX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, ulong p,
    1047             :   ulong pi, GEN *pr)
    1048             : {
    1049             :   GEN q, r;
    1050      110590 :   long lt = degpol(S); /*We discard the leading term*/
    1051             :   long ld, lm, lT, lmg;
    1052      110590 :   ld = l-lt;
    1053      110590 :   lm = minss(ld, lgpol(mg));
    1054      110590 :   lT  = FlxX_lgrenormalizespec(S+2,lt);
    1055      110590 :   lmg = FlxX_lgrenormalizespec(mg+2,lm);
    1056      110590 :   q = FlxX_recipspec(x+lt,ld,ld,0);               /* = rec(x)     lq<=ld*/
    1057      110590 :   q = FlxqX_mulspec(q+2,mg+2,T,p,pi,lgpol(q),lmg); /* = rec(x)*mg lq<=ld+lm*/
    1058      110590 :   q = FlxX_recipspec(q+2,minss(ld,lgpol(q)),ld,0); /* = rec(rec(x)*mg) lq<=ld*/
    1059      110590 :   if (!pr) return q;
    1060      110317 :   r = FlxqX_mulspec(q+2,S+2,T,p,pi,lgpol(q),lT);  /* = q*pol   lr<=ld+lt*/
    1061      110317 :   r = FlxX_subspec(x,r+2,p,lt,minss(lt,lgpol(r)));/* = x - r   lr<=lt */
    1062      110317 :   if (pr == ONLY_REM) return r;
    1063        7688 :   *pr = r; return q;
    1064             : }
    1065             : 
    1066             : static GEN
    1067      103701 : FlxqX_divrem_Barrett(GEN x, GEN mg, GEN S, GEN T, ulong p, ulong pi, GEN *pr)
    1068             : {
    1069      103701 :   GEN q = NULL, r = FlxqX_red_pre(x, T, p, pi);
    1070      103701 :   long l = lgpol(r), lt = degpol(S), lm = 2*lt-1, v = varn(S);
    1071             :   long i;
    1072      103701 :   if (l <= lt)
    1073             :   {
    1074           0 :     if (pr == ONLY_REM) return r;
    1075           0 :     if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
    1076           0 :     if (pr) *pr = r;
    1077           0 :     return pol_0(v);
    1078             :   }
    1079      103701 :   if (lt <= 1)
    1080           0 :     return FlxqX_divrem_basecase(x,S,T,p,pi,pr);
    1081      103701 :   if (pr != ONLY_REM && l>lm)
    1082             :   {
    1083         764 :     long vT = get_Flx_var(T);
    1084         764 :     q = cgetg(l-lt+2, t_POL); q[1] = S[1];
    1085       56948 :     for (i=0;i<l-lt;i++) gel(q+2,i) = pol0_Flx(vT);
    1086             :   }
    1087      110672 :   while (l>lm)
    1088             :   {
    1089        6971 :     GEN zr, zq = FlxqX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,p,pi,&zr);
    1090        6971 :     long lz = lgpol(zr);
    1091        6971 :     if (pr != ONLY_REM)
    1092             :     {
    1093        2582 :       long lq = lgpol(zq);
    1094       50816 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
    1095             :     }
    1096       72514 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
    1097        6971 :     l = l-lm+lz;
    1098             :   }
    1099      103701 :   if (pr == ONLY_REM)
    1100             :   {
    1101      102629 :     if (l > lt)
    1102      102629 :       r = FlxqX_divrem_Barrettspec(r+2,l,mg,S,T,p,pi,ONLY_REM);
    1103             :     else
    1104           0 :       r = FlxX_renormalize(r, l+2);
    1105      102629 :     setvarn(r, v); return r;
    1106             :   }
    1107        1072 :   if (l > lt)
    1108             :   {
    1109         990 :     GEN zq = FlxqX_divrem_Barrettspec(r+2,l,mg,S,T,p,pi,pr? &r: NULL);
    1110         990 :     if (!q) q = zq;
    1111             :     else
    1112             :     {
    1113         682 :       long lq = lgpol(zq);
    1114        6048 :       for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
    1115             :     }
    1116             :   }
    1117          82 :   else if (pr)
    1118          82 :     r = FlxX_renormalize(r, l+2);
    1119        1072 :   setvarn(q, v); q = FlxX_renormalize(q, lg(q));
    1120        1072 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
    1121        1072 :   if (pr) { setvarn(r, v); *pr = r; }
    1122        1072 :   return q;
    1123             : }
    1124             : 
    1125             : GEN
    1126     1576374 : FlxqX_divrem_pre(GEN x, GEN S, GEN T, ulong p, long pi, GEN *pr)
    1127             : {
    1128             :   GEN B, y;
    1129             :   long dy, dx, d;
    1130     1576374 :   if (pr==ONLY_REM) return FlxqX_rem_pre(x, S, T, p, pi);
    1131     1576374 :   y = get_FlxqX_red(S, &B);
    1132     1576363 :   dy = degpol(y); dx = degpol(x); d = dx-dy;
    1133     1576323 :   if (!B && d+3 < FlxqX_DIVREM_BARRETT_LIMIT)
    1134     1575251 :     return FlxqX_divrem_basecase(x,y,T,p,pi,pr);
    1135             :   else
    1136             :   {
    1137        1072 :     pari_sp av = avma;
    1138        1072 :     GEN mg = B? B: FlxqX_invBarrett_pre(y, T, p, pi);
    1139        1072 :     GEN q = FlxqX_divrem_Barrett(x,mg,y,T,p,pi,pr);
    1140        1072 :     if (!q) return gc_NULL(av);
    1141        1072 :     if (!pr || pr==ONLY_DIVIDES) return gc_GEN(av, q);
    1142         799 :     return gc_all(av, 2, &q, pr);
    1143             :   }
    1144             : }
    1145             : GEN
    1146     1073763 : FlxqX_divrem(GEN x, GEN S, GEN T, ulong p, GEN *pr)
    1147             : {
    1148     1073763 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1149     1073763 :   return FlxqX_divrem_pre(x, S, T, p, pi, pr);
    1150             : }
    1151             : 
    1152             : GEN
    1153     2037479 : FlxqX_rem_pre(GEN x, GEN S, GEN T, ulong p, ulong pi)
    1154             : {
    1155     2037479 :   GEN B, y = get_FlxqX_red(S, &B);
    1156     2037481 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    1157     2037477 :   if (d < 0) return FlxqX_red_pre(x, T, p, pi);
    1158     1689736 :   if (!B && d+3 < FlxqX_REM_BARRETT_LIMIT)
    1159     1587107 :     return FlxqX_divrem_basecase(x,y, T, p, pi, ONLY_REM);
    1160             :   else
    1161             :   {
    1162      102629 :     pari_sp av=avma;
    1163      102629 :     GEN mg = B? B: FlxqX_invBarrett_pre(y, T, p, pi);
    1164      102629 :     GEN r = FlxqX_divrem_Barrett(x, mg, y, T, p, pi, ONLY_REM);
    1165      102629 :     return gc_upto(av, r);
    1166             :   }
    1167             : }
    1168             : GEN
    1169        5949 : FlxqX_rem(GEN x, GEN S, GEN T, ulong p)
    1170        5949 : { return FlxqX_rem_pre(x, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1171             : 
    1172             : /* x + y*z mod p */
    1173             : INLINE GEN
    1174      103656 : Flxq_addmul_pre(GEN x, GEN y, GEN z, GEN T, ulong p, ulong pi)
    1175             : {
    1176             :   pari_sp av;
    1177      103656 :   if (!lgpol(y) || !lgpol(z)) return Flx_rem_pre(x, T, p, pi);
    1178      102125 :   if (!lgpol(x)) return Flxq_mul_pre(z, y, T, p, pi);
    1179      102021 :   av = avma;
    1180      102021 :   return gc_upto(av, Flx_add(x, Flxq_mul_pre(y, z, T, p, pi), p));
    1181             : }
    1182             : 
    1183             : GEN
    1184       51828 : FlxqX_div_by_X_x_pre(GEN a, GEN x, GEN T, ulong p, ulong pi, GEN *r)
    1185             : {
    1186       51828 :   long l = lg(a), i;
    1187             :   GEN z;
    1188       51828 :   if (l <= 3)
    1189             :   {
    1190           0 :     if (r) *r = l == 2? pol0_Flx(get_Flx_var(T)): Flx_copy(gel(a,2));
    1191           0 :     return pol_0(varn(a));
    1192             :   }
    1193       51828 :   l--; z = cgetg(l, t_POL); z[1] = a[1];
    1194       51828 :   gel(z, l-1) = gel(a,l);
    1195      155484 :   for (i=l-2; i>1; i--) /* z[i] = a[i+1] + x*z[i+1] */
    1196      103656 :     gel(z, i) = Flxq_addmul_pre(gel(a,i+1), x, gel(z,i+1), T, p, pi);
    1197       51828 :   if (r) *r = Flxq_addmul_pre(gel(a,2), x, gel(z,2), T, p, pi);
    1198       51828 :   return z;
    1199             : }
    1200             : 
    1201             : GEN
    1202       51828 : FlxqX_div_by_X_x(GEN a, GEN x, GEN T, ulong p, GEN *r)
    1203       51828 : { return FlxqX_div_by_X_x_pre(a, x, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p), r); }
    1204             : 
    1205             : static GEN
    1206       13530 : FlxqX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN T, ulong p, ulong pi)
    1207             : {
    1208       13530 :   return FlxX_add(FlxqX_mul_pre(u, x, T, p, pi),
    1209             :                   FlxqX_mul_pre(v, y, T, p, pi), p);
    1210             : }
    1211             : 
    1212             : static GEN
    1213        6626 : FlxqXM_FlxqX_mul2(GEN M, GEN x, GEN y, GEN T, ulong p, ulong pi)
    1214             : {
    1215        6626 :   GEN res = cgetg(3, t_COL);
    1216        6626 :   gel(res, 1) = FlxqX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, T, p, pi);
    1217        6626 :   gel(res, 2) = FlxqX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, T, p, pi);
    1218        6626 :   return res;
    1219             : }
    1220             : 
    1221             : static GEN
    1222        3276 : FlxqXM_mul2(GEN A, GEN B, GEN T, ulong p, ulong pi)
    1223             : {
    1224        3276 :   GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
    1225        3276 :   GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
    1226        3276 :   GEN M1 = FlxqX_mul_pre(FlxX_add(A11,A22, p), FlxX_add(B11,B22, p), T, p, pi);
    1227        3276 :   GEN M2 = FlxqX_mul_pre(FlxX_add(A21,A22, p), B11, T, p, pi);
    1228        3276 :   GEN M3 = FlxqX_mul_pre(A11, FlxX_sub(B12,B22, p), T, p, pi);
    1229        3276 :   GEN M4 = FlxqX_mul_pre(A22, FlxX_sub(B21,B11, p), T, p, pi);
    1230        3276 :   GEN M5 = FlxqX_mul_pre(FlxX_add(A11,A12, p), B22, T, p, pi);
    1231        3276 :   GEN M6 = FlxqX_mul_pre(FlxX_sub(A21,A11, p), FlxX_add(B11,B12, p), T, p, pi);
    1232        3276 :   GEN M7 = FlxqX_mul_pre(FlxX_sub(A12,A22, p), FlxX_add(B21,B22, p), T, p, pi);
    1233        3276 :   GEN T1 = FlxX_add(M1,M4, p), T2 = FlxX_sub(M7,M5, p);
    1234        3276 :   GEN T3 = FlxX_sub(M1,M2, p), T4 = FlxX_add(M3,M6, p);
    1235        3276 :   retmkmat22(FlxX_add(T1,T2, p), FlxX_add(M3,M5, p),
    1236             :              FlxX_add(M2,M4, p), FlxX_add(T3,T4, p));
    1237             : }
    1238             : 
    1239             : /* Return [0,1;1,-q]*M */
    1240             : static GEN
    1241        3276 : FlxqX_FlxqXM_qmul(GEN q, GEN M, GEN T, ulong p, ulong pi)
    1242             : {
    1243        3276 :   GEN u = FlxqX_mul_pre(gcoeff(M,2,1), q, T,p,pi);
    1244        3276 :   GEN v = FlxqX_mul_pre(gcoeff(M,2,2), q, T,p,pi);
    1245        3276 :   retmkmat22(gcoeff(M,2,1), gcoeff(M,2,2),
    1246             :     FlxX_sub(gcoeff(M,1,1), u, p), FlxX_sub(gcoeff(M,1,2), v, p));
    1247             : }
    1248             : 
    1249             : static GEN
    1250          16 : matid2_FlxXM(long v, long sv)
    1251          16 : { retmkmat22(pol1_FlxX(v, sv),pol_0(v),pol_0(v),pol1_FlxX(v, sv)); }
    1252             : 
    1253             : static GEN
    1254           0 : matJ2_FlxXM(long v, long sv)
    1255           0 : { retmkmat22(pol_0(v),pol1_FlxX(v, sv),pol1_FlxX(v, sv),pol_0(v)); }
    1256             : 
    1257             : struct FlxqX_res
    1258             : {
    1259             :    GEN res, lc;
    1260             :    long deg0, deg1, off;
    1261             : };
    1262             : 
    1263             : INLINE void
    1264           0 : FlxqX_halfres_update(long da, long db, long dr, GEN T, ulong p, ulong pi, struct FlxqX_res *res)
    1265             : {
    1266           0 :   if (dr >= 0)
    1267             :   {
    1268           0 :     if (!Flx_equal1(res->lc))
    1269             :     {
    1270           0 :       res->lc  = Flxq_powu_pre(res->lc, da - dr, T, p, pi);
    1271           0 :       res->res = Flxq_mul_pre(res->res, res->lc, T, p, pi);
    1272             :     }
    1273           0 :     if (both_odd(da + res->off, db + res->off))
    1274           0 :       res->res = Flx_neg(res->res, p);
    1275             :   } else
    1276             :   {
    1277           0 :     if (db == 0)
    1278             :     {
    1279           0 :       if (!Flx_equal1(res->lc))
    1280             :       {
    1281           0 :           res->lc  = Flxq_powu_pre(res->lc, da, T, p, pi);
    1282           0 :           res->res = Flxq_mul_pre(res->res, res->lc, T, p, pi);
    1283             :       }
    1284             :     } else
    1285           0 :       res->res = pol0_Flx(get_Flx_var(T));
    1286             :   }
    1287           0 : }
    1288             : 
    1289             : static GEN
    1290        4035 : FlxqX_halfres_basecase(GEN a, GEN b, GEN T, ulong p, ulong pi, GEN *pa, GEN *pb, struct FlxqX_res *res)
    1291             : {
    1292        4035 :   pari_sp av=avma;
    1293             :   GEN u,u1,v,v1, M;
    1294        4035 :   long vx = varn(a), vT = get_Flx_var(T), n = lgpol(a)>>1;
    1295        4035 :   u1 = v = pol_0(vx);
    1296        4035 :   u = v1 = pol1_FlxX(vx, vT);
    1297       22321 :   while (lgpol(b)>n)
    1298             :   {
    1299             :     GEN r, q;
    1300       18286 :     q = FlxqX_divrem(a,b, T, p, &r);
    1301       18286 :     if (res)
    1302             :     {
    1303           0 :       long da = degpol(a), db = degpol(b), dr = degpol(r);
    1304           0 :       res->lc = gel(b,db+2);
    1305           0 :       if (dr >= n)
    1306           0 :         FlxqX_halfres_update(da, db, dr, T, p, pi, res);
    1307             :       else
    1308             :       {
    1309           0 :         res->deg0 = da;
    1310           0 :         res->deg1 = db;
    1311             :       }
    1312             :     }
    1313       18286 :     a = b; b = r; swap(u,u1); swap(v,v1);
    1314       18286 :     u1 = FlxX_sub(u1, FlxqX_mul_pre(u, q, T, p, pi), p);
    1315       18286 :     v1 = FlxX_sub(v1, FlxqX_mul_pre(v, q, T, p, pi), p);
    1316       18286 :     if (gc_needed(av,2))
    1317             :     {
    1318           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_halfgcd (d = %ld)",degpol(b));
    1319           0 :       if (res)
    1320           0 :         (void)gc_all(av, 8, &a,&b,&u1,&v1,&u,&v,&res->res,&res->lc);
    1321             :       else
    1322           0 :         (void)gc_all(av, 6, &a,&b,&u1,&v1,&u,&v);
    1323             :     }
    1324             :   }
    1325        4035 :   M = mkmat22(u,v,u1,v1); *pa = a; *pb = b;
    1326           0 :   return res ? gc_all(av, 5, &M, pa, pb, &res->res, &res->lc)
    1327        4035 :              : gc_all(av, 3, &M, pa, pb);
    1328             : }
    1329             : 
    1330             : static GEN FlxqX_halfres_i(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *a, GEN *b, struct FlxqX_res *res);
    1331             : 
    1332             : static GEN
    1333        3366 : FlxqX_halfres_split(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *a, GEN *b, struct FlxqX_res *res)
    1334             : {
    1335        3366 :   pari_sp av = avma;
    1336             :   GEN Q, R, S, V1, V2;
    1337             :   GEN x1, y1, r, q;
    1338        3366 :   long l = lgpol(x), n = l>>1, k, vT = get_Flx_var(T);
    1339        3366 :   if (lgpol(y) <= n)
    1340          16 :     { *a = RgX_copy(x); *b = RgX_copy(y); return matid2_FlxXM(varn(x), vT); }
    1341        3350 :   if (res)
    1342             :   {
    1343           0 :      res->lc = leading_coeff(y);
    1344           0 :      res->deg0 -= n;
    1345           0 :      res->deg1 -= n;
    1346           0 :      res->off += n;
    1347             :   }
    1348        3350 :   R = FlxqX_halfres_i(FlxX_shift(x,-n, vT),FlxX_shift(y,-n, vT), T, p, pi, a, b, res);
    1349        3350 :   if (res)
    1350             :   {
    1351           0 :     res->off -= n;
    1352           0 :     res->deg0 += n;
    1353           0 :     res->deg1 += n;
    1354             :   }
    1355        3350 :   V1 = FlxqXM_FlxqX_mul2(R, Flxn_red(x,n), Flxn_red(y,n), T, p, pi);
    1356        3350 :   x1 = FlxX_add(FlxX_shift(*a,n,vT), gel(V1,1), p);
    1357        3350 :   y1 = FlxX_add(FlxX_shift(*b,n,vT), gel(V1,2), p);
    1358        3350 :   if (lgpol(y1) <= n)
    1359             :   {
    1360          74 :     *a = x1; *b = y1;
    1361           0 :     return res ? gc_all(av, 5, &R, a, b, &res->res, &res->lc)
    1362          74 :                : gc_all(av, 3, &R, a, b);
    1363             :   }
    1364        3276 :   k = 2*n-degpol(y1);
    1365        3276 :   q = FlxqX_divrem(x1, y1, T, p, &r);
    1366        3276 :   if (res)
    1367             :   {
    1368           0 :     long dx1 = degpol(x1), dy1 = degpol(y1), dr = degpol(r);
    1369           0 :     if (dy1 < degpol(y))
    1370           0 :       FlxqX_halfres_update(res->deg0, res->deg1, dy1, T, p, pi, res);
    1371           0 :     res->lc = leading_coeff(y1);
    1372           0 :     res->deg0 = dx1;
    1373           0 :     res->deg1 = dy1;
    1374           0 :     if (dr >= n)
    1375             :     {
    1376           0 :       FlxqX_halfres_update(dx1, dy1, dr, T, p, pi, res);
    1377           0 :       res->deg0 = dy1;
    1378           0 :       res->deg1 = dr;
    1379             :     }
    1380           0 :     res->deg0 -= k;
    1381           0 :     res->deg1 -= k;
    1382           0 :     res->off += k;
    1383             :   }
    1384        3276 :   S = FlxqX_halfres_i(FlxX_shift(y1,-k, vT), FlxX_shift(r,-k, vT), T, p, pi, a, b, res);
    1385        3276 :   if (res)
    1386             :   {
    1387           0 :     res->deg0 += k;
    1388           0 :     res->deg1 += k;
    1389           0 :     res->off -= k;
    1390             :   }
    1391        3276 :   Q = FlxqXM_mul2(S, FlxqX_FlxqXM_qmul(q, R, T, p, pi), T, p, pi);
    1392        3276 :   V2 = FlxqXM_FlxqX_mul2(S, FlxXn_red(y1,k), FlxXn_red(r,k), T, p, pi);
    1393        3276 :   *a = FlxX_add(FlxX_shift(*a,k,vT), gel(V2,1), p);
    1394        3276 :   *b = FlxX_add(FlxX_shift(*b,k,vT), gel(V2,2), p);
    1395           0 :   return res ? gc_all(av, 5, &Q, a, b, &res->res, &res->lc)
    1396        3276 :              : gc_all(av, 3, &Q, a, b);
    1397             : }
    1398             : 
    1399             : static GEN
    1400        7401 : FlxqX_halfres_i(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *a, GEN *b, struct FlxqX_res *res)
    1401             : {
    1402        7401 :   if (lgpol(x) < FlxqX_HALFGCD_LIMIT)
    1403        4035 :     return FlxqX_halfres_basecase(x, y, T, p, pi, a, b, res);
    1404        3366 :   return FlxqX_halfres_split(x, y, T, p, pi, a, b, res);
    1405             : }
    1406             : 
    1407             : static GEN
    1408         775 : FlxqX_halfgcd_all_i(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *pa, GEN *pb)
    1409             : {
    1410             :   GEN a, b;
    1411         775 :   GEN R = FlxqX_halfres_i(x, y, T, p, pi, &a, &b, NULL);
    1412         775 :   if (pa) *pa = a;
    1413         775 :   if (pb) *pb = b;
    1414         775 :   return R;
    1415             : }
    1416             : 
    1417             : /* Return M in GL_2(Fp[X]/(T)[Y]) such that:
    1418             : if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
    1419             : */
    1420             : 
    1421             : GEN
    1422         775 : FlxqX_halfgcd_all_pre(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *a, GEN *b)
    1423             : {
    1424         775 :   pari_sp av = avma;
    1425             :   GEN R,q,r;
    1426         775 :   if (!signe(x))
    1427             :   {
    1428           0 :     if (a) *a = RgX_copy(y);
    1429           0 :     if (b) *b = RgX_copy(x);
    1430           0 :     return matJ2_FlxXM(varn(x),get_Flx_var(T));
    1431             :   }
    1432         775 :   if (degpol(y)<degpol(x)) return FlxqX_halfgcd_all_i(x, y, T, p, pi, a, b);
    1433         180 :   q = FlxqX_divrem_pre(y, x, T, p, pi, &r);
    1434         180 :   R = FlxqX_halfgcd_all_i(x, r, T, p, pi, a, b);
    1435         180 :   gcoeff(R,1,1) = FlxX_sub(gcoeff(R,1,1),
    1436         180 :                            FlxqX_mul_pre(q, gcoeff(R,1,2), T, p, pi), p);
    1437         180 :   gcoeff(R,2,1) = FlxX_sub(gcoeff(R,2,1),
    1438         180 :                            FlxqX_mul_pre(q, gcoeff(R,2,2), T, p, pi), p);
    1439         180 :   return !a && b ? gc_all(av, 2, &R, b): gc_all(av, 1+!!a+!!b, &R, a, b);
    1440             : }
    1441             : GEN
    1442           7 : FlxqX_halfgcd_all(GEN x, GEN y, GEN T, ulong p, GEN *a, GEN *b)
    1443           7 : { return FlxqX_halfgcd_all_pre(x, y, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p), a, b); }
    1444             : 
    1445             : GEN
    1446         253 : FlxqX_halfgcd_pre(GEN x, GEN y, GEN T, ulong p, ulong pi)
    1447         253 : { return FlxqX_halfgcd_all_pre(x, y, T, p, pi, NULL, NULL); }
    1448             : 
    1449             : GEN
    1450           0 : FlxqX_halfgcd(GEN x, GEN y, GEN T, ulong p)
    1451           0 : { return FlxqX_halfgcd_pre(x, y, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1452             : 
    1453             : static GEN
    1454      166770 : FlxqX_gcd_basecase(GEN a, GEN b, GEN T, ulong p, ulong pi)
    1455             : {
    1456      166770 :   pari_sp av = avma, av0=avma;
    1457     1076592 :   while (signe(b))
    1458             :   {
    1459             :     GEN c;
    1460      909822 :     if (gc_needed(av0,2))
    1461             :     {
    1462           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_gcd (d = %ld)",degpol(b));
    1463           0 :       (void)gc_all(av0,2, &a,&b);
    1464             :     }
    1465      909822 :     av = avma; c = FlxqX_rem_pre(a, b, T, p, pi); a=b; b=c;
    1466             :   }
    1467      166770 :   return gc_const(av, a);
    1468             : }
    1469             : 
    1470             : GEN
    1471      175808 : FlxqX_gcd_pre(GEN x, GEN y, GEN T, ulong p, ulong pi)
    1472             : {
    1473      175808 :   pari_sp av = avma;
    1474      175808 :   x = FlxqX_red_pre(x, T, p, pi);
    1475      175808 :   y = FlxqX_red_pre(y, T, p, pi);
    1476      175808 :   if (!signe(x)) return gc_upto(av, y);
    1477      167146 :   while (lgpol(y)>=FlxqX_GCD_LIMIT)
    1478             :   {
    1479         376 :     if (lgpol(y)<=(lgpol(x)>>1))
    1480             :     {
    1481           0 :       GEN r = FlxqX_rem_pre(x, y, T, p, pi);
    1482           0 :       x = y; y = r;
    1483             :     }
    1484         376 :     (void) FlxqX_halfgcd_all_pre(x,y, T, p, pi, &x, &y);
    1485         376 :     if (gc_needed(av,2))
    1486             :     {
    1487           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_gcd (y = %ld)",degpol(y));
    1488           0 :       (void)gc_all(av,2,&x,&y);
    1489             :     }
    1490             :   }
    1491      166770 :   return gc_upto(av, FlxqX_gcd_basecase(x, y, T, p, pi));
    1492             : }
    1493             : GEN
    1494       23458 : FlxqX_gcd(GEN x, GEN y, GEN T, ulong p)
    1495       23458 : { return FlxqX_gcd_pre(x, y, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1496             : 
    1497             : static GEN
    1498      133829 : FlxqX_extgcd_basecase(GEN a, GEN b, GEN T, ulong p,ulong pi, GEN *ptu, GEN *ptv)
    1499             : {
    1500      133829 :   pari_sp av=avma;
    1501             :   GEN u,v,d,d1,v1;
    1502      133829 :   long vx = varn(a);
    1503      133829 :   d = a; d1 = b;
    1504      133829 :   v = pol_0(vx); v1 = pol1_FlxX(vx, get_Flx_var(T));
    1505      470920 :   while (signe(d1))
    1506             :   {
    1507      337095 :     GEN r, q = FlxqX_divrem_pre(d, d1, T, p, pi, &r);
    1508      337102 :     v = FlxX_sub(v, FlxqX_mul_pre(q,v1,T, p, pi),p);
    1509      337088 :     u=v; v=v1; v1=u;
    1510      337088 :     u=r; d=d1; d1=u;
    1511      337088 :     if (gc_needed(av,2))
    1512             :     {
    1513           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_extgcd (d = %ld)",degpol(d));
    1514           0 :       (void)gc_all(av,5, &d,&d1,&u,&v,&v1);
    1515             :     }
    1516             :   }
    1517      133825 :   if (ptu)
    1518      133812 :     *ptu = FlxqX_div_pre(FlxX_sub(d,FlxqX_mul_pre(b,v, T,p,pi), p), a, T,p,pi);
    1519      133826 :   *ptv = v; return d;
    1520             : }
    1521             : 
    1522             : static GEN
    1523         130 : FlxqX_extgcd_halfgcd(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *ptu, GEN *ptv)
    1524             : {
    1525             :   GEN u,v;
    1526         130 :   GEN V = cgetg(expu(lgpol(y))+2,t_VEC);
    1527         130 :   long i, n = 0, vs = varn(x), vT = get_Flx_var(T);
    1528         269 :   while (lgpol(y) >= FlxqX_EXTGCD_LIMIT)
    1529             :   {
    1530         139 :     if (lgpol(y)<=(lgpol(x)>>1))
    1531             :     {
    1532           0 :       GEN r, q = FlxqX_divrem_pre(x, y, T, p, pi, &r);
    1533           0 :       x = y; y = r;
    1534           0 :       gel(V,++n) = mkmat22(pol_0(vs),pol1_FlxX(vs,vT),pol1_FlxX(vs,vT),FlxX_neg(q,p));
    1535             :     } else
    1536         139 :       gel(V,++n) = FlxqX_halfgcd_all_pre(x, y, T, p, pi, &x, &y);
    1537             :   }
    1538         130 :   y = FlxqX_extgcd_basecase(x,y, T, p, pi, &u,&v);
    1539         139 :   for (i = n; i>1; i--)
    1540             :   {
    1541           9 :     GEN R = gel(V,i);
    1542           9 :     GEN u1 = FlxqX_addmulmul(u, v, gcoeff(R,1,1), gcoeff(R,2,1), T, p, pi);
    1543           9 :     GEN v1 = FlxqX_addmulmul(u, v, gcoeff(R,1,2), gcoeff(R,2,2), T, p, pi);
    1544           9 :     u = u1; v = v1;
    1545             :   }
    1546             :   {
    1547         130 :     GEN R = gel(V,1);
    1548         130 :     if (ptu)
    1549         130 :       *ptu = FlxqX_addmulmul(u, v, gcoeff(R,1,1), gcoeff(R,2,1), T, p, pi);
    1550         130 :     *ptv   = FlxqX_addmulmul(u, v, gcoeff(R,1,2), gcoeff(R,2,2), T, p, pi);
    1551             :   }
    1552         130 :   return y;
    1553             : }
    1554             : 
    1555             : /* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
    1556             :  * ux + vy = gcd (mod T,p) */
    1557             : GEN
    1558      133827 : FlxqX_extgcd_pre(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *ptu, GEN *ptv)
    1559             : {
    1560      133827 :   pari_sp av = avma;
    1561             :   GEN d;
    1562      133827 :   x = FlxqX_red_pre(x, T, p, pi);
    1563      133826 :   y = FlxqX_red_pre(y, T, p, pi);
    1564      133828 :   if (lgpol(y)>=FlxqX_EXTGCD_LIMIT)
    1565         130 :     d = FlxqX_extgcd_halfgcd(x, y, T, p, pi, ptu, ptv);
    1566             :   else
    1567      133698 :     d = FlxqX_extgcd_basecase(x, y, T, p, pi, ptu, ptv);
    1568      133826 :   return gc_all(av, ptu?3:2, &d, ptv, ptu);
    1569             : }
    1570             : GEN
    1571      133813 : FlxqX_extgcd(GEN x, GEN y, GEN T, ulong p, GEN *ptu, GEN *ptv)
    1572             : {
    1573      133813 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1574      133813 :   return FlxqX_extgcd_pre(x, y, T, p, pi, ptu, ptv);
    1575             : }
    1576             : 
    1577             : static GEN
    1578      378263 : FlxqX_saferem(GEN P, GEN Q, GEN T, ulong p, ulong pi)
    1579             : {
    1580      378263 :   GEN U = Flxq_invsafe_pre(leading_coeff(Q), T, p, pi);
    1581      378260 :   if (!U) return NULL;
    1582      378260 :   Q = FlxqX_Flxq_mul_to_monic_pre(Q,U,T,p,pi);
    1583      378273 :   return FlxqX_rem_pre(P,Q,T,p,pi);
    1584             : }
    1585             : 
    1586             : GEN
    1587           0 : FlxqX_eval(GEN x, GEN y, GEN T, ulong p)
    1588             : {
    1589             :   pari_sp av;
    1590             :   GEN p1, r;
    1591           0 :   long j, i=lg(x)-1;
    1592           0 :   if (i<=2)
    1593           0 :     return (i==2)? gcopy(gel(x,2)): pol0_Flx(get_Flx_var(T));
    1594           0 :   av=avma; p1=gel(x,i);
    1595             :   /* specific attention to sparse polynomials (see poleval)*/
    1596             :   /*You've guessed it! It's a copy-paste(tm)*/
    1597           0 :   for (i--; i>=2; i=j-1)
    1598             :   {
    1599           0 :     for (j=i; lg(gel(x,j))==1; j--)
    1600           0 :       if (j==2)
    1601             :       {
    1602           0 :         if (i!=j) y = Flxq_powu(y, i-j+1, T, p);
    1603           0 :         return gc_upto(av, Flxq_mul(p1,y, T, p));
    1604             :       }
    1605           0 :     r = (i==j)? y: Flxq_powu(y, i-j+1, T, p);
    1606           0 :     p1 = Flx_add(Flxq_mul(p1,r,T,p), gel(x,j), p);
    1607             :   }
    1608           0 :   return gc_upto(av, p1);
    1609             : }
    1610             : 
    1611             : GEN
    1612       95876 : FlxqX_safegcd(GEN P, GEN Q, GEN T, ulong p)
    1613             : {
    1614       95876 :   pari_sp av = avma;
    1615             :   ulong pi;
    1616             :   GEN U;
    1617       95876 :   if (!signe(P)) return gcopy(Q);
    1618       95876 :   if (!signe(Q)) return gcopy(P);
    1619       95876 :   pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1620       95876 :   T = Flx_get_red_pre(T,p,pi);
    1621             :   for(;;)
    1622             :   {
    1623      324261 :     P = FlxqX_saferem(P,Q,T,p,pi);
    1624      324262 :     if (!P) return gc_NULL(av);
    1625      324262 :     if (!signe(P)) break;
    1626      228385 :     if (gc_needed(av, 1))
    1627             :     {
    1628           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_safegcd");
    1629           0 :       (void)gc_all(av, 2, &P,&Q);
    1630             :     }
    1631      228385 :     swap(P, Q);
    1632             :   }
    1633       95877 :   U = Flxq_invsafe_pre(leading_coeff(Q), T, p, pi);
    1634       95877 :   if (!U) return gc_NULL(av);
    1635       95877 :   Q = FlxqX_Flxq_mul_to_monic_pre(Q,U,T,p,pi);
    1636       95877 :   return gc_upto(av, Q);
    1637             : }
    1638             : 
    1639             : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
    1640             : GEN
    1641       11010 : FlxqX_saferesultant(GEN a, GEN b, GEN T, ulong p)
    1642             : {
    1643       11010 :   long vT = get_Flx_var(T), da,db,dc;
    1644             :   ulong pi;
    1645             :   pari_sp av;
    1646       11010 :   GEN c,lb, res = pol1_Flx(vT);
    1647             : 
    1648       11010 :   if (!signe(a) || !signe(b)) return pol0_Flx(vT);
    1649             : 
    1650       11010 :   da = degpol(a);
    1651       11010 :   db = degpol(b);
    1652       11010 :   if (db > da)
    1653             :   {
    1654           0 :     swapspec(a,b, da,db);
    1655           0 :     if (both_odd(da,db)) res = Flx_neg(res, p);
    1656             :   }
    1657       11010 :   if (!da) return pol1_Flx(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
    1658       11010 :   pi = SMALL_ULONG(p)? 0: get_Fl_red(p); av = avma;
    1659       64981 :   while (db)
    1660             :   {
    1661       54000 :     lb = gel(b,db+2);
    1662       54000 :     c = FlxqX_saferem(a,b, T,p,pi);
    1663       54046 :     if (!c) return gc_NULL(av);
    1664       54046 :     a = b; b = c; dc = degpol(c);
    1665       54046 :     if (dc < 0) { set_avma(av); return pol0_Flx(vT); }
    1666             : 
    1667       54032 :     if (both_odd(da,db)) res = Flx_neg(res, p);
    1668       54030 :     if (!Flx_equal1(lb))
    1669       53966 :       res = Flxq_mul_pre(res, Flxq_powu_pre(lb, da - dc, T, p, pi), T, p, pi);
    1670       53971 :     if (gc_needed(av,2))
    1671             :     {
    1672           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_resultant (da = %ld)",da);
    1673           0 :       (void)gc_all(av,3, &a,&b,&res);
    1674             :     }
    1675       53971 :     da = db; /* = degpol(a) */
    1676       53971 :     db = dc; /* = degpol(b) */
    1677             :   }
    1678       10981 :   res = Flxq_mul_pre(res, Flxq_powu_pre(gel(b,2), da, T, p, pi), T, p, pi);
    1679       10992 :   return gc_upto(av, res);
    1680             : }
    1681             : 
    1682             : static GEN
    1683           0 : FlxqX_halfres(GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *a, GEN *b, GEN *r)
    1684             : {
    1685             :   struct FlxqX_res res;
    1686             :   GEN V;
    1687             :   long dB;
    1688             : 
    1689           0 :   res.res  = *r;
    1690           0 :   res.lc   = leading_coeff(y);
    1691           0 :   res.deg0 = degpol(x);
    1692           0 :   res.deg1 = degpol(y);
    1693           0 :   res.off = 0;
    1694           0 :   V = FlxqX_halfres_i(x, y, T, p, pi, a, b, &res);
    1695           0 :   dB = degpol(*b);
    1696           0 :   if (dB < degpol(y))
    1697           0 :     FlxqX_halfres_update(res.deg0, res.deg1, dB, T, p, pi, &res);
    1698           0 :   *r = res.res;
    1699           0 :   return V;
    1700             : }
    1701             : 
    1702             : static GEN
    1703          56 : FlxqX_resultant_basecase(GEN a, GEN b, GEN T, ulong p, ulong pi)
    1704             : {
    1705          56 :   pari_sp av = avma;
    1706          56 :   long vT = get_Flx_var(T), da,db,dc;
    1707          56 :   GEN c,lb, res = pol1_Flx(vT);
    1708             : 
    1709          56 :   if (!signe(a) || !signe(b)) return pol0_Flx(vT);
    1710             : 
    1711          56 :   da = degpol(a);
    1712          56 :   db = degpol(b);
    1713          56 :   if (db > da)
    1714             :   {
    1715           0 :     swapspec(a,b, da,db);
    1716           0 :     if (both_odd(da,db)) res = Flx_neg(res, p);
    1717             :   }
    1718          56 :   if (!da) return pol1_Flx(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
    1719         147 :   while (db)
    1720             :   {
    1721          91 :     lb = gel(b,db+2);
    1722          91 :     c = FlxqX_rem_pre(a,b, T,p,pi);
    1723          91 :     a = b; b = c; dc = degpol(c);
    1724          91 :     if (dc < 0) { set_avma(av); return pol0_Flx(vT); }
    1725             : 
    1726          91 :     if (both_odd(da,db)) res = Flx_neg(res, p);
    1727          91 :     if (!Flx_equal1(lb))
    1728          63 :       res = Flxq_mul_pre(res, Flxq_powu_pre(lb, da - dc, T,p,pi), T,p,pi);
    1729          91 :     if (gc_needed(av,2))
    1730             :     {
    1731           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_resultant (da = %ld)",da);
    1732           0 :       (void)gc_all(av,3, &a,&b,&res);
    1733             :     }
    1734          91 :     da = db; /* = degpol(a) */
    1735          91 :     db = dc; /* = degpol(b) */
    1736             :   }
    1737          56 :   res = Flxq_mul_pre(res, Flxq_powu_pre(gel(b,2), da, T,p,pi), T,p,pi);
    1738          56 :   return gc_upto(av, res);
    1739             : }
    1740             : 
    1741             : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
    1742             : GEN
    1743          56 : FlxqX_resultant_pre(GEN x, GEN y, GEN T, ulong p, ulong pi)
    1744             : {
    1745          56 :   pari_sp av = avma;
    1746          56 :   long dx, dy, vT = get_Flx_var(T);
    1747          56 :   GEN res = pol1_Flx(vT);
    1748          56 :   if (!signe(x) || !signe(y)) return pol0_Flx(vT);
    1749          56 :   dx = degpol(x); dy = degpol(y);
    1750          56 :   if (dx < dy)
    1751             :   {
    1752          21 :     swap(x,y);
    1753          21 :     if (both_odd(dx, dy))
    1754           0 :       res = Flx_neg(res, p);
    1755             :   }
    1756          56 :   while (lgpol(y) >= FlxqX_GCD_LIMIT)
    1757             :   {
    1758           0 :     if (lgpol(y)<=(lgpol(x)>>1))
    1759             :     {
    1760           0 :       GEN r = FlxqX_rem_pre(x, y, T, p, pi);
    1761           0 :       long dx = degpol(x), dy = degpol(y), dr = degpol(r);
    1762           0 :       GEN ly = gel(y,dy+2);
    1763           0 :       if (!Flx_equal1(ly))
    1764           0 :         res = Flxq_mul_pre(res, Flxq_powu_pre(ly, dx - dr, T, p, pi), T, p, pi);
    1765           0 :       if (both_odd(dx, dy))
    1766           0 :         res = Flx_neg(res, p);
    1767           0 :       x = y; y = r;
    1768             :     }
    1769           0 :     (void) FlxqX_halfres(x, y, T, p, pi, &x, &y, &res);
    1770           0 :     if (gc_needed(av,2))
    1771             :     {
    1772           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqX_resultant (y = %ld)",degpol(y));
    1773           0 :       (void)gc_all(av,3,&x,&y,&res);
    1774             :     }
    1775             :   }
    1776          56 :   res = Flxq_mul_pre(res, FlxqX_resultant_basecase(x, y, T, p, pi), T, p, pi);
    1777          56 :   return gc_upto(av, res);
    1778             : }
    1779             : GEN
    1780          56 : FlxqX_resultant(GEN x, GEN y, GEN T, ulong p)
    1781          56 : { return FlxqX_resultant_pre(x, y, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1782             : 
    1783             : /* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
    1784             : GEN
    1785          14 : FlxqX_disc(GEN P, GEN T, ulong p)
    1786             : {
    1787          14 :   pari_sp av = avma;
    1788          14 :   GEN L, dP = FlxX_deriv(P, p), D = FlxqX_resultant(P, dP, T, p);
    1789             :   long dd;
    1790          14 :   if (!lgpol(D)) return pol0_Flx(get_Flx_var(T));
    1791          14 :   dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
    1792          14 :   L = leading_coeff(P);
    1793          14 :   if (dd && !Flx_equal1(L))
    1794             :   {
    1795           0 :     ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1796           0 :     D = (dd == -1)? Flxq_div_pre(D,L,T,p,pi)
    1797           0 :                   : Flxq_mul_pre(D, Flxq_powu_pre(L, dd, T,p,pi), T,p,pi); }
    1798          14 :   if (degpol(P) & 2) D = Flx_neg(D, p);
    1799          14 :   return gc_upto(av, D);
    1800             : }
    1801             : 
    1802             : INLINE GEN
    1803        6080 : FlxXn_recip(GEN x, long n, long v)
    1804        6080 : { return FlxX_recipspec(x+2, minss(lgpol(x), n), n, v); }
    1805             : 
    1806             : GEN
    1807        2432 : FlxqX_Newton_pre(GEN P, long n, GEN T, ulong p, ulong pi)
    1808             : {
    1809        2432 :   pari_sp av = avma;
    1810        2432 :   long d = degpol(P), vT = get_Flx_var(T);
    1811        2432 :   GEN dP = FlxXn_recip(FlxX_deriv(P, p), d, vT);
    1812        2432 :   GEN Q = FlxqXn_mul_pre(FlxqXn_inv_pre(FlxXn_recip(P, d+1, vT), n, T,p,pi),
    1813             :                          dP, n, T, p, pi);
    1814        2432 :   return gc_GEN(av, Q);
    1815             : }
    1816             : GEN
    1817           0 : FlxqX_Newton(GEN P, long n, GEN T, ulong p)
    1818           0 : { return FlxqX_Newton_pre(P, n, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1819             : 
    1820             : GEN
    1821        1216 : FlxqX_fromNewton_pre(GEN P, GEN T, ulong p, ulong pi)
    1822             : {
    1823        1216 :   pari_sp av = avma;
    1824        1216 :   long vT = get_Flx_var(T);
    1825        1216 :   long n = Flx_constant(constant_coeff(P))+1;
    1826        1216 :   GEN z = FlxX_neg(FlxX_shift(P, -1, vT), p);
    1827        1216 :   GEN Q = FlxXn_recip(FlxqXn_expint_pre(z, n, T, p, pi), n, vT);
    1828        1216 :   return gc_GEN(av, Q);
    1829             : }
    1830             : GEN
    1831           0 : FlxqX_fromNewton(GEN P, GEN T, ulong p)
    1832           0 : { return FlxqX_fromNewton_pre(P, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1833             : 
    1834             : GEN
    1835        1216 : FlxqX_composedsum(GEN P, GEN Q, GEN T, ulong p)
    1836             : {
    1837        1216 :   pari_sp av = avma;
    1838        1216 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1839        1216 :   long n = 1+ degpol(P)*degpol(Q);
    1840        1216 :   GEN Pl = FlxX_invLaplace(FlxqX_Newton_pre(P,n, T,p,pi), p);
    1841        1216 :   GEN Ql = FlxX_invLaplace(FlxqX_Newton_pre(Q,n, T,p,pi), p);
    1842        1216 :   GEN L = FlxX_Laplace(FlxqXn_mul_pre(Pl, Ql, n, T,p,pi), p);
    1843        1216 :   GEN R = FlxqX_fromNewton_pre(L, T, p, pi);
    1844        1216 :   GEN lead = Flxq_mul_pre(Flxq_powu_pre(leading_coeff(P),degpol(Q), T,p,pi),
    1845        1216 :                           Flxq_powu_pre(leading_coeff(Q),degpol(P), T,p,pi),
    1846             :                           T, p, pi);
    1847        1216 :   return gc_upto(av, FlxqX_Flxq_mul_pre(R, lead, T, p, pi));
    1848             : }
    1849             : 
    1850             : GEN
    1851      223093 : FlxqXV_prod(GEN V, GEN T, ulong p)
    1852             : {
    1853      223093 :   struct _FlxqXQ d; d.p=p; d.T=T; d.pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1854      223093 :   return gen_product(V, (void*)&d, &_FlxqX_mul);
    1855             : }
    1856             : 
    1857             : static GEN
    1858       32151 : FlxqV_roots_to_deg1(GEN x, GEN T, ulong p, long v)
    1859             : {
    1860       32151 :   long sv = get_Flx_var(T);
    1861      124249 :   pari_APPLY_same(deg1pol_shallow(pol1_Flx(sv),Flx_neg(gel(x,i),p),v))
    1862             : }
    1863             : 
    1864             : GEN
    1865       32151 : FlxqV_roots_to_pol(GEN V, GEN T, ulong p, long v)
    1866             : {
    1867       32151 :   pari_sp ltop = avma;
    1868       32151 :   GEN W = FlxqV_roots_to_deg1(V, T, p, v);
    1869       32151 :   return gc_upto(ltop, FlxqXV_prod(W, T, p));
    1870             : }
    1871             : 
    1872             : /*******************************************************************/
    1873             : /*                                                                 */
    1874             : /*                       (Fl[X]/T(X))[Y] / S(Y)                    */
    1875             : /*                                                                 */
    1876             : /*******************************************************************/
    1877             : 
    1878             : GEN
    1879      470985 : FlxqXQ_mul_pre(GEN x, GEN y, GEN S, GEN T, ulong p, ulong pi)
    1880      470985 : { return FlxqX_rem_pre(FlxqX_mul_pre(x,y,T,p,pi),S,T,p,pi); }
    1881             : GEN
    1882        1947 : FlxqXQ_mul(GEN x, GEN y, GEN S, GEN T, ulong p)
    1883        1947 : { return FlxqXQ_mul_pre(x, y, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1884             : 
    1885             : GEN
    1886      261973 : FlxqXQ_sqr_pre(GEN x, GEN S, GEN T, ulong p, ulong pi)
    1887      261973 : { return FlxqX_rem_pre(FlxqX_sqr_pre(x,T,p,pi),S,T,p,pi); }
    1888             : GEN
    1889           0 : FlxqXQ_sqr(GEN x, GEN S, GEN T, ulong p)
    1890           0 : { return FlxqXQ_sqr_pre(x, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1891             : 
    1892             : GEN
    1893          14 : FlxqXQ_invsafe_pre(GEN x, GEN S, GEN T, ulong p, ulong pi)
    1894             : {
    1895          14 :   GEN V, z = FlxqX_extgcd_pre(get_FlxqX_mod(S), x, T, p, pi, NULL, &V);
    1896          14 :   if (degpol(z)) return NULL;
    1897          14 :   z = Flxq_invsafe_pre(gel(z,2),T,p,pi);
    1898          14 :   if (!z) return NULL;
    1899          14 :   return FlxqX_Flxq_mul_pre(V, z, T, p, pi);
    1900             : }
    1901             : GEN
    1902           0 : FlxqXQ_invsafe(GEN x, GEN S, GEN T, ulong p)
    1903           0 : { return FlxqXQ_invsafe_pre(x, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1904             : 
    1905             : GEN
    1906          14 : FlxqXQ_inv_pre(GEN x, GEN S, GEN T, ulong p, ulong pi)
    1907             : {
    1908          14 :   pari_sp av = avma;
    1909          14 :   GEN U = FlxqXQ_invsafe_pre(x, S, T, p, pi);
    1910          14 :   if (!U) pari_err_INV("FlxqXQ_inv",x);
    1911          14 :   return gc_upto(av, U);
    1912             : }
    1913             : GEN
    1914          14 : FlxqXQ_inv(GEN x, GEN S, GEN T,ulong p)
    1915          14 : { return FlxqXQ_inv_pre(x, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1916             : 
    1917             : GEN
    1918           0 : FlxqXQ_div_pre(GEN x, GEN y, GEN S, GEN T, ulong p, ulong pi)
    1919           0 : { return FlxqXQ_mul_pre(x, FlxqXQ_inv_pre(y,S,T,p,pi),S,T,p,pi); }
    1920             : GEN
    1921           0 : FlxqXQ_div(GEN x, GEN y, GEN S, GEN T, ulong p)
    1922           0 : { return FlxqXQ_div_pre(x, y, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    1923             : 
    1924             : static GEN
    1925           0 : _FlxqX_add(void *data, GEN x, GEN y) {
    1926           0 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1927           0 :   return FlxX_add(x,y, d->p);
    1928             : }
    1929             : static GEN
    1930        5526 : _FlxqX_sub(void *data, GEN x, GEN y) {
    1931        5526 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1932        5526 :   return FlxX_sub(x,y, d->p);
    1933             : }
    1934             : #if 0
    1935             : static GEN
    1936             : _FlxqXQ_cmul(void *data, GEN P, long a, GEN x) {
    1937             :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1938             :   return FlxY_Flx_mul_pre(x,gel(P,a+2), d->p, d->pi);
    1939             : }
    1940             : #endif
    1941             : static GEN
    1942        6044 : _FlxqXQ_red(void *data, GEN x) {
    1943        6044 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1944        6044 :   return FlxqX_red_pre(x, d->T, d->p, d->pi);
    1945             : }
    1946             : static GEN
    1947      179118 : _FlxqXQ_mul(void *data, GEN x, GEN y) {
    1948      179118 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1949      179118 :   return FlxqXQ_mul_pre(x,y, d->S,d->T, d->p, d->pi);
    1950             : }
    1951             : static GEN
    1952      261525 : _FlxqXQ_sqr(void *data, GEN x) {
    1953      261525 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1954      261525 :   return FlxqXQ_sqr_pre(x, d->S,d->T, d->p, d->pi);
    1955             : }
    1956             : 
    1957             : static GEN
    1958      111276 : _FlxqXQ_one(void *data) {
    1959      111276 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1960      111276 :   return pol1_FlxX(get_FlxqX_var(d->S),get_Flx_var(d->T));
    1961             : }
    1962             : 
    1963             : static GEN
    1964         316 : _FlxqXQ_zero(void *data) {
    1965         316 :   struct _FlxqXQ *d = (struct _FlxqXQ*) data;
    1966         316 :   return pol_0(get_FlxqX_var(d->S));
    1967             : }
    1968             : 
    1969             : static struct bb_algebra FlxqXQ_algebra = { _FlxqXQ_red, _FlxqX_add,
    1970             :        _FlxqX_sub, _FlxqXQ_mul, _FlxqXQ_sqr, _FlxqXQ_one, _FlxqXQ_zero };
    1971             : 
    1972             : const struct bb_algebra *
    1973         761 : get_FlxqXQ_algebra(void **E, GEN S, GEN T, ulong p)
    1974             : {
    1975         761 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1976         761 :   GEN z = new_chunk(sizeof(struct _FlxqXQ));
    1977         761 :   struct _FlxqXQ *e = (struct _FlxqXQ *) z;
    1978         761 :   e->T = Flx_get_red_pre(T, p, pi);
    1979         761 :   e->S = FlxqX_get_red_pre(S, e->T, p, pi);
    1980         761 :   e->p = p;
    1981         761 :   e->pi= pi; *E = (void*)e;
    1982         761 :   return &FlxqXQ_algebra;
    1983             : }
    1984             : 
    1985             : static struct bb_algebra FlxqX_algebra = { _FlxqXQ_red, _FlxqX_add,
    1986             :        _FlxqX_sub, _FlxqX_mul, _FlxqX_sqr, _FlxqXQ_one, _FlxqXQ_zero };
    1987             : 
    1988             : const struct bb_algebra *
    1989           0 : get_FlxqX_algebra(void **E, GEN T, ulong p, long v)
    1990             : {
    1991           0 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    1992           0 :   GEN z = new_chunk(sizeof(struct _FlxqXQ));
    1993           0 :   struct _FlxqXQ *e = (struct _FlxqXQ *) z;
    1994           0 :   e->T = Flx_get_red(T, p);
    1995           0 :   e->S = pol_x(v);
    1996           0 :   e->p = p;
    1997           0 :   e->pi= pi; *E = (void*)e;
    1998           0 :   return &FlxqX_algebra;
    1999             : }
    2000             : 
    2001             : /* x over Fq, return lift(x^n) mod S */
    2002             : GEN
    2003          91 : FlxqXQ_pow_pre(GEN x, GEN n, GEN S, GEN T, ulong p, ulong pi)
    2004             : {
    2005          91 :   pari_sp av = avma;
    2006             :   struct _FlxqXQ D;
    2007          91 :   long s = signe(n);
    2008          91 :   if (!s) return pol1_FlxX(get_FlxqX_var(S),get_Flx_var(T));
    2009          91 :   if (s < 0) x = FlxqXQ_inv_pre(x,S,T,p,pi);
    2010          91 :   if (is_pm1(n)) return s < 0 ? x : gcopy(x);
    2011          91 :   if (degpol(x) >= get_FlxqX_degree(S)) x = FlxqX_rem_pre(x,S,T,p,pi);
    2012          91 :   T = Flx_get_red_pre(T, p, pi);
    2013          91 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2014          91 :   D.S = S; D.T = T; D.p = p; D.pi = pi;
    2015          91 :   x = gen_pow_i(x, n, (void*)&D, &_FlxqXQ_sqr, &_FlxqXQ_mul);
    2016          91 :   return gc_GEN(av, x);
    2017             : }
    2018             : GEN
    2019          35 : FlxqXQ_pow(GEN x, GEN n, GEN S, GEN T, ulong p)
    2020          35 : { return FlxqXQ_pow_pre(x, n, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2021             : 
    2022             : /* x over Fq, return lift(x^n) mod S */
    2023             : GEN
    2024       82058 : FlxqXQ_powu_pre(GEN x, ulong n, GEN S, GEN T, ulong p, ulong pi)
    2025             : {
    2026       82058 :   pari_sp av = avma;
    2027             :   struct _FlxqXQ D;
    2028       82058 :   switch(n)
    2029             :   {
    2030           0 :     case 0: return pol1_FlxX(get_FlxqX_var(S),get_Flx_var(T));
    2031        7690 :     case 1: return gcopy(x);
    2032         448 :     case 2: return FlxqXQ_sqr_pre(x, S, T, p, pi);
    2033             :   }
    2034       73920 :   T = Flx_get_red_pre(T, p, pi);
    2035       73920 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2036       73920 :   D.S = S; D.T = T; D.p = p; D.pi = pi;
    2037       73920 :   x = gen_powu_i(x, n, (void*)&D, &_FlxqXQ_sqr, &_FlxqXQ_mul);
    2038       73920 :   return gc_GEN(av, x);
    2039             : }
    2040             : GEN
    2041           0 : FlxqXQ_powu(GEN x, ulong n, GEN S, GEN T, ulong p)
    2042           0 : { return FlxqXQ_powu_pre(x, n, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2043             : 
    2044             : GEN
    2045      108241 : FlxqXQ_powers_pre(GEN x, long l, GEN S, GEN T, ulong p, ulong pi)
    2046             : {
    2047             :   struct _FlxqXQ D;
    2048      108241 :   int use_sqr = 2*degpol(x) >= get_FlxqX_degree(S);
    2049      108241 :   T = Flx_get_red_pre(T, p, pi);
    2050      108241 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2051      108241 :   D.S = S; D.T = T; D.p = p; D.pi = pi;
    2052      108241 :   return gen_powers(x, l, use_sqr, (void*)&D, &_FlxqXQ_sqr, &_FlxqXQ_mul,&_FlxqXQ_one);
    2053             : }
    2054             : GEN
    2055           0 : FlxqXQ_powers(GEN x, long l, GEN S, GEN T, ulong p)
    2056           0 : { return FlxqXQ_powers_pre(x, l, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2057             : 
    2058             : /* Let v a linear form, return the linear form z->v(tau*z)
    2059             :    that is, v*(M_tau) */
    2060             : static GEN
    2061         506 : FlxqXQ_transmul_init(GEN tau, GEN S, GEN T, ulong p, ulong pi)
    2062             : {
    2063             :   GEN bht;
    2064         506 :   GEN h, Sp = get_FlxqX_red(S, &h);
    2065         506 :   long n = degpol(Sp), vS = varn(Sp), vT = get_Flx_var(T);
    2066         506 :   GEN ft = FlxX_recipspec(Sp+2, n+1, n+1, vT);
    2067         506 :   GEN bt = FlxX_recipspec(tau+2, lgpol(tau), n, vT);
    2068         506 :   setvarn(ft, vS); setvarn(bt, vS);
    2069         506 :   if (h)
    2070           0 :     bht = FlxqXn_mul_pre(bt, h, n-1, T, p, pi);
    2071             :   else
    2072             :   {
    2073         506 :     GEN bh = FlxqX_div_pre(FlxX_shift(tau, n-1, vT), S, T, p, pi);
    2074         506 :     bht = FlxX_recipspec(bh+2, lgpol(bh), n-1, vT);
    2075         506 :     setvarn(bht, vS);
    2076             :   }
    2077         506 :   return mkvec3(bt, bht, ft);
    2078             : }
    2079             : 
    2080             : static GEN
    2081        1071 : FlxqXQ_transmul(GEN tau, GEN a, long n, GEN T, ulong p, ulong pi)
    2082             : {
    2083        1071 :   pari_sp ltop = avma;
    2084             :   GEN t1, t2, t3, vec;
    2085        1071 :   GEN bt = gel(tau, 1), bht = gel(tau, 2), ft = gel(tau, 3);
    2086        1071 :   long vT = get_Flx_var(T);
    2087        1071 :   if (signe(a)==0) return pol_0(varn(a));
    2088        1061 :   t2 = FlxX_shift(FlxqX_mul_pre(bt, a, T, p, pi),1-n,vT);
    2089        1061 :   if (signe(bht)==0) return gc_GEN(ltop, t2);
    2090         767 :   t1 = FlxX_shift(FlxqX_mul_pre(ft, a, T, p, pi),-n,vT);
    2091         767 :   t3 = FlxqXn_mul_pre(t1, bht, n-1, T, p, pi);
    2092         767 :   vec = FlxX_sub(t2, FlxX_shift(t3, 1, vT), p);
    2093         767 :   return gc_upto(ltop, vec);
    2094             : }
    2095             : 
    2096             : static GEN
    2097         253 : polxn_FlxX(long n, long v, long vT)
    2098             : {
    2099         253 :   long i, a = n+2;
    2100         253 :   GEN p = cgetg(a+1, t_POL);
    2101         253 :   p[1] = evalsigne(1)|evalvarn(v);
    2102        2171 :   for (i = 2; i < a; i++) gel(p,i) = pol0_Flx(vT);
    2103         253 :   gel(p,a) = pol1_Flx(vT); return p;
    2104             : }
    2105             : 
    2106             : GEN
    2107         224 : FlxqXQ_minpoly_pre(GEN x, GEN S, GEN T, ulong p, ulong pi)
    2108             : {
    2109         224 :   pari_sp ltop = avma;
    2110             :   long vS, vT, n;
    2111             :   GEN v_x, g, tau;
    2112         224 :   vS = get_FlxqX_var(S);
    2113         224 :   vT = get_Flx_var(T);
    2114         224 :   n = get_FlxqX_degree(S);
    2115         224 :   g = pol1_FlxX(vS,vT);
    2116         224 :   tau = pol1_FlxX(vS,vT);
    2117         224 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2118         224 :   v_x = FlxqXQ_powers_pre(x, usqrt(2*n), S, T, p, pi);
    2119         477 :   while(signe(tau) != 0)
    2120             :   {
    2121             :     long i, j, m, k1;
    2122             :     GEN M, v, tr;
    2123             :     GEN g_prime, c;
    2124         253 :     if (degpol(g) == n) { tau = pol1_FlxX(vS, vT); g = pol1_FlxX(vS, vT); }
    2125         253 :     v = random_FlxqX(n, vS, T, p);
    2126         253 :     tr = FlxqXQ_transmul_init(tau, S, T, p, pi);
    2127         253 :     v = FlxqXQ_transmul(tr, v, n, T, p, pi);
    2128         253 :     m = 2*(n-degpol(g));
    2129         253 :     k1 = usqrt(m);
    2130         253 :     tr = FlxqXQ_transmul_init(gel(v_x,k1+1), S, T, p, pi);
    2131         253 :     c = cgetg(m+2,t_POL);
    2132         253 :     c[1] = evalsigne(1)|evalvarn(vS);
    2133        1071 :     for (i=0; i<m; i+=k1)
    2134             :     {
    2135         818 :       long mj = minss(m-i, k1);
    2136        2736 :       for (j=0; j<mj; j++)
    2137        1918 :         gel(c,m+1-(i+j)) = FlxqX_dotproduct(v, gel(v_x,j+1), T, p);
    2138         818 :       v = FlxqXQ_transmul(tr, v, n, T, p, pi);
    2139             :     }
    2140         253 :     c = FlxX_renormalize(c, m+2);
    2141             :     /* now c contains <v,x^i> , i = 0..m-1  */
    2142         253 :     M = FlxqX_halfgcd_pre(polxn_FlxX(m, vS, vT), c, T, p, pi);
    2143         253 :     g_prime = gmael(M, 2, 2);
    2144         253 :     if (degpol(g_prime) < 1) continue;
    2145         252 :     g = FlxqX_mul_pre(g, g_prime, T, p, pi);
    2146         252 :     tau = FlxqXQ_mul_pre(tau, FlxqX_FlxqXQV_eval_pre(g_prime, v_x, S, T,p,pi),
    2147             :                          S, T, p,pi);
    2148             :   }
    2149         224 :   g = FlxqX_normalize_pre(g,T,p,pi);
    2150         224 :   return gc_GEN(ltop,g);
    2151             : }
    2152             : GEN
    2153          62 : FlxqXQ_minpoly(GEN x, GEN S, GEN T, ulong p)
    2154          62 : { return FlxqXQ_minpoly_pre(x, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2155             : 
    2156             : GEN
    2157           0 : FlxqXQ_matrix_pow(GEN y, long n, long m, GEN S, GEN T, ulong p)
    2158           0 : { return FlxXV_to_FlxM(FlxqXQ_powers(y,m-1,S,T,p), n, get_Flx_var(T)); }
    2159             : 
    2160             : static GEN
    2161      138362 : FlxX_blocks_FlxM(GEN P, long n, long m, long v)
    2162             : {
    2163      138362 :   GEN z = cgetg(m+1,t_MAT);
    2164      138362 :   long i,j, k=2, l = lg(P);
    2165      536339 :   for(i=1; i<=m; i++)
    2166             :   {
    2167      397977 :     GEN zi = cgetg(n+1,t_COL);
    2168      397977 :     gel(z,i) = zi;
    2169     1274305 :     for(j=1; j<=n; j++)
    2170      876328 :       gel(zi, j) = k==l ? pol0_Flx(v) : gel(P,k++);
    2171             :   }
    2172      138362 :   return z;
    2173             : }
    2174             : 
    2175             : GEN
    2176      138362 : FlxqX_FlxqXQV_eval_pre(GEN Q, GEN x, GEN S, GEN T, ulong p, ulong pi)
    2177             : {
    2178      138362 :   pari_sp btop, av = avma;
    2179      138362 :   long v = get_FlxqX_var(S), m = get_FlxqX_degree(S);
    2180      138362 :   long vT = get_Flx_var(T);
    2181      138362 :   long i, l = lg(x)-1, lQ = lgpol(Q), n,  d;
    2182             :   GEN A, B, C, R, g;
    2183      138362 :   if (lQ == 0) return pol_0(v);
    2184      138362 :   if (lQ <= l)
    2185             :   {
    2186       43859 :     n = l;
    2187       43859 :     d = 1;
    2188             :   }
    2189             :   else
    2190             :   {
    2191       94503 :     n = l-1;
    2192       94503 :     d = (lQ+n-1)/n;
    2193             :   }
    2194      138362 :   A = FlxXV_to_FlxM_lg(x, m, n, vT);
    2195      138362 :   B = FlxX_blocks_FlxM(Q, n, d, vT);
    2196      138362 :   C = gc_upto(av, FlxqM_mul(A, B, T, p));
    2197      138362 :   g = gel(x, l);
    2198      138362 :   T = Flx_get_red_pre(T, p, pi);
    2199      138362 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2200      138362 :   btop = avma;
    2201      138362 :   R = FlxV_to_FlxX(gel(C, d), v);
    2202      397977 :   for (i = d-1; i>0; i--)
    2203             :   {
    2204      259615 :     R = FlxX_add(FlxqXQ_mul_pre(R, g, S, T,p,pi), FlxV_to_FlxX(gel(C,i), v), p);
    2205      259615 :     if (gc_needed(btop,1))
    2206           6 :       R = gc_upto(btop, R);
    2207             :   }
    2208      138362 :   return gc_GEN(av, R);
    2209             : }
    2210             : GEN
    2211           0 : FlxqX_FlxqXQV_eval(GEN Q, GEN x, GEN S, GEN T, ulong p)
    2212           0 : { return FlxqX_FlxqXQV_eval_pre(Q,x,S,T,p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2213             : 
    2214             : GEN
    2215       76758 : FlxqX_FlxqXQ_eval_pre(GEN Q, GEN x, GEN S, GEN T, ulong p, ulong pi)
    2216             : {
    2217       76758 :   pari_sp av = avma;
    2218             :   GEN z, V;
    2219       76758 :   long d = degpol(Q), rtd;
    2220       76758 :   if (d < 0) return pol_0(get_FlxqX_var(S));
    2221       76758 :   rtd = (long) sqrt((double)d);
    2222       76758 :   T = Flx_get_red_pre(T, p, pi);
    2223       76758 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2224       76758 :   V = FlxqXQ_powers_pre(x, rtd, S, T, p, pi);
    2225       76758 :   z = FlxqX_FlxqXQV_eval_pre(Q, V, S, T, p, pi);
    2226       76758 :   return gc_upto(av, z);
    2227             : }
    2228             : GEN
    2229           0 : FlxqX_FlxqXQ_eval(GEN Q, GEN x, GEN S, GEN T, ulong p)
    2230           0 : { return FlxqX_FlxqXQ_eval_pre(Q, x, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2231             : 
    2232             : GEN
    2233           0 : FlxqXC_FlxqXQV_eval_pre(GEN x, GEN v, GEN S, GEN T, ulong p, ulong pi)
    2234           0 : { pari_APPLY_type(t_COL, FlxqX_FlxqXQV_eval_pre(gel(x,i), v, S, T, p, pi)) }
    2235             : GEN
    2236           0 : FlxqXC_FlxqXQV_eval(GEN x, GEN v, GEN S, GEN T, ulong p)
    2237           0 : { return FlxqXC_FlxqXQV_eval_pre(x, v, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2238             : 
    2239             : GEN
    2240           0 : FlxqXC_FlxqXQ_eval(GEN x, GEN F, GEN S, GEN T, ulong p)
    2241             : {
    2242           0 :   long d = brent_kung_optpow(get_FlxqX_degree(S)-1,lg(x)-1,1);
    2243           0 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    2244           0 :   GEN Fp = FlxqXQ_powers_pre(F, d, S, T, p, pi);
    2245           0 :   return FlxqXC_FlxqXQV_eval_pre(x, Fp, S, T, p, pi);
    2246             : }
    2247             : 
    2248             : static GEN
    2249       72682 : FlxqXQ_autpow_sqr(void * E, GEN x)
    2250             : {
    2251       72682 :   struct _FlxqXQ *D = (struct _FlxqXQ *)E;
    2252       72682 :   GEN S = D->S, T = D->T;
    2253       72682 :   ulong p = D->p, pi = D->pi;
    2254       72682 :   GEN phi = gel(x,1), S1 = gel(x,2);
    2255       72682 :   long n = brent_kung_optpow(get_Flx_degree(T)-1,lgpol(S1)+1,1);
    2256       72682 :   GEN V = Flxq_powers_pre(phi, n, T, p, pi);
    2257       72682 :   GEN phi2 = Flx_FlxqV_eval_pre(phi, V, T, p, pi);
    2258       72682 :   GEN Sphi = FlxY_FlxqV_evalx_pre(S1, V, T, p, pi);
    2259       72682 :   GEN S2 = FlxqX_FlxqXQ_eval_pre(Sphi, S1, S, T, p, pi);
    2260       72682 :   return mkvec2(phi2, S2);
    2261             : }
    2262             : 
    2263             : static GEN
    2264        3714 : FlxqXQ_autpow_mul(void * E, GEN x, GEN y)
    2265             : {
    2266        3714 :   struct _FlxqXQ *D = (struct _FlxqXQ *)E;
    2267        3714 :   GEN S = D->S, T = D->T;
    2268        3714 :   ulong p = D->p, pi = D->pi;
    2269        3714 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    2270        3714 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    2271        3714 :   long n = brent_kung_optpow(get_Flx_degree(T)-1,lgpol(S1)+1,1);
    2272        3714 :   GEN V = Flxq_powers_pre(phi2, n, T, p, pi);
    2273        3714 :   GEN phi3 = Flx_FlxqV_eval_pre(phi1, V, T, p, pi);
    2274        3714 :   GEN Sphi = FlxY_FlxqV_evalx_pre(S1, V, T, p, pi);
    2275        3714 :   GEN S3 = FlxqX_FlxqXQ_eval_pre(Sphi, S2, S, T, p, pi);
    2276        3714 :   return mkvec2(phi3, S3);
    2277             : }
    2278             : 
    2279             : GEN
    2280       69275 : FlxqXQ_autpow_pre(GEN aut, long n, GEN S, GEN T, ulong p, ulong pi)
    2281             : {
    2282       69275 :   pari_sp av = avma;
    2283             :   struct _FlxqXQ D;
    2284       69275 :   T = Flx_get_red_pre(T, p, pi);
    2285       69275 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2286       69275 :   D.S = S; D.T = T; D.p = p; D.pi = pi;
    2287       69275 :   aut = gen_powu_i(aut,n,&D,FlxqXQ_autpow_sqr,FlxqXQ_autpow_mul);
    2288       69275 :   return gc_GEN(av, aut);
    2289             : }
    2290             : GEN
    2291           0 : FlxqXQ_autpow(GEN aut, long n, GEN S, GEN T, ulong p)
    2292           0 : { return FlxqXQ_autpow_pre(aut, n, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2293             : 
    2294             : static GEN
    2295       29983 : FlxqXQ_autsum_mul(void *E, GEN x, GEN y)
    2296             : {
    2297       29983 :   struct _FlxqXQ *D = (struct _FlxqXQ *)E;
    2298       29983 :   GEN S = D->S, T = D->T;
    2299       29983 :   ulong p = D->p, pi = D->pi;
    2300       29983 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    2301       29983 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    2302       29983 :   long n2 = brent_kung_optpow(get_Flx_degree(T)-1, lgpol(S1)+lgpol(a1)+1,1);
    2303       29983 :   GEN V2 = Flxq_powers_pre(phi2, n2, T, p, pi);
    2304       29983 :   GEN phi3 = Flx_FlxqV_eval_pre(phi1, V2, T, p, pi);
    2305       29983 :   GEN Sphi = FlxY_FlxqV_evalx_pre(S1, V2, T, p, pi);
    2306       29983 :   GEN aphi = FlxY_FlxqV_evalx_pre(a1, V2, T, p, pi);
    2307       29983 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    2308       29983 :   GEN V = FlxqXQ_powers_pre(S2, n, S, T, p, pi);
    2309       29983 :   GEN S3 = FlxqX_FlxqXQV_eval_pre(Sphi, V, S, T, p, pi);
    2310       29983 :   GEN aS = FlxqX_FlxqXQV_eval_pre(aphi, V, S, T, p, pi);
    2311       29983 :   GEN a3 = FlxqXQ_mul_pre(aS, a2, S, T, p, pi);
    2312       29983 :   return mkvec3(phi3, S3, a3);
    2313             : }
    2314             : 
    2315             : static GEN
    2316       18582 : FlxqXQ_autsum_sqr(void * T, GEN x)
    2317       18582 : { return FlxqXQ_autsum_mul(T, x, x); }
    2318             : 
    2319             : GEN
    2320       12125 : FlxqXQ_autsum_pre(GEN aut, long n, GEN S, GEN T, ulong p, ulong pi)
    2321             : {
    2322       12125 :   pari_sp av = avma;
    2323             :   struct _FlxqXQ D;
    2324       12125 :   T = Flx_get_red_pre(T, p, pi);
    2325       12125 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2326       12125 :   D.S=S; D.T=T; D.p=p; D.pi=pi;
    2327       12125 :   aut = gen_powu_i(aut,n,&D,FlxqXQ_autsum_sqr,FlxqXQ_autsum_mul);
    2328       12125 :   return gc_GEN(av, aut);
    2329             : }
    2330             : GEN
    2331           0 : FlxqXQ_autsum(GEN aut, long n, GEN S, GEN T, ulong p)
    2332           0 : { return FlxqXQ_autsum_pre(aut, n, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2333             : 
    2334             : static GEN
    2335          27 : FlxqXQ_auttrace_mul(void *E, GEN x, GEN y)
    2336             : {
    2337          27 :   struct _FlxqXQ *D = (struct _FlxqXQ *)E;
    2338          27 :   GEN S = D->S, T = D->T;
    2339          27 :   ulong p = D->p, pi = D->pi;
    2340          27 :   GEN S1 = gel(x,1), a1 = gel(x,2);
    2341          27 :   GEN S2 = gel(y,1), a2 = gel(y,2);
    2342          27 :   long n = brent_kung_optpow(maxss(degpol(S1),degpol(a1)),2,1);
    2343          27 :   GEN V = FlxqXQ_powers_pre(S2, n, S, T, p, pi);
    2344          27 :   GEN S3 = FlxqX_FlxqXQV_eval_pre(S1, V, S, T, p, pi);
    2345          27 :   GEN aS = FlxqX_FlxqXQV_eval_pre(a1, V, S, T, p, pi);
    2346          27 :   GEN a3 = FlxX_add(aS, a2, p);
    2347          27 :   return mkvec2(S3, a3);
    2348             : }
    2349             : 
    2350             : static GEN
    2351          20 : FlxqXQ_auttrace_sqr(void *E, GEN x)
    2352          20 : { return FlxqXQ_auttrace_mul(E, x, x); }
    2353             : 
    2354             : GEN
    2355         337 : FlxqXQ_auttrace_pre(GEN x, ulong n, GEN S, GEN T, ulong p, ulong pi)
    2356             : {
    2357         337 :   pari_sp av = avma;
    2358             :   struct _FlxqXQ D;
    2359         337 :   T = Flx_get_red_pre(T, p, pi);
    2360         337 :   S = FlxqX_get_red_pre(S, T, p, pi);
    2361         337 :   D.S=S; D.T=T; D.p=p; D.pi = pi;
    2362         337 :   x = gen_powu_i(x,n,(void*)&D,FlxqXQ_auttrace_sqr,FlxqXQ_auttrace_mul);
    2363         337 :   return gc_GEN(av, x);
    2364             : }
    2365             : GEN
    2366           0 : FlxqXQ_auttrace(GEN x, ulong n, GEN S, GEN T, ulong p)
    2367           0 : { return FlxqXQ_auttrace_pre(x, n, S, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2368             : 
    2369             : /*******************************************************************/
    2370             : /*                                                                 */
    2371             : /*                      FlxYqQ                                     */
    2372             : /*                                                                 */
    2373             : /*******************************************************************/
    2374             : 
    2375             : /*Preliminary implementation to speed up FpX_ffisom*/
    2376             : typedef struct {
    2377             :   GEN S, T;
    2378             :   ulong p, pi;
    2379             : } FlxYqq_muldata;
    2380             : 
    2381             : /* reduce x in Fl[X, Y] in the algebra Fl[X, Y]/ (P(X),Q(Y)) */
    2382             : static GEN
    2383       90884 : FlxYqq_redswap(GEN x, GEN S, GEN T, ulong p, ulong pi)
    2384             : {
    2385       90884 :   pari_sp ltop=avma;
    2386       90884 :   long n = get_Flx_degree(S);
    2387       90884 :   long m = get_Flx_degree(T);
    2388       90883 :   long w = get_Flx_var(T);
    2389       90883 :   GEN V = FlxX_swap(x,m,w);
    2390       90883 :   V = FlxqX_red_pre(V,S,p,pi);
    2391       90881 :   V = FlxX_swap(V,n,w);
    2392       90883 :   return gc_GEN(ltop,V);
    2393             : }
    2394             : static GEN
    2395       80516 : FlxYqq_sqr(void *data, GEN x)
    2396             : {
    2397       80516 :   FlxYqq_muldata *D = (FlxYqq_muldata*)data;
    2398       80516 :   return FlxYqq_redswap(FlxqX_sqr_pre(x,D->T,D->p,D->pi),D->S,D->T,D->p,D->pi);
    2399             : }
    2400             : 
    2401             : static GEN
    2402       10368 : FlxYqq_mul(void *data, GEN x, GEN y)
    2403             : {
    2404       10368 :   FlxYqq_muldata *D = (FlxYqq_muldata*)data;
    2405       10368 :   return FlxYqq_redswap(FlxqX_mul_pre(x,y, D->T,D->p,D->pi),D->S,D->T,D->p,D->pi);
    2406             : }
    2407             : 
    2408             : /* x in Z[X,Y], S in Z[X] over Fq = Z[Y]/(p,T); compute lift(x^n mod (S,T,p)) */
    2409             : GEN
    2410       39226 : FlxYqq_pow(GEN x, GEN n, GEN S, GEN T, ulong p)
    2411             : {
    2412             :   FlxYqq_muldata D;
    2413       39226 :   D.S = S; D.T = T; D.p = p; D.pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
    2414       39226 :   return gen_pow(x, n, (void*)&D, &FlxYqq_sqr, &FlxYqq_mul);
    2415             : }
    2416             : 
    2417             : /*******************************************************************/
    2418             : /*                                                                 */
    2419             : /*                      FlxqXn                                     */
    2420             : /*                                                                 */
    2421             : /*******************************************************************/
    2422             : 
    2423             : GEN
    2424       66176 : FlxXn_red(GEN a, long n)
    2425             : {
    2426       66176 :   long i, L = n+2, l = lg(a);
    2427             :   GEN  b;
    2428       66176 :   if (L >= l) return a; /* deg(x) < n */
    2429       36738 :   b = cgetg(L, t_POL); b[1] = a[1];
    2430      391853 :   for (i=2; i<L; i++) gel(b,i) = gel(a,i);
    2431       36740 :   return FlxX_renormalize(b,L);
    2432             : }
    2433             : 
    2434             : GEN
    2435       40406 : FlxqXn_mul_pre(GEN a, GEN b, long n, GEN T, ulong p, ulong pi)
    2436       40406 : { return FlxXn_red(FlxqX_mul_pre(a, b, T, p, pi), n); }
    2437             : GEN
    2438           0 : FlxqXn_mul(GEN a, GEN b, long n, GEN T, ulong p)
    2439           0 : { return FlxqXn_mul_pre(a, b, n, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2440             : 
    2441             : GEN
    2442           0 : FlxqXn_sqr_pre(GEN a, long n, GEN T, ulong p, ulong pi)
    2443           0 : { return FlxXn_red(FlxqX_sqr_pre(a, T, p, pi), n); }
    2444             : GEN
    2445           0 : FlxqXn_sqr(GEN a, long n, GEN T, ulong p)
    2446           0 : { return FlxqXn_sqr_pre(a, n, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2447             : 
    2448             : /* (f*g) \/ x^n */
    2449             : static GEN
    2450       17998 : FlxqX_mulhigh_i(GEN f, GEN g, long n, GEN T, ulong p, ulong pi)
    2451       17998 : { return FlxX_shift(FlxqX_mul_pre(f, g, T, p, pi), -n , get_Flx_var(T)); }
    2452             : 
    2453             : static GEN
    2454       13195 : FlxqXn_mulhigh(GEN f, GEN g, long n2, long n, GEN T, ulong p, ulong pi)
    2455             : {
    2456       13195 :   long vT = get_Flx_var(T);
    2457       13195 :   GEN F = FlxX_blocks(f, n2, 2, vT), fl = gel(F,1), fh = gel(F,2);
    2458       13194 :   return FlxX_add(FlxqX_mulhigh_i(fl, g, n2, T, p, pi),
    2459             :                   FlxqXn_mul_pre(fh, g, n - n2, T, p, pi), p);
    2460             : }
    2461             : 
    2462             : GEN
    2463        2432 : FlxqXn_inv_pre(GEN f, long e, GEN T, ulong p, ulong pi)
    2464             : {
    2465        2432 :   pari_sp av = avma, av2;
    2466             :   ulong mask;
    2467             :   GEN W, a;
    2468        2432 :   long v = varn(f), n = 1, vT = get_Flx_var(T);
    2469             : 
    2470        2432 :   if (!signe(f)) pari_err_INV("FlxqXn_inv",f);
    2471        2432 :   a = Flxq_inv_pre(gel(f,2), T, p, pi);
    2472        2432 :   if (e == 1) return scalarpol(a, v);
    2473        2432 :   else if (e == 2)
    2474             :   {
    2475             :     GEN b;
    2476           0 :     if (degpol(f) <= 0) return scalarpol(a, v);
    2477           0 :     b = Flx_neg(gel(f,3), p);
    2478           0 :     if (lgpol(b)==0) return scalarpol(a, v);
    2479           0 :     b = Flxq_mul_pre(b, Flxq_sqr_pre(a, T, p, pi), T, p, pi);
    2480           0 :     W = deg1pol_shallow(b, a, v);
    2481           0 :     return gc_GEN(av, W);
    2482             :   }
    2483        2432 :   W = scalarpol_shallow(Flxq_inv_pre(gel(f,2), T, p, pi), v);
    2484        2432 :   mask = quadratic_prec_mask(e);
    2485        2432 :   av2 = avma;
    2486       12040 :   for (;mask>1;)
    2487             :   {
    2488             :     GEN u, fr;
    2489        9608 :     long n2 = n;
    2490        9608 :     n<<=1; if (mask & 1) n--;
    2491        9608 :     mask >>= 1;
    2492        9608 :     fr = FlxXn_red(f, n);
    2493        9607 :     u = FlxqXn_mul_pre(W, FlxqXn_mulhigh(fr, W, n2, n, T,p,pi), n-n2, T,p,pi);
    2494        9608 :     W = FlxX_sub(W, FlxX_shift(u, n2, vT), p);
    2495        9608 :     if (gc_needed(av2,2))
    2496             :     {
    2497           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"FlxqXn_inv, e = %ld", n);
    2498           0 :       W = gc_upto(av2, W);
    2499             :     }
    2500             :   }
    2501        2432 :   return gc_upto(av, W);
    2502             : }
    2503             : GEN
    2504           0 : FlxqXn_inv(GEN f, long e, GEN T, ulong p)
    2505           0 : { return FlxqXn_inv_pre(f, e, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }
    2506             : 
    2507             : /* Compute intformal(x^n*S)/x^(n+1) */
    2508             : static GEN
    2509        4803 : FlxX_integXn(GEN x, long n, ulong p)
    2510             : {
    2511        4803 :   long i, lx = lg(x);
    2512             :   GEN y;
    2513        4803 :   if (lx == 2) return gcopy(x);
    2514        3997 :   y = cgetg(lx, t_POL); y[1] = x[1];
    2515       26729 :   for (i=2; i<lx; i++)
    2516             :   {
    2517       22731 :     GEN xi = gel(x,i);
    2518       22731 :     gel(y,i) = Flx_Fl_mul(xi, Fl_inv((n+i-1)%p, p), p);
    2519             :   }
    2520        3998 :   return FlxX_renormalize(y, lx);;
    2521             : }
    2522             : 
    2523             : GEN
    2524        1216 : FlxqXn_expint_pre(GEN h, long e, GEN T, ulong p, ulong pi)
    2525             : {
    2526        1216 :   pari_sp av = avma, av2;
    2527        1216 :   long v = varn(h), n = 1, vT = get_Flx_var(T);
    2528        1216 :   GEN f = pol1_FlxX(v, vT), g = pol1_FlxX(v, vT);
    2529        1216 :   ulong mask = quadratic_prec_mask(e);
    2530        1216 :   av2 = avma;
    2531        4804 :   for (;mask>1;)
    2532             :   {
    2533             :     GEN u, w;
    2534        4804 :     long n2 = n;
    2535        4804 :     n<<=1; if (mask & 1) n--;
    2536        4804 :     mask >>= 1;
    2537        4804 :     u = FlxqXn_mul_pre(g, FlxqX_mulhigh_i(f, FlxXn_red(h, n2-1), n2-1, T,p,pi), n-n2, T,p,pi);
    2538        4804 :     u = FlxX_add(u, FlxX_shift(FlxXn_red(h, n-1), 1-n2, vT), p);
    2539        4803 :     w = FlxqXn_mul_pre(f, FlxX_integXn(u, n2-1, p), n-n2, T, p, pi);
    2540        4804 :     f = FlxX_add(f, FlxX_shift(w, n2, vT), p);
    2541        4804 :     if (mask<=1) break;
    2542        3588 :     u = FlxqXn_mul_pre(g, FlxqXn_mulhigh(f, g, n2, n, T,p,pi), n-n2, T,p,pi);
    2543        3588 :     g = FlxX_sub(g, FlxX_shift(u, n2, vT), p);
    2544        3588 :     if (gc_needed(av2,2))
    2545             :     {
    2546           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FlxqXn_exp, e = %ld", n);
    2547           0 :       (void)gc_all(av2, 2, &f, &g);
    2548             :     }
    2549             :   }
    2550        1216 :   return gc_upto(av, f);
    2551             : }
    2552             : GEN
    2553           0 : FlxqXn_expint(GEN h, long e, GEN T, ulong p)
    2554           0 : { return FlxqXn_expint_pre(h, e, T, p, SMALL_ULONG(p)? 0: get_Fl_red(p)); }

Generated by: LCOV version 1.16