bool intVecCRT(vec_ZZ& vp, const ZZ& p, const zzvec& vq, long q)
{
  long pInv = InvMod(rem(p,q), q); // p^{-1} mod q
  long n = min(vp.length(),vq.length());
  long q_over_2 = q/2;
  ZZ tmp;
  long vqi;
  mulmod_precon_t pqInv = PrepMulModPrecon(pInv, q);
  for (long i=0; i<n; i++) {
    conv(vqi, vq[i]); // convert to single precision
    long vq_minus_vp_mod_q = SubMod(vqi, rem(vp[i],q), q);

    long delta_times_pInv = MulModPrecon(vq_minus_vp_mod_q, pInv, q, pqInv);
    if (delta_times_pInv > q_over_2) delta_times_pInv -= q;

    mul(tmp, delta_times_pInv, p); // tmp = [(vq_i-vp_i)*p^{-1}]_q * p
    vp[i] += tmp;
  }
  // other entries (if any) are 0 mod q
  for (long i=vq.length(); i<vp.length(); i++) {
    long minus_vp_mod_q = NegateMod(rem(vp[i],q), q);

    long delta_times_pInv = MulModPrecon(minus_vp_mod_q, pInv, q, pqInv);
    if (delta_times_pInv > q_over_2) delta_times_pInv -= q;

    mul(tmp, delta_times_pInv, p); // tmp = [(vq_i-vp_i)*p^{-1}]_q * p
    vp[i] += tmp;
  }
  return (vp.length()==vq.length());
}

void mul(vec_ZZ& x, const vec_ZZ& a, long b)
{
   long n = a.length();
   x.SetLength(n);
   long i;
   for (i = 0; i < n; i++)
      mul(x[i], a[i], b);
}

void negate(vec_ZZ& x, const vec_ZZ& a)
{
   long n = a.length();
   x.SetLength(n);
   long i;
   for (i = 0; i < n; i++)
      negate(x[i], a[i]);
}

void sub(vec_ZZ& x, const vec_ZZ& a, const vec_ZZ& b)
{
   long n = a.length();
   if (b.length() != n) LogicError("vector sub: dimension mismatch");
   x.SetLength(n);
   long i;
   for (i = 0; i < n; i++)
      sub(x[i], a[i], b[i]);
}

static void MulSubFrom(vec_ZZ& c, const vec_ZZ& c2, long x)

// c = c - x*c2

{
   long n = c.length();
   if (c2.length() != n) Error("MulSubFrom: length mismatch");

   long i;
   for (i = 1; i <= n; i++)
      MulSubFrom(c(i), c2(i), x);
}

void conv(vec_zz_p& x, const vec_ZZ& a)
{
   long i, n;

   n = a.length();
   x.SetLength(n);

   zz_p* xp = x.elts();
   const ZZ* ap = a.elts();

   for (i = 0; i < n; i++)
      conv(xp[i], ap[i]);
}

NTL_START_IMPL


// NOTE: the signature for this is in lzz_p.h
void conv(vec_zz_p& x, const vec_ZZ& a)
{
   long i, n;

   n = a.length();
   x.SetLength(n);

   VectorConv(n, x.elts(), a.elts());
}

static
void SubDiv(vec_ZZ& e, const vec_ZZ& t, long p)
{
    long n = e.length();
    if (t.length() != n) Error("SubDiv: dimension mismatch");

    ZZ s;
    long i;

    for (i = 0; i < n; i++) {
        sub(s, e[i], t[i]);
        div(e[i], s, p);
    }
}

static void MulSubDiv(vec_ZZ& c, const vec_ZZ& c1, const vec_ZZ& c2,
                      const ZZ& x, const ZZ& y, const ZZ& z)

// c = (x*c1 + y*c2)/z

{
   long n = c1.length();
   if (c2.length() != n) Error("MulSubDiv: length mismatch");
   c.SetLength(n);

   long i;
   for (i = 1; i <= n; i++)
      MulSubDiv(c(i), c1(i), c2(i), x, y, z);
}

void clear(vec_ZZ& x)
{
   long n = x.length();
   long i;
   for (i = 0; i < n; i++)
      clear(x[i]);
}

