void power(mat_zz_pE& X, const mat_zz_pE& A, const ZZ& e)
{
   if (A.NumRows() != A.NumCols()) Error("power: non-square matrix");

   if (e == 0) {
      ident(X, A.NumRows());
      return;
   }

   mat_zz_pE T1, T2;
   long i, k;

   k = NumBits(e);
   T1 = A;

   for (i = k-2; i >= 0; i--) {
      sqr(T2, T1);
      if (bit(e, i))
         mul(T1, T2, A);
      else
         T1 = T2;
   }

   if (e < 0)
      inv(X, T1);
   else
      X = T1;
}

void transpose(mat_zz_pE& X, const mat_zz_pE& A)
{
   long n = A.NumRows();
   long m = A.NumCols();

   long i, j;

   if (&X == & A) {
      if (n == m)
         for (i = 1; i <= n; i++)
            for (j = i+1; j <= n; j++)
               swap(X(i, j), X(j, i));
      else {
         mat_zz_pE tmp;
         tmp.SetDims(m, n);
         for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
               tmp(j, i) = A(i, j);
         X.kill();
         X = tmp;
      }
   }
   else {
      X.SetDims(m, n);
      for (i = 1; i <= n; i++)
         for (j = 1; j <= m; j++)
            X(j, i) = A(i, j);
   }
}

void mul_aux(mat_zz_pE& X, const mat_zz_pE& A, const mat_zz_pE& B)  
{  
   long n = A.NumRows();  
   long l = A.NumCols();  
   long m = B.NumCols();  
  
   if (l != B.NumRows())  
      Error("matrix mul: dimension mismatch");  
  
   X.SetDims(n, m);  
  
   long i, j, k;  
   zz_pX acc, tmp;  
  
   for (i = 1; i <= n; i++) {  
      for (j = 1; j <= m; j++) {  
         clear(acc);  
         for(k = 1; k <= l; k++) {  
            mul(tmp, rep(A(i,k)), rep(B(k,j)));  
            add(acc, acc, tmp);  
         }  
         conv(X(i,j), acc);  
      }  
   }  
}  

void negate(mat_zz_pE& X, const mat_zz_pE& A)  
{  
   long n = A.NumRows();  
   long m = A.NumCols();  
  
  
   X.SetDims(n, m);  
  
   long i, j;  
   for (i = 1; i <= n; i++)  
      for (j = 1; j <= m; j++)  
         negate(X(i,j), A(i,j));  
}  

void mul(mat_zz_pE& X, const mat_zz_pE& A, const zz_pE& b_in)
{
   zz_pE b = b_in;
   long n = A.NumRows();
   long m = A.NumCols();

   X.SetDims(n, m);

   long i, j;
   for (i = 0; i < n; i++)
      for (j = 0; j < m; j++)
         mul(X[i][j], A[i][j], b);
}

void sub(mat_zz_pE& X, const mat_zz_pE& A, const mat_zz_pE& B)  
{  
   long n = A.NumRows();  
   long m = A.NumCols();  
  
   if (B.NumRows() != n || B.NumCols() != m)  
      Error("matrix sub: dimension mismatch");  
  
   X.SetDims(n, m);  
  
   long i, j;  
   for (i = 1; i <= n; i++)  
      for (j = 1; j <= m; j++)  
         sub(X(i,j), A(i,j), B(i,j));  
}  

void convert(vector< vector<ZZX> >& X, const mat_zz_pE& A)
{
   long n = A.NumRows();
   X.resize(n);
   for (long i = 0; i < n; i++)
      convert(X[i], A[i]);
}

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

long IsDiag(const mat_zz_pE& A, long n, const zz_pE& d)
{
   if (A.NumRows() != n || A.NumCols() != n)
      return 0;

   long i, j;

   for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
         if (i != j) {
            if (!IsZero(A(i, j))) return 0;
         }
         else {
            if (A(i, j) != d) return 0;
         }

   return 1;
}

NTL_START_IMPL

  
void add(mat_zz_pE& X, const mat_zz_pE& A, const mat_zz_pE& B)  
{  
   long n = A.NumRows();  
   long m = A.NumCols();  
  
   if (B.NumRows() != n || B.NumCols() != m)   
      LogicError("matrix add: dimension mismatch");  
  
   X.SetDims(n, m);  
  
   long i, j;  
   for (i = 1; i <= n; i++)   
      for (j = 1; j <= m; j++)  
         add(X(i,j), A(i,j), B(i,j));  
}  

long IsZero(const mat_zz_pE& a)
{
   long n = a.NumRows();
   long i;

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

   return 1;
}

