Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - FpX.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.14.0 lcov report (development 27775-aca467eab2) Lines: 1426 1573 90.7 %
Date: 2022-07-03 07:33:15 Functions: 174 187 93.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2007  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : #include "pari.h"
      16             : #include "paripriv.h"
      17             : 
      18             : /* Not so fast arithmetic with polynomials over Fp */
      19             : 
      20             : static GEN
      21    63518585 : get_FpX_red(GEN T, GEN *B)
      22             : {
      23    63518585 :   if (typ(T)!=t_VEC) { *B=NULL; return T; }
      24      164363 :   *B = gel(T,1); return gel(T,2);
      25             : }
      26             : 
      27             : /***********************************************************************/
      28             : /**                                                                   **/
      29             : /**                              FpX                                  **/
      30             : /**                                                                   **/
      31             : /***********************************************************************/
      32             : 
      33             : /* FpX are polynomials over Z/pZ represented as t_POL with
      34             :  * t_INT coefficients.
      35             :  * 1) Coefficients should belong to {0,...,p-1}, though nonreduced
      36             :  * coefficients should work but be slower.
      37             :  *
      38             :  * 2) p is not assumed to be prime, but it is assumed that impossible divisions
      39             :  *    will not happen.
      40             :  * 3) Theses functions let some garbage on the stack, but are gerepileupto
      41             :  * compatible.
      42             :  */
      43             : 
      44             : static ulong
      45    42153502 : to_Flx(GEN *P, GEN *Q, GEN p)
      46             : {
      47    42153502 :   ulong pp = uel(p,2);
      48    42153502 :   *P = ZX_to_Flx(*P, pp);
      49    42146215 :   if(Q) *Q = ZX_to_Flx(*Q, pp);
      50    42145187 :   return pp;
      51             : }
      52             : 
      53             : static ulong
      54     2134485 : to_Flxq(GEN *P, GEN *T, GEN p)
      55             : {
      56     2134485 :   ulong pp = uel(p,2);
      57     2134485 :   if (P) *P = ZX_to_Flx(*P, pp);
      58     2134456 :   *T = ZXT_to_FlxT(*T, pp); return pp;
      59             : }
      60             : 
      61             : GEN
      62        1711 : Z_to_FpX(GEN a, GEN p, long v)
      63             : {
      64        1711 :   pari_sp av = avma;
      65        1711 :   GEN z = cgetg(3, t_POL);
      66        1711 :   GEN x = modii(a, p);
      67        1711 :   if (!signe(x)) { set_avma(av); return pol_0(v); }
      68        1711 :   z[1] = evalsigne(1) | evalvarn(v);
      69        1711 :   gel(z,2) = x; return z;
      70             : }
      71             : 
      72             : /* z in Z[X], return lift(z * Mod(1,p)), normalized*/
      73             : GEN
      74    68586537 : FpX_red(GEN z, GEN p)
      75             : {
      76    68586537 :   long i, l = lg(z);
      77    68586537 :   GEN x = cgetg(l, t_POL);
      78   659041796 :   for (i=2; i<l; i++) gel(x,i) = modii(gel(z,i),p);
      79    68093097 :   x[1] = z[1]; return FpX_renormalize(x,l);
      80             : }
      81             : 
      82             : GEN
      83      403788 : FpXV_red(GEN x, GEN p)
      84     1896196 : { pari_APPLY_type(t_VEC, FpX_red(gel(x,i), p)) }
      85             : 
      86             : GEN
      87     1663675 : FpXT_red(GEN x, GEN p)
      88             : {
      89     1663675 :   if (typ(x) == t_POL)
      90     1575187 :     return FpX_red(x, p);
      91             :   else
      92      393170 :     pari_APPLY_type(t_VEC, FpXT_red(gel(x,i), p))
      93             : }
      94             : 
      95             : GEN
      96     1722695 : FpX_normalize(GEN z, GEN p)
      97             : {
      98     1722695 :   GEN p1 = leading_coeff(z);
      99     1722695 :   if (lg(z) == 2 || equali1(p1)) return z;
     100       97071 :   return FpX_Fp_mul_to_monic(z, Fp_inv(p1,p), p);
     101             : }
     102             : 
     103             : GEN
     104      118416 : FpX_center(GEN T, GEN p, GEN pov2)
     105             : {
     106      118416 :   long i, l = lg(T);
     107      118416 :   GEN P = cgetg(l,t_POL);
     108      611069 :   for(i=2; i<l; i++) gel(P,i) = Fp_center(gel(T,i), p, pov2);
     109      118417 :   P[1] = T[1]; return P;
     110             : }
     111             : GEN
     112     1229625 : FpX_center_i(GEN T, GEN p, GEN pov2)
     113             : {
     114     1229625 :   long i, l = lg(T);
     115     1229625 :   GEN P = cgetg(l,t_POL);
     116     5412511 :   for(i=2; i<l; i++) gel(P,i) = Fp_center_i(gel(T,i), p, pov2);
     117     1229611 :   P[1] = T[1]; return P;
     118             : }
     119             : 
     120             : GEN
     121    10691314 : FpX_add(GEN x,GEN y,GEN p)
     122             : {
     123    10691314 :   long lx = lg(x), ly = lg(y), i;
     124             :   GEN z;
     125    10691314 :   if (lx < ly) swapspec(x,y, lx,ly);
     126    10691314 :   z = cgetg(lx,t_POL); z[1] = x[1];
     127    84312596 :   for (i=2; i<ly; i++) gel(z,i) = Fp_add(gel(x,i),gel(y,i), p);
     128    27951893 :   for (   ; i<lx; i++) gel(z,i) = modii(gel(x,i), p);
     129    10691271 :   z = ZX_renormalize(z, lx);
     130    10691317 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); return pol_0(varn(x)); }
     131    10367214 :   return z;
     132             : }
     133             : 
     134             : static GEN
     135       11953 : Fp_red_FpX(GEN x, GEN p, long v)
     136             : {
     137             :   GEN z;
     138       11953 :   if (!signe(x)) return pol_0(v);
     139        8373 :   z = cgetg(3, t_POL);
     140        8373 :   gel(z,2) = Fp_red(x,p);
     141        8373 :   z[1] = evalvarn(v);
     142        8373 :   return FpX_renormalize(z, 3);
     143             : }
     144             : 
     145             : static GEN
     146         104 : Fp_neg_FpX(GEN x, GEN p, long v)
     147             : {
     148             :   GEN z;
     149         104 :   if (!signe(x)) return pol_0(v);
     150           0 :   z = cgetg(3, t_POL);
     151           0 :   gel(z,2) = Fp_neg(x,p);
     152           0 :   z[1] = evalvarn(v);
     153           0 :   return FpX_renormalize(z, 3);
     154             : }
     155             : 
     156             : GEN
     157      313820 : FpX_Fp_add(GEN y,GEN x,GEN p)
     158             : {
     159      313820 :   long i, lz = lg(y);
     160             :   GEN z;
     161      313820 :   if (lz == 2) return Fp_red_FpX(x,p,varn(y));
     162      301867 :   z = cgetg(lz,t_POL); z[1] = y[1];
     163      301867 :   gel(z,2) = Fp_add(gel(y,2),x, p);
     164      301867 :   if (lz == 3) z = FpX_renormalize(z,lz);
     165             :   else
     166      943878 :     for(i=3;i<lz;i++) gel(z,i) = icopy(gel(y,i));
     167      301867 :   return z;
     168             : }
     169             : GEN
     170           0 : FpX_Fp_add_shallow(GEN y,GEN x,GEN p)
     171             : {
     172           0 :   long i, lz = lg(y);
     173             :   GEN z;
     174           0 :   if (lz == 2) return scalar_ZX_shallow(x,varn(y));
     175           0 :   z = cgetg(lz,t_POL); z[1] = y[1];
     176           0 :   gel(z,2) = Fp_add(gel(y,2),x, p);
     177           0 :   if (lz == 3) z = FpX_renormalize(z,lz);
     178             :   else
     179           0 :     for(i=3;i<lz;i++) gel(z,i) = gel(y,i);
     180           0 :   return z;
     181             : }
     182             : GEN
     183      572078 : FpX_Fp_sub(GEN y,GEN x,GEN p)
     184             : {
     185      572078 :   long i, lz = lg(y);
     186             :   GEN z;
     187      572078 :   if (lz == 2) return Fp_neg_FpX(x,p,varn(y));
     188      571974 :   z = cgetg(lz,t_POL); z[1] = y[1];
     189      571975 :   gel(z,2) = Fp_sub(gel(y,2),x, p);
     190      571976 :   if (lz == 3) z = FpX_renormalize(z,lz);
     191             :   else
     192     1314873 :     for(i=3;i<lz;i++) gel(z,i) = icopy(gel(y,i));
     193      571976 :   return z;
     194             : }
     195             : GEN
     196        1711 : FpX_Fp_sub_shallow(GEN y,GEN x,GEN p)
     197             : {
     198        1711 :   long i, lz = lg(y);
     199             :   GEN z;
     200        1711 :   if (lz == 2) return Fp_neg_FpX(x,p,varn(y));
     201        1711 :   z = cgetg(lz,t_POL); z[1] = y[1];
     202        1711 :   gel(z,2) = Fp_sub(gel(y,2),x, p);
     203        1711 :   if (lz == 3) z = FpX_renormalize(z,lz);
     204             :   else
     205        8798 :     for(i=3;i<lz;i++) gel(z,i) = gel(y,i);
     206        1711 :   return z;
     207             : }
     208             : 
     209             : GEN
     210      209941 : FpX_neg(GEN x,GEN p)
     211             : {
     212      209941 :   long i, lx = lg(x);
     213      209941 :   GEN y = cgetg(lx,t_POL);
     214      209941 :   y[1] = x[1];
     215     1599544 :   for(i=2; i<lx; i++) gel(y,i) = Fp_neg(gel(x,i), p);
     216      209926 :   return ZX_renormalize(y, lx);
     217             : }
     218             : 
     219             : static GEN
     220     7400986 : FpX_subspec(GEN x,GEN y,GEN p, long nx, long ny)
     221             : {
     222             :   long i, lz;
     223             :   GEN z;
     224     7400986 :   if (nx >= ny)
     225             :   {
     226     5470321 :     lz = nx+2;
     227     5470321 :     z = cgetg(lz,t_POL); z[1] = 0; z += 2;
     228    30210132 :     for (i=0; i<ny; i++) gel(z,i) = Fp_sub(gel(x,i),gel(y,i), p);
     229     6056518 :     for (   ; i<nx; i++) gel(z,i) = modii(gel(x,i), p);
     230             :   }
     231             :   else
     232             :   {
     233     1930665 :     lz = ny+2;
     234     1930665 :     z = cgetg(lz,t_POL); z[1] = 0; z += 2;
     235     5760936 :     for (i=0; i<nx; i++) gel(z,i) = Fp_sub(gel(x,i),gel(y,i), p);
     236     5262647 :     for (   ; i<ny; i++) gel(z,i) = Fp_neg(gel(y,i), p);
     237             :   }
     238     7400261 :   z = FpX_renormalize(z-2, lz);
     239     7400988 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lz)); return pol_0(0); }
     240     7251130 :   return z;
     241             : }
     242             : 
     243             : GEN
     244     7275485 : FpX_sub(GEN x,GEN y,GEN p)
     245             : {
     246     7275485 :   GEN z = FpX_subspec(x+2,y+2,p,lgpol(x),lgpol(y));
     247     7275495 :   setvarn(z, varn(x));
     248     7275495 :   return z;
     249             : }
     250             : 
     251             : GEN
     252       11885 : Fp_FpX_sub(GEN x, GEN y, GEN p)
     253             : {
     254       11885 :   long ly = lg(y), i;
     255             :   GEN z;
     256       11885 :   if (ly <= 3) {
     257         351 :     z = cgetg(3, t_POL);
     258         351 :     x = (ly == 3)? Fp_sub(x, gel(y,2), p): modii(x, p);
     259         351 :     if (!signe(x)) { set_avma((pari_sp)(z + 3)); return pol_0(varn(y)); }
     260         284 :     z[1] = evalsigne(1)|y[1]; gel(z,2) = x; return z;
     261             :   }
     262       11534 :   z = cgetg(ly,t_POL);
     263       11534 :   gel(z,2) = Fp_sub(x, gel(y,2), p);
     264       51231 :   for (i = 3; i < ly; i++) gel(z,i) = Fp_neg(gel(y,i), p);
     265       11534 :   z = ZX_renormalize(z, ly);
     266       11534 :   if (!lgpol(z)) { set_avma((pari_sp)(z + ly)); return pol_0(varn(x)); }
     267       11534 :   z[1] = y[1]; return z;
     268             : }
     269             : 
     270             : GEN
     271         868 : FpX_convol(GEN x, GEN y, GEN p)
     272             : {
     273         868 :   long lx = lg(x), ly = lg(y), i;
     274             :   GEN z;
     275         868 :   if (lx < ly) swapspec(x,y, lx,ly);
     276         868 :   z = cgetg(lx,t_POL); z[1] = x[1];
     277       43274 :   for (i=2; i<ly; i++) gel(z,i) = Fp_mul(gel(x,i),gel(y,i), p);
     278         868 :   for (   ; i<lx; i++) gel(z,i) = modii(gel(x,i), p);
     279         868 :   z = ZX_renormalize(z, lx);
     280         868 :   if (!lgpol(z)) { set_avma((pari_sp)(z + lx)); return pol_0(varn(x)); }
     281         868 :   return z;
     282             : }
     283             : 
     284             : GEN
     285    21681375 : FpX_mul(GEN x,GEN y,GEN p)
     286             : {
     287    21681375 :   if (lgefint(p) == 3)
     288             :   {
     289    13157263 :     ulong pp = to_Flx(&x, &y, p);
     290    13157071 :     return Flx_to_ZX(Flx_mul(x, y, pp));
     291             :   }
     292     8524112 :   return FpX_red(ZX_mul(x, y), p);
     293             : }
     294             : 
     295             : GEN
     296     2012620 : FpX_mulspec(GEN a, GEN b, GEN p, long na, long nb)
     297     2012620 : { return FpX_red(ZX_mulspec(a, b, na, nb), p); }
     298             : 
     299             : GEN
     300     4942798 : FpX_sqr(GEN x,GEN p)
     301             : {
     302     4942798 :   if (lgefint(p) == 3)
     303             :   {
     304      277106 :     ulong pp = to_Flx(&x, NULL, p);
     305      277103 :     return Flx_to_ZX(Flx_sqr(x, pp));
     306             :   }
     307     4665692 :   return FpX_red(ZX_sqr(x), p);
     308             : }
     309             : 
     310             : GEN
     311      801064 : FpX_mulu(GEN y, ulong x,GEN p)
     312             : {
     313             :   GEN z;
     314             :   long i, l;
     315      801064 :   x = umodui(x, p);
     316      801064 :   if (!x) return zeropol(varn(y));
     317      800924 :   z = cgetg_copy(y, &l); z[1] = y[1];
     318     3947512 :   for(i=2; i<l; i++) gel(z,i) = Fp_mulu(gel(y,i), x, p);
     319      800924 :   return z;
     320             : }
     321             : 
     322             : GEN
     323        4851 : FpX_divu(GEN y, ulong x, GEN p)
     324             : {
     325        4851 :   return FpX_Fp_div(y, utoi(umodui(x, p)), p);
     326             : }
     327             : 
     328             : GEN
     329     4629277 : FpX_Fp_mulspec(GEN y,GEN x,GEN p,long ly)
     330             : {
     331             :   GEN z;
     332             :   long i;
     333     4629277 :   if (!signe(x)) return pol_0(0);
     334     4580199 :   z = cgetg(ly+2,t_POL); z[1] = evalsigne(1);
     335    28920524 :   for(i=0; i<ly; i++) gel(z,i+2) = Fp_mul(gel(y,i), x, p);
     336     4577588 :   return ZX_renormalize(z, ly+2);
     337             : }
     338             : 
     339             : GEN
     340     4622420 : FpX_Fp_mul(GEN y,GEN x,GEN p)
     341             : {
     342     4622420 :   GEN z = FpX_Fp_mulspec(y+2,x,p,lgpol(y));
     343     4622516 :   setvarn(z, varn(y)); return z;
     344             : }
     345             : 
     346             : GEN
     347      291091 : FpX_Fp_div(GEN y, GEN x, GEN p)
     348             : {
     349      291091 :   return FpX_Fp_mul(y, Fp_inv(x, p), p);
     350             : }
     351             : 
     352             : GEN
     353      105151 : FpX_Fp_mul_to_monic(GEN y,GEN x,GEN p)
     354             : {
     355             :   GEN z;
     356             :   long i, l;
     357      105151 :   z = cgetg_copy(y, &l); z[1] = y[1];
     358      380145 :   for(i=2; i<l-1; i++) gel(z,i) = Fp_mul(gel(y,i), x, p);
     359      105151 :   gel(z,l-1) = gen_1; return z;
     360             : }
     361             : 
     362             : struct _FpXQ {
     363             :   GEN T, p, aut;
     364             : };
     365             : 
     366             : struct _FpX
     367             : {
     368             :   GEN p;
     369             :   long v;
     370             : };
     371             : 
     372             : static GEN
     373      245238 : _FpX_mul(void* E, GEN x, GEN y)
     374      245238 : { struct _FpX *D = (struct _FpX *)E; return FpX_mul(x, y, D->p); }
     375             : static GEN
     376       85880 : _FpX_sqr(void *E, GEN x)
     377       85880 : { struct _FpX *D = (struct _FpX *)E; return FpX_sqr(x, D->p); }
     378             : 
     379             : GEN
     380      306903 : FpX_powu(GEN x, ulong n, GEN p)
     381             : {
     382             :   struct _FpX D;
     383      306903 :   if (n==0) return pol_1(varn(x));
     384       50115 :   D.p = p;
     385       50115 :   return gen_powu(x, n, (void *)&D, _FpX_sqr, _FpX_mul);
     386             : }
     387             : 
     388             : GEN
     389      236922 : FpXV_prod(GEN V, GEN p)
     390             : {
     391             :   struct _FpX D;
     392      236922 :   D.p = p;
     393      236922 :   return gen_product(V, (void *)&D, &_FpX_mul);
     394             : }
     395             : 
     396             : static GEN
     397       26154 : _FpX_pow(void* E, GEN x, GEN y)
     398       26154 : { struct _FpX *D = (struct _FpX *)E; return FpX_powu(x, itou(y), D->p); }
     399             : static GEN
     400           0 : _FpX_one(void *E)
     401           0 : { struct _FpX *D = (struct _FpX *)E; return pol_1(D->v); }
     402             : 
     403             : GEN
     404       16387 : FpXV_factorback(GEN f, GEN e, GEN p, long v)
     405             : {
     406             :   struct _FpX D;
     407       16387 :   D.p = p; D.v = v;
     408       16387 :   return gen_factorback(f, e, (void *)&D, &_FpX_mul, &_FpX_pow, &_FpX_one);
     409             : }
     410             : 
     411             : GEN
     412       21887 : FpX_halve(GEN y, GEN p)
     413             : {
     414             :   GEN z;
     415             :   long i, l;
     416       21887 :   z = cgetg_copy(y, &l); z[1] = y[1];
     417       66244 :   for(i=2; i<l; i++) gel(z,i) = Fp_halve(gel(y,i), p);
     418       21887 :   return z;
     419             : }
     420             : 
     421             : static GEN
     422    49250584 : FpX_divrem_basecase(GEN x, GEN y, GEN p, GEN *pr)
     423             : {
     424             :   long vx, dx, dy, dy1, dz, i, j, sx, lr;
     425             :   pari_sp av0, av;
     426             :   GEN z,p1,rem,lead;
     427             : 
     428    49250584 :   if (!signe(y)) pari_err_INV("FpX_divrem",y);
     429    49250584 :   vx = varn(x);
     430    49250584 :   dy = degpol(y);
     431    49248354 :   dx = degpol(x);
     432    49249845 :   if (dx < dy)
     433             :   {
     434      123425 :     if (pr)
     435             :     {
     436      122979 :       av0 = avma; x = FpX_red(x, p);
     437      122979 :       if (pr == ONLY_DIVIDES) { set_avma(av0); return signe(x)? NULL: pol_0(vx); }
     438      122979 :       if (pr == ONLY_REM) return x;
     439      122979 :       *pr = x;
     440             :     }
     441      123425 :     return pol_0(vx);
     442             :   }
     443    49126420 :   lead = leading_coeff(y);
     444    49126995 :   if (!dy) /* y is constant */
     445             :   {
     446      295602 :     if (pr && pr != ONLY_DIVIDES)
     447             :     {
     448      291599 :       if (pr == ONLY_REM) return pol_0(vx);
     449      273748 :       *pr = pol_0(vx);
     450             :     }
     451      277751 :     av0 = avma;
     452      277751 :     if (equali1(lead)) return FpX_red(x, p);
     453      272940 :     else return gerepileupto(av0, FpX_Fp_div(x, lead, p));
     454             :   }
     455    48831393 :   av0 = avma; dz = dx-dy;
     456    48831393 :   if (lgefint(p) == 3)
     457             :   { /* assume ab != 0 mod p */
     458    27010974 :     ulong pp = to_Flx(&x, &y, p);
     459    27007218 :     z = Flx_divrem(x, y, pp, pr);
     460    26990298 :     set_avma(av0); /* HACK: assume pr last on stack, then z */
     461    26991143 :     if (!z) return NULL;
     462    26991003 :     z = leafcopy(z);
     463    27002545 :     if (pr && pr != ONLY_DIVIDES && pr != ONLY_REM)
     464             :     {
     465     5477874 :       *pr = leafcopy(*pr);
     466     5477900 :       *pr = Flx_to_ZX_inplace(*pr);
     467             :     }
     468    27002494 :     return Flx_to_ZX_inplace(z);
     469             :   }
     470    21820419 :   lead = equali1(lead)? NULL: gclone(Fp_inv(lead,p));
     471    21820123 :   set_avma(av0);
     472    21820033 :   z=cgetg(dz+3,t_POL); z[1] = x[1];
     473    21820230 :   x += 2; y += 2; z += 2;
     474    24611508 :   for (dy1=dy-1; dy1>=0 && !signe(gel(y, dy1)); dy1--);
     475             : 
     476    21820230 :   p1 = gel(x,dx); av = avma;
     477    21820230 :   gel(z,dz) = lead? gerepileuptoint(av, Fp_mul(p1,lead, p)): icopy(p1);
     478    62357570 :   for (i=dx-1; i>=dy; i--)
     479             :   {
     480    40536804 :     av=avma; p1=gel(x,i);
     481   428369733 :     for (j=i-dy1; j<=i && j<=dz; j++)
     482   387840152 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     483    40529581 :     if (lead) p1 = mulii(p1,lead);
     484    40529581 :     gel(z,i-dy) = gerepileuptoint(av,modii(p1, p));
     485             :   }
     486    21820766 :   if (!pr) { guncloneNULL(lead); return z-2; }
     487             : 
     488    21767597 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
     489    21767551 :   for (sx=0; ; i--)
     490             :   {
     491     1386408 :     p1 = gel(x,i);
     492    87963672 :     for (j=maxss(0,i-dy1); j<=i && j<=dz; j++)
     493    64810144 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     494    23153329 :     p1 = modii(p1,p); if (signe(p1)) { sx = 1; break; }
     495     1495599 :     if (!i) break;
     496     1386335 :     set_avma(av);
     497             :   }
     498    21766418 :   if (pr == ONLY_DIVIDES)
     499             :   {
     500           0 :     guncloneNULL(lead);
     501           0 :     if (sx) return gc_NULL(av0);
     502           0 :     return gc_const((pari_sp)rem, z-2);
     503             :   }
     504    21766418 :   lr=i+3; rem -= lr;
     505    21766418 :   rem[0] = evaltyp(t_POL) | evallg(lr);
     506    21766486 :   rem[1] = z[-1];
     507    21766486 :   p1 = gerepileuptoint((pari_sp)rem, p1);
     508    21767485 :   rem += 2; gel(rem,i) = p1;
     509    91171447 :   for (i--; i>=0; i--)
     510             :   {
     511    69404009 :     av=avma; p1 = gel(x,i);
     512   528570856 :     for (j=maxss(0,i-dy1); j<=i && j<=dz; j++)
     513   459178903 :       p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
     514    69391714 :     gel(rem,i) = gerepileuptoint(av, modii(p1,p));
     515             :   }
     516    21767438 :   rem -= 2;
     517    21767438 :   guncloneNULL(lead);
     518    21767357 :   if (!sx) (void)FpX_renormalize(rem, lr);
     519    21767348 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
     520      913387 :   *pr = rem; return z-2;
     521             : }
     522             : 
     523             : GEN
     524      161987 : FpX_div_by_X_x(GEN a, GEN x, GEN p, GEN *r)
     525             : {
     526      161987 :   long l = lg(a), i;
     527             :   GEN z;
     528      161987 :   if (l <= 3)
     529             :   {
     530           0 :     if (r) *r = l == 2? gen_0: icopy(gel(a,2));
     531           0 :     return pol_0(0);
     532             :   }
     533      161987 :   l--; z = cgetg(l, t_POL); z[1] = evalsigne(1) | evalvarn(0);
     534      161987 :   gel(z, l-1) = gel(a,l);
     535     2470423 :   for (i = l-2; i > 1; i--) /* z[i] = a[i+1] + x*z[i+1] */
     536     2308448 :     gel(z,i) = Fp_addmul(gel(a,i+1), x, gel(z,i+1), p);
     537      161975 :   if (r) *r = Fp_addmul(gel(a,2), x, gel(z,2), p);
     538      161975 :   return z;
     539             : }
     540             : 
     541             : static GEN
     542      134778 : _FpX_divrem(void * E, GEN x, GEN y, GEN *r)
     543             : {
     544      134778 :   struct _FpX *D = (struct _FpX*) E;
     545      134778 :   return FpX_divrem(x, y, D->p, r);
     546             : }
     547             : static GEN
     548       20062 : _FpX_add(void * E, GEN x, GEN y) {
     549       20062 :   struct _FpX *D = (struct _FpX*) E;
     550       20062 :   return FpX_add(x, y, D->p);
     551             : }
     552             : 
     553             : static struct bb_ring FpX_ring = { _FpX_add,_FpX_mul,_FpX_sqr };
     554             : 
     555             : GEN
     556       11403 : FpX_digits(GEN x, GEN T, GEN p)
     557             : {
     558             :   struct _FpX D;
     559       11403 :   long d = degpol(T), n = (lgpol(x)+d-1)/d;
     560       11403 :   D.p = p;
     561       11403 :   return gen_digits(x,T,n,(void *)&D, &FpX_ring, _FpX_divrem);
     562             : }
     563             : 
     564             : GEN
     565        4564 : FpXV_FpX_fromdigits(GEN x, GEN T, GEN p)
     566             : {
     567             :   struct _FpX D;
     568        4564 :   D.p = p;
     569        4564 :   return gen_fromdigits(x,T,(void *)&D, &FpX_ring);
     570             : }
     571             : 
     572             : long
     573      252923 : FpX_valrem(GEN x, GEN t, GEN p, GEN *py)
     574             : {
     575      252923 :   pari_sp av=avma;
     576             :   long k;
     577             :   GEN r, y;
     578             : 
     579      252923 :   for (k=0; ; k++)
     580             :   {
     581      646221 :     y = FpX_divrem(x, t, p, &r);
     582      646222 :     if (signe(r)) break;
     583      393298 :     x = y;
     584             :   }
     585      252924 :   *py = gerepilecopy(av,x);
     586      252929 :   return k;
     587             : }
     588             : 
     589             : static GEN
     590         618 : FpX_halfgcd_basecase(GEN a, GEN b, GEN p)
     591             : {
     592         618 :   pari_sp av=avma;
     593             :   GEN u,u1,v,v1;
     594         618 :   long vx = varn(a);
     595         618 :   long n = lgpol(a)>>1;
     596         618 :   u1 = v = pol_0(vx);
     597         618 :   u = v1 = pol_1(vx);
     598        5037 :   while (lgpol(b)>n)
     599             :   {
     600        4419 :     GEN r, q = FpX_divrem(a,b,p, &r);
     601        4419 :     a = b; b = r; swap(u,u1); swap(v,v1);
     602        4419 :     u1 = FpX_sub(u1, FpX_mul(u, q, p), p);
     603        4419 :     v1 = FpX_sub(v1, FpX_mul(v, q ,p), p);
     604        4419 :     if (gc_needed(av,2))
     605             :     {
     606           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpX_halfgcd (d = %ld)",degpol(b));
     607           0 :       gerepileall(av,6, &a,&b,&u1,&v1,&u,&v);
     608             :     }
     609             :   }
     610         618 :   return gerepilecopy(av, mkmat2(mkcol2(u,u1), mkcol2(v,v1)));
     611             : }
     612             : static GEN
     613         402 : FpX_addmulmul(GEN u, GEN v, GEN x, GEN y, GEN p)
     614             : {
     615         402 :   return FpX_add(FpX_mul(u, x, p),FpX_mul(v, y, p), p);
     616             : }
     617             : 
     618             : static GEN
     619         197 : FpXM_FpX_mul2(GEN M, GEN x, GEN y, GEN p)
     620             : {
     621         197 :   GEN res = cgetg(3, t_COL);
     622         197 :   gel(res, 1) = FpX_addmulmul(gcoeff(M,1,1), gcoeff(M,1,2), x, y, p);
     623         197 :   gel(res, 2) = FpX_addmulmul(gcoeff(M,2,1), gcoeff(M,2,2), x, y, p);
     624         197 :   return res;
     625             : }
     626             : 
     627             : static GEN
     628         169 : FpXM_mul2(GEN A, GEN B, GEN p)
     629             : {
     630         169 :   GEN A11=gcoeff(A,1,1),A12=gcoeff(A,1,2), B11=gcoeff(B,1,1),B12=gcoeff(B,1,2);
     631         169 :   GEN A21=gcoeff(A,2,1),A22=gcoeff(A,2,2), B21=gcoeff(B,2,1),B22=gcoeff(B,2,2);
     632         169 :   GEN M1 = FpX_mul(FpX_add(A11,A22, p), FpX_add(B11,B22, p), p);
     633         169 :   GEN M2 = FpX_mul(FpX_add(A21,A22, p), B11, p);
     634         169 :   GEN M3 = FpX_mul(A11, FpX_sub(B12,B22, p), p);
     635         169 :   GEN M4 = FpX_mul(A22, FpX_sub(B21,B11, p), p);
     636         169 :   GEN M5 = FpX_mul(FpX_add(A11,A12, p), B22, p);
     637         169 :   GEN M6 = FpX_mul(FpX_sub(A21,A11, p), FpX_add(B11,B12, p), p);
     638         169 :   GEN M7 = FpX_mul(FpX_sub(A12,A22, p), FpX_add(B21,B22, p), p);
     639         169 :   GEN T1 = FpX_add(M1,M4, p), T2 = FpX_sub(M7,M5, p);
     640         169 :   GEN T3 = FpX_sub(M1,M2, p), T4 = FpX_add(M3,M6, p);
     641         169 :   retmkmat2(mkcol2(FpX_add(T1,T2, p), FpX_add(M2,M4, p)),
     642             :             mkcol2(FpX_add(M3,M5, p), FpX_add(T3,T4, p)));
     643             : }
     644             : 
     645             : /* Return [0,1;1,-q]*M */
     646             : static GEN
     647         165 : FpX_FpXM_qmul(GEN q, GEN M, GEN p)
     648             : {
     649         165 :   GEN u, v, res = cgetg(3, t_MAT);
     650         165 :   u = FpX_sub(gcoeff(M,1,1), FpX_mul(gcoeff(M,2,1), q, p), p);
     651         165 :   gel(res,1) = mkcol2(gcoeff(M,2,1), u);
     652         165 :   v = FpX_sub(gcoeff(M,1,2), FpX_mul(gcoeff(M,2,2), q, p), p);
     653         165 :   gel(res,2) = mkcol2(gcoeff(M,2,2), v);
     654         165 :   return res;
     655             : }
     656             : 
     657             : static GEN
     658           4 : matid2_FpXM(long v)
     659             : {
     660           4 :   retmkmat2(mkcol2(pol_1(v),pol_0(v)),
     661             :             mkcol2(pol_0(v),pol_1(v)));
     662             : }
     663             : 
     664             : static GEN
     665      668591 : FpX_shift(GEN a, long n) { return RgX_shift_shallow(a, n); }
     666             : 
     667             : static GEN
     668         193 : FpX_halfgcd_split(GEN x, GEN y, GEN p)
     669             : {
     670         193 :   pari_sp av=avma;
     671             :   GEN R, S, V;
     672             :   GEN y1, r, q;
     673         193 :   long l = lgpol(x), n = l>>1, k;
     674         193 :   if (lgpol(y)<=n) return matid2_FpXM(varn(x));
     675         193 :   R = FpX_halfgcd(FpX_shift(x,-n), FpX_shift(y,-n), p);
     676         193 :   V = FpXM_FpX_mul2(R,x,y,p); y1 = gel(V,2);
     677         193 :   if (lgpol(y1)<=n) return gerepilecopy(av, R);
     678         165 :   q = FpX_divrem(gel(V,1), y1, p, &r);
     679         165 :   k = 2*n-degpol(y1);
     680         165 :   S = FpX_halfgcd(FpX_shift(y1,-k), FpX_shift(r,-k), p);
     681         165 :   return gerepileupto(av, FpXM_mul2(S,FpX_FpXM_qmul(q,R,p),p));
     682             : }
     683             : 
     684             : /* Return M in GL_2(Fp[X]) such that:
     685             : if [a',b']~=M*[a,b]~ then degpol(a')>= (lgpol(a)>>1) >degpol(b')
     686             : */
     687             : 
     688             : static GEN
     689         811 : FpX_halfgcd_i(GEN x, GEN y, GEN p)
     690             : {
     691         811 :   if (lg(x)<=FpX_HALFGCD_LIMIT) return FpX_halfgcd_basecase(x,y,p);
     692         193 :   return FpX_halfgcd_split(x,y,p);
     693             : }
     694             : 
     695             : GEN
     696         923 : FpX_halfgcd(GEN x, GEN y, GEN p)
     697             : {
     698         923 :   pari_sp av = avma;
     699             :   GEN M,q,r;
     700         923 :   if (lgefint(p)==3)
     701             :   {
     702         112 :     ulong pp = to_Flx(&x, &y, p);
     703         112 :     M = FlxM_to_ZXM(Flx_halfgcd(x, y, pp));
     704             :   }
     705             :   else
     706             :   {
     707         811 :     if (!signe(x))
     708             :     {
     709           0 :       long v = varn(x);
     710           0 :       retmkmat2(mkcol2(pol_0(v),pol_1(v)),
     711             :                 mkcol2(pol_1(v),pol_0(v)));
     712             :     }
     713         811 :     if (degpol(y)<degpol(x)) return FpX_halfgcd_i(x,y,p);
     714          11 :     q = FpX_divrem(y,x,p,&r);
     715          11 :     M = FpX_halfgcd_i(x,r,p);
     716          11 :     gcoeff(M,1,1) = FpX_sub(gcoeff(M,1,1), FpX_mul(q, gcoeff(M,1,2), p), p);
     717          11 :     gcoeff(M,2,1) = FpX_sub(gcoeff(M,2,1), FpX_mul(q, gcoeff(M,2,2), p), p);
     718             :   }
     719         123 :   return gerepilecopy(av, M);
     720             : }
     721             : 
     722             : static GEN
     723       39185 : FpX_gcd_basecase(GEN a, GEN b, GEN p)
     724             : {
     725       39185 :   pari_sp av = avma, av0=avma;
     726      424510 :   while (signe(b))
     727             :   {
     728             :     GEN c;
     729      385592 :     if (gc_needed(av0,2))
     730             :     {
     731           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpX_gcd (d = %ld)",degpol(b));
     732           0 :       gerepileall(av0,2, &a,&b);
     733             :     }
     734      385592 :     av = avma; c = FpX_rem(a,b,p); a=b; b=c;
     735             :   }
     736       38918 :   return gc_const(av, a);
     737             : }
     738             : 
     739             : GEN
     740      514241 : FpX_gcd(GEN x, GEN y, GEN p)
     741             : {
     742      514241 :   pari_sp av = avma;
     743      514241 :   if (lgefint(p)==3)
     744             :   {
     745             :     ulong pp;
     746      474557 :     (void)new_chunk((lg(x) + lg(y)) << 2); /* scratch space */
     747      474556 :     pp = to_Flx(&x, &y, p);
     748      474559 :     x = Flx_gcd(x, y, pp);
     749      474557 :     set_avma(av); return Flx_to_ZX(x);
     750             :   }
     751       39684 :   x = FpX_red(x, p);
     752       39684 :   y = FpX_red(y, p);
     753       39684 :   if (!signe(x)) return gerepileupto(av, y);
     754       39185 :   while (lg(y)>FpX_GCD_LIMIT)
     755             :   {
     756             :     GEN c;
     757           0 :     if (lgpol(y)<=(lgpol(x)>>1))
     758             :     {
     759           0 :       GEN r = FpX_rem(x, y, p);
     760           0 :       x = y; y = r;
     761             :     }
     762           0 :     c = FpXM_FpX_mul2(FpX_halfgcd(x,y, p), x, y, p);
     763           0 :     x = gel(c,1); y = gel(c,2);
     764           0 :     gerepileall(av,2,&x,&y);
     765             :   }
     766       39185 :   return gerepileupto(av, FpX_gcd_basecase(x,y,p));
     767             : }
     768             : 
     769             : /* Return NULL if gcd can be computed else return a factor of p */
     770             : GEN
     771         793 : FpX_gcd_check(GEN x, GEN y, GEN p)
     772             : {
     773         793 :   pari_sp av = avma;
     774             :   GEN a,b,c;
     775             : 
     776         793 :   a = FpX_red(x, p);
     777         793 :   b = FpX_red(y, p);
     778        8868 :   while (signe(b))
     779             :   {
     780             :     GEN g;
     781        8131 :     if (!invmod(leading_coeff(b), p, &g)) return gerepileuptoint(av,g);
     782        8075 :     b = FpX_Fp_mul_to_monic(b, g, p);
     783        8075 :     c = FpX_rem(a, b, p); a = b; b = c;
     784        8075 :     if (gc_needed(av,1))
     785             :     {
     786           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpX_gcd_check (d = %ld)",degpol(b));
     787           0 :       gerepileall(av,2,&a,&b);
     788             :     }
     789             :   }
     790         737 :   return gc_NULL(av);
     791             : }
     792             : 
     793             : static GEN
     794      273748 : FpX_extgcd_basecase(GEN a, GEN b, GEN p, GEN *ptu, GEN *ptv)
     795             : {
     796      273748 :   pari_sp av=avma;
     797             :   GEN u,v,d,d1,v1;
     798      273748 :   long vx = varn(a);
     799      273748 :   d = a; d1 = b;
     800      273748 :   v = pol_0(vx); v1 = pol_1(vx);
     801      940848 :   while (signe(d1))
     802             :   {
     803      667100 :     GEN r, q = FpX_divrem(d,d1,p, &r);
     804      667100 :     v = FpX_sub(v,FpX_mul(q,v1,p),p);
     805      667100 :     u=v; v=v1; v1=u;
     806      667100 :     u=r; d=d1; d1=u;
     807      667100 :     if (gc_needed(av,2))
     808             :     {
     809           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpX_extgcd (d = %ld)",degpol(d));
     810           0 :       gerepileall(av,5, &d,&d1,&u,&v,&v1);
     811             :     }
     812             :   }
     813      273748 :   if (ptu) *ptu = FpX_div(FpX_sub(d,FpX_mul(b,v,p),p),a,p);
     814      273748 :   *ptv = v; return d;
     815             : }
     816             : 
     817             : static GEN
     818           4 : FpX_extgcd_halfgcd(GEN x, GEN y, GEN p, GEN *ptu, GEN *ptv)
     819             : {
     820           4 :   pari_sp av=avma;
     821           4 :   GEN u,v,R = matid2_FpXM(varn(x));
     822           8 :   while (lg(y)>FpX_EXTGCD_LIMIT)
     823             :   {
     824             :     GEN M, c;
     825           4 :     if (lgpol(y)<=(lgpol(x)>>1))
     826             :     {
     827           0 :       GEN r, q = FpX_divrem(x, y, p, &r);
     828           0 :       x = y; y = r;
     829           0 :       R = FpX_FpXM_qmul(q, R, p);
     830             :     }
     831           4 :     M = FpX_halfgcd(x,y, p);
     832           4 :     c = FpXM_FpX_mul2(M, x,y, p);
     833           4 :     R = FpXM_mul2(M, R, p);
     834           4 :     x = gel(c,1); y = gel(c,2);
     835           4 :     gerepileall(av,3,&x,&y,&R);
     836             :   }
     837           4 :   y = FpX_extgcd_basecase(x,y,p,&u,&v);
     838           4 :   if (ptu) *ptu = FpX_addmulmul(u,v,gcoeff(R,1,1),gcoeff(R,2,1),p);
     839           4 :   *ptv = FpX_addmulmul(u,v,gcoeff(R,1,2),gcoeff(R,2,2),p);
     840           4 :   return y;
     841             : }
     842             : 
     843             : /* x and y in Z[X], return lift(gcd(x mod p, y mod p)). Set u and v st
     844             :  * ux + vy = gcd (mod p) */
     845             : GEN
     846     1103119 : FpX_extgcd(GEN x, GEN y, GEN p, GEN *ptu, GEN *ptv)
     847             : {
     848     1103119 :   pari_sp av = avma;
     849             :   GEN d;
     850     1103119 :   if (lgefint(p)==3)
     851             :   {
     852      829372 :     ulong pp = to_Flx(&x, &y, p);
     853      829344 :     d = Flx_extgcd(x,y, pp, ptu,ptv);
     854      829382 :     d = Flx_to_ZX(d);
     855      829332 :     if (ptu) *ptu=Flx_to_ZX(*ptu);
     856      829330 :     *ptv=Flx_to_ZX(*ptv);
     857             :   }
     858             :   else
     859             :   {
     860      273747 :     x = FpX_red(x, p);
     861      273748 :     y = FpX_red(y, p);
     862      273748 :     if (lg(y)>FpX_EXTGCD_LIMIT)
     863           4 :       d = FpX_extgcd_halfgcd(x, y, p, ptu, ptv);
     864             :     else
     865      273744 :       d = FpX_extgcd_basecase(x, y, p, ptu, ptv);
     866             :   }
     867     1103092 :   return gc_all(av, ptu?3:2, &d, ptv, ptu);
     868             : }
     869             : 
     870             : GEN
     871      176417 : FpX_rescale(GEN P, GEN h, GEN p)
     872             : {
     873      176417 :   long i, l = lg(P);
     874      176417 :   GEN Q = cgetg(l,t_POL), hi = h;
     875      176426 :   gel(Q,l-1) = gel(P,l-1);
     876      361316 :   for (i=l-2; i>=2; i--)
     877             :   {
     878      361313 :     gel(Q,i) = Fp_mul(gel(P,i), hi, p);
     879      361312 :     if (i == 2) break;
     880      184887 :     hi = Fp_mul(hi,h, p);
     881             :   }
     882      176428 :   Q[1] = P[1]; return Q;
     883             : }
     884             : 
     885             : GEN
     886     1192270 : FpX_deriv(GEN x, GEN p) { return FpX_red(ZX_deriv(x), p); }
     887             : 
     888             : /* Compute intformal(x^n*S)/x^(n+1) */
     889             : static GEN
     890       21677 : FpX_integXn(GEN x, long n, GEN p)
     891             : {
     892       21677 :   long i, lx = lg(x);
     893             :   GEN y;
     894       21677 :   if (lx == 2) return ZX_copy(x);
     895       20410 :   y = cgetg(lx, t_POL); y[1] = x[1];
     896       77137 :   for (i=2; i<lx; i++)
     897             :   {
     898       56727 :     GEN xi = gel(x,i);
     899       56727 :     if (!signe(xi))
     900           0 :       gel(y,i) = gen_0;
     901             :     else
     902             :     {
     903       56727 :       ulong j = n+i-1;
     904       56727 :       ulong d = ugcd(j, umodiu(xi, j));
     905       56727 :       if (d==1)
     906       36282 :         gel(y,i) = Fp_divu(xi, j, p);
     907             :       else
     908       20445 :         gel(y,i) = Fp_divu(diviuexact(xi, d), j/d, p);
     909             :     }
     910             :   }
     911       20410 :   return ZX_renormalize(y, lx);;
     912             : }
     913             : 
     914             : GEN
     915           0 : FpX_integ(GEN x, GEN p)
     916             : {
     917           0 :   long i, lx = lg(x);
     918             :   GEN y;
     919           0 :   if (lx == 2) return ZX_copy(x);
     920           0 :   y = cgetg(lx+1, t_POL); y[1] = x[1];
     921           0 :   gel(y,2) = gen_0;
     922           0 :   for (i=3; i<=lx; i++)
     923           0 :     gel(y,i) = signe(gel(x,i-1))? Fp_divu(gel(x,i-1), i-2, p): gen_0;
     924           0 :   return ZX_renormalize(y, lx+1);;
     925             : }
     926             : 
     927             : INLINE GEN
     928      522454 : FpXn_recip(GEN P, long n)
     929      522454 : { return RgXn_recip_shallow(P, n); }
     930             : 
     931             : GEN
     932      522418 : FpX_Newton(GEN P, long n, GEN p)
     933             : {
     934      522418 :   pari_sp av = avma;
     935      522418 :   GEN dP = FpX_deriv(P, p);
     936      522423 :   GEN Q = FpXn_recip(FpX_div(FpX_shift(dP,n), P, p), n);
     937      522426 :   return gerepilecopy(av, Q);
     938             : }
     939             : 
     940             : GEN
     941         464 : FpX_fromNewton(GEN P, GEN p)
     942             : {
     943         464 :   pari_sp av = avma;
     944         464 :   if (lgefint(p)==3)
     945             :   {
     946         432 :     ulong pp = p[2];
     947         432 :     GEN Q = Flx_fromNewton(ZX_to_Flx(P, pp), pp);
     948         432 :     return gerepileupto(av, Flx_to_ZX(Q));
     949             :   } else
     950             :   {
     951          32 :     long n = itos(modii(constant_coeff(P), p))+1;
     952          32 :     GEN z = FpX_neg(FpX_shift(P,-1),p);
     953          32 :     GEN Q = FpXn_recip(FpXn_expint(z, n, p), n);
     954          32 :     return gerepilecopy(av, Q);
     955             :   }
     956             : }
     957             : 
     958             : GEN
     959          60 : FpX_invLaplace(GEN x, GEN p)
     960             : {
     961          60 :   pari_sp av = avma;
     962          60 :   long i, d = degpol(x);
     963             :   GEN t, y;
     964          60 :   if (d <= 1) return gcopy(x);
     965          60 :   t = Fp_inv(factorial_Fp(d, p), p);
     966          60 :   y = cgetg(d+3, t_POL);
     967          60 :   y[1] = x[1];
     968         656 :   for (i=d; i>=2; i--)
     969             :   {
     970         596 :     gel(y,i+2) = Fp_mul(gel(x,i+2), t, p);
     971         596 :     t = Fp_mulu(t, i, p);
     972             :   }
     973          60 :   gel(y,3) = gel(x,3);
     974          60 :   gel(y,2) = gel(x,2);
     975          60 :   return gerepilecopy(av, y);
     976             : }
     977             : 
     978             : GEN
     979         464 : FpX_Laplace(GEN x, GEN p)
     980             : {
     981         464 :   pari_sp av = avma;
     982         464 :   long i, d = degpol(x);
     983         464 :   GEN t = gen_1;
     984             :   GEN y;
     985         464 :   if (d <= 1) return gcopy(x);
     986         464 :   y = cgetg(d+3, t_POL);
     987         464 :   y[1] = x[1];
     988         464 :   gel(y,2) = gel(x,2);
     989         464 :   gel(y,3) = gel(x,3);
     990       21097 :   for (i=2; i<=d; i++)
     991             :   {
     992       20633 :     t = Fp_mulu(t, i, p);
     993       20633 :     gel(y,i+2) = Fp_mul(gel(x,i+2), t, p);
     994             :   }
     995         464 :   return gerepilecopy(av, y);
     996             : }
     997             : 
     998             : int
     999       39207 : FpX_is_squarefree(GEN f, GEN p)
    1000             : {
    1001       39207 :   pari_sp av = avma;
    1002       39207 :   GEN z = FpX_gcd(f,FpX_deriv(f,p),p);
    1003       39206 :   set_avma(av);
    1004       39206 :   return degpol(z)==0;
    1005             : }
    1006             : 
    1007             : GEN
    1008      259281 : random_FpX(long d1, long v, GEN p)
    1009             : {
    1010      259281 :   long i, d = d1+2;
    1011      259281 :   GEN y = cgetg(d,t_POL); y[1] = evalsigne(1) | evalvarn(v);
    1012      869311 :   for (i=2; i<d; i++) gel(y,i) = randomi(p);
    1013      259280 :   return FpX_renormalize(y,d);
    1014             : }
    1015             : 
    1016             : GEN
    1017        8408 : FpX_dotproduct(GEN x, GEN y, GEN p)
    1018             : {
    1019        8408 :   long i, l = minss(lg(x), lg(y));
    1020             :   pari_sp av;
    1021             :   GEN c;
    1022        8408 :   if (l == 2) return gen_0;
    1023        8331 :   av = avma; c = mulii(gel(x,2),gel(y,2));
    1024      635938 :   for (i=3; i<l; i++) c = addii(c, mulii(gel(x,i),gel(y,i)));
    1025        8331 :   return gerepileuptoint(av, modii(c,p));
    1026             : }
    1027             : 
    1028             : /* Evaluation in Fp
    1029             :  * x a ZX and y an Fp, return x(y) mod p
    1030             :  *
    1031             :  * If p is very large (several longs) and x has small coefficients(<<p),
    1032             :  * then Brent & Kung algorithm is faster. */
    1033             : GEN
    1034      819915 : FpX_eval(GEN x,GEN y,GEN p)
    1035             : {
    1036             :   pari_sp av;
    1037             :   GEN p1,r,res;
    1038      819915 :   long j, i=lg(x)-1;
    1039      819915 :   if (i<=2 || !signe(y))
    1040      171088 :     return (i==1)? gen_0: modii(gel(x,2),p);
    1041      648827 :   res=cgeti(lgefint(p));
    1042      648828 :   av=avma; p1=gel(x,i);
    1043             :   /* specific attention to sparse polynomials (see poleval)*/
    1044             :   /*You've guessed it! It's a copy-paste(tm)*/
    1045     2796397 :   for (i--; i>=2; i=j-1)
    1046             :   {
    1047     3178215 :     for (j=i; !signe(gel(x,j)); j--)
    1048     1030658 :       if (j==2)
    1049             :       {
    1050      150155 :         if (i!=j) y = Fp_powu(y,i-j+1,p);
    1051      150155 :         p1=mulii(p1,y);
    1052      150138 :         goto fppoleval;/*sorry break(2) no implemented*/
    1053             :       }
    1054     2147557 :     r = (i==j)? y: Fp_powu(y,i-j+1,p);
    1055     2147556 :     p1 = Fp_addmul(gel(x,j), p1, r, p);
    1056     2147570 :     if ((i & 7) == 0) { affii(p1, res); p1 = res; set_avma(av); }
    1057             :   }
    1058      498685 :  fppoleval:
    1059      648823 :   modiiz(p1,p,res); return gc_const(av, res);
    1060             : }
    1061             : 
    1062             : /* Tz=Tx*Ty where Tx and Ty coprime
    1063             :  * return lift(chinese(Mod(x*Mod(1,p),Tx*Mod(1,p)),Mod(y*Mod(1,p),Ty*Mod(1,p))))
    1064             :  * if Tz is NULL it is computed
    1065             :  * As we do not return it, and the caller will frequently need it,
    1066             :  * it must compute it and pass it.
    1067             :  */
    1068             : GEN
    1069           0 : FpX_chinese_coprime(GEN x,GEN y,GEN Tx,GEN Ty,GEN Tz,GEN p)
    1070             : {
    1071           0 :   pari_sp av = avma;
    1072             :   GEN ax,p1;
    1073           0 :   ax = FpX_mul(FpXQ_inv(Tx,Ty,p), Tx,p);
    1074           0 :   p1 = FpX_mul(ax, FpX_sub(y,x,p),p);
    1075           0 :   p1 = FpX_add(x,p1,p);
    1076           0 :   if (!Tz) Tz=FpX_mul(Tx,Ty,p);
    1077           0 :   p1 = FpX_rem(p1,Tz,p);
    1078           0 :   return gerepileupto(av,p1);
    1079             : }
    1080             : 
    1081             : /* Res(A,B) = Res(B,R) * lc(B)^(a-r) * (-1)^(ab), with R=A%B, a=deg(A) ...*/
    1082             : GEN
    1083      413222 : FpX_resultant(GEN a, GEN b, GEN p)
    1084             : {
    1085             :   long da,db,dc;
    1086             :   pari_sp av;
    1087      413222 :   GEN c,lb, res = gen_1;
    1088             : 
    1089      413222 :   if (!signe(a) || !signe(b)) return gen_0;
    1090      413222 :   if (lgefint(p) == 3)
    1091             :   {
    1092      409417 :     pari_sp av = avma;
    1093      409417 :     ulong pp = to_Flx(&a, &b, p);
    1094      409416 :     long r = Flx_resultant(a, b, pp);
    1095      409417 :     set_avma(av);
    1096      409417 :     return utoi(r);
    1097             :   }
    1098             : 
    1099        3805 :   da = degpol(a);
    1100        3805 :   db = degpol(b);
    1101        3805 :   if (db > da)
    1102             :   {
    1103           0 :     swapspec(a,b, da,db);
    1104           0 :     if (both_odd(da,db)) res = subii(p, res);
    1105             :   }
    1106        3805 :   if (!da) return gen_1; /* = res * a[2] ^ db, since 0 <= db <= da = 0 */
    1107        3805 :   av = avma;
    1108        8929 :   while (db)
    1109             :   {
    1110        5124 :     lb = gel(b,db+2);
    1111        5124 :     c = FpX_rem(a,b, p);
    1112        5124 :     a = b; b = c; dc = degpol(c);
    1113        5124 :     if (dc < 0) return gc_const(av, gen_0);
    1114             : 
    1115        5124 :     if (both_odd(da,db)) res = subii(p, res);
    1116        5124 :     if (!equali1(lb)) res = Fp_mul(res, Fp_powu(lb, da - dc, p), p);
    1117        5124 :     if (gc_needed(av,2))
    1118             :     {
    1119           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpX_resultant (da = %ld)",da);
    1120           0 :       gerepileall(av,3, &a,&b,&res);
    1121             :     }
    1122        5124 :     da = db; /* = degpol(a) */
    1123        5124 :     db = dc; /* = degpol(b) */
    1124             :   }
    1125        3805 :   res = Fp_mul(res, Fp_powu(gel(b,2), da, p), p);
    1126        3805 :   return gerepileuptoint(av, res);
    1127             : }
    1128             : 
    1129             : /* disc P = (-1)^(n(n-1)/2) lc(P)^(n - deg P' - 2) Res(P,P'), n = deg P */
    1130             : GEN
    1131          42 : FpX_disc(GEN P, GEN p)
    1132             : {
    1133          42 :   pari_sp av = avma;
    1134          42 :   GEN L, dP = FpX_deriv(P,p), D = FpX_resultant(P, dP, p);
    1135             :   long dd;
    1136          42 :   if (!signe(D)) return gen_0;
    1137          35 :   dd = degpol(P) - 2 - degpol(dP); /* >= -1; > -1 iff p | deg(P) */
    1138          35 :   L = leading_coeff(P);
    1139          35 :   if (dd && !equali1(L))
    1140           7 :     D = (dd == -1)? Fp_div(D,L,p): Fp_mul(D, Fp_powu(L, dd, p), p);
    1141          35 :   if (degpol(P) & 2) D = Fp_neg(D ,p);
    1142          35 :   return gerepileuptoint(av, D);
    1143             : }
    1144             : 
    1145             : GEN
    1146       18030 : FpV_roots_to_pol(GEN V, GEN p, long v)
    1147             : {
    1148       18030 :   pari_sp ltop=avma;
    1149             :   long i;
    1150       18030 :   GEN g=cgetg(lg(V),t_VEC);
    1151      103748 :   for(i=1;i<lg(V);i++)
    1152       85719 :     gel(g,i) = deg1pol_shallow(gen_1,modii(negi(gel(V,i)),p),v);
    1153       18029 :   return gerepileupto(ltop,FpXV_prod(g,p));
    1154             : }
    1155             : 
    1156             : /* invert all elements of x mod p using Montgomery's multi-inverse trick.
    1157             :  * Not stack-clean. */
    1158             : GEN
    1159       34129 : FpV_inv(GEN x, GEN p)
    1160             : {
    1161       34129 :   long i, lx = lg(x);
    1162       34129 :   GEN u, y = cgetg(lx, t_VEC);
    1163             : 
    1164       34129 :   gel(y,1) = gel(x,1);
    1165      471065 :   for (i=2; i<lx; i++) gel(y,i) = Fp_mul(gel(y,i-1), gel(x,i), p);
    1166             : 
    1167       34130 :   u = Fp_inv(gel(y,--i), p);
    1168      471069 :   for ( ; i > 1; i--)
    1169             :   {
    1170      436939 :     gel(y,i) = Fp_mul(u, gel(y,i-1), p);
    1171      436938 :     u = Fp_mul(u, gel(x,i), p); /* u = 1 / (x[1] ... x[i-1]) */
    1172             :   }
    1173       34130 :   gel(y,1) = u; return y;
    1174             : }
    1175             : GEN
    1176           0 : FqV_inv(GEN x, GEN T, GEN p)
    1177             : {
    1178           0 :   long i, lx = lg(x);
    1179           0 :   GEN u, y = cgetg(lx, t_VEC);
    1180             : 
    1181           0 :   gel(y,1) = gel(x,1);
    1182           0 :   for (i=2; i<lx; i++) gel(y,i) = Fq_mul(gel(y,i-1), gel(x,i), T,p);
    1183             : 
    1184           0 :   u = Fq_inv(gel(y,--i), T,p);
    1185           0 :   for ( ; i > 1; i--)
    1186             :   {
    1187           0 :     gel(y,i) = Fq_mul(u, gel(y,i-1), T,p);
    1188           0 :     u = Fq_mul(u, gel(x,i), T,p); /* u = 1 / (x[1] ... x[i-1]) */
    1189             :   }
    1190           0 :   gel(y,1) = u; return y;
    1191             : }
    1192             : 
    1193             : /***********************************************************************/
    1194             : /**                                                                   **/
    1195             : /**                      Barrett reduction                            **/
    1196             : /**                                                                   **/
    1197             : /***********************************************************************/
    1198             : 
    1199             : static GEN
    1200        3243 : FpX_invBarrett_basecase(GEN T, GEN p)
    1201             : {
    1202        3243 :   long i, l=lg(T)-1, lr = l-1, k;
    1203        3243 :   GEN r=cgetg(lr, t_POL); r[1]=T[1];
    1204        3243 :   gel(r,2) = gen_1;
    1205      162929 :   for (i=3; i<lr; i++)
    1206             :   {
    1207      159686 :     pari_sp av = avma;
    1208      159686 :     GEN u = gel(T,l-i+2);
    1209     4334533 :     for (k=3; k<i; k++)
    1210     4174847 :       u = addii(u, mulii(gel(T,l-i+k), gel(r,k)));
    1211      159686 :     gel(r,i) = gerepileupto(av, modii(negi(u), p));
    1212             :   }
    1213        3243 :   return FpX_renormalize(r,lr);
    1214             : }
    1215             : 
    1216             : /* Return new lgpol */
    1217             : static long
    1218      276892 : ZX_lgrenormalizespec(GEN x, long lx)
    1219             : {
    1220             :   long i;
    1221      326798 :   for (i = lx-1; i>=0; i--)
    1222      326798 :     if (signe(gel(x,i))) break;
    1223      276892 :   return i+1;
    1224             : }
    1225             : 
    1226             : INLINE GEN
    1227      254803 : FpX_recipspec(GEN x, long l, long n)
    1228             : {
    1229      254803 :   return RgX_recipspec_shallow(x, l, n);
    1230             : }
    1231             : 
    1232             : static GEN
    1233        1228 : FpX_invBarrett_Newton(GEN T, GEN p)
    1234             : {
    1235        1228 :   pari_sp av = avma;
    1236        1228 :   long nold, lx, lz, lq, l = degpol(T), i, lQ;
    1237        1228 :   GEN q, y, z, x = cgetg(l+2, t_POL) + 2;
    1238        1228 :   ulong mask = quadratic_prec_mask(l-2); /* assume l > 2 */
    1239      164044 :   for (i=0;i<l;i++) gel(x,i) = gen_0;
    1240        1228 :   q = FpX_recipspec(T+2,l+1,l+1); lQ = lgpol(q); q+=2;
    1241             :   /* We work on _spec_ FpX's, all the l[xzq] below are lgpol's */
    1242             : 
    1243             :   /* initialize */
    1244        1228 :   gel(x,0) = Fp_inv(gel(q,0), p);
    1245        1228 :   if (lQ>1) gel(q,1) = Fp_red(gel(q,1), p);
    1246        1228 :   if (lQ>1 && signe(gel(q,1)))
    1247        1177 :   {
    1248        1177 :     GEN u = gel(q, 1);
    1249        1177 :     if (!equali1(gel(x,0))) u = Fp_mul(u, Fp_sqr(gel(x,0), p), p);
    1250        1177 :     gel(x,1) = Fp_neg(u, p); lx = 2;
    1251             :   }
    1252             :   else
    1253          51 :     lx = 1;
    1254        1228 :   nold = 1;
    1255        9878 :   for (; mask > 1; )
    1256             :   { /* set x -= x(x*q - 1) + O(t^(nnew + 1)), knowing x*q = 1 + O(t^(nold+1)) */
    1257        8779 :     long i, lnew, nnew = nold << 1;
    1258             : 
    1259        8779 :     if (mask & 1) nnew--;
    1260        8779 :     mask >>= 1;
    1261             : 
    1262        8779 :     lnew = nnew + 1;
    1263        8779 :     lq = ZX_lgrenormalizespec(q, minss(lQ,lnew));
    1264        8782 :     z = FpX_mulspec(x, q, p, lx, lq); /* FIXME: high product */
    1265        8781 :     lz = lgpol(z); if (lz > lnew) lz = lnew;
    1266        8781 :     z += 2;
    1267             :     /* subtract 1 [=>first nold words are 0]: renormalize so that z(0) != 0 */
    1268       19437 :     for (i = nold; i < lz; i++) if (signe(gel(z,i))) break;
    1269        8781 :     nold = nnew;
    1270        8781 :     if (i >= lz) continue; /* z-1 = 0(t^(nnew + 1)) */
    1271             : 
    1272             :     /* z + i represents (x*q - 1) / t^i */
    1273        8590 :     lz = ZX_lgrenormalizespec (z+i, lz-i);
    1274        8591 :     z = FpX_mulspec(x, z+i, p, lx, lz); /* FIXME: low product */
    1275        8590 :     lz = lgpol(z); z += 2;
    1276        8589 :     if (lz > lnew-i) lz = ZX_lgrenormalizespec(z, lnew-i);
    1277             : 
    1278        8589 :     lx = lz+ i;
    1279        8589 :     y  = x + i; /* x -= z * t^i, in place */
    1280      163944 :     for (i = 0; i < lz; i++) gel(y,i) = Fp_neg(gel(z,i), p);
    1281             :   }
    1282        1099 :   x -= 2; setlg(x, lx + 2); x[1] = T[1];
    1283        1228 :   return gerepilecopy(av, x);
    1284             : }
    1285             : 
    1286             : /* 1/polrecip(T)+O(x^(deg(T)-1)) */
    1287             : GEN
    1288        4524 : FpX_invBarrett(GEN T, GEN p)
    1289             : {
    1290        4524 :   pari_sp ltop = avma;
    1291        4524 :   long l = lg(T);
    1292             :   GEN r;
    1293        4524 :   if (l<5) return pol_0(varn(T));
    1294        4471 :   if (l<=FpX_INVBARRETT_LIMIT)
    1295             :   {
    1296        3243 :     GEN c = gel(T,l-1), ci=gen_1;
    1297        3243 :     if (!equali1(c))
    1298             :     {
    1299           4 :       ci = Fp_inv(c, p);
    1300           4 :       T = FpX_Fp_mul(T, ci, p);
    1301           4 :       r = FpX_invBarrett_basecase(T, p);
    1302           4 :       r = FpX_Fp_mul(r, ci, p);
    1303             :     } else
    1304        3239 :       r = FpX_invBarrett_basecase(T, p);
    1305             :   }
    1306             :   else
    1307        1228 :     r = FpX_invBarrett_Newton(T, p);
    1308        4471 :   return gerepileupto(ltop, r);
    1309             : }
    1310             : 
    1311             : GEN
    1312      916854 : FpX_get_red(GEN T, GEN p)
    1313             : {
    1314      916854 :   if (typ(T)==t_POL && lg(T)>FpX_BARRETT_LIMIT)
    1315        4029 :     retmkvec2(FpX_invBarrett(T,p),T);
    1316      912825 :   return T;
    1317             : }
    1318             : 
    1319             : /* Compute x mod T where 2 <= degpol(T) <= l+1 <= 2*(degpol(T)-1)
    1320             :  * and mg is the Barrett inverse of T. */
    1321             : static GEN
    1322      125494 : FpX_divrem_Barrettspec(GEN x, long l, GEN mg, GEN T, GEN p, GEN *pr)
    1323             : {
    1324             :   GEN q, r;
    1325      125494 :   long lt = degpol(T); /*We discard the leading term*/
    1326             :   long ld, lm, lT, lmg;
    1327      125494 :   ld = l-lt;
    1328      125494 :   lm = minss(ld, lgpol(mg));
    1329      125494 :   lT  = ZX_lgrenormalizespec(T+2,lt);
    1330      125494 :   lmg = ZX_lgrenormalizespec(mg+2,lm);
    1331      125494 :   q = FpX_recipspec(x+lt,ld,ld);              /* q = rec(x)     lq<=ld*/
    1332      125495 :   q = FpX_mulspec(q+2,mg+2,p,lgpol(q),lmg);    /* q = rec(x) * mg lq<=ld+lm*/
    1333      125494 :   q = FpX_recipspec(q+2,minss(ld,lgpol(q)),ld);/* q = rec (rec(x) * mg) lq<=ld*/
    1334      125495 :   if (!pr) return q;
    1335      125491 :   r = FpX_mulspec(q+2,T+2,p,lgpol(q),lT);      /* r = q*pol        lr<=ld+lt*/
    1336      125489 :   r = FpX_subspec(x,r+2,p,lt,minss(lt,lgpol(r)));/* r = x - r   lr<=lt */
    1337      125491 :   if (pr == ONLY_REM) return r;
    1338         747 :   *pr = r; return q;
    1339             : }
    1340             : 
    1341             : static GEN
    1342      124985 : FpX_divrem_Barrett(GEN x, GEN mg, GEN T, GEN p, GEN *pr)
    1343             : {
    1344      124985 :   GEN q = NULL, r = FpX_red(x, p);
    1345      124985 :   long l = lgpol(r), lt = degpol(T), lm = 2*lt-1, v = varn(T);
    1346             :   long i;
    1347      124985 :   if (l <= lt)
    1348             :   {
    1349           0 :     if (pr == ONLY_REM) return r;
    1350           0 :     if (pr == ONLY_DIVIDES) return signe(r)? NULL: pol_0(v);
    1351           0 :     if (pr) *pr = r;
    1352           0 :     return pol_0(v);
    1353             :   }
    1354      124985 :   if (lt <= 1)
    1355          53 :     return FpX_divrem_basecase(r,T,p,pr);
    1356      124932 :   if (pr != ONLY_REM && l>lm)
    1357             :   {
    1358         155 :     q = cgetg(l-lt+2, t_POL); q[1] = T[1];
    1359       27211 :     for (i=0;i<l-lt;i++) gel(q+2,i) = gen_0;
    1360             :   }
    1361      125495 :   while (l>lm)
    1362             :   {
    1363         563 :     GEN zr, zq = FpX_divrem_Barrettspec(r+2+l-lm,lm,mg,T,p,&zr);
    1364         563 :     long lz = lgpol(zr);
    1365         563 :     if (pr != ONLY_REM)
    1366             :     {
    1367         389 :       long lq = lgpol(zq);
    1368       24195 :       for(i=0; i<lq; i++) gel(q+2+l-lm,i) = gel(zq,2+i);
    1369             :     }
    1370       35174 :     for(i=0; i<lz; i++) gel(r+2+l-lm,i) = gel(zr,2+i);
    1371         563 :     l = l-lm+lz;
    1372             :   }
    1373      124932 :   if (pr == ONLY_REM)
    1374             :   {
    1375      124743 :     if (l > lt)
    1376      124743 :       r = FpX_divrem_Barrettspec(r+2, l, mg, T, p, ONLY_REM);
    1377             :     else
    1378           0 :       r = FpX_renormalize(r, l+2);
    1379      124744 :     setvarn(r, v); return r;
    1380             :   }
    1381         189 :   if (l > lt)
    1382             :   {
    1383         188 :     GEN zq = FpX_divrem_Barrettspec(r+2,l,mg,T,p, pr? &r: NULL);
    1384         188 :     if (!q) q = zq;
    1385             :     else
    1386             :     {
    1387         154 :       long lq = lgpol(zq);
    1388        3359 :       for(i=0; i<lq; i++) gel(q+2,i) = gel(zq,2+i);
    1389             :     }
    1390             :   }
    1391           1 :   else if (pr)
    1392           1 :     r = FpX_renormalize(r, l+2);
    1393         189 :   setvarn(q, v); q = FpX_renormalize(q, lg(q));
    1394         189 :   if (pr == ONLY_DIVIDES) return signe(r)? NULL: q;
    1395         189 :   if (pr) { setvarn(r, v); *pr = r; }
    1396         189 :   return q;
    1397             : }
    1398             : 
    1399             : GEN
    1400    11430860 : FpX_divrem(GEN x, GEN T, GEN p, GEN *pr)
    1401             : {
    1402             :   GEN B, y;
    1403             :   long dy, dx, d;
    1404    11430860 :   if (pr==ONLY_REM) return FpX_rem(x, T, p);
    1405    11430860 :   y = get_FpX_red(T, &B);
    1406    11430942 :   dy = degpol(y); dx = degpol(x); d = dx-dy;
    1407    11430901 :   if (!B && d+3 < FpX_DIVREM_BARRETT_LIMIT)
    1408    11429382 :     return FpX_divrem_basecase(x,y,p,pr);
    1409        1519 :   else if (lgefint(p)==3)
    1410             :   {
    1411        1300 :     pari_sp av = avma;
    1412        1300 :     ulong pp = to_Flxq(&x, &T, p);
    1413        1300 :     GEN z = Flx_divrem(x, T, pp, pr);
    1414        1300 :     if (!z) return gc_NULL(av);
    1415        1300 :     if (!pr || pr == ONLY_DIVIDES)
    1416          41 :       return Flx_to_ZX_inplace(gerepileuptoleaf(av, z));
    1417        1259 :     z = Flx_to_ZX(z);
    1418        1259 :     *pr = Flx_to_ZX(*pr);
    1419        1259 :     return gc_all(av, 2, &z, pr);
    1420             :   } else
    1421             :   {
    1422         219 :     pari_sp av = avma;
    1423         219 :     GEN mg = B? B: FpX_invBarrett(y, p);
    1424         219 :     GEN z = FpX_divrem_Barrett(x,mg,y,p,pr);
    1425         219 :     if (!z) return gc_NULL(av);
    1426         219 :     if (!pr || pr==ONLY_DIVIDES) return gerepilecopy(av, z);
    1427         215 :     return gc_all(av, 2, &z, pr);
    1428             :   }
    1429             : }
    1430             : 
    1431             : GEN
    1432    52089503 : FpX_rem(GEN x, GEN T, GEN p)
    1433             : {
    1434    52089503 :   GEN B, y = get_FpX_red(T, &B);
    1435    52090358 :   long dy = degpol(y), dx = degpol(x), d = dx-dy;
    1436    52104813 :   if (d < 0) return FpX_red(x,p);
    1437    37987033 :   if (!B && d+3 < FpX_REM_BARRETT_LIMIT)
    1438    37821518 :     return FpX_divrem_basecase(x,y,p,ONLY_REM);
    1439      165515 :   else if (lgefint(p)==3)
    1440             :   {
    1441       40749 :     pari_sp av = avma;
    1442       40749 :     ulong pp = to_Flxq(&x, &T, p);
    1443       40752 :     return Flx_to_ZX_inplace(gerepileuptoleaf(av, Flx_rem(x, T, pp)));
    1444             :   } else
    1445             :   {
    1446      124766 :     pari_sp av = avma;
    1447      124766 :     GEN mg = B? B: FpX_invBarrett(y, p);
    1448      124766 :     return gerepileupto(av, FpX_divrem_Barrett(x, mg, y, p, ONLY_REM));
    1449             :   }
    1450             : }
    1451             : 
    1452             : static GEN
    1453       32292 : FpXV_producttree_dbl(GEN t, long n, GEN p)
    1454             : {
    1455       32292 :   long i, j, k, m = n==1 ? 1: expu(n-1)+1;
    1456       32292 :   GEN T = cgetg(m+1, t_VEC);
    1457       32292 :   gel(T,1) = t;
    1458       63400 :   for (i=2; i<=m; i++)
    1459             :   {
    1460       31109 :     GEN u = gel(T, i-1);
    1461       31109 :     long n = lg(u)-1;
    1462       31109 :     GEN t = cgetg(((n+1)>>1)+1, t_VEC);
    1463      101634 :     for (j=1, k=1; k<n; j++, k+=2)
    1464       70526 :       gel(t, j) = FpX_mul(gel(u, k), gel(u, k+1), p);
    1465       31108 :     gel(T, i) = t;
    1466             :   }
    1467       32291 :   return T;
    1468             : }
    1469             : 
    1470             : static GEN
    1471       31702 : FpV_producttree(GEN xa, GEN s, GEN p, long vs)
    1472             : {
    1473       31702 :   long n = lg(xa)-1;
    1474       31702 :   long j, k, ls = lg(s);
    1475       31702 :   GEN t = cgetg(ls, t_VEC);
    1476      131662 :   for (j=1, k=1; j<ls; k+=s[j++])
    1477       99961 :     gel(t, j) = s[j] == 1 ?
    1478       99959 :              deg1pol_shallow(gen_1, Fp_neg(gel(xa,k), p), vs):
    1479       61727 :              deg2pol_shallow(gen_1,
    1480       61727 :                Fp_neg(Fp_add(gel(xa,k), gel(xa,k+1), p), p),
    1481       61725 :                Fp_mul(gel(xa,k), gel(xa,k+1), p), vs);
    1482       31703 :   return FpXV_producttree_dbl(t, n, p);
    1483             : }
    1484             : 
    1485             : static GEN
    1486       32291 : FpX_FpXV_multirem_dbl_tree(GEN P, GEN T, GEN p)
    1487             : {
    1488             :   long i,j,k;
    1489       32291 :   long m = lg(T)-1;
    1490             :   GEN t;
    1491       32291 :   GEN Tp = cgetg(m+1, t_VEC);
    1492       32291 :   gel(Tp, m) = mkvec(P);
    1493       63400 :   for (i=m-1; i>=1; i--)
    1494             :   {
    1495       31109 :     GEN u = gel(T, i);
    1496       31109 :     GEN v = gel(Tp, i+1);
    1497       31109 :     long n = lg(u)-1;
    1498       31109 :     t = cgetg(n+1, t_VEC);
    1499      101634 :     for (j=1, k=1; k<n; j++, k+=2)
    1500             :     {
    1501       70525 :       gel(t, k)   = FpX_rem(gel(v, j), gel(u, k), p);
    1502       70524 :       gel(t, k+1) = FpX_rem(gel(v, j), gel(u, k+1), p);
    1503             :     }
    1504       31109 :     gel(Tp, i) = t;
    1505             :   }
    1506       32291 :   return Tp;
    1507             : }
    1508             : 
    1509             : static GEN
    1510       31703 : FpX_FpV_multieval_tree(GEN P, GEN xa, GEN T, GEN p)
    1511             : {
    1512       31703 :   pari_sp av = avma;
    1513             :   long j,k;
    1514       31703 :   GEN Tp = FpX_FpXV_multirem_dbl_tree(P, T, p);
    1515       31703 :   GEN R = cgetg(lg(xa), t_VEC);
    1516       31705 :   GEN u = gel(T, 1);
    1517       31705 :   GEN v = gel(Tp, 1);
    1518       31705 :   long n = lg(u)-1;
    1519      131661 :   for (j=1, k=1; j<=n; j++)
    1520             :   {
    1521       99959 :     long c, d = degpol(gel(u,j));
    1522      261634 :     for (c=1; c<=d; c++, k++)
    1523      161678 :       gel(R,k) = FpX_eval(gel(v, j), gel(xa,k), p);
    1524             :   }
    1525       31702 :   return gerepileupto(av, R);
    1526             : }
    1527             : 
    1528             : static GEN
    1529           1 : FpVV_polint_tree(GEN T, GEN R, GEN s, GEN xa, GEN ya, GEN p, long vs)
    1530             : {
    1531           1 :   pari_sp av = avma;
    1532           1 :   long m = lg(T)-1;
    1533           1 :   long i, j, k, ls = lg(s);
    1534           1 :   GEN Tp = cgetg(m+1, t_VEC);
    1535           1 :   GEN t = cgetg(ls, t_VEC);
    1536           3 :   for (j=1, k=1; j<ls; k+=s[j++])
    1537           2 :     if (s[j]==2)
    1538             :     {
    1539           2 :       GEN a = Fp_mul(gel(ya,k), gel(R,k), p);
    1540           2 :       GEN b = Fp_mul(gel(ya,k+1), gel(R,k+1), p);
    1541           2 :       gel(t, j) = deg1pol_shallow(Fp_add(a, b, p),
    1542           2 :               Fp_neg(Fp_add(Fp_mul(gel(xa,k), b, p ),
    1543           2 :               Fp_mul(gel(xa,k+1), a, p), p), p), vs);
    1544             :     }
    1545             :     else
    1546           0 :       gel(t, j) = scalarpol(Fp_mul(gel(ya,k), gel(R,k), p), vs);
    1547           1 :   gel(Tp, 1) = t;
    1548           2 :   for (i=2; i<=m; i++)
    1549             :   {
    1550           1 :     GEN u = gel(T, i-1);
    1551           1 :     GEN t = cgetg(lg(gel(T,i)), t_VEC);
    1552           1 :     GEN v = gel(Tp, i-1);
    1553           1 :     long n = lg(v)-1;
    1554           2 :     for (j=1, k=1; k<n; j++, k+=2)
    1555           1 :       gel(t, j) = FpX_add(ZX_mul(gel(u, k), gel(v, k+1)),
    1556           1 :                           ZX_mul(gel(u, k+1), gel(v, k)), p);
    1557           1 :     gel(Tp, i) = t;
    1558             :   }
    1559           1 :   return gerepilecopy(av, gmael(Tp,m,1));
    1560             : }
    1561             : 
    1562             : GEN
    1563           0 : FpX_FpV_multieval(GEN P, GEN xa, GEN p)
    1564             : {
    1565           0 :   pari_sp av = avma;
    1566           0 :   GEN s = producttree_scheme(lg(xa)-1);
    1567           0 :   GEN T = FpV_producttree(xa, s, p, varn(P));
    1568           0 :   return gerepileupto(av, FpX_FpV_multieval_tree(P, xa, T, p));
    1569             : }
    1570             : 
    1571             : GEN
    1572           8 : FpV_polint(GEN xa, GEN ya, GEN p, long vs)
    1573             : {
    1574           8 :   pari_sp av = avma;
    1575             :   GEN s, T, P, R;
    1576             :   long m;
    1577           8 :   if (lgefint(p) == 3)
    1578             :   {
    1579           7 :     ulong pp = p[2];
    1580           7 :     P = Flv_polint(ZV_to_Flv(xa, pp), ZV_to_Flv(ya, pp), pp, evalvarn(vs));
    1581           7 :     return gerepileupto(av, Flx_to_ZX(P));
    1582             :   }
    1583           1 :   s = producttree_scheme(lg(xa)-1);
    1584           1 :   T = FpV_producttree(xa, s, p, vs);
    1585           1 :   m = lg(T)-1;
    1586           1 :   P = FpX_deriv(gmael(T, m, 1), p);
    1587           1 :   R = FpV_inv(FpX_FpV_multieval_tree(P, xa, T, p), p);
    1588           1 :   return gerepileupto(av, FpVV_polint_tree(T, R, s, xa, ya, p, vs));
    1589             : }
    1590             : 
    1591             : GEN
    1592           0 : FpV_FpM_polint(GEN xa, GEN ya, GEN p, long vs)
    1593             : {
    1594           0 :   pari_sp av = avma;
    1595           0 :   GEN s = producttree_scheme(lg(xa)-1);
    1596           0 :   GEN T = FpV_producttree(xa, s, p, vs);
    1597           0 :   long i, m = lg(T)-1, l = lg(ya)-1;
    1598           0 :   GEN P = FpX_deriv(gmael(T, m, 1), p);
    1599           0 :   GEN R = FpV_inv(FpX_FpV_multieval_tree(P, xa, T, p), p);
    1600           0 :   GEN M = cgetg(l+1, t_VEC);
    1601           0 :   for (i=1; i<=l; i++)
    1602           0 :     gel(M,i) = FpVV_polint_tree(T, R, s, xa, gel(ya,i), p, vs);
    1603           0 :   return gerepileupto(av, M);
    1604             : }
    1605             : 
    1606             : GEN
    1607       31701 : FpV_invVandermonde(GEN L, GEN den, GEN p)
    1608             : {
    1609       31701 :   pari_sp av = avma;
    1610       31701 :   long i, n = lg(L);
    1611             :   GEN M, R;
    1612       31701 :   GEN s = producttree_scheme(n-1);
    1613       31701 :   GEN tree = FpV_producttree(L, s, p, 0);
    1614       31702 :   long m = lg(tree)-1;
    1615       31702 :   GEN T = gmael(tree, m, 1);
    1616       31702 :   R = FpV_inv(FpX_FpV_multieval_tree(FpX_deriv(T, p), L, tree, p), p);
    1617       31701 :   if (den) R = FpC_Fp_mul(R, den, p);
    1618       31702 :   M = cgetg(n, t_MAT);
    1619      193389 :   for (i = 1; i < n; i++)
    1620             :   {
    1621      161686 :     GEN P = FpX_Fp_mul(FpX_div_by_X_x(T, gel(L,i), p, NULL), gel(R,i), p);
    1622      161678 :     gel(M,i) = RgX_to_RgC(P, n-1);
    1623             :   }
    1624       31703 :   return gerepilecopy(av, M);
    1625             : }
    1626             : 
    1627             : static GEN
    1628         588 : FpXV_producttree(GEN xa, GEN s, GEN p)
    1629             : {
    1630         588 :   long n = lg(xa)-1;
    1631         588 :   long j, k, ls = lg(s);
    1632         588 :   GEN t = cgetg(ls, t_VEC);
    1633        3444 :   for (j=1, k=1; j<ls; k+=s[j++])
    1634        2856 :     gel(t, j) = s[j] == 1 ?
    1635        2856 :              gel(xa,k): FpX_mul(gel(xa,k),gel(xa,k+1),p);
    1636         588 :   return FpXV_producttree_dbl(t, n, p);
    1637             : }
    1638             : 
    1639             : static GEN
    1640         588 : FpX_FpXV_multirem_tree(GEN P, GEN xa, GEN T, GEN s, GEN p)
    1641             : {
    1642         588 :   pari_sp av = avma;
    1643         588 :   long j, k, ls = lg(s);
    1644         588 :   GEN Tp = FpX_FpXV_multirem_dbl_tree(P, T, p);
    1645         588 :   GEN R = cgetg(lg(xa), t_VEC);
    1646         588 :   GEN v = gel(Tp, 1);
    1647        3444 :   for (j=1, k=1; j<ls; k+=s[j++])
    1648             :   {
    1649        2856 :     gel(R,k) = FpX_rem(gel(v, j), gel(xa,k), p);
    1650        2856 :     if (s[j] == 2)
    1651        1050 :       gel(R,k+1) = FpX_rem(gel(v, j), gel(xa,k+1), p);
    1652             :   }
    1653         588 :   return gerepileupto(av, R);
    1654             : }
    1655             : 
    1656             : GEN
    1657           0 : FpX_FpXV_multirem(GEN P, GEN xa, GEN p)
    1658             : {
    1659           0 :   pari_sp av = avma;
    1660           0 :   GEN s = producttree_scheme(lg(xa)-1);
    1661           0 :   GEN T = FpXV_producttree(xa, s, p);
    1662           0 :   return gerepileupto(av, FpX_FpXV_multirem_tree(P, xa, T, s, p));
    1663             : }
    1664             : 
    1665             : /* T = ZV_producttree(P), R = ZV_chinesetree(P,T) */
    1666             : static GEN
    1667         588 : FpXV_chinese_tree(GEN A, GEN P, GEN T, GEN R, GEN s, GEN p)
    1668             : {
    1669         588 :   long m = lg(T)-1, ls = lg(s);
    1670             :   long i,j,k;
    1671         588 :   GEN Tp = cgetg(m+1, t_VEC);
    1672         588 :   GEN M = gel(T, 1);
    1673         588 :   GEN t = cgetg(lg(M), t_VEC);
    1674        3444 :   for (j=1, k=1; j<ls; k+=s[j++])
    1675        2856 :     if (s[j] == 2)
    1676             :     {
    1677        1050 :       pari_sp av = avma;
    1678        1050 :       GEN a = FpX_mul(gel(A,k), gel(R,k), p), b = FpX_mul(gel(A,k+1), gel(R,k+1), p);
    1679        1050 :       GEN tj = FpX_rem(FpX_add(FpX_mul(gel(P,k), b, p),
    1680        1050 :             FpX_mul(gel(P,k+1), a, p), p), gel(M,j), p);
    1681        1050 :       gel(t, j) = gerepileupto(av, tj);
    1682             :     }
    1683             :     else
    1684        1806 :       gel(t, j) = FpX_rem(FpX_mul(gel(A,k), gel(R,k), p), gel(M, j), p);
    1685         588 :   gel(Tp, 1) = t;
    1686        1890 :   for (i=2; i<=m; i++)
    1687             :   {
    1688        1302 :     GEN u = gel(T, i-1), M = gel(T, i);
    1689        1302 :     GEN t = cgetg(lg(M), t_VEC);
    1690        1302 :     GEN v = gel(Tp, i-1);
    1691        1302 :     long n = lg(v)-1;
    1692        3570 :     for (j=1, k=1; k<n; j++, k+=2)
    1693             :     {
    1694        2268 :       pari_sp av = avma;
    1695        2268 :       gel(t, j) = gerepileupto(av, FpX_rem(FpX_add(FpX_mul(gel(u, k), gel(v, k+1), p),
    1696        2268 :               FpX_mul(gel(u, k+1), gel(v, k), p), p), gel(M, j), p));
    1697             :     }
    1698        1302 :     if (k==n) gel(t, j) = gel(v, k);
    1699        1302 :     gel(Tp, i) = t;
    1700             :   }
    1701         588 :   return gmael(Tp,m,1);
    1702             : }
    1703             : 
    1704             : static GEN
    1705         588 : FpXV_sqr(GEN x, GEN p)
    1706        4494 : { pari_APPLY_type(t_VEC, FpX_sqr(gel(x,i), p)) }
    1707             : 
    1708             : static GEN
    1709        7602 : FpXT_sqr(GEN x, GEN p)
    1710             : {
    1711        7602 :   if (typ(x) == t_POL)
    1712        5124 :     return FpX_sqr(x, p);
    1713        9492 :   pari_APPLY_type(t_VEC, FpXT_sqr(gel(x,i), p))
    1714             : }
    1715             : 
    1716             : static GEN
    1717         588 : FpXV_invdivexact(GEN x, GEN y, GEN p)
    1718        4494 : { pari_APPLY_type(t_VEC, FpXQ_inv(FpX_div(gel(x,i), gel(y,i),p), gel(y,i),p)) }
    1719             : 
    1720             : static GEN
    1721         588 : FpXV_chinesetree(GEN P, GEN T, GEN s, GEN p)
    1722             : {
    1723         588 :   GEN T2 = FpXT_sqr(T, p), P2 = FpXV_sqr(P, p);
    1724         588 :   GEN mod = gmael(T,lg(T)-1,1);
    1725         588 :   return FpXV_invdivexact(FpX_FpXV_multirem_tree(mod, P2, T2, s, p), P, p);
    1726             : }
    1727             : 
    1728             : static GEN
    1729         588 : gc_chinese(pari_sp av, GEN T, GEN a, GEN *pt_mod)
    1730             : {
    1731         588 :   if (!pt_mod)
    1732         588 :     return gerepileupto(av, a);
    1733             :   else
    1734             :   {
    1735           0 :     GEN mod = gmael(T, lg(T)-1, 1);
    1736           0 :     gerepileall(av, 2, &a, &mod);
    1737           0 :     *pt_mod = mod;
    1738           0 :     return a;
    1739             :   }
    1740             : }
    1741             : 
    1742             : GEN
    1743         588 : FpXV_chinese(GEN A, GEN P, GEN p, GEN *pt_mod)
    1744             : {
    1745         588 :   pari_sp av = avma;
    1746         588 :   GEN s = producttree_scheme(lg(P)-1);
    1747         588 :   GEN T = FpXV_producttree(P, s, p);
    1748         588 :   GEN R = FpXV_chinesetree(P, T, s, p);
    1749         588 :   GEN a = FpXV_chinese_tree(A, P, T, R, s, p);
    1750         588 :   return gc_chinese(av, T, a, pt_mod);
    1751             : }
    1752             : 
    1753             : /***********************************************************************/
    1754             : /**                                                                   **/
    1755             : /**                              FpXQ                                 **/
    1756             : /**                                                                   **/
    1757             : /***********************************************************************/
    1758             : 
    1759             : /* FpXQ are elements of Fp[X]/(T), represented by FpX*/
    1760             : 
    1761             : GEN
    1762    12542809 : FpXQ_red(GEN x, GEN T, GEN p)
    1763             : {
    1764    12542809 :   GEN z = FpX_red(x,p);
    1765    12538159 :   return FpX_rem(z, T,p);
    1766             : }
    1767             : 
    1768             : GEN
    1769    10442006 : FpXQ_mul(GEN x,GEN y,GEN T,GEN p)
    1770             : {
    1771    10442006 :   GEN z = FpX_mul(x,y,p);
    1772    10441735 :   return FpX_rem(z, T, p);
    1773             : }
    1774             : 
    1775             : GEN
    1776     4749329 : FpXQ_sqr(GEN x, GEN T, GEN p)
    1777             : {
    1778     4749329 :   GEN z = FpX_sqr(x,p);
    1779     4748980 :   return FpX_rem(z, T, p);
    1780             : }
    1781             : 
    1782             : /* Inverse of x in Z/pZ[X]/(pol) or NULL if inverse doesn't exist
    1783             :  * return lift(1 / (x mod (p,pol))) */
    1784             : GEN
    1785      778250 : FpXQ_invsafe(GEN x, GEN y, GEN p)
    1786             : {
    1787      778250 :   GEN V, z = FpX_extgcd(get_FpX_mod(y), x, p, NULL, &V);
    1788      778246 :   if (degpol(z)) return NULL;
    1789      778243 :   z = Fp_invsafe(gel(z,2), p);
    1790      778161 :   if (!z) return NULL;
    1791      778161 :   return FpX_Fp_mul(V, z, p);
    1792             : }
    1793             : 
    1794             : GEN
    1795      778249 : FpXQ_inv(GEN x,GEN T,GEN p)
    1796             : {
    1797      778249 :   pari_sp av = avma;
    1798      778249 :   GEN U = FpXQ_invsafe(x, T, p);
    1799      778220 :   if (!U) pari_err_INV("FpXQ_inv",x);
    1800      778220 :   return gerepileupto(av, U);
    1801             : }
    1802             : 
    1803             : GEN
    1804      233584 : FpXQ_div(GEN x,GEN y,GEN T,GEN p)
    1805             : {
    1806      233584 :   pari_sp av = avma;
    1807      233584 :   return gerepileupto(av, FpXQ_mul(x,FpXQ_inv(y,T,p),T,p));
    1808             : }
    1809             : 
    1810             : static GEN
    1811     2197883 : _FpXQ_add(void *data, GEN x, GEN y)
    1812             : {
    1813             :   (void) data;
    1814     2197883 :   return ZX_add(x, y);
    1815             : }
    1816             : static GEN
    1817       37107 : _FpXQ_sub(void *data, GEN x, GEN y)
    1818             : {
    1819             :   (void) data;
    1820       37107 :   return ZX_sub(x, y);
    1821             : }
    1822             : static GEN
    1823     2581246 : _FpXQ_cmul(void *data, GEN P, long a, GEN x)
    1824             : {
    1825             :   (void) data;
    1826     2581246 :   return ZX_Z_mul(x, gel(P,a+2));
    1827             : }
    1828             : static GEN
    1829     4271444 : _FpXQ_sqr(void *data, GEN x)
    1830             : {
    1831     4271444 :   struct _FpXQ *D = (struct _FpXQ*)data;
    1832     4271444 :   return FpXQ_sqr(x, D->T, D->p);
    1833             : }
    1834             : static GEN
    1835     1440053 : _FpXQ_mul(void *data, GEN x, GEN y)
    1836             : {
    1837     1440053 :   struct _FpXQ *D = (struct _FpXQ*)data;
    1838     1440053 :   return FpXQ_mul(x,y, D->T, D->p);
    1839             : }
    1840             : static GEN
    1841        4158 : _FpXQ_zero(void *data)
    1842             : {
    1843        4158 :   struct _FpXQ *D = (struct _FpXQ*)data;
    1844        4158 :   return pol_0(get_FpX_var(D->T));
    1845             : }
    1846             : static GEN
    1847      811545 : _FpXQ_one(void *data)
    1848             : {
    1849      811545 :   struct _FpXQ *D = (struct _FpXQ*)data;
    1850      811545 :   return pol_1(get_FpX_var(D->T));
    1851             : }
    1852             : static GEN
    1853      832700 : _FpXQ_red(void *data, GEN x)
    1854             : {
    1855      832700 :   struct _FpXQ *D = (struct _FpXQ*)data;
    1856      832700 :   return FpX_red(x,D->p);
    1857             : }
    1858             : 
    1859             : static struct bb_algebra FpXQ_algebra = { _FpXQ_red, _FpXQ_add, _FpXQ_sub,
    1860             :        _FpXQ_mul, _FpXQ_sqr, _FpXQ_one, _FpXQ_zero };
    1861             : 
    1862             : const struct bb_algebra *
    1863        8113 : get_FpXQ_algebra(void **E, GEN T, GEN p)
    1864             : {
    1865        8113 :   GEN z = new_chunk(sizeof(struct _FpXQ));
    1866        8113 :   struct _FpXQ *e = (struct _FpXQ *) z;
    1867        8113 :   e->T = FpX_get_red(T, p);
    1868        8113 :   e->p  = p; *E = (void*)e;
    1869        8113 :   return &FpXQ_algebra;
    1870             : }
    1871             : 
    1872             : static GEN
    1873           0 : _FpX_red(void *E, GEN x)
    1874           0 : { struct _FpX *D = (struct _FpX*)E; return FpX_red(x,D->p); }
    1875             : 
    1876             : static GEN
    1877           0 : _FpX_zero(void *E)
    1878           0 : { struct _FpX *D = (struct _FpX *)E; return pol_0(D->v); }
    1879             : 
    1880             : 
    1881             : static struct bb_algebra FpX_algebra = { _FpX_red, _FpXQ_add, _FpXQ_sub,
    1882             :        _FpX_mul, _FpX_sqr, _FpX_one, _FpX_zero };
    1883             : 
    1884             : const struct bb_algebra *
    1885           0 : get_FpX_algebra(void **E, GEN p, long v)
    1886             : {
    1887           0 :   GEN z = new_chunk(sizeof(struct _FpX));
    1888           0 :   struct _FpX *e = (struct _FpX *) z;
    1889           0 :   e->p  = p; e->v = v; *E = (void*)e;
    1890           0 :   return &FpX_algebra;
    1891             : }
    1892             : 
    1893             : /* x,pol in Z[X], p in Z, n in Z, compute lift(x^n mod (p, pol)) */
    1894             : GEN
    1895     1010535 : FpXQ_pow(GEN x, GEN n, GEN T, GEN p)
    1896             : {
    1897             :   struct _FpXQ D;
    1898             :   pari_sp av;
    1899     1010535 :   long s = signe(n);
    1900             :   GEN y;
    1901     1010535 :   if (!s) return pol_1(varn(x));
    1902     1008487 :   if (is_pm1(n)) /* +/- 1 */
    1903       39775 :     return (s < 0)? FpXQ_inv(x,T,p): FpXQ_red(x,T,p);
    1904      968714 :   av = avma;
    1905      968714 :   if (!is_bigint(p))
    1906             :   {
    1907      717801 :     ulong pp = to_Flxq(&x, &T, p);
    1908      717800 :     y = Flxq_pow(x, n, T, pp);
    1909      717789 :     return Flx_to_ZX_inplace(gerepileuptoleaf(av, y));
    1910             :   }
    1911      250915 :   if (s < 0) x = FpXQ_inv(x,T,p);
    1912      250915 :   D.p = p; D.T = FpX_get_red(T,p);
    1913      250915 :   y = gen_pow_i(x, n, (void*)&D, &_FpXQ_sqr, &_FpXQ_mul);
    1914      250915 :   return gerepilecopy(av, y);
    1915             : }
    1916             : 
    1917             : GEN /*Assume n is very small*/
    1918      601197 : FpXQ_powu(GEN x, ulong n, GEN T, GEN p)
    1919             : {
    1920             :   struct _FpXQ D;
    1921             :   pari_sp av;
    1922             :   GEN y;
    1923      601197 :   if (!n) return pol_1(varn(x));
    1924      601197 :   if (n==1) return FpXQ_red(x,T,p);
    1925      201798 :   av = avma;
    1926      201798 :   if (!is_bigint(p))
    1927             :   {
    1928      195577 :     ulong pp = to_Flxq(&x, &T, p);
    1929      195573 :     y = Flxq_powu(x, n, T, pp);
    1930      195570 :     return Flx_to_ZX_inplace(gerepileuptoleaf(av, y));
    1931             :   }
    1932        6237 :   D.T = FpX_get_red(T, p); D.p = p;
    1933        6237 :   y = gen_powu_i(x, n, (void*)&D, &_FpXQ_sqr, &_FpXQ_mul);
    1934        6237 :   return gerepilecopy(av, y);
    1935             : }
    1936             : 
    1937             : /* generates the list of powers of x of degree 0,1,2,...,l*/
    1938             : GEN
    1939      346837 : FpXQ_powers(GEN x, long l, GEN T, GEN p)
    1940             : {
    1941             :   struct _FpXQ D;
    1942             :   int use_sqr;
    1943      346837 :   if (l>2 && lgefint(p) == 3) {
    1944      209228 :     pari_sp av = avma;
    1945      209228 :     ulong pp = to_Flxq(&x, &T, p);
    1946      209228 :     GEN z = FlxV_to_ZXV(Flxq_powers(x, l, T, pp));
    1947      209231 :     return gerepileupto(av, z);
    1948             :   }
    1949      137609 :   use_sqr = 2*degpol(x)>=get_FpX_degree(T);
    1950      137626 :   D.T = FpX_get_red(T,p); D.p = p;
    1951      137629 :   return gen_powers(x, l, use_sqr, (void*)&D, &_FpXQ_sqr, &_FpXQ_mul,&_FpXQ_one);
    1952             : }
    1953             : 
    1954             : GEN
    1955       32674 : FpXQ_matrix_pow(GEN y, long n, long m, GEN P, GEN l)
    1956             : {
    1957       32674 :   return RgXV_to_RgM(FpXQ_powers(y,m-1,P,l),n);
    1958             : }
    1959             : 
    1960             : GEN
    1961      391677 : FpX_Frobenius(GEN T, GEN p)
    1962             : {
    1963      391677 :   return FpXQ_pow(pol_x(get_FpX_var(T)), p, T, p);
    1964             : }
    1965             : 
    1966             : GEN
    1967       31436 : FpX_matFrobenius(GEN T, GEN p)
    1968             : {
    1969       31436 :   long n = get_FpX_degree(T);
    1970       31436 :   return FpXQ_matrix_pow(FpX_Frobenius(T, p), n, n, T, p);
    1971             : }
    1972             : 
    1973             : GEN
    1974      378358 : FpX_FpXQV_eval(GEN Q, GEN x, GEN T, GEN p)
    1975             : {
    1976             :   struct _FpXQ D;
    1977      378358 :   D.T = FpX_get_red(T,p); D.p = p;
    1978      378368 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&D,&FpXQ_algebra,_FpXQ_cmul);
    1979             : }
    1980             : 
    1981             : GEN
    1982      792170 : FpX_FpXQ_eval(GEN Q, GEN x, GEN T, GEN p)
    1983             : {
    1984             :   struct _FpXQ D;
    1985             :   int use_sqr;
    1986      792170 :   if (lgefint(p) == 3)
    1987             :   {
    1988      786488 :     pari_sp av = avma;
    1989      786488 :     ulong pp = to_Flxq(&x, &T, p);
    1990      786497 :     GEN z = Flx_Flxq_eval(ZX_to_Flx(Q, pp), x, T, pp);
    1991      786494 :     return Flx_to_ZX_inplace(gerepileuptoleaf(av, z));
    1992             :   }
    1993        5682 :   use_sqr = 2*degpol(x) >= get_FpX_degree(T);
    1994        5682 :   D.T = FpX_get_red(T,p); D.p = p;
    1995        5682 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&D,&FpXQ_algebra,_FpXQ_cmul);
    1996             : }
    1997             : 
    1998             : GEN
    1999        1470 : FpXC_FpXQV_eval(GEN x, GEN v, GEN T, GEN p)
    2000        8316 : { pari_APPLY_type(t_COL, FpX_FpXQV_eval(gel(x,i), v, T, p)) }
    2001             : 
    2002             : GEN
    2003         315 : FpXM_FpXQV_eval(GEN x, GEN v, GEN T, GEN p)
    2004        1197 : { pari_APPLY_same(FpXC_FpXQV_eval(gel(x,i), v, T, p)) }
    2005             : 
    2006             : GEN
    2007         588 : FpXC_FpXQ_eval(GEN x, GEN F, GEN T, GEN p)
    2008             : {
    2009         588 :   long d = brent_kung_optpow(RgXV_maxdegree(x), lg(x)-1, 1);
    2010         588 :   GEN Fp = FpXQ_powers(F, d, T, p);
    2011         588 :   return FpXC_FpXQV_eval(x, Fp, T, p);
    2012             : }
    2013             : 
    2014             : GEN
    2015        1757 : FpXQ_autpowers(GEN aut, long f, GEN T, GEN p)
    2016             : {
    2017        1757 :   pari_sp av = avma;
    2018        1757 :   long n = get_FpX_degree(T);
    2019        1757 :   long i, nautpow = brent_kung_optpow(n-1,f-2,1);
    2020        1757 :   long v = get_FpX_var(T);
    2021             :   GEN autpow, V;
    2022        1757 :   T = FpX_get_red(T, p);
    2023        1757 :   autpow = FpXQ_powers(aut, nautpow,T,p);
    2024        1757 :   V = cgetg(f + 2, t_VEC);
    2025        1757 :   gel(V,1) = pol_x(v); if (f==0) return gerepileupto(av, V);
    2026        1757 :   gel(V,2) = gcopy(aut);
    2027        6244 :   for (i = 3; i <= f+1; i++)
    2028        4487 :     gel(V,i) = FpX_FpXQV_eval(gel(V,i-1),autpow,T,p);
    2029        1757 :   return gerepileupto(av, V);
    2030             : }
    2031             : 
    2032             : static GEN
    2033        5025 : FpXQ_autpow_sqr(void *E, GEN x)
    2034             : {
    2035        5025 :   struct _FpXQ *D = (struct _FpXQ*)E;
    2036        5025 :   return FpX_FpXQ_eval(x, x, D->T, D->p);
    2037             : }
    2038             : 
    2039             : static GEN
    2040          21 : FpXQ_autpow_msqr(void *E, GEN x)
    2041             : {
    2042          21 :   struct _FpXQ *D = (struct _FpXQ*)E;
    2043          21 :   return FpX_FpXQV_eval(FpXQ_autpow_sqr(E, x), D->aut, D->T, D->p);
    2044             : }
    2045             : 
    2046             : GEN
    2047        4731 : FpXQ_autpow(GEN x, ulong n, GEN T, GEN p)
    2048             : {
    2049        4731 :   pari_sp av = avma;
    2050             :   struct _FpXQ D;
    2051             :   long d;
    2052        4731 :   if (n==0) return FpX_rem(pol_x(varn(x)), T, p);
    2053        4731 :   if (n==1) return FpX_rem(x, T, p);
    2054        4731 :   D.T = FpX_get_red(T, p); D.p = p;
    2055        4731 :   d = brent_kung_optpow(degpol(T), hammingl(n)-1, 1);
    2056        4731 :   D.aut = FpXQ_powers(x, d, T, p);
    2057        4731 :   x = gen_powu_fold(x,n,(void*)&D,FpXQ_autpow_sqr,FpXQ_autpow_msqr);
    2058        4731 :   return gerepilecopy(av, x);
    2059             : }
    2060             : 
    2061             : static GEN
    2062         421 : FpXQ_auttrace_mul(void *E, GEN x, GEN y)
    2063             : {
    2064         421 :   struct _FpXQ *D = (struct _FpXQ*)E;
    2065         421 :   GEN T = D->T, p = D->p;
    2066         421 :   GEN phi1 = gel(x,1), a1 = gel(x,2);
    2067         421 :   GEN phi2 = gel(y,1), a2 = gel(y,2);
    2068         421 :   ulong d = brent_kung_optpow(maxss(degpol(phi2),degpol(a2)),2,1);
    2069         421 :   GEN V1 = FpXQ_powers(phi1, d, T, p);
    2070         421 :   GEN phi3 = FpX_FpXQV_eval(phi2, V1, T, p);
    2071         421 :   GEN aphi = FpX_FpXQV_eval(a2, V1, T, p);
    2072         421 :   GEN a3 = FpX_add(a1, aphi, p);
    2073         421 :   return mkvec2(phi3, a3);
    2074             : }
    2075             : 
    2076             : static GEN
    2077         365 : FpXQ_auttrace_sqr(void *E, GEN x)
    2078         365 : { return FpXQ_auttrace_mul(E, x, x); }
    2079             : 
    2080             : GEN
    2081         392 : FpXQ_auttrace(GEN x, ulong n, GEN T, GEN p)
    2082             : {
    2083         392 :   pari_sp av = avma;
    2084             :   struct _FpXQ D;
    2085         392 :   D.T = FpX_get_red(T, p); D.p = p;
    2086         392 :   x = gen_powu_i(x,n,(void*)&D,FpXQ_auttrace_sqr,FpXQ_auttrace_mul);
    2087         392 :   return gerepilecopy(av, x);
    2088             : }
    2089             : 
    2090             : static GEN
    2091        5208 : FpXQ_autsum_mul(void *E, GEN x, GEN y)
    2092             : {
    2093        5208 :   struct _FpXQ *D = (struct _FpXQ*)E;
    2094        5208 :   GEN T = D->T, p = D->p;
    2095        5208 :   GEN phi1 = gel(x,1), a1 = gel(x,2);
    2096        5208 :   GEN phi2 = gel(y,1), a2 = gel(y,2);
    2097        5208 :   ulong d = brent_kung_optpow(maxss(degpol(phi2),degpol(a2)),2,1);
    2098        5208 :   GEN V1 = FpXQ_powers(phi1, d, T, p);
    2099        5208 :   GEN phi3 = FpX_FpXQV_eval(phi2, V1, T, p);
    2100        5208 :   GEN aphi = FpX_FpXQV_eval(a2, V1, T, p);
    2101        5208 :   GEN a3 = FpXQ_mul(a1, aphi, T, p);
    2102        5208 :   return mkvec2(phi3, a3);
    2103             : }
    2104             : static GEN
    2105        4053 : FpXQ_autsum_sqr(void *E, GEN x)
    2106        4053 : { return FpXQ_autsum_mul(E, x, x); }
    2107             : 
    2108             : GEN
    2109        3997 : FpXQ_autsum(GEN x, ulong n, GEN T, GEN p)
    2110             : {
    2111        3997 :   pari_sp av = avma;
    2112             :   struct _FpXQ D;
    2113        3997 :   D.T = FpX_get_red(T, p); D.p = p;
    2114        3997 :   x = gen_powu_i(x,n,(void*)&D,FpXQ_autsum_sqr,FpXQ_autsum_mul);
    2115        3997 :   return gerepilecopy(av, x);
    2116             : }
    2117             : 
    2118             : static GEN
    2119         315 : FpXQM_autsum_mul(void *E, GEN x, GEN y)
    2120             : {
    2121         315 :   struct _FpXQ *D = (struct _FpXQ*)E;
    2122         315 :   GEN T = D->T, p = D->p;
    2123         315 :   GEN phi1 = gel(x,1), a1 = gel(x,2);
    2124         315 :   GEN phi2 = gel(y,1), a2 = gel(y,2);
    2125         315 :   long g = lg(a2)-1, dT = get_FpX_degree(T);
    2126         315 :   ulong d = brent_kung_optpow(dT-1, g*g+1, 1);
    2127         315 :   GEN V1 = FpXQ_powers(phi1, d, T, p);
    2128         315 :   GEN phi3 = FpX_FpXQV_eval(phi2, V1, T, p);
    2129         315 :   GEN aphi = FpXM_FpXQV_eval(a2, V1, T, p);
    2130         315 :   GEN a3 = FqM_mul(a1, aphi, T, p);
    2131         315 :   return mkvec2(phi3, a3);
    2132             : }
    2133             : static GEN
    2134         217 : FpXQM_autsum_sqr(void *E, GEN x)
    2135         217 : { return FpXQM_autsum_mul(E, x, x); }
    2136             : 
    2137             : GEN
    2138         147 : FpXQM_autsum(GEN x, ulong n, GEN T, GEN p)
    2139             : {
    2140         147 :   pari_sp av = avma;
    2141             :   struct _FpXQ D;
    2142         147 :   D.T = FpX_get_red(T, p); D.p = p;
    2143         147 :   x = gen_powu_i(x, n, (void*)&D, FpXQM_autsum_sqr, FpXQM_autsum_mul);
    2144         147 :   return gerepilecopy(av, x);
    2145             : }
    2146             : 
    2147             : static long
    2148        9180 : bounded_order(GEN p, GEN b, long k)
    2149             : {
    2150             :   long i;
    2151        9180 :   GEN a=modii(p,b);
    2152       18649 :   for(i=1;i<k;i++)
    2153             :   {
    2154       13980 :     if (equali1(a))
    2155        4511 :       return i;
    2156        9469 :     a = Fp_mul(a,p,b);
    2157             :   }
    2158        4669 :   return 0;
    2159             : }
    2160             : 
    2161             : /*
    2162             :   n = (p^d-a)\b
    2163             :   b = bb*p^vb
    2164             :   p^k = 1 [bb]
    2165             :   d = m*k+r+vb
    2166             :   u = (p^k-1)/bb;
    2167             :   v = (p^(r+vb)-a)/b;
    2168             :   w = (p^(m*k)-1)/(p^k-1)
    2169             :   n = p^r*w*u+v
    2170             :   w*u = p^vb*(p^(m*k)-1)/b
    2171             :   n = p^(r+vb)*(p^(m*k)-1)/b+(p^(r+vb)-a)/b
    2172             : */
    2173             : 
    2174             : static GEN
    2175      249570 : FpXQ_pow_Frobenius(GEN x, GEN n, GEN aut, GEN T, GEN p)
    2176             : {
    2177      249570 :   pari_sp av=avma;
    2178      249570 :   long d = get_FpX_degree(T);
    2179      249570 :   GEN an = absi_shallow(n), z, q;
    2180      249570 :   if (cmpii(an,p)<0 || cmpis(an,d)<=0) return FpXQ_pow(x, n, T, p);
    2181        9201 :   q = powiu(p, d);
    2182        9201 :   if (dvdii(q, n))
    2183             :   {
    2184           0 :     long vn = logint(an,p);
    2185           0 :     GEN autvn = vn==1 ? aut: FpXQ_autpow(aut,vn,T,p);
    2186           0 :     z = FpX_FpXQ_eval(x,autvn,T,p);
    2187             :   } else
    2188             :   {
    2189        9201 :     GEN b = diviiround(q, an), a = subii(q, mulii(an,b));
    2190             :     GEN bb, u, v, autk;
    2191        9201 :     long vb = Z_pvalrem(b,p,&bb);
    2192        9201 :     long m, r, k = is_pm1(bb) ? 1 : bounded_order(p,bb,d);
    2193        9201 :     if (!k || d-vb<k) return FpXQ_pow(x,n, T, p);
    2194        4532 :     m = (d-vb)/k; r = (d-vb)%k;
    2195        4532 :     u = diviiexact(subiu(powiu(p,k),1),bb);
    2196        4532 :     v = diviiexact(subii(powiu(p,r+vb),a),b);
    2197        4532 :     autk = k==1 ? aut: FpXQ_autpow(aut,k,T,p);
    2198        4532 :     if (r)
    2199             :     {
    2200         549 :       GEN autr = r==1 ? aut: FpXQ_autpow(aut,r,T,p);
    2201         549 :       z = FpX_FpXQ_eval(x,autr,T,p);
    2202        3983 :     } else z = x;
    2203        4532 :     if (m > 1) z = gel(FpXQ_autsum(mkvec2(autk, z), m, T, p), 2);
    2204        4532 :     if (!is_pm1(u)) z = FpXQ_pow(z, u, T, p);
    2205        4532 :     if (signe(v)) z = FpXQ_mul(z, FpXQ_pow(x, v, T, p), T, p);
    2206             :   }
    2207        4532 :   return gerepileupto(av,signe(n)>0 ? z : FpXQ_inv(z,T,p));
    2208             : }
    2209             : 
    2210             : /* assume T irreducible mod p */
    2211             : int
    2212      389574 : FpXQ_issquare(GEN x, GEN T, GEN p)
    2213             : {
    2214             :   pari_sp av;
    2215      389574 :   if (lg(x) == 2 || absequalui(2, p)) return 1;
    2216      389560 :   if (lg(x) == 3) return Fq_issquare(gel(x,2), T, p);
    2217      360470 :   av = avma; /* Ng = g^((q-1)/(p-1)) */
    2218      360470 :   return gc_bool(av, kronecker(FpXQ_norm(x,T,p), p) != -1);
    2219             : }
    2220             : int
    2221     1286494 : Fp_issquare(GEN x, GEN p)
    2222     1286494 : { return absequalui(2, p) || kronecker(x, p) != -1; }
    2223             : /* assume T irreducible mod p */
    2224             : int
    2225     1560643 : Fq_issquare(GEN x, GEN T, GEN p)
    2226             : {
    2227     1560643 :   if (typ(x) != t_INT) return FpXQ_issquare(x, T, p);
    2228     1174670 :   return (T && ! odd(get_FpX_degree(T))) || Fp_issquare(x, p);
    2229             : }
    2230             : 
    2231             : long
    2232          70 : Fq_ispower(GEN x, GEN K, GEN T, GEN p)
    2233             : {
    2234          70 :   pari_sp av = avma;
    2235             :   long d;
    2236             :   GEN Q;
    2237          70 :   if (equaliu(K,2)) return Fq_issquare(x, T, p);
    2238           0 :   if (!T) return Fp_ispower(x, K, p);
    2239           0 :   d = get_FpX_degree(T);
    2240           0 :   if (typ(x) == t_INT && !umodui(d, K)) return 1;
    2241           0 :   Q = subiu(powiu(p,d), 1);
    2242           0 :   Q = diviiexact(Q, gcdii(Q, K));
    2243           0 :   d = gequal1(Fq_pow(x, Q, T,p));
    2244           0 :   return gc_long(av, d);
    2245             : }
    2246             : 
    2247             : /* discrete log in FpXQ for a in Fp^*, g in FpXQ^* of order ord */
    2248             : GEN
    2249       40815 : Fp_FpXQ_log(GEN a, GEN g, GEN o, GEN T, GEN p)
    2250             : {
    2251       40815 :   pari_sp av = avma;
    2252             :   GEN q,n_q,ord,ordp, op;
    2253             : 
    2254       40815 :   if (equali1(a)) return gen_0;
    2255             :   /* p > 2 */
    2256             : 
    2257        8810 :   ordp = subiu(p, 1); /* even */
    2258        8810 :   ord  = get_arith_Z(o);
    2259        8782 :   if (!ord) ord = T? subiu(powiu(p, get_FpX_degree(T)), 1): ordp;
    2260        8782 :   if (equalii(a, ordp)) /* -1 */
    2261        6559 :     return gerepileuptoint(av, shifti(ord,-1));
    2262        2223 :   ordp = gcdii(ordp,ord);
    2263        2223 :   op = typ(o)==t_MAT ? famat_Z_gcd(o,ordp) : ordp;
    2264             : 
    2265        2223 :   q = NULL;
    2266        2223 :   if (T)
    2267             :   { /* we want < g > = Fp^* */
    2268        2223 :     if (!equalii(ord,ordp)) {
    2269        2192 :       q = diviiexact(ord,ordp);
    2270        2192 :       g = FpXQ_pow(g,q,T,p);
    2271             :     }
    2272        2223 :     g = constant_coeff(g);
    2273             :   }
    2274        2223 :   n_q = Fp_log(a,g,op,p);
    2275        2223 :   if (lg(n_q)==1) return gerepileuptoleaf(av, n_q);
    2276        2223 :   if (q) n_q = mulii(q, n_q);
    2277        2223 :   return gerepileuptoint(av, n_q);
    2278             : }
    2279             : 
    2280             : static GEN
    2281      234309 : _FpXQ_pow(void *data, GEN x, GEN n)
    2282             : {
    2283      234309 :   struct _FpXQ *D = (struct _FpXQ*)data;
    2284      234309 :   return FpXQ_pow_Frobenius(x,n, D->aut, D->T, D->p);
    2285             : }
    2286             : 
    2287             : static GEN
    2288        3796 : _FpXQ_rand(void *data)
    2289             : {
    2290        3796 :   pari_sp av=avma;
    2291        3796 :   struct _FpXQ *D = (struct _FpXQ*)data;
    2292             :   GEN z;
    2293             :   do
    2294             :   {
    2295        3796 :     set_avma(av);
    2296        3796 :     z=random_FpX(get_FpX_degree(D->T),get_FpX_var(D->T),D->p);
    2297        3796 :   } while (!signe(z));
    2298        3796 :   return z;
    2299             : }
    2300             : 
    2301             : static GEN
    2302        1645 : _FpXQ_easylog(void *E, GEN a, GEN g, GEN ord)
    2303             : {
    2304        1645 :   struct _FpXQ *s=(struct _FpXQ*) E;
    2305        1645 :   if (degpol(a)) return NULL;
    2306        1558 :   return Fp_FpXQ_log(constant_coeff(a),g,ord,s->T,s->p);
    2307             : }
    2308             : 
    2309             : static const struct bb_group FpXQ_star={_FpXQ_mul,_FpXQ_pow,_FpXQ_rand,hash_GEN,ZX_equal,ZX_equal1,_FpXQ_easylog};
    2310             : 
    2311             : const struct bb_group *
    2312        2223 : get_FpXQ_star(void **E, GEN T, GEN p)
    2313             : {
    2314        2223 :   struct _FpXQ *e = (struct _FpXQ *) stack_malloc(sizeof(struct _FpXQ));
    2315        2223 :   e->T = T; e->p  = p; e->aut =  FpX_Frobenius(T, p);
    2316        2223 :   *E = (void*)e; return &FpXQ_star;
    2317             : }
    2318             : 
    2319             : GEN
    2320          29 : FpXQ_order(GEN a, GEN ord, GEN T, GEN p)
    2321             : {
    2322          29 :   if (lgefint(p)==3)
    2323             :   {
    2324           0 :     pari_sp av=avma;
    2325           0 :     ulong pp = to_Flxq(&a, &T, p);
    2326           0 :     GEN z = Flxq_order(a, ord, T, pp);
    2327           0 :     return gerepileuptoint(av,z);
    2328             :   }
    2329             :   else
    2330             :   {
    2331             :     void *E;
    2332          29 :     const struct bb_group *S = get_FpXQ_star(&E,T,p);
    2333          29 :     return gen_order(a,ord,E,S);
    2334             :   }
    2335             : }
    2336             : 
    2337             : GEN
    2338      293474 : FpXQ_log(GEN a, GEN g, GEN ord, GEN T, GEN p)
    2339             : {
    2340      293474 :   pari_sp av=avma;
    2341      293474 :   if (lgefint(p)==3)
    2342             :   {
    2343      293339 :     if (uel(p,2) == 2)
    2344             :     {
    2345      135464 :       GEN z = F2xq_log(ZX_to_F2x(a), ZX_to_F2x(g), ord,
    2346             :                                      ZX_to_F2x(get_FpX_mod(T)));
    2347      135464 :       return gerepileuptoleaf(av, z);
    2348             :     }
    2349             :     else
    2350             :     {
    2351      157875 :       ulong pp = to_Flxq(&a, &T, p);
    2352      157875 :       GEN z = Flxq_log(a, ZX_to_Flx(g, pp), ord, T, pp);
    2353      157875 :       return gerepileuptoleaf(av, z);
    2354             :     }
    2355             :   }
    2356             :   else
    2357             :   {
    2358             :     void *E;
    2359         135 :     const struct bb_group *S = get_FpXQ_star(&E,T,p);
    2360         135 :     GEN z = gen_PH_log(a,g,ord,E,S);
    2361         107 :     return gerepileuptoleaf(av, z);
    2362             :   }
    2363             : }
    2364             : 
    2365             : GEN
    2366     1191396 : Fq_log(GEN a, GEN g, GEN ord, GEN T, GEN p)
    2367             : {
    2368     1191396 :   if (!T) return Fp_log(a,g,ord,p);
    2369      332678 :   if (typ(g) == t_INT)
    2370             :   {
    2371           0 :     if (typ(a) == t_POL)
    2372             :     {
    2373           0 :       if (degpol(a)) return cgetg(1,t_VEC);
    2374           0 :       a = gel(a,2);
    2375             :     }
    2376           0 :     return Fp_log(a,g,ord,p);
    2377             :   }
    2378      332678 :   return typ(a) == t_INT? Fp_FpXQ_log(a,g,ord,T,p): FpXQ_log(a,g,ord,T,p);
    2379             : }
    2380             : 
    2381             : GEN
    2382       12783 : FpXQ_sqrtn(GEN a, GEN n, GEN T, GEN p, GEN *zeta)
    2383             : {
    2384       12783 :   pari_sp av = avma;
    2385             :   GEN z;
    2386       12783 :   if (!signe(a))
    2387             :   {
    2388        2611 :     long v=varn(a);
    2389        2611 :     if (signe(n) < 0) pari_err_INV("FpXQ_sqrtn",a);
    2390        2604 :     if (zeta) *zeta=pol_1(v);
    2391        2604 :     return pol_0(v);
    2392             :   }
    2393       10172 :   if (lgefint(p)==3)
    2394             :   {
    2395        8113 :     if (uel(p,2) == 2)
    2396             :     {
    2397        2317 :       z = F2xq_sqrtn(ZX_to_F2x(a), n, ZX_to_F2x(get_FpX_mod(T)), zeta);
    2398        2317 :       if (!z) return NULL;
    2399        2317 :       z = F2x_to_ZX(z);
    2400        2317 :       if (!zeta) return gerepileuptoleaf(av, z);
    2401           7 :       *zeta=F2x_to_ZX(*zeta);
    2402             :     } else
    2403             :     {
    2404        5796 :       ulong pp = to_Flxq(&a, &T, p);
    2405        5796 :       z = Flxq_sqrtn(a, n, T, pp, zeta);
    2406        5796 :       if (!z) return NULL;
    2407        3458 :       if (!zeta) return Flx_to_ZX_inplace(gerepileuptoleaf(av, z));
    2408          56 :       z = Flx_to_ZX(z);
    2409          56 :       *zeta=Flx_to_ZX(*zeta);
    2410             :     }
    2411             :   }
    2412             :   else
    2413             :   {
    2414             :     void *E;
    2415        2059 :     const struct bb_group *S = get_FpXQ_star(&E,T,p);
    2416        2059 :     GEN o = subiu(powiu(p,get_FpX_degree(T)),1);
    2417        2059 :     z = gen_Shanks_sqrtn(a,n,o,zeta,E,S);
    2418        4033 :     if (!z) return NULL;
    2419        2031 :     if (!zeta) return gerepileupto(av, z);
    2420             :   }
    2421         120 :   return gc_all(av, 2, &z,zeta);
    2422             : }
    2423             : 
    2424             : GEN
    2425       12163 : FpXQ_sqrt(GEN a, GEN T, GEN p)
    2426             : {
    2427       12163 :   return FpXQ_sqrtn(a, gen_2, T, p, NULL);
    2428             : }
    2429             : 
    2430             : GEN
    2431      360471 : FpXQ_norm(GEN x, GEN TB, GEN p)
    2432             : {
    2433      360471 :   pari_sp av = avma;
    2434      360471 :   GEN T = get_FpX_mod(TB);
    2435      360471 :   GEN y = FpX_resultant(T, x, p);
    2436      360471 :   GEN L = leading_coeff(T);
    2437      360471 :   if (gequal1(L) || signe(x)==0) return y;
    2438           0 :   return gerepileupto(av, Fp_div(y, Fp_pows(L, degpol(x), p), p));
    2439             : }
    2440             : 
    2441             : GEN
    2442       21081 : FpXQ_trace(GEN x, GEN TB, GEN p)
    2443             : {
    2444       21081 :   pari_sp av = avma;
    2445       21081 :   GEN T = get_FpX_mod(TB);
    2446       21081 :   GEN dT = FpX_deriv(T,p);
    2447       21081 :   long n = degpol(dT);
    2448       21081 :   GEN z = FpXQ_mul(x, dT, TB, p);
    2449       21081 :   if (degpol(z)<n) return gc_const(av, gen_0);
    2450       19898 :   return gerepileuptoint(av, Fp_div(gel(z,2+n), gel(T,3+n),p));
    2451             : }
    2452             : 
    2453             : GEN
    2454           1 : FpXQ_charpoly(GEN x, GEN T, GEN p)
    2455             : {
    2456           1 :   pari_sp ltop=avma;
    2457           1 :   long vT, v = fetch_var();
    2458             :   GEN R;
    2459           1 :   T = leafcopy(get_FpX_mod(T));
    2460           1 :   vT = varn(T); setvarn(T, v);
    2461           1 :   x = leafcopy(x); setvarn(x, v);
    2462           1 :   R = FpX_FpXY_resultant(T, deg1pol_shallow(gen_1,FpX_neg(x,p),vT),p);
    2463           1 :   (void)delete_var(); return gerepileupto(ltop,R);
    2464             : }
    2465             : 
    2466             : /* Computing minimal polynomial :                         */
    2467             : /* cf Shoup 'Efficient Computation of Minimal Polynomials */
    2468             : /*          in Algebraic Extensions of Finite Fields'     */
    2469             : 
    2470             : /* Let v a linear form, return the linear form z->v(tau*z)
    2471             :    that is, v*(M_tau) */
    2472             : 
    2473             : static GEN
    2474         870 : FpXQ_transmul_init(GEN tau, GEN T, GEN p)
    2475             : {
    2476             :   GEN bht;
    2477         870 :   GEN h, Tp = get_FpX_red(T, &h);
    2478         870 :   long n = degpol(Tp), vT = varn(Tp);
    2479         870 :   GEN ft = FpX_recipspec(Tp+2, n+1, n+1);
    2480         870 :   GEN bt = FpX_recipspec(tau+2, lgpol(tau), n);
    2481         870 :   setvarn(ft, vT); setvarn(bt, vT);
    2482         870 :   if (h)
    2483          20 :     bht = FpXn_mul(bt, h, n-1, p);
    2484             :   else
    2485             :   {
    2486         850 :     GEN bh = FpX_div(FpX_shift(tau, n-1), T, p);
    2487         850 :     bht = FpX_recipspec(bh+2, lgpol(bh), n-1);
    2488         850 :     setvarn(bht, vT);
    2489             :   }
    2490         870 :   return mkvec3(bt, bht, ft);
    2491             : }
    2492             : 
    2493             : static GEN
    2494        2398 : FpXQ_transmul(GEN tau, GEN a, long n, GEN p)
    2495             : {
    2496        2398 :   pari_sp ltop = avma;
    2497             :   GEN t1, t2, t3, vec;
    2498        2398 :   GEN bt = gel(tau, 1), bht = gel(tau, 2), ft = gel(tau, 3);
    2499        2398 :   if (signe(a)==0) return pol_0(varn(a));
    2500        2363 :   t2 = FpX_shift(FpX_mul(bt, a, p),1-n);
    2501        2363 :   if (signe(bht)==0) return gerepilecopy(ltop, t2);
    2502        1907 :   t1 = FpX_shift(FpX_mul(ft, a, p),-n);
    2503        1907 :   t3 = FpXn_mul(t1, bht, n-1, p);
    2504        1907 :   vec = FpX_sub(t2, FpX_shift(t3, 1), p);
    2505        1907 :   return gerepileupto(ltop, vec);
    2506             : }
    2507             : 
    2508             : GEN
    2509       13217 : FpXQ_minpoly(GEN x, GEN T, GEN p)
    2510             : {
    2511       13217 :   pari_sp ltop = avma;
    2512             :   long vT, n;
    2513             :   GEN v_x, g, tau;
    2514       13217 :   if (lgefint(p)==3)
    2515             :   {
    2516       12782 :     ulong pp = to_Flxq(&x, &T, p);
    2517       12782 :     GEN g = Flxq_minpoly(x, T, pp);
    2518       12782 :     return gerepileupto(ltop, Flx_to_ZX(g));
    2519             :   }
    2520         435 :   vT = get_FpX_var(T);
    2521         435 :   n = get_FpX_degree(T);
    2522         435 :   g = pol_1(vT);
    2523         435 :   tau = pol_1(vT);
    2524         435 :   T = FpX_get_red(T, p);
    2525         435 :   x = FpXQ_red(x, T, p);
    2526         435 :   v_x = FpXQ_powers(x, usqrt(2*n), T, p);
    2527         870 :   while(signe(tau) != 0)
    2528             :   {
    2529             :     long i, j, m, k1;
    2530             :     GEN M, v, tr;
    2531             :     GEN g_prime, c;
    2532         435 :     if (degpol(g) == n) { tau = pol_1(vT); g = pol_1(vT); }
    2533         435 :     v = random_FpX(n, vT, p);
    2534         435 :     tr = FpXQ_transmul_init(tau, T, p);
    2535         435 :     v = FpXQ_transmul(tr, v, n, p);
    2536         435 :     m = 2*(n-degpol(g));
    2537         435 :     k1 = usqrt(m);
    2538         435 :     tr = FpXQ_transmul_init(gel(v_x,k1+1), T, p);
    2539         435 :     c = cgetg(m+2,t_POL);
    2540         435 :     c[1] = evalsigne(1)|evalvarn(vT);
    2541        2398 :     for (i=0; i<m; i+=k1)
    2542             :     {
    2543        1963 :       long mj = minss(m-i, k1);
    2544       10371 :       for (j=0; j<mj; j++)
    2545        8408 :         gel(c,m+1-(i+j)) = FpX_dotproduct(v, gel(v_x,j+1), p);
    2546        1963 :       v = FpXQ_transmul(tr, v, n, p);
    2547             :     }
    2548         435 :     c = FpX_renormalize(c, m+2);
    2549             :     /* now c contains <v,x^i> , i = 0..m-1  */
    2550         435 :     M = FpX_halfgcd(pol_xn(m, vT), c, p);
    2551         435 :     g_prime = gmael(M, 2, 2);
    2552         435 :     if (degpol(g_prime) < 1) continue;
    2553         435 :     g = FpX_mul(g, g_prime, p);
    2554         435 :     tau = FpXQ_mul(tau, FpX_FpXQV_eval(g_prime, v_x, T, p), T, p);
    2555             :   }
    2556         435 :   g = FpX_normalize(g,p);
    2557         435 :   return gerepilecopy(ltop,g);
    2558             : }
    2559             : 
    2560             : GEN
    2561           8 : FpXQ_conjvec(GEN x, GEN T, GEN p)
    2562             : {
    2563           8 :   pari_sp av=avma;
    2564             :   long i;
    2565           8 :   long n = get_FpX_degree(T), v = varn(x);
    2566           8 :   GEN M = FpX_matFrobenius(T, p);
    2567           8 :   GEN z = cgetg(n+1,t_COL);
    2568           8 :   gel(z,1) = RgX_to_RgC(x,n);
    2569          17 :   for (i=2; i<=n; i++) gel(z,i) = FpM_FpC_mul(M,gel(z,i-1),p);
    2570           8 :   gel(z,1) = x;
    2571          17 :   for (i=2; i<=n; i++) gel(z,i) = RgV_to_RgX(gel(z,i),v);
    2572           8 :   return gerepilecopy(av,z);
    2573             : }
    2574             : 
    2575             : /* p prime, p_1 = p-1, q = p^deg T, Lp = cofactors of some prime divisors
    2576             :  * l_p of p-1, Lq = cofactors of some prime divisors l_q of q-1, return a
    2577             :  * g in Fq such that
    2578             :  * - Ng generates all l_p-Sylows of Fp^*
    2579             :  * - g generates all l_q-Sylows of Fq^* */
    2580             : static GEN
    2581       83242 : gener_FpXQ_i(GEN T, GEN p, GEN p_1, GEN Lp, GEN Lq)
    2582             : {
    2583             :   pari_sp av;
    2584       83242 :   long vT = varn(T), f = degpol(T), l = lg(Lq);
    2585       83242 :   GEN F = FpX_Frobenius(T, p);
    2586       83244 :   int p_is_2 = is_pm1(p_1);
    2587      168831 :   for (av = avma;; set_avma(av))
    2588       85587 :   {
    2589      168831 :     GEN t, g = random_FpX(f, vT, p);
    2590             :     long i;
    2591      168831 :     if (degpol(g) < 1) continue;
    2592      108510 :     if (p_is_2)
    2593       55812 :       t = g;
    2594             :     else
    2595             :     {
    2596       52698 :       t = FpX_resultant(T, g, p); /* Ng = g^((q-1)/(p-1)), assuming T monic */
    2597       52698 :       if (kronecker(t, p) == 1) continue;
    2598       31345 :       if (lg(Lp) > 1 && !is_gener_Fp(t, p, p_1, Lp)) continue;
    2599       29932 :       t = FpXQ_pow(g, shifti(p_1,-1), T, p);
    2600             :     }
    2601       98506 :     for (i = 1; i < l; i++)
    2602             :     {
    2603       15261 :       GEN a = FpXQ_pow_Frobenius(t, gel(Lq,i), F, T, p);
    2604       15261 :       if (!degpol(a) && equalii(gel(a,2), p_1)) break;
    2605             :     }
    2606       85744 :     if (i == l) return g;
    2607             :   }
    2608             : }
    2609             : 
    2610             : GEN
    2611        6939 : gener_FpXQ(GEN T, GEN p, GEN *po)
    2612             : {
    2613        6939 :   long i, j, f = get_FpX_degree(T);
    2614             :   GEN g, Lp, Lq, p_1, q_1, N, o;
    2615        6939 :   pari_sp av = avma;
    2616             : 
    2617        6939 :   p_1 = subiu(p,1);
    2618        6939 :   if (f == 1) {
    2619             :     GEN Lp, fa;
    2620           7 :     o = p_1;
    2621           7 :     fa = Z_factor(o);
    2622           7 :     Lp = gel(fa,1);
    2623           7 :     Lp = vecslice(Lp, 2, lg(Lp)-1); /* remove 2 for efficiency */
    2624             : 
    2625           7 :     g = cgetg(3, t_POL);
    2626           7 :     g[1] = evalsigne(1) | evalvarn(get_FpX_var(T));
    2627           7 :     gel(g,2) = pgener_Fp_local(p, Lp);
    2628           7 :     if (po) *po = mkvec2(o, fa);
    2629           7 :     return g;
    2630             :   }
    2631        6932 :   if (lgefint(p) == 3)
    2632             :   {
    2633        6895 :     ulong pp = to_Flxq(NULL, &T, p);
    2634        6895 :     g = gener_Flxq(T, pp, po);
    2635        6895 :     if (!po) return Flx_to_ZX_inplace(gerepileuptoleaf(av, g));
    2636        6895 :     g = Flx_to_ZX(g); return gc_all(av, 2, &g, po);
    2637             :   }
    2638             :   /* p now odd */
    2639          37 :   q_1 = subiu(powiu(p,f), 1);
    2640          37 :   N = diviiexact(q_1, p_1);
    2641          37 :   Lp = odd_prime_divisors(p_1);
    2642         168 :   for (i=lg(Lp)-1; i; i--) gel(Lp,i) = diviiexact(p_1, gel(Lp,i));
    2643          37 :   o = factor_pn_1(p,f);
    2644          37 :   Lq = leafcopy( gel(o, 1) );
    2645         353 :   for (i = j = 1; i < lg(Lq); i++)
    2646             :   {
    2647         316 :     if (dvdii(p_1, gel(Lq,i))) continue;
    2648         148 :     gel(Lq,j++) = diviiexact(N, gel(Lq,i));
    2649             :   }
    2650          37 :   setlg(Lq, j);
    2651          37 :   g = gener_FpXQ_i(get_FpX_mod(T), p, p_1, Lp, Lq);
    2652          37 :   if (!po) g = gerepilecopy(av, g);
    2653             :   else {
    2654          21 :     *po = mkvec2(q_1, o);
    2655          21 :     gerepileall(av, 2, &g, po);
    2656             :   }
    2657          37 :   return g;
    2658             : }
    2659             : 
    2660             : GEN
    2661       83207 : gener_FpXQ_local(GEN T, GEN p, GEN L)
    2662             : {
    2663       83207 :   GEN Lp, Lq, p_1 = subiu(p,1), q_1, N, Q;
    2664       83202 :   long f, i, ip, iq, l = lg(L);
    2665       83202 :   T = get_FpX_mod(T);
    2666       83202 :   f = degpol(T);
    2667       83204 :   q_1 = subiu(powiu(p,f), 1);
    2668       83201 :   N = diviiexact(q_1, p_1);
    2669             : 
    2670       83198 :   Q = is_pm1(p_1)? gen_1: shifti(p_1,-1);
    2671       83202 :   Lp = cgetg(l, t_VEC); ip = 1;
    2672       83203 :   Lq = cgetg(l, t_VEC); iq = 1;
    2673       98650 :   for (i=1; i < l; i++)
    2674             :   {
    2675       15448 :     GEN a, b, ell = gel(L,i);
    2676       15448 :     if (absequaliu(ell,2)) continue;
    2677       15167 :     a = dvmdii(Q, ell, &b);
    2678       15167 :     if (b == gen_0)
    2679        2555 :       gel(Lp,ip++) = a;
    2680             :     else
    2681       12612 :       gel(Lq,iq++) = diviiexact(N,ell);
    2682             :   }
    2683       83202 :   setlg(Lp, ip);
    2684       83202 :   setlg(Lq, iq);
    2685       83201 :   return gener_FpXQ_i(T, p, p_1, Lp, Lq);
    2686             : }
    2687             : 
    2688             : /***********************************************************************/
    2689             : /**                                                                   **/
    2690             : /**                              FpXn                                 **/
    2691             : /**                                                                   **/
    2692             : /***********************************************************************/
    2693             : 
    2694             : INLINE GEN
    2695       64893 : FpXn_red(GEN a, long n)
    2696       64893 : { return RgXn_red_shallow(a, n); }
    2697             : 
    2698             : GEN
    2699     2447412 : FpXn_mul(GEN a, GEN b, long n, GEN p)
    2700             : {
    2701     2447412 :   return FpX_red(ZXn_mul(a, b, n), p);
    2702             : }
    2703             : 
    2704             : GEN
    2705           0 : FpXn_sqr(GEN a, long n, GEN p)
    2706             : {
    2707           0 :   return FpX_red(ZXn_sqr(a, n), p);
    2708             : }
    2709             : 
    2710             : /* (f*g) \/ x^n */
    2711             : static GEN
    2712       58358 : FpX_mulhigh_i(GEN f, GEN g, long n, GEN p)
    2713             : {
    2714       58358 :   return FpX_shift(FpX_mul(f,g, p),-n);
    2715             : }
    2716             : 
    2717             : static GEN
    2718       36681 : FpXn_mulhigh(GEN f, GEN g, long n2, long n, GEN p)
    2719             : {
    2720       36681 :   GEN F = RgX_blocks(f, n2, 2), fl = gel(F,1), fh = gel(F,2);
    2721       36681 :   return FpX_add(FpX_mulhigh_i(fl, g, n2, p), FpXn_mul(fh, g, n - n2, p), p);
    2722             : }
    2723             : 
    2724             : GEN
    2725        6503 : FpXn_div(GEN g, GEN f, long e, GEN p)
    2726             : {
    2727        6503 :   pari_sp av = avma, av2;
    2728             :   ulong mask;
    2729             :   GEN W, a;
    2730        6503 :   long v = varn(f), n = 1;
    2731             : 
    2732        6503 :   if (!signe(f)) pari_err_INV("FpXn_inv",f);
    2733        6503 :   a = Fp_inv(gel(f,2), p);
    2734        6503 :   if (e == 1 && !g) return scalarpol(a, v);
    2735        6503 :   else if (e == 2 && !g)
    2736             :   {
    2737             :     GEN b;
    2738           0 :     if (degpol(f) <= 0) return scalarpol(a, v);
    2739           0 :     b = Fp_neg(gel(f,3),p);
    2740           0 :     if (signe(b)==0) return scalarpol(a, v);
    2741           0 :     if (!is_pm1(a)) b = Fp_mul(b, Fp_sqr(a, p), p);
    2742           0 :     W = deg1pol_shallow(b, a, v);
    2743           0 :     return gerepilecopy(av, W);
    2744             :   }
    2745        6503 :   W = scalarpol_shallow(Fp_inv(gel(f,2), p),v);
    2746        6503 :   mask = quadratic_prec_mask(e);
    2747        6503 :   av2 = avma;
    2748       28042 :   for (;mask>1;)
    2749             :   {
    2750             :     GEN u, fr;
    2751       21539 :     long n2 = n;
    2752       21539 :     n<<=1; if (mask & 1) n--;
    2753       21539 :     mask >>= 1;
    2754       21539 :     fr = FpXn_red(f, n);
    2755       21539 :     if (mask>1 || !g)
    2756             :     {
    2757       21539 :       u = FpXn_mul(W, FpXn_mulhigh(fr, W, n2, n, p), n-n2, p);
    2758       21539 :       W = FpX_sub(W, FpX_shift(u, n2), p);
    2759             :     }
    2760             :     else
    2761             :     {
    2762           0 :       GEN y = FpXn_mul(g, W, n, p), yt =  FpXn_red(y, n-n2);
    2763           0 :       u = FpXn_mul(yt, FpXn_mulhigh(fr,  W, n2, n, p), n-n2, p);
    2764           0 :       W = FpX_sub(y, FpX_shift(u, n2), p);
    2765             :     }
    2766       21539 :     if (gc_needed(av2,2))
    2767             :     {
    2768           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"FpXn_inv, e = %ld", n);
    2769           0 :       W = gerepileupto(av2, W);
    2770             :     }
    2771             :   }
    2772        6503 :   return gerepileupto(av, W);
    2773             : }
    2774             : 
    2775             : GEN
    2776        6503 : FpXn_inv(GEN f, long e, GEN p)
    2777        6503 : { return FpXn_div(NULL, f, e, p); }
    2778             : 
    2779             : GEN
    2780        6535 : FpXn_expint(GEN h, long e, GEN p)
    2781             : {
    2782        6535 :   pari_sp av = avma, av2;
    2783        6535 :   long v = varn(h), n=1;
    2784        6535 :   GEN f = pol_1(v), g = pol_1(v);
    2785        6535 :   ulong mask = quadratic_prec_mask(e);
    2786        6535 :   av2 = avma;
    2787       21677 :   for (;mask>1;)
    2788             :   {
    2789             :     GEN u, w;
    2790       21677 :     long n2 = n;
    2791       21677 :     n<<=1; if (mask & 1) n--;
    2792       21677 :     mask >>= 1;
    2793       21677 :     u = FpXn_mul(g, FpX_mulhigh_i(f, FpXn_red(h, n2-1), n2-1, p), n-n2, p);
    2794       21677 :     u = FpX_add(u, FpX_shift(FpXn_red(h, n-1), 1-n2), p);
    2795       21677 :     w = FpXn_mul(f, FpX_integXn(u, n2-1, p), n-n2, p);
    2796       21677 :     f = FpX_add(f, FpX_shift(w, n2), p);
    2797       21677 :     if (mask<=1) break;
    2798       15142 :     u = FpXn_mul(g, FpXn_mulhigh(f, g, n2, n, p), n-n2, p);
    2799       15142 :     g = FpX_sub(g, FpX_shift(u, n2), p);
    2800       15142 :     if (gc_needed(av2,2))
    2801             :     {
    2802           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"FpXn_exp, e = %ld", n);
    2803           0 :       gerepileall(av2, 2, &f, &g);
    2804             :     }
    2805             :   }
    2806        6535 :   return gerepileupto(av, f);
    2807             : }
    2808             : 
    2809             : GEN
    2810           0 : FpXn_exp(GEN h, long e, GEN p)
    2811             : {
    2812           0 :   if (signe(h)==0 || degpol(h)<1 || !gequal0(gel(h,2)))
    2813           0 :     pari_err_DOMAIN("FpXn_exp","valuation", "<", gen_1, h);
    2814           0 :   return FpXn_expint(FpX_deriv(h, p), e, p);
    2815             : }

Generated by: LCOV version 1.13