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 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.10.0 lcov report (development 21059-cbe0d6a) Lines: 817 899 90.9 %
Date: 2017-09-22 06:24:58 Functions: 101 106 95.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2012  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /* Not so fast arithmetic with polynomials over FpX */
      18             : 
      19             : /*******************************************************************/
      20             : /*                                                                 */
      21             : /*                             FpXX                                */
      22             : /*                                                                 */
      23             : /*******************************************************************/
      24             : /*Polynomials whose coefficients are either polynomials or integers*/
      25             : 
      26             : static ulong
      27      215446 : to_FlxqX(GEN P, GEN Q, GEN T, GEN p, GEN *pt_P, GEN *pt_Q, GEN *pt_T)
      28             : {
      29      215446 :   ulong pp = uel(p,2);
      30      215446 :   long v = get_FpX_var(T);
      31      215446 :   *pt_P = ZXX_to_FlxX(P, pp, v);
      32      215446 :   if (pt_Q) *pt_Q = ZXX_to_FlxX(Q, pp, v);
      33      215446 :   *pt_T = ZXT_to_FlxT(T, pp);
      34      215446 :   return pp;
      35             : }
      36             : 
      37             : static GEN
      38          81 : ZXX_copy(GEN a) { return gcopy(a); }
      39             : 
      40             : GEN
      41       32515 : FpXX_red(GEN z, GEN p)
      42             : {
      43             :   GEN res;
      44       32515 :   long i, l = lg(z);
      45       32515 :   res = cgetg(l,t_POL); res[1] = z[1];
      46      211148 :   for (i=2; i<l; i++)
      47             :   {
      48      178633 :     GEN zi = gel(z,i), c;
      49      178633 :     if (typ(zi)==t_INT)
      50        1799 :       c = modii(zi,p);
      51             :     else
      52             :     {
      53      176834 :       pari_sp av = avma;
      54      176834 :       c = FpX_red(zi,p);
      55      176834 :       switch(lg(c)) {
      56          14 :         case 2: avma = av; c = gen_0; break;
      57       16023 :         case 3: c = gerepilecopy(av, gel(c,2)); break;
      58             :       }
      59             :     }
      60      178633 :     gel(res,i) = c;
      61             :   }
      62       32515 :   return FpXX_renormalize(res,lg(res));
      63             : }
      64             : GEN
      65      403031 : FpXX_add(GEN x, GEN y, GEN p)
      66             : {
      67             :   long i,lz;
      68             :   GEN z;
      69      403031 :   long lx=lg(x);
      70      403031 :   long ly=lg(y);
      71      403031 :   if (ly>lx) swapspec(x,y, lx,ly);
      72      403031 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
      73      403031 :   for (i=2; i<ly; i++) gel(z,i) = Fq_add(gel(x,i), gel(y,i), NULL, p);
      74      403031 :   for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
      75      403031 :   return FpXX_renormalize(z, lz);
      76             : }
      77             : GEN
      78       13872 : FpXX_sub(GEN x, GEN y, GEN p)
      79             : {
      80             :   long i,lz;
      81             :   GEN z;
      82       13872 :   long lx=lg(x);
      83       13872 :   long ly=lg(y);
      84       13872 :   if (ly <= lx)
      85             :   {
      86       12058 :     lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
      87       12058 :     for (i=2; i<ly; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
      88       12058 :     for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
      89             :   }
      90             :   else
      91             :   {
      92        1814 :     lz = ly; z = cgetg(lz, t_POL); z[1]=x[1];
      93        1814 :     for (i=2; i<lx; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
      94        1814 :     for (   ; i<ly; i++) gel(z,i) = Fq_neg(gel(y,i), NULL, p);
      95             :   }
      96       13872 :   return FpXX_renormalize(z, lz);
      97             : }
      98             : 
      99             : static GEN
     100       47545 : FpXX_subspec(GEN x, GEN y, GEN p, long nx, long ny)
     101             : {
     102             :   long i,lz;
     103             :   GEN z;
     104       47545 :   if (ny <= nx)
     105             :   {
     106       47545 :     lz = nx+2; z = cgetg(lz, t_POL)+2;
     107       47545 :     for (i=0; i<ny; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
     108       47545 :     for (   ; i<nx; i++) gel(z,i) = gcopy(gel(x,i));
     109             :   }
     110             :   else
     111             :   {
     112           0 :     lz = ny+2; z = cgetg(lz, t_POL)+2;
     113           0 :     for (i=0; i<nx; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
     114           0 :     for (   ; i<ny; i++) gel(z,i) = Fq_neg(gel(y,i), NULL, p);
     115             :   }
     116       47545 :   return FpXX_renormalize(z-2, lz);
     117             : }
     118             : 
     119             : GEN
     120         471 : FpXX_neg(GEN x, GEN p)
     121             : {
     122         471 :   long i, lx = lg(x);
     123         471 :   GEN y = cgetg(lx,t_POL);
     124         471 :   y[1] = x[1];
     125         471 :   for(i=2; i<lx; i++) gel(y,i) = Fq_neg(gel(x,i), NULL, p);
     126         471 :   return FpXX_renormalize(y, lx);
     127             : }
     128             : 
     129             : GEN
     130       63996 : FpXX_Fp_mul(GEN P, GEN u, GEN p)
     131             : {
     132             :   long i, lP;
     133       63996 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     134      471980 :   for(i=2; i<lP; i++)
     135             :   {
     136      407984 :     GEN x = gel(P,i);
     137      407984 :     gel(res,i) = typ(x)==t_INT? Fp_mul(x,u,p): FpX_Fp_mul(x,u,p);
     138             :   }
     139       63996 :   return FpXX_renormalize(res,lP);
     140             : }
     141             : 
     142             : GEN
     143       51908 : FpXX_mulu(GEN P, ulong u, GEN p)
     144             : {
     145             :   long i, lP;
     146       51908 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     147      276753 :   for(i=2; i<lP; i++)
     148             :   {
     149      224845 :     GEN x = gel(P,i);
     150      224845 :     gel(res,i) = typ(x)==t_INT? Fp_mulu(x,u,p): FpX_mulu(x,u,p);
     151             :   }
     152       51908 :   return FpXX_renormalize(res,lP);
     153             : }
     154             : 
     155             : GEN
     156      270117 : FpXX_deriv(GEN P, GEN p)
     157             : {
     158      270117 :   long i, l = lg(P)-1;
     159             :   GEN res;
     160             : 
     161      270117 :   if (l < 3) return pol_0(varn(P));
     162      265238 :   res = cgetg(l, t_POL);
     163      265238 :   res[1] = P[1];
     164      946869 :   for (i=2; i<l ; i++)
     165             :   {
     166      681631 :     GEN x = gel(P,i+1);
     167      681631 :     gel(res,i) = typ(x)==t_INT? Fp_mulu(x,i-1,p): FpX_mulu(x,i-1,p);
     168             :   }
     169      265238 :   return FpXX_renormalize(res, l);
     170             : }
     171             : 
     172             : /*******************************************************************/
     173             : /*                                                                 */
     174             : /*                             (Fp[X]/(Q))[Y]                      */
     175             : /*                                                                 */
     176             : /*******************************************************************/
     177             : 
     178             : static GEN
     179      384100 : get_FpXQX_red(GEN T, GEN *B)
     180             : {
     181      384100 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
     182       58494 :   *B = gel(T,1); return gel(T,2);
     183             : }
     184             : 
     185             : GEN
     186          16 : random_FpXQX(long d1, long v, GEN T, GEN p)
     187             : {
     188          16 :   long dT = get_FpX_degree(T), vT = get_FpX_var(T);
     189          16 :   long i, d = d1+2;
     190          16 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
     191          16 :   for (i=2; i<d; i++) gel(y,i) = random_FpX(dT, vT, p);
     192          16 :   return FpXQX_renormalize(y,d);
     193             : }
     194             : 
     195             : /*Not stack clean*/
     196             : GEN
     197      522621 : Kronecker_to_FpXQX(GEN Z, GEN T, GEN p)
     198             : {
     199      522621 :   long i,j,lx,l, N = (get_FpX_degree(T)<<1) + 1;
     200      522621 :   GEN x, t = cgetg(N,t_POL), z = FpX_red(Z, p);
     201      522621 :   t[1] = evalvarn(get_FpX_var(T));
     202      522621 :   l = lg(z); lx = (l-2) / (N-2);
     203      522621 :   x = cgetg(lx+3,t_POL);
     204      522621 :   x[1] = z[1];
     205    13808489 :   for (i=2; i<lx+2; i++)
     206             :   {
     207    13285868 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     208    13285868 :     z += (N-2);
     209    13285868 :     gel(x,i) = FpX_rem(FpX_renormalize(t,N), T,p);
     210             :   }
     211      522621 :   N = (l-2) % (N-2) + 2;
     212      522621 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     213      522621 :   gel(x,i) = FpX_rem(FpX_renormalize(t,N), T,p);
     214      522621 :   return FpXQX_renormalize(x, i+1);
     215             : }
     216             : 
     217             : /* shallow, n = deg(T) */
     218             : GEN
     219       99127 : Kronecker_to_ZXX(GEN z, long n, long v)
     220             : {
     221       99127 :   long i,j,lx,l, N = (n<<1)+1;
     222             :   GEN x, t;
     223       99127 :   l = lg(z); lx = (l-2) / (N-2);
     224       99127 :   x = cgetg(lx+3,t_POL);
     225       99127 :   x[1] = z[1];
     226     1691837 :   for (i=2; i<lx+2; i++)
     227             :   {
     228     1592710 :     t = cgetg(N,t_POL); t[1] = evalvarn(v);
     229     1592710 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     230     1592710 :     z += (N-2);
     231     1592710 :     gel(x,i) = ZX_renormalize(t,N);
     232             :   }
     233       99127 :   N = (l-2) % (N-2) + 2;
     234       99127 :   t = cgetg(N,t_POL); t[1] = evalvarn(v);
     235       99127 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     236       99127 :   gel(x,i) = ZX_renormalize(t,N);
     237       99127 :   return ZXX_renormalize(x, i+1);
     238             : }
     239             : /* shallow */
     240             : GEN
     241      250556 : ZXX_mul_Kronecker(GEN x, GEN y, long n)
     242      250556 : { return ZX_mul(ZXX_to_Kronecker(x,n), ZXX_to_Kronecker(y,n)); }
     243             : 
     244             : GEN
     245        3487 : ZXX_sqr_Kronecker(GEN x, long n)
     246        3487 : { return ZX_sqr(ZXX_to_Kronecker(x,n)); }
     247             : 
     248             : GEN
     249      160518 : FpXQX_red(GEN z, GEN T, GEN p)
     250             : {
     251      160518 :   long i, l = lg(z);
     252      160518 :   GEN res = cgetg(l,t_POL); res[1] = z[1];
     253     1601339 :   for(i=2;i<l;i++)
     254     1440821 :     if (typ(gel(z,i)) == t_INT)
     255       26658 :       gel(res,i) = modii(gel(z,i),p);
     256             :     else
     257     1414163 :       gel(res,i) = FpXQ_red(gel(z,i),T,p);
     258      160518 :   return FpXQX_renormalize(res,l);
     259             : }
     260             : 
     261             : /* z in Z[X], return z * Mod(1,p), normalized*/
     262             : GEN
     263          42 : FpXQX_to_mod(GEN z, GEN T, GEN p)
     264             : {
     265          42 :   long i,l = lg(z);
     266          42 :   GEN x = cgetg(l, t_POL);
     267          42 :   x[1] = z[1];
     268          42 :   if (l == 2) return x;
     269          42 :   T = FpX_to_mod(T, p);
     270         196 :   for (i=2; i<l; i++)
     271             :   {
     272         154 :     GEN zi = gel(z,i);
     273         154 :     gel(x,i) = typ(zi) == t_POL? mkpolmod(FpX_to_mod(zi, p), T): icopy(zi);
     274             :   }
     275          42 :   return normalizepol_lg(x,l);
     276             : }
     277             : 
     278             : static int
     279      933243 : ZXX_is_ZX_spec(GEN a,long na)
     280             : {
     281             :   long i;
     282     1099299 :   for(i=0;i<na;i++)
     283     1085540 :     if(typ(gel(a,i))!=t_INT) return 0;
     284       13759 :   return 1;
     285             : }
     286             : 
     287             : static int
     288      133393 : ZXX_is_ZX(GEN a) { return ZXX_is_ZX_spec(a+2,lgpol(a)); }
     289             : 
     290             : static GEN
     291       42933 : FpXX_FpX_mulspec(GEN P, GEN U, GEN p, long v, long lU)
     292             : {
     293       42933 :   long i, lP =lg(P);
     294             :   GEN res;
     295       42933 :   res = cgetg(lP, t_POL); res[1] = P[1];
     296     1801996 :   for(i=2; i<lP; i++)
     297             :   {
     298     1759063 :     GEN Pi = gel(P,i);
     299     3511667 :     gel(res,i) = typ(Pi)==t_INT? FpX_Fp_mulspec(U, Pi, p, lU):
     300     1752604 :                                  FpX_mulspec(U, Pi+2, p, lU, lgpol(Pi));
     301     1759063 :     setvarn(gel(res,i),v);
     302             :   }
     303       42933 :   return FpXQX_renormalize(res,lP);
     304             : }
     305             : 
     306             : GEN
     307       36877 : FpXX_FpX_mul(GEN P, GEN U, GEN p)
     308       36877 : { return FpXX_FpX_mulspec(P,U+2,p,varn(U),lgpol(U)); }
     309             : 
     310             : static GEN
     311        6056 : FpXY_FpY_mulspec(GEN x, GEN y, GEN T, GEN p, long lx, long ly)
     312             : {
     313        6056 :   pari_sp av = avma;
     314        6056 :   long v = fetch_var();
     315        6056 :   GEN z = RgXY_swapspec(x,get_FpX_degree(T)-1,v,lx);
     316        6056 :   z = FpXX_FpX_mulspec(z,y,p,v,ly);
     317        6056 :   z = RgXY_swapspec(z+2,lx+ly+3,get_FpX_var(T),lgpol(z));
     318        6056 :   (void)delete_var(); return gerepilecopy(av,z);
     319             : }
     320             : 
     321             : static GEN
     322      399925 : FpXQX_mulspec(GEN x, GEN y, GEN T, GEN p, long lx, long ly)
     323             : {
     324      399925 :   pari_sp av = avma;
     325             :   GEN z, kx, ky;
     326             :   long n;
     327      399925 :   if (ZXX_is_ZX_spec(y,ly))
     328             :   {
     329        6512 :     if (ZXX_is_ZX_spec(x,lx))
     330        3062 :       return FpX_mulspec(x,y,p,lx,ly);
     331             :     else
     332        3450 :       return FpXY_FpY_mulspec(x,y,T,p,lx,ly);
     333      393413 :   } else if (ZXX_is_ZX_spec(x,lx))
     334        2606 :       return FpXY_FpY_mulspec(y,x,T,p,ly,lx);
     335      390807 :   n = get_FpX_degree(T);
     336      390807 :   kx = ZXX_to_Kronecker_spec(x, lx, n);
     337      390807 :   ky = ZXX_to_Kronecker_spec(y, ly, n);
     338      390807 :   z = Kronecker_to_FpXQX(ZX_mul(ky,kx), T, p);
     339      390807 :   return gerepileupto(av, z);
     340             : }
     341             : 
     342             : GEN
     343      302525 : FpXQX_mul(GEN x, GEN y, GEN T, GEN p)
     344             : {
     345      302525 :   GEN z = FpXQX_mulspec(x+2,y+2,T,p,lgpol(x),lgpol(y));
     346      302525 :   setvarn(z,varn(x)); return z;
     347             : }
     348             : 
     349             : GEN
     350      133393 : FpXQX_sqr(GEN x, GEN T, GEN p)
     351             : {
     352      133393 :   pari_sp av = avma;
     353             :   GEN z, kx;
     354      133393 :   if (ZXX_is_ZX(x)) return ZX_sqr(x);
     355      131814 :   kx= ZXX_to_Kronecker(x, get_FpX_degree(T));
     356      131814 :   z = Kronecker_to_FpXQX(ZX_sqr(kx), T, p);
     357      131814 :   return gerepileupto(av, z);
     358             : }
     359             : 
     360             : GEN
     361      152695 : FpXQX_FpXQ_mul(GEN P, GEN U, GEN T, GEN p)
     362             : {
     363             :   long i, lP;
     364             :   GEN res;
     365      152695 :   res = cgetg_copy(P, &lP); res[1] = P[1];
     366      683679 :   for(i=2; i<lP; i++)
     367      942702 :     gel(res,i) = typ(gel(P,i))==t_INT? FpX_Fp_mul(U, gel(P,i), p):
     368      411718 :                                        FpXQ_mul(U, gel(P,i), T,p);
     369      152695 :   return FpXQX_renormalize(res,lP);
     370             : }
     371             : 
     372             : /* x and y in Z[Y][X]. Assume T irreducible mod p */
     373             : static GEN
     374      122690 : FpXQX_divrem_basecase(GEN x, GEN y, GEN T, GEN p, GEN *pr)
     375             : {
     376             :   long vx, dx, dy, dy1, dz, i, j, sx, lr;
     377             :   pari_sp av0, av, tetpil;
     378             :   GEN z,p1,rem,lead;
     379             : 
     380      122690 :   if (!signe(y)) pari_err_INV("FpX_divrem",y);
     381      122690 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
     382      122690 :   if (dx < dy)
     383             :   {
     384           8 :     if (pr)
     385             :     {
     386           0 :       av0 = avma; x = FpXQX_red(x, T, p);
     387           0 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: pol_0(vx); }
     388           0 :       if (pr == ONLY_REM) return x;
     389           0 :       *pr = x;
     390             :     }
     391           8 :     return pol_0(vx);
     392             :   }
     393      122682 :   lead = leading_coeff(y);
     394      122682 :   if (!dy) /* y is constant */
     395             :   {
     396         866 :     if (pr && pr != ONLY_DIVIDES)
     397             :     {
     398         635 :       if (pr == ONLY_REM) return pol_0(vx);
     399           4 :       *pr = pol_0(vx);
     400             :     }
     401         235 :     if (gequal1(lead)) return FpXQX_red(x,T,p);
     402         179 :     av0 = avma; x = FqX_Fq_mul(x, Fq_inv(lead, T,p), T,p);
     403         179 :     return gerepileupto(av0,x);
     404             :   }
     405      121816 :   av0 = avma; dz = dx-dy;
     406      121816 :   lead = gequal1(lead)? NULL: gclone(Fq_inv(lead,T,p));
     407      121816 :   avma = av0;
     408      121816 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
     409      121816 :   x += 2; y += 2; z += 2;
     410      121816 :   for (dy1=dy-1; dy1>=0 && !signe(gel(y, dy1)); dy1--);
     411             : 
     412      121816 :   p1 = gel(x,dx); av = avma;
     413      121816 :   gel(z,dz) = lead? gerepileupto(av, Fq_mul(p1,lead, T, p)): gcopy(p1);
     414      391707 :   for (i=dx-1; i>=dy; i--)
     415             :   {
     416      269891 :     av=avma; p1=gel(x,i);
     417      915500 :     for (j=i-dy1; j<=i && j<=dz; j++)
     418      645609 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j),NULL,p),NULL,p);
     419      269891 :     if (lead) p1 = Fq_mul(p1, lead, NULL,p);
     420      269891 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,Fq_red(p1,T,p));
     421             :   }
     422      121816 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
     423             : 
     424      120694 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     425      128793 :   for (sx=0; ; i--)
     426             :   {
     427      128793 :     p1 = gel(x,i);
     428      528371 :     for (j=maxss(0,i-dy1); j<=i && j<=dz; j++)
     429      399578 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j),NULL,p),NULL,p);
     430      128793 :     tetpil=avma; p1 = Fq_red(p1, T, p); if (signe(p1)) { sx = 1; break; }
     431        9243 :     if (!i) break;
     432        8099 :     avma=av;
     433        8099 :   }
     434      120694 :   if (pr == ONLY_DIVIDES)
     435             :   {
     436           0 :     if (lead) gunclone(lead);
     437           0 :     if (sx) { avma=av0; return NULL; }
     438           0 :     avma = (pari_sp)rem; return z-2;
     439             :   }
     440      120694 :   lr=i+3; rem -= lr;
     441      120694 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     442      120694 :   rem[1] = z[-1];
     443      120694 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
     444      120694 :   rem += 2; gel(rem,i) = p1;
     445      905527 :   for (i--; i>=0; i--)
     446             :   {
     447      784833 :     av=avma; p1 = gel(x,i);
     448     2557193 :     for (j=maxss(0,i-dy1); j<=i && j<=dz; j++)
     449     1772360 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j), NULL,p), NULL,p);
     450      784833 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, Fq_red(p1, T, p));
     451             :   }
     452      120694 :   rem -= 2;
     453      120694 :   if (lead) gunclone(lead);
     454      120694 :   if (!sx) (void)FpXQX_renormalize(rem, lr);
     455      120694 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
     456        6661 :   *pr = rem; return z-2;
     457             : }
     458             : 
     459             : static GEN
     460          76 : FpXQX_halfgcd_basecase(GEN a, GEN b, GEN T, GEN p)
     461             : {
     462          76 :   pari_sp av=avma;
     463             :   GEN u,u1,v,v1;
     464          76 :   long vx = varn(a);
     465          76 :   long n = lgpol(a)>>1;
     466          76 :   u1 = v = pol_0(vx);
     467          76 :   u = v1 = pol_1(vx);
     468         891 :   while (lgpol(b)>n)
     469             :   {
     470         739 :     GEN r, q = FpXQX_divrem(a,b, T, p, &r);
     471         739 :     a = b; b = r; swap(u,u1); swap(v,v1);
     472         739 :     u1 = FpXX_sub(u1, FpXQX_mul(u, q, T, p), p);
     473         739 :     v1 = FpXX_sub(v1, FpXQX_mul(v, q ,T, p), p);
     474         739 :     if (gc_needed(av,2))
     475             :     {
     476           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_halfgcd (d = %ld)",degpol(b));
     477           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     478             :     }
     479             :   }
     480          76 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     481             : }
     482             : static GEN
     483         136 : FpXQX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN T, GEN p)
     484             : {
     485         136 :   return FpXX_add(FpXQX_mul(u, x, T, p),FpXQX_mul(v, y, T, p), p);
     486             : }
     487             : 
     488             : static GEN
     489          68 : FpXQXM_FpXQX_mul2(GEN M, GEN x, GEN y, GEN T, GEN p)
     490             : {
     491          68 :   GEN res = cgetg(3, t_COL);
     492          68 :   gel(res, 1) = FpXQX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, T, p);
     493          68 :   gel(res, 2) = FpXQX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, T, p);
     494          68 :   return res;
     495             : }
     496             : 
     497             : static GEN
     498          56 : FpXQXM_mul2(GEN A, GEN B, GEN T, GEN p)
     499             : {
     500          56 :   GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
     501          56 :   GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
     502          56 :   GEN M1 = FpXQX_mul(FpXX_add(A11,A22, p), FpXX_add(B11,B22, p), T, p);
     503          56 :   GEN M2 = FpXQX_mul(FpXX_add(A21,A22, p), B11, T, p);
     504          56 :   GEN M3 = FpXQX_mul(A11, FpXX_sub(B12,B22, p), T, p);
     505          56 :   GEN M4 = FpXQX_mul(A22, FpXX_sub(B21,B11, p), T, p);
     506          56 :   GEN M5 = FpXQX_mul(FpXX_add(A11,A12, p), B22, T, p);
     507          56 :   GEN M6 = FpXQX_mul(FpXX_sub(A21,A11, p), FpXX_add(B11,B12, p), T, p);
     508          56 :   GEN M7 = FpXQX_mul(FpXX_sub(A12,A22, p), FpXX_add(B21,B22, p), T, p);
     509          56 :   GEN T1 = FpXX_add(M1,M4, p), T2 = FpXX_sub(M7,M5, p);
     510          56 :   GEN T3 = FpXX_sub(M1,M2, p), T4 = FpXX_add(M3,M6, p);
     511          56 :   retmkmat2(mkcol2(FpXX_add(T1,T2, p), FpXX_add(M2,M4, p)),
     512             :             mkcol2(FpXX_add(M3,M5, p), FpXX_add(T3,T4, p)));
     513             : }
     514             : /* Return [0,1;1,-q]*M */
     515             : static GEN
     516          56 : FpXQX_FpXQXM_qmul(GEN q, GEN M, GEN T, GEN p)
     517             : {
     518          56 :   GEN u, v, res = cgetg(3, t_MAT);
     519          56 :   u = FpXX_sub(gcoeff(M,1,1), FpXQX_mul(gcoeff(M,2,1), q, T, p), p);
     520          56 :   gel(res,1) = mkcol2(gcoeff(M,2,1), u);
     521          56 :   v = FpXX_sub(gcoeff(M,1,2), FpXQX_mul(gcoeff(M,2,2), q, T, p), p);
     522          56 :   gel(res,2) = mkcol2(gcoeff(M,2,2), v);
     523          56 :   return res;
     524             : }
     525             : 
     526             : static GEN
     527           0 : matid2_FpXQXM(long v)
     528             : {
     529           0 :   retmkmat2(mkcol2(pol_1(v),pol_0(v)),
     530             :             mkcol2(pol_0(v),pol_1(v)));
     531             : }
     532             : 
     533             : static GEN
     534          56 : FpXQX_halfgcd_split(GEN x, GEN y, GEN T, GEN p)
     535             : {
     536          56 :   pari_sp av=avma;
     537             :   GEN R, S, V;
     538             :   GEN y1, r, q;
     539          56 :   long l = lgpol(x), n = l>>1, k;
     540          56 :   if (lgpol(y)<=n) return matid2_FpXQXM(varn(x));
     541          56 :   R = FpXQX_halfgcd(RgX_shift_shallow(x,-n),RgX_shift_shallow(y,-n), T, p);
     542          56 :   V = FpXQXM_FpXQX_mul2(R,x,y, T, p); y1 = gel(V,2);
     543          56 :   if (lgpol(y1)<=n) return gerepilecopy(av, R);
     544          56 :   q = FpXQX_divrem(gel(V,1), y1, T, p, &r);
     545          56 :   k = 2*n-degpol(y1);
     546          56 :   S = FpXQX_halfgcd(RgX_shift_shallow(y1,-k), RgX_shift_shallow(r,-k), T, p);
     547          56 :   return gerepileupto(av, FpXQXM_mul2(S,FpXQX_FpXQXM_qmul(q,R, T, p), T, p));
     548             : }
     549             : 
     550             : /* Return M in GL_2(Fp[X]) such that:
     551             : if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
     552             : */
     553             : 
     554             : static GEN
     555         132 : FpXQX_halfgcd_i(GEN x, GEN y, GEN T, GEN p)
     556             : {
     557         132 :   if (lg(x)<=FpXQX_HALFGCD_LIMIT) return FpXQX_halfgcd_basecase(x, y, T, p);
     558          56 :   return FpXQX_halfgcd_split(x, y, T, p);
     559             : }
     560             : 
     561             : GEN
     562         132 : FpXQX_halfgcd(GEN x, GEN y, GEN T, GEN p)
     563             : {
     564         132 :   pari_sp av = avma;
     565             :   GEN M,q,r;
     566         132 :   if (lgefint(p)==3)
     567             :   {
     568           0 :     ulong pp = to_FlxqX(x, y, T, p, &x, &y, &T);
     569           0 :     M = FlxXM_to_ZXXM(FlxqX_halfgcd(x, y, T, pp));
     570             :   }
     571             :   else
     572             :   {
     573         132 :     if (!signe(x))
     574             :     {
     575           0 :       long v = varn(x);
     576           0 :       retmkmat2(mkcol2(pol_0(v),pol_1(v)),
     577             :                 mkcol2(pol_1(v),pol_0(v)));
     578             :     }
     579         132 :     if (degpol(y)<degpol(x)) return FpXQX_halfgcd_i(x, y, T, p);
     580           8 :     q = FpXQX_divrem(y, x, T, p, &r);
     581           8 :     M = FpXQX_halfgcd_i(x, r, T, p);
     582           8 :     gcoeff(M,1,1) = FpXX_sub(gcoeff(M,1,1), FpXQX_mul(q, gcoeff(M,1,2), T, p), p);
     583           8 :     gcoeff(M,2,1) = FpXX_sub(gcoeff(M,2,1), FpXQX_mul(q, gcoeff(M,2,2), T, p), p);
     584             :   }
     585           8 :   return gerepilecopy(av, M);
     586             : }
     587             : 
     588             : static GEN
     589        1895 : FpXQX_gcd_basecase(GEN a, GEN b, GEN T, GEN p)
     590             : {
     591        1895 :   pari_sp av = avma, av0=avma;
     592       22737 :   while (signe(b))
     593             :   {
     594             :     GEN c;
     595       18947 :     if (gc_needed(av0,2))
     596             :     {
     597           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_gcd (d = %ld)",degpol(b));
     598           0 :       gerepileall(av0,2, &a,&b);
     599             :     }
     600       18947 :     av = avma; c = FpXQX_rem(a, b, T, p); a=b; b=c;
     601             :   }
     602        1895 :   avma = av; return a;
     603             : }
     604             : 
     605             : GEN
     606       11223 : FpXQX_gcd(GEN x, GEN y, GEN T, GEN p)
     607             : {
     608       11223 :   pari_sp av = avma;
     609       11223 :   if (lgefint(p) == 3)
     610             :   {
     611             :     GEN Pl, Ql, Tl, U;
     612        9272 :     ulong pp = to_FlxqX(x, y, T, p, &Pl, &Ql, &Tl);
     613        9272 :     U  = FlxqX_gcd(Pl, Ql, Tl, pp);
     614        9272 :     return gerepileupto(av, FlxX_to_ZXX(U));
     615             :   }
     616        1951 :   x = FpXQX_red(x, T, p);
     617        1951 :   y = FpXQX_red(y, T, p);
     618        1951 :   if (!signe(x)) return gerepileupto(av, y);
     619        3802 :   while (lg(y)>FpXQX_GCD_LIMIT)
     620             :   {
     621             :     GEN c;
     622          12 :     if (lgpol(y)<=(lgpol(x)>>1))
     623             :     {
     624           0 :       GEN r = FpXQX_rem(x, y, T, p);
     625           0 :       x = y; y = r;
     626             :     }
     627          12 :     c = FpXQXM_FpXQX_mul2(FpXQX_halfgcd(x,y, T, p), x, y, T, p);
     628          12 :     x = gel(c,1); y = gel(c,2);
     629          12 :     gerepileall(av,2,&x,&y);
     630             :   }
     631        1895 :   return gerepileupto(av, FpXQX_gcd_basecase(x, y, T, p));
     632             : }
     633             : 
     634             : static GEN
     635           0 : FpXQX_extgcd_basecase(GEN a, GEN b, GEN T, GEN p, GEN *ptu, GEN *ptv)
     636             : {
     637           0 :   pari_sp av=avma;
     638             :   GEN u,v,d,d1,v1;
     639           0 :   long vx = varn(a);
     640           0 :   d = a; d1 = b;
     641           0 :   v = pol_0(vx); v1 = pol_1(vx);
     642           0 :   while (signe(d1))
     643             :   {
     644           0 :     GEN r, q = FpXQX_divrem(d, d1, T, p, &r);
     645           0 :     v = FpXX_sub(v,FpXQX_mul(q,v1,T, p),p);
     646           0 :     u=v; v=v1; v1=u;
     647           0 :     u=r; d=d1; d1=u;
     648           0 :     if (gc_needed(av,2))
     649             :     {
     650           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXQX_extgcd (d = %ld)",degpol(d));
     651           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     652             :     }
     653             :   }
     654           0 :   if (ptu) *ptu = FpXQX_div(FpXX_sub(d,FpXQX_mul(b,v, T, p), p), a, T, p);
     655           0 :   *ptv = v; return d;
     656             : }
     657             : 
     658             : static GEN
     659           0 : FpXQX_extgcd_halfgcd(GEN x, GEN y, GEN T, GEN p, GEN *ptu, GEN *ptv)
     660             : {
     661           0 :   pari_sp av=avma;
     662           0 :   GEN u,v,R = matid2_FpXQXM(varn(x));
     663           0 :   while (lg(y)>FpXQX_EXTGCD_LIMIT)
     664             :   {
     665             :     GEN M, c;
     666           0 :     if (lgpol(y)<=(lgpol(x)>>1))
     667             :     {
     668           0 :       GEN r, q = FpXQX_divrem(x, y, T, p, &r);
     669           0 :       x = y; y = r;
     670           0 :       R = FpXQX_FpXQXM_qmul(q, R, T, p);
     671             :     }
     672           0 :     M = FpXQX_halfgcd(x,y, T, p);
     673           0 :     c = FpXQXM_FpXQX_mul2(M, x,y, T, p);
     674           0 :     R = FpXQXM_mul2(M, R, T, p);
     675           0 :     x = gel(c,1); y = gel(c,2);
     676           0 :     gerepileall(av,3,&x,&y,&R);
     677             :   }
     678           0 :   y = FpXQX_extgcd_basecase(x,y, T, p, &u,&v);
     679           0 :   if (ptu) *ptu = FpXQX_addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1), T, p);
     680           0 :   *ptv = FpXQX_addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2), T, p);
     681           0 :   return y;
     682             : }
     683             : 
     684             : /* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
     685             :  * ux + vy = gcd (mod T,p) */
     686             : GEN
     687        5901 : FpXQX_extgcd(GEN x, GEN y, GEN T, GEN p, GEN *ptu, GEN *ptv)
     688             : {
     689             :   GEN d;
     690        5901 :   pari_sp ltop=avma;
     691        5901 :   if (lgefint(p) == 3)
     692             :   {
     693             :     GEN Pl, Ql, Tl, Dl;
     694        5901 :     ulong pp = to_FlxqX(x, y, T, p, &Pl, &Ql, &Tl);
     695        5901 :     Dl = FlxqX_extgcd(Pl, Ql, Tl, pp, ptu, ptv);
     696        5901 :     if (ptu) *ptu = FlxX_to_ZXX(*ptu);
     697        5901 :     *ptv = FlxX_to_ZXX(*ptv);
     698        5901 :     d = FlxX_to_ZXX(Dl);
     699             :   }
     700             :   else
     701             :   {
     702           0 :     x = FpXQX_red(x, T, p);
     703           0 :     y = FpXQX_red(y, T, p);
     704           0 :     if (lg(y)>FpXQX_EXTGCD_LIMIT)
     705           0 :       d = FpXQX_extgcd_halfgcd(x, y, T, p, ptu, ptv);
     706             :     else
     707           0 :       d = FpXQX_extgcd_basecase(x, y, T, p, ptu, ptv);
     708             :   }
     709        5901 :   gerepileall(ltop,ptu?3:2,&d,ptv,ptu);
     710        5901 :   return d;
     711             : }
     712             : 
     713             : GEN
     714          68 : FpXQX_dotproduct(GEN x, GEN y, GEN T, GEN p)
     715             : {
     716          68 :   long i, l = minss(lg(x), lg(y));
     717             :   pari_sp av;
     718             :   GEN c;
     719          68 :   if (l == 2) return gen_0;
     720          68 :   av = avma; c = gmul(gel(x,2),gel(y,2));
     721          68 :   for (i=3; i<l; i++) c = gadd(c, gmul(gel(x,i),gel(y,i)));
     722          68 :   return gerepileupto(av, Fq_red(c,T,p));
     723             : }
     724             : 
     725             : /***********************************************************************/
     726             : /**                                                                   **/
     727             : /**                       Barrett reduction                           **/
     728             : /**                                                                   **/
     729             : /***********************************************************************/
     730             : 
     731             : /* Return new lgpol */
     732             : static long
     733       98555 : ZXX_lgrenormalizespec(GEN x, long lx)
     734             : {
     735             :   long i;
     736       99129 :   for (i = lx-1; i>=0; i--)
     737       99129 :     if (signe(gel(x,i))) break;
     738       98555 :   return i+1;
     739             : }
     740             : 
     741             : static GEN
     742         979 : FpXQX_invBarrett_basecase(GEN S, GEN T, GEN p)
     743             : {
     744         979 :   long i, l=lg(S)-1, lr = l-1, k;
     745         979 :   GEN r=cgetg(lr, t_POL); r[1]=S[1];
     746         979 :   gel(r,2) = gen_1;
     747       17679 :   for (i=3; i<lr; i++)
     748             :   {
     749       16700 :     pari_sp av = avma;
     750       16700 :     GEN u = gel(S,l-i+2);
     751      174658 :     for (k=3; k<i; k++)
     752      157958 :       u = Fq_add(u, Fq_mul(gel(S,l-i+k), gel(r,k), NULL, p), NULL, p);
     753       16700 :     gel(r,i) = gerepileupto(av, Fq_red(Fq_neg(u, NULL, p), T, p));
     754             :   }
     755         979 :   return FpXQX_renormalize(r,lr);
     756             : }
     757             : 
     758             : INLINE GEN
     759       95090 : FpXX_recipspec(GEN x, long l, long n)
     760             : {
     761       95090 :   return RgX_recipspec_shallow(x, l, n);
     762             : }
     763             : 
     764             : static GEN
     765         182 : FpXQX_invBarrett_Newton(GEN S, GEN T, GEN p)
     766             : {
     767         182 :   pari_sp av = avma;
     768         182 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
     769         182 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
     770         182 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
     771         182 :   for (i=0;i<l;i++) gel(x,i) = gen_0;
     772         182 :   q = RgX_recipspec_shallow(S+2,l+1,l+1); lQ = lgpol(q); q+=2;
     773             :   /* We work on _spec_ FpX's, all the l[xzq] below are lgpol's */
     774             : 
     775             :   /* initialize */
     776         182 :   gel(x,0) = Fq_inv(gel(q,0), T, p);
     777         182 :   if (lQ>1) gel(q,1) = Fq_red(gel(q,1), T, p);
     778         182 :   if (lQ>1 && signe(gel(q,1)))
     779         182 :   {
     780         182 :     GEN u = gel(q, 1);
     781         182 :     if (!gequal1(gel(x,0))) u = Fq_mul(u, Fq_sqr(gel(x,0), T, p), T, p);
     782         182 :     gel(x,1) = Fq_neg(u, T, p); lx = 2;
     783             :   }
     784             :   else
     785           0 :     lx = 1;
     786         182 :   nold = 1;
     787        1519 :   for (; mask > 1; )
     788             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
     789        1155 :     long i, lnew, nnew = nold << 1;
     790             : 
     791        1155 :     if (mask & 1) nnew--;
     792        1155 :     mask >>= 1;
     793             : 
     794        1155 :     lnew = nnew + 1;
     795        1155 :     lq = ZXX_lgrenormalizespec(q, minss(lQ,lnew));
     796        1155 :     z = FpXQX_mulspec(x, q, T, p, lx, lq); /* FIXME: high product */
     797        1155 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
     798        1155 :     z += 2;
     799             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
     800        1155 :     for (i = nold; i < lz; i++) if (signe(gel(z,i))) break;
     801        1155 :     nold = nnew;
     802        1155 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
     803             : 
     804             :     /* z + i represents (x*q - 1) / t^i */
     805        1155 :     lz = ZXX_lgrenormalizespec (z+i, lz-i);
     806        1155 :     z = FpXQX_mulspec(x, z+i, T, p, lx, lz); /* FIXME: low product */
     807        1155 :     lz = lgpol(z); z += 2;
     808        1155 :     if (lz > lnew-i) lz = ZXX_lgrenormalizespec(z, lnew-i);
     809             : 
     810        1155 :     lx = lz+ i;
     811        1155 :     y  = x + i; /* x -= z * t^i, in place */
     812        1155 :     for (i = 0; i < lz; i++) gel(y,i) = Fq_neg(gel(z,i), T, p);
     813             :   }
     814         182 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
     815         182 :   return gerepilecopy(av, x);
     816             : }
     817             : 
     818             : /* 1/polrecip(S)+O(x^(deg(S)-1)) */
     819             : GEN
     820        1318 : FpXQX_invBarrett(GEN S, GEN T, GEN p)
     821             : {
     822        1318 :   pari_sp ltop = avma;
     823        1318 :   long l = lg(S);
     824             :   GEN r;
     825        1318 :   if (l<5) return pol_0(varn(S));
     826        1161 :   if (l<=FpXQX_INVBARRETT_LIMIT)
     827             :   {
     828         979 :     GEN c = gel(S,l-1), ci=gen_1;
     829         979 :     if (!gequal1(c))
     830             :     {
     831           0 :       ci = Fq_inv(c, T, p);
     832           0 :       S = FqX_Fq_mul(S, ci, T, p);
     833           0 :       r = FpXQX_invBarrett_basecase(S, T, p);
     834           0 :       r = FqX_Fq_mul(r, ci, T, p);
     835             :     } else
     836         979 :       r = FpXQX_invBarrett_basecase(S, T, p);
     837             :   }
     838             :   else
     839         182 :     r = FpXQX_invBarrett_Newton(S, T, p);
     840        1161 :   return gerepileupto(ltop, r);
     841             : }
     842             : 
     843             : GEN
     844        8586 : FpXQX_get_red(GEN S, GEN T, GEN p)
     845             : {
     846        8586 :   if (typ(S)==t_POL && lg(S)>FpXQX_BARRETT_LIMIT)
     847         710 :     retmkvec2(FpXQX_invBarrett(S,T,p),S);
     848        7876 :   return S;
     849             : }
     850             : 
     851             : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
     852             :  * and mg is the Barrett inverse of S. */
     853             : static GEN
     854       47545 : FpXQX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN p, GEN *pr)
     855             : {
     856             :   GEN q, r;
     857       47545 :   long lt = degpol(S); /*We discard the leading term*/
     858             :   long ld, lm, lT, lmg;
     859       47545 :   ld = l-lt;
     860       47545 :   lm = minss(ld, lgpol(mg));
     861       47545 :   lT  = ZXX_lgrenormalizespec(S+2,lt);
     862       47545 :   lmg = ZXX_lgrenormalizespec(mg+2,lm);
     863       47545 :   q = FpXX_recipspec(x+lt,ld,ld);                 /* q = rec(x)     lq<=ld*/
     864       47545 :   q = FpXQX_mulspec(q+2,mg+2,T,p,lgpol(q),lmg);    /* q = rec(x) * mg lq<=ld+lm*/
     865       47545 :   q = FpXX_recipspec(q+2,minss(ld,lgpol(q)),ld);  /* q = rec (rec(x) * mg) lq<=ld*/
     866       47545 :   if (!pr) return q;
     867       47545 :   r = FpXQX_mulspec(q+2,S+2,T,p,lgpol(q),lT);      /* r = q*pol        lr<=ld+lt*/
     868       47545 :   r = FpXX_subspec(x,r+2,p,lt,minss(lt,lgpol(r))); /* r = x - r   lr<=lt */
     869       47545 :   if (pr == ONLY_REM) return r;
     870       47545 :   *pr = r; return q;
     871             : }
     872             : 
     873             : static GEN
     874       47083 : FpXQX_divrem_Barrett_noGC(GEN x, GEN mg, GEN S, GEN T, GEN p, GEN *pr)
     875             : {
     876       47083 :   long l = lgpol(x), lt = degpol(S), lm = 2*lt-1;
     877       47083 :   GEN q = NULL, r;
     878             :   long i;
     879       47083 :   if (l <= lt)
     880             :   {
     881           0 :     if (pr == ONLY_REM) return ZXX_copy(x);
     882           0 :     if (pr == ONLY_DIVIDES) return signe(x)? NULL: pol_0(varn(x));
     883           0 :     if (pr) *pr =  ZXX_copy(x);
     884           0 :     return pol_0(varn(x));
     885             :   }
     886       47083 :   if (lt <= 1)
     887         157 :     return FpXQX_divrem_basecase(x,S,T,p,pr);
     888       46926 :   if (pr != ONLY_REM && l>lm)
     889             :   {
     890         442 :     q = cgetg(l-lt+2, t_POL);
     891         442 :     for (i=0;i<l-lt;i++) gel(q+2,i) = gen_0;
     892             :   }
     893       46926 :   r = l>lm ? shallowcopy(x): x;
     894       94552 :   while (l>lm)
     895             :   {
     896         700 :     GEN zr, zq = FpXQX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,p,&zr);
     897         700 :     long lz = lgpol(zr);
     898         700 :     if (pr != ONLY_REM)
     899             :     {
     900         576 :       long lq = lgpol(zq);
     901         576 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
     902             :     }
     903         700 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
     904         700 :     l = l-lm+lz;
     905             :   }
     906       46926 :   if (pr != ONLY_REM)
     907             :   {
     908         449 :     if (l > lt)
     909             :     {
     910         368 :       GEN zq = FpXQX_divrem_Barrettspec(r+2,l,mg,S,T,p,&r);
     911         368 :       if (!q) q = zq;
     912             :       else
     913             :       {
     914         361 :         long lq = lgpol(zq);
     915         361 :         for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
     916             :       }
     917             :     }
     918             :     else
     919          81 :     { setlg(r, l+2); r = ZXX_copy(r); }
     920             :   }
     921             :   else
     922             :   {
     923       46477 :     if (l > lt)
     924       46477 :       (void) FpXQX_divrem_Barrettspec(r+2,l,mg,S,T,p,&r);
     925             :     else
     926           0 :     { setlg(r, l+2); r = ZXX_copy(r); }
     927       46477 :     r[1] = x[1]; return FpXQX_renormalize(r, lg(r));
     928             :   }
     929         449 :   if (pr) { r[1] = x[1]; r = FpXQX_renormalize(r, lg(r)); }
     930         449 :   q[1] = x[1]; q = FpXQX_renormalize(q, lg(q));
     931         449 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
     932         449 :   if (pr) *pr = r;
     933         449 :   return q;
     934             : }
     935             : 
     936             : GEN
     937      199263 : FpXQX_divrem(GEN x, GEN S, GEN T, GEN p, GEN *pr)
     938             : {
     939      199263 :   GEN B, y = get_FpXQX_red(S, &B);
     940      199263 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
     941      199263 :   if (pr==ONLY_REM) return FpXQX_rem(x, y, T, p);
     942      199263 :   if (lgefint(p) == 3)
     943             :   {
     944             :     GEN a, b, t, z;
     945      190788 :     pari_sp tetpil, av = avma;
     946      190788 :     ulong pp = to_FlxqX(x, y, T, p, &a, &b, &t);
     947      190788 :     z = FlxqX_divrem(a, b, t, pp, pr);
     948      190788 :     if (pr == ONLY_DIVIDES && !z) { avma = av; return NULL; }
     949      190697 :     tetpil=avma;
     950      190697 :     z = FlxX_to_ZXX(z);
     951      190697 :     if (pr && pr != ONLY_DIVIDES && pr != ONLY_REM)
     952      189199 :       *pr = FlxX_to_ZXX(*pr);
     953        1498 :     else return gerepile(av, tetpil, z);
     954      189199 :     gerepileallsp(av,tetpil,2, pr, &z);
     955      189199 :     return z;
     956             :   }
     957        8475 :   if (!B && d+3 < FpXQX_DIVREM_BARRETT_LIMIT)
     958        7959 :     return FpXQX_divrem_basecase(x,y,T,p,pr);
     959             :   else
     960             :   {
     961         516 :     pari_sp av=avma;
     962         516 :     GEN mg = B? B: FpXQX_invBarrett(y, T, p);
     963         516 :     GEN q = FpXQX_divrem_Barrett_noGC(x,mg,y,T,p,pr);
     964         516 :     if (!q) {avma=av; return NULL;}
     965         516 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
     966         425 :     gerepileall(av,2,&q,pr);
     967         425 :     return q;
     968             :   }
     969             : }
     970             : 
     971             : GEN
     972      184821 : FpXQX_rem(GEN x, GEN S, GEN T, GEN p)
     973             : {
     974      184821 :   GEN B, y = get_FpXQX_red(S, &B);
     975      184821 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
     976      184821 :   if (d < 0) return FpXQX_red(x, T, p);
     977      170626 :   if (lgefint(p) == 3)
     978             :   {
     979        9485 :     pari_sp av = avma;
     980             :     GEN a, b, t, z;
     981        9485 :     ulong pp = to_FlxqX(x, y, T, p, &a, &b, &t);
     982        9485 :     z = FlxqX_rem(a, b, t, pp);
     983        9485 :     z = FlxX_to_ZXX(z);
     984        9485 :     return gerepileupto(av, z);
     985             :   }
     986      161141 :   if (!B && d+3 < FpXQX_REM_BARRETT_LIMIT)
     987      114574 :     return FpXQX_divrem_basecase(x,y, T, p, ONLY_REM);
     988             :   else
     989             :   {
     990       46567 :     pari_sp av=avma;
     991       46567 :     GEN mg = B? B: FpXQX_invBarrett(y, T, p);
     992       46567 :     GEN r = FpXQX_divrem_Barrett_noGC(x, mg, y, T, p, ONLY_REM);
     993       46567 :     return gerepileupto(av, r);
     994             :   }
     995             : }
     996             : 
     997             : /* x + y*z mod p */
     998             : INLINE GEN
     999       11914 : Fq_addmul(GEN x, GEN y, GEN z, GEN T, GEN p)
    1000             : {
    1001             :   pari_sp av;
    1002       11914 :   if (!signe(y) || !signe(z)) return Fq_red(x, T, p);
    1003       11781 :   if (!signe(x)) return Fq_mul(z,y, T, p);
    1004       11767 :   av = avma;
    1005       11767 :   return gerepileupto(av, Fq_add(x, Fq_mul(y, z, T, p), T, p));
    1006             : }
    1007             : 
    1008             : GEN
    1009        5957 : FpXQX_div_by_X_x(GEN a, GEN x, GEN T, GEN p, GEN *r)
    1010             : {
    1011        5957 :   long l = lg(a)-1, i;
    1012        5957 :   GEN z = cgetg(l, t_POL);
    1013        5957 :   z[1] = evalsigne(1) | evalvarn(0);
    1014        5957 :   gel(z, l-1) = gel(a,l);
    1015       17871 :   for (i=l-2; i>1; i--) /* z[i] = a[i+1] + x*z[i+1] */
    1016       11914 :     gel(z, i) = Fq_addmul(gel(a,i+1), x, gel(z,i+1), T, p);
    1017        5957 :   if (r) *r = Fq_addmul(gel(a,2), x, gel(z,2), T, p);
    1018        5957 :   return z;
    1019             : }
    1020             : 
    1021             : struct _FpXQXQ {
    1022             :   GEN T, S;
    1023             :   GEN p;
    1024             : };
    1025             : 
    1026        2745 : static GEN _FpXQX_mul(void *data, GEN a,GEN b)
    1027             : {
    1028        2745 :   struct _FpXQXQ *d=(struct _FpXQXQ*)data;
    1029        2745 :   return FpXQX_mul(a,b,d->T,d->p);
    1030             : }
    1031             : 
    1032        2142 : static GEN _FpXQX_sqr(void *data, GEN a)
    1033             : {
    1034        2142 :   struct _FpXQXQ *d=(struct _FpXQXQ*)data;
    1035        2142 :   return FpXQX_sqr(a, d->T, d->p);
    1036             : }
    1037             : 
    1038             : GEN
    1039         182 : FpXQX_powu(GEN x, ulong n, GEN T, GEN p)
    1040             : {
    1041             :   struct _FpXQXQ D;
    1042         182 :   if (n==0) return pol_1(varn(x));
    1043         182 :   D.T = T; D.p = p;
    1044         182 :   return gen_powu(x, n, (void *)&D, _FpXQX_sqr, _FpXQX_mul);
    1045             : }
    1046             : 
    1047             : GEN
    1048         109 : FpXQXV_prod(GEN V, GEN T, GEN p)
    1049             : {
    1050         109 :   if (lgefint(p) == 3)
    1051             :   {
    1052          12 :     pari_sp av = avma;
    1053          12 :     ulong pp = p[2];
    1054          12 :     GEN Tl = ZXT_to_FlxT(T, pp);
    1055          12 :     GEN Vl = ZXXV_to_FlxXV(V, pp, get_FpX_var(T));
    1056          12 :     Tl = FlxqXV_prod(Vl, Tl, pp);
    1057          12 :     return gerepileupto(av, FlxX_to_ZXX(Tl));
    1058             :   }
    1059             :   else
    1060             :   {
    1061             :     struct _FpXQXQ d;
    1062          97 :     d.T=T; d.p=p;
    1063          97 :     return gen_product(V, (void*)&d, &_FpXQX_mul);
    1064             :   }
    1065             : }
    1066             : 
    1067             : static GEN
    1068        9905 : _FpXQX_divrem(void * E, GEN x, GEN y, GEN *r)
    1069             : {
    1070        9905 :   struct _FpXQXQ *d = (struct _FpXQXQ *) E;
    1071        9905 :   return FpXQX_divrem(x, y, d->T, d->p, r);
    1072             : }
    1073             : 
    1074             : static GEN
    1075       35233 : _FpXQX_add(void * E, GEN x, GEN y)
    1076             : {
    1077       35233 :   struct _FpXQXQ *d = (struct _FpXQXQ *) E;
    1078       35233 :   return FpXX_add(x, y, d->p);
    1079             : }
    1080             : 
    1081             : static GEN
    1082        4109 : _FpXQX_sub(void * E, GEN x, GEN y) {
    1083        4109 :   struct _FpXQXQ *d = (struct _FpXQXQ*) E;
    1084        4109 :   return FpXX_sub(x,y, d->p);
    1085             : }
    1086             : 
    1087             : static struct bb_ring FpXQX_ring = { _FpXQX_add, _FpXQX_mul, _FpXQX_sqr };
    1088             : 
    1089             : GEN
    1090         588 : FpXQX_digits(GEN x, GEN B, GEN T, GEN p)
    1091             : {
    1092         588 :   pari_sp av = avma;
    1093         588 :   long d = degpol(B), n = (lgpol(x)+d-1)/d;
    1094             :   GEN z;
    1095             :   struct _FpXQXQ D;
    1096         588 :   D.T = T; D.p = p;
    1097         588 :   z = gen_digits(x, B, n, (void *)&D, &FpXQX_ring, _FpXQX_divrem);
    1098         588 :   return gerepileupto(av, z);
    1099             : }
    1100             : 
    1101             : GEN
    1102         189 : FpXQXV_FpXQX_fromdigits(GEN x, GEN B, GEN T, GEN p)
    1103             : {
    1104         189 :   pari_sp av = avma;
    1105             :   struct _FpXQXQ D;
    1106             :   GEN z;
    1107         189 :   D.T = T; D.p = p;
    1108         189 :   z = gen_fromdigits(x,B,(void *)&D, &FpXQX_ring);
    1109         189 :   return gerepileupto(av, z);
    1110             : }
    1111             : 
    1112             : /* Q an FpXY (t_POL with FpX coeffs), evaluate at X = x */
    1113             : GEN
    1114       55461 : FpXY_evalx(GEN Q, GEN x, GEN p)
    1115             : {
    1116       55461 :   long i, lb = lg(Q);
    1117             :   GEN z;
    1118       55461 :   z = cgetg(lb, t_POL); z[1] = Q[1];
    1119      467950 :   for (i=2; i<lb; i++)
    1120             :   {
    1121      412489 :     GEN q = gel(Q,i);
    1122      412489 :     gel(z,i) = typ(q) == t_INT? modii(q,p): FpX_eval(q, x, p);
    1123             :   }
    1124       55461 :   return FpX_renormalize(z, lb);
    1125             : }
    1126             : /* Q an FpXY, evaluate at Y = y */
    1127             : GEN
    1128       16692 : FpXY_evaly(GEN Q, GEN y, GEN p, long vx)
    1129             : {
    1130       16692 :   pari_sp av = avma;
    1131       16692 :   long i, lb = lg(Q);
    1132             :   GEN z;
    1133       16692 :   if (!signe(Q)) return pol_0(vx);
    1134       16692 :   if (lb == 3 || !signe(y)) {
    1135          21 :     z = gel(Q, 2);
    1136          21 :     return typ(z)==t_INT? scalar_ZX(z, vx): ZX_copy(z);
    1137             :   }
    1138       16671 :   z = gel(Q, lb-1);
    1139       16671 :   if (typ(z) == t_INT) z = scalar_ZX_shallow(z, vx);
    1140       16671 :   for (i=lb-2; i>=2; i--) z = Fq_add(gel(Q,i), FpX_Fp_mul(z, y, p), NULL, p);
    1141       16671 :   return gerepileupto(av, z);
    1142             : }
    1143             : /* Q an FpXY, evaluate at (X,Y) = (x,y) */
    1144             : GEN
    1145       12397 : FpXY_eval(GEN Q, GEN y, GEN x, GEN p)
    1146             : {
    1147       12397 :   pari_sp av = avma;
    1148       12397 :   return gerepileuptoint(av, FpX_eval(FpXY_evalx(Q, x, p), y, p));
    1149             : }
    1150             : 
    1151             : GEN
    1152        2676 : FpXY_FpXQV_evalx(GEN P, GEN x, GEN T, GEN p)
    1153             : {
    1154        2676 :   long i, lP = lg(P);
    1155        2676 :   GEN res = cgetg(lP,t_POL);
    1156        2676 :   res[1] = P[1];
    1157       32329 :   for(i=2; i<lP; i++)
    1158       58935 :     gel(res,i) = typ(gel(P,i))==t_INT? icopy(gel(P,i)):
    1159       29282 :                                        FpX_FpXQV_eval(gel(P,i), x, T, p);
    1160        2676 :   return FlxX_renormalize(res, lP);
    1161             : }
    1162             : 
    1163             : GEN
    1164         147 : FpXY_FpXQ_evalx(GEN P, GEN x, GEN T, GEN p)
    1165             : {
    1166         147 :   pari_sp av = avma;
    1167         147 :   long n = brent_kung_optpow(get_FpX_degree(T)-1,lgpol(P),1);
    1168         147 :   GEN xp = FpXQ_powers(x, n, T, p);
    1169         147 :   return gerepileupto(av, FpXY_FpXQV_evalx(P, xp, T, p));
    1170             : }
    1171             : 
    1172             : /*******************************************************************/
    1173             : /*                                                                 */
    1174             : /*                       (Fp[X]/T(X))[Y] / S(Y)                    */
    1175             : /*                                                                 */
    1176             : /*******************************************************************/
    1177             : 
    1178             : /*Preliminary implementation to speed up FpX_ffisom*/
    1179             : typedef struct {
    1180             :   GEN S, T, p;
    1181             : } FpXYQQ_muldata;
    1182             : 
    1183             : /* reduce x in Fp[X, Y] in the algebra Fp[X,Y]/ (S(X),T(Y)) */
    1184             : static GEN
    1185         112 : FpXYQQ_redswap(GEN x, GEN S, GEN T, GEN p)
    1186             : {
    1187         112 :   pari_sp ltop=avma;
    1188         112 :   long n = get_FpX_degree(S);
    1189         112 :   long m = get_FpX_degree(T);
    1190         112 :   long v = get_FpX_var(T);
    1191         112 :   GEN V = RgXY_swap(x,m,v);
    1192         112 :   V = FpXQX_red(V,S,p);
    1193         112 :   V = RgXY_swap(V,n,v);
    1194         112 :   return gerepilecopy(ltop,V);
    1195             : }
    1196             : static GEN
    1197          70 : FpXYQQ_sqr(void *data, GEN x)
    1198             : {
    1199          70 :   FpXYQQ_muldata *D = (FpXYQQ_muldata*)data;
    1200          70 :   return FpXYQQ_redswap(FpXQX_sqr(x, D->T, D->p),D->S,D->T,D->p);
    1201             : 
    1202             : }
    1203             : static GEN
    1204          42 : FpXYQQ_mul(void *data, GEN x, GEN y)
    1205             : {
    1206          42 :   FpXYQQ_muldata *D = (FpXYQQ_muldata*)data;
    1207          42 :   return FpXYQQ_redswap(FpXQX_mul(x,y, D->T, D->p),D->S,D->T,D->p);
    1208             : }
    1209             : 
    1210             : /* x in Z[X,Y], S in Z[X] over Fq = Z[Y]/(p,T); compute lift(x^n mod (S,T,p)) */
    1211             : GEN
    1212          28 : FpXYQQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
    1213             : {
    1214          28 :   pari_sp av = avma;
    1215             :   FpXYQQ_muldata D;
    1216             :   GEN y;
    1217          28 :   if (lgefint(p) == 3)
    1218             :   {
    1219           0 :     ulong pp = to_FlxqX(x, NULL, T, p, &x, NULL, &T);
    1220           0 :     S = ZX_to_Flx(S, pp);
    1221           0 :     y = FlxX_to_ZXX( FlxYqq_pow(x, n, S, T, pp) );
    1222             :   }
    1223             :   else
    1224             :   {
    1225          28 :     D.S = S;
    1226          28 :     D.T = T;
    1227          28 :     D.p = p;
    1228          28 :     y = gen_pow(x, n, (void*)&D, &FpXYQQ_sqr, &FpXYQQ_mul);
    1229             :   }
    1230          28 :   return gerepileupto(av, y);
    1231             : }
    1232             : 
    1233             : GEN
    1234       32392 : FpXQXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN p) {
    1235       32392 :   return FpXQX_rem(FpXQX_mul(x, y, T, p), S, T, p);
    1236             : }
    1237             : 
    1238             : GEN
    1239      130712 : FpXQXQ_sqr(GEN x, GEN S, GEN T, GEN p) {
    1240      130712 :   return FpXQX_rem(FpXQX_sqr(x, T, p), S, T, p);
    1241             : }
    1242             : 
    1243             : /* Inverse of x in Z/pZ[X]/(pol) or NULL if inverse doesn't exist
    1244             :  * return lift(1 / (x mod (p,pol))) */
    1245             : GEN
    1246          21 : FpXQXQ_invsafe(GEN x, GEN S, GEN T, GEN p)
    1247             : {
    1248          21 :   GEN V, z = FpXQX_extgcd(get_FpXQX_mod(S), x, T, p, NULL, &V);
    1249          21 :   if (degpol(z)) return NULL;
    1250          21 :   z = gel(z,2);
    1251          21 :   z = typ(z)==t_INT ? Fp_invsafe(z,p) : FpXQ_invsafe(z,T,p);
    1252          21 :   if (!z) return NULL;
    1253          21 :   return typ(z)==t_INT ? FpXX_Fp_mul(V, z, p): FpXQX_FpXQ_mul(V, z, T, p);
    1254             : }
    1255             : 
    1256             : GEN
    1257          21 : FpXQXQ_inv(GEN x, GEN S, GEN T,GEN p)
    1258             : {
    1259          21 :   pari_sp av = avma;
    1260          21 :   GEN U = FpXQXQ_invsafe(x, S, T, p);
    1261          21 :   if (!U) pari_err_INV("FpXQXQ_inv",x);
    1262          21 :   return gerepileupto(av, U);
    1263             : }
    1264             : 
    1265             : GEN
    1266           0 : FpXQXQ_div(GEN x,GEN y,GEN S, GEN T,GEN p)
    1267             : {
    1268           0 :   pari_sp av = avma;
    1269           0 :   return gerepileupto(av, FpXQXQ_mul(x, FpXQXQ_inv(y,S,T,p),S,T,p));
    1270             : }
    1271             : 
    1272             : static GEN
    1273       36900 : _FpXQXQ_cmul(void *data, GEN P, long a, GEN x) {
    1274       36900 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1275       36900 :   GEN y = gel(P,a+2);
    1276       73777 :   return typ(y)==t_INT ? FpXX_Fp_mul(x,y, d->p):
    1277       36877 :                          FpXX_FpX_mul(x,y,d->p);
    1278             : }
    1279             : static GEN
    1280       12352 : _FpXQXQ_red(void *data, GEN x) {
    1281       12352 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1282       12352 :   return FpXQX_red(x, d->T, d->p);
    1283             : }
    1284             : static GEN
    1285       29864 : _FpXQXQ_mul(void *data, GEN x, GEN y) {
    1286       29864 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1287       29864 :   return FpXQXQ_mul(x,y, d->S,d->T, d->p);
    1288             : }
    1289             : static GEN
    1290      130712 : _FpXQXQ_sqr(void *data, GEN x) {
    1291      130712 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1292      130712 :   return FpXQXQ_sqr(x, d->S,d->T, d->p);
    1293             : }
    1294             : 
    1295             : static GEN
    1296        9340 : _FpXQXQ_one(void *data) {
    1297        9340 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1298        9340 :   return pol_1(get_FpXQX_var(d->S));
    1299             : }
    1300             : 
    1301             : static GEN
    1302          68 : _FpXQXQ_zero(void *data) {
    1303          68 :   struct _FpXQXQ *d = (struct _FpXQXQ*) data;
    1304          68 :   return pol_0(get_FpXQX_var(d->S));
    1305             : }
    1306             : 
    1307             : static struct bb_algebra FpXQXQ_algebra = { _FpXQXQ_red, _FpXQX_add,
    1308             :        _FpXQX_sub, _FpXQXQ_mul, _FpXQXQ_sqr, _FpXQXQ_one, _FpXQXQ_zero };
    1309             : 
    1310             : const struct bb_algebra *
    1311         495 : get_FpXQXQ_algebra(void **E, GEN S, GEN T, GEN p)
    1312             : {
    1313         495 :   GEN z = new_chunk(sizeof(struct _FpXQXQ));
    1314         495 :   struct _FpXQXQ *e = (struct _FpXQXQ *) z;
    1315         495 :   e->T = FpX_get_red(T, p);
    1316         495 :   e->S = FpXQX_get_red(S, e->T, p);
    1317         495 :   e->p  = p; *E = (void*)e;
    1318         495 :   return &FpXQXQ_algebra;
    1319             : }
    1320             : 
    1321             : static struct bb_algebra FpXQX_algebra = { _FpXQXQ_red, _FpXQX_add,
    1322             :        _FpXQX_sub, _FpXQX_mul, _FpXQX_sqr, _FpXQXQ_one, _FpXQXQ_zero };
    1323             : 
    1324             : const struct bb_algebra *
    1325          42 : get_FpXQX_algebra(void **E, GEN T, GEN p, long v)
    1326             : {
    1327          42 :   GEN z = new_chunk(sizeof(struct _FpXQXQ));
    1328          42 :   struct _FpXQXQ *e = (struct _FpXQXQ *) z;
    1329          42 :   e->T = FpX_get_red(T, p);
    1330          42 :   e->S = pol_x(v);
    1331          42 :   e->p  = p; *E = (void*)e;
    1332          42 :   return &FpXQX_algebra;
    1333             : }
    1334             : 
    1335             : /* x over Fq, return lift(x^n) mod S */
    1336             : GEN
    1337        1359 : FpXQXQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
    1338             : {
    1339        1359 :   pari_sp ltop = avma;
    1340             :   GEN y;
    1341             :   struct _FpXQXQ D;
    1342        1359 :   long s = signe(n);
    1343        1359 :   if (!s) return pol_1(varn(x));
    1344        1359 :   if (is_pm1(n)) /* +/- 1 */
    1345           0 :     return (s < 0)? FpXQXQ_inv(x,S,T,p): ZXX_copy(x);
    1346        1359 :   if (lgefint(p) == 3)
    1347             :   {
    1348           0 :     ulong pp = to_FlxqX(x, S, T, p, &x, &S, &T);
    1349           0 :     GEN z = FlxqXQ_pow(x, n, S, T, pp);
    1350           0 :     y = FlxX_to_ZXX(z);
    1351             :   }
    1352             :   else
    1353             :   {
    1354        1359 :     T = FpX_get_red(T, p);
    1355        1359 :     S = FpXQX_get_red(S, T, p);
    1356        1359 :     D.S = S; D.T = T; D.p = p;
    1357        1359 :     if (s < 0) x = FpXQXQ_inv(x,S,T,p);
    1358        1359 :     y = gen_pow(x, n, (void*)&D,&_FpXQXQ_sqr,&_FpXQXQ_mul);
    1359             :   }
    1360        1359 :   return gerepileupto(ltop, y);
    1361             : }
    1362             : 
    1363             : /* generates the list of powers of x of degree 0,1,2,...,l*/
    1364             : GEN
    1365        1320 : FpXQXQ_powers(GEN x, long l, GEN S, GEN T, GEN p)
    1366             : {
    1367             :   struct _FpXQXQ D;
    1368        1320 :   int use_sqr = 2*degpol(x) >= get_FpXQX_degree(S);
    1369        1320 :   T = FpX_get_red(T, p);
    1370        1320 :   S = FpXQX_get_red(S, T, p);
    1371        1320 :   D.S = S; D.T = T; D.p = p;
    1372        1320 :   return gen_powers(x, l, use_sqr, (void*)&D, &_FpXQXQ_sqr, &_FpXQXQ_mul,&_FpXQXQ_one);
    1373             : }
    1374             : 
    1375             : static GEN
    1376          32 : FpXQXn_mul(GEN a, GEN b, long n, GEN T, GEN p)
    1377             : {
    1378          32 :   return RgXn_red_shallow(FpXQX_mul(a, b, T, p), n);
    1379             : }
    1380             : 
    1381             : /* Let v a linear form, return the linear form z->v(tau*z)
    1382             :    that is, v*(M_tau) */
    1383             : 
    1384             : INLINE GEN
    1385          48 : FpXQX_recipspec(GEN x, long l, long n)
    1386             : {
    1387          48 :   return RgX_recipspec_shallow(x, l, n);
    1388             : }
    1389             : 
    1390             : static GEN
    1391          16 : FpXQXQ_transmul_init(GEN tau, GEN S, GEN T, GEN p)
    1392             : {
    1393             :   GEN bht;
    1394          16 :   GEN h, Sp = get_FpXQX_red(S, &h);
    1395          16 :   long n = degpol(Sp), vT = varn(Sp);
    1396          16 :   GEN ft = FpXQX_recipspec(Sp+2, n+1, n+1);
    1397          16 :   GEN bt = FpXQX_recipspec(tau+2, lgpol(tau), n);
    1398          16 :   setvarn(ft, vT); setvarn(bt, vT);
    1399          16 :   if (h)
    1400           0 :     bht = FpXQXn_mul(bt, h, n-1, T, p);
    1401             :   else
    1402             :   {
    1403          16 :     GEN bh = FpXQX_div(RgX_shift_shallow(tau, n-1), S, T, p);
    1404          16 :     bht = FpXQX_recipspec(bh+2, lgpol(bh), n-1);
    1405          16 :     setvarn(bht, vT);
    1406             :   }
    1407          16 :   return mkvec3(bt, bht, ft);
    1408             : }
    1409             : 
    1410             : static GEN
    1411          40 : FpXQXQ_transmul(GEN tau, GEN a, long n, GEN T, GEN p)
    1412             : {
    1413          40 :   pari_sp ltop = avma;
    1414             :   GEN t1, t2, t3, vec;
    1415          40 :   GEN bt = gel(tau, 1), bht = gel(tau, 2), ft = gel(tau, 3);
    1416          40 :   if (signe(a)==0) return pol_0(varn(a));
    1417          40 :   t2 = RgX_shift_shallow(FpXQX_mul(bt, a, T, p),1-n);
    1418          40 :   if (signe(bht)==0) return gerepilecopy(ltop, t2);
    1419          32 :   t1 = RgX_shift_shallow(FpXQX_mul(ft, a, T, p),-n);
    1420          32 :   t3 = FpXQXn_mul(t1, bht, n-1, T, p);
    1421          32 :   vec = FpXX_sub(t2, RgX_shift_shallow(t3, 1), p);
    1422          32 :   return gerepileupto(ltop, vec);
    1423             : }
    1424             : 
    1425             : static GEN
    1426           8 : polxn_FpXX(long n, long v, long vT)
    1427             : {
    1428           8 :   long i, a = n+2;
    1429           8 :   GEN p = cgetg(a+1, t_POL);
    1430           8 :   p[1] = evalsigne(1)|evalvarn(v);
    1431           8 :   for (i = 2; i < a; i++) gel(p,i) = pol_0(vT);
    1432           8 :   gel(p,a) = pol_1(vT); return p;
    1433             : }
    1434             : 
    1435             : GEN
    1436           8 : FpXQXQ_minpoly(GEN x, GEN S, GEN T, GEN p)
    1437             : {
    1438           8 :   pari_sp ltop = avma;
    1439             :   long vS, vT, n;
    1440             :   GEN v_x, g, tau;
    1441           8 :   vS = get_FpXQX_var(S);
    1442           8 :   vT = get_FpX_var(T);
    1443           8 :   n = get_FpXQX_degree(S);
    1444           8 :   g = pol_1(vS);
    1445           8 :   tau = pol_1(vS);
    1446           8 :   S = FpXQX_get_red(S, T, p);
    1447           8 :   v_x = FpXQXQ_powers(x, usqrt(2*n), S, T, p);
    1448          24 :   while(signe(tau) != 0)
    1449             :   {
    1450             :     long i, j, m, k1;
    1451             :     GEN M, v, tr;
    1452             :     GEN g_prime, c;
    1453           8 :     if (degpol(g) == n) { tau = pol_1(vS); g = pol_1(vS); }
    1454           8 :     v = random_FpXQX(n, vS, T, p);
    1455           8 :     tr = FpXQXQ_transmul_init(tau, S, T, p);
    1456           8 :     v = FpXQXQ_transmul(tr, v, n, T, p);
    1457           8 :     m = 2*(n-degpol(g));
    1458           8 :     k1 = usqrt(m);
    1459           8 :     tr = FpXQXQ_transmul_init(gel(v_x,k1+1), S, T, p);
    1460           8 :     c = cgetg(m+2,t_POL);
    1461           8 :     c[1] = evalsigne(1)|evalvarn(vS);
    1462          40 :     for (i=0; i<m; i+=k1)
    1463             :     {
    1464          32 :       long mj = minss(m-i, k1);
    1465         100 :       for (j=0; j<mj; j++)
    1466          68 :         gel(c,m+1-(i+j)) = FpXQX_dotproduct(v, gel(v_x,j+1), T, p);
    1467          32 :       v = FpXQXQ_transmul(tr, v, n, T, p);
    1468             :     }
    1469           8 :     c = FpXX_renormalize(c, m+2);
    1470             :     /* now c contains <v,x^i> , i = 0..m-1  */
    1471           8 :     M = FpXQX_halfgcd(polxn_FpXX(m, vS, vT), c, T, p);
    1472           8 :     g_prime = gmael(M, 2, 2);
    1473           8 :     if (degpol(g_prime) < 1) continue;
    1474           8 :     g = FpXQX_mul(g, g_prime, T, p);
    1475           8 :     tau = FpXQXQ_mul(tau, FpXQX_FpXQXQV_eval(g_prime, v_x, S, T, p), S, T, p);
    1476             :   }
    1477           8 :   g = FpXQX_normalize(g,T, p);
    1478           8 :   return gerepilecopy(ltop,g);
    1479             : }
    1480             : 
    1481             : GEN
    1482           0 : FpXQXQ_matrix_pow(GEN y, long n, long m, GEN S, GEN T, GEN p)
    1483             : {
    1484           0 :   return RgXV_to_RgM(FpXQXQ_powers(y,m-1,S,T,p),n);
    1485             : }
    1486             : 
    1487             : GEN
    1488        2618 : FpXQX_FpXQXQV_eval(GEN P, GEN V, GEN S, GEN T, GEN p)
    1489             : {
    1490             :   struct _FpXQXQ D;
    1491        2618 :   T = FpX_get_red(T, p);
    1492        2618 :   S = FpXQX_get_red(S, T, p);
    1493        2618 :   D.S=S; D.T=T; D.p=p;
    1494        2618 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &FpXQXQ_algebra,
    1495             :                                                    _FpXQXQ_cmul);
    1496             : }
    1497             : 
    1498             : GEN
    1499         218 : FpXQX_FpXQXQ_eval(GEN Q, GEN x, GEN S, GEN T, GEN p)
    1500             : {
    1501             :   struct _FpXQXQ D;
    1502         218 :   int use_sqr = 2*degpol(x) >= get_FpXQX_degree(S);
    1503         218 :   T = FpX_get_red(T, p);
    1504         218 :   S = FpXQX_get_red(S, T, p);
    1505         218 :   D.S=S; D.T=T; D.p=p;
    1506         218 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &FpXQXQ_algebra,
    1507             :       _FpXQXQ_cmul);
    1508             : }
    1509             : 
    1510             : static GEN
    1511         166 : FpXQXQ_autpow_sqr(void * E, GEN x)
    1512             : {
    1513         166 :   struct _FpXQXQ *D = (struct _FpXQXQ *)E;
    1514         166 :   GEN S = D->S, T = D->T, p = D->p;
    1515         166 :   GEN phi = gel(x,1), S1 = gel(x,2);
    1516         166 :   long n = brent_kung_optpow(get_FpX_degree(T)-1,lgpol(S1)+1,1);
    1517         166 :   GEN V = FpXQ_powers(phi, n, T, p);
    1518         166 :   GEN phi2 = FpX_FpXQV_eval(phi, V, T, p);
    1519         166 :   GEN Sphi = FpXY_FpXQV_evalx(S1, V, T, p);
    1520         166 :   GEN S2 = FpXQX_FpXQXQ_eval(Sphi, S1, S, T, p);
    1521         166 :   return mkvec2(phi2, S2);
    1522             : }
    1523             : 
    1524             : static GEN
    1525          29 : FpXQXQ_autpow_mul(void * E, GEN x, GEN y)
    1526             : {
    1527          29 :   struct _FpXQXQ *D = (struct _FpXQXQ *)E;
    1528          29 :   GEN S = D->S, T = D->T, p = D->p;
    1529          29 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    1530          29 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    1531          29 :   long n = brent_kung_optpow(get_FpX_degree(T)-1, lgpol(S1)+1, 1);
    1532          29 :   GEN V = FpXQ_powers(phi2, n, T, p);
    1533          29 :   GEN phi3 = FpX_FpXQV_eval(phi1, V, T, p);
    1534          29 :   GEN Sphi = FpXY_FpXQV_evalx(S1, V, T, p);
    1535          29 :   GEN S3 = FpXQX_FpXQXQ_eval(Sphi, S2, S, T, p);
    1536          29 :   return mkvec2(phi3, S3);
    1537             : }
    1538             : 
    1539             : GEN
    1540         166 : FpXQXQ_autpow(GEN aut, long n, GEN S, GEN T, GEN p)
    1541             : {
    1542             :   struct _FpXQXQ D;
    1543         166 :   T = FpX_get_red(T, p);
    1544         166 :   S = FpXQX_get_red(S, T, p);
    1545         166 :   D.S=S; D.T=T; D.p=p;
    1546         166 :   return gen_powu(aut,n,&D,FpXQXQ_autpow_sqr,FpXQXQ_autpow_mul);
    1547             : }
    1548             : 
    1549             : static GEN
    1550           1 : FpXQXQ_auttrace_mul(void *E, GEN x, GEN y)
    1551             : {
    1552           1 :   struct _FpXQXQ *D = (struct _FpXQXQ *)E;
    1553           1 :   GEN S = D->S, T = D->T;
    1554           1 :   GEN p = D->p;
    1555           1 :   GEN S1 = gel(x,1), a1 = gel(x,2);
    1556           1 :   GEN S2 = gel(y,1), a2 = gel(y,2);
    1557           1 :   long n = brent_kung_optpow(maxss(degpol(S1),degpol(a1)),2,1);
    1558           1 :   GEN V = FpXQXQ_powers(S2, n, S, T, p);
    1559           1 :   GEN S3 = FpXQX_FpXQXQV_eval(S1, V, S, T, p);
    1560           1 :   GEN aS = FpXQX_FpXQXQV_eval(a1, V, S, T, p);
    1561           1 :   GEN a3 = FpXX_add(aS, a2, p);
    1562           1 :   return mkvec2(S3, a3);
    1563             : }
    1564             : 
    1565             : static GEN
    1566           1 : FpXQXQ_auttrace_sqr(void *E, GEN x)
    1567           1 : { return FpXQXQ_auttrace_mul(E, x, x); }
    1568             : 
    1569             : GEN
    1570           8 : FpXQXQ_auttrace(GEN aut, long n, GEN S, GEN T, GEN p)
    1571             : {
    1572             :   struct _FpXQXQ D;
    1573           8 :   T = FpX_get_red(T, p);
    1574           8 :   S = FpXQX_get_red(S, T, p);
    1575           8 :   D.S=S; D.T=T; D.p=p;
    1576           8 :   return gen_powu(aut,n,&D,FpXQXQ_auttrace_sqr,FpXQXQ_auttrace_mul);
    1577             : }
    1578             : 
    1579             : static GEN
    1580        1167 : FpXQXQ_autsum_mul(void *E, GEN x, GEN y)
    1581             : {
    1582        1167 :   struct _FpXQXQ *D = (struct _FpXQXQ *) E;
    1583        1167 :   GEN S = D->S, T = D->T, p = D->p;
    1584        1167 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    1585        1167 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    1586        1167 :   long n2 = brent_kung_optpow(get_FpX_degree(T)-1, lgpol(S1)+lgpol(a1)+1, 1);
    1587        1167 :   GEN V2 = FpXQ_powers(phi2, n2, T, p);
    1588        1167 :   GEN phi3 = FpX_FpXQV_eval(phi1, V2, T, p);
    1589        1167 :   GEN Sphi = FpXY_FpXQV_evalx(S1, V2, T, p);
    1590        1167 :   GEN aphi = FpXY_FpXQV_evalx(a1, V2, T, p);
    1591        1167 :   long n = brent_kung_optpow(maxss(degpol(Sphi),degpol(aphi)),2,1);
    1592        1167 :   GEN V = FpXQXQ_powers(S2, n, S, T, p);
    1593        1167 :   GEN S3 = FpXQX_FpXQXQV_eval(Sphi, V, S, T, p);
    1594        1167 :   GEN aS = FpXQX_FpXQXQV_eval(aphi, V, S, T, p);
    1595        1167 :   GEN a3 = FpXQXQ_mul(aS, a2, S, T, p);
    1596        1167 :   return mkvec3(phi3, S3, a3);
    1597             : }
    1598             : 
    1599             : static GEN
    1600        1113 : FpXQXQ_autsum_sqr(void * T, GEN x)
    1601        1113 : { return FpXQXQ_autsum_mul(T,x,x); }
    1602             : 
    1603             : GEN
    1604        1113 : FpXQXQ_autsum(GEN aut, long n, GEN S, GEN T, GEN p)
    1605             : {
    1606             :   struct _FpXQXQ D;
    1607        1113 :   T = FpX_get_red(T, p);
    1608        1113 :   S = FpXQX_get_red(S, T, p);
    1609        1113 :   D.S=S; D.T=T; D.p=p;
    1610        1113 :   return gen_powu(aut,n,&D,FpXQXQ_autsum_sqr,FpXQXQ_autsum_mul);
    1611             : }

Generated by: LCOV version 1.11