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-bordeaux1.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 16624-25b9976) Lines: 544 584 93.2 %
Date: 2014-06-24 Functions: 66 69 95.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 238 325 73.2 %

           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                 :      31277 : to_FlxqX(GEN P, GEN Q, GEN T, GEN p, GEN *pt_P, GEN *pt_Q, GEN *pt_T)
      28                 :            : {
      29                 :      31277 :   ulong pp = uel(p,2);
      30                 :      31277 :   long v = get_FpX_var(T);
      31                 :      31277 :   *pt_P = ZXX_to_FlxX(P, pp, v);
      32         [ +  + ]:      31277 :   if (pt_Q) *pt_Q = ZXX_to_FlxX(Q, pp, v);
      33                 :      31277 :   *pt_T = ZXT_to_FlxT(T, pp);
      34                 :      31277 :   return pp;
      35                 :            : }
      36                 :            : 
      37                 :            : static GEN
      38                 :         80 : ZXX_copy(GEN a) { return gcopy(a); }
      39                 :            : 
      40                 :            : GEN
      41                 :      11265 : FpXX_red(GEN z, GEN p)
      42                 :            : {
      43                 :            :   GEN res;
      44                 :      11265 :   long i, l = lg(z);
      45                 :      11265 :   res = cgetg(l,t_POL); res[1] = z[1];
      46         [ +  + ]:     114850 :   for (i=2; i<l; i++)
      47                 :            :   {
      48                 :     103585 :     GEN zi = gel(z,i), c;
      49         [ +  + ]:     103585 :     if (typ(zi)==t_INT)
      50                 :      90074 :       c = modii(zi,p);
      51                 :            :     else
      52                 :            :     {
      53                 :      13511 :       pari_sp av = avma;
      54                 :      13511 :       c = FpX_red(zi,p);
      55      [ +  +  + ]:      13511 :       switch(lg(c)) {
      56                 :        125 :         case 2: avma = av; c = gen_0; break;
      57                 :         75 :         case 3: c = gerepilecopy(av, gel(c,2)); break;
      58                 :            :       }
      59                 :            :     }
      60                 :     103585 :     gel(res,i) = c;
      61                 :            :   }
      62                 :      11265 :   return FpXX_renormalize(res,lg(res));
      63                 :            : }
      64                 :            : GEN
      65                 :      61120 : FpXX_add(GEN x, GEN y, GEN p)
      66                 :            : {
      67                 :            :   long i,lz;
      68                 :            :   GEN z;
      69                 :      61120 :   long lx=lg(x);
      70                 :      61120 :   long ly=lg(y);
      71         [ +  + ]:      61120 :   if (ly>lx) swapspec(x,y, lx,ly);
      72                 :      61120 :   lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
      73         [ +  + ]:     459033 :   for (i=2; i<ly; i++) gel(z,i) = Fq_add(gel(x,i), gel(y,i), NULL, p);
      74         [ +  + ]:     130454 :   for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
      75                 :      61120 :   return FpXX_renormalize(z, lz);
      76                 :            : }
      77                 :            : GEN
      78                 :       7692 : FpXX_sub(GEN x, GEN y, GEN p)
      79                 :            : {
      80                 :            :   long i,lz;
      81                 :            :   GEN z;
      82                 :       7692 :   long lx=lg(x);
      83                 :       7692 :   long ly=lg(y);
      84         [ +  + ]:       7692 :   if (ly <= lx)
      85                 :            :   {
      86                 :       2427 :     lz = lx; z = cgetg(lz, t_POL); z[1]=x[1];
      87         [ +  + ]:      21786 :     for (i=2; i<ly; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
      88         [ +  + ]:      24063 :     for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
      89                 :            :   }
      90                 :            :   else
      91                 :            :   {
      92                 :       5265 :     lz = ly; z = cgetg(lz, t_POL); z[1]=x[1];
      93         [ +  + ]:      55880 :     for (i=2; i<lx; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
      94         [ +  + ]:      18130 :     for (   ; i<ly; i++) gel(z,i) = Fq_neg(gel(y,i), NULL, p);
      95                 :            :   }
      96                 :       7692 :   return FpXX_renormalize(z, lz);
      97                 :            : }
      98                 :            : 
      99                 :            : static GEN
     100                 :       1475 : FpXX_subspec(GEN x, GEN y, GEN p, long nx, long ny)
     101                 :            : {
     102                 :            :   long i,lz;
     103                 :            :   GEN z;
     104         [ +  - ]:       1475 :   if (ny <= nx)
     105                 :            :   {
     106                 :       1475 :     lz = nx+2; z = cgetg(lz, t_POL)+2;
     107         [ +  + ]:      72535 :     for (i=0; i<ny; i++) gel(z,i) = Fq_sub(gel(x,i), gel(y,i), NULL, p);
     108         [ -  + ]:       1475 :     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                 :       1475 :   return FpXX_renormalize(z-2, lz);
     117                 :            : }
     118                 :            : 
     119                 :            : GEN
     120                 :         45 : FpXX_neg(GEN x, GEN p)
     121                 :            : {
     122                 :         45 :   long i, lx = lg(x);
     123                 :         45 :   GEN y = cgetg(lx,t_POL);
     124                 :         45 :   y[1] = x[1];
     125         [ +  + ]:        630 :   for(i=2; i<lx; i++) gel(y,i) = Fq_neg(gel(x,i), NULL, p);
     126                 :         45 :   return FpXX_renormalize(y, lx);
     127                 :            : }
     128                 :            : 
     129                 :            : GEN
     130                 :       9105 : FpXX_Fp_mul(GEN P, GEN u, GEN p)
     131                 :            : {
     132                 :            :   long i, lP;
     133                 :       9105 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     134         [ +  + ]:     146086 :   for(i=2; i<lP; i++)
     135                 :            :   {
     136                 :     136981 :     GEN x = gel(P,i);
     137         [ +  + ]:     136981 :     gel(res,i) = typ(x)==t_INT? Fp_mul(x,u,p): FpX_Fp_mul(x,u,p);
     138                 :            :   }
     139                 :       9105 :   return FpXX_renormalize(res,lP);
     140                 :            : }
     141                 :            : 
     142                 :            : GEN
     143                 :      23150 : FpXX_mulu(GEN P, ulong u, GEN p)
     144                 :            : {
     145                 :            :   long i, lP;
     146                 :      23150 :   GEN res = cgetg_copy(P, &lP); res[1] = P[1];
     147         [ +  + ]:     116225 :   for(i=2; i<lP; i++)
     148                 :            :   {
     149                 :      93075 :     GEN x = gel(P,i);
     150         [ +  + ]:      93075 :     gel(res,i) = typ(x)==t_INT? Fp_mulu(x,u,p): FpX_mulu(x,u,p);
     151                 :            :   }
     152                 :      23150 :   return FpXX_renormalize(res,lP);
     153                 :            : }
     154                 :            : 
     155                 :            : /*******************************************************************/
     156                 :            : /*                                                                 */
     157                 :            : /*                             (Fp[X]/(Q))[Y]                      */
     158                 :            : /*                                                                 */
     159                 :            : /*******************************************************************/
     160                 :            : /*Not stack clean*/
     161                 :            : GEN
     162                 :      90901 : Kronecker_to_FpXQX(GEN Z, GEN T, GEN p)
     163                 :            : {
     164                 :      90901 :   long i,j,lx,l, N = (get_FpX_degree(T)<<1) + 1;
     165                 :      90901 :   GEN x, t = cgetg(N,t_POL), z = FpX_red(Z, p);
     166                 :      90901 :   t[1] = evalvarn(get_FpX_var(T));
     167                 :      90901 :   l = lg(z); lx = (l-2) / (N-2);
     168                 :      90901 :   x = cgetg(lx+3,t_POL);
     169                 :      90901 :   x[1] = z[1];
     170         [ +  + ]:    2001794 :   for (i=2; i<lx+2; i++)
     171                 :            :   {
     172         [ +  + ]:   31641504 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     173                 :    1910893 :     z += (N-2);
     174                 :    1910893 :     gel(x,i) = FpX_rem(FpX_renormalize(t,N), T,p);
     175                 :            :   }
     176                 :      90901 :   N = (l-2) % (N-2) + 2;
     177         [ +  + ]:     317101 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     178                 :      90901 :   gel(x,i) = FpX_rem(FpX_renormalize(t,N), T,p);
     179                 :      90901 :   return FpXQX_renormalize(x, i+1);
     180                 :            : }
     181                 :            : 
     182                 :            : /* shallow, n = deg(T) */
     183                 :            : GEN
     184                 :      59935 : Kronecker_to_ZXX(GEN z, long n, long v)
     185                 :            : {
     186                 :      59935 :   long i,j,lx,l, N = (n<<1)+1;
     187                 :            :   GEN x, t;
     188                 :      59935 :   l = lg(z); lx = (l-2) / (N-2);
     189                 :      59935 :   x = cgetg(lx+3,t_POL);
     190                 :      59935 :   x[1] = z[1];
     191         [ +  + ]:     924968 :   for (i=2; i<lx+2; i++)
     192                 :            :   {
     193                 :     865033 :     t = cgetg(N,t_POL); t[1] = evalvarn(v);
     194         [ +  + ]:   13140208 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     195                 :     865033 :     z += (N-2);
     196                 :     865033 :     gel(x,i) = ZX_renormalize(t,N);
     197                 :            :   }
     198                 :      59935 :   N = (l-2) % (N-2) + 2;
     199                 :      59935 :   t = cgetg(N,t_POL); t[1] = evalvarn(v);
     200         [ +  + ]:     273998 :   for (j=2; j<N; j++) gel(t,j) = gel(z,j);
     201                 :      59935 :   gel(x,i) = ZX_renormalize(t,N);
     202                 :      59935 :   return ZXX_renormalize(x, i+1);
     203                 :            : }
     204                 :            : /* shallow */
     205                 :            : GEN
     206                 :      93475 : ZXX_mul_Kronecker(GEN x, GEN y, long n)
     207                 :      93475 : { return ZX_mul(ZXX_to_Kronecker(x,n), ZXX_to_Kronecker(y,n)); }
     208                 :            : 
     209                 :            : GEN
     210                 :     114706 : FpXQX_red(GEN z, GEN T, GEN p)
     211                 :            : {
     212                 :     114706 :   long i, l = lg(z);
     213                 :     114706 :   GEN res = cgetg(l,t_POL); res[1] = z[1];
     214         [ +  + ]:     945084 :   for(i=2;i<l;i++)
     215         [ +  + ]:     830378 :     if (typ(gel(z,i)) == t_INT)
     216                 :      83035 :       gel(res,i) = modii(gel(z,i),p);
     217                 :            :     else
     218                 :     747343 :       gel(res,i) = FpXQ_red(gel(z,i),T,p);
     219                 :     114706 :   return FpXQX_renormalize(res,l);
     220                 :            : }
     221                 :            : 
     222                 :            : static int
     223                 :     178556 : ZXX_is_ZX_spec(GEN a,long na)
     224                 :            : {
     225                 :            :   long i;
     226         [ +  + ]:     217878 :   for(i=0;i<na;i++)
     227         [ +  + ]:     212152 :     if(typ(gel(a,i))!=t_INT) return 0;
     228                 :     178556 :   return 1;
     229                 :            : }
     230                 :            : 
     231                 :            : static int
     232                 :      12946 : ZXX_is_ZX(GEN a) { return ZXX_is_ZX_spec(a+2,lgpol(a)); }
     233                 :            : 
     234                 :            : static GEN
     235                 :       6927 : FpXX_FpX_mulspec(GEN P, GEN U, GEN p, long v, long lU)
     236                 :            : {
     237                 :       6927 :   long i, lP =lg(P);
     238                 :            :   GEN res;
     239                 :       6927 :   res = cgetg(lP, t_POL); res[1] = P[1];
     240         [ +  + ]:     106441 :   for(i=2; i<lP; i++)
     241                 :            :   {
     242                 :      99514 :     GEN Pi = gel(P,i);
     243         [ +  + ]:     198257 :     gel(res,i) = typ(Pi)==t_INT? FpX_Fp_mulspec(U, Pi, p, lU):
     244                 :      98743 :                                  FpX_mulspec(U, Pi+2, p, lU, lgpol(Pi));
     245                 :      99514 :     setvarn(gel(res,i),v);
     246                 :            :   }
     247                 :       6927 :   return FpXQX_renormalize(res,lP);
     248                 :            : }
     249                 :            : 
     250                 :            : GEN
     251                 :       3671 : FpXX_FpX_mul(GEN P, GEN U, GEN p)
     252                 :       3671 : { return FpXX_FpX_mulspec(P,U+2,p,varn(U),lgpol(U)); }
     253                 :            : 
     254                 :            : static GEN
     255                 :       3256 : FpXY_FpY_mulspec(GEN x, GEN y, GEN T, GEN p, long lx, long ly)
     256                 :            : {
     257                 :       3256 :   pari_sp av = avma;
     258                 :       3256 :   GEN z = RgXY_swapspec(x,get_FpX_degree(T)-1,MAXVARN,lx);
     259                 :       3256 :   z = FpXX_FpX_mulspec(z,y,p,MAXVARN,ly);
     260                 :       3256 :   z = RgXY_swapspec(z+2,lx+ly+3,get_FpX_var(T),lgpol(z));
     261                 :       3256 :   return gerepilecopy(av,z);
     262                 :            : }
     263                 :            : 
     264                 :            : static GEN
     265                 :      82805 : FpXQX_mulspec(GEN x, GEN y, GEN T, GEN p, long lx, long ly)
     266                 :            : {
     267                 :      82805 :   pari_sp av = avma;
     268                 :            :   GEN z, kx, ky;
     269                 :            :   long n;
     270         [ +  + ]:      82805 :   if (ZXX_is_ZX_spec(y,ly))
     271                 :            :   {
     272         [ +  + ]:       1615 :     if (ZXX_is_ZX_spec(x,lx))
     273                 :        876 :       return FpX_mulspec(x,y,p,lx,ly);
     274                 :            :     else
     275                 :        739 :       return FpXY_FpY_mulspec(x,y,T,p,lx,ly);
     276         [ +  + ]:      81190 :   } else if (ZXX_is_ZX_spec(x,lx))
     277                 :       2517 :       return FpXY_FpY_mulspec(y,x,T,p,ly,lx);
     278                 :      78673 :   n = get_FpX_degree(T);
     279                 :      78673 :   kx = ZXX_to_Kronecker_spec(x, lx, n);
     280                 :      78673 :   ky = ZXX_to_Kronecker_spec(y, ly, n);
     281                 :      78673 :   z = Kronecker_to_FpXQX(ZX_mul(ky,kx), T, p);
     282                 :      82805 :   return gerepileupto(av, z);
     283                 :            : }
     284                 :            : 
     285                 :            : GEN
     286                 :      68035 : FpXQX_mul(GEN x, GEN y, GEN T, GEN p)
     287                 :            : {
     288                 :      68035 :   GEN z = FpXQX_mulspec(x+2,y+2,T,p,lgpol(x),lgpol(y));
     289                 :      68035 :   setvarn(z,varn(x)); return z;
     290                 :            : }
     291                 :            : 
     292                 :            : GEN
     293                 :      12946 : FpXQX_sqr(GEN x, GEN T, GEN p)
     294                 :            : {
     295                 :      12946 :   pari_sp av = avma;
     296                 :            :   GEN z, kx;
     297         [ +  + ]:      12946 :   if (ZXX_is_ZX(x)) return ZX_sqr(x);
     298                 :      12228 :   kx= ZXX_to_Kronecker(x, get_FpX_degree(T));
     299                 :      12228 :   z = Kronecker_to_FpXQX(ZX_sqr(kx), T, p);
     300                 :      12946 :   return gerepileupto(av, z);
     301                 :            : }
     302                 :            : 
     303                 :            : GEN
     304                 :      40783 : FpXQX_FpXQ_mul(GEN P, GEN U, GEN T, GEN p)
     305                 :            : {
     306                 :            :   long i, lP;
     307                 :            :   GEN res;
     308                 :      40783 :   res = cgetg_copy(P, &lP); res[1] = P[1];
     309         [ +  + ]:     169163 :   for(i=2; i<lP; i++)
     310         [ +  + ]:     128380 :     gel(res,i) = typ(gel(P,i))==t_INT? FpX_Fp_mul(U, gel(P,i), p):
     311                 :      80638 :                                        FpXQ_mul(U, gel(P,i), T,p);
     312                 :      40783 :   return FpXQX_renormalize(res,lP);
     313                 :            : }
     314                 :            : 
     315                 :            : /* x and y in Z[Y][X]. Assume T irreducible mod p */
     316                 :            : static GEN
     317                 :      51800 : FpXQX_divrem_basecase(GEN x, GEN y, GEN T, GEN p, GEN *pr)
     318                 :            : {
     319                 :            :   long vx, dx, dy, dz, i, j, sx, lr;
     320                 :            :   pari_sp av0, av, tetpil;
     321                 :            :   GEN z,p1,rem,lead;
     322                 :            : 
     323         [ -  + ]:      51800 :   if (!T) return FpX_divrem(x,y,p,pr);
     324         [ -  + ]:      51800 :   if (!signe(y)) pari_err_INV("FpX_divrem",y);
     325                 :      51800 :   vx=varn(x); dy=degpol(y); dx=degpol(x);
     326         [ +  + ]:      51800 :   if (dx < dy)
     327                 :            :   {
     328         [ +  - ]:         10 :     if (pr)
     329                 :            :     {
     330                 :         10 :       av0 = avma; x = FpXQX_red(x, T, p);
     331 [ -  + ][ #  # ]:         10 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: pol_0(vx); }
     332         [ -  + ]:         10 :       if (pr == ONLY_REM) return x;
     333                 :         10 :       *pr = x;
     334                 :            :     }
     335                 :         10 :     return pol_0(vx);
     336                 :            :   }
     337                 :      51790 :   lead = leading_term(y);
     338         [ +  + ]:      51790 :   if (!dy) /* y is constant */
     339                 :            :   {
     340 [ +  - ][ +  - ]:        442 :     if (pr && pr != ONLY_DIVIDES)
     341                 :            :     {
     342         [ +  + ]:        442 :       if (pr == ONLY_REM) return pol_0(vx);
     343                 :        325 :       *pr = pol_0(vx);
     344                 :            :     }
     345         [ -  + ]:        325 :     if (gequal1(lead)) return FpXQX_red(x,T,p);
     346                 :        325 :     av0 = avma; x = FqX_Fq_mul(x, Fq_inv(lead, T,p), T,p);
     347                 :        325 :     return gerepileupto(av0,x);
     348                 :            :   }
     349                 :      51348 :   av0 = avma; dz = dx-dy;
     350         [ +  + ]:      51348 :   if (lgefint(p) == 3)
     351                 :            :   { /* assume ab != 0 mod p */
     352                 :            :     {
     353                 :            :       GEN *gptr[2];
     354                 :            :       GEN a, b, t;
     355                 :      24095 :       ulong pp = to_FlxqX(x, y, T, p, &a, &b, &t);
     356                 :      24095 :       z = FlxqX_divrem(a,b,t,pp,pr);
     357                 :      24095 :       tetpil=avma;
     358                 :      24095 :       z = FlxX_to_ZXX(z);
     359 [ +  + ][ +  - ]:      24095 :       if (pr && pr != ONLY_DIVIDES && pr != ONLY_REM)
                 [ +  + ]
     360                 :      22171 :         *pr = FlxX_to_ZXX(*pr);
     361                 :      24095 :       else return gerepile(av0,tetpil,z);
     362                 :      22171 :       gptr[0]=pr; gptr[1]=&z;
     363                 :      22171 :       gerepilemanysp(av0,tetpil,gptr,2);
     364                 :      22171 :       return z;
     365                 :            :     }
     366                 :            :   }
     367         [ +  + ]:      27253 :   lead = gequal1(lead)? NULL: gclone(Fq_inv(lead,T,p));
     368                 :      27253 :   avma = av0;
     369                 :      27253 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
     370                 :      27253 :   x += 2; y += 2; z += 2;
     371                 :            : 
     372                 :      27253 :   p1 = gel(x,dx); av = avma;
     373         [ +  + ]:      27253 :   gel(z,dz) = lead? gerepileupto(av, Fq_mul(p1,lead, T, p)): gcopy(p1);
     374         [ +  + ]:     274197 :   for (i=dx-1; i>=dy; i--)
     375                 :            :   {
     376                 :     246944 :     av=avma; p1=gel(x,i);
     377 [ +  + ][ +  + ]:    3303449 :     for (j=i-dy+1; j<=i && j<=dz; j++)
     378                 :    3056505 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j),NULL,p),NULL,p);
     379         [ +  + ]:     246944 :     if (lead) p1 = Fq_mul(p1, lead, NULL,p);
     380                 :     246944 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil,Fq_red(p1,T,p));
     381                 :            :   }
     382 [ +  + ][ -  + ]:      27253 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
     383                 :            : 
     384                 :      27250 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     385                 :      27250 :   for (sx=0; ; i--)
     386                 :            :   {
     387                 :      30737 :     p1 = gel(x,i);
     388 [ +  + ][ +  + ]:     306678 :     for (j=0; j<=i && j<=dz; j++)
     389                 :     275941 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j),NULL,p),NULL,p);
     390         [ +  + ]:      30737 :     tetpil=avma; p1 = Fq_red(p1, T, p); if (signe(p1)) { sx = 1; break; }
     391         [ +  + ]:       3546 :     if (!i) break;
     392                 :       3487 :     avma=av;
     393                 :       3487 :   }
     394         [ -  + ]:      27250 :   if (pr == ONLY_DIVIDES)
     395                 :            :   {
     396         [ #  # ]:          0 :     if (lead) gunclone(lead);
     397         [ #  # ]:          0 :     if (sx) { avma=av0; return NULL; }
     398                 :          0 :     avma = (pari_sp)rem; return z-2;
     399                 :            :   }
     400                 :      27250 :   lr=i+3; rem -= lr;
     401                 :      27250 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     402                 :      27250 :   rem[1] = z[-1];
     403                 :      27250 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
     404                 :      27250 :   rem += 2; gel(rem,i) = p1;
     405         [ +  + ]:     406957 :   for (i--; i>=0; i--)
     406                 :            :   {
     407                 :     379707 :     av=avma; p1 = gel(x,i);
     408 [ +  + ][ +  + ]:    3852106 :     for (j=0; j<=i && j<=dz; j++)
     409                 :    3472399 :       p1 = Fq_sub(p1, Fq_mul(gel(z,j),gel(y,i-j), NULL,p), NULL,p);
     410                 :     379707 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, Fq_red(p1, T, p));
     411                 :            :   }
     412                 :      27250 :   rem -= 2;
     413         [ +  + ]:      27250 :   if (lead) gunclone(lead);
     414         [ +  + ]:      27250 :   if (!sx) (void)FpXQX_renormalize(rem, lr);
     415         [ +  + ]:      27250 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
     416                 :      51800 :   *pr = rem; return z-2;
     417                 :            : }
     418                 :            : 
     419                 :            : GEN
     420                 :       2893 : FpXQX_gcd(GEN P, GEN Q, GEN T, GEN p)
     421                 :            : {
     422                 :       2893 :   pari_sp av=avma, av0;
     423                 :            :   GEN R;
     424         [ +  + ]:       2893 :   if (lgefint(p) == 3)
     425                 :            :   {
     426                 :            :     GEN Pl, Ql, Tl, U;
     427                 :       2723 :     ulong pp = to_FlxqX(P, Q, T, p, &Pl, &Ql, &Tl);
     428                 :       2723 :     U  = FlxqX_gcd(Pl, Ql, Tl, pp);
     429                 :       2723 :     return gerepileupto(av, FlxX_to_ZXX(U));
     430                 :            :   }
     431                 :        170 :   P = FpXX_red(P, p); av0 = avma;
     432                 :        170 :   Q = FpXX_red(Q, p);
     433         [ +  + ]:       4722 :   while (signe(Q))
     434                 :            :   {
     435                 :       4552 :     av0 = avma; R = FpXQX_rem(P,Q,T,p); P=Q; Q=R;
     436                 :            :   }
     437                 :       2893 :   avma = av0; return gerepileupto(av, P);
     438                 :            : }
     439                 :            : 
     440                 :            : /* x and y in Z[Y][X], return lift(gcd(x mod T,p, y mod T,p)). Set u and v st
     441                 :            :  * ux + vy = gcd (mod T,p) */
     442                 :            : GEN
     443                 :       3780 : FpXQX_extgcd(GEN x, GEN y, GEN T, GEN p, GEN *ptu, GEN *ptv)
     444                 :            : {
     445                 :            :   GEN a, b, q, r, u, v, d, d1, v1;
     446                 :       3780 :   long vx = varn(x);
     447                 :       3780 :   pari_sp ltop=avma;
     448         [ +  + ]:       3780 :   if (lgefint(p) == 3)
     449                 :            :   {
     450                 :            :     GEN Pl, Ql, Tl, Dl;
     451                 :       3455 :     ulong pp = to_FlxqX(x, y, T, p, &Pl, &Ql, &Tl);
     452                 :       3455 :     Dl = FlxqX_extgcd(Pl, Ql, Tl, pp, ptu, ptv);
     453         [ +  - ]:       3455 :     if (ptu) *ptu = FlxX_to_ZXX(*ptu);
     454                 :       3455 :     *ptv = FlxX_to_ZXX(*ptv);
     455                 :       3455 :     d = FlxX_to_ZXX(Dl);
     456                 :            :   }
     457                 :            :   else
     458                 :            :   {
     459                 :        325 :     a = FpXQX_red(x, T, p);
     460                 :        325 :     b = FpXQX_red(y, T, p);
     461                 :        325 :     d = a; d1 = b; v = pol_0(vx); v1 = pol_1(vx);
     462         [ +  + ]:       5515 :     while (signe(d1))
     463                 :            :     {
     464                 :       5190 :       q = FpXQX_divrem(d,d1,T,p, &r);
     465                 :       5190 :       v = FpXX_sub(v, FpXQX_mul(q,v1, T,p), p);
     466                 :       5190 :       u=v; v=v1; v1=u;
     467                 :       5190 :       u=r; d=d1; d1=u;
     468                 :            :     }
     469         [ -  + ]:        325 :     if (ptu) *ptu = FpXQX_div(FpXX_sub(d, FpXQX_mul(b,v, T,p), p),a, T,p);
     470                 :        325 :     *ptv = v;
     471                 :            :   }
     472         [ +  + ]:       3780 :   gerepileall(ltop,ptu?3:2,&d,ptv,ptu);
     473                 :       3780 :   return d;
     474                 :            : }
     475                 :            : 
     476                 :            : /***********************************************************************/
     477                 :            : /**                                                                   **/
     478                 :            : /**                       Barrett reduction                           **/
     479                 :            : /**                                                                   **/
     480                 :            : /***********************************************************************/
     481                 :            : 
     482                 :            : /* Return new lgpol */
     483                 :            : static long
     484                 :      20680 : ZXX_lgrenormalizespec(GEN x, long lx)
     485                 :            : {
     486                 :            :   long i;
     487         [ +  - ]:      21000 :   for (i = lx-1; i>=0; i--)
     488         [ +  + ]:      21000 :     if (signe(gel(x,i))) break;
     489                 :      20680 :   return i+1;
     490                 :            : }
     491                 :            : 
     492                 :            : static GEN
     493                 :        245 : FpXQX_invBarrett_basecase(GEN S, GEN T, GEN p)
     494                 :            : {
     495                 :        245 :   long i, l=lg(S)-1, lr = l-1, k;
     496                 :        245 :   GEN r=cgetg(lr, t_POL); r[1]=S[1];
     497                 :        245 :   gel(r,2) = gen_1;
     498         [ +  + ]:       7595 :   for (i=3; i<lr; i++)
     499                 :            :   {
     500                 :       7350 :     pari_sp av = avma;
     501                 :       7350 :     GEN u = gel(S,l-i+2);
     502         [ +  + ]:     113925 :     for (k=3; k<i; k++)
     503                 :     106575 :       u = Fq_add(u, Fq_mul(gel(S,l-i+k), gel(r,k), NULL, p), NULL, p);
     504                 :       7350 :     gel(r,i) = gerepileupto(av, Fq_red(Fq_neg(u, NULL, p), T, p));
     505                 :            :   }
     506                 :        245 :   return FpXQX_renormalize(r,lr);
     507                 :            : }
     508                 :            : 
     509                 :            : INLINE GEN
     510                 :       2950 : FpXQX_recipspec(GEN x, long l, long n)
     511                 :            : {
     512                 :       2950 :   return RgX_recipspec_shallow(x, l, n);
     513                 :            : }
     514                 :            : 
     515                 :            : static GEN
     516                 :        985 : FpXQX_invBarrett_Newton(GEN S, GEN T, GEN p)
     517                 :            : {
     518                 :        985 :   pari_sp av = avma;
     519                 :        985 :   long nold, lx, lz, lq, l = degpol(S), i, lQ;
     520                 :        985 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
     521                 :        985 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
     522         [ +  + ]:      56365 :   for (i=0;i<l;i++) gel(x,i) = gen_0;
     523                 :        985 :   q = RgX_recipspec_shallow(S+2,l+1,l+1); lQ = lgpol(q); q+=2;
     524                 :            :   /* We work on _spec_ FpX's, all the l[xzq] below are lgpol's */
     525                 :            : 
     526                 :            :   /* initialize */
     527                 :        985 :   gel(x,0) = Fq_inv(gel(q,0), T, p);
     528         [ +  - ]:        985 :   if (lQ>1) gel(q,1) = Fq_red(gel(q,1), T, p);
     529 [ +  - ][ +  - ]:        985 :   if (lQ>1 && signe(gel(q,1)))
     530                 :        985 :   {
     531                 :        985 :     GEN u = gel(q, 1);
     532         [ -  + ]:        985 :     if (!gequal1(gel(x,0))) u = Fq_mul(u, Fq_sqr(gel(x,0), T, p), T, p);
     533                 :        985 :     gel(x,1) = Fq_neg(u, T, p); lx = 2;
     534                 :            :   }
     535                 :            :   else
     536                 :          0 :     lx = 1;
     537                 :        985 :   nold = 1;
     538         [ +  + ]:       6895 :   for (; mask > 1; )
     539                 :            :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
     540                 :       5910 :     long i, lnew, nnew = nold << 1;
     541                 :            : 
     542         [ +  + ]:       5910 :     if (mask & 1) nnew--;
     543                 :       5910 :     mask >>= 1;
     544                 :            : 
     545                 :       5910 :     lnew = nnew + 1;
     546                 :       5910 :     lq = ZXX_lgrenormalizespec(q, minss(lQ,lnew));
     547                 :       5910 :     z = FpXQX_mulspec(x, q, T, p, lx, lq); /* FIXME: high product */
     548         [ +  - ]:       5910 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
     549                 :       5910 :     z += 2;
     550                 :            :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
     551 [ +  + ][ +  - ]:      11820 :     for (i = nold; i < lz; i++) if (signe(gel(z,i))) break;
     552                 :       5910 :     nold = nnew;
     553         [ -  + ]:       5910 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
     554                 :            : 
     555                 :            :     /* z + i represents (x*q - 1) / t^i */
     556                 :       5910 :     lz = ZXX_lgrenormalizespec (z+i, lz-i);
     557                 :       5910 :     z = FpXQX_mulspec(x, z+i, T, p, lx, lz); /* FIXME: low product */
     558                 :       5910 :     lz = lgpol(z); z += 2;
     559         [ +  - ]:       5910 :     if (lz > lnew-i) lz = ZXX_lgrenormalizespec(z, lnew-i);
     560                 :            : 
     561                 :       5910 :     lx = lz+ i;
     562                 :       5910 :     y  = x + i; /* x -= z * t^i, in place */
     563         [ +  + ]:      58335 :     for (i = 0; i < lz; i++) gel(y,i) = Fq_neg(gel(z,i), T, p);
     564                 :            :   }
     565                 :        985 :   x -= 2; setlg(x, lx + 2); x[1] = S[1];
     566                 :        985 :   return gerepilecopy(av, x);
     567                 :            : }
     568                 :            : 
     569                 :            : const long FpXQX_INVBARRETT_LIMIT = 50;
     570                 :            : const long FpXQX_DIVREM_BARRETT_LIMIT = 50;
     571                 :            : const long FpXQX_REM_BARRETT_LIMIT = 50;
     572                 :            : 
     573                 :            : /* 1/polrecip(S)+O(x^(deg(S)-1)) */
     574                 :            : GEN
     575                 :       1230 : FpXQX_invBarrett(GEN S, GEN T, GEN p)
     576                 :            : {
     577                 :       1230 :   pari_sp ltop = avma;
     578                 :       1230 :   long l = lg(S);
     579                 :            :   GEN r;
     580         [ -  + ]:       1230 :   if (l<5) return pol_0(varn(S));
     581         [ +  + ]:       1230 :   if (l<=FpXQX_INVBARRETT_LIMIT)
     582                 :            :   {
     583                 :        245 :     GEN c = gel(S,l-1), ci=gen_1;
     584         [ -  + ]:        245 :     if (!gequal1(c))
     585                 :            :     {
     586                 :          0 :       ci = Fq_inv(c, T, p);
     587                 :          0 :       S = FqX_Fq_mul(S, ci, T, p);
     588                 :          0 :       r = FpXQX_invBarrett_basecase(S, T, p);
     589                 :          0 :       r = FqX_Fq_mul(r, ci, T, p);
     590                 :            :     } else
     591                 :        245 :       r = FpXQX_invBarrett_basecase(S, T, p);
     592                 :            :   }
     593                 :            :   else
     594                 :        985 :     r = FpXQX_invBarrett_Newton(S, T, p);
     595                 :       1230 :   return gerepileupto(ltop, r);
     596                 :            : }
     597                 :            : 
     598                 :            : /* Compute x mod S where 2 <= degpol(S) <= l+1 <= 2*(degpol(S)-1)
     599                 :            :  * and mg is the Barrett inverse of S. */
     600                 :            : static GEN
     601                 :       1475 : FpXQX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN S, GEN T, GEN p, GEN *pr)
     602                 :            : {
     603                 :            :   GEN q, r;
     604                 :       1475 :   long lt = degpol(S); /*We discard the leading term*/
     605                 :            :   long ld, lm, lT, lmg;
     606                 :       1475 :   ld = l-lt;
     607                 :       1475 :   lm = minss(ld, lgpol(mg));
     608                 :       1475 :   lT  = ZXX_lgrenormalizespec(S+2,lt);
     609                 :       1475 :   lmg = ZXX_lgrenormalizespec(mg+2,lm);
     610                 :       1475 :   q = FpXQX_recipspec(x+lt,ld,ld);                 /* q = rec(x)     lq<=ld*/
     611                 :       1475 :   q = FpXQX_mulspec(q+2,mg+2,T,p,lgpol(q),lmg);    /* q = rec(x) * mg lq<=ld+lm*/
     612                 :       1475 :   q = FpXQX_recipspec(q+2,minss(ld,lgpol(q)),ld);  /* q = rec (rec(x) * mg) lq<=ld*/
     613         [ -  + ]:       1475 :   if (!pr) return q;
     614                 :       1475 :   r = FpXQX_mulspec(q+2,S+2,T,p,lgpol(q),lT);      /* r = q*pol        lr<=ld+lt*/
     615                 :       1475 :   r = FpXX_subspec(x,r+2,p,lt,minss(lt,lgpol(r))); /* r = x - r   lr<=lt */
     616         [ -  + ]:       1475 :   if (pr == ONLY_REM) return r;
     617                 :       1475 :   *pr = r; return q;
     618                 :            : }
     619                 :            : 
     620                 :            : static GEN
     621                 :       1230 : FpXQX_divrem_Barrett_noGC(GEN x, GEN mg, GEN S, GEN T, GEN p, GEN *pr)
     622                 :            : {
     623                 :       1230 :   long l = lgpol(x), lt = degpol(S), lm = 2*lt-1;
     624                 :       1230 :   GEN q = NULL, r;
     625                 :            :   long i;
     626         [ -  + ]:       1230 :   if (l <= lt)
     627                 :            :   {
     628         [ #  # ]:          0 :     if (pr == ONLY_REM) return ZXX_copy(x);
     629 [ #  # ][ #  # ]:          0 :     if (pr == ONLY_DIVIDES) return signe(x)? NULL: pol_0(varn(x));
     630         [ #  # ]:          0 :     if (pr) *pr =  ZXX_copy(x);
     631                 :          0 :     return pol_0(varn(x));
     632                 :            :   }
     633         [ -  + ]:       1230 :   if (lt <= 1)
     634                 :          0 :     return FpXQX_divrem_basecase(x,S,T,p,pr);
     635 [ +  + ][ +  - ]:       1230 :   if (pr != ONLY_REM && l>lm)
     636                 :            :   {
     637                 :        245 :     q = cgetg(l-lt+2, t_POL);
     638         [ +  + ]:      15070 :     for (i=0;i<l-lt;i++) gel(q+2,i) = gen_0;
     639                 :            :   }
     640         [ +  + ]:       1230 :   r = l>lm ? shallowcopy(x): x;
     641         [ +  + ]:       1555 :   while (l>lm)
     642                 :            :   {
     643                 :        325 :     GEN zr, zq = FpXQX_divrem_Barrettspec(r+2+l-lm,lm,mg,S,T,p,&zr);
     644                 :        325 :     long lz = lgpol(zr);
     645         [ +  - ]:        325 :     if (pr != ONLY_REM)
     646                 :            :     {
     647                 :        325 :       long lq = lgpol(zq);
     648         [ +  + ]:      10400 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
     649                 :            :     }
     650         [ +  + ]:      10475 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
     651                 :        325 :     l = l-lm+lz;
     652                 :            :   }
     653         [ +  + ]:       1230 :   if (pr != ONLY_REM)
     654                 :            :   {
     655         [ +  + ]:        245 :     if (l > lt)
     656                 :            :     {
     657                 :        165 :       GEN zq = FpXQX_divrem_Barrettspec(r+2,l,mg,S,T,p,&r);
     658         [ -  + ]:        165 :       if (!q) q = zq;
     659                 :            :       else
     660                 :            :       {
     661                 :        165 :         long lq = lgpol(zq);
     662         [ +  + ]:       4670 :         for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
     663                 :            :       }
     664                 :            :     }
     665                 :            :     else
     666                 :         80 :     { setlg(r, l+2); r = ZXX_copy(r); }
     667                 :            :   }
     668                 :            :   else
     669                 :            :   {
     670         [ +  - ]:        985 :     if (l > lt)
     671                 :        985 :       (void) FpXQX_divrem_Barrettspec(r+2,l,mg,S,T,p,&r);
     672                 :            :     else
     673                 :          0 :     { setlg(r, l+2); r = ZXX_copy(r); }
     674                 :        985 :     r[1] = x[1]; return FpXQX_renormalize(r, lg(r));
     675                 :            :   }
     676         [ +  - ]:        245 :   if (pr) { r[1] = x[1]; r = FpXQX_renormalize(r, lg(r)); }
     677                 :        245 :   q[1] = x[1]; q = FpXQX_renormalize(q, lg(q));
     678 [ -  + ][ #  # ]:        245 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
     679         [ +  - ]:        245 :   if (pr) *pr = r;
     680                 :       1230 :   return q;
     681                 :            : }
     682                 :            : 
     683                 :            : GEN
     684                 :          0 : FpXQX_divrem_Barrett(GEN x, GEN B, GEN S, GEN T, GEN p, GEN *pr)
     685                 :            : {
     686                 :          0 :   pari_sp av = avma;
     687                 :          0 :   GEN q = FpXQX_divrem_Barrett_noGC(x,B,S,T,p,pr);
     688         [ #  # ]:          0 :   if (!q) {avma=av; return NULL;}
     689 [ #  # ][ #  # ]:          0 :   if (!pr || pr==ONLY_REM || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
                 [ #  # ]
     690                 :          0 :   gerepileall(av,2,&q,pr);
     691                 :          0 :   return q;
     692                 :            : }
     693                 :            : 
     694                 :            : GEN
     695                 :      34108 : FpXQX_divrem(GEN x, GEN y, GEN T, GEN p, GEN *pr)
     696                 :            : {
     697                 :      34108 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
     698         [ -  + ]:      34108 :   if (pr==ONLY_REM) return FpXQX_rem(x, y, T, p);
     699         [ +  + ]:      34108 :   if (d+3 < FpXQX_DIVREM_BARRETT_LIMIT)
     700                 :      33863 :     return FpXQX_divrem_basecase(x,y,T,p,pr);
     701                 :            :   else
     702                 :            :   {
     703                 :        245 :     pari_sp av=avma;
     704                 :        245 :     GEN mg = FpXQX_invBarrett(y, T, p);
     705                 :        245 :     GEN q = FpXQX_divrem_Barrett_noGC(x,mg,y,T,p,pr);
     706         [ -  + ]:        245 :     if (!q) {avma=av; return NULL;}
     707 [ +  - ][ -  + ]:        245 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, q);
     708                 :        245 :     gerepileall(av,2,&q,pr);
     709                 :      34108 :     return q;
     710                 :            :   }
     711                 :            : }
     712                 :            : 
     713                 :            : GEN
     714                 :          0 : FpXQX_rem_Barrett(GEN x, GEN mg, GEN S, GEN T, GEN p)
     715                 :            : {
     716                 :          0 :   pari_sp av = avma;
     717                 :          0 :   return gerepileupto(av, FpXQX_divrem_Barrett_noGC(x,mg,S, T, p, ONLY_REM));
     718                 :            : }
     719                 :            : 
     720                 :            : GEN
     721                 :      21341 : FpXQX_rem(GEN x, GEN y, GEN T, GEN p)
     722                 :            : {
     723                 :      21341 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
     724         [ +  + ]:      21341 :   if (d < 0) return FpXQX_red(x, T, p);
     725         [ +  + ]:      18922 :   if (d+3 < FpXQX_REM_BARRETT_LIMIT)
     726                 :      17937 :     return FpXQX_divrem_basecase(x,y, T, p, ONLY_REM);
     727                 :            :   else
     728                 :            :   {
     729                 :        985 :     pari_sp av=avma;
     730                 :        985 :     GEN mg = FpXQX_invBarrett(y, T, p);
     731                 :        985 :     GEN r = FpXQX_divrem_Barrett_noGC(x, mg, y, T, p, ONLY_REM);
     732                 :      21341 :     return gerepileupto(av, r);
     733                 :            :   }
     734                 :            : }
     735                 :            : 
     736                 :            : struct _FpXQX { GEN T,p; };
     737                 :        337 : static GEN _FpXQX_mul(void *data, GEN a,GEN b)
     738                 :            : {
     739                 :        337 :   struct _FpXQX *d=(struct _FpXQX*)data;
     740                 :        337 :   return FpXQX_mul(a,b,d->T,d->p);
     741                 :            : }
     742                 :            : GEN
     743                 :         91 : FpXQXV_prod(GEN V, GEN T, GEN p)
     744                 :            : {
     745         [ -  + ]:         91 :   if (lgefint(p) == 3)
     746                 :            :   {
     747                 :          0 :     pari_sp av = avma;
     748                 :          0 :     ulong pp = p[2];
     749                 :          0 :     GEN Tl = ZXT_to_FlxT(T, pp);
     750                 :          0 :     GEN Vl = ZXXV_to_FlxXV(V, pp, get_FpX_var(T));
     751                 :          0 :     Tl = FlxqXV_prod(Vl, Tl, pp);
     752                 :          0 :     return gerepileupto(av, FlxX_to_ZXX(Tl));
     753                 :            :   }
     754                 :            :   else
     755                 :            :   {
     756                 :            :     struct _FpXQX d;
     757                 :         91 :     d.p=p;
     758                 :         91 :     d.T=T;
     759                 :         91 :     return divide_conquer_assoc(V, (void*)&d, &_FpXQX_mul);
     760                 :            :   }
     761                 :            : }
     762                 :            : 
     763                 :            : /* Q an FpXY (t_POL with FpX coeffs), evaluate at X = x */
     764                 :            : GEN
     765                 :      11602 : FpXY_evalx(GEN Q, GEN x, GEN p)
     766                 :            : {
     767                 :      11602 :   long i, lb = lg(Q);
     768                 :            :   GEN z;
     769                 :      11602 :   z = cgetg(lb, t_POL); z[1] = Q[1];
     770         [ +  + ]:     132910 :   for (i=2; i<lb; i++)
     771                 :            :   {
     772                 :     121308 :     GEN q = gel(Q,i);
     773         [ +  + ]:     121308 :     gel(z,i) = typ(q) == t_INT? modii(q,p): FpX_eval(q, x, p);
     774                 :            :   }
     775                 :      11602 :   return FpX_renormalize(z, lb);
     776                 :            : }
     777                 :            : /* Q an FpXY, evaluate at Y = y */
     778                 :            : GEN
     779                 :       7880 : FpXY_evaly(GEN Q, GEN y, GEN p, long vx)
     780                 :            : {
     781                 :       7880 :   pari_sp av = avma;
     782                 :       7880 :   long i, lb = lg(Q);
     783                 :            :   GEN z;
     784         [ -  + ]:       7880 :   if (lb == 2) return pol_0(vx);
     785                 :       7880 :   z = gel(Q, lb-1);
     786 [ +  - ][ -  + ]:       7880 :   if (lb == 3 || !signe(y)) return typ(z)==t_INT? scalar_ZX(z, vx): ZX_copy(z);
                 [ #  # ]
     787                 :            : 
     788         [ +  + ]:       7880 :   if (typ(z) == t_INT) z = scalar_ZX_shallow(z, vx);
     789         [ +  + ]:     113400 :   for (i=lb-2; i>=2; i--) z = Fq_add(gel(Q,i), FpX_Fp_mul(z, y, p), NULL, p);
     790                 :       7880 :   return gerepileupto(av, z);
     791                 :            : }
     792                 :            : /* Q an FpXY, evaluate at (X,Y) = (x,y) */
     793                 :            : GEN
     794                 :       5985 : FpXY_eval(GEN Q, GEN y, GEN x, GEN p)
     795                 :            : {
     796                 :       5985 :   pari_sp av = avma;
     797                 :       5985 :   return gerepileuptoint(av, FpX_eval(FpXY_evalx(Q, x, p), y, p));
     798                 :            : }
     799                 :            : 
     800                 :            : GEN
     801                 :        195 : FpXY_FpXQ_evalx(GEN P, GEN x, GEN T, GEN p)
     802                 :            : {
     803                 :        195 :   long i, lP = lg(P);
     804                 :        195 :   GEN res = cgetg(lP,t_POL);
     805                 :        195 :   res[1] = P[1];
     806         [ +  + ]:       3866 :   for(i=2; i<lP; i++)
     807                 :       3671 :     gel(res,i) = FpX_FpXQ_eval(gel(P,i), x, T, p);
     808                 :        195 :   return FlxX_renormalize(res, lP);
     809                 :            : }
     810                 :            : 
     811                 :            : /*******************************************************************/
     812                 :            : /*                                                                 */
     813                 :            : /*                       (Fp[X]/T(X))[Y] / S(Y)                    */
     814                 :            : /*                                                                 */
     815                 :            : /*******************************************************************/
     816                 :            : 
     817                 :            : /*Preliminary implementation to speed up FpX_ffisom*/
     818                 :            : typedef struct {
     819                 :            :   GEN S, T, p;
     820                 :            : } FpXYQQ_muldata;
     821                 :            : 
     822                 :            : /* reduce x in Fp[X, Y] in the algebra Fp[X,Y]/ (S(X),T(Y)) */
     823                 :            : static GEN
     824                 :         80 : FpXYQQ_redswap(GEN x, GEN S, GEN T, GEN p)
     825                 :            : {
     826                 :         80 :   pari_sp ltop=avma;
     827                 :         80 :   long n = get_FpX_degree(S);
     828                 :         80 :   long m = get_FpX_degree(T);
     829                 :         80 :   long v = get_FpX_var(T);
     830                 :         80 :   GEN V = RgXY_swap(x,m,v);
     831                 :         80 :   V = FpXQX_red(V,S,p);
     832                 :         80 :   V = RgXY_swap(V,n,v);
     833                 :         80 :   return gerepilecopy(ltop,V);
     834                 :            : }
     835                 :            : static GEN
     836                 :         50 : FpXYQQ_sqr(void *data, GEN x)
     837                 :            : {
     838                 :         50 :   FpXYQQ_muldata *D = (FpXYQQ_muldata*)data;
     839                 :         50 :   return FpXYQQ_redswap(FpXQX_sqr(x, D->T, D->p),D->S,D->T,D->p);
     840                 :            : 
     841                 :            : }
     842                 :            : static GEN
     843                 :         30 : FpXYQQ_mul(void *data, GEN x, GEN y)
     844                 :            : {
     845                 :         30 :   FpXYQQ_muldata *D = (FpXYQQ_muldata*)data;
     846                 :         30 :   return FpXYQQ_redswap(FpXQX_mul(x,y, D->T, D->p),D->S,D->T,D->p);
     847                 :            : }
     848                 :            : 
     849                 :            : /* x in Z[X,Y], S in Z[X] over Fq = Z[Y]/(p,T); compute lift(x^n mod (S,T,p)) */
     850                 :            : GEN
     851                 :       1024 : FpXYQQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
     852                 :            : {
     853                 :       1024 :   pari_sp av = avma;
     854                 :            :   FpXYQQ_muldata D;
     855                 :            :   GEN y;
     856         [ +  + ]:       1024 :   if (lgefint(p) == 3)
     857                 :            :   {
     858                 :       1004 :     ulong pp = to_FlxqX(x, NULL, T, p, &x, NULL, &T);
     859                 :       1004 :     S = ZX_to_Flx(S, pp);
     860                 :       1004 :     y = FlxX_to_ZXX( FlxYqq_pow(x, n, S, T, pp) );
     861                 :            :   }
     862                 :            :   else
     863                 :            :   {
     864                 :         20 :     D.S = S;
     865                 :         20 :     D.T = T;
     866                 :         20 :     D.p = p;
     867                 :         20 :     y = gen_pow(x, n, (void*)&D, &FpXYQQ_sqr, &FpXYQQ_mul);
     868                 :            :   }
     869                 :       1024 :   return gerepileupto(av, y);
     870                 :            : }
     871                 :            : 
     872                 :            : GEN
     873                 :       3653 : FpXQXQ_mul(GEN x, GEN y, GEN S, GEN T, GEN p) {
     874                 :       3653 :   return FpXQX_rem(FpXQX_mul(x, y, T, p), S, T, p);
     875                 :            : }
     876                 :            : 
     877                 :            : GEN
     878                 :      12776 : FpXQXQ_sqr(GEN x, GEN S, GEN T, GEN p) {
     879                 :      12776 :   return FpXQX_rem(FpXQX_sqr(x, T, p), S, T, p);
     880                 :            : }
     881                 :            : 
     882                 :            : /* Inverse of x in Z/pZ[X]/(pol) or NULL if inverse doesn't exist
     883                 :            :  * return lift(1 / (x mod (p,pol))) */
     884                 :            : GEN
     885                 :        325 : FpXQXQ_invsafe(GEN x, GEN S, GEN T, GEN p)
     886                 :            : {
     887                 :        325 :   GEN V, z = FpXQX_extgcd(S, x, T, p, NULL, &V);
     888         [ -  + ]:        325 :   if (degpol(z)) return NULL;
     889                 :        325 :   z = gel(z,2);
     890         [ -  + ]:        325 :   z = typ(z)==t_INT ? Fp_invsafe(z,p) : FpXQ_invsafe(z,T,p);
     891         [ -  + ]:        325 :   if (!z) return NULL;
     892         [ -  + ]:        325 :   return typ(z)==t_INT ? FpXX_Fp_mul(V, z, p): FpXQX_FpXQ_mul(V, z, T, p);
     893                 :            : }
     894                 :            : 
     895                 :            : GEN
     896                 :        325 : FpXQXQ_inv(GEN x, GEN S, GEN T,GEN p)
     897                 :            : {
     898                 :        325 :   pari_sp av = avma;
     899                 :        325 :   GEN U = FpXQXQ_invsafe(x, S, T, p);
     900         [ -  + ]:        325 :   if (!U) pari_err_INV("FpXQXQ_inv",x);
     901                 :        325 :   return gerepileupto(av, U);
     902                 :            : }
     903                 :            : 
     904                 :            : GEN
     905                 :        325 : FpXQXQ_div(GEN x,GEN y,GEN S, GEN T,GEN p)
     906                 :            : {
     907                 :        325 :   pari_sp av = avma;
     908                 :        325 :   return gerepileupto(av, FpXQXQ_mul(x, FpXQXQ_inv(y,S,T,p),S,T,p));
     909                 :            : }
     910                 :            : 
     911                 :            : typedef struct {
     912                 :            :   GEN T, S;
     913                 :            :   GEN p;
     914                 :            : } FpXQXQ_muldata;
     915                 :            : static GEN
     916                 :       3476 : _FpXQXQ_add(void *data, GEN x, GEN y) {
     917                 :       3476 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     918                 :       3476 :   return FpXX_add(x,y, d->p);
     919                 :            : }
     920                 :            : static GEN
     921                 :       3671 : _FpXQXQ_cmul(void *data, GEN P, long a, GEN x) {
     922                 :       3671 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     923                 :       3671 :   GEN y = gel(P,a+2);
     924         [ -  + ]:       3671 :   return typ(y)==t_INT ? FpXX_Fp_mul(x,y, d->p):
     925                 :       3671 :                          FpXX_FpX_mul(x,y,d->p);
     926                 :            : }
     927                 :            : static GEN
     928                 :        942 : _FpXQXQ_red(void *data, GEN x) {
     929                 :        942 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     930                 :        942 :   return FpXQX_red(x, d->T, d->p);
     931                 :            : }
     932                 :            : static GEN
     933                 :       2610 : _FpXQXQ_mul(void *data, GEN x, GEN y) {
     934                 :       2610 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     935                 :       2610 :   return FpXQXQ_mul(x,y, d->S,d->T, d->p);
     936                 :            : }
     937                 :            : static GEN
     938                 :      12486 : _FpXQXQ_sqr(void *data, GEN x) {
     939                 :      12486 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     940                 :      12486 :   return FpXQXQ_sqr(x, d->S,d->T, d->p);
     941                 :            : }
     942                 :            : 
     943                 :            : static GEN
     944                 :        950 : _FpXQXQ_one(void *data) {
     945                 :        950 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     946                 :        950 :   return pol_1(varn(d->S));
     947                 :            : }
     948                 :            : 
     949                 :            : static GEN
     950                 :          0 : _FpXQXQ_zero(void *data) {
     951                 :          0 :   FpXQXQ_muldata *d = (FpXQXQ_muldata*) data;
     952                 :          0 :   return pol_0(varn(d->S));
     953                 :            : }
     954                 :            : 
     955                 :            : static struct bb_algebra FpXQXQ_algebra = { _FpXQXQ_red,_FpXQXQ_add,_FpXQXQ_mul,_FpXQXQ_sqr,_FpXQXQ_one,_FpXQXQ_zero };
     956                 :            : 
     957                 :            : /* x over Fq, return lift(x^n) mod S */
     958                 :            : GEN
     959                 :        185 : FpXQXQ_pow(GEN x, GEN n, GEN S, GEN T, GEN p)
     960                 :            : {
     961                 :        185 :   pari_sp ltop = avma;
     962                 :            :   GEN y;
     963                 :            :   FpXQXQ_muldata D;
     964                 :        185 :   long s = signe(n);
     965         [ -  + ]:        185 :   if (!s) return pol_1(varn(x));
     966         [ -  + ]:        185 :   if (is_pm1(n)) /* +/- 1 */
     967         [ #  # ]:          0 :     return (s < 0)? FpXQXQ_inv(x,S,T,p): ZXX_copy(x);
     968         [ -  + ]:        185 :   if (lgefint(p) == 3)
     969                 :            :   {
     970                 :          0 :     ulong pp = to_FlxqX(x, S, T, p, &x, &S, &T);
     971                 :          0 :     GEN z = FlxqXQ_pow(x, n, S, T, pp);
     972                 :          0 :     y = FlxX_to_ZXX(z);
     973                 :            :   }
     974                 :            :   else
     975                 :            :   {
     976                 :        185 :     D.S = S; D.T = T; D.p = p;
     977         [ -  + ]:        185 :     if (s < 0) x = FpXQXQ_inv(x,S,T,p);
     978                 :        185 :     y = gen_pow(x, n, (void*)&D,&_FpXQXQ_sqr,&_FpXQXQ_mul);
     979                 :            :   }
     980                 :        185 :   return gerepileupto(ltop, y);
     981                 :            : }
     982                 :            : 
     983                 :            : /* generates the list of powers of x of degree 0,1,2,...,l*/
     984                 :            : GEN
     985                 :         90 : FpXQXQ_powers(GEN x, long l, GEN S, GEN T, GEN p)
     986                 :            : {
     987                 :            :   FpXQXQ_muldata D;
     988                 :         90 :   int use_sqr = (degpol(x)<<1) >= degpol(S);
     989                 :         90 :   D.S = S; D.T = T; D.p = p;
     990                 :         90 :   return gen_powers(x, l, use_sqr, (void*)&D, &_FpXQXQ_sqr, &_FpXQXQ_mul,&_FpXQXQ_one);
     991                 :            : }
     992                 :            : 
     993                 :            : GEN
     994                 :         37 : FpXQXQ_matrix_pow(GEN y, long n, long m, GEN S, GEN T, GEN p)
     995                 :            : {
     996                 :         37 :   return RgXV_to_RgM(FpXQXQ_powers(y,m-1,S,T,p),n);
     997                 :            : }
     998                 :            : 
     999                 :            : GEN
    1000                 :        106 : FpXQX_FpXQXQV_eval(GEN P, GEN V, GEN S, GEN T, GEN p)
    1001                 :            : {
    1002                 :            :   FpXQXQ_muldata D;
    1003                 :        106 :   D.S=S; D.T=T; D.p=p;
    1004                 :        106 :   return gen_bkeval_powers(P, degpol(P), V, (void*)&D, &FpXQXQ_algebra,
    1005                 :            :                                                    _FpXQXQ_cmul);
    1006                 :            : }
    1007                 :            : 
    1008                 :            : GEN
    1009                 :         89 : FpXQX_FpXQXQ_eval(GEN Q, GEN x, GEN S, GEN T, GEN p)
    1010                 :            : {
    1011                 :            :   FpXQXQ_muldata D;
    1012                 :         89 :   int use_sqr = (degpol(x)<<1) >= degpol(S);
    1013                 :         89 :   D.S=S; D.T=T; D.p=p;
    1014                 :         89 :   return gen_bkeval(Q, degpol(Q), x, use_sqr, (void*)&D, &FpXQXQ_algebra,
    1015                 :            :                                                     _FpXQXQ_cmul);
    1016                 :            : }
    1017                 :            : 
    1018                 :            : static GEN
    1019                 :         87 : FpXQXQ_autpow_sqr(void * T, GEN x)
    1020                 :            : {
    1021                 :         87 :   FpXQXQ_muldata *D = (FpXQXQ_muldata *)T;
    1022                 :         87 :   GEN phi = gel(x,1), S = gel(x,2);
    1023                 :         87 :   GEN phi2 = FpX_FpXQ_eval(phi,phi,D->T,D->p);
    1024                 :         87 :   GEN Sphi = FpXY_FpXQ_evalx(S,phi,D->T,D->p);
    1025                 :         87 :   GEN S2 = FpXQX_FpXQXQ_eval(Sphi, S, D->S,D->T,D->p);
    1026                 :         87 :   return mkvec2(phi2, S2);
    1027                 :            : }
    1028                 :            : 
    1029                 :            : static GEN
    1030                 :          2 : FpXQXQ_autpow_mul(void * T, GEN x, GEN y)
    1031                 :            : {
    1032                 :          2 :   FpXQXQ_muldata *D = (FpXQXQ_muldata *)T;
    1033                 :          2 :   GEN phi1 = gel(x,1), S1 = gel(x,2);
    1034                 :          2 :   GEN phi2 = gel(y,1), S2 = gel(y,2);
    1035                 :          2 :   GEN phi3 = FpX_FpXQ_eval(phi1,phi2,D->T,D->p);
    1036                 :          2 :   GEN Sphi = FpXY_FpXQ_evalx(S1,phi2,D->T,D->p);
    1037                 :          2 :   GEN S3 = FpXQX_FpXQXQ_eval(Sphi, S2, D->S,D->T,D->p);
    1038                 :          2 :   return mkvec2(phi3, S3);
    1039                 :            : }
    1040                 :            : 
    1041                 :            : GEN
    1042                 :         87 : FpXQXQV_autpow(GEN aut, long n, GEN S, GEN T, GEN p)
    1043                 :            : {
    1044                 :            :   FpXQXQ_muldata D;
    1045                 :         87 :   D.S=S; D.T=T; D.p=p;
    1046                 :         87 :   return gen_powu(aut,n,&D,FpXQXQ_autpow_sqr,FpXQXQ_autpow_mul);
    1047                 :            : }
    1048                 :            : 
    1049                 :            : static GEN
    1050                 :         53 : FpXQXQ_autsum_mul(void * T, GEN x, GEN y)
    1051                 :            : {
    1052                 :         53 :   FpXQXQ_muldata *D = (FpXQXQ_muldata *)T;
    1053                 :         53 :   GEN phi1 = gel(x,1), S1 = gel(x,2), a1 = gel(x,3);
    1054                 :         53 :   GEN phi2 = gel(y,1), S2 = gel(y,2), a2 = gel(y,3);
    1055                 :         53 :   GEN phi3 = FpX_FpXQ_eval(phi1,phi2,D->T,D->p);
    1056                 :         53 :   GEN Sphi = FpXY_FpXQ_evalx(S1,phi2,D->T,D->p);
    1057                 :         53 :   long n = brent_kung_optpow(degpol(D->S)-1,2,1);
    1058                 :         53 :   GEN V = FpXQXQ_powers(S2, n, D->S,D->T,D->p);
    1059                 :         53 :   GEN S3 = FpXQX_FpXQXQV_eval(Sphi, V, D->S,D->T,D->p);
    1060                 :         53 :   GEN aphi = FpXY_FpXQ_evalx(a1,phi2,D->T,D->p);
    1061                 :         53 :   GEN aS = FpXQX_FpXQXQV_eval(aphi,V,D->S,D->T,D->p);
    1062                 :         53 :   GEN a3 = FpXQXQ_mul(aS,a2,D->S,D->T,D->p);
    1063                 :         53 :   return mkvec3(phi3, S3, a3);
    1064                 :            : }
    1065                 :            : 
    1066                 :            : static GEN
    1067                 :         49 : FpXQXQ_autsum_sqr(void * T, GEN x)
    1068                 :         49 : { return FpXQXQ_autsum_mul(T,x,x); }
    1069                 :            : 
    1070                 :            : GEN
    1071                 :         49 : FpXQXQV_autsum(GEN aut, long n, GEN S, GEN T, GEN p)
    1072                 :            : {
    1073                 :            :   FpXQXQ_muldata D;
    1074                 :         49 :   D.S=S; D.T=T; D.p=p;
    1075                 :         49 :   return gen_powu(aut,n,&D,FpXQXQ_autsum_sqr,FpXQXQ_autsum_mul);
    1076                 :            : }

Generated by: LCOV version 1.9