/* Copyright (C) 2007  The PARI group.

This file is part of the PARI/GP package.

PARI/GP is free software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the Free Software
Foundation. It is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY WHATSOEVER.

Check the License for details. You should have received a copy of it, along
with the package; see the file 'COPYING'. If not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */

#include "pari.h"
#include "paripriv.h"

/*******************************************************************/
/*                                                                 */
/*                                ZX                               */
/*                                                                 */
/*******************************************************************/
void
RgX_check_QX(GEN x, const char *s)
{ if (!RgX_is_QX(x)) pari_err_TYPE(stack_strcat(s," [not in Q[X]]"), x); }
void
RgX_check_ZX(GEN x, const char *s)
{ if (!RgX_is_ZX(x)) pari_err_TYPE(stack_strcat(s," [not in Z[X]]"), x); }
pari_long
ZX_max_lg(GEN x)
{
  pari_long i, prec = 0, lx = lg(x);

  for (i=2; i<lx; i++) { pari_long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
  return prec;
}

GEN
ZX_add(GEN x, GEN y)
{
  pari_long lx,ly,i;
  GEN z;
  lx = lg(x); ly = lg(y); if (lx < ly) swapspec(x,y, lx,ly);
  z = cgetg(lx,t_POL); z[1] = x[1];
  for (i=2; i<ly; i++) gel(z,i) = addii(gel(x,i),gel(y,i));
  for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
  if (lx == ly) z = ZX_renormalize(z, lx);
  if (!lgpol(z)) { avma = (pari_sp)(z + lx); return pol_0(varn(x)); }
  return z;
}

GEN
ZX_sub(GEN x,GEN y)
{
  pari_long i, lx = lg(x), ly = lg(y);
  GEN z;
  if (lx >= ly)
  {
    z = cgetg(lx,t_POL); z[1] = x[1];
    for (i=2; i<ly; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
    if (lx == ly)
    {
      z = ZX_renormalize(z, lx);
      if (!lgpol(z)) { avma = (pari_sp)(z + lx); z = pol_0(varn(x)); }
    }
    else
      for (   ; i<lx; i++) gel(z,i) = icopy(gel(x,i));
  }
  else
  {
    z = cgetg(ly,t_POL); z[1] = y[1];
    for (i=2; i<lx; i++) gel(z,i) = subii(gel(x,i),gel(y,i));
    for (   ; i<ly; i++) gel(z,i) = negi(gel(y,i));
  }
  return z;
}

GEN
ZX_neg(GEN x)
{
  pari_long i, l = lg(x);
  GEN y = cgetg(l,t_POL);
  y[1] = x[1]; for(i=2; i<l; i++) gel(y,i) = negi(gel(x,i));
  return y;
}
GEN
ZX_copy(GEN x)
{
  pari_long i, l = lg(x);
  GEN y = cgetg(l, t_POL);
  y[1] = x[1];
  for (i=2; i<l; i++)
  {
    GEN c = gel(x,i);
    gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
  }
  return y;
}

GEN
scalar_ZX(GEN x, pari_long v)
{
  GEN z;
  if (!signe(x)) return pol_0(v);
  z = cgetg(3, t_POL);
  z[1] = evalsigne(1) | evalvarn(v);
  gel(z,2) = icopy(x); return z;
}

GEN
scalar_ZX_shallow(GEN x, pari_long v)
{
  GEN z;
  if (!signe(x)) return pol_0(v);
  z = cgetg(3, t_POL);
  z[1] = evalsigne(1) | evalvarn(v);
  gel(z,2) = x; return z;
}

GEN
ZX_Z_add(GEN y, GEN x)
{
  pari_long lz, i;
  GEN z = cgetg_copy(y, &lz);
  if (lz == 2) { avma = (pari_sp)(z + 2); return scalar_ZX(x,varn(y)); }
  z[1] = y[1];
  gel(z,2) = addii(gel(y,2),x);
  for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
  if (lz==3) z = ZX_renormalize(z,lz);
  return z;
}
GEN
ZX_Z_add_shallow(GEN y, GEN x)
{
  pari_long lz, i;
  GEN z = cgetg_copy(y, &lz);
  if (lz == 2) { avma = (pari_sp)(z + 2); return scalar_ZX_shallow(x,varn(y)); }
  z[1] = y[1];
  gel(z,2) = addii(gel(y,2),x);
  for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
  if (lz==3) z = ZX_renormalize(z,lz);
  return z;
}

GEN
ZX_Z_sub(GEN y, GEN x)
{
  pari_long lz, i;
  GEN z = cgetg_copy(y, &lz);
  if (lz == 2)
  { /* scalarpol(negi(x), v) */
    pari_long v = varn(y);
    avma = (pari_sp)(z + 2);
    if (!signe(x)) return pol_0(v);
    z = cgetg(3,t_POL);
    z[1] = evalvarn(v) | evalsigne(1);
    gel(z,2) = negi(x); return z;
  }
  z[1] = y[1];
  gel(z,2) = subii(gel(y,2),x);
  for(i=3; i<lz; i++) gel(z,i) = icopy(gel(y,i));
  if (lz==3) z = ZX_renormalize(z,lz);
  return z;
}

GEN
Z_ZX_sub(GEN x, GEN y)
{
  pari_long lz, i;
  GEN z = cgetg_copy(y, &lz);
  if (lz == 2) { avma = (pari_sp)(z + 2); return scalar_ZX(x,varn(y)); }
  z[1] = y[1];
  gel(z,2) = subii(x, gel(y,2));
  for(i=3; i<lz; i++) gel(z,i) = negi(gel(y,i));
  if (lz==3) z = ZX_renormalize(z,lz);
  return z;
}

GEN
ZX_Z_divexact(GEN y,GEN x)
{
  pari_long i, l = lg(y);
  GEN z = cgetg(l,t_POL); z[1] = y[1];
  for(i=2; i<l; i++) gel(z,i) = diviiexact(gel(y,i),x);
  return z;
}

GEN
ZX_Z_mul(GEN y,GEN x)
{
  GEN z;
  pari_long i, l;
  if (!signe(x)) return pol_0(varn(y));
  l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
  for(i=2; i<l; i++) gel(z,i) = mulii(gel(y,i),x);
  return z;
}

GEN
ZX_mulu(GEN y, ulong x)
{
  GEN z;
  pari_long i, l;
  if (!x) return pol_0(varn(y));
  l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
  for(i=2; i<l; i++) gel(z,i) = mului(x,gel(y,i));
  return z;
}

GEN
ZX_shifti(GEN y, pari_long n)
{
  GEN z;
  pari_long i, l;
  l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
  for(i=2; i<l; i++) gel(z,i) = shifti(gel(y,i),n);
  return ZX_renormalize(z,l);
}

GEN
ZX_remi2n(GEN y, pari_long n)
{
  GEN z;
  pari_long i, l;
  l = lg(y); z = cgetg(l,t_POL); z[1] = y[1];
  for(i=2; i<l; i++) gel(z,i) = remi2n(gel(y,i),n);
  return ZX_renormalize(z,l);
}

GEN
ZXT_remi2n(GEN z, pari_long n)
{
  if (typ(z) == t_POL)
    return ZX_remi2n(z, n);
  else
  {
    pari_long i,l = lg(z);
    GEN x = cgetg(l, t_VEC);
    for (i=1; i<l; i++) gel(x,i) = ZXT_remi2n(gel(z,i), n);
    return x;
  }
}

GEN
zx_to_ZX(GEN z)
{
  pari_long i, l = lg(z);
  GEN x = cgetg(l,t_POL);
  for (i=2; i<l; i++) gel(x,i) = stoi(z[i]);
  x[1] = evalsigne(l-2!=0)| z[1]; return x;
}

GEN
ZX_deriv(GEN x)
{
  pari_long i,lx = lg(x)-1;
  GEN y;

  if (lx<3) return pol_0(varn(x));
  y = cgetg(lx,t_POL);
  for (i=2; i<lx ; i++) gel(y,i) = mului(i-1,gel(x,i+1));
  y[1] = x[1]; return y;
}

int
ZX_equal(GEN V, GEN W)
{
  pari_long i, l = lg(V);
  if (lg(W) != l) return 0;
  for (i = 2; i < l; i++)
    if (!equalii(gel(V,i), gel(W,i))) return 0;
  return 1;
}

static pari_long
ZX_valspec(GEN x, pari_long nx)
{
  pari_long vx;
  for (vx = 0; vx<nx ; vx++)
    if (signe(gel(x,vx))) break;
  return vx;
}

pari_long
ZX_val(GEN x)
{
  pari_long vx;
  if (!signe(x)) return LONG_MAX;
  for (vx = 0;; vx++)
    if (signe(gel(x,2+vx))) break;
  return vx;
}
pari_long
ZX_valrem(GEN x, GEN *Z)
{
  pari_long vx;
  if (!signe(x)) { *Z = pol_0(varn(x)); return LONG_MAX; }
  for (vx = 0;; vx++)
    if (signe(gel(x,2+vx))) break;
  *Z = RgX_shift_shallow(x, -vx);
  return vx;
}

/* Return h^deg(P) P(x / h), not memory clean. h integer, P ZX */
GEN
ZX_rescale(GEN P, GEN h)
{
  pari_long l = lg(P);
  GEN Q = cgetg(l,t_POL);
  if (l != 2)
  {
    pari_long i = l-1;
    GEN hi = h;
    gel(Q,i) = gel(P,i);
    if (l != 3) { i--; gel(Q,i) = mulii(gel(P,i), h); }
    for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
  }
  Q[1] = P[1]; return Q;
}
/* Return h^(deg(P)-1) P(x / h), P!=0, h=lt(P), memory unclean; monic result */
GEN
ZX_rescale_lt(GEN P)
{
  pari_long l = lg(P);
  GEN Q = cgetg(l,t_POL);
  gel(Q,l-1) = gen_1;
  if (l != 3)
  {
    pari_long i = l-1;
    GEN h = gel(P,i), hi = h;
    i--; gel(Q,i) = gel(P,i);
    if (l != 4) { i--; gel(Q,i) = mulii(gel(P,i), h); }
    for (i--; i>=2; i--) { hi = mulii(hi,h); gel(Q,i) = mulii(gel(P,i), hi); }
  }
  Q[1] = P[1]; return Q;
}


/*Eval x in 2^(k*BIL) in linear time*/
static GEN
ZX_eval2BILspec(GEN x, pari_long k, pari_long nx)
{
  pari_long i,j, lz = k*nx, ki;
  GEN pz = cgetipos(2+lz);
  GEN nz = cgetipos(2+lz);
  for(i=0; i < lz; i++)
  {
    *int_W(pz,i) = 0ULL;
    *int_W(nz,i) = 0ULL;
  }
  for(i=0, ki=0; i<nx; i++, ki+=k)
  {
    GEN c = gel(x,i);
    pari_long lc = lgefint(c)-2;
    if (signe(c)==0) continue;
    if (signe(c) > 0)
      for (j=0; j<lc; j++) *int_W(pz,j+ki) = *int_W(c,j);
    else
      for (j=0; j<lc; j++) *int_W(nz,j+ki) = *int_W(c,j);
  }
  pz = int_normalize(pz,0);
  nz = int_normalize(nz,0); return subii(pz,nz);
}

static pari_long
ZX_expispec(GEN x, pari_long nx)
{
  pari_long i, m = 0;
  for(i = 0; i < nx; i++)
  {
    pari_long e = expi(gel(x,i));
    if (e > m) m = e;
  }
  return m;
}

static GEN
Z_mod2BIL_ZX(GEN x, pari_long bs, pari_long d, pari_long vx)
{
  pari_long i, offset, lm = lgefint(x)-2, l = d+vx+3, sx = signe(x);
  GEN s1 = int2n(bs*BITS_IN_LONG), pol = cgetg(l, t_POL);
  int carry = 0;

  for (i=0; i<vx; i++) gel(pol,i+2) = gen_0;
  for (offset=0; i <= d+vx; i++, offset += bs)
  {
    pari_sp av = avma;
    pari_long lz = minss(bs, lm-offset);
    GEN z = adduispec_offset(carry, x, offset, lz);
    if (lgefint(z) == 3+bs) { carry = 1; z = gen_0;}
    else
    {
      carry = (lgefint(z) == 2+bs && (HIGHBIT & *int_W(z,bs-1)));
      if (carry)
        z = gerepileuptoint(av, (sx==-1)? subii(s1,z): subii(z,s1));
      else if (sx==-1) togglesign(z);
    }
    gel(pol,i+2) = z;
  }
  return ZX_renormalize(pol,l);
}

static GEN
ZX_sqrspec_sqri(GEN x, pari_long nx, pari_long ex, pari_long v)
{
  pari_long e = 2*ex + expu(nx) + 3;
  pari_long N = divsBIL(e)+1;
  GEN  z = sqri(ZX_eval2BILspec(x,N,nx));
  return Z_mod2BIL_ZX(z, N, nx*2-2, v);
}

static GEN
ZX_mulspec_mulii(GEN x, GEN y, pari_long nx, pari_long ny, pari_long ex, pari_long ey, pari_long v)
{
  pari_long e = ex + ey + expu(minss(nx,ny)) + 3;
  pari_long N = divsBIL(e)+1;
  GEN  z = mulii(ZX_eval2BILspec(x,N,nx), ZX_eval2BILspec(y,N,ny));
  return Z_mod2BIL_ZX(z, N, nx+ny-2, v);
}

INLINE GEN
ZX_sqrspec_basecase_limb(GEN x, pari_long a, pari_long i)
{
  pari_sp av = avma;
  GEN s = gen_0;
  pari_long j, l = (i+1)>>1;
  for (j=a; j<l; j++)
  {
    GEN xj = gel(x,j), xx = gel(x,i-j);
    if (signe(xj) && signe(xx))
      s = addii(s, mulii(xj, xx));
  }
  s = shifti(s,1);
  if ((i&1) == 0)
  {
    GEN t = gel(x, i>>1);
    if (signe(t))
      s = addii(s, sqri(t));
  }
  return gerepileuptoint(av,s);
}

static GEN
ZX_sqrspec_basecase(GEN x, pari_long nx, pari_long v)
{
  pari_long i, lz, nz;
  GEN z;

  lz = (nx << 1) + 1; nz = lz-2;
  lz += v;
  z = cgetg(lz,t_POL); z[1] = evalsigne(1); z += 2;
  for (i=0; i<v; i++) gel(z++, 0) = gen_0;
  for (i=0; i<nx; i++)
    gel(z,i) = ZX_sqrspec_basecase_limb(x, 0, i);
  for (  ; i<nz; i++) gel(z,i) = ZX_sqrspec_basecase_limb(x, i-nx+1, i);
  z -= v+2; return z;
}

static GEN
Z_sqrshiftspec_ZX(GEN x, pari_long vx)
{
  pari_long i, nz = 2*vx+1;
  GEN z = cgetg(2+nz, t_POL);
  z[1] = evalsigne(1);
  for(i=2;i<nz+1;i++) gel(z,i) = gen_0;
  gel(z,nz+1) = sqri(x);
  return z;
}

static GEN
Z_ZX_mulshiftspec(GEN x, GEN y, pari_long ny, pari_long vz)
{
  pari_long i, nz = vz+ny;
  GEN z = cgetg(2+nz, t_POL);
  z[1] = evalsigne(1);
  for (i=0; i<vz; i++)   gel(z,i+2)    = gen_0;
  for (i=0; i<ny; i++) gel(z,i+vz+2) = mulii(x, gel(y,i));
  return z;
}

GEN
ZX_sqrspec(GEN x, pari_long nx)
{
#ifdef PARI_KERNEL_GMP
  const pari_long low[]={ 17, 32, 96, 112, 160, 128, 128, 160, 160, 160, 160, 160, 176, 192, 192, 192, 192, 192, 224, 224, 224, 240, 240, 240, 272, 288, 288, 240, 288, 304, 304, 304, 304, 304, 304, 352, 352, 368, 352, 352, 352, 368, 368, 432, 432, 496, 432, 496, 496};
  const pari_long high[]={ 102860, 70254, 52783, 27086, 24623, 18500, 15289, 13899, 12635, 11487, 10442, 9493, 8630, 7845, 7132, 7132, 6484, 6484, 5894, 5894, 4428, 4428, 3660, 4428, 3660, 3660, 2749, 2499, 2272, 2066, 1282, 1282, 1166, 1166, 1166, 1166, 1166, 1166, 1166, 963, 963, 724, 658, 658, 658, 528, 528, 528, 528};
#else
  const pari_long low[]={ 17, 17, 32, 32, 96, 96, 96, 96, 96, 96, 96, 96, 96, 96, 112, 112, 128, 112, 112, 112, 112, 112, 128, 128, 160, 160, 112, 128, 128, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 160, 176, 160, 160, 176, 160, 160, 176, 176, 208, 176, 176, 176, 192, 192, 176, 176, 224, 176, 224, 224, 176, 224, 224, 224, 176, 176, 176, 176, 176, 176, 176, 176, 224, 176, 176, 224, 224, 224, 224, 224, 224, 224, 240, 288, 240, 288, 288, 240, 288, 288, 240, 240, 304, 304};
  const pari_long high[]={ 165657, 85008, 52783, 43622, 32774, 27086, 22385, 15289, 13899, 12635, 11487, 10442, 9493, 7845, 6484, 6484, 5894, 5894, 4871, 4871, 4428, 4026, 3660, 3660, 3660, 3327, 3327, 3024, 2749, 2749, 2272, 2749, 2499, 2499, 2272, 1878, 1878, 1878, 1707, 1552, 1552, 1552, 1552, 1552, 1411, 1411, 1411, 1282, 1282, 1282, 1282, 1282, 1166, 1166, 1166, 1166, 1166, 1166, 1166, 1166, 1060, 1060, 963, 963, 963, 963, 963, 963, 963, 963, 963, 963, 963, 876, 876, 876, 876, 796, 658, 724, 658, 724, 658, 658, 658, 658, 658, 658, 658, 658, 658, 658, 658, 658, 336, 658, 658, 592, 336, 336};
#endif
  const pari_long nblow = sizeof(low)/sizeof(*low);
  pari_sp av;
  pari_long ex, vx;
  GEN z;
  if (!nx) return pol_0(0);
  vx = ZX_valspec(x,nx); nx-=vx; x+=vx;
  if (nx==1) return Z_sqrshiftspec_ZX(gel(x, 0), vx);
  av = avma;
  ex = ZX_expispec(x,nx);
  if (nx-2 < nblow && low[nx-2]<=ex && ex<=high[nx-2])
    z = ZX_sqrspec_basecase(x, nx, 2*vx);
  else
    z = ZX_sqrspec_sqri(x, nx, ex, 2*vx);
  return gerepileupto(av, z);
}

GEN
ZX_sqr(GEN x)
{
  GEN z = ZX_sqrspec(x+2, lgpol(x));
  z[1] = x[1];
  return z;
}

GEN
ZX_mulspec(GEN x, GEN y, pari_long nx, pari_long ny)
{
  pari_sp av;
  pari_long ex, ey, vx, vy;
  GEN z;
  if (!nx || !ny) return pol_0(0);
  vx = ZX_valspec(x,nx); nx-=vx; x += vx;
  vy = ZX_valspec(y,ny); ny-=vy; y += vy;
  if (nx==1) return Z_ZX_mulshiftspec(gel(x,0), y, ny, vx+vy);
  if (ny==1) return Z_ZX_mulshiftspec(gel(y,0), x, nx, vy+vx);
  av = avma;
  ex = ZX_expispec(x, nx); ey = ZX_expispec(y, ny);
  z  = ZX_mulspec_mulii(x,y,nx,ny,ex,ey,vx+vy);
  return gerepileupto(av, z);
}
GEN
ZX_mul(GEN x, GEN y)
{
  GEN z;
  if (x == y) return ZX_sqr(x);
  z = ZX_mulspec(x+2,y+2,lgpol(x),lgpol(y));
  z[1] = x[1];
  if (!signe(y)) z[1] &= VARNBITS;
  return z;
}

/* x,y two ZX in the same variable; assume y is monic */
GEN
ZX_rem(GEN x, GEN y)
{
  pari_long vx, dx, dy, dz, i, j, sx, lr;
  pari_sp av0, av;
  GEN z,p1,rem;

  vx = varn(x);
  dy = degpol(y);
  dx = degpol(x);
  if (dx < dy) return ZX_copy(x);
  if (!dy) return pol_0(vx); /* y is constant */
  av0 = avma; dz = dx-dy;
  z=cgetg(dz+3,t_POL); z[1] = x[1];
  x += 2; y += 2; z += 2;

  p1 = gel(x,dx);
  gel(z,dz) = icopy(p1);
  for (i=dx-1; i>=dy; i--)
  {
    av=avma; p1=gel(x,i);
    for (j=i-dy+1; j<=i && j<=dz; j++)
      p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
    gel(z,i-dy) = avma == av? icopy(p1): gerepileuptoint(av, p1);
  }
  rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
  for (sx=0; ; i--)
  {
    p1 = gel(x,i);
    for (j=0; j<=i && j<=dz; j++)
      p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
    if (signe(p1)) { sx = 1; break; }
    if (!i) break;
    avma=av;
  }
  lr=i+3; rem -= lr;
  rem[0] = evaltyp(t_POL) | evallg(lr);
  rem[1] = z[-1];
  p1 = gerepileuptoint((pari_sp)rem, p1);
  rem += 2; gel(rem,i) = p1;
  for (i--; i>=0; i--)
  {
    av=avma; p1 = gel(x,i);
    for (j=0; j<=i && j<=dz; j++)
      p1 = subii(p1, mulii(gel(z,j),gel(y,i-j)));
    gel(rem,i) = avma == av? icopy(p1): gerepileuptoint(av, p1);
  }
  rem -= 2;
  if (!sx) (void)ZX_renormalize(rem, lr);
  return gerepileupto(av0,rem);
}

/* return x(1) */
GEN
ZX_eval1(GEN x)
{
  pari_sp av = avma;
  pari_long i = lg(x)-1;
  GEN s;
  if (i < 2) return gen_0;
  s = gel(x,i); i--;
  if (i == 1) return icopy(s);
  for ( ; i>=2; i--)
  {
    GEN c = gel(x,i);
    if (signe(c)) s = addii(s, c);
  }
  return gerepileuptoint(av,s);
}

/* reduce T mod X^n - 1. Shallow function */
GEN
ZX_mod_Xnm1(GEN T, ulong n)
{
  pari_long i, j, L = lg(T), l = n+2;
  GEN S;
  if (L <= l) return T;
  S = cgetg(l, t_POL);
  S[1] = T[1];
  for (i = 2; i < l; i++) gel(S,i) = gel(T,i);
  for (j = 2; i < L; i++) {
    gel(S,j) = addii(gel(S,j), gel(T,i));
    if (++j == l) j = 2;
  }
  return normalizepol_lg(S, l);
}

/*******************************************************************/
/*                                                                 */
/*                                ZXV                              */
/*                                                                 */
/*******************************************************************/

int
ZXV_equal(GEN V, GEN W)
{
  pari_long l = lg(V);
  if (l!=lg(W)) return 0;
  while (--l > 0)
    if (!ZX_equal(gel(V,l), gel(W,l))) return 0;
  return 1;
}

GEN
ZXV_Z_mul(GEN y, GEN x)
{
  pari_long i, l;
  GEN z = cgetg_copy(y, &l);
  for(i=1; i<l; i++) gel(z,i) = ZX_Z_mul(gel(y,i), x);
  return z;
}

GEN
ZXV_remi2n(GEN y, pari_long N)
{
  pari_long i, l;
  GEN z = cgetg_copy(y, &l);
  for(i=1; i<l; i++) gel(z,i) = ZX_remi2n(gel(y,i), N);
  return z;
}
GEN
ZXV_dotproduct(GEN x, GEN y)
{
  pari_sp av = avma;
  pari_long i, lx = lg(x);
  GEN c;
  if (lx == 1) return pol_0(varn(x));
  c = ZX_mul(gel(x,1), gel(y,1));
  for (i = 2; i < lx; i++)
  {
    GEN t = ZX_mul(gel(x,i), gel(y,i));
    if (signe(t)) c = ZX_add(c, t);
  }
  return gerepileupto(av, c);
}

/*******************************************************************/
/*                                                                 */
/*                                ZXX                              */
/*                                                                 */
/*******************************************************************/

void
RgX_check_ZXX(GEN x, const char *s)
{
  pari_long k = lg(x)-1;
  for ( ; k>1; k--) {
    GEN t = gel(x,k);
    switch(typ(t)) {
      case t_INT: break;
      case t_POL: if (RgX_is_ZX(t)) break;
      /* fall through */
      default: pari_err_TYPE(stack_strcat(s, " not in Z[X,Y]"),x);
    }
  }
}

/*Renormalize (in place) polynomial with t_INT or ZX coefficients.*/
GEN
ZXX_renormalize(GEN x, pari_long lx)
{
  pari_long i;
  for (i = lx-1; i>1; i--)
    if (signe(gel(x,i))) break;
  stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + (i+1)));
  setlg(x, i+1); setsigne(x, i!=1); return x;
}

