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

Generated by: LCOV version 1.13