long CRT(vec_ZZ& gg, ZZ& a, const vec_zz_p& G)
{
   long n = gg.length();
   if (G.length() != n) Error("CRT: vector length mismatch");

   long p = zz_p::modulus();

   ZZ new_a;
   mul(new_a, a, p);

   long a_inv;
   a_inv = rem(a, p);
   a_inv = InvMod(a_inv, p);

   long p1;
   p1 = p >> 1;

   ZZ a1;
   RightShift(a1, a, 1);

   long p_odd = (p & 1);

   long modified = 0;

   long h;

   ZZ g;
   long i;
   for (i = 0; i < n; i++) {
      if (!CRTInRange(gg[i], a)) {
         modified = 1;
         rem(g, gg[i], a);
         if (g > a1) sub(g, g, a);
      }
      else
         g = gg[i];

      h = rem(g, p);
      h = SubMod(rep(G[i]), h, p);
      h = MulMod(h, a_inv, p);
      if (h > p1)
         h = h - p;

      if (h != 0) {
         modified = 1;

         if (!p_odd && g > 0 && (h == p1))
            MulSubFrom(g, a, h);
         else
            MulAddTo(g, a, h);
      }

      gg[i] = g;
   }

   a = new_a;

   return modified;
}

void VectorCopy(vec_ZZ& x, const vec_ZZ& a, long n)
{
   if (n < 0) LogicError("VectorCopy: negative length");
   if (NTL_OVERFLOW(n, 1, 0)) ResourceError("overflow in VectorCopy");

   long m = min(n, a.length());

   x.SetLength(n);

   long i;

   for (i = 0; i < m; i++)
      x[i] = a[i];

   for (i = m; i < n; i++)
      clear(x[i]);
}

NTL_START_IMPL


void InnerProduct(ZZ& xx, const vec_ZZ& a, const vec_ZZ& b)
{
   ZZ t1, x;

   long n = min(a.length(), b.length());
   long i;

   clear(x);
   for (i = 1; i <= n; i++) {
      mul(t1, a(i), b(i));
      add(x, x, t1);
   }

   xx = x;
}

static
void ExactDiv(vec_ZZ& x, const ZZ& d)
{
    long n = x.length();
    long i;

    for (i = 0; i < n; i++)
        if (!divide(x[i], x[i], d))
            Error("inexact division");
}

long IsZero(const vec_ZZ& a)
{
   long n = a.length();
   long i;

   for (i = 0; i < n; i++)
      if (!IsZero(a[i]))
         return 0;

   return 1;
}

vec_ZZ  vec_shift(vec_ZZ v, int dim)
{
    vec_ZZ  shifted_vec;
    int     len;
    len =   v.length();
    shifted_vec.SetLength(dim);
 //   if (len>dim-1)
 //       cout<<"incorrect length "<<len<<"    "<<dim<<endl;
    for (int i=0; i<len-1;i++)
        shifted_vec[i+1]    =   v[i];
    return shifted_vec;
}

static void RowTransform2(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1)
// x = x + y*MU
{
   NTL_ZZRegister(T);
   NTL_ZZRegister(MU);
   long k;

   long n = A.length();
   long i;

   MU = MU1;

   if (MU == 1) {
      for (i = 1; i <= n; i++)
         add(A(i), A(i), B(i));

      return;
   }

   if (MU == -1) {
      for (i = 1; i <= n; i++)
         sub(A(i), A(i), B(i));

      return;
   }

   if (MU == 0) return;

   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
      k = MakeOdd(MU);
   else
      k = 0;

   if (MU.WideSinglePrecision()) {
      long mu1;
      conv(mu1, MU);

      for (i = 1; i <= n; i++) {
         mul(T, B(i), mu1);
         if (k > 0) LeftShift(T, T, k);
         add(A(i), A(i), T);
      }
   }
   else {
      for (i = 1; i <= n; i++) {
         mul(T, B(i), MU);
         if (k > 0) LeftShift(T, T, k);
         add(A(i), A(i), T);
      }
   }
}

static
void mul_aux(vec_ZZ& x, const vec_ZZ& a, const mat_ZZ& B)
{
    long n = B.NumRows();
    long l = B.NumCols();

    if (n != a.length())
        Error("matrix mul: dimension mismatch");

    x.SetLength(l);

    long i, k;
    ZZ acc, tmp;

    for (i = 1; i <= l; i++) {
        clear(acc);
        for (k = 1; k <= n; k++) {
            mul(tmp, a(k), B(k,i));
            add(acc, acc, tmp);
        }
        x(i) = acc;
    }
}

NTL_CLIENT

long SubsetSumSolution(const vec_ZZ& z)
{
   long n = z.length()-3;
   long j;

   if (z(n+1) != 0) return 0;
   if (z(n+2) != -1 && z(n+2) != 1) return 0;
   for (j = 1; j <= n; j++) 
      if (z(j) != -1 && z(j) != 1) return 0;

   return 1;
}

static
void MulAdd(vec_ZZ& x, const ZZ& prod, const vec_zz_p& h)
{
    long n = x.length();
    if (h.length() != n) Error("MulAdd: dimension mismatch");

    ZZ t;
    long i;

    for (i = 0; i < n; i++) {
        mul(t, prod, rep(h[i]));
        add(x[i], x[i], t);
    }
}