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 18948-dd2a64a) Lines: 724 819 88.4 %
Date: 2016-05-28 Functions: 94 101 93.1 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 313 401 78.1 %

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

Generated by: LCOV version 1.9