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.8.0 lcov report (development 19614-52e089f) Lines: 718 826 86.9 %
Date: 2016-09-28 05:54:17 Functions: 93 101 92.1 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.11