gt:             if (cm.isConstant()) {
context: /*
   * $Id$
   */
  
  package edu.jas.ufd;
  
  
  import org.apache.log4j.Logger;
  
  import edu.jas.arith.Modular;
  import edu.jas.arith.ModularRingFactory;
  import edu.jas.poly.ExpVector;
  import edu.jas.poly.GenPolynomial;
  import edu.jas.poly.GenPolynomialRing;
  import edu.jas.poly.PolyUtil;
  import edu.jas.structure.GcdRingElem;
  
  
  /**
   * Greatest common divisor algorithms with modular evaluation algorithm for
   * recursion.
   * @author Heinz Kredel
   */
  
  public class GreatestCommonDivisorModEval <MOD extends GcdRingElem<MOD> & Modular> 
          extends GreatestCommonDivisorAbstract<MOD> {
  
  
      private static final Logger logger = Logger.getLogger(GreatestCommonDivisorModEval.class);
  
  
      private final boolean debug = logger.isDebugEnabled();
  
  
      /**
       * Modular gcd algorithm to use.
       */
      protected final GreatestCommonDivisorAbstract<MOD> mufd 
         = new GreatestCommonDivisorSimple<MOD>();
      // = new GreatestCommonDivisorPrimitive<MOD>();
      // not okay: = new GreatestCommonDivisorSubres<MOD>();
  
  
      /**
       * Univariate GenPolynomial greatest common divisor. 
       * @param P univariate GenPolynomial.
       * @param S univariate GenPolynomial.
       * @return gcd(P,S).
       */
      @Override
      public GenPolynomial<MOD> baseGcd(GenPolynomial<MOD> P, GenPolynomial<MOD> S) {
          // required as recursion base
          return mufd.baseGcd(P, S);
      }
  
  
      /**
       * Recursive univariate GenPolynomial greatest common divisor. 
       * @param P univariate recursive GenPolynomial.
       * @param S univariate recursive GenPolynomial.
       * @return gcd(P,S).
       */
      @Override
      public GenPolynomial<GenPolynomial<MOD>> recursiveUnivariateGcd(
              GenPolynomial<GenPolynomial<MOD>> P, GenPolynomial<GenPolynomial<MOD>> S) {
          return mufd.recursiveUnivariateGcd(P, S);
      }
  
  
      /**
       * GenPolynomial greatest common divisor, modular evaluation algorithm.
       * @param P GenPolynomial.
       * @param S GenPolynomial.
       * @return gcd(P,S).
       */
      @Override
      public GenPolynomial<MOD> gcd(GenPolynomial<MOD> P, GenPolynomial<MOD> S) {
          if (S == null || S.isZERO()) {
              return P;
          }
          if (P == null || P.isZERO()) {
              return S;
          }
          GenPolynomialRing<MOD> fac = P.ring;
          // recusion base case for univariate polynomials
          if (fac.nvar <= 1) {
              GenPolynomial<MOD> T = baseGcd(P, S);
              return T;
          }
          long e = P.degree(fac.nvar-1);
          long f = S.degree(fac.nvar-1);
          if ( e == 0 && f == 0 ) {
              GenPolynomialRing<GenPolynomial<MOD>> rfac = fac.recursive(1);
              GenPolynomial<MOD> Pc = PolyUtil.<MOD> recursive(rfac, P).leadingBaseCoefficient();
              GenPolynomial<MOD> Sc = PolyUtil.<MOD> recursive(rfac, S).leadingBaseCoefficient();
              GenPolynomial<MOD> r = gcd(Pc,Sc);
              return r.extend(fac,0,0L);
          }
          GenPolynomial<MOD> q;
          GenPolynomial<MOD> r;
          if (f > e) {
              r = P;
              q = S;
              long g = f;
              f = e;
              e = g;
          } else {
              q = P;
              r = S;
          }
          if (debug) {
              logger.debug("degrees: e = " + e + ", f = " + f);
          }
          r = r.abs();
          q = q.abs();
          // setup factories
          ModularRingFactory<MOD> cofac = (ModularRingFactory<MOD>) P.ring.coFac;
          if (!cofac.isField()) {
              logger.warn("cofac is not a field: " + cofac);
          }
          GenPolynomialRing<GenPolynomial<MOD>> rfac = fac.recursive(fac.nvar - 1);
          GenPolynomialRing<MOD> mfac = new GenPolynomialRing<MOD>(cofac, rfac);
          GenPolynomialRing<MOD> ufac = (GenPolynomialRing<MOD>) rfac.coFac;
          //GenPolynomialRing<MOD> mfac = new GenPolynomialRing<MOD>(cofac, fac.nvar - 1, fac.tord);
          //GenPolynomialRing<MOD> ufac = new GenPolynomialRing<MOD>(cofac, 1, fac.tord);
          //GenPolynomialRing<GenPolynomial<MOD>> rfac = new GenPolynomialRing<GenPolynomial<MOD>>(ufac, fac.nvar - 1, fac.tord);
          // convert polynomials
          GenPolynomial<GenPolynomial<MOD>> qr;
          GenPolynomial<GenPolynomial<MOD>> rr;
          qr = PolyUtil.<MOD> recursive(rfac, q);
          rr = PolyUtil.<MOD> recursive(rfac, r);
  
          // compute univariate contents and primitive parts
          GenPolynomial<MOD> a = recursiveContent(rr);
          GenPolynomial<MOD> b = recursiveContent(qr);
          // gcd of univariate coefficient contents
          GenPolynomial<MOD> c = gcd(a, b);
          rr = PolyUtil.<MOD> recursiveDivide(rr, a);
          qr = PolyUtil.<MOD> recursiveDivide(qr, b);
          if (rr.isONE()) {
              rr = rr.multiply(c);
              r = PolyUtil.<MOD> distribute(fac, rr);
              return r;
          }
          if (qr.isONE()) {
              qr = qr.multiply(c);
              q = PolyUtil.<MOD> distribute(fac, qr);
              return q;
          }
          // compute normalization factor
          GenPolynomial<MOD> ac = rr.leadingBaseCoefficient();
          GenPolynomial<MOD> bc = qr.leadingBaseCoefficient();
          GenPolynomial<MOD> cc = gcd(ac, bc);
          // compute degrees and degree vectors
          ExpVector rdegv = rr.degreeVector();
          ExpVector qdegv = qr.degreeVector();
          long rd0 = PolyUtil.<MOD> coeffMaxDegree(rr);
          long qd0 = PolyUtil.<MOD> coeffMaxDegree(qr);
          long cd0 = cc.degree(0);
          long G = (rd0 >= qd0 ? rd0 : qd0) + cd0;
  
          // initialize element and degree vector
          ExpVector wdegv = rdegv.subst(0, rdegv.getVal(0) + 1);
          // +1 seems to be a hack for the unlucky prime test
          MOD inc = cofac.getONE();
          long i = 0;
          long en = cofac.getIntegerModul().longValue() - 1; // just a stopper
          MOD end = cofac.fromInteger(en);
          MOD mi;
          GenPolynomial<MOD> M = null;
          GenPolynomial<MOD> mn;
          GenPolynomial<MOD> qm;
          GenPolynomial<MOD> rm;
          GenPolynomial<MOD> cm;
          GenPolynomial<GenPolynomial<MOD>> cp = null;
          if (debug) {
              logger.debug("c = " + c);
              logger.debug("cc = " + cc);
              logger.debug("G = " + G);
              logger.info("wdegv = " + wdegv);
          }
          for (MOD d = cofac.getZERO(); d.compareTo(end) <= 0; d = d.sum(inc)) {
              if (++i >= en) {
                  logger.warn("elements of Z_p exhausted, en = " + en);
                  return mufd.gcd(P, S);
                  //throw new ArithmeticException("prime list exhausted");
              }
              // map normalization factor
              MOD nf = PolyUtil.<MOD> evaluateMain(cofac, cc, d);
              if (nf.isZERO()) {
                  continue;
              }
              // map polynomials
              qm = PolyUtil.<MOD> evaluateFirstRec(ufac, mfac, qr, d);
              if (qm.isZERO() || !qm.degreeVector().equals(qdegv)) {
                  continue;
              }
              rm = PolyUtil.<MOD> evaluateFirstRec(ufac, mfac, rr, d);
              if (rm.isZERO() || !rm.degreeVector().equals(rdegv)) {
                  continue;
              }
              if (debug) {
                  logger.debug("eval d = " + d);
              }
              // compute modular gcd in recursion
              cm = gcd(rm, qm);
              //System.out.println("cm = " + cm);
              // test for constant g.c.d
  