// prime power solver
// A is an n x n matrix, we compute its inverse mod p^r. An error is raised
// if A is not inverible mod p. zz_p::modulus() is assumed to be p^r, for
// p prime, r >= 1. Also zz_pE::modulus() is assumed to be initialized.
void ppInvert(mat_zz_pE& X, const mat_zz_pE& A, long p, long r)
{
  if (r == 1) { // use native inversion from NTL
    inv(X, A);    // X = A^{-1}
    return;
  }

  // begin by inverting A modulo p

  // convert to ZZX for a safe transaltion to mod-p objects
  vector< vector<ZZX> > tmp;
  convert(tmp, A);
  { // open a new block for mod-p computation
  ZZX G;
  convert(G, zz_pE::modulus());
  zz_pBak bak_pr; bak_pr.save(); // backup the mod-p^r moduli
  zz_pEBak bak_prE; bak_prE.save();
  zz_p::init(p);   // Set the mod-p moduli
  zz_pE::init(conv<zz_pX>(G));

  mat_zz_pE A1, Inv1;
  convert(A1, tmp);   // Recover A as a mat_zz_pE object modulo p
  inv(Inv1, A1);      // Inv1 = A^{-1} (mod p)
  convert(tmp, Inv1); // convert to ZZX for transaltion to a mod-p^r object
  } // mod-p^r moduli restored on desctuction of bak_pr and bak_prE
  mat_zz_pE XX;
  convert(XX, tmp); // XX = A^{-1} (mod p)

  // Now lift the solution modulo p^r

  // Compute the "correction factor" Z, s.t. XX*A = I - p*Z (mod p^r)
  long n = A.NumRows();
  const mat_zz_pE I = ident_mat_zz_pE(n); // identity matrix
  mat_zz_pE Z = I - XX*A;

  convert(tmp, Z);  // Conver to ZZX to divide by p
  for (long i=0; i<n; i++) for (long j=0; j<n; j++) tmp[i][j] /= p;
  convert(Z, tmp);  // convert back to a mod-p^r object

  // The inverse of A is ( I+(pZ)+(pZ)^2+...+(pZ)^{r-1} )*XX (mod p^r). We use
  // O(log r) products to copmute it as (I+pZ)* (I+(pZ)^2)* (I+(pZ)^4)*...* XX

  long e = NextPowerOfTwo(r); // 2^e is smallest power of two >= r

  Z *= p;                 // = pZ
  mat_zz_pE prod = I + Z; // = I + pZ
  for (long i=1; i<e; i++) {
    sqr(Z, Z);     // = (pZ)^{2^i}
    prod *= (I+Z); // = sum_{j=0}^{2^{i+1}-1} (pZ)^j
  }
  mul(X, prod, XX); // X = A^{-1} mod p^r
  assert(X*A == I);
}

void ident(mat_zz_pE& X, long n)  
{  
   X.SetDims(n, n);  
   long i, j;  
  
   for (i = 1; i <= n; i++)  
      for (j = 1; j <= n; j++)  
         if (i == j)  
            set(X(i, j));  
         else  
            clear(X(i, j));  
} 

void diag(mat_zz_pE& X, long n, const zz_pE& d_in)  
{  
   zz_pE d = d_in;
   X.SetDims(n, n);  
   long i, j;  
  
   for (i = 1; i <= n; i++)  
      for (j = 1; j <= n; j++)  
         if (i == j)  
            X(i, j) = d;  
         else  
            clear(X(i, j));  
} 

void buildLinPolyMatrix(mat_zz_pE& M, long p)
{
   long d = zz_pE::degree();

   M.SetDims(d, d);

   for (long j = 0; j < d; j++) 
      conv(M[0][j], zz_pX(j, 1));

   for (long i = 1; i < d; i++)
      for (long j = 0; j < d; j++)
         M[i][j] = power(M[i-1][j], p);
}

void determinant(zz_pE& d, const mat_zz_pE& M_in)
{
   long k, n;
   long i, j;
   long pos;
   zz_pX t1, t2;
   zz_pX *x, *y;

   const zz_pXModulus& p = zz_pE::modulus();

   n = M_in.NumRows();

   if (M_in.NumCols() != n)
      Error("determinant: nonsquare matrix");

   if (n == 0) {
      set(d);
      return;
   }

   vec_zz_pX *M = newNTL_NEW_OP vec_zz_pX[n];

   for (i = 0; i < n; i++) {
      M[i].SetLength(n);
      for (j = 0; j < n; j++) {
         M[i][j].rep.SetMaxLength(2*deg(p)-1);
         M[i][j] = rep(M_in[i][j]);
      }
   }

   zz_pX det;
   set(det);

   for (k = 0; k < n; k++) {
      pos = -1;
      for (i = k; i < n; i++) {
         rem(t1, M[i][k], p);
         M[i][k] = t1;
         if (pos == -1 && !IsZero(t1))
            pos = i;
      }

      if (pos != -1) {
         if (k != pos) {
            swap(M[pos], M[k]);
            negate(det, det);
         }

         MulMod(det, det, M[k][k], p);

         // make M[k, k] == -1 mod p, and make row k reduced

         InvMod(t1, M[k][k], p);
         negate(t1, t1);
         for (j = k+1; j < n; j++) {
            rem(t2, M[k][j], p);
            MulMod(M[k][j], t2, t1, p);
         }

         for (i = k+1; i < n; i++) {
            // M[i] = M[i] + M[k]*M[i,k]

            t1 = M[i][k];   // this is already reduced

            x = M[i].elts() + (k+1);
            y = M[k].elts() + (k+1);

            for (j = k+1; j < n; j++, x++, y++) {
               // *x = *x + (*y)*t1

               mul(t2, *y, t1);
               add(*x, *x, t2);
            }
         }
      }
      else {
         clear(d);
         goto done;
      }
   }

   conv(d, det);

done:
   delete[] M;
}

long gauss(mat_zz_pE& M_in, long w)
{
   long k, l;
   long i, j;
   long pos;
   zz_pX t1, t2, t3;
   zz_pX *x, *y;

   long n = M_in.NumRows();
   long m = M_in.NumCols();

   if (w < 0 || w > m)
      Error("gauss: bad args");

   const zz_pXModulus& p = zz_pE::modulus();


   vec_zz_pX *M = newNTL_NEW_OP vec_zz_pX[n];

   for (i = 0; i < n; i++) {
      M[i].SetLength(m);
      for (j = 0; j < m; j++) {
         M[i][j].rep.SetMaxLength(2*deg(p)-1);
         M[i][j] = rep(M_in[i][j]);
      }
   }

   l = 0;
   for (k = 0; k < w && l < n; k++) {

      pos = -1;
      for (i = l; i < n; i++) {
         rem(t1, M[i][k], p);
         M[i][k] = t1;
         if (pos == -1 && !IsZero(t1)) {
            pos = i;
         }
      }

      if (pos != -1) {
         swap(M[pos], M[l]);

         InvMod(t3, M[l][k], p);
         negate(t3, t3);

         for (j = k+1; j < m; j++) {
            rem(M[l][j], M[l][j], p);
         }

         for (i = l+1; i < n; i++) {
            // M[i] = M[i] + M[l]*M[i,k]*t3

            MulMod(t1, M[i][k], t3, p);

            clear(M[i][k]);

            x = M[i].elts() + (k+1);
            y = M[l].elts() + (k+1);

            for (j = k+1; j < m; j++, x++, y++) {
               // *x = *x + (*y)*t1

               mul(t2, *y, t1);
               add(t2, t2, *x);
               *x = t2;
            }
         }

         l++;
      }
   }
   
   for (i = 0; i < n; i++)
      for (j = 0; j < m; j++)
         conv(M_in[i][j], M[i][j]);

   delete [] M;

   return l;
}

// prime power solver
// zz_p::modulus() is assumed to be p^r, for p prime, r >= 1
// A is an n x n matrix, b is a length n (row) vector,
// and a solution for the matrix-vector equation x A = b is found.
// If A is not inverible mod p, then error is raised.
void ppsolve(vec_zz_pE& x, const mat_zz_pE& A, const vec_zz_pE& b,
             long p, long r) 
{

   if (r == 1) {
      zz_pE det;
      solve(det, x, A, b);
      if (det == 0) Error("ppsolve: matrix not invertible");
      return;
   }

   long n = A.NumRows();
   if (n != A.NumCols()) 
      Error("ppsolve: matrix not square");
   if (n == 0)
      Error("ppsolve: matrix of dimension 0");

   zz_pContext pr_context;
   pr_context.save();

   zz_pEContext prE_context;
   prE_context.save();

   zz_pX G = zz_pE::modulus();

   ZZX GG = to_ZZX(G);

   vector< vector<ZZX> > AA;
   convert(AA, A);

   vector<ZZX> bb;
   convert(bb, b);

   zz_pContext p_context(p);
   p_context.restore();

   zz_pX G1 = to_zz_pX(GG);
   zz_pEContext pE_context(G1);
   pE_context.restore();

   // we are now working mod p...

   // invert A mod p

   mat_zz_pE A1;
   convert(A1, AA);

   mat_zz_pE I1;
   zz_pE det;

   inv(det, I1, A1);
   if (det == 0) {
      Error("ppsolve: matrix not invertible");
   }

   vec_zz_pE b1;
   convert(b1, bb);

   vec_zz_pE y1;
   y1 = b1 * I1;

   vector<ZZX> yy;
   convert(yy, y1);

   // yy is a solution mod p

   for (long k = 1; k < r; k++) {
      // lift solution yy mod p^k to a solution mod p^{k+1}

      pr_context.restore();
      prE_context.restore();
      // we are now working mod p^r

      vec_zz_pE d, y;
      convert(y, yy);

      d = b - y * A;

      vector<ZZX> dd;
      convert(dd, d);

      long pk = power_long(p, k);
      vector<ZZX> ee;
      div(ee, dd, pk);

      p_context.restore();
      pE_context.restore();

      // we are now working mod p

      vec_zz_pE e1;
      convert(e1, ee);
      vec_zz_pE z1;
      z1 = e1 * I1;

//.........这里部分代码省略.........

void kernel(mat_zz_pE& X, const mat_zz_pE& A)
{
   long m = A.NumRows();
   long n = A.NumCols();

   mat_zz_pE M;
   long r;

   transpose(M, A);
   r = gauss(M);

   X.SetDims(m-r, m);

   long i, j, k, s;
   zz_pX t1, t2;

   zz_pE T3;

   vec_long D;
   D.SetLength(m);
   for (j = 0; j < m; j++) D[j] = -1;

   vec_zz_pE inverses;
   inverses.SetLength(m);

   j = -1;
   for (i = 0; i < r; i++) {
      do {
         j++;
      } while (IsZero(M[i][j]));

      D[j] = i;
      inv(inverses[j], M[i][j]); 
   }

   for (k = 0; k < m-r; k++) {
      vec_zz_pE& v = X[k];
      long pos = 0;
      for (j = m-1; j >= 0; j--) {
         if (D[j] == -1) {
            if (pos == k)
               set(v[j]);
            else
               clear(v[j]);
            pos++;
         }
         else {
            i = D[j];

            clear(t1);

            for (s = j+1; s < m; s++) {
               mul(t2, rep(v[s]), rep(M[i][s]));
               add(t1, t1, t2);
            }

            conv(T3, t1);
            mul(T3, T3, inverses[j]);
            negate(v[j], T3);
         }
      }
   }
}

void inv(zz_pE& d, mat_zz_pE& X, const mat_zz_pE& A)
{
   long n = A.NumRows();
   if (A.NumCols() != n)
      Error("inv: nonsquare matrix");

   if (n == 0) {
      set(d);
      X.SetDims(0, 0);
      return;
   }

   long i, j, k, pos;
   zz_pX t1, t2;
   zz_pX *x, *y;

   const zz_pXModulus& p = zz_pE::modulus();


   vec_zz_pX *M = newNTL_NEW_OP vec_zz_pX[n];

   for (i = 0; i < n; i++) {
      M[i].SetLength(2*n);
      for (j = 0; j < n; j++) {
         M[i][j].rep.SetMaxLength(2*deg(p)-1);
         M[i][j] = rep(A[i][j]);
         M[i][n+j].rep.SetMaxLength(2*deg(p)-1);
         clear(M[i][n+j]);
      }
      set(M[i][n+i]);
   }

   zz_pX det;
   set(det);

   for (k = 0; k < n; k++) {
      pos = -1;
      for (i = k; i < n; i++) {
         rem(t1, M[i][k], p);
         M[i][k] = t1;
         if (pos == -1 && !IsZero(t1)) {
            pos = i;
         }
      }

      if (pos != -1) {
         if (k != pos) {
            swap(M[pos], M[k]);
            negate(det, det);
         }

         MulMod(det, det, M[k][k], p);

         // make M[k, k] == -1 mod p, and make row k reduced

         InvMod(t1, M[k][k], p);
         negate(t1, t1);
         for (j = k+1; j < 2*n; j++) {
            rem(t2, M[k][j], p);
            MulMod(M[k][j], t2, t1, p);
         }

         for (i = k+1; i < n; i++) {
            // M[i] = M[i] + M[k]*M[i,k]

            t1 = M[i][k];   // this is already reduced

            x = M[i].elts() + (k+1);
            y = M[k].elts() + (k+1);

            for (j = k+1; j < 2*n; j++, x++, y++) {
               // *x = *x + (*y)*t1

               mul(t2, *y, t1);
               add(*x, *x, t2);
            }
         }
      }
      else {
         clear(d);
         goto done;
      }
   }

   X.SetDims(n, n);
   for (k = 0; k < n; k++) {
      for (i = n-1; i >= 0; i--) {
         clear(t1);
         for (j = i+1; j < n; j++) {
            mul(t2, rep(X[j][k]), M[i][j]);
            add(t1, t1, t2);
         }
         sub(t1, t1, M[i][n+k]);
         conv(X[i][k], t1);
      }
   }

   conv(d, det);

done:
//.........这里部分代码省略.........