Index: factory/cf_gcd.cc
===================================================================
--- factory/cf_gcd.cc	(revision a9a6dcbcbc4f0be99516f14eae42b1776235ca9f)
+++ factory/cf_gcd.cc	(revision f7a4e9271997208f4ee40a14fd1e1b5c6c0c1ffc)
@@ -757,25 +757,8 @@
   else if (!fc_and_gc_Univariate)
   {
-    if (
-    isOn(SW_USE_CHINREM_GCD)
-    && (isPurePoly_m(fc)) && (isPurePoly_m(gc))
-    )
-    {
-    #if 0
-      if ( p1 == fc.level() )
-        fc = chinrem_gcd( fc, gc );
-      else
-      {
-        fc = replacevar( fc, Variable(p1), Variable(mp) );
-        gc = replacevar( gc, Variable(p1), Variable(mp) );
-        fc = replacevar( chinrem_gcd( fc, gc ), Variable(mp), Variable(p1) );
-      }
-    #else
-      fc = chinrem_gcd( fc, gc);
-    #endif
-    }
-    else if ( isOn( SW_USE_EZGCD ) )
-    {
-      if ( pe == 1 )
+    if ( isOn( SW_USE_EZGCD ) )
+    {
+      fc= ezgcd (fc, gc);
+      /*if ( pe == 1 )
         fc = ezgcd( fc, gc );
       else if ( pe > 0 )// no variable at position 1
@@ -791,5 +774,23 @@
         gc = swapvar( gc, Variable(pe), Variable(1) );
         fc = swapvar( ezgcd( fc, gc ), Variable(1), Variable(pe) );
+      }*/
+    }
+    else if (
+    isOn(SW_USE_CHINREM_GCD)
+    && (isPurePoly_m(fc)) && (isPurePoly_m(gc))
+    )
+    {
+    #if 0
+      if ( p1 == fc.level() )
+        fc = chinrem_gcd( fc, gc );
+      else
+      {
+        fc = replacevar( fc, Variable(p1), Variable(mp) );
+        gc = replacevar( gc, Variable(p1), Variable(mp) );
+        fc = replacevar( chinrem_gcd( fc, gc ), Variable(mp), Variable(p1) );
       }
+    #else
+      fc = chinrem_gcd( fc, gc);
+    #endif
     }
     else
Index: factory/fac_ezgcd.cc
===================================================================
--- factory/fac_ezgcd.cc	(revision a9a6dcbcbc4f0be99516f14eae42b1776235ca9f)
+++ factory/fac_ezgcd.cc	(revision f7a4e9271997208f4ee40a14fd1e1b5c6c0c1ffc)
@@ -16,4 +16,318 @@
 #include "fac_distrib.h"
 #include "templates/ftmpl_functions.h"
+#include "cf_map.h"
+#include "facHensel.h"
+
+static
+int compress4EZGCD (const CanonicalForm& F, const CanonicalForm& G, CFMap & M,
+                    CFMap & N, int& both_non_zero)
+{
+  int n= tmax (F.level(), G.level());
+  int * degsf= new int [n + 1];
+  int * degsg= new int [n + 1];
+
+  for (int i = 0; i <= n; i++)
+    degsf[i]= degsg[i]= 0;
+
+  degsf= degrees (F, degsf);
+  degsg= degrees (G, degsg);
+
+  both_non_zero= 0;
+  int f_zero= 0;
+  int g_zero= 0;
+
+  for (int i= 1; i <= n; i++)
+  {
+    if (degsf[i] != 0 && degsg[i] != 0)
+    {
+      both_non_zero++;
+      continue;
+    }
+    if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
+    {
+      f_zero++;
+      continue;
+    }
+    if (degsg[i] == 0 && degsf[i] && i <= F.level())
+    {
+      g_zero++;
+      continue;
+    }
+  }
+
+  if (both_non_zero == 0)
+  {
+    delete [] degsf;
+    delete [] degsg;
+    return 0;
+  }
+
+  // map Variables which do not occur in both polynomials to higher levels
+  int k= 1;
+  int l= 1;
+  for (int i= 1; i <= n; i++)
+  {
+    if (degsf[i] != 0 && degsg[i] == 0 && i <= F.level())
+    {
+      if (k + both_non_zero != i)
+      {
+        M.newpair (Variable (i), Variable (k + both_non_zero));
+        N.newpair (Variable (k + both_non_zero), Variable (i));
+      }
+      k++;
+    }
+    if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
+    {
+      if (l + g_zero + both_non_zero != i)
+      {
+        M.newpair (Variable (i), Variable (l + g_zero + both_non_zero));
+        N.newpair (Variable (l + g_zero + both_non_zero), Variable (i));
+      }
+      l++;
+    }
+  }
+
+  // sort Variables x_{i} in decreasing order of
+  // min(deg_{x_{i}}(f),deg_{x_{i}}(g))
+  int m= tmin (F.level(), G.level());
+  int max_min_deg;
+  k= both_non_zero;
+  l= 0;
+  int i= 1;
+  while (k > 0)
+  {
+    max_min_deg= tmin (degsf[i], degsg[i]);
+    while (max_min_deg == 0)
+    {
+      i++;
+      max_min_deg= tmin (degsf[i], degsg[i]);
+    }
+    for (int j= i + 1; j <= m; j++)
+    {
+      if ((tmin (degsf[j],degsg[j]) < max_min_deg) &&
+          (tmin (degsf[j], degsg[j]) != 0))
+      {
+        max_min_deg= tmin (degsf[j], degsg[j]);
+        l= j;
+      }
+    }
+
+    if (l != 0)
+    {
+      if (l != k)
+      {
+        M.newpair (Variable (l), Variable(k));
+        N.newpair (Variable (k), Variable(l));
+        degsf[l]= 0;
+        degsg[l]= 0;
+        l= 0;
+      }
+      else
+      {
+        degsf[l]= 0;
+        degsg[l]= 0;
+        l= 0;
+      }
+    }
+    else if (l == 0)
+    {
+      if (i != k)
+      {
+        M.newpair (Variable (i), Variable (k));
+        N.newpair (Variable (k), Variable (i));
+        degsf[i]= 0;
+        degsg[i]= 0;
+      }
+      else
+      {
+        degsf[i]= 0;
+        degsg[i]= 0;
+      }
+      i++;
+    }
+    k--;
+  }
+
+  delete [] degsf;
+  delete [] degsg;
+
+  return both_non_zero;
+}
+
+static inline
+CanonicalForm myShift2Zero (const CanonicalForm& F, CFList& Feval,
+                            const CFList& evaluation)
+{
+  CanonicalForm A= F;
+  int k= 2;
+  for (CFListIterator i= evaluation; i.hasItem(); i++, k++)
+    A= A (Variable (k) + i.getItem(), k);
+
+  CanonicalForm buf= A;
+  Feval= CFList();
+  Feval.append (buf);
+  for (k= evaluation.length() + 1; k > 2; k--)
+  {
+    buf= mod (buf, Variable (k));
+    Feval.insert (buf);
+  }
+  return A;
+}
+
+static inline
+CanonicalForm myReverseShift (const CanonicalForm& F, const CFList& evaluation)
+{
+  int l= evaluation.length() + 1;
+  CanonicalForm result= F;
+  CFListIterator j= evaluation;
+  for (int i= 2; i < l + 1; i++, j++)
+  {
+    if (F.level() < i)
+      continue;
+    result= result (Variable (i) - j.getItem(), i);
+  }
+  return result;
+}
+
+static inline
+Evaluation optimize4Lift (const CanonicalForm& F, CFMap & M,
+                    CFMap & N, const Evaluation& A)
+{
+  int n= F.level();
+  int * degsf= new int [n + 1];
+
+  for (int i = 0; i <= n; i++)
+    degsf[i]= 0;
+
+  degsf= degrees (F, degsf);
+
+  Evaluation result= Evaluation (A.min(), A.max());
+  ASSERT (A.min() == 2, "expected A.min() == 2");
+  ASSERT (A.max() == n, "expected A.max() == n");
+  int max_deg;
+  int k= n;
+  int l= 1;
+  int i= 2;
+  int pos= 2;
+  while (k > 1)
+  {
+    max_deg= degsf [i];
+    while (max_deg == 0)
+    {
+      i++;
+      max_deg= degsf [i];
+    }
+    l= i;
+    for (int j= i + 1; j <=  n; j++)
+    {
+      if (degsf[j] > max_deg)
+      {
+        max_deg= degsf[j];
+        l= j;
+      }
+    }
+
+    if (l <= n)
+    {
+      if (l != pos)
+      {
+        result.setValue (pos, A [l]);
+        M.newpair (Variable (l), Variable (pos));
+        N.newpair (Variable (pos), Variable (l));
+        degsf[l]= 0;
+        l= 2;
+        if (k == 2 && n == 3)
+        {
+          result.setValue (l, A [pos]);
+          M.newpair (Variable (pos), Variable (l));
+          N.newpair (Variable (l), Variable (pos));
+          degsf[pos]= 0;
+        }
+      }
+      else
+      {
+        result.setValue (l, A [l]);
+        degsf [l]= 0;
+      }
+    }
+    pos++;
+    k--;
+    l= 2;
+  }
+
+  delete [] degsf;
+
+  return result;
+}
+
+static inline
+int Hensel (const CanonicalForm & UU, CFArray & G, const Evaluation & AA,
+            const CFArray& LeadCoeffs )
+{
+  CFList factors;
+  factors.append (G[1]);
+  factors.append (G[2]);
+
+  CFMap NN, MM;
+  Evaluation A= optimize4Lift (UU, MM, NN, AA);
+
+  CanonicalForm U= MM (UU);
+  CFArray LCs= CFArray (1,2);
+  LCs [1]= MM (LeadCoeffs [1]);
+  LCs [2]= MM (LeadCoeffs [2]);
+
+  CFList evaluation;
+  for (int i= A.min(); i <= A.max(); i++)
+    evaluation.append (A [i]);
+  CFList UEval;
+  CanonicalForm shiftedU= myShift2Zero (U, UEval, evaluation);
+
+  if (size (shiftedU)/getNumVars (U) > 500)
+    return -1;
+
+  CFArray shiftedLCs= CFArray (2);
+  CFList shiftedLCsEval1, shiftedLCsEval2;
+  shiftedLCs[0]= myShift2Zero (LCs[1], shiftedLCsEval1, evaluation);
+  shiftedLCs[1]= myShift2Zero (LCs[2], shiftedLCsEval2, evaluation);
+  factors.insert (1);
+  int liftBound= degree (UEval.getLast(), 2) + 1;
+  CFArray Pi;
+  CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
+  CFList diophant;
+  CFArray lcs= CFArray (2);
+  lcs [0]= shiftedLCsEval1.getFirst();
+  lcs [1]= shiftedLCsEval2.getFirst();
+  nonMonicHenselLift12 (UEval.getFirst(), factors, liftBound, Pi, diophant, M,
+                        lcs, false);
+
+  for (CFListIterator i= factors; i.hasItem(); i++)
+  {
+    if (!fdivides (i.getItem(), UEval.getFirst()))
+      return 0;
+  }
+
+  int * liftBounds;
+  bool noOneToOne= false;
+  if (U.level() > 2)
+  {
+    liftBounds= new int [U.level() - 1]; /* index: 0.. U.level()-2 */
+    liftBounds[0]= liftBound;
+    for (int i= 1; i < U.level() - 1; i++)
+      liftBounds[i]= degree (shiftedU, Variable (i + 2)) + 1;
+    factors= nonMonicHenselLift2 (UEval, factors, liftBounds, U.level() - 1,
+                                  false, shiftedLCsEval1, shiftedLCsEval2, Pi,
+                                  diophant, noOneToOne);
+    delete [] liftBounds;
+    if (noOneToOne)
+      return 0;
+  }
+  G[1]= factors.getFirst();
+  G[2]= factors.getLast();
+  G[1]= myReverseShift (G[1], evaluation);
+  G[2]= myReverseShift (G[2], evaluation);
+  G[1]= NN (G[1]);
+  G[2]= NN (G[2]);
+  return 1;
+}
 
 static void findeval( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db, REvaluation & b, int delta, int degF, int degG );
@@ -37,5 +351,5 @@
 ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b, bool internal )
 {
-    CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG, lcD;
+    CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG, lcD, cand, result;
     CFArray DD( 1, 2 ), lcDD( 1, 2 );
     int degF, degG, delta, t;
@@ -45,11 +359,24 @@
     modpk bound;
 
+    F= FF;
+    G= GG;
+
+    CFMap M,N;
+    int smallestDegLev;
+    int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
+
+    if (best_level == 0) return G.genOne();
+
+    F= M (F);
+    G= M (G);
+
+
     DEBINCLEVEL( cerr, "ezgcd" );
     DEBOUTLN( cerr, "FF = " << FF );
     DEBOUTLN( cerr, "GG = " << GG );
-    f = content( FF, x ); g = content( GG, x ); d = gcd( f, g );
+    f = content( F, x ); g = content( G, x ); d = gcd( f, g );
     DEBOUTLN( cerr, "f = " << f );
     DEBOUTLN( cerr, "g = " << g );
-    F = FF / f; G = GG / g;
+    F /= f; G /= g;
     if ( F.isUnivariate() && G.isUnivariate() )
     {
@@ -57,10 +384,10 @@
         if(F.mvar()==G.mvar())
           d*=gcd(F,G);
-        return d;
+        return N (d);
     }
     else  if ( gcd_test_one( F, G, false ) )
     {
         DEBDECLEVEL( cerr, "ezgcd" );
-        return d;
+        return N (d);
     }
     lcF = LC( F, x ); lcG = LC( G, x );
@@ -69,8 +396,9 @@
     degF = degree( F, x ); degG = degree( G, x );
     t = tmax( F.level(), G.level() );
-    bound = findBound( F, G, lcF, lcG, degF, degG );
+    //bound = findBound( F, G, lcF, lcG, degF, degG );
     if ( ! internal )
         b = REvaluation( 2, t, IntRandom( 25 ) );
-    while ( ! gcdfound ) {
+    while ( ! gcdfound )
+    {
         /// ---> A2
         DEBOUTLN( cerr, "search for evaluation, delta = " << delta );
@@ -87,5 +415,5 @@
         {
           DEBDECLEVEL( cerr, "ezgcd" );
-          return d;
+          return N (d);
         }
         /// ---> A4
@@ -98,5 +426,5 @@
             {
                 DEBDECLEVEL( cerr, "ezgcd" );
-                return d;
+                return N (d);
             }
             if ( dd /*degree( Dbt )*/ == delta )
@@ -110,18 +438,63 @@
         DEBOUTLN( cerr, "now after A4, delta = " << delta );
         /// ---> A5
-        if ( degF <= degG && delta == degF && fdivides( F, G ) )
+        if (delta == degF)
         {
+          if (degF <= degG  && fdivides (F, G))
+          {
             DEBDECLEVEL( cerr, "ezgcd" );
-            return d*F;
-        }
-        if ( degG < degF && delta == degG && fdivides( G, F ) )
+            return N (d*F);
+          }
+          else
+            delta--;
+        }
+        else if (delta == degG)
         {
+          if (degG <= degF && fdivides( G, F ))
+          {
             DEBDECLEVEL( cerr, "ezgcd" );
-            return d*G;
-        }
-        if ( delta != degF && delta != degG ) {
+            return N (d*G);
+          }
+          else
+            delta--;
+        }
+        if ( delta != degF && delta != degG )
+        {
+            /// ---> A6
             bool B_is_F;
-            /// ---> A6
-            CanonicalForm xxx;
+            CanonicalForm xxx1, xxx2;
+            CanonicalForm buf;
+            DD[1] = Fb / Db;
+            buf= Gb/Db;
+            xxx1 = gcd( DD[1], Db );
+            xxx2 = gcd( buf, Db );
+            if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
+                (size (F) <= size (G)))
+                 || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
+            {
+              B = F;
+              DD[2] = Db;
+              lcDD[1] = lcF;
+              lcDD[2] = lcD;
+              B_is_F = true;
+            }
+            else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
+                     (size (G) < size (F)))
+                     || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
+            {
+              DD[1] = buf;
+              B = G;
+              DD[2] = Db;
+              lcDD[1] = lcG;
+              lcDD[2] = lcD;
+              B_is_F = false;
+            }
+            else
+            {
+              Off(SW_USE_EZGCD);
+              result=gcd( F, G );
+              On(SW_USE_EZGCD);
+              return N (d*result);
+            }
+            /*CanonicalForm xxx;
             //if ( gcd( (DD[1] = Fb / Db), Db ) == 1 ) {
             DD[1] = Fb / Db;
@@ -165,9 +538,9 @@
 #endif
               }
-            }
+            }*/
             /// ---> A7
             DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
             DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
-            bound = enlargeBound( B, DD[2], DD[1], bound );
+            //bound = enlargeBound( B, DD[2], DD[1], bound );
             DEBOUTLN( cerr, "(hensel) B    = " << B );
             DEBOUTLN( cerr, "(hensel) lcB  = " << LC( B, Variable(1) ) );
@@ -175,33 +548,27 @@
             DEBOUTLN( cerr, "(hensel) DD   = " << DD );
             DEBOUTLN( cerr, "(hensel) lcDD = " << lcDD );
-            gcdfound = Hensel( B, DD, lcDD, b, bound, x );
+            gcdfound= Hensel (B*lcD, DD, b, lcDD);
             DEBOUTLN( cerr, "(hensel finished) DD   = " << DD );
+
+            if (gcdfound == -1)
+            {
+              Off (SW_USE_EZGCD);
+              result= gcd (F,G);
+              On (SW_USE_EZGCD_P);
+              return N (d*result);
+            }
 
             if (gcdfound)
             {
-              CanonicalForm xxx=content(DD[2],Variable(1));
-              CanonicalForm cand=DD[2] / xxx; //content(DD[2],Variable(1));
-#if 0
-              gcdfound= fdivides(cand,G) &&  fdivides(cand,F);
-#else
-              if (B_is_F /*B==F*lcF*/)
-              {
-                DEBOUTLN( cerr, "(test) G: "<<G<<" % gcd:"<<cand<<" -> " << G%cand );
-                gcdfound= fdivides(cand,G);
-              }
-              else
-              {
-                DEBOUTLN( cerr, "(test) F: "<<F<<" % gcd:"<<cand<<" -> " << F%cand);
-                gcdfound= fdivides(cand,F);
-              }
-#endif
+              cand = DD[2] / content( DD[2], Variable(1) );
+              gcdfound = fdivides( cand, G ) && fdivides ( cand, F );
             }
             /// ---> A8 (gcdfound)
         }
-        delta++;
+        delta--;
     }
     /// ---> A9
     DEBDECLEVEL( cerr, "ezgcd" );
-    return d * DD[2] / content(DD[2],Variable(1));
+    return N (d*cand);
 }
 