pari_long
ZXX_max_lg(GEN x)
{
  pari_long i, prec = 0, lx = lg(x);
  for (i=2; i<lx; i++)
  {
    GEN p = gel(x,i);
    pari_long l = (typ(p) == t_INT)? lgefint(p): ZX_max_lg(p);
    if (l > prec) prec = l;
  }
  return prec;
}

GEN
ZXX_Z_divexact(GEN y, GEN x)
{
  pari_long i, l = lg(y);
  GEN z = cgetg(l,t_POL); z[1] = y[1];
  for(i=2; i<l; i++)
    if(typ(gel(y,i))==t_INT)
      gel(z,i) = diviiexact(gel(y,i),x);
    else
      gel(z,i) = ZX_Z_divexact(gel(y,i),x);
  return z;
}

/* Kronecker substitution, ZXX -> ZX:
 * P(X,Y) = sum_{0<=i<lP} P_i(X) * Y^i, where deg P_i < n.
 * Returns P(X,X^(2n-1)) */
GEN
ZXX_to_Kronecker_spec(GEN P, pari_long lP, pari_long n)
{
  pari_long i, k, N = (n<<1) + 1;
  GEN y;
  if (!lP) return pol_0(0);
  y = cgetg((N-2)*lP + 2, t_POL) + 2;
  for (k=i=0; i<lP; i++)
  {
    pari_long j;
    GEN c = gel(P,i);
    if (typ(c)==t_INT)
    {
      gel(y,k++) = c;
      j = 3;
    }
    else
    {
      pari_long l = lg(c);
      if (l-3 >= n)
        pari_err_BUG("ZXX_to_Kronecker, P is not reduced mod Q");
      for (j=2; j < l; j++) gel(y,k++) = gel(c,j);
    }
    if (i == lP-1) break;
    for (   ; j < N; j++) gel(y,k++) = gen_0;
  }
  y-=2; setlg(y, k+2); y[1] = evalsigne(1); return y;
}

GEN
ZXX_to_Kronecker(GEN P, pari_long n)
{
  GEN z = ZXX_to_Kronecker_spec(P+2, lgpol(P), n);
  setvarn(z,varn(P)); return z;
}