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 - FpXX.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24964-97b24cd8ac) Lines: 881 1043 84.5 %
Date: 2020-01-22 05:56:41 Functions: 104 118 88.1 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2012  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /* Not so fast arithmetic with polynomials over FpX */
      18             : 
      19             : /*******************************************************************/
      20             : /*                                                                 */
      21             : /*                             FpXX                                */
      22             : /*                                                                 */
      23             : /*******************************************************************/
      24             : /*Polynomials whose coefficients are either polynomials or integers*/
      25             : 
      26             : static ulong
      27      240760 : to_FlxqX(GEN P, GEN Q, GEN T, GEN p, GEN *pt_P, GEN *pt_Q, GEN *pt_T)
      28             : {
      29      240760 :   ulong pp = uel(p,2);
      30      240760 :   long v = get_FpX_var(T);
      31      240760 :   *pt_P = ZXX_to_FlxX(P, pp, v);
      32      240760 :   if (pt_Q) *pt_Q = ZXX_to_FlxX(Q, pp, v);
      33      240760 :   *pt_T = ZXT_to_FlxT(T, pp);
      34      240760 :   return pp;
      35             : }
      36             : 
      37             : static GEN
      38           0 : ZXX_copy(GEN a) { return gcopy(a); }
      39             : 
      40             : GEN
      41       34426 : FpXX_red(GEN z, GEN p)
      42             : {
      43             :   GEN res;
      44       34426 :   long i, l = lg(z);
      45       34426 :   res = cgetg(l,t_POL); res[1] = z[1];
      46      243929 :   for (i=2; i<l; i++)
      47             :   {
      48      209503 :     GEN zi = gel(z,i), c;
      49      209503 :     if (typ(zi)==t_INT)
      50        2352 :       c = modii(zi,p);
      51             :     else
      52             :     {
      53      207151 :       pari_sp av = avma;
      54      207151 :       c = FpX_red(zi,p);
      55      207151 :       switch(lg(c)) {
      56          14 :         case 2: set_avma(av); c = gen_0; break;
      57       17472 :         case 3: c = gerepilecopy(av, gel(c,2)); break;
      58             :       }
      59             :     }
      60      209503 :     gel(res,i) = c;
      61             :   }
      62       34426 :   return FpXX_renormalize(res,lg(res));
      63             : }
      64             : GEN
      65      403984 : FpXX_add(GEN x, GEN y, GEN p)
      66             : {
      67             :   long i,lz;
      68             :   GEN z;
      69      403984 :   long lx=lg(x);
      70      403984 :   long ly=lg(y);
      71      403984 :   if (ly>lx) swapspec(x,y, lx,ly);
      72      403984 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
      73      403984 :   for (i=2; i<ly; i++) gel(z,i) = Fq_add(gel(x,i), gel(y,i), NULL, p);
      74      403984 :   for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
      75      403984 :   return FpXX_renormalize(z, lz);
      76             : }
      77             : GEN
      78       13648 : FpXX_sub(GEN x, GEN y, GEN p)
      79             : {
      80             :   long i,lz;
      81             :   GEN z;
      82       13648 :   long lx=lg(x);
      83       13648 :   long ly=lg(y);
      84       13648 :   if (ly <= lx)
      85             :   {
      86       11655 :     lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
      87       11655 :     for (i=2; i<ly; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
      88       11655 :     for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
      89             :   }
      90             :   else
      91             :   {
      92        1993 :     lz = ly; z = cgetg(lz, t_POL); z[1]=x[1];
      93        1993 :     for (i=2; i<lx; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
      94        1993 :     for (   ; i<ly; i++) gel(z,i) = Fq_neg(gel(y,i), NULL, p);
      95             :   }
      96       13648 :   return FpXX_renormalize(z, lz);
      97             : }
      98             : 
      99             : static GEN
     100      117158 : FpXX_subspec(GEN x, GEN y, GEN p, long nx, long ny)
     101             : {
     102             :   long i,lz;
     103             :   GEN z;
     104      117158 :   if (ny <= nx)
     105             :   {
     106      117158 :     lz = nx+2; z = cgetg(lz, t_POL);
     107      117158 :     for (i=0; i<ny; i++) gel(z,i+2) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
     108      117158 :     for (   ; i<nx; i++) gel(z,i+2) = gcopy(gel(x,i));
     109             :   }
     110             :   else
     111             :   {
     112           0 :     lz = ny+2; z = cgetg(lz, t_POL);
     113           0 :     for (i=0; i<nx; i++) gel(z,i+2) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
     114           0 :     for (   ; i<ny; i++) gel(z,i+2) = Fq_neg(gel(y,i), NULL, p);
     115             :   }
     116      117158 :   z[1] = 0; return FpXX_renormalize(z, lz);
     117             : }
     118             : 
     119             : GEN
     120         471 : FpXX_neg(GEN x, GEN p)
     121             : {
     122         471 :   long i, lx = lg(x);
     123         471 :   GEN y = cgetg(lx,t_POL);
     124         471 :   y[1] = x[1];
     125         471 :   for(i=2; i<lx; i++) gel(y,i) = Fq_neg(gel(x,i), NULL, p);
     126         471 :   return FpXX_renormalize(y, lx);
     127             : }
     128             : 
     129             : GEN
     130       66894 : FpXX_Fp_mul(GEN P, GEN u, GEN p)
     131             : {
     132             :   long i, lP;
     133       66894 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     134      535834 :   for(i=2; i<lP; i++)
     135             :   {
     136      468940 :     GEN x = gel(P,i);
     137      468940 :     gel(res,i) = typ(x)==t_INT? Fp_mul(x,u,p): FpX_Fp_mul(x,u,p);
     138             :   }
     139       66894 :   return FpXX_renormalize(res,lP);
     140             : }
     141             : 
     142             : GEN
     143       50368 : FpXX_mulu(GEN P, ulong u, GEN p)
     144             : {
     145             :   long i, lP;
     146       50368 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     147      269214 :   for(i=2; i<lP; i++)
     148             :   {
     149      218846 :     GEN x = gel(P,i);
     150      218846 :     gel(res,i) = typ(x)==t_INT? Fp_mulu(x,u,p): FpX_mulu(x,u,p);
     151             :   }
     152       50368 :   return FpXX_renormalize(res,lP);
     153             : }
     154             : 
     155             : GEN
     156           0 : FpXX_halve(GEN P, GEN p)
     157             : {
     158             :   long i, lP;
     159           0 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     160           0 :   for(i=2; i<lP; i++)
     161             :   {
     162           0 :     GEN x = gel(P,i);
     163           0 :     gel(res,i) = typ(x)==t_INT? Fp_halve(x,p): FpX_halve(x,p);
     164             :   }
     165           0 :   return FpXX_renormalize(res,lP);
     166             : }
     167             : 
     168             : GEN
     169        9691 : FpXX_deriv(GEN P, GEN p)
     170             : {
     171        9691 :   long i, l = lg(P)-1;
     172             :   GEN res;
     173             : 
     174        9691 :   if (l < 3) return pol_0(varn(P));
     175        9474 :   res = cgetg(l, t_POL);
     176        9474 :   res[1] = P[1];
     177       50965 :   for (i=2; i<l ; i++)
     178             :   {
     179       41491 :     GEN x = gel(P,i+1);
     180       41491 :     gel(res,i) = typ(x)==t_INT? Fp_mulu(x,i-1,p): FpX_mulu(x,i-1,p);
     181             :   }
     182        9474 :   return FpXX_renormalize(res, l);
     183             : }
     184             : 
     185             : GEN
     186           0 : FpXX_integ(GEN P, GEN p)
     187             : {
     188           0 :   long i, l = lg(P);
     189             :   GEN res;
     190             : 
     191           0 :   if (l == 2) return pol_0(varn(P));
     192           0 :   res = cgetg(l+1, t_POL);
     193           0 :   res[1] = P[1];
     194           0 :   gel(res,2) = gen_0;
     195           0 :   for (i=3; i<=l ; i++)
     196             :   {
     197           0 :     GEN x = gel(P,i-1);
     198           0 :     if (signe(x))
     199             :     {
     200           0 :       GEN i1 = Fp_inv(utoi(i-2), p);
     201           0 :       gel(res,i) = typ(x)==t_INT? Fp_mul(x,i1,p): FpX_Fp_mul(x,i1,p);
     202             :     } else
     203           0 :       gel(res,i) = gen_0;
     204             :   }
     205           0 :   return FpXX_renormalize(res, l+1);
     206             : }
     207             : 
     208             : /*******************************************************************/
     209             : /*                                                                 */
     210             : /*                             (Fp[X]/(Q))[Y]                      */
     211             : /*                                                                 */
     212             : /*******************************************************************/
     213             : 
     214             : static GEN
     215      418782 : get_FpXQX_red(GEN T, GEN *B)
     216             : {
     217      418782 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
     218       60184 :   *B = gel(T,1); return gel(T,2);
     219             : }
     220             : 
     221             : GEN
     222          52 : random_FpXQX(long d1, long v, GEN T, GEN p)
     223             : {
     224          52 :   long dT = get_FpX_degree(T), vT = get_FpX_var(T);
     225          52 :   long i, d = d1+2;
     226          52 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
     227          52 :   for (i=2; i<d; i++) gel(y,i) = random_FpX(dT, vT, p);
     228          52 :   return FpXQX_renormalize(y,d);
     229             : }
     230             : 
     231             : /*Not stack clean*/
     232             : GEN
     233      750224 : Kronecker_to_FpXQX(GEN Z, GEN T, GEN p)
     234             : {
     235      750224 :   long i,j,lx,l, N = (get_FpX_degree(T)<<1) + 1;
     236      750224 :   GEN x, t = cgetg(N,t_POL), z = FpX_red(Z, p);
     237      750224 :   t[1] = evalvarn(get_FpX_var(T));
     238      750224 :   l = lg(z); lx = (l-2) / (N-2);
     239      750224 :   x = cgetg(lx+3,t_POL);
     240      750224 :   x[1] = z[1];
     241    14952278 :   for (i=2; i<lx+2; i++)
     242             :   {
     243    14202054 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     244    14202054 :     z += (N-2);
     245    14202054 :     gel(x,i) = FpX_rem(FpX_renormalize(t,N), T,p);
     246             :   }
     247      750224 :   N = (l-2) % (N-2) + 2;
     248      750224 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     249      750224 :   gel(x,i) = FpX_rem(FpX_renormalize(t,N), T,p);
     250      750224 :   return FpXQX_renormalize(x, i+1);
     251             : }
     252             : 
     253             : /* shallow, n = deg(T) */
     254             : GEN
     255      151305 : Kronecker_to_ZXX(GEN z, long n, long v)
     256             : {
     257      151305 :   long i,j,lx,l, N = (n<<1)+1;
     258             :   GEN x, t;
     259      151305 :   l = lg(z); lx = (l-2) / (N-2);
     260      151305 :   x = cgetg(lx+3,t_POL);
     261      151305 :   x[1] = z[1];
     262     2502080 :   for (i=2; i<lx+2; i++)
     263             :   {
     264     2350775 :     t = cgetg(N,t_POL); t[1] = evalvarn(v);
     265     2350775 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     266     2350775 :     z += (N-2);
     267     2350775 :     gel(x,i) = ZX_renormalize(t,N);
     268             :   }
     269      151305 :   N = (l-2) % (N-2) + 2;
     270      151305 :   t = cgetg(N,t_POL); t[1] = evalvarn(v);
     271      151305 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     272      151305 :   gel(x,i) = ZX_renormalize(t,N);
     273      151305 :   return ZXX_renormalize(x, i+1);
     274             : }
     275             : /* shallow */
     276             : GEN
     277      238574 : ZXX_mul_Kronecker(GEN x, GEN y, long n)
     278      238574 : { return ZX_mul(ZXX_to_Kronecker(x,n), ZXX_to_Kronecker(y,n)); }
     279             : 
     280             : GEN
     281        3402 : ZXX_sqr_Kronecker(GEN x, long n)
     282        3402 : { return ZX_sqr(ZXX_to_Kronecker(x,n)); }
     283             : 
     284             : GEN
     285      271959 : FpXQX_red(GEN z, GEN T, GEN p)
     286             : {
     287      271959 :   long i, l = lg(z);
     288      271959 :   GEN res = cgetg(l,t_POL); res[1] = z[1];
     289     5270193 :   for(i=2;i<l;i++)
     290     4998234 :     if (typ(gel(z,i)) == t_INT)
     291      117506 :       gel(res,i) = modii(gel(z,i),p);
     292             :     else
     293     4880728 :       gel(res,i) = FpXQ_red(gel(z,i),T,p);
     294      271959 :   return FpXQX_renormalize(res,l);
     295             : }
     296             : 
     297             : static GEN
     298       44338 : to_intmod(GEN x, GEN p) { retmkintmod(modii(x, p), p); }
     299             : 
     300             : static GEN
     301        4494 : FpX_to_mod_raw(GEN z, GEN p)
     302             : {
     303        4494 :   long i,l = lg(z);
     304             :   GEN x;
     305        4494 :   if (l == 2)
     306             :   {
     307           0 :     x = cgetg(3,t_POL); x[1] = z[1];
     308           0 :     gel(x,2) = mkintmod(gen_0,p); return x;
     309             :   }
     310        4494 :   x = cgetg(l,t_POL);
     311        4494 :   for (i=2; i<l; i++) gel(x,i) = to_intmod(gel(z,i), p);
     312        4494 :   x[1] = z[1]; return normalizepol_lg(x,l);
     313             : }
     314             : 
     315             : GEN
     316         518 : FpXQX_to_mod(GEN z, GEN T, GEN p)
     317             : {
     318         518 :   long i,l = lg(z);
     319         518 :   GEN x = cgetg(l, t_POL);
     320         518 :   x[1] = z[1];
     321         518 :   if (l == 2) return x;
     322         518 :   p = icopy(p);
     323         518 :   T = FpX_to_mod_raw(T, p);
     324        5502 :   for (i=2; i<l; i++)
     325             :   {
     326        4984 :     GEN zi = gel(z,i);
     327       13944 :     gel(x,i) = typ(zi) == t_POL? mkpolmod(FpX_to_mod_raw(zi, p), T)
     328        8960 :                                : to_intmod(zi, p);
     329             :   }
     330         518 :   return normalizepol_lg(x,l);
     331             : }
     332             : 
     333             : static int
     334     1386142 : ZXX_is_ZX_spec(GEN a,long na)
     335             : {
     336             :   long i;
     337     1494498 :   for(i=0;i<na;i++)
     338     1478977 :     if(typ(gel(a,i))!=t_INT) return 0;
     339       15521 :   return 1;
     340             : }
     341             : 
     342             : static int
     343      141256 : ZXX_is_ZX(GEN a) { return ZXX_is_ZX_spec(a+2,lgpol(a)); }
     344             : 
     345             : static GEN
     346       46525 : FpXX_FpX_mulspec(GEN P, GEN U, GEN p, long v, long lU)
     347             : {
     348       46525 :   long i, lP =lg(P);
     349             :   GEN res;
     350       46525 :   res = cgetg(lP, t_POL); res[1] = P[1];
     351     1792126 :   for(i=2; i<lP; i++)
     352             :   {
     353     1745601 :     GEN Pi = gel(P,i);
     354     3484555 :     gel(res,i) = typ(Pi)==t_INT? FpX_Fp_mulspec(U, Pi, p, lU):
     355     1738954 :                                  FpX_mulspec(U, Pi+2, p, lU, lgpol(Pi));
     356     1745601 :     setvarn(gel(res,i),v);
     357             :   }
     358       46525 :   return FpXQX_renormalize(res,lP);
     359             : }
     360             : 
     361             : GEN
     362       36808 : FpXX_FpX_mul(GEN P, GEN U, GEN p)
     363       36808 : { return FpXX_FpX_mulspec(P,U+2,p,varn(U),lgpol(U)); }
     364             : 
     365             : static GEN
     366        9717 : FpXY_FpY_mulspec(GEN x, GEN y, GEN T, GEN p, long lx, long ly)
     367             : {
     368        9717 :   pari_sp av = avma;
     369        9717 :   long v = fetch_var();
     370        9717 :   GEN z = RgXY_swapspec(x,get_FpX_degree(T)-1,v,lx);
     371        9717 :   z = FpXX_FpX_mulspec(z,y,p,v,ly);
     372        9717 :   z = RgXY_swapspec(z+2,lx+ly+3,get_FpX_var(T),lgpol(z));
     373        9717 :   (void)delete_var(); return gerepilecopy(av,z);
     374             : }
     375             : 
     376             : static GEN
     377      622443 : FpXQX_mulspec(GEN x, GEN y, GEN T, GEN p, long lx, long ly)
     378             : {
     379      622443 :   pari_sp av = avma;
     380             :   GEN z, kx, ky;
     381             :   long n;
     382      622443 :   if (ZXX_is_ZX_spec(y,ly))
     383             :   {
     384        6754 :     if (ZXX_is_ZX_spec(x,lx))
     385        2046 :       return FpX_mulspec(x,y,p,lx,ly);
     386             :     else
     387        4708 :       return FpXY_FpY_mulspec(x,y,T,p,lx,ly);
     388      615689 :   } else if (ZXX_is_ZX_spec(x,lx))
     389        5009 :       return FpXY_FpY_mulspec(y,x,T,p,ly,lx);
     390      610680 :   n = get_FpX_degree(T);
     391      610680 :   kx = ZXX_to_Kronecker_spec(x, lx, n);
     392      610680 :   ky = ZXX_to_Kronecker_spec(y, ly, n);
     393      610680 :   z = Kronecker_to_FpXQX(ZX_mul(ky,kx), T, p);
     394      610680 :   return gerepileupto(av, z);
     395             : }
     396             : 
     397             : GEN
     398      384844 : FpXQX_mul(GEN x, GEN y, GEN T, GEN p)
     399             : {
     400      384844 :   GEN z = FpXQX_mulspec(x+2,y+2,T,p,lgpol(x),lgpol(y));
     401      384844 :   setvarn(z,varn(x)); return z;
     402             : }
     403             : 
     404             : GEN
     405      141126 : FpXQX_sqr(GEN x, GEN T, GEN p)
     406             : {
     407      141126 :   pari_sp av = avma;
     408             :   GEN z, kx;
     409      141126 :   if (ZXX_is_ZX(x)) return ZX_sqr(x);
     410      139414 :   kx= ZXX_to_Kronecker(x, get_FpX_degree(T));
     411      139414 :   z = Kronecker_to_FpXQX(ZX_sqr(kx), T, p);
     412      139414 :   return gerepileupto(av, z);
     413             : }
     414             : 
     415             : GEN
     416      249392 : FpXQX_FpXQ_mul(GEN P, GEN U, GEN T, GEN p)
     417             : {
     418             :   long i, lP;
     419             :   GEN res;
     420      249392 :   res = cgetg_copy(P, &lP); res[1] = P[1];
     421     1150678 :   for(i=2; i<lP; i++)
     422     1704729 :     gel(res,i) = typ(gel(P,i))==t_INT? FpX_Fp_mul(U, gel(P,i), p):
     423      803443 :                                        FpXQ_mul(U, gel(P,i), T,p);
     424      249392 :   return FpXQX_renormalize(res,lP);
     425             : }
     426             : 
     427             : /* x and y in Z[Y][X]. Assume T irreducible mod p */
     428             : static GEN
     429      129505 : FpXQX_divrem_basecase(GEN x, GEN y, GEN T, GEN p, GEN *pr)
     430             : {
     431             :   long vx, dx, dy, dy1, dz, i, j, sx, lr;
     432             :   pari_sp av0, av, tetpil;
     433             :   GEN z,p1,rem,lead;
     434             : 
     435      129505 :   if (!signe(y)) pari_err_INV("FpX_divrem",y);
     436      129505 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
     437      129505 :   if (dx < dy)
     438             :   {
     439         185 :     if (pr)
     440             :     {
     441         135 :       av0 = avma; x = FpXQX_red(x, T, p);
     442         135 :       if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
     443         135 :       if (pr == ONLY_REM) return x;
     444         135 :       *pr = x;
     445             :     }
     446         185 :     return pol_0(vx);
     447             :   }
     448      129320 :   lead = leading_coeff(y);
     449      129320 :   if (!dy) /* y is constant */
     450             :   {
     451         829 :     if (pr && pr != ONLY_DIVIDES)
     452             :     {
     453         571 :       if (pr == ONLY_REM) return pol_0(vx);
     454           4 :       *pr = pol_0(vx);
     455             :     }
     456         262 :     if (gequal1(lead)) return FpXQX_red(x,T,p);
     457         246 :     av0 = avma; x = FqX_Fq_mul(x, Fq_inv(lead, T,p), T,p);
     458         246 :     return gerepileupto(av0,x);
     459             :   }
     460      128491 :   av0 = avma; dz = dx-dy;
     461      128491 :   lead = gequal1(lead)? NULL: gclone(Fq_inv(lead,T,p));
     462      128491 :   set_avma(av0);
     463      128491 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
     464      128491 :   x += 2; y += 2; z += 2;
     465      128491 :   for (dy1=dy-1; dy1>=0 && !signe(gel(y, dy1)); dy1--);
     466             : 
     467      128491 :   p1 = gel(x,dx); av = avma;
     468      128491 :   gel(z,dz) = lead? gerepileupto(av, Fq_mul(p1,lead, T, p)): gcopy(p1);
     469      414281 :   for (i=dx-1; i>=dy; i--)
     470             :   {
     471      285790 :     av=avma; p1=gel(x,i);
     472      983187 :     for (j=i-dy1; j<=i && j<=dz; j++)
     473      697397 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j),NULL,p),NULL,p);
     474      285790 :     if (lead) p1 = Fq_mul(p1, lead, NULL,p);
     475      285790 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,Fq_red(p1,T,p));
     476             :   }
     477      128491 :   if (!pr) { guncloneNULL(lead); return z-2; }
     478             : 
     479      125376 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     480      139887 :   for (sx=0; ; i--)
     481             :   {
     482      154398 :     p1 = gel(x,i);
     483      545996 :     for (j=maxss(0,i-dy1); j<=i && j<=dz; j++)
     484      406109 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j),NULL,p),NULL,p);
     485      139887 :     tetpil=avma; p1 = Fq_red(p1, T, p); if (signe(p1)) { sx = 1; break; }
     486       16317 :     if (!i) break;
     487       14511 :     set_avma(av);
     488             :   }
     489      125376 :   if (pr == ONLY_DIVIDES)
     490             :   {
     491           0 :     guncloneNULL(lead);
     492           0 :     if (sx) return gc_NULL(av0);
     493           0 :     set_avma((pari_sp)rem); return z-2;
     494             :   }
     495      125376 :   lr=i+3; rem -= lr;
     496      125376 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     497      125376 :   rem[1] = z[-1];
     498      125376 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
     499      125376 :   rem += 2; gel(rem,i) = p1;
     500      836024 :   for (i--; i>=0; i--)
     501             :   {
     502      710648 :     av=avma; p1 = gel(x,i);
     503     2312059 :     for (j=maxss(0,i-dy1); j<=i && j<=dz; j++)
     504     1601411 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j), NULL,p), NULL,p);
     505      710648 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, Fq_red(p1, T, p));
     506             :   }
     507      125376 :   rem -= 2;
     508      125376 :   guncloneNULL(lead);
     509      125376 :   if (!sx) (void)FpXQX_renormalize(rem, lr);
     510      125376 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
     511       10578 :   *pr = rem; return z-2;
     512             : }
     513             : 
     514             : static GEN
     515         112 : FpXQX_halfgcd_basecase(GEN a, GEN b, GEN T, GEN p)
     516             : {
     517         112 :   pari_sp av=avma;
     518             :   GEN u,u1,v,v1;
     519         112 :   long vx = varn(a);
     520         112 :   long n = lgpol(a)>>1;
     521         112 :   u1 = v = pol_0(vx);
     522         112 :   u = v1 = pol_1(vx);
     523        1111 :   while (lgpol(b)>n)
     524             :   {
     525         887 :     GEN r, q = FpXQX_divrem(a,b, T, p, &r);
     526         887 :     a = b; b = r; swap(u,u1); swap(v,v1);
     527         887 :     u1 = FpXX_sub(u1, FpXQX_mul(u, q, T, p), p);
     528         887 :     v1 = FpXX_sub(v1, FpXQX_mul(v, q ,T, p), p);
     529         887 :     if (gc_needed(av,2))
     530             :     {
     531           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_halfgcd (d = %ld)",degpol(b));
     532           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     533             :     }
     534             :   }
     535         112 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     536             : }
     537             : static GEN
     538         136 : FpXQX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN T, GEN p)
     539             : {
     540         136 :   return FpXX_add(FpXQX_mul(u, x, T, p),FpXQX_mul(v, y, T, p), p);
     541             : }
     542             : 
     543             : static GEN
     544          68 : FpXQXM_FpXQX_mul2(GEN M, GEN x, GEN y, GEN T, GEN p)
     545             : {
     546          68 :   GEN res = cgetg(3, t_COL);
     547          68 :   gel(res, 1) = FpXQX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, T, p);
     548          68 :   gel(res, 2) = FpXQX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, T, p);
     549          68 :   return res;
     550             : }
     551             : 
     552             : static GEN
     553          56 : FpXQXM_mul2(GEN A, GEN B, GEN T, GEN p)
     554             : {
     555          56 :   GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
     556          56 :   GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
     557          56 :   GEN M1 = FpXQX_mul(FpXX_add(A11,A22, p), FpXX_add(B11,B22, p), T, p);
     558          56 :   GEN M2 = FpXQX_mul(FpXX_add(A21,A22, p), B11, T, p);
     559          56 :   GEN M3 = FpXQX_mul(A11, FpXX_sub(B12,B22, p), T, p);
     560          56 :   GEN M4 = FpXQX_mul(A22, FpXX_sub(B21,B11, p), T, p);
     561          56 :   GEN M5 = FpXQX_mul(FpXX_add(A11,A12, p), B22, T, p);
     562          56 :   GEN M6 = FpXQX_mul(FpXX_sub(A21,A11, p), FpXX_add(B11,B12, p), T, p);
     563          56 :   GEN M7 = FpXQX_mul(FpXX_sub(A12,A22, p), FpXX_add(B21,B22, p), T, p);
     564          56 :   GEN T1 = FpXX_add(M1,M4, p), T2 = FpXX_sub(M7,M5, p);
     565          56 :   GEN T3 = FpXX_sub(M1,M2, p), T4 = FpXX_add(M3,M6, p);
     566          56 :   retmkmat2(mkcol2(FpXX_add(T1,T2, p), FpXX_add(M2,M4, p)),
     567             :             mkcol2(FpXX_add(M3,M5, p), FpXX_add(T3,T4, p)));
     568             : }
     569             : /* Return [0,1;1,-q]*M */
     570             : static GEN
     571          56 : FpXQX_FpXQXM_qmul(GEN q, GEN M, GEN T, GEN p)
     572             : {
     573          56 :   GEN u, v, res = cgetg(3, t_MAT);
     574          56 :   u = FpXX_sub(gcoeff(M,1,1), FpXQX_mul(gcoeff(M,2,1), q, T, p), p);
     575          56 :   gel(res,1) = mkcol2(gcoeff(M,2,1), u);
     576          56 :   v = FpXX_sub(gcoeff(M,1,2), FpXQX_mul(gcoeff(M,2,2), q, T, p), p);
     577          56 :   gel(res,2) = mkcol2(gcoeff(M,2,2), v);
     578          56 :   return res;
     579             : }
     580             : 
     581             : static GEN
     582           0 : matid2_FpXQXM(long v)
     583             : {
     584           0 :   retmkmat2(mkcol2(pol_1(v),pol_0(v)),
     585             :             mkcol2(pol_0(v),pol_1(v)));
     586             : }
     587             : 
     588             : static GEN
     589          56 : FpXQX_halfgcd_split(GEN x, GEN y, GEN T, GEN p)
     590             : {
     591          56 :   pari_sp av=avma;
     592             :   GEN R, S, V;
     593             :   GEN y1, r, q;
     594          56 :   long l = lgpol(x), n = l>>1, k;
     595          56 :   if (lgpol(y)<=n) return matid2_FpXQXM(varn(x));
     596          56 :   R = FpXQX_halfgcd(RgX_shift_shallow(x,-n),RgX_shift_shallow(y,-n), T, p);
     597          56 :   V = FpXQXM_FpXQX_mul2(R,x,y, T, p); y1 = gel(V,2);
     598          56 :   if (lgpol(y1)<=n) return gerepilecopy(av, R);
     599          56 :   q = FpXQX_divrem(gel(V,1), y1, T, p, &r);
     600          56 :   k = 2*n-degpol(y1);
     601          56 :   S = FpXQX_halfgcd(RgX_shift_shallow(y1,-k), RgX_shift_shallow(r,-k), T, p);
     602          56 :   return gerepileupto(av, FpXQXM_mul2(S,FpXQX_FpXQXM_qmul(q,R, T, p), T, p));
     603             : }
     604             : 
     605             : /* Return M in GL_2(Fp[X]) such that:
     606             : if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
     607             : */
     608             : 
     609             : static GEN
     610         168 : FpXQX_halfgcd_i(GEN x, GEN y, GEN T, GEN p)
     611             : {
     612         168 :   if (lg(x)<=FpXQX_HALFGCD_LIMIT) return FpXQX_halfgcd_basecase(x, y, T, p);
     613          56 :   return FpXQX_halfgcd_split(x, y, T, p);
     614             : }
     615             : 
     616             : GEN
     617         168 : FpXQX_halfgcd(GEN x, GEN y, GEN T, GEN p)
     618             : {
     619         168 :   pari_sp av = avma;
     620             :   GEN M,q,r;
     621         168 :   if (lgefint(p)==3)
     622             :   {
     623           0 :     ulong pp = to_FlxqX(x, y, T, p, &x, &y, &T);
     624           0 :     M = FlxXM_to_ZXXM(FlxqX_halfgcd(x, y, T, pp));
     625             :   }
     626             :   else
     627             :   {
     628         168 :     if (!signe(x))
     629             :     {
     630           0 :       long v = varn(x);
     631           0 :       retmkmat2(mkcol2(pol_0(v),pol_1(v)),
     632             :                 mkcol2(pol_1(v),pol_0(v)));
     633             :     }
     634         168 :     if (degpol(y)<degpol(x)) return FpXQX_halfgcd_i(x, y, T, p);
     635           8 :     q = FpXQX_divrem(y, x, T, p, &r);
     636           8 :     M = FpXQX_halfgcd_i(x, r, T, p);
     637           8 :     gcoeff(M,1,1) = FpXX_sub(gcoeff(M,1,1), FpXQX_mul(q, gcoeff(M,1,2), T, p), p);
     638           8 :     gcoeff(M,2,1) = FpXX_sub(gcoeff(M,2,1), FpXQX_mul(q, gcoeff(M,2,2), T, p), p);
     639             :   }
     640           8 :   return gerepilecopy(av, M);
     641             : }
     642             : 
     643             : static GEN
     644        3291 : FpXQX_gcd_basecase(GEN a, GEN b, GEN T, GEN p)
     645             : {
     646        3291 :   pari_sp av = avma, av0=avma;
     647       22793 :   while (signe(b))
     648             :   {
     649             :     GEN c;
     650       16211 :     if (gc_needed(av0,2))
     651             :     {
     652           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_gcd (d = %ld)",degpol(b));
     653           0 :       gerepileall(av0,2, &a,&b);
     654             :     }
     655       16211 :     av = avma; c = FpXQX_rem(a, b, T, p); a=b; b=c;
     656             :   }
     657        3291 :   set_avma(av); return a;
     658             : }
     659             : 
     660             : GEN
     661       13039 : FpXQX_gcd(GEN x, GEN y, GEN T, GEN p)
     662             : {
     663       13039 :   pari_sp av = avma;
     664       13039 :   if (lgefint(p) == 3)
     665             :   {
     666             :     GEN Pl, Ql, Tl, U;
     667        9671 :     ulong pp = to_FlxqX(x, y, T, p, &Pl, &Ql, &Tl);
     668        9671 :     U  = FlxqX_gcd(Pl, Ql, Tl, pp);
     669        9671 :     return gerepileupto(av, FlxX_to_ZXX(U));
     670             :   }
     671        3368 :   x = FpXQX_red(x, T, p);
     672        3368 :   y = FpXQX_red(y, T, p);
     673        3368 :   if (!signe(x)) return gerepileupto(av, y);
     674        6594 :   while (lg(y)>FpXQX_GCD_LIMIT)
     675             :   {
     676             :     GEN c;
     677          12 :     if (lgpol(y)<=(lgpol(x)>>1))
     678             :     {
     679           0 :       GEN r = FpXQX_rem(x, y, T, p);
     680           0 :       x = y; y = r;
     681             :     }
     682          12 :     c = FpXQXM_FpXQX_mul2(FpXQX_halfgcd(x,y, T, p), x, y, T, p);
     683          12 :     x = gel(c,1); y = gel(c,2);
     684          12 :     gerepileall(av,2,&x,&y);
     685             :   }
     686        3291 :   return gerepileupto(av, FpXQX_gcd_basecase(x, y, T, p));
     687             : }
     688             : 
     689             : static GEN
     690           0 : FpXQX_extgcd_basecase(GEN a, GEN b, GEN T, GEN p, GEN *ptu, GEN *ptv)
     691             : {
     692           0 :   pari_sp av=avma;
     693             :   GEN u,v,d,d1,v1;
     694           0 :   long vx = varn(a);
     695           0 :   d = a; d1 = b;
     696           0 :   v = pol_0(vx); v1 = pol_1(vx);
     697           0 :   while (signe(d1))
     698             :   {
     699           0 :     GEN r, q = FpXQX_divrem(d, d1, T, p, &r);
     700           0 :     v = FpXX_sub(v,FpXQX_mul(q,v1,T, p),p);
     701           0 :     u=v; v=v1; v1=u;
     702           0 :     u=r; d=d1; d1=u;
     703           0 :     if (gc_needed(av,2))
     704             :     {
     705           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_extgcd (d = %ld)",degpol(d));
     706           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     707             :     }
     708             :   }
     709           0 :   if (ptu) *ptu = FpXQX_div(FpXX_sub(d,FpXQX_mul(b,v, T, p), p), a, T, p);
     710           0 :   *ptv = v; return d;
     711             : }
     712             : 
     713             : static GEN
     714           0 : FpXQX_extgcd_halfgcd(GEN x, GEN y, GEN T, GEN p, GEN *ptu, GEN *ptv)
     715             : {
     716           0 :   pari_sp av=avma;
     717           0 :   GEN u,v,R = matid2_FpXQXM(varn(x));
     718           0 :   while (lg(y)>FpXQX_EXTGCD_LIMIT)
     719             :   {
     720             :     GEN M, c;
     721           0 :     if (lgpol(y)<=(lgpol(x)>>1))
     722             :     {
     723           0 :       GEN r, q = FpXQX_divrem(x, y, T, p, &r);
     724           0 :       x = y; y = r;
     725           0 :       R = FpXQX_FpXQXM_qmul(q, R, T, p);
     726             :     }
     727           0 :     M = FpXQX_halfgcd(x,y, T, p);
     728           0 :     c = FpXQXM_FpXQX_mul2(M, x,y, T, p);
     729           0 :     R = FpXQXM_mul2(M, R, T, p);
     730           0 :     x = gel(c,1); y = gel(c,2);
     731           0 :     gerepileall(av,3,&x,&y,&R);
     732             :   }
     733           0 :   y = FpXQX_extgcd_basecase(x,y, T, p, &u,&v);
     734           0 :   if (ptu) *ptu = FpXQX_addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1), T, p);
     735           0 :   *ptv = FpXQX_addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2), T, p);
     736           0 :   return y;
     737             : }
     738             : 
     739             : /* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
     740             :  * ux + vy = gcd (mod T,p) */
     741             : GEN
     742        8932 : FpXQX_extgcd(GEN x, GEN y, GEN T, GEN p, GEN *ptu, GEN *ptv)
     743             : {
     744             :   GEN d;
     745        8932 :   pari_sp ltop=avma;
     746        8932 :   if (lgefint(p) == 3)
     747             :   {
     748             :     GEN Pl, Ql, Tl, Dl;
     749        8932 :     ulong pp = to_FlxqX(x, y, T, p, &Pl, &Ql, &Tl);
     750        8932 :     Dl = FlxqX_extgcd(Pl, Ql, Tl, pp, ptu, ptv);
     751        8932 :     if (ptu) *ptu = FlxX_to_ZXX(*ptu);
     752        8932 :     *ptv = FlxX_to_ZXX(*ptv);
     753        8932 :     d = FlxX_to_ZXX(Dl);
     754             :   }
     755             :   else
     756             :   {
     757           0 :     x = FpXQX_red(x, T, p);
     758           0 :     y = FpXQX_red(y, T, p);
     759           0 :     if (lg(y)>FpXQX_EXTGCD_LIMIT)
     760           0 :       d = FpXQX_extgcd_halfgcd(x, y, T, p, ptu, ptv);
     761             :     else
     762           0 :       d = FpXQX_extgcd_basecase(x, y, T, p, ptu, ptv);
     763             :   }
     764        8932 :   gerepileall(ltop,ptu?3:2,&d,ptv,ptu);
     765        8932 :   return d;
     766             : }
     767             : 
     768             : GEN
     769         396 : FpXQX_dotproduct(GEN x, GEN y, GEN T, GEN p)
     770             : {
     771         396 :   long i, l = minss(lg(x), lg(y));
     772             :   pari_sp av;
     773             :   GEN c;
     774         396 :   if (l == 2) return gen_0;
     775         396 :   av = avma; c = gmul(gel(x,2),gel(y,2));
     776         396 :   for (i=3; i<l; i++) c = gadd(c, gmul(gel(x,i),gel(y,i)));
     777         396 :   return gerepileupto(av, Fq_red(c,T,p));
     778             : }
     779             : 
     780             : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
     781             : GEN
     782          63 : FpXQX_resultant(GEN a, GEN b, GEN T, GEN p)
     783             : {
     784             :   long da,db,dc;
     785             :   pari_sp av;
     786          63 :   long vT = get_FpX_var(T);
     787          63 :   GEN c,lb, res = pol_1(vT);
     788             : 
     789          63 :   if (!signe(a) || !signe(b)) return pol_0(vT);
     790          63 :   if (lgefint(p) == 3)
     791             :   {
     792          35 :     pari_sp av = avma;
     793             :     GEN Pl, Ql, Tl, R;
     794          35 :     ulong pp = to_FlxqX(a, b, T, p, &Pl, &Ql, &Tl);
     795          35 :     R = FlxqX_resultant(Pl, Ql, Tl, pp);
     796          35 :     return gerepileupto(av, Flx_to_ZX(R));
     797             :   }
     798             : 
     799          28 :   da = degpol(a);
     800          28 :   db = degpol(b);
     801          28 :   if (db > da)
     802             :   {
     803          14 :     swapspec(a,b, da,db);
     804          14 :     if (both_odd(da,db)) res = FpX_neg(res, p);
     805             :   }
     806          28 :   if (!da) return pol_1(vT); /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
     807          28 :   av = avma;
     808         126 :   while (db)
     809             :   {
     810          70 :     lb = gel(b,db+2);
     811          70 :     c = FpXQX_rem(a,b, T,p);
     812          70 :     a = b; b = c; dc = degpol(c);
     813          70 :     if (dc < 0) { set_avma(av); return pol_0(vT); }
     814             : 
     815          70 :     if (both_odd(da,db)) res = FpX_neg(res, p);
     816          70 :     if (!equali1(lb)) res = FpXQ_mul(res, FpXQ_powu(lb, da - dc, T, p), T, p);
     817          70 :     if (gc_needed(av,2))
     818             :     {
     819           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_resultant (da = %ld)",da);
     820           0 :       gerepileall(av,3, &a,&b,&res);
     821             :     }
     822          70 :     da = db; /* = degpol(a) */
     823          70 :     db = dc; /* = degpol(b) */
     824             :   }
     825          28 :   res = FpXQ_mul(res, FpXQ_powu(gel(b,2), da, T, p), T, p);
     826          28 :   return gerepileupto(av, res);
     827             : }
     828             : 
     829             : /* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
     830             : GEN
     831          35 : FpXQX_disc(GEN P, GEN T, GEN p)
     832             : {
     833          35 :   pari_sp av = avma;
     834          35 :   GEN L, dP = FpXX_deriv(P, p), D = FpXQX_resultant(P, dP, T, p);
     835             :   long dd;
     836          35 :   if (!signe(D)) return pol_0(get_FpX_var(T));
     837          35 :   dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
     838          35 :   L = leading_coeff(P);
     839          35 :   if (dd && !gequal1(L))
     840           0 :     D = (dd == -1)? FpXQ_div(D,L,T,p): FpXQ_mul(D, FpXQ_powu(L, dd, T, p), T, p);
     841          35 :   if (degpol(P) & 2) D = FpX_neg(D, p);
     842          35 :   return gerepileupto(av, D);
     843             : }
     844             : 
     845             : /***********************************************************************/
     846             : /**                                                                   **/
     847             : /**                       Barrett reduction                           **/
     848             : /**                                                                   **/
     849             : /***********************************************************************/
     850             : 
     851             : /* Return new lgpol */
     852             : static long
     853      239727 : ZXX_lgrenormalizespec(GEN x, long lx)
     854             : {
     855             :   long i;
     856      240237 :   for (i = lx-1; i>=0; i--)
     857      240237 :     if (signe(gel(x,i))) break;
     858      239727 :   return i+1;
     859             : }
     860             : 
     861             : static GEN
     862        2896 : FpXQX_invBarrett_basecase(GEN S, GEN T, GEN p)
     863             : {
     864        2896 :   long i, l=lg(S)-1, lr = l-1, k;
     865        2896 :   GEN r=cgetg(lr, t_POL); r[1]=S[1];
     866        2896 :   gel(r,2) = gen_1;
     867       23104 :   for (i=3; i<lr; i++)
     868             :   {
     869       20208 :     pari_sp av = avma;
     870       20208 :     GEN u = gel(S,l-i+2);
     871      188414 :     for (k=3; k<i; k++)
     872      168206 :       u = Fq_add(u, Fq_mul(gel(S,l-i+k), gel(r,k), NULL, p), NULL, p);
     873       20208 :     gel(r,i) = gerepileupto(av, Fq_red(Fq_neg(u, NULL, p), T, p));
     874             :   }
     875        2896 :   return FpXQX_renormalize(r,lr);
     876             : }
     877             : 
     878             : INLINE GEN
     879      236262 : FpXX_recipspec(GEN x, long l, long n)
     880             : {
     881      236262 :   return RgX_recipspec_shallow(x, l, n);
     882             : }
     883             : 
     884             : static GEN
     885         182 : FpXQX_invBarrett_Newton(GEN S, GEN T, GEN p)
     886             : {
     887         182 :   pari_sp av = avma;
     888         182 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
     889         182 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
     890         182 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
     891         182 :   for (i=0;i<l;i++) gel(x,i) = gen_0;
     892         182 :   q = RgX_recipspec_shallow(S+2,l+1,l+1); lQ = lgpol(q); q+=2;
     893             :   /* We work on _spec_ FpX's, all the l[xzq] below are lgpol's */
     894             : 
     895             :   /* initialize */
     896         182 :   gel(x,0) = Fq_inv(gel(q,0), T, p);
     897         182 :   if (lQ>1) gel(q,1) = Fq_red(gel(q,1), T, p);
     898         182 :   if (lQ>1 && signe(gel(q,1)))
     899         182 :   {
     900         182 :     GEN u = gel(q, 1);
     901         182 :     if (!gequal1(gel(x,0))) u = Fq_mul(u, Fq_sqr(gel(x,0), T, p), T, p);
     902         182 :     gel(x,1) = Fq_neg(u, T, p); lx = 2;
     903             :   }
     904             :   else
     905           0 :     lx = 1;
     906         182 :   nold = 1;
     907        1519 :   for (; mask > 1; )
     908             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
     909        1155 :     long i, lnew, nnew = nold << 1;
     910             : 
     911        1155 :     if (mask & 1) nnew--;
     912        1155 :     mask >>= 1;
     913             : 
     914        1155 :     lnew = nnew + 1;
     915        1155 :     lq = ZXX_lgrenormalizespec(q, minss(lQ,lnew));
     916        1155 :     z = FpXQX_mulspec(x, q, T, p, lx, lq); /* FIXME: high product */
     917        1155 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
     918        1155 :     z += 2;
     919             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
     920        1155 :     for (i = nold; i < lz; i++) if (signe(gel(z,i))) break;
     921        1155 :     nold = nnew;
     922        1155 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
     923             : 
     924             :     /* z + i represents (x*q - 1) / t^i */
     925        1155 :     lz = ZXX_lgrenormalizespec (z+i, lz-i);
     926        1155 :     z = FpXQX_mulspec(x, z+i, T, p, lx, lz); /* FIXME: low product */
     927        1155 :     lz = lgpol(z); z += 2;
     928        1155 :     if (lz > lnew-i) lz = ZXX_lgrenormalizespec(z, lnew-i);
     929             : 
     930        1155 :     lx = lz+ i;
     931        1155 :     y  = x + i; /* x -= z * t^i, in place */
     932        1155 :     for (i = 0; i < lz; i++) gel(y,i) = Fq_neg(gel(z,i), T, p);
     933             :   }
     934         182 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
     935         182 :   return gerepilecopy(av, x);
     936             : }
     937             : 
     938             : GEN
     939        3099 : FpXQX_invBarrett(GEN S, GEN T, GEN p)
     940             : {
     941        3099 :   pari_sp ltop = avma;
     942        3099 :   long l = lg(S);
     943             :   GEN r;
     944        3099 :   if (l<5) return pol_0(varn(S));
     945        3078 :   if (l<=FpXQX_INVBARRETT_LIMIT)
     946             :   {
     947        2896 :     GEN c = gel(S,l-1), ci=gen_1;
     948        2896 :     if (!gequal1(c))
     949             :     {
     950        1870 :       ci = Fq_inv(c, T, p);
     951        1870 :       S = FqX_Fq_mul(S, ci, T, p);
     952        1870 :       r = FpXQX_invBarrett_basecase(S, T, p);
     953        1870 :       r = FqX_Fq_mul(r, ci, T, p);
     954             :     } else
     955        1026 :       r = FpXQX_invBarrett_basecase(S, T, p);
     956             :   }
     957             :   else
     958         182 :     r = FpXQX_invBarrett_Newton(S, T, p);
     959        3078 :   return gerepileupto(ltop, r);
     960             : }
     961             : 
     962             : GEN
     963        9270 : FpXQX_get_red(GEN S, GEN T, GEN p)
     964             : {
     965        9270 :   if (typ(S)==t_POL && lg(S)>FpXQX_BARRETT_LIMIT)
     966         760 :     retmkvec2(FpXQX_invBarrett(S,T,p),S);
     967        8510 :   return S;
     968             : }
     969             : 
     970             : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
     971             :  * and mg is the Barrett inverse of S. */
     972             : static GEN
     973      118131 : FpXQX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN p, GEN *pr)
     974             : {
     975             :   GEN q, r;
     976      118131 :   long lt = degpol(S); /*We discard the leading term*/
     977             :   long ld, lm, lT, lmg;
     978      118131 :   ld = l-lt;
     979      118131 :   lm = minss(ld, lgpol(mg));
     980      118131 :   lT  = ZXX_lgrenormalizespec(S+2,lt);
     981      118131 :   lmg = ZXX_lgrenormalizespec(mg+2,lm);
     982      118131 :   q = FpXX_recipspec(x+lt,ld,ld);                 /* q = rec(x)     lq<=ld*/
     983      118131 :   q = FpXQX_mulspec(q+2,mg+2,T,p,lgpol(q),lmg);    /* q = rec(x) * mg lq<=ld+lm*/
     984      118131 :   q = FpXX_recipspec(q+2,minss(ld,lgpol(q)),ld);  /* q = rec (rec(x) * mg) lq<=ld*/
     985      118131 :   if (!pr) return q;
     986      117158 :   r = FpXQX_mulspec(q+2,S+2,T,p,lgpol(q),lT);      /* r = q*pol        lr<=ld+lt*/
     987      117158 :   r = FpXX_subspec(x,r+2,p,lt,minss(lt,lgpol(r))); /* r = x - r   lr<=lt */
     988      117158 :   if (pr == ONLY_REM) return r;
     989       68413 :   *pr = r; return q;
     990             : }
     991             : 
     992             : static GEN
     993       50151 : FpXQX_divrem_Barrett(GEN x, GEN mg, GEN S, GEN T, GEN p, GEN *pr)
     994             : {
     995       50151 :   GEN q = NULL, r = FpXQX_red(x, T, p);
     996       50151 :   long l = lgpol(r), lt = degpol(S), lm = 2*lt-1, v = varn(S);
     997             :   long i;
     998       50151 :   if (l <= lt)
     999             :   {
    1000           0 :     if (pr == ONLY_REM) return r;
    1001           0 :     if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
    1002           0 :     if (pr) *pr = r;
    1003           0 :     return pol_0(v);
    1004             :   }
    1005       50151 :   if (lt <= 1)
    1006          21 :     return FpXQX_divrem_basecase(r,S,T,p,pr);
    1007       50130 :   if (pr != ONLY_REM && l>lm)
    1008             :   {
    1009        1364 :     q = cgetg(l-lt+2, t_POL); q[1] = S[1];
    1010        1364 :     for (i=0;i<l-lt;i++) gel(q+2,i) = gen_0;
    1011             :   }
    1012      168342 :   while (l>lm)
    1013             :   {
    1014       68082 :     GEN zr, zq = FpXQX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,p,&zr);
    1015       68082 :     long lz = lgpol(zr);
    1016       68082 :     if (pr != ONLY_REM)
    1017             :     {
    1018       34939 :       long lq = lgpol(zq);
    1019       34939 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
    1020             :     }
    1021       68082 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
    1022       68082 :     l = l-lm+lz;
    1023             :   }
    1024       50130 :   if (pr == ONLY_REM)
    1025             :   {
    1026       48745 :     if (l > lt)
    1027       48745 :       r = FpXQX_divrem_Barrettspec(r+2,l,mg,S,T,p,ONLY_REM);
    1028             :     else
    1029           0 :       r = FpXQX_renormalize(r, l+2);
    1030       48745 :     setvarn(r, v); return r;
    1031             :   }
    1032        1385 :   if (l > lt)
    1033             :   {
    1034        1304 :     GEN zq = FpXQX_divrem_Barrettspec(r+2,l,mg,S,T,p,pr ? &r: NULL);
    1035        1304 :     if (!q) q = zq;
    1036             :     else
    1037             :     {
    1038        1283 :       long lq = lgpol(zq);
    1039        1283 :       for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
    1040             :     }
    1041             :   }
    1042          81 :   else if (pr)
    1043          81 :     r = FpX_renormalize(r, l+2);
    1044        1385 :   setvarn(q, v); q = FpXQX_renormalize(q, lg(q));
    1045        1385 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
    1046        1385 :   if (pr) { setvarn(r, v); *pr = r; }
    1047        1385 :   return q;
    1048             : }
    1049             : 
    1050             : GEN
    1051      227940 : FpXQX_divrem(GEN x, GEN S, GEN T, GEN p, GEN *pr)
    1052             : {
    1053             :   GEN B, y;
    1054             :   long dy, dx, d;
    1055      227940 :   if (pr==ONLY_REM) return FpXQX_rem(x, S, T, p);
    1056      227940 :   y = get_FpXQX_red(S, &B);
    1057      227940 :   dy = degpol(y); dx = degpol(x); d = dx-dy;
    1058      227940 :   if (lgefint(p) == 3)
    1059             :   {
    1060             :     GEN a, b, t, z;
    1061      212415 :     pari_sp tetpil, av = avma;
    1062      212415 :     ulong pp = to_FlxqX(x, y, T, p, &a, &b, &t);
    1063      212415 :     z = FlxqX_divrem(a, b, t, pp, pr);
    1064      212415 :     if (pr == ONLY_DIVIDES && !z) return gc_NULL(av);
    1065      212415 :     tetpil=avma;
    1066      212415 :     z = FlxX_to_ZXX(z);
    1067      212415 :     if (pr && pr != ONLY_DIVIDES && pr != ONLY_REM)
    1068      210833 :       *pr = FlxX_to_ZXX(*pr);
    1069        1582 :     else return gerepile(av, tetpil, z);
    1070      210833 :     gerepileallsp(av,tetpil,2, pr, &z);
    1071      210833 :     return z;
    1072             :   }
    1073       15525 :   if (!B && d+3 < FpXQX_DIVREM_BARRETT_LIMIT)
    1074       14122 :     return FpXQX_divrem_basecase(x,y,T,p,pr);
    1075             :   else
    1076             :   {
    1077        1403 :     pari_sp av=avma;
    1078        1403 :     GEN mg = B? B: FpXQX_invBarrett(y, T, p);
    1079        1403 :     GEN q = FpXQX_divrem_Barrett(x,mg,y,T,p,pr);
    1080        1403 :     if (!q) return gc_NULL(av);
    1081        1403 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
    1082         416 :     gerepileall(av,2,&q,pr);
    1083         416 :     return q;
    1084             :   }
    1085             : }
    1086             : 
    1087             : GEN
    1088      190754 : FpXQX_rem(GEN x, GEN S, GEN T, GEN p)
    1089             : {
    1090      190754 :   GEN B, y = get_FpXQX_red(S, &B);
    1091      190754 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    1092      190754 :   if (d < 0) return FpXQX_red(x, T, p);
    1093      173817 :   if (lgefint(p) == 3)
    1094             :   {
    1095        9707 :     pari_sp av = avma;
    1096             :     GEN a, b, t, z;
    1097        9707 :     ulong pp = to_FlxqX(x, y, T, p, &a, &b, &t);
    1098        9707 :     z = FlxqX_rem(a, b, t, pp);
    1099        9707 :     z = FlxX_to_ZXX(z);
    1100        9707 :     return gerepileupto(av, z);
    1101             :   }
    1102      164110 :   if (!B && d+3 < FpXQX_REM_BARRETT_LIMIT)
    1103      115362 :     return FpXQX_divrem_basecase(x,y, T, p, ONLY_REM);
    1104             :   else
    1105             :   {
    1106       48748 :     pari_sp av=avma;
    1107       48748 :     GEN mg = B? B: FpXQX_invBarrett(y, T, p);
    1108       48748 :     GEN r = FpXQX_divrem_Barrett(x, mg, y, T, p, ONLY_REM);
    1109       48748 :     return gerepileupto(av, r);
    1110             :   }
    1111             : }
    1112             : 
    1113             : /* x + y*z mod p */
    1114             : INLINE GEN
    1115       11872 : Fq_addmul(GEN x, GEN y, GEN z, GEN T, GEN p)
    1116             : {
    1117             :   pari_sp av;
    1118       11872 :   if (!signe(y) || !signe(z)) return Fq_red(x, T, p);
    1119       11760 :   if (!signe(x)) return Fq_mul(z,y, T, p);
    1120       11746 :   av = avma;
    1121       11746 :   return gerepileupto(av, Fq_add(x, Fq_mul(y, z, T, p), T, p));
    1122             : }
    1123             : 
    1124             : GEN
    1125        5936 : FpXQX_div_by_X_x(GEN a, GEN x, GEN T, GEN p, GEN *r)
    1126             : {
    1127        5936 :   long l = lg(a)-1, i;
    1128        5936 :   GEN z = cgetg(l, t_POL);
    1129        5936 :   z[1] = evalsigne(1) | evalvarn(0);
    1130        5936 :   gel(z, l-1) = gel(a,l);
    1131       17808 :   for (i=l-2; i>1; i--) /* z[i] = a[i+1] + x*z[i+1] */
    1132       11872 :     gel(z, i) = Fq_addmul(gel(a,i+1), x, gel(z,i+1), T, p);
    1133        5936 :   if (r) *r = Fq_addmul(gel(a,2), x, gel(z,2), T, p);
    1134        5936 :   return z;
    1135             : }
    1136             : 
    1137             : struct _FpXQXQ {
    1138             :   GEN T, S;
    1139             :   GEN p;
    1140             : };
    1141             : 
    1142       53494 : static GEN _FpXQX_mul(void *data, GEN a,GEN b)
    1143             : {
    1144       53494 :   struct _FpXQXQ *d=(struct _FpXQXQ*)data;
    1145       53494 :   return FpXQX_mul(a,b,d->T,d->p);
    1146             : }
    1147             : 
    1148        1939 : static GEN _FpXQX_sqr(void *data, GEN a)
    1149             : {
    1150        1939 :   struct _FpXQXQ *d=(struct _FpXQXQ*)data;
    1151        1939 :   return FpXQX_sqr(a, d->T, d->p);
    1152             : }
    1153             : 
    1154             : GEN
    1155          35 : FpXQX_powu(GEN x, ulong n, GEN T, GEN p)
    1156             : {
    1157             :   struct _FpXQXQ D;
    1158          35 :   if (n==0) return pol_1(varn(x));
    1159          35 :   D.T = T; D.p = p;
    1160          35 :   return gen_powu(x, n, (void *)&D, _FpXQX_sqr, _FpXQX_mul);
    1161             : }
    1162             : 
    1163             : GEN
    1164        4787 : FpXQXV_prod(GEN V, GEN T, GEN p)
    1165             : {
    1166        4787 :   if (lgefint(p) == 3)
    1167             :   {
    1168          12 :     pari_sp av = avma;
    1169          12 :     ulong pp = p[2];
    1170          12 :     GEN Tl = ZXT_to_FlxT(T, pp);
    1171          12 :     GEN Vl = ZXXV_to_FlxXV(V, pp, get_FpX_var(T));
    1172          12 :     Tl = FlxqXV_prod(Vl, Tl, pp);
    1173          12 :     return gerepileupto(av, FlxX_to_ZXX(Tl));
    1174             :   }
    1175             :   else
    1176             :   {
    1177             :     struct _FpXQXQ d;
    1178        4775 :     d.T=T; d.p=p;
    1179        4775 :     return gen_product(V, (void*)&d, &_FpXQX_mul);
    1180             :   }
    1181             : }
    1182             : 
    1183             : static GEN
    1184        9954 : _FpXQX_divrem(void * E, GEN x, GEN y, GEN *r)
    1185             : {
    1186        9954 :   struct _FpXQXQ *d = (struct _FpXQXQ *) E;
    1187        9954 :   return FpXQX_divrem(x, y, d->T, d->p, r);
    1188             : }
    1189             : 
    1190             : static GEN
    1191       34982 : _FpXQX_add(void * E, GEN x, GEN y)
    1192             : {
    1193       34982 :   struct _FpXQXQ *d = (struct _FpXQXQ *) E;
    1194       34982 :   return FpXX_add(x, y, d->p);
    1195             : }
    1196             : 
    1197             : static GEN
    1198        4088 : _FpXQX_sub(void * E, GEN x, GEN y) {
    1199        4088 :   struct _FpXQXQ *d = (struct _FpXQXQ*) E;
    1200        4088 :   return FpXX_sub(x,y, d->p);
    1201             : }
    1202             : 
    1203             : static struct bb_ring FpXQX_ring = { _FpXQX_add, _FpXQX_mul, _FpXQX_sqr };
    1204             : 
    1205             : GEN
    1206         623 : FpXQX_digits(GEN x, GEN B, GEN T, GEN p)
    1207             : {
    1208         623 :   pari_sp av = avma;
    1209         623 :   long d = degpol(B), n = (lgpol(x)+d-1)/d;
    1210             :   GEN z;
    1211             :   struct _FpXQXQ D;
    1212         623 :   D.T = T; D.p = p;
    1213         623 :   z = gen_digits(x, B, n, (void *)&D, &FpXQX_ring, _FpXQX_divrem);
    1214         623 :   return gerepileupto(av, z);
    1215             : }
    1216             : 
    1217             : GEN
    1218         189 : FpXQXV_FpXQX_fromdigits(GEN x, GEN B, GEN T, GEN p)
    1219             : {
    1220         189 :   pari_sp av = avma;
    1221             :   struct _FpXQXQ D;
    1222             :   GEN z;
    1223         189 :   D.T = T; D.p = p;
    1224         189 :   z = gen_fromdigits(x,B,(void *)&D, &FpXQX_ring);
    1225         189 :   return gerepileupto(av, z);
    1226             : }
    1227             : 
    1228             : /* Q an FpXY (t_POL with FpX coeffs), evaluate at X = x */
    1229             : GEN
    1230       47880 : FpXY_evalx(GEN Q, GEN x, GEN p)
    1231             : {
    1232       47880 :   long i, lb = lg(Q);
    1233             :   GEN z;
    1234       47880 :   z = cgetg(lb, t_POL); z[1] = Q[1];
    1235      434721 :   for (i=2; i<lb; i++)
    1236             :   {
    1237      386841 :     GEN q = gel(Q,i);
    1238      386841 :     gel(z,i) = typ(q) == t_INT? modii(q,p): FpX_eval(q, x, p);
    1239             :   }
    1240       47880 :   return FpX_renormalize(z, lb);
    1241             : }
    1242             : /* Q an FpXY, evaluate at Y = y */
    1243             : GEN
    1244       18834 : FpXY_evaly(GEN Q, GEN y, GEN p, long vx)
    1245             : {
    1246       18834 :   pari_sp av = avma;
    1247       18834 :   long i, lb = lg(Q);
    1248             :   GEN z;
    1249       18834 :   if (!signe(Q)) return pol_0(vx);
    1250       18806 :   if (lb == 3 || !signe(y)) {
    1251          84 :     z = gel(Q, 2);
    1252          84 :     return typ(z)==t_INT? scalar_ZX(z, vx): ZX_copy(z);
    1253             :   }
    1254       18722 :   z = gel(Q, lb-1);
    1255       18722 :   if (typ(z) == t_INT) z = scalar_ZX_shallow(z, vx);
    1256       18722 :   for (i=lb-2; i>=2; i--) z = Fq_add(gel(Q,i), FpX_Fp_mul(z, y, p), NULL, p);
    1257       18722 :   return gerepileupto(av, z);
    1258             : }
    1259             : /* Q an FpXY, evaluate at (X,Y) = (x,y) */
    1260             : GEN
    1261       13909 : FpXY_eval(GEN Q, GEN y, GEN x, GEN p)
    1262             : {
    1263       13909 :   pari_sp av = avma;
    1264       13909 :   return gerepileuptoint(av, FpX_eval(FpXY_evalx(Q, x, p), y, p));
    1265             : }
    1266             : 
    1267             : GEN
    1268        2832 : FpXY_FpXQV_evalx(GEN P, GEN x, GEN T, GEN p)
    1269             : {
    1270        2832 :   long i, lP = lg(P);
    1271        2832 :   GEN res = cgetg(lP,t_POL);
    1272        2832 :   res[1] = P[1];
    1273       32957 :   for(i=2; i<lP; i++)
    1274       60250 :     gel(res,i) = typ(gel(P,i))==t_INT? icopy(gel(P,i)):
    1275       30125 :                                        FpX_FpXQV_eval(gel(P,i), x, T, p);
    1276        2832 :   return FlxX_renormalize(res, lP);
    1277             : }
    1278             : 
    1279             : GEN
    1280         154 : FpXY_FpXQ_evalx(GEN P, GEN x, GEN T, GEN p)
    1281             : {
    1282         154 :   pari_sp av = avma;
    1283         154 :   long n = brent_kung_optpow(get_FpX_degree(T)-1,lgpol(P),1);
    1284         154 :   GEN xp = FpXQ_powers(x, n, T, p);
    1285         154 :   return gerepileupto(av, FpXY_FpXQV_evalx(P, xp, T, p));
    1286             : }
    1287             : 
    1288             : /*******************************************************************/
    1289             : /*                                                                 */
    1290             : /*                       (Fp[X]/T(X))[Y] / S(Y)                    */
    1291             : /*                                                                 */
    1292             : /*******************************************************************/
    1293             : 
    1294             : /*Preliminary implementation to speed up FpX_ffisom*/
    1295             : typedef struct {
    1296             :   GEN S, T, p;
    1297             : } FpXYQQ_muldata;
    1298             : 
    1299             : /* reduce x in Fp[X, Y] in the algebra Fp[X,Y]/ (S(X),T(Y)) */
    1300             : static GEN
    1301         476 : FpXYQQ_redswap(GEN x, GEN S, GEN T, GEN p)
    1302             : {
    1303         476 :   pari_sp ltop=avma;
    1304         476 :   long n = get_FpX_degree(S);
    1305         476 :   long m = get_FpX_degree(T);
    1306         476 :   long v = get_FpX_var(T);
    1307         476 :   GEN V = RgXY_swap(x,m,v);
    1308         476 :   V = FpXQX_red(V,S,p);
    1309         476 :   V = RgXY_swap(V,n,v);
    1310         476 :   return gerepilecopy(ltop,V);
    1311             : }
    1312             : static GEN
    1313         280 : FpXYQQ_sqr(void *data, GEN x)
    1314             : {
    1315         280 :   FpXYQQ_muldata *D = (FpXYQQ_muldata*)data;
    1316         280 :   return FpXYQQ_redswap(FpXQX_sqr(x, D->T, D->p),D->S,D->T,D->p);
    1317             : 
    1318             : }
    1319             : static GEN
    1320         196 : FpXYQQ_mul(void *data, GEN x, GEN y)
    1321             : {
    1322         196 :   FpXYQQ_muldata *D = (FpXYQQ_muldata*)data;
    1323         196 :   return FpXYQQ_redswap(FpXQX_mul(x,y, D->T, D->p),D->S,D->T,D->p);
    1324             : }
    1325             : 
    1326             : /* x in Z[X,Y], S in Z[X] over Fq = Z[Y]/(p,T); compute lift(x^n mod (S,T,p)) */
    1327             : GEN
    1328         182 : FpXYQQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
    1329             : {
    1330         182 :   pari_sp av = avma;
    1331             :   FpXYQQ_muldata D;
    1332             :   GEN y;
    1333         182 :   if (lgefint(p) == 3)
    1334             :   {
    1335           0 :     ulong pp = to_FlxqX(x, NULL, T, p, &x, NULL, &T);
    1336           0 :     S = ZX_to_Flx(S, pp);
    1337           0 :     y = FlxX_to_ZXX( FlxYqq_pow(x, n, S, T, pp) );
    1338           0 :     y = gerepileupto(av, y);
    1339             :   }
    1340             :   else
    1341             :   {
    1342         182 :     D.S = S;
    1343         182 :     D.T = T;
    1344         182 :     D.p = p;
    1345         182 :     y = gen_pow(x, n, (void*)&D, &FpXYQQ_sqr, &FpXYQQ_mul);
    1346             :   }
    1347         182 :   return y;
    1348             : }
    1349             : 
    1350             : GEN
    1351       32893 : FpXQXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN p) {
    1352       32893 :   return FpXQX_rem(FpXQX_mul(x, y, T, p), S, T, p);
    1353             : }
    1354             : 
    1355             : GEN
    1356      137941 : FpXQXQ_sqr(GEN x, GEN S, GEN T, GEN p) {
    1357      137941 :   return FpXQX_rem(FpXQX_sqr(x, T, p), S, T, p);
    1358             : }
    1359             : 
    1360             : /* Inverse of x in Z/pZ[X]/(pol) or NULL if inverse doesn't exist
    1361             :  * return lift(1 / (x mod (p,pol))) */
    1362             : GEN
    1363          21 : FpXQXQ_invsafe(GEN x, GEN S, GEN T, GEN p)
    1364             : {
    1365          21 :   GEN V, z = FpXQX_extgcd(get_FpXQX_mod(S), x, T, p, NULL, &V);
    1366          21 :   if (degpol(z)) return NULL;
    1367          21 :   z = gel(z,2);
    1368          21 :   z = typ(z)==t_INT ? Fp_invsafe(z,p) : FpXQ_invsafe(z,T,p);
    1369          21 :   if (!z) return NULL;
    1370          21 :   return typ(z)==t_INT ? FpXX_Fp_mul(V, z, p): FpXQX_FpXQ_mul(V, z, T, p);
    1371             : }
    1372             : 
    1373             : GEN
    1374          21 : FpXQXQ_inv(GEN x, GEN S, GEN T,GEN p)
    1375             : {
    1376          21 :   pari_sp av = avma;
    1377          21 :   GEN U = FpXQXQ_invsafe(x, S, T, p);
    1378          21 :   if (!U) pari_err_INV("FpXQXQ_inv",x);
    1379          21 :   return gerepileupto(av, U);
    1380             : }
    1381             : 
    1382             : GEN
    1383           0 : FpXQXQ_div(GEN x,GEN y,GEN S, GEN T,GEN p)
    1384             : {
    1385           0 :   pari_sp av = avma;
    1386           0 :   return gerepileupto(av, FpXQXQ_mul(x, FpXQXQ_inv(y,S,T,p),S,T,p));
    1387             : }
    1388             : 
    1389             : static GEN
    1390       36831 : _FpXQXQ_cmul(void *data, GEN P, long a, GEN x) {
    1391       36831 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1392       36831 :   GEN y = gel(P,a+2);
    1393       73639 :   return typ(y)==t_INT ? FpXX_Fp_mul(x,y, d->p):
    1394       36808 :                          FpXX_FpX_mul(x,y,d->p);
    1395             : }
    1396             : static GEN
    1397       12508 : _FpXQXQ_red(void *data, GEN x) {
    1398       12508 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1399       12508 :   return FpXQX_red(x, d->T, d->p);
    1400             : }
    1401             : static GEN
    1402       30575 : _FpXQXQ_mul(void *data, GEN x, GEN y) {
    1403       30575 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1404       30575 :   return FpXQXQ_mul(x,y, d->S,d->T, d->p);
    1405             : }
    1406             : static GEN
    1407      137941 : _FpXQXQ_sqr(void *data, GEN x) {
    1408      137941 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1409      137941 :   return FpXQXQ_sqr(x, d->S,d->T, d->p);
    1410             : }
    1411             : 
    1412             : static GEN
    1413        9831 : _FpXQXQ_one(void *data) {
    1414        9831 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1415        9831 :   return pol_1(get_FpXQX_var(d->S));
    1416             : }
    1417             : 
    1418             : static GEN
    1419          68 : _FpXQXQ_zero(void *data) {
    1420          68 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1421          68 :   return pol_0(get_FpXQX_var(d->S));
    1422             : }
    1423             : 
    1424             : static struct bb_algebra FpXQXQ_algebra = { _FpXQXQ_red, _FpXQX_add,
    1425             :        _FpXQX_sub, _FpXQXQ_mul, _FpXQXQ_sqr, _FpXQXQ_one, _FpXQXQ_zero };
    1426             : 
    1427             : const struct bb_algebra *
    1428         628 : get_FpXQXQ_algebra(void **E, GEN S, GEN T, GEN p)
    1429             : {
    1430         628 :   GEN z = new_chunk(sizeof(struct _FpXQXQ));
    1431         628 :   struct _FpXQXQ *e = (struct _FpXQXQ *) z;
    1432         628 :   e->T = FpX_get_red(T, p);
    1433         628 :   e->S = FpXQX_get_red(S, e->T, p);
    1434         628 :   e->p  = p; *E = (void*)e;
    1435         628 :   return &FpXQXQ_algebra;
    1436             : }
    1437             : 
    1438             : static struct bb_algebra FpXQX_algebra = { _FpXQXQ_red, _FpXQX_add,
    1439             :        _FpXQX_sub, _FpXQX_mul, _FpXQX_sqr, _FpXQXQ_one, _FpXQXQ_zero };
    1440             : 
    1441             : const struct bb_algebra *
    1442          42 : get_FpXQX_algebra(void **E, GEN T, GEN p, long v)
    1443             : {
    1444          42 :   GEN z = new_chunk(sizeof(struct _FpXQXQ));
    1445          42 :   struct _FpXQXQ *e = (struct _FpXQXQ *) z;
    1446          42 :   e->T = FpX_get_red(T, p);
    1447          42 :   e->S = pol_x(v);
    1448          42 :   e->p  = p; *E = (void*)e;
    1449          42 :   return &FpXQX_algebra;
    1450             : }
    1451             : 
    1452             : /* x over Fq, return lift(x^n) mod S */
    1453             : GEN
    1454        1431 : FpXQXQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
    1455             : {
    1456        1431 :   pari_sp ltop = avma;
    1457             :   GEN y;
    1458             :   struct _FpXQXQ D;
    1459        1431 :   long s = signe(n);
    1460        1431 :   if (!s) return pol_1(varn(x));
    1461        1431 :   if (is_pm1(n)) /* +/- 1 */
    1462           0 :     return (s < 0)? FpXQXQ_inv(x,S,T,p): ZXX_copy(x);
    1463        1431 :   if (lgefint(p) == 3)
    1464             :   {
    1465           0 :     ulong pp = to_FlxqX(x, S, T, p, &x, &S, &T);
    1466           0 :     GEN z = FlxqXQ_pow(x, n, S, T, pp);
    1467           0 :     y = FlxX_to_ZXX(z);
    1468           0 :     return gerepileupto(ltop, y);
    1469             :   }
    1470             :   else
    1471             :   {
    1472        1431 :     T = FpX_get_red(T, p);
    1473        1431 :     S = FpXQX_get_red(S, T, p);
    1474        1431 :     D.S = S; D.T = T; D.p = p;
    1475        1431 :     if (s < 0) x = FpXQXQ_inv(x,S,T,p);
    1476        1431 :     y = gen_pow_i(x, n, (void*)&D,&_FpXQXQ_sqr,&_FpXQXQ_mul);
    1477        1431 :     return gerepilecopy(ltop, y);
    1478             :   }
    1479             : }
    1480             : 
    1481             : /* generates the list of powers of x of degree 0,1,2,...,l*/
    1482             : GEN
    1483        1439 : FpXQXQ_powers(GEN x, long l, GEN S, GEN T, GEN p)
    1484             : {
    1485             :   struct _FpXQXQ D;
    1486        1439 :   int use_sqr = 2*degpol(x) >= get_FpXQX_degree(S);
    1487        1439 :   T = FpX_get_red(T, p);
    1488        1439 :   S = FpXQX_get_red(S, T, p);
    1489        1439 :   D.S = S; D.T = T; D.p = p;
    1490        1439 :   return gen_powers(x, l, use_sqr, (void*)&D, &_FpXQXQ_sqr, &_FpXQXQ_mul,&_FpXQXQ_one);
    1491             : }
    1492             : 
    1493             : /* Let v a linear form, return the linear form z->v(tau*z)
    1494             :    that is, v*(M_tau) */
    1495             : 
    1496             : INLINE GEN
    1497         248 : FpXQX_recipspec(GEN x, long l, long n)
    1498             : {
    1499         248 :   return RgX_recipspec_shallow(x, l, n);
    1500             : }
    1501             : 
    1502             : static GEN
    1503          88 : FpXQXQ_transmul_init(GEN tau, GEN S, GEN T, GEN p)
    1504             : {
    1505             :   GEN bht;
    1506          88 :   GEN h, Sp = get_FpXQX_red(S, &h);
    1507          88 :   long n = degpol(Sp), vT = varn(Sp);
    1508          88 :   GEN ft = FpXQX_recipspec(Sp+2, n+1, n+1);
    1509          88 :   GEN bt = FpXQX_recipspec(tau+2, lgpol(tau), n);
    1510          88 :   setvarn(ft, vT); setvarn(bt, vT);
    1511          88 :   if (h)
    1512          16 :     bht = FpXQXn_mul(bt, h, n-1, T, p);
    1513             :   else
    1514             :   {
    1515          72 :     GEN bh = FpXQX_div(RgX_shift_shallow(tau, n-1), S, T, p);
    1516          72 :     bht = FpXQX_recipspec(bh+2, lgpol(bh), n-1);
    1517          72 :     setvarn(bht, vT);
    1518             :   }
    1519          88 :   return mkvec3(bt, bht, ft);
    1520             : }
    1521             : 
    1522             : static GEN
    1523         200 : FpXQXQ_transmul(GEN tau, GEN a, long n, GEN T, GEN p)
    1524             : {
    1525         200 :   pari_sp ltop = avma;
    1526             :   GEN t1, t2, t3, vec;
    1527         200 :   GEN bt = gel(tau, 1), bht = gel(tau, 2), ft = gel(tau, 3);
    1528         200 :   if (signe(a)==0) return pol_0(varn(a));
    1529         200 :   t2 = RgX_shift_shallow(FpXQX_mul(bt, a, T, p),1-n);
    1530         200 :   if (signe(bht)==0) return gerepilecopy(ltop, t2);
    1531         114 :   t1 = RgX_shift_shallow(FpXQX_mul(ft, a, T, p),-n);
    1532         114 :   t3 = FpXQXn_mul(t1, bht, n-1, T, p);
    1533         114 :   vec = FpXX_sub(t2, RgX_shift_shallow(t3, 1), p);
    1534         114 :   return gerepileupto(ltop, vec);
    1535             : }
    1536             : 
    1537             : static GEN
    1538          44 : polxn_FpXX(long n, long v, long vT)
    1539             : {
    1540          44 :   long i, a = n+2;
    1541          44 :   GEN p = cgetg(a+1, t_POL);
    1542          44 :   p[1] = evalsigne(1)|evalvarn(v);
    1543          44 :   for (i = 2; i < a; i++) gel(p,i) = pol_0(vT);
    1544          44 :   gel(p,a) = pol_1(vT); return p;
    1545             : }
    1546             : 
    1547             : GEN
    1548          44 : FpXQXQ_minpoly(GEN x, GEN S, GEN T, GEN p)
    1549             : {
    1550          44 :   pari_sp ltop = avma;
    1551             :   long vS, vT, n;
    1552             :   GEN v_x, g, tau;
    1553          44 :   vS = get_FpXQX_var(S);
    1554          44 :   vT = get_FpX_var(T);
    1555          44 :   n = get_FpXQX_degree(S);
    1556          44 :   g = pol_1(vS);
    1557          44 :   tau = pol_1(vS);
    1558          44 :   S = FpXQX_get_red(S, T, p);
    1559          44 :   v_x = FpXQXQ_powers(x, usqrt(2*n), S, T, p);
    1560         132 :   while(signe(tau) != 0)
    1561             :   {
    1562             :     long i, j, m, k1;
    1563             :     GEN M, v, tr;
    1564             :     GEN g_prime, c;
    1565          44 :     if (degpol(g) == n) { tau = pol_1(vS); g = pol_1(vS); }
    1566          44 :     v = random_FpXQX(n, vS, T, p);
    1567          44 :     tr = FpXQXQ_transmul_init(tau, S, T, p);
    1568          44 :     v = FpXQXQ_transmul(tr, v, n, T, p);
    1569          44 :     m = 2*(n-degpol(g));
    1570          44 :     k1 = usqrt(m);
    1571          44 :     tr = FpXQXQ_transmul_init(gel(v_x,k1+1), S, T, p);
    1572          44 :     c = cgetg(m+2,t_POL);
    1573          44 :     c[1] = evalsigne(1)|evalvarn(vS);
    1574         200 :     for (i=0; i<m; i+=k1)
    1575             :     {
    1576         156 :       long mj = minss(m-i, k1);
    1577         552 :       for (j=0; j<mj; j++)
    1578         396 :         gel(c,m+1-(i+j)) = FpXQX_dotproduct(v, gel(v_x,j+1), T, p);
    1579         156 :       v = FpXQXQ_transmul(tr, v, n, T, p);
    1580             :     }
    1581          44 :     c = FpXX_renormalize(c, m+2);
    1582             :     /* now c contains <v,x^i> , i = 0..m-1  */
    1583          44 :     M = FpXQX_halfgcd(polxn_FpXX(m, vS, vT), c, T, p);
    1584          44 :     g_prime = gmael(M, 2, 2);
    1585          44 :     if (degpol(g_prime) < 1) continue;
    1586          44 :     g = FpXQX_mul(g, g_prime, T, p);
    1587          44 :     tau = FpXQXQ_mul(tau, FpXQX_FpXQXQV_eval(g_prime, v_x, S, T, p), S, T, p);
    1588             :   }
    1589          44 :   g = FpXQX_normalize(g,T, p);
    1590          44 :   return gerepilecopy(ltop,g);
    1591             : }
    1592             : 
    1593             : GEN
    1594           0 : FpXQXQ_matrix_pow(GEN y, long n, long m, GEN S, GEN T, GEN p)
    1595             : {
    1596           0 :   return RgXV_to_RgM(FpXQXQ_powers(y,m-1,S,T,p),n);
    1597             : }
    1598             : 
    1599             : GEN
    1600        2665 : FpXQX_FpXQXQV_eval(GEN P, GEN V, GEN S, GEN T, GEN p)
    1601             : {
    1602             :   struct _FpXQXQ D;
    1603        2665 :   T = FpX_get_red(T, p);
    1604        2665 :   S = FpXQX_get_red(S, T, p);
    1605        2665 :   D.S=S; D.T=T; D.p=p;
    1606        2665 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &FpXQXQ_algebra,
    1607             :                                                    _FpXQXQ_cmul);
    1608             : }
    1609             : 
    1610             : GEN
    1611         353 : FpXQX_FpXQXQ_eval(GEN Q, GEN x, GEN S, GEN T, GEN p)
    1612             : {
    1613             :   struct _FpXQXQ D;
    1614         353 :   int use_sqr = 2*degpol(x) >= get_FpXQX_degree(S);
    1615         353 :   T = FpX_get_red(T, p);
    1616         353 :   S = FpXQX_get_red(S, T, p);
    1617         353 :   D.S=S; D.T=T; D.p=p;
    1618         353 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &FpXQXQ_algebra,
    1619             :       _FpXQXQ_cmul);
    1620             : }
    1621             : 
    1622             : static GEN
    1623         245 : FpXQXQ_autpow_sqr(void * E, GEN x)
    1624             : {
    1625         245 :   struct _FpXQXQ *D = (struct _FpXQXQ *)E;
    1626         245 :   GEN S = D->S, T = D->T, p = D->p;
    1627         245 :   GEN phi = gel(x,1), S1 = gel(x,2);
    1628         245 :   long n = brent_kung_optpow(get_FpX_degree(T)-1,lgpol(S1)+1,1);
    1629         245 :   GEN V = FpXQ_powers(phi, n, T, p);
    1630         245 :   GEN phi2 = FpX_FpXQV_eval(phi, V, T, p);
    1631         245 :   GEN Sphi = FpXY_FpXQV_evalx(S1, V, T, p);
    1632         245 :   GEN S2 = FpXQX_FpXQXQ_eval(Sphi, S1, S, T, p);
    1633         245 :   return mkvec2(phi2, S2);
    1634             : }
    1635             : 
    1636             : static GEN
    1637          85 : FpXQXQ_autpow_mul(void * E, GEN x, GEN y)
    1638             : {
    1639          85 :   struct _FpXQXQ *D = (struct _FpXQXQ *)E;
    1640          85 :   GEN S = D->S, T = D->T, p = D->p;
    1641          85 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    1642          85 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    1643          85 :   long n = brent_kung_optpow(get_FpX_degree(T)-1, lgpol(S1)+1, 1);
    1644          85 :   GEN V = FpXQ_powers(phi2, n, T, p);
    1645          85 :   GEN phi3 = FpX_FpXQV_eval(phi1, V, T, p);
    1646          85 :   GEN Sphi = FpXY_FpXQV_evalx(S1, V, T, p);
    1647          85 :   GEN S3 = FpXQX_FpXQXQ_eval(Sphi, S2, S, T, p);
    1648          85 :   return mkvec2(phi3, S3);
    1649             : }
    1650             : 
    1651             : GEN
    1652         231 : FpXQXQ_autpow(GEN aut, long n, GEN S, GEN T, GEN p)
    1653             : {
    1654         231 :   pari_sp av = avma;
    1655             :   struct _FpXQXQ D;
    1656         231 :   T = FpX_get_red(T, p);
    1657         231 :   S = FpXQX_get_red(S, T, p);
    1658         231 :   D.S=S; D.T=T; D.p=p;
    1659         231 :   aut = gen_powu_i(aut,n,&D,FpXQXQ_autpow_sqr,FpXQXQ_autpow_mul);
    1660         231 :   return gerepilecopy(av, aut);
    1661             : }
    1662             : 
    1663             : static GEN
    1664           1 : FpXQXQ_auttrace_mul(void *E, GEN x, GEN y)
    1665             : {
    1666           1 :   struct _FpXQXQ *D = (struct _FpXQXQ *)E;
    1667           1 :   GEN S = D->S, T = D->T;
    1668           1 :   GEN p = D->p;
    1669           1 :   GEN S1 = gel(x,1), a1 = gel(x,2);
    1670           1 :   GEN S2 = gel(y,1), a2 = gel(y,2);
    1671           1 :   long n = brent_kung_optpow(maxss(degpol(S1),degpol(a1)),2,1);
    1672           1 :   GEN V = FpXQXQ_powers(S2, n, S, T, p);
    1673           1 :   GEN S3 = FpXQX_FpXQXQV_eval(S1, V, S, T, p);
    1674           1 :   GEN aS = FpXQX_FpXQXQV_eval(a1, V, S, T, p);
    1675           1 :   GEN a3 = FpXX_add(aS, a2, p);
    1676           1 :   return mkvec2(S3, a3);
    1677             : }
    1678             : 
    1679             : static GEN
    1680           1 : FpXQXQ_auttrace_sqr(void *E, GEN x)
    1681           1 : { return FpXQXQ_auttrace_mul(E, x, x); }
    1682             : 
    1683             : GEN
    1684           8 : FpXQXQ_auttrace(GEN aut, long n, GEN S, GEN T, GEN p)
    1685             : {
    1686           8 :   pari_sp av = avma;
    1687             :   struct _FpXQXQ D;
    1688           8 :   T = FpX_get_red(T, p);
    1689           8 :   S = FpXQX_get_red(S, T, p);
    1690           8 :   D.S=S; D.T=T; D.p=p;
    1691           8 :   aut = gen_powu_i(aut,n,&D,FpXQXQ_auttrace_sqr,FpXQXQ_auttrace_mul);
    1692           8 :   return gerepilecopy(av, aut);
    1693             : }
    1694             : 
    1695             : static GEN
    1696        1174 : FpXQXQ_autsum_mul(void *E, GEN x, GEN y)
    1697             : {
    1698        1174 :   struct _FpXQXQ *D = (struct _FpXQXQ *) E;
    1699        1174 :   GEN S = D->S, T = D->T, p = D->p;
    1700        1174 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    1701        1174 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    1702        1174 :   long n2 = brent_kung_optpow(get_FpX_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    1703        1174 :   GEN V2 = FpXQ_powers(phi2, n2, T, p);
    1704        1174 :   GEN phi3 = FpX_FpXQV_eval(phi1, V2, T, p);
    1705        1174 :   GEN Sphi = FpXY_FpXQV_evalx(S1, V2, T, p);
    1706        1174 :   GEN aphi = FpXY_FpXQV_evalx(a1, V2, T, p);
    1707        1174 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    1708        1174 :   GEN V = FpXQXQ_powers(S2, n, S, T, p);
    1709        1174 :   GEN S3 = FpXQX_FpXQXQV_eval(Sphi, V, S, T, p);
    1710        1174 :   GEN aS = FpXQX_FpXQXQV_eval(aphi, V, S, T, p);
    1711        1174 :   GEN a3 = FpXQXQ_mul(aS, a2, S, T, p);
    1712        1174 :   return mkvec3(phi3, S3, a3);
    1713             : }
    1714             : 
    1715             : static GEN
    1716        1134 : FpXQXQ_autsum_sqr(void * T, GEN x)
    1717        1134 : { return FpXQXQ_autsum_mul(T,x,x); }
    1718             : 
    1719             : GEN
    1720        1120 : FpXQXQ_autsum(GEN aut, long n, GEN S, GEN T, GEN p)
    1721             : {
    1722        1120 :   pari_sp av = avma;
    1723             :   struct _FpXQXQ D;
    1724        1120 :   T = FpX_get_red(T, p);
    1725        1120 :   S = FpXQX_get_red(S, T, p);
    1726        1120 :   D.S=S; D.T=T; D.p=p;
    1727        1120 :   aut = gen_powu_i(aut,n,&D,FpXQXQ_autsum_sqr,FpXQXQ_autsum_mul);
    1728        1120 :   return gerepilecopy(av, aut);
    1729             : }
    1730             : 
    1731             : GEN
    1732         130 : FpXQXn_mul(GEN x, GEN y, long n, GEN T, GEN p)
    1733             : {
    1734         130 :   pari_sp av = avma;
    1735             :   GEN z, kx, ky;
    1736             :   long d;
    1737         130 :   if (ZXX_is_ZX(y) && ZXX_is_ZX(x))
    1738           0 :     return FpXn_mul(x,y,n,p);
    1739         130 :   d = get_FpX_degree(T);
    1740         130 :   kx = ZXX_to_Kronecker(x, d);
    1741         130 :   ky = ZXX_to_Kronecker(y, d);
    1742         130 :   z = Kronecker_to_FpXQX(ZXn_mul(ky,kx,(2*d-1)*n), T, p);
    1743         130 :   return gerepileupto(av, z);
    1744             : }
    1745             : 
    1746             : GEN
    1747           0 : FpXQXn_sqr(GEN x, long n, GEN T, GEN p)
    1748             : {
    1749           0 :   pari_sp av = avma;
    1750             :   GEN z, kx;
    1751             :   long d;
    1752           0 :   if (ZXX_is_ZX(x)) return ZXn_sqr(x, n);
    1753           0 :   d = get_FpX_degree(T);
    1754           0 :   kx= ZXX_to_Kronecker(x, d);
    1755           0 :   z = Kronecker_to_FpXQX(ZXn_sqr(kx, (2*d-1)*n), T, p);
    1756           0 :   return gerepileupto(av, z);
    1757             : }
    1758             : 
    1759             : INLINE GEN
    1760           0 : FpXXn_red(GEN a, long n)
    1761           0 : { return RgXn_red_shallow(a, n); }
    1762             : 
    1763             : GEN
    1764           0 : FpXQXn_exp(GEN h, long e, GEN T, GEN p)
    1765             : {
    1766           0 :   pari_sp av = avma, av2;
    1767           0 :   long v = varn(h), n=1;
    1768           0 :   GEN f = pol_1(v), g = pol_1(v);
    1769           0 :   ulong mask = quadratic_prec_mask(e);
    1770           0 :   av2 = avma;
    1771           0 :   if (signe(h)==0 || degpol(h)<1 || !gequal0(gel(h,2)))
    1772           0 :     pari_err_DOMAIN("FpXQXn_exp","valuation", "<", gen_1, h);
    1773           0 :   for (;mask>1;)
    1774             :   {
    1775             :     GEN q, w;
    1776           0 :     long n2 = n;
    1777           0 :     n<<=1; if (mask & 1) n--;
    1778           0 :     mask >>= 1;
    1779           0 :     g = FpXX_sub(FpXX_mulu(g,2,p), FpXQXn_mul(f, FpXQXn_sqr(g, n2, T, p), n2, T, p), p);
    1780           0 :     q = FpXX_deriv(FpXXn_red(h,n2), p);
    1781           0 :     w = FpXX_add(q, FpXQXn_mul(g, FpXX_sub(FpXX_deriv(f, p), FpXQXn_mul(f,q,n-1, T, p), p),n-1, T, p), p);
    1782           0 :     f = FpXX_add(f, FpXQXn_mul(f, FpXX_sub(FpXXn_red(h, n), FpXX_integ(w, p), p), n, T, p), p);
    1783           0 :     if (gc_needed(av2,2))
    1784             :     {
    1785           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQXn_exp, e = %ld", n);
    1786           0 :       gerepileall(av2, 2, &f, &g);
    1787             :     }
    1788             :   }
    1789           0 :   return gerepileupto(av, f);
    1790             : }
    1791             : 
    1792             : /* (f*g) \/ x^n */
    1793             : static GEN
    1794           0 : FpXQX_mulhigh_i(GEN f, GEN g, long n, GEN T, GEN p)
    1795             : {
    1796           0 :   return RgX_shift_shallow(FpXQX_mul(f,g,T, p),-n);
    1797             : }
    1798             : 
    1799             : static GEN
    1800           0 : FpXQXn_mulhigh(GEN f, GEN g, long n2, long n, GEN T, GEN p)
    1801             : {
    1802           0 :   GEN F = RgX_blocks(f, n2, 2), fl = gel(F,1), fh = gel(F,2);
    1803           0 :   return FpXX_add(FpXQX_mulhigh_i(fl, g, n2, T, p), FpXQXn_mul(fh, g, n - n2, T, p), p);
    1804             : }
    1805             : 
    1806             : GEN
    1807           0 : FpXQXn_inv(GEN f, long e, GEN T, GEN p)
    1808             : {
    1809           0 :   pari_sp av = avma, av2;
    1810             :   ulong mask;
    1811             :   GEN W, a;
    1812           0 :   long v = varn(f), n = 1;
    1813             : 
    1814           0 :   if (!signe(f)) pari_err_INV("FpXXn_inv",f);
    1815           0 :   a = Fq_inv(gel(f,2), T, p);
    1816           0 :   if (e == 1) return scalarpol(a, v);
    1817           0 :   else if (e == 2)
    1818             :   {
    1819             :     GEN b;
    1820           0 :     if (degpol(f) <= 0) return scalarpol(a, v);
    1821           0 :     b = Fq_neg(gel(f,3),T,p);
    1822           0 :     if (signe(b)==0) return scalarpol(a, v);
    1823           0 :     if (!is_pm1(a)) b = Fq_mul(b, Fq_sqr(a, T, p), T, p);
    1824           0 :     W = deg1pol_shallow(b, a, v);
    1825           0 :     return gerepilecopy(av, W);
    1826             :   }
    1827           0 :   W = scalarpol_shallow(Fq_inv(gel(f,2), T, p),v);
    1828           0 :   mask = quadratic_prec_mask(e);
    1829           0 :   av2 = avma;
    1830           0 :   for (;mask>1;)
    1831             :   {
    1832             :     GEN u, fr;
    1833           0 :     long n2 = n;
    1834           0 :     n<<=1; if (mask & 1) n--;
    1835           0 :     mask >>= 1;
    1836           0 :     fr = FpXXn_red(f, n);
    1837           0 :     u = FpXQXn_mul(W, FpXQXn_mulhigh(fr, W, n2, n, T, p), n-n2, T, p);
    1838           0 :     W = FpXX_sub(W, RgX_shift_shallow(u, n2), p);
    1839           0 :     if (gc_needed(av2,2))
    1840             :     {
    1841           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"FpXQXn_inv, e = %ld", n);
    1842           0 :       W = gerepileupto(av2, W);
    1843             :     }
    1844             :   }
    1845           0 :   return gerepileupto(av, W);
    1846             : }

Generated by: LCOV version 1.13