Changeset d51d87 in git

Timestamp:

Aug 30, 2013, 7:45:42 PM (10 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')

Children:

c44f0c47dd0522db3b9d26283ffefec28e6d53aa

Parents:

62e51f3a438d0476a7cc82ebe3df5d93b7a740b0035b6439d8381335d8497466228554322c60d1de

Message:

Merge pull request #354 from mmklee/multi_sw

Multi sw: absolute factorization

Files:

• Singular/LIB/absfact.lib (modified) (9 diffs)
• Singular/extra.cc (modified) (2 diffs)
• Singular/misc_ip.cc (modified) (2 diffs)
• Tst/Short.lst (modified) (1 diff)
• Tst/Short/absbifact.res.gz.uu (deleted)
• Tst/Short/absbifact.stat (deleted)
• Tst/Short/absfact.res.gz.uu (added)
• Tst/Short/absfact.stat (added)
• Tst/Short/absfact.tst (moved) (moved from Tst/Short/absbifact.tst) (14 diffs)
• Tst/Short/ok_s.lst (modified) (1 diff)
• factory/Makefile.am (modified) (2 diffs)
• factory/cfNewtonPolygon.cc (modified) (5 diffs)
• factory/facAbsBiFact.cc (added)
• factory/facAbsBiFact.h (added)
• factory/facAbsFact.cc (modified) (4 diffs)
• factory/facAbsFact.h (modified) (2 diffs)
• factory/facFactorize.cc (modified) (8 diffs)
• factory/facFactorize.h (modified) (1 diff)
• factory/facFqBivarUtil.cc (modified) (9 diffs)
• factory/facFqBivarUtil.h (modified) (8 diffs)
• factory/facFqFactorize.cc (modified) (9 diffs)
• factory/facFqFactorize.h (modified) (7 diffs)
• libpolys/polys/clapsing.cc (modified) (3 diffs)
• libpolys/polys/clapsing.h (modified) (1 diff)

Singular/LIB/absfact.lib

@@ -7 +7 @@
          Gregoire Lecerf,      lecerf at math.uvsq.fr
          Gerhard Pfister,      pfister at mathematik.uni-kl.de
+         Martin Lee,           mlee at mathematik.uni-kl.de
 
 OVERVIEW:
@@ -16 +17 @@
 Then a minimal extension field is determined making use of the
 Rothstein-Trager partial fraction decomposition algorithm.
+absFactorizeBCG uses the algorithm of Bertone, Cheze and Galligo for bivariate
+polynomials and similar ideas as above to reduce to this case.
 
 REFERENCES:
 G. Cheze, G. Lecerf: Lifting and recombination techniques for absolute
                   factorization. Journal of Complexity, 23(3):380-420, 2007.
+C. Bertone, G. Cheze, and A. Galligo: Modular las vegas algorithms for
+                  polynomial absolute factorization. J. Symb. Comput.,
+                  45(12):1280-1295, December 2010
 
 KEYWORDS: factorization; absolute factorization.
@@ -26 +32 @@
 PROCEDURES:
   absFactorize();        absolute factorization of poly
-  absBiFactorize();      absolute factorization of bivariate poly
+  absFactorizeBCG();     absolute factorization of poly
 ";
 
@@ -611 +617 @@
 
 ////////////////////////////////////////////////////////////////////////////////
-proc absBiFactorize(poly p, list #)
-"USAGE:  absBiFactorize(p [,s]);   p poly, s string
+proc absFactorizeBCG(poly p, list #)
+"USAGE:  absFactorizeBCG(p [,s]);   p poly, s string
 ASSUME: coefficient field is the field of rational numbers or a
         transcendental extension thereof
@@ -637 +643 @@
         no field extension was necessary for the @code{j}th (class of)
         absolute factor(s).
-NOTE:   The input polynomial p is assumed to be bivariate or to contain one para-
-        meter and one variable. All factors are presented denominator- and 
-        content-free. The constant factor (first entry) is chosen such that the
-        product of all (!) the (denominator- and content-free) absolute factors
-        of @code{p} equals @code{p / absolute_factors[1][1]}.
+NOTE:   All factors are presented denominator- and content-free. The constant
+        factor (first entry) is chosen such that the product of all (!) the
+        (denominator- and content-free) absolute factors of @code{p} equals
+        @code{p / absolute_factors[1][1]}.
 SEE ALSO: factorize, absPrimdecGTZ, absFactorize
-EXAMPLE: example absBiFactorize; shows an example
+EXAMPLE: example absFactorizeBCG; shows an example
 "
 {
   int dblevel = printlevel - voice + 2;
-  dbprint(dblevel,"Entering absfact.lib::absBiFactorize with ",p);
+  dbprint(dblevel,"Entering absfact.lib::absFactorizeBCG with ",p);
   def MP = basering;
   int i;
   if (char(MP) != 0)
   {
-    ERROR("// absfact.lib::absBiFactorize is only implemented for "+
+    ERROR("// absfact.lib::absFactorizeBCG is only implemented for "+
           "characteristic 0");
   }
   if(minpoly!=0)
   {
-    ERROR("// absfact.lib::absBiFactorize is not implemented for algebraic "
+    ERROR("// absfact.lib::absFactorizeBCG is not implemented for algebraic "
           +"extensions");
   }
@@ -745 +750 @@
   poly p=imap(MP,p);
 
-  if (size (variables (p)) > 2)
-  {
-    ERROR("// absfact.lib::absBiFactorize is not implemented for polynomials "
-          +"with more than 2 variables");
-  }
-
   // special treatment in the homogeneous case, dropping one variable
   // by substituting the first variable by 1
@@ -761 +760 @@
   }
 
-  list tmpf=system ("absBiFact", p);
+  list tmpf=system ("absFact", p);
 
   // the homogeneous case, homogenizing the result
@@ -824 +823 @@
 
   dbprint( printlevel-voice+3,"
-// 'absBiFactorize' created a ring, in which a list absolute_factors (the
+// 'absFactorizeBCG' created a ring, in which a list absolute_factors (the
 // absolute factors) is stored.
 // To access the list of absolute factors, type (if the name S was assigned
@@ -836 +835 @@
   ring R = (0), (x,y), lp;
   poly p = (-7*x^2 + 2*x*y^2 + 6*x + y^4 + 14*y^2 + 47)*(5x2+y2)^3*(x-y)^4;
-  def S = absBiFactorize(p) ;
+  def S = absFactorizeBCG(p) ;
   setring(S);
   absolute_factors;

Singular/extra.cc

@@ -3696 +3696 @@
       else
   /*================= absBiFact ======================*/
-      if (strcmp(sys_cmd, "absBiFact") == 0)
+      if (strcmp(sys_cmd, "absFact") == 0)
       {
         if (h!=NULL)
@@ -3706 +3706 @@
             ideal mipos= NULL;
             int n= 0;
-            ideal f=singclap_absBiFactorize((poly)(h->Data()), mipos, &v, n, currRing);
+            ideal f=singclap_absFactorize((poly)(h->Data()), mipos, &v, n, currRing);
             if (f==NULL) return TRUE;
             ivTest(v);

Singular/misc_ip.cc

@@ -769 +769 @@
 }
 
+/* version strings */
+#ifdef HAVE_FLINT
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+#ifndef __GMP_BITS_PER_MP_LIMB
+#define __GMP_BITS_PER_MP_LIMB GMP_LIMB_BITS
+#endif
+#include <flint/flint.h>
+#ifdef __cplusplus
+}
+#endif
+#endif
+
 char * versionString()
 {
@@ -797 +812 @@
 #endif
 
+#ifdef HAVE_FACTORY
 #ifdef HAVE_FLINT
-// #include <NTL/version.h>
-              StringAppend("FLINT(??){'%s','%s'},", FLINT_CFLAGS, FLINT_LIBS);
-#endif
-   
+              StringAppend("FLINT(%s){'%s','%s'},",version, FLINT_CFLAGS, FLINT_LIBS);
+#endif
+#endif
 
 #if SIZEOF_VOIDP == 8

Tst/Short.lst

@@ -1 @@
-Short/absbifact.tst
+Short/absfact.tst
 Short/alexpoly.tst
 Short/algebralib.tst

Tst/Short/absfact.tst

@@ -12 +12 @@
 absolute_factors;
 setring R;
-def T= absBiFactorize (p);
+def T= absFactorizeBCG (p);
 setring T;
 short= 0;
@@ -26 +26 @@
 absolute_factors;
 setring R;
-def T= absBiFactorize (p);
+def T= absFactorizeBCG (p);
 setring T;
 short= 0;
@@ -36 +36 @@
 poly p = (5x2+y2);
 absFactorize(p,77) ;
-absBiFactorize (p,77);
+absFactorizeBCG (p,77);
 
 kill R;
@@ -47 +47 @@
 absolute_factors;
 setring R;
-def T= absBiFactorize (p);
+def T= absFactorizeBCG (p);
 setring T;
 short= 0;
@@ -59 +59 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p, "s");
+def T= absFactorizeBCG(p, "s");
 setring T;
 absolute_factors;
@@ -70 +70 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p);
+def T= absFactorizeBCG(p);
 setring T;
 absolute_factors;
@@ -81 +81 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p);
+def T= absFactorizeBCG(p);
 setring T;
 absolute_factors;
@@ -92 +92 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p);
+def T= absFactorizeBCG(p);
 setring T;
 absolute_factors;
@@ -103 +103 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p);
+def T= absFactorizeBCG(p);
 setring T;
 absolute_factors;
@@ -114 +114 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p,"s");
+def T= absFactorizeBCG(p,"s");
 setring T;
 absolute_factors;
@@ -125 +125 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p,"s");
+def T= absFactorizeBCG(p,"s");
 setring T;
 absolute_factors;
@@ -136 +136 @@
 absolute_factors;
 setring r;
-def T= absBiFactorize(p,"s");
+def T= absFactorizeBCG(p,"s");
 setring T;
 absolute_factors;
@@ -146 +146 @@
 absolute_factors;
 setring R1;
-def T= absBiFactorize(f);
+def T= absFactorizeBCG(f);
 setring T;
 absolute_factors;
@@ -156 +156 @@
 absolute_factors;
 setring R3;
-def T=absBiFactorize (f3);
+def T=absFactorizeBCG (f3);
+setring T;
+absolute_factors;
+
+ring r2=0,(x,y,z,w),dp;
+poly f=(x2+y2+z2)^2+w4;
+def S =absFactorize(f);
+setring(S);
+absolute_factors;
+setring r2;
+def T=absFactorizeBCG (f);
+setring T;
+absolute_factors;
+
+ring r1=(0,a,b),(x,y),dp;
+poly p=(a3-a2b+27ab3-27b4)/(a+b5)*x2+(a2+27b3)*y;
+def S = absFactorize(p);
+setring(S);
+absolute_factors;
+setring r1;
+def T=absFactorizeBCG (p);
+setring T;
+absolute_factors;
+
+ring r3=0,(x,y,z,w),dp;
+poly f=(x2+y2+z2)^4+w8;
+tst_status();
+def S =absFactorize(f);
+tst_status();
+setring(S);
+absolute_factors;
+setring r3;
+tst_status();
+def T=absFactorizeBCG (f);
+tst_status();
+setring T;
+absolute_factors;
+
+ring R = 0, (x,y,z), dp;
+poly f = y4+z2-y2*(1-x2);
+def S = absFactorize(f);
+setring S;
+absolute_factors;
+setring R;
+def T=absFactorizeBCG (f);
 setring T;
 absolute_factors;

Tst/Short/ok_s.lst

@@ -1 +1 @@
 ;; Test which should pass shifted exponents
-absbifact
+absfact
 abusalem
 alexpoly

factory/Makefile.am

@@ -63 +63 @@
                 DegreePattern.cc \
                 ExtensionInfo.cc \
+                facAbsBiFact.cc \
                 facAbsFact.cc \
                 facAlgExt.cc \
@@ -146 +147 @@
                 DegreePattern.h \
                 ExtensionInfo.h \
+                facAbsBiFact.h \
                 facAbsFact.h \
                 facAlgExt.h \

factory/cfNewtonPolygon.cc

@@ -65 +65 @@
 bool isLess (int* point1, int* point2)
 {
-  int area= point1[0]*point2[1]- point1[1]*point2[0];
+  long area= point1[0]*point2[1]- point1[1]*point2[0];
   if (area > 0) return true;
   if (area == 0)
@@ -108 +108 @@
 bool isConvex (int* point1, int* point2, int* point3)
 {
-  int relArea= (point1[0] - point2[0])*(point3[1] - point2[1]) -
-               (point1[1] - point2[1])*(point3[0] - point2[0]);
+  long relArea= (point1[0] - point2[0])*(point3[1] - point2[1]) -
+                (point1[1] - point2[1])*(point3[0] - point2[0]);
   if (relArea < 0)
     return true;
@@ -153 +153 @@
   if (i + 1 <= sizePoints || i == sizePoints)
   {
-    int relArea=
+    long relArea=
     (points [i-2][0] - points [i-1][0])*(points [0][1] - points [i-1][1])-
     (points [i-2][1] - points [i-1][1])*(points [0][0] - points [i-1][0]);
@@ -1173 +1173 @@
 
   if (isRat)
+  {
     ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
+  }
 
   CanonicalForm Fp, N= maxNorm (F);
@@ -1250 +1252 @@
 
   if (isRat)
+  {
     ASSERT (bCommonDen (F).isOne(), "poly over Z expected");
+  }
 
   Variable x= Variable (1);

factory/facAbsFact.cc

@@ -16 +16 @@
 #include "debug.h"
 
+#include "facAbsBiFact.h"
 #include "facAbsFact.h"
-#include "facBivar.h"
-#include "facFqBivar.h"
+#include "facFqFactorize.h"
+#include "facFqFactorizeUtil.h"
+#include "facHensel.h"
+#include "facSparseHensel.h"
+#include "facFactorize.h"
 #include "cf_reval.h"
 #include "cf_primes.h"
 #include "cf_algorithm.h"
+#include "cfModResultant.h"
 #ifdef HAVE_FLINT
 #include "FLINTconvert.h"
-#include <flint/fmpz_poly_factor.h>
 #endif
 #ifdef HAVE_NTL
@@ -32 +36 @@
 
 #ifdef HAVE_NTL
-
-TIMING_DEFINE_PRINT(fac_Qa_factorize)
-TIMING_DEFINE_PRINT(fac_evalpoint)
-
-//TODO optimize choice of p -> choose p as large as possible (better than small p since factorization mod p does not require field extension, also less lifting)
-int choosePoint (const CanonicalForm& F, int tdegF, CFArray& eval, bool rec)
+TIMING_DEFINE_PRINT(abs_fac_bi_factorizer)
+TIMING_DEFINE_PRINT(abs_fac_hensel_lift)
+TIMING_DEFINE_PRINT(abs_fac_factor_recombination)
+TIMING_DEFINE_PRINT(abs_fac_shift_to_zero)
+TIMING_DEFINE_PRINT(abs_fac_precompute_leadcoeff)
+TIMING_DEFINE_PRINT(abs_fac_evaluation)
+TIMING_DEFINE_PRINT(abs_fac_recover_factors)
+TIMING_DEFINE_PRINT(abs_fac_bifactor_total)
+TIMING_DEFINE_PRINT(abs_fac_luckswang)
+TIMING_DEFINE_PRINT(abs_fac_lcheuristic)
+TIMING_DEFINE_PRINT(abs_fac_cleardenom)
+TIMING_DEFINE_PRINT(abs_fac_compress)
+
+/// steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular
+/// Introduction to Commutative Algebra"
+CFAFList
+RothsteinTragerResultant (const CanonicalForm& F, const CanonicalForm& w, int s,
+                          const CFList& evaluation, const Variable& y)
 {
-  REvaluation E1 (1, 1, IntRandom (25));
-  REvaluation E2 (2, 2, IntRandom (25));
-  if (rec)
-  {
-    E1.nextpoint();
-    E2.nextpoint();
-  }
-  CanonicalForm f, f1, f2, Fp;
-  int i, p;
-  eval=CFArray (2);
-  while (1)
-  {
-    f1= E1(F);
-    if (!f1.isZero() && factorize (f1).length() == 2)
-    {
-      Off (SW_RATIONAL);
-      f= E2(f1);
-      f2= E2 (F);
-      if ((!f.isZero()) && (abs(f)>cf_getSmallPrime (cf_getNumSmallPrimes()-1)))
-      {
-        for (i= cf_getNumPrimes()-1; i >= 0; i--)
-        {
-          if (f % CanonicalForm (cf_getPrime (i)) == 0)
-          {
-            p= cf_getPrime(i);
-            Fp= mod (F,p);
-            if (totaldegree (Fp) == tdegF &&
-                degree (mod (f2,p), 1) == degree (F,1) &&
-                degree (mod (f1, p),2) == degree (F,2))
-            {
-              eval[0]= E1[1];
-              eval[1]= E2[2];
-              return p;
-            }
-          }
-        }
-      }
-      else if (!f.isZero())
-      {
-        for (i= cf_getNumSmallPrimes()-1; i >= 0; i--)
-        {
-          if (f % CanonicalForm (cf_getSmallPrime (i)) == 0)
-          {
-            p= cf_getSmallPrime (i);
-            Fp= mod (F,p);
-            if (totaldegree (Fp) == tdegF &&
-                degree (mod (f2, p),1) == degree (F,1) &&
-                degree (mod (f1,p),2) == degree (F,2))
-            {
-              eval[0]= E1[1];
-              eval[1]= E2[2];
-              return p;
-            }
-          }
-        }
-      }
-      E2.nextpoint();
-      On (SW_RATIONAL);
-    }
-    E1.nextpoint();
-  }
-  return 0;
+  CFList terms;
+  for (CFIterator i= w; i.hasTerms(); i++)
+    terms.append (i.coeff());
+
+  Variable x= Variable (1);
+  CanonicalForm derivF= deriv (F, x);
+  CanonicalForm g, geval, derivFeval, Feval, H, res, sqrfPartRes;
+  CFListIterator iter;
+
+  REvaluation E (1, terms.length(), IntRandom (25));
+
+  do
+  {
+    E.nextpoint();
+    g= 0;
+    iter= terms;
+    for (int i= terms.length(); i >= 1; i--, iter++)
+      g += E[i]*iter.getItem();
+
+    geval= g;
+    Feval= F;
+    derivFeval= derivF;
+    iter= evaluation;
+    for (int i= F.level(); i >= 2; iter++, i--)
+    {
+      Feval= Feval (iter.getItem(), i);
+      geval= geval (iter.getItem(), i);
+      derivFeval= derivFeval (iter.getItem(), i);
+    }
+
+    H= y*derivFeval-geval;
+
+    if (degree (Feval, x) >= 8 || degree (H, x) >= 8)
+      res= resultantZ (Feval, H, x);
+    else
+      res= resultant (Feval, H, x);
+
+    sqrfPartRes= sqrfPart (res); //univariate poly in y
+  }
+  while (degree (sqrfPartRes) != s);
+
+  Variable beta= rootOf (sqrfPartRes);
+
+  CanonicalForm factor= gcd (F, beta*derivF-g);
+
+  return CFAFList (CFAFactor (factor, getMipo (beta), 1));
 }
 
-//G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
-CFAFList absFactorizeMain (const CanonicalForm& G)
+
+/// Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative
+/// Algebra"
+CFAFList
+RothsteinTrager (const CanonicalForm& F, const CFList& factors,
+                 const Variable& alpha, const CFList& evaluation)
 {
-  CanonicalForm F= bCommonDen (G)*G;
-  Off (SW_RATIONAL);
-  F /= icontent (F);
-  On (SW_RATIONAL);
-  CFArray eval;
-  int minTdeg, tdegF= totaldegree (F);
-  CanonicalForm Fp, smallestFactor;
-  int p;
-  CFFList factors;
-  Variable alpha;
-  bool rec= false;
   Variable x= Variable (1);
-  Variable y= Variable (2);
-  CanonicalForm bufF= F;
-  CFFListIterator iter;
-differentevalpoint:
-  while (1)
-  {
-    TIMING_START (fac_evalpoint);
-    p= choosePoint (F, tdegF, eval, rec);
-    TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
-
-    setCharacteristic (p);
-    Fp=F.mapinto();
-    factors= factorize (Fp);
-
-    if (factors.getFirst().factor().inCoeffDomain())
-      factors.removeFirst();
-
-    if (factors.length() == 1 && factors.getFirst().exp() == 1)
-    {
-      if (absIrredTest (Fp))
-      {
-        setCharacteristic(0);
-        return CFAFList (CFAFactor (G, 1, 1));
-      }
+  ASSERT (factors.length() == 2, "expected two factors");
+  CanonicalForm G, H;
+  if (totaldegree (factors.getFirst()) > totaldegree (factors.getLast()))
+  {
+    H= factors.getLast();
+    G= factors.getFirst();
+  }
+  else
+  {
+    H= factors.getFirst();
+    G= factors.getLast();
+  }
+  CanonicalForm derivH= deriv (H, x);
+  CanonicalForm w= G*derivH;
+  Variable y= Variable (F.level()+1);
+  w= replacevar (w, alpha, y);
+
+  int s= totaldegree (F)/totaldegree (H);
+
+  return RothsteinTragerResultant (F, w, s, evaluation, y);
+}
+
+CFList
+evalPoints4AbsFact (const CanonicalForm& F, CFList& eval, Evaluation& E,
+                    int& intervalSize)
+{
+  CFList result;
+  Variable x= Variable (1);
+
+  CanonicalForm LCF= LC (F, x);
+  CFList LCFeval= CFList();
+
+  bool found= false;
+  bool allZero= true;
+  bool foundZero= false;
+  CanonicalForm deriv_x, gcd_deriv;
+  CFFList uniFactors;
+  CFListIterator iter;
+  int count= 0;
+  do
+  {
+    count++;
+    if (count==E.max() - E.min() + 1)
+    {
+      count= 1;
+      intervalSize++;
+      E= REvaluation (E.min(), E.max(), IntRandom (intervalSize));
+      E.nextpoint();
+    }
+    eval.insert (F);
+    LCFeval.insert (LCF);
+    bool bad= false;
+    for (int i= E.max(); i >= E.min(); i--)
+    {
+      eval.insert (eval.getFirst()( E [i], i));
+      LCFeval.insert (LCFeval.getFirst()( E [i], i));
+      result.append (E[i]);
+      if (!E[i].isZero())
+        allZero= false;
       else
-      {
-        setCharacteristic (0);
-        if (modularIrredTestWithShift (F))
-        {
-          return CFAFList (CFAFactor (G, 1, 1));
-        }
-        rec= true;
-        continue;
-      }
-    }
-    iter= factors;
-    smallestFactor= iter.getItem().factor();
-    while (smallestFactor.isUnivariate() && iter.hasItem())
-    {
-      iter++;
-      if (!iter.hasItem())
+        foundZero= true;
+      if (!allZero && foundZero)
+      {
+        result= CFList();
+        eval= CFList();
+        LCFeval= CFList();
+        bad= true;
+        foundZero= false;
         break;
-      smallestFactor= iter.getItem().factor();
-    }
-
-    minTdeg= totaldegree (smallestFactor);
-    if (iter.hasItem())
-      iter++;
-    for (; iter.hasItem(); iter++)
-    {
-      if (!iter.getItem().factor().isUnivariate() &&
-          (totaldegree (iter.getItem().factor()) < minTdeg))
-      {
-        smallestFactor= iter.getItem().factor();
-        minTdeg= totaldegree (smallestFactor);
-      }
-    }
-    if (tdegF % minTdeg == 0)
-      break;
-    setCharacteristic(0);
-    rec=true;
-  }
-  CanonicalForm Gp= Fp/smallestFactor;
-  Gp= Gp /Lc (Gp);
-
-  CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
-  CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
-  CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
-  CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
-
-  bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
-               !gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
-  bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
-               !gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
-  if (!xValid && !yValid)
-  {
-    rec= true;
-    setCharacteristic (0);
-    goto differentevalpoint;
-  }
-
-  setCharacteristic (0);
-
-  CanonicalForm mipo;
-
-  int loop, i;
-  if (xValid && yValid)
-  {
-    loop= 3;
-    i=1;
-  }
-  else if (xValid)
-  {
-    loop= 3;
-    i=2;
-  }
-  else
-  {
-    loop= 2;
-    i=1;
-  }
-
-  CFArray mipos= CFArray (loop-i);
-  for (; i < loop; i++)
-  {
-    CanonicalForm Fi= F(eval[i-1],i);
-
-    int s= tdegF/minTdeg + 1;
-    CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
-    bound *= power (CanonicalForm (s),s-1);
-    bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
-
-    CanonicalForm B = p;
-    long k = 1L;
-    while ( B < bound ) {
-      B *= p;
-      k++;
-    }
-
-    //TODO take floor (log2(k))
-    k= k+1;
-#ifdef HAVE_FLINT
-    fmpz_poly_t FLINTFi;
-    convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
-    setCharacteristic (p);
-    nmod_poly_t FLINTFpi, FLINTGpi;
-    if (i == 2)
-    {
-      convertFacCF2nmod_poly_t (FLINTFpi,
-                                smallestFactorEvalx/lc (smallestFactorEvalx));
-      convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
-    }
-    else
-    {
-      convertFacCF2nmod_poly_t (FLINTFpi,
-                                smallestFactorEvaly/lc (smallestFactorEvaly));
-      convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
-    }
-    nmod_poly_factor_t nmodFactors;
-    nmod_poly_factor_init (nmodFactors);
-    nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
-    nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
-
-    long * link= new long [2];
-    fmpz_poly_t *v= new fmpz_poly_t[2];
-    fmpz_poly_t *w= new fmpz_poly_t[2];
-    fmpz_poly_init(v[0]);
-    fmpz_poly_init(v[1]);
-    fmpz_poly_init(w[0]);
-    fmpz_poly_init(w[1]);
-
-    fmpz_poly_factor_t liftedFactors;
-    fmpz_poly_factor_init (liftedFactors);
-    _fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
-                                  nmodFactors, k);
-
-    nmod_poly_factor_clear (nmodFactors);
-    nmod_poly_clear (FLINTFpi);
-    nmod_poly_clear (FLINTGpi);
-
-    setCharacteristic(0);
-    CanonicalForm liftedSmallestFactor=
-    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
-
-    CanonicalForm otherFactor=
-    convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
-    modpk pk= modpk (p, k);
-#else
-    modpk pk= modpk (p, k);
-    ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
-    setCharacteristic (p);
-
-    if (fac_NTL_char != p)
-    {
-      fac_NTL_char= p;
-      zz_p::init (p);
-    }
-    zz_pX NTLFpi, NTLGpi;
-    if (i == 2)
-    {
-      NTLFpi= convertFacCF2NTLzzpX (smallestFactorEvalx/lc (smallestFactorEvalx));
-      NTLGpi= convertFacCF2NTLzzpX (Gpx/lc (Gpx));
-    }
-    else
-    {
-      NTLFpi= convertFacCF2NTLzzpX (smallestFactorEvaly/lc (smallestFactorEvaly));
-      NTLGpi= convertFacCF2NTLzzpX (Gpy/lc (Gpy));
-    }
-    vec_zz_pX modFactors;
-    modFactors.SetLength(2);
-    modFactors[0]= NTLFpi;
-    modFactors[1]= NTLGpi;
-    vec_ZZX liftedFactors;
-    MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
-    setCharacteristic(0);
-    CanonicalForm liftedSmallestFactor=
-                  convertNTLZZX2CF (liftedFactors[0], x);
-
-    CanonicalForm otherFactor=
-                  convertNTLZZX2CF (liftedFactors[1], x);
-#endif
-
-    Off (SW_SYMMETRIC_FF);
-    liftedSmallestFactor= pk (liftedSmallestFactor);
-    if (i == 2)
-      liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
-    else
-      liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
-
-    On (SW_SYMMETRIC_FF);
-    CFMatrix M= CFMatrix (s, s);
-    M(s,s)= power (CanonicalForm (p), k);
-    for (int j= 1; j < s; j++)
-    {
-      M (j,j)= 1;
-      M (j+1,j)= -liftedSmallestFactor;
-    }
-
-    mat_ZZ NTLM= *convertFacCFMatrix2NTLmat_ZZ (M);
-
-    ZZ det;
-
-    transpose (NTLM, NTLM);
-    (void) LLL (det, NTLM, 1L, 1L); //use floating point LLL ?
-    transpose (NTLM, NTLM);
-    M= *convertNTLmat_ZZ2FacCFMatrix (NTLM);
-
-    mipo= 0;
-    for (int j= 1; j <= s; j++)
-      mipo += M (j,1)*power (x,s-j);
-
-    CFFList mipoFactors= factorize (mipo);
-    mipoFactors.removeFirst();
-
-#ifdef HAVE_FLINT
-    fmpz_poly_clear (v[0]);
-    fmpz_poly_clear (v[1]);
-    fmpz_poly_clear (w[0]);
-    fmpz_poly_clear (w[1]);
-    delete [] v;
-    delete [] w;
-    delete [] link;
-    fmpz_poly_factor_clear (liftedFactors);
-#endif
-
-    if (mipoFactors.length() > 1 ||
-        (mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1))
-    {
-      if (i+1 >= loop && ((loop-i == 1) || (loop-i==2 && mipos[0].isZero())))
-      {
-        rec=true;
-        goto differentevalpoint;
-      }
-    }
-    else
-      mipos[loop-i-1]= mipo;
-  }
-
-  On (SW_RATIONAL);
-  if (xValid && yValid && !mipos[0].isZero() && !mipos[1].isZero())
-  {
-    if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
-      alpha= rootOf (mipos[0]);
-    else
-      alpha= rootOf (mipos[1]);
-  }
-  else if (xValid && yValid)
-  {
-    if (mipos[0].isZero())
-      alpha= rootOf (mipos[1]);
-    else
-      alpha= rootOf (mipos[0]);
-  }
-  else
-    alpha= rootOf (mipo);
-
-  CanonicalForm F1;
-  CFFList QaF1Factors;
-  int wrongMipo= 0;
-  if (xValid && yValid)
-  {
-    if (degree (F,1) > minTdeg)
-      F1= F (eval[1], 2);
-    else
-      F1= F (eval[0], 1);
-  }
-  else if (xValid)
-    F1= F (eval[1], 2);
-  else
-    F1= F (eval[0], 1);
-
-  bool swap= false;
-  if (F1.level() == 2)
-  {
-    swap= true;
-    F1=swapvar (F1, x, y);
-    F= swapvar (F, x, y);
-  }
-
-  QaF1Factors= factorize (F1, alpha);
-  if (QaF1Factors.getFirst().factor().inCoeffDomain())
-    QaF1Factors.removeFirst();
-  for (iter= QaF1Factors; iter.hasItem(); iter++)
-  {
-    if (degree (iter.getItem().factor()) > minTdeg)
-      wrongMipo++;
-  }
-
-  if (wrongMipo == QaF1Factors.length())
-  {
-    if (xValid && yValid && !mipos[0].isZero() && !mipos[1].isZero())
-    {
-      if (maxNorm (mipos[0]) < maxNorm (mipos[1])) //try the other minpoly
-        alpha= rootOf (mipos[1]);
-      else
-        alpha= rootOf (mipos[0]);
-    }
-    else
-    {
-      rec= true;
-      F= bufF;
-      goto differentevalpoint;
-    }
-
-    wrongMipo= 0;
-    QaF1Factors= factorize (F1, alpha);
-    if (QaF1Factors.getFirst().factor().inCoeffDomain())
-      QaF1Factors.removeFirst();
-    for (iter= QaF1Factors; iter.hasItem(); iter++)
-    {
-      if (degree (iter.getItem().factor()) > minTdeg)
-        wrongMipo++;
-    }
-    if (wrongMipo == QaF1Factors.length())
-    {
-      rec= true;
-      F= bufF;
-      goto differentevalpoint;
-    }
-  }
-
-  CanonicalForm evaluation;
-  if (swap)
-    evaluation= eval[0];
-  else
-    evaluation= eval[1];
-
-  F *= bCommonDen (F);
-  F= F (y + evaluation, y);
-
-  int liftBound= degree (F,y) + 1;
-
-  modpk b= modpk();
-
-  CanonicalForm den= 1;
-
-  mipo= getMipo (alpha);
-
-  CFList uniFactors;
-  for (iter=QaF1Factors; iter.hasItem(); iter++)
-    uniFactors.append (iter.getItem().factor());
-
-  F /= Lc (F1);
-  ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
-  ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
-  ZZ NTLf= resultant (NTLmipo, NTLLcf);
-  ZZ NTLD= discriminant (NTLmipo);
-  den= abs (convertZZ2CF (NTLD*NTLf));
-
-  // make factors elements of Z(a)[x] disable for modularDiophant
-  CanonicalForm multiplier= 1;
-  for (CFListIterator i= uniFactors; i.hasItem(); i++)
-  {
-    multiplier *= bCommonDen (i.getItem());
-    i.getItem()= i.getItem()*bCommonDen(i.getItem());
-  }
-  F *= multiplier;
-  F *= bCommonDen (F);
-
-  Off (SW_RATIONAL);
-  int ii= 0;
-  CanonicalForm discMipo= convertZZ2CF (NTLD);
-  findGoodPrime (bufF*discMipo,ii);
-  findGoodPrime (F1*discMipo,ii);
-  findGoodPrime (F*discMipo,ii);
-
-  int pp=cf_getBigPrime(ii);
-  b = coeffBound( F, pp, mipo );
-  modpk bb= coeffBound (F1, pp, mipo);
-  if (bb.getk() > b.getk() ) b=bb;
-    bb= coeffBound (F, pp, mipo);
-  if (bb.getk() > b.getk() ) b=bb;
-
-  ExtensionInfo dummy= ExtensionInfo (alpha, false);
-  DegreePattern degs= DegreePattern (uniFactors);
-
-  bool earlySuccess= false;
-  CFList earlyFactors;
-  uniFactors= henselLiftAndEarly
-              (F, earlySuccess, earlyFactors, degs, liftBound,
-               uniFactors, dummy, evaluation, b, den);
-  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
-
-  CanonicalForm MODl= power (y, liftBound);
-
-  On (SW_RATIONAL);
-  F *= bCommonDen (F);
-  Off (SW_RATIONAL);
-
-  CFList biFactors;
-
-  biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
-                                  uniFactors.length()/2, b, den);
-
-  On (SW_RATIONAL);
-
-  if (earlySuccess)
-    biFactors= Union (earlyFactors, biFactors);
-  else if (!earlySuccess && degs.getLength() == 1)
-    biFactors= earlyFactors;
-
-  bool swap2= false;
-  appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
-  if (isOn (SW_RATIONAL))
-    normalize (biFactors);
-
-  CFAFList result;
-  bool found= false;
-
-  for (CFListIterator i= biFactors; i.hasItem(); i++)
-  {
-    if (totaldegree (i.getItem()) == minTdeg)
-    {
-      result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1));
-      found= true;
-      break;
-    }
-  }
-
-  if (!found)
-  {
-    rec= true;
-    F= bufF;
-    goto differentevalpoint;
-  }
-
+      }
+      if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
+      {
+        result= CFList();
+        LCFeval= CFList();
+        eval= CFList();
+        bad= true;
+        break;
+      }
+      if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
+      {
+        result= CFList();
+        LCFeval= CFList();
+        eval= CFList();
+        bad= true;
+        break;
+      }
+    }
+
+    if (bad)
+    {
+      E.nextpoint();
+      continue;
+    }
+
+    if (degree (eval.getFirst()) != degree (F, 1))
+    {
+      result= CFList();
+      eval= CFList();
+      LCFeval= CFList();
+      E.nextpoint();
+      continue;
+    }
+
+    deriv_x= deriv (eval.getFirst(), x);
+    gcd_deriv= gcd (eval.getFirst(), deriv_x);
+    if (degree (gcd_deriv) > 0)
+    {
+      result= CFList();
+      eval= CFList();
+      LCFeval= CFList();
+      E.nextpoint();
+      continue;
+    }
+    uniFactors= factorize (eval.getFirst());
+    if (uniFactors.getFirst().factor().inCoeffDomain())
+      uniFactors.removeFirst();
+    if (uniFactors.length() > 1 || uniFactors.getFirst().exp() > 1)
+    {
+      result= CFList();
+      eval= CFList();
+      LCFeval= CFList();
+      E.nextpoint();
+      continue;
+    }
+    iter= eval;
+    iter++;
+    CanonicalForm contentx= content (iter.getItem(), x);
+    if (degree (contentx) > 0)
+    {
+      result= CFList();
+      eval= CFList();
+      LCFeval= CFList();
+      E.nextpoint();
+      continue;
+    }
+    found= true;
+  }
+  while (!found);
+
+  if (!eval.isEmpty())
+    eval.removeFirst();
   return result;
 }
 
-#endif
-
-#ifdef HAVE_NTL
-/// absolute factorization of bivariate poly over Q
-///
-/// @return absFactorize returns a list whose entries contain three entities:
-///         an absolute irreducible factor, an irreducible univariate polynomial
-///         that defines the minimal field extension over which the irreducible
-///         factor is defined and the multiplicity of the absolute irreducible
-///         factor
-CFAFList absFactorize (const CanonicalForm& G ///<[in] bivariate poly over Q
-                      )
+CFAFList absFactorize (const CanonicalForm& G
+                           )
 {
-  //TODO handle homogeneous input
-  ASSERT (getNumVars (G) <= 2, "expected bivariate input");
+  //TODO handle homogeneous input, is already done in LIB interface but still...
   ASSERT (getCharacteristic() == 0, "expected poly over Q");
 
-  CFMap N;
-  CanonicalForm F= compress (G, N);
+  CanonicalForm F= G;
+
+  CanonicalForm LcF= Lc (F);
   bool isRat= isOn (SW_RATIONAL);
   if (isRat)
@@ -595 +273 @@
     On (SW_RATIONAL);
 
-  CanonicalForm contentX= content (F, 1);
-  CanonicalForm contentY= content (F, 2);
-  F /= (contentX*contentY);
-  CFAFList contentXFactors, contentYFactors;
-  contentXFactors= uniAbsFactorize (contentX);
-  contentYFactors= uniAbsFactorize (contentY);
-
-  if (contentXFactors.getFirst().factor().inCoeffDomain())
-    contentXFactors.removeFirst();
-  if (contentYFactors.getFirst().factor().inCoeffDomain())
-    contentYFactors.removeFirst();
-  if (F.inCoeffDomain())
-  {
-    CFAFList result;
-    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
-      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
-                                i.getItem().exp()));
-    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
-      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
-                                i.getItem().exp()));
-    normalize (result);
-    result.insert (CFAFactor (Lc (G), 1, 1));
-    return result;
-  }
   CFFList rationalFactors= factorize (F);
 
@@ -635 +289 @@
   }
 
-  for (CFAFListIterator i= result; i.hasItem(); i++)
-    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
-                            i.getItem().exp());
-  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
-    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
-                              i.getItem().exp()));
-  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
-    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
-                              i.getItem().exp()));
-  normalize (result);
-  result.insert (CFAFactor (Lc(G), 1, 1));
+  if (isRat)
+    normalize (result);
+  result.insert (CFAFactor (LcF, 1, 1));
 
   return result;
 }
+
+CFAFList absFactorizeMain (const CanonicalForm& G)
+{
+  CanonicalForm F= bCommonDen (G)*G;
+
+  Off (SW_RATIONAL);
+  F /= icontent (F);
+  On (SW_RATIONAL);
+
+  if (F.inCoeffDomain())
+    return CFAFList (CFAFactor (F, 1, 1));
+
+  // compress and find main Variable
+  CFMap N;
+  TIMING_START (abs_fac_compress)
+  CanonicalForm A= myCompress (F, N);
+  TIMING_END_AND_PRINT (abs_fac_compress,
+                        "time to compress poly in abs fact: ")
+
+  //univariate case
+  if (F.isUnivariate())
+  {
+    CFAFList result;
+    result= uniAbsFactorize (F);
+    if (result.getFirst().factor().inCoeffDomain())
+      result.removeFirst();
+    return result;
+  }
+
+  //bivariate case
+  if (A.level() == 2)
+  {
+    CFAFList result= absBiFactorizeMain (A);
+    decompress (result, N);
+    return result; //needs compressed input
+  }
+
+  Variable x= Variable (1);
+  Variable y= Variable (2);
+
+  CFAFList factors;
+  A *= bCommonDen (A);
+  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
+  int factorNums= 1;
+  CFAFList absBiFactors, absBufBiFactors;
+  CanonicalForm evalPoly;
+  int lift, bufLift, lengthAeval2= A.level()-2;
+  CFList* bufAeval2= new CFList [lengthAeval2];
+  CFList* Aeval2= new CFList [lengthAeval2];
+  int counter;
+  int differentSecondVar= 0;
+  CanonicalForm bufA;
+
+  // several bivariate factorizations
+  TIMING_START (abs_fac_bifactor_total);
+  int absValue= 2;
+  REvaluation E (2, A.level(), IntRandom (absValue));
+  for (int i= 0; i < factorNums; i++)
+  {
+    counter= 0;
+    bufA= A;
+    bufAeval= CFList();
+    TIMING_START (abs_fac_evaluation);
+    bufEvaluation= evalPoints4AbsFact (bufA, bufAeval, E, absValue);
+    TIMING_END_AND_PRINT (abs_fac_evaluation,
+                          "time to find evaluation point in abs fact: ");
+    E.nextpoint();
+    evalPoly= 0;
+
+    TIMING_START (abs_fac_evaluation);
+    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
+    TIMING_END_AND_PRINT (abs_fac_evaluation,
+                          "time to eval wrt diff second vars in abs fact: ");
+
+    for (int j= 0; j < lengthAeval2; j++)
+    {
+      if (!bufAeval2[j].isEmpty())
+        counter++;
+    }
+
+    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
+
+    TIMING_START (abs_fac_bi_factorizer);
+    absBufBiFactors= absBiFactorizeMain (bufAeval.getFirst(), true);
+    TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
+                          "time for bivariate factorization in abs fact: ");
+
+    if (absBufBiFactors.length() == 1)
+    {
+      factors.append (CFAFactor (A, 1, 1));
+      decompress (factors, N);
+      if (isOn (SW_RATIONAL))
+        normalize (factors);
+      delete [] bufAeval2;
+      delete [] Aeval2;
+      return factors;
+    }
+
+    if (i == 0)
+    {
+      Aeval= bufAeval;
+      evaluation= bufEvaluation;
+      absBiFactors= absBufBiFactors;
+      lift= bufLift;
+      for (int j= 0; j < lengthAeval2; j++)
+        Aeval2 [j]= bufAeval2 [j];
+      differentSecondVar= counter;
+    }
+    else
+    {
+      if (absBufBiFactors.length() < absBiFactors.length() ||
+          ((bufLift < lift) &&
+          (absBufBiFactors.length() == absBiFactors.length())) ||
+          counter > differentSecondVar)
+      {
+        Aeval= bufAeval;
+        evaluation= bufEvaluation;
+        absBiFactors= absBufBiFactors;
+        lift= bufLift;
+        for (int j= 0; j < lengthAeval2; j++)
+          Aeval2 [j]= bufAeval2 [j];
+        differentSecondVar= counter;
+      }
+    }
+    int k= 0;
+    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
+      evalPoly += j.getItem()*power (x, k);
+    list.append (evalPoly);
+  }
+
+  delete [] bufAeval2;
+
+  CFList rationalFactors;
+  Variable v= mvar (absBiFactors.getFirst().minpoly());
+
+  CFList biFactors;
+  for (CFAFListIterator iter= absBiFactors; iter.hasItem(); iter++)
+    biFactors.append (iter.getItem().factor());
+
+  sortList (biFactors, x);
+
+  int minFactorsLength;
+  bool irred= false;
+
+  TIMING_START (abs_fac_bi_factorizer);
+  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
+  TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
+         "time for bivariate factorization wrt diff second vars in abs fact: ");
+
+  TIMING_END_AND_PRINT (abs_fac_bifactor_total,
+                        "total time for eval and bivar factors in abs fact: ");
+  if (irred)
+  {
+    factors.append (CFAFactor (A, 1, 1));
+    decompress (factors, N);
+    if (isOn (SW_RATIONAL))
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
+
+  if (minFactorsLength == 0)
+    minFactorsLength= biFactors.length();
+  else if (biFactors.length() > minFactorsLength)
+    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
+
+  bool found= false;
+  if (differentSecondVar == lengthAeval2)
+  {
+    bool zeroOccured= false;
+    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
+    {
+      if (iter.getItem().isZero())
+      {
+        zeroOccured= true;
+        break;
+      }
+    }
+    if (!zeroOccured)
+    {
+      rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
+                                       minFactorsLength);
+      if (rationalFactors.length() == biFactors.length())
+      {
+        for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
+        {
+          if (totaldegree(iter.getItem())*degree(getMipo(v)) == totaldegree (G))
+          {
+            factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
+            found= true;
+            break;
+          }
+        }
+        // necessary since extension may be too large
+        if (!found)
+          factors= RothsteinTrager (A, rationalFactors, v, evaluation);
+
+        decompress (factors, N);
+        normalize (factors);
+        delete [] Aeval2;
+        return factors;
+      }
+      else
+        rationalFactors= CFList();
+      //TODO case where factors.length() > 0
+    }
+  }
+
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
+
+  CFList * oldAeval= new CFList [lengthAeval2];
+  for (int i= 0; i < lengthAeval2; i++)
+    oldAeval[i]= Aeval2[i];
+
+  getLeadingCoeffs (A, Aeval2);
+
+  CFList biFactorsLCs;
+  for (CFListIterator i= biFactors; i.hasItem(); i++)
+    biFactorsLCs.append (LC (i.getItem(), 1));
+
+  Variable w;
+  TIMING_START (abs_fac_precompute_leadcoeff);
+  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
+                                          evaluation, Aeval2, lengthAeval2, w);
+
+  if (w.level() != 1)
+    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
+                          uniFactors, w);
+
+  CanonicalForm oldA= A;
+  CFList oldBiFactors= biFactors;
+
+  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
+  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
+  leadingCoeffs.removeFirst();
+
+  if (!LCmultiplierIsConst)
+    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation,
+                            LCmultiplier);
+
+  //prepare leading coefficients
+  CFList* leadingCoeffs2= new CFList [lengthAeval2];
+  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
+                        biFactors, evaluation);
+
+  CFListIterator iter;
+  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
+  CFList bufBiFactors= biFactors;
+  bufA= A;
+  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
+  if (!LCmultiplierIsConst)
+  {
+    testVars= Variable (2);
+    for (int i= 0; i < lengthAeval2; i++)
+    {
+      if (!oldAeval[i].isEmpty())
+        testVars *= oldAeval[i].getFirst().mvar();
+    }
+  }
+  TIMING_END_AND_PRINT(abs_fac_precompute_leadcoeff,
+                       "time to precompute LC in abs fact: ");
+
+  TIMING_START (abs_fac_luckswang);
+  CFList bufFactors= CFList();
+  bool LCheuristic= false;
+  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
+                                rationalFactors))
+  {
+    int check= biFactors.length();
+    int * index= new int [factors.length()];
+    CFList oldFactors= rationalFactors;
+    rationalFactors= recoverFactors (A, rationalFactors, index);
+
+    if (check == rationalFactors.length())
+    {
+      if (w.level() != 1)
+      {
+        for (iter= rationalFactors; iter.hasItem(); iter++)
+          iter.getItem()= swapvar (iter.getItem(), w, y);
+      }
+
+      for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
+      {
+        if (totaldegree(iter.getItem())*degree (getMipo (v)) == totaldegree (G))
+        {
+          factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
+          found=true;
+          break;
+        }
+      }
+      // necessary since extension may be too large
+      if (!found)
+        factors= RothsteinTrager (A, rationalFactors, v, evaluation);
+
+      decompress (factors, N);
+      normalize (factors);
+      delete [] index;
+      delete [] Aeval2;
+      TIMING_END_AND_PRINT (abs_fac_luckswang,
+                            "time for successful LucksWang in abs fact: ");
+      return factors;
+    }
+    else if (rationalFactors.length() > 0)
+    {
+      int oneCount= 0;
+      CFList l;
+      for (int i= 0; i < check; i++)
+      {
+        if (index[i] == 1)
+        {
+          iter=biFactors;
+          for (int j=1; j <= i-oneCount; j++)
+            iter++;
+          iter.remove (1);
+          for (int j= 0; j < lengthAeval2; j++)
+          {
+            l= leadingCoeffs2[j];
+            iter= l;
+            for (int k=1; k <= i-oneCount; k++)
+              iter++;
+            iter.remove (1);
+            leadingCoeffs2[j]=l;
+          }
+          oneCount++;
+        }
+      }
+      bufFactors= rationalFactors;
+      rationalFactors= CFList();
+    }
+    else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
+    {
+      LCheuristic= true;
+      rationalFactors= oldFactors;
+      CFList contents, LCs;
+      bool foundTrueMultiplier= false;
+      LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
+                    contents, LCs, foundTrueMultiplier);
+      if (foundTrueMultiplier)
+      {
+          A= oldA;
+          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
+          for (int i= lengthAeval2-1; i > -1; i--)
+            leadingCoeffs2[i]= CFList();
+          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
+                                leadingCoeffs, biFactors, evaluation);
+      }
+      else
+      {
+        bool foundMultiplier= false;
+        LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
+                      oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
+        // coming from above: divide out more LCmultiplier if possible
+        if (foundMultiplier)
+        {
+          foundMultiplier= false;
+          LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
+                        testVars, lengthAeval2, leadingCoeffs2, A, LCmultiplier,
+                        foundMultiplier);
+        }
+        else
+        {
+          LCHeuristicCheck (LCs, contents, A, oldA,
+                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
+          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
+          {
+            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
+                         lengthAeval2, evaluation, oldBiFactors);
+          }
+        }
+
+        // patch everything together again
+        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
+        for (int i= lengthAeval2-1; i > -1; i--)
+          leadingCoeffs2[i]= CFList();
+        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
+                              biFactors, evaluation);
+      }
+      rationalFactors= CFList();
+      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
+      {
+        LCheuristic= false;
+        A= bufA;
+        biFactors= bufBiFactors;
+        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
+        LCmultiplier= bufLCmultiplier;
+      }
+    }
+    else
+      rationalFactors= CFList();
+    delete [] index;
+  }
+  TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
+
+  TIMING_START (abs_fac_lcheuristic);
+  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
+      && fdivides (getVars (LCmultiplier), testVars))
+  {
+    LCheuristic= true;
+    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
+                 lengthAeval2, evaluation, oldBiFactors);
+
+    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
+    for (int i= lengthAeval2-1; i > -1; i--)
+      leadingCoeffs2[i]= CFList();
+    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
+                          biFactors, evaluation);
+
+    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
+    {
+      LCheuristic= false;
+      A= bufA;
+      biFactors= bufBiFactors;
+      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
+      LCmultiplier= bufLCmultiplier;
+    }
+  }
+  TIMING_END_AND_PRINT (abs_fac_lcheuristic,
+                        "time for Lc heuristic in abs fact: ");
+
+tryAgainWithoutHeu:
+  //shifting to zero
+  TIMING_START (abs_fac_shift_to_zero);
+  CanonicalForm denA= bCommonDen (A);
+  A *= denA;
+  A= shift2Zero (A, Aeval, evaluation);
+  A /= denA;
+
+  for (iter= biFactors; iter.hasItem(); iter++)
+    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
+
+  for (int i= 0; i < lengthAeval2-1; i++)
+    leadingCoeffs2[i]= CFList();
+  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
+  {
+    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
+    for (int i= A.level() - 4; i > -1; i--)
+    {
+      if (i + 1 == lengthAeval2-1)
+        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
+      else
+        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
+    }
+  }
+  TIMING_END_AND_PRINT (abs_fac_shift_to_zero,
+                        "time to shift evaluation point to zero in abs fact: ");
+
+  CFArray Pi;
+  CFList diophant;
+  int* liftBounds= new int [A.level() - 1];
+  int liftBoundsLength= A.level() - 1;
+  for (int i= 0; i < liftBoundsLength; i++)
+    liftBounds [i]= degree (A, i + 2) + 1;
+
+  Aeval.removeFirst();
+  bool noOneToOne= false;
+
+  TIMING_START (abs_fac_cleardenom);
+  CFList commonDenominators;
+  for (iter=biFactors; iter.hasItem(); iter++)
+    commonDenominators.append (bCommonDen (iter.getItem()));
+  CanonicalForm tmp1, tmp2, tmp3=1;
+  CFListIterator iter2;
+  for (int i= 0; i < lengthAeval2; i++)
+  {
+    iter2= commonDenominators;
+    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
+    {
+      tmp1= bCommonDen (iter.getItem());
+      Off (SW_RATIONAL);
+      iter2.getItem()= lcm (iter2.getItem(), tmp1);
+      On (SW_RATIONAL);
+    }
+  }
+  tmp1= prod (commonDenominators);
+  for (iter= Aeval; iter.hasItem(); iter++)
+  {
+    tmp2= bCommonDen (iter.getItem()/denA);
+    Off (SW_RATIONAL);
+    tmp3= lcm (tmp2,tmp3);
+    On (SW_RATIONAL);
+  }
+  CanonicalForm multiplier;
+  multiplier= tmp3/tmp1;
+  iter2= commonDenominators;
+  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
+    iter.getItem() *= iter2.getItem()*multiplier;
+
+  for (iter= Aeval; iter.hasItem(); iter++)
+    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
+
+  for (int i= 0; i < lengthAeval2; i++)
+  {
+    iter2= commonDenominators;
+    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
+      iter.getItem() *= iter2.getItem()*multiplier;
+  }
+
+  TIMING_END_AND_PRINT (abs_fac_cleardenom,
+                        "time to clear denominators in abs fact: ");
+
+  TIMING_START (abs_fac_hensel_lift);
+  rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
+                               Pi, liftBounds, liftBoundsLength, noOneToOne);
+  TIMING_END_AND_PRINT (abs_fac_hensel_lift,
+                        "time for non monic hensel lifting in abs fact: ");
+
+  if (!noOneToOne)
+  {
+    int check= rationalFactors.length();
+    A= oldA;
+    TIMING_START (abs_fac_recover_factors);
+    rationalFactors= recoverFactors (A, rationalFactors, evaluation);
+    TIMING_END_AND_PRINT (abs_fac_recover_factors,
+                          "time to recover factors in abs fact: ");
+    if (check != rationalFactors.length())
+      noOneToOne= true;
+    else
+      rationalFactors= Union (rationalFactors, bufFactors);
+  }
+  if (noOneToOne)
+  {
+    if (!LCmultiplierIsConst && LCheuristic)
+    {
+      A= bufA;
+      biFactors= bufBiFactors;
+      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
+      delete [] liftBounds;
+      LCheuristic= false;
+      goto tryAgainWithoutHeu;
+      //something probably went wrong in the heuristic
+    }
+
+    A= shift2Zero (oldA, Aeval, evaluation);
+    biFactors= oldBiFactors;
+    for (iter= biFactors; iter.hasItem(); iter++)
+      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
+    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
+    CanonicalForm yToLift= power (y, lift);
+    CFListIterator i= biFactors;
+    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
+    i++;
+
+    for (; i.hasItem(); i++)
+      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
+
+    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
+
+    i= biFactors;
+    yToLift= power (y, lift);
+    CanonicalForm dummy;
+    for (; i.hasItem(); i++)
+    {
+      LCA= LC (i.getItem(), 1);
+      extgcd (LCA, yToLift, LCA, dummy);
+      i.getItem()= mod (i.getItem()*LCA, yToLift);
+    }
+
+    liftBoundsLength= F.level() - 1;
+    liftBounds= liftingBounds (A, lift);
+
+    CFList MOD;
+    bool earlySuccess;
+    CFList earlyFactors;
+    ExtensionInfo info= ExtensionInfo (false);
+    CFList liftedFactors;
+    TIMING_START (abs_fac_hensel_lift);
+    liftedFactors= henselLiftAndEarly
+                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
+                    Aeval, biFactors, evaluation, info);
+    TIMING_END_AND_PRINT (abs_fac_hensel_lift,
+                          "time for hensel lifting in abs fact: ");
+
+    TIMING_START (abs_fac_factor_recombination);
+    rationalFactors= factorRecombination (A, liftedFactors, MOD);
+    TIMING_END_AND_PRINT (abs_fac_factor_recombination,
+                          "time for factor recombination in abs fact: ");
+
+    if (earlySuccess)
+      rationalFactors= Union (rationalFactors, earlyFactors);
+
+    for (CFListIterator i= rationalFactors; i.hasItem(); i++)
+    {
+      int kk= Aeval.getLast().level();
+      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
+      {
+        if (i.getItem().level() < kk)
+          continue;
+       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
+      }
+    }
+  }
+
+  if (w.level() != 1)
+  {
+    for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
+      iter.getItem()= swapvar (iter.getItem(), w, y);
+  }
+
+  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
+  {
+    if (totaldegree (iter.getItem())*degree (getMipo (v)) == totaldegree (G))
+    {
+      factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
+      found= true;
+      break;
+    }
+  }
+
+  // necessary since extension may be too large
+  if (!found)
+    factors= RothsteinTrager (A, rationalFactors, v, evaluation);
+
+  decompress (factors, N);
+  if (isOn (SW_RATIONAL))
+    normalize (factors);
+
+  delete [] leadingCoeffs2;
+  delete [] oldAeval;
+  delete [] Aeval2;
+  delete[] liftBounds;
+
+  return factors;
+}
+
 #endif
-
-

factory/facAbsFact.h

@@ -4 +4 @@
 /** @file facAbsFact.h
  *
- * bivariate absolute factorization over Q described in "Modular Las Vegas
- * Algorithms for Polynomial Absolute Factorization" by Bertone, ChÚze, Galligo
+ * absolute multivariate factorization over Q
  *
  * @author Martin Lee
@@ -15 +14 @@
 #define FAC_ABS_FACT_H
 
-#include "cf_assert.h"
-
-#include "cf_algorithm.h"
-#include "cf_map.h"
+#include "facAbsBiFact.h"
 
 #ifdef HAVE_NTL
-/// main absolute factorization routine, expects bivariate poly which is
-/// primitive wrt. any of its variables and irreducible over Q
-///
-/// @return absFactorizeMain returns a list whose entries contain three entities:
-///         an absolute irreducible factor, an irreducible univariate polynomial
-///         that defines the minimal field extension over which the irreducible
-///         factor is defined and the multiplicity of the absolute irreducible
-///         factor
-CFAFList absFactorizeMain (const CanonicalForm& F ///<[in] s.a.
-                          );
+CFAFList absFactorizeMain (const CanonicalForm& F);
 #endif
 
-/// normalize factors, i.e. make factors monic
-static inline
-void normalize (CFAFList & L)
-{
-  for (CFAFListIterator i= L; i.hasItem(); i++)
-    i.getItem()= CFAFactor (i.getItem().factor()/Lc (i.getItem().factor()),
-                            i.getItem().minpoly(), i.getItem().exp());
-}
-
-/// univariate absolute factorization over Q
-///
-/// @return uniAbsFactorize returns a list whose entries contain three entities:
-///         an absolute irreducible factor, an irreducible univariate polynomial
-///         that defines the minimal field extension over which the irreducible
-///         factor is defined and the multiplicity of the absolute irreducible
-///         factor
-static inline
-CFAFList uniAbsFactorize (const CanonicalForm& F ///<[in] univariate poly over Q
-                         )
-{
-  CFFList rationalFactors= factorize (F);
-  CFFListIterator i= rationalFactors;
-  i++;
-  Variable alpha;
-  CFAFList result;
-  CFFList QaFactors;
-  CFFListIterator iter;
-  for (; i.hasItem(); i++)
-  {
-    if (degree (i.getItem().factor()) == 1)
-    {
-      result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp()));
-      continue;
-    }
-    alpha= rootOf (i.getItem().factor());
-    QaFactors= factorize (i.getItem().factor(), alpha);
-    iter= QaFactors;
-    if (iter.getItem().factor().inCoeffDomain())
-      iter++;
-    for (;iter.hasItem(); iter++)
-    {
-      if (degree (iter.getItem().factor()) == 1)
-      {
-        result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
-                                  i.getItem().exp()));
-        break;
-      }
-    }
-  }
-  result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
-  return result;
-}
-
 /*BEGINPUBLIC*/
-
 #ifdef HAVE_NTL
-CFAFList absFactorize (const CanonicalForm& G);
+CFAFList absFactorize (const CanonicalForm& G ///<[in] poly over Q
+                      );
 #endif
-
 /*ENDPUBLIC*/
 
+
 #endif

factory/facFactorize.cc

@@ -52 +52 @@
   Variable x= Variable (1);
 
+  CanonicalForm LCF=LC (F,x);
+  CFList LCFeval;
+
   bool found= false;
   bool allZero= true;
@@ -60 +63 @@
   {
     eval.insert (F);
+    LCFeval.insert (LCF);
     bool bad= false;
     for (int i= E.max(); i >= E.min(); i--)
     {
       eval.insert (eval.getFirst()( E [i], i));
+      LCFeval.insert (LCFeval.getFirst() (E [i], i));
       result.append (E[i]);
       if (!E[i].isZero())
@@ -73 +78 @@
         result= CFList();
         eval= CFList();
+        LCFeval= CFList();
         bad= true;
         foundZero= false;
@@ -81 +87 @@
         result= CFList();
         eval= CFList();
+        LCFeval= CFList();
         bad= true;
         break;
       }
+      if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
+      {
+        result= CFList();
+        eval= CFList();
+        LCFeval= CFList();
+        bad= true;
+        break;
+      }
     }
 
@@ -96 +111 @@
       result= CFList();
       eval= CFList();
+      LCFeval= CFList();
       E.nextpoint();
       continue;
@@ -106 +122 @@
       result= CFList();
       eval= CFList();
+      LCFeval= CFList();
       E.nextpoint();
       continue;
@@ -116 +133 @@
       result= CFList();
       eval= CFList();
+      LCFeval= CFList();
       E.nextpoint();
       continue;
@@ -769 +787 @@
   }
 
-  swap (factors, 0, 0, x);
   append (factors, contentAFactors);
   decompress (factors, N);

factory/facFactorize.h

@@ -22 +22 @@
 TIMING_DEFINE_PRINT (fac_squarefree)
 TIMING_DEFINE_PRINT (fac_factor_squarefree)
+
+/// Factorization of A wrt. to different second vars
+void
+factorizationWRTDifferentSecondVars (
+                          const CanonicalForm& A, ///<[in] poly
+                          CFList*& Aeval,         ///<[in,out] A evaluated wrt.
+                                                  ///< different second vars
+                                                  ///< returns bivariate factors
+                          int& minFactorsLength,  ///<[in,out] minimal length of
+                                                  ///< bivariate factors
+                          bool& irred,            ///<[in,out] Is A irreducible?
+                          const Variable& w       ///<[in] alg. variable
+                                    );
 
 /// Factorization over Q (a)

factory/facFqBivarUtil.cc

@@ -58 +58 @@
 }
 
+void decompress (CFAFList& factors, const CFMap& N)
+{
+  for (CFAFListIterator i= factors; i.hasItem(); i++)
+    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
+                            i.getItem().exp());
+}
+
 void appendSwapDecompress (CFList& factors1, const CFList& factors2,
                            const CFList& factors3, const bool swap1,
@@ -464 +471 @@
   logDeriv= mulMod2 (q, deriv (G, y), xToL);
   TIMING_END_AND_PRINT (fac_log_deriv_mul, "time to multiply in logderiv1: ");
+
+  if (degree (logDeriv, x) == 0)
+  {
+    Q= q;
+    return CFArray();
+  }
 
   int j= degree (logDeriv, y) + 1;
@@ -543 +556 @@
   TIMING_END_AND_PRINT (fac_log_deriv_mul, "time for mul in logderiv2: ");
 
+  if (degree (logDeriv, x) == 0)
+  {
+    Q= q;
+    return CFArray();
+  }
+
   int j= degree (logDeriv,y) + 1;
   CFArray result= CFArray (j);
@@ -726 +745 @@
   maxX= minX;
   maxY= minY;
+  int indZero= 0;
   for (int i= 1; i < sizeOfNewtonPolygon; i++)
   {
+    if (newtonPolyg[i][1] == 0)
+    {
+      if (newtonPolyg[indZero][1] == 0)
+      {
+        if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
+          indZero= i;
+      }
+      else
+        indZero= i;
+    }
     if (minX > newtonPolyg [i] [0])
       minX= newtonPolyg [i] [0];
@@ -738 +768 @@
   }
 
-  int k= maxX;
+  int slopeNum, slopeDen, constTerm;
+  bool negativeSlope=false;
+  if (indZero != sizeOfNewtonPolygon - 1)
+  {
+    slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
+    slopeDen= newtonPolyg[indZero+1][1];
+    constTerm= newtonPolyg[indZero][0];
+  }
+  else
+  {
+    slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
+    slopeDen= newtonPolyg[0][1];
+    constTerm= newtonPolyg[indZero][0];
+  }
+  if (slopeNum < 0)
+  {
+    slopeNum= -slopeNum;
+    negativeSlope= true;
+  }
+  int k= 0;
   for (int i= 0; i < n; i++)
   {
+    if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
+        || ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
+    {
+      if (indZero + 1 != sizeOfNewtonPolygon)
+        indZero++;
+      else
+        indZero= 0;
+      if (indZero != sizeOfNewtonPolygon - 1)
+      {
+        slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
+        slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
+        constTerm= newtonPolyg[indZero][0];
+      }
+      else
+      {
+        slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
+        slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
+        constTerm= newtonPolyg[indZero][0];
+      }
+      if (slopeNum < 0)
+      {
+        negativeSlope= true;
+        slopeNum= - slopeNum;
+        k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
+                   slopeDen) + constTerm;
+      }
+      else
+        k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
+                  + constTerm;
+    }
+    else
+    {
+      if (negativeSlope)
+        k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
+                   slopeDen) + constTerm;
+      else
+        k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
+                  + constTerm;
+    }
     if (i + 1 > maxY || i + 1 < minY)
     {
@@ -749 +837 @@
     point [0]= k;
     point [1]= i + 1;
-    while (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
-    {
-      k--;
-      point [0]= k;
-    }
+    if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
+      k= 0;
     result [i]= k;
-    k= maxX;
     delete [] point;
   }
+
+  for (int i= 0; i < sizeOfNewtonPolygon; i++)
+    delete [] newtonPolyg[i];
+  delete [] newtonPolyg;
 
   return result;
@@ -811 +899 @@
   maxX= minX;
   maxY= minY;
+  int indZero= 0;
   for (int i= 1; i < sizeOfNewtonPolygon; i++)
   {
+    if (newtonPolyg[i][0] == 0)
+    {
+      if (newtonPolyg[indZero][0] == 0)
+      {
+        if (newtonPolyg[indZero][1] < newtonPolyg[i][1])
+          indZero= i;
+      }
+      else
+        indZero= i;
+    }
     if (minX > newtonPolyg [i] [0])
       minX= newtonPolyg [i] [0];
@@ -823 +922 @@
   }
 
-  int k= maxY;
+  int slopeNum, slopeDen, constTerm;
+  bool negativeSlope=false;
+  if (indZero != sizeOfNewtonPolygon - 1)
+  {
+    slopeNum= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
+    slopeDen= newtonPolyg[indZero+1][0];
+    constTerm= newtonPolyg[indZero][1];
+  }
+  else
+  {
+    slopeNum= newtonPolyg[0][1]-newtonPolyg[indZero][1];
+    slopeDen= newtonPolyg[0][0];
+    constTerm= newtonPolyg[indZero][1];
+  }
+  if (slopeNum < 0)
+  {
+    slopeNum= -slopeNum;
+    negativeSlope= true;
+  }
+  int k= 0;
   for (int i= 0; i < n; i++)
   {
+    if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][0])
+        || ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][0]))
+    {
+      if (indZero + 1 != sizeOfNewtonPolygon)
+        indZero++;
+      else
+        indZero= 0;
+      if (indZero != sizeOfNewtonPolygon - 1)
+      {
+        slopeNum= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
+        slopeDen= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
+        constTerm= newtonPolyg[indZero][1];
+      }
+      else
+      {
+        slopeNum= newtonPolyg[0][1]-newtonPolyg[indZero][1];
+        slopeDen= newtonPolyg[0][0]-newtonPolyg[indZero][0];
+        constTerm= newtonPolyg[indZero][1];
+      }
+      if (slopeNum < 0)
+      {
+        negativeSlope= true;
+        slopeNum= - slopeNum;
+        k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][0])+slopeDen-1)/
+                   slopeDen) + constTerm;
+      }
+      else
+        k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][0])) / slopeDen)
+                  + constTerm;
+    }
+    else
+    {
+      if (negativeSlope)
+        k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][0])+slopeDen-1)/
+                   slopeDen) + constTerm;
+      else
+        k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][0])) / slopeDen
+                  + constTerm;
+    }
     if (i + 1 > maxX || i + 1 < minX)
     {
@@ -834 +991 @@
     point [0]= i + 1;
     point [1]= k;
-    while (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
-    {
-      k--;
-      point [1]= k;
-    }
+    if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
+      k= 0;
     result [i]= k;
-    k= maxY;
     delete [] point;
   }
+
+  for (int i= 0; i < sizeOfNewtonPolygon; i++)
+    delete [] newtonPolyg[i];
+  delete [] newtonPolyg;
 
   return result;

factory/facFqBivarUtil.h

@@ -38 +38 @@
                 );
 
+/// as above
+void decompress (CFAFList& factors, ///< [in,out] a list of factors
+                 const CFMap& N    ///< [in] a map
+                );
+
 /// first swap Variables in @a factors1 if necessary, then append @a factors2
 /// and @a factors3 on @a factors1 and finally decompress @a factors1
@@ -68 +73 @@
                                                  ///< Fq if we are not over some
                                                  ///< GF
-                    const int k,                 ///< some int k such that k 
+                    const int k,                 ///< some int k such that k
                                                  ///< divides l if we are not
                                                  ///< over some Fq
@@ -189 +194 @@
 ///         Variable (2)^l
 CFArray
-logarithmicDerivative (const CanonicalForm& F,   ///< [in] bivariate poly 
+logarithmicDerivative (const CanonicalForm& F,   ///< [in] bivariate poly
                                                  ///< truncated at Variable(2)^l
                        const CanonicalForm& G,   ///< [in] a factor of F
@@ -199 +204 @@
                       );
 
-/// compute bounds for logarithmic derivative as described in K. Belabas, 
-/// M. van Hoeij, J. KlÃŒners, and A. Steel, Factoring polynomials over global 
+/// compute bounds for logarithmic derivative as described in K. Belabas,
+/// M. van Hoeij, J. KlÃŒners, and A. Steel, Factoring polynomials over global
 /// fields
 ///
@@ -225 +230 @@
 /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
 /// @sa {getCoeffs (const CanonicalForm&, const int, const Variable&),
-/// getCoeffs (const CanonicalForm&, const int, const int, const int, 
+/// getCoeffs (const CanonicalForm&, const int, const int, const int,
 /// const Variable&, const CanonicalForm&, const mat_zz_p&)}
 CFArray
@@ -237 +242 @@
 /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
 /// @sa {getCoeffs (const CanonicalForm&, const int),
-/// getCoeffs (const CanonicalForm&, const int, const int, const int, 
+/// getCoeffs (const CanonicalForm&, const int, const int, const int,
 /// const Variable&, const CanonicalForm&, const mat_zz_p&)}
 CFArray
-getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over 
+getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over
                                   ///< F_p(alpha)
            const int k,           ///< [in] some int
@@ -281 +286 @@
 /// substitute x^d by x in F
 void
-subst (const CanonicalForm& F, ///< [in] a polynomial 
+subst (const CanonicalForm& F, ///< [in] a polynomial
        CanonicalForm& A,       ///< [in,out] returns F with x^d replaced by x
        const int d,            ///< d > 1 such that a substitution x^d -> x
@@ -299 +304 @@
 /// reverse a substitution x^d->x
 void
-reverseSubst (CFList& L,        ///< [in,out] a list of polys, returns the 
+reverseSubst (CFList& L,        ///< [in,out] a list of polys, returns the
                                 ///< given list with x replaced by x^d
               const int d,      ///< [in] an integer > 0

factory/facFqFactorize.cc

@@ -8 +8 @@
  *
  * ABSTRACT: "Efficient Multivariate Factorization over Finite Fields" by
- * L. Bernardin & M. Monagon. Precomputation of leading coefficients is 
+ * L. Bernardin & M. Monagon. Precomputation of leading coefficients is
  * described in "Sparse Hensel lifting" by E. Kaltofen
  *
@@ -743 +743 @@
   int k= F.level() - 1;
   Variable x= Variable (1);
+  CanonicalForm LCF=LC (F, x);
+  CFList LCFeval;
+
   CFList result;
   FFRandom genFF;
@@ -818 +821 @@
     int l= F.level();
     eval.insert (F);
+    LCFeval.insert (LCF);
     bool bad= false;
     for (CFListIterator i= result; i.hasItem(); i++, l--)
     {
       eval.insert (eval.getFirst()(i.getItem(), l));
+      LCFeval.insert (LCFeval.getFirst()(i.getItem(), l));
       if (degree (eval.getFirst(), l - 1) != degree (F, l - 1))
       {
@@ -828 +833 @@
         result= CFList();
         eval= CFList();
+        LCFeval= CFList();
+        bad= true;
+        break;
+      }
+      if ((l != 2) && (degree (LCFeval.getFirst(), l-1) != degree (LCF, l-1)))
+      {
+        if (!find (list, random))
+          list.append (random);
+        result= CFList();
+        eval= CFList();
+        LCFeval= CFList();
         bad= true;
         break;
@@ -841 +857 @@
         list.append (random);
       result= CFList();
+      LCFeval= CFList();
       eval= CFList();
       continue;
@@ -852 +869 @@
         list.append (random);
       result= CFList();
+      LCFeval= CFList();
       eval= CFList();
       continue;
@@ -863 +881 @@
         list.append (random);
       result= CFList();
+      LCFeval= CFList();
       eval= CFList();
       continue;
@@ -2014 +2033 @@
     }
     s++;
-    if (T.length() < 2*s || T.length() == s) 
+    if (T.length() < 2*s || T.length() == s)
     {
       delete [] v;
@@ -3638 +3657 @@
 #endif
 /* HAVE_NTL */
-

factory/facFqFactorize.h

@@ -472 +472 @@
 /// polynomial has main variable Variable (1), is squarefree and its degree
 /// coincides with degree(F) and the bivariate one is primitive wrt.
-/// Variable(1), and successively evaluated polynomials have the same degree in 
-/// their main variable as F has, fails if there are no valid evaluation points, 
+/// Variable(1), and successively evaluated polynomials have the same degree in
+/// their main variable as F has, fails if there are no valid evaluation points,
 /// eval contains the intermediate evaluated polynomials.
 ///
@@ -527 +527 @@
 /// A.
 ///
-/// @return @a lcmContent returns the LCM of the contents of @a A wrt to each 
+/// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
 ///         variable occuring in @a A.
 CanonicalForm
-lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly 
+lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
             CFList& contentAi       ///< [in,out] an empty list, returns a list
-                                    ///< of the contents of @a A wrt to each 
+                                    ///< of the contents of @a A wrt to each
                                     ///< variable occuring in @a A starting from
                                     ///< @a A.mvar().
            );
 
-/// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and 
+/// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
 /// no gaps between the variables occur
 ///
 /// @return a compressed poly with the above properties
 CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
-                          CFMap& N                ///< [in,out] a map to 
+                          CFMap& N                ///< [in,out] a map to
                                                   ///< decompress
                          );
@@ -579 +579 @@
 /// plug in evalPoint for y in a list of polys
 ///
-/// @return returns a list of the evaluated polys, these evaluated polys are 
+/// @return returns a list of the evaluated polys, these evaluated polys are
 /// made monic
 CFList
@@ -607 +607 @@
 
 /// normalize precomputed leading coefficients such that leading coefficients
-/// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt 
+/// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt
 /// Variable(1) of bivariate factors and change @a A and @a Aeval accordingly
 void
@@ -641 +641 @@
 distributeContent (
           const CFList& L,                        ///<[in] list of polys, first
-                                                  ///< entry the content to be 
+                                                  ///< entry the content to be
                                                   ///< distributed
-          const CFList* differentSecondVarFactors,///<[in] factorization wrt 
+          const CFList* differentSecondVarFactors,///<[in] factorization wrt
                                                   ///< different second vars
-          int length                              ///<[in] length of 
+          int length                              ///<[in] length of
                                                   ///<differentSecondVarFactors
                   );
@@ -659 +659 @@
 /// computes a list l of length length(LCFFactors)+1 of polynomials such that
 /// prod (l)=LCF, note that the first entry of l may be non constant. Intended
-/// to be used to precompute coefficients of a polynomial f from its bivariate 
+/// to be used to precompute coefficients of a polynomial f from its bivariate
 /// factorizations.
 ///
@@ -795 +795 @@
 #endif
 /* FAC_FQ_FACTORIZE_H */
-

libpolys/polys/clapsing.cc

@@ -1695 +1695 @@
 }
 
-ideal singclap_absBiFactorize ( poly f, ideal & mipos, intvec ** exps, int & numFactors, const ring r)
+ideal singclap_absFactorize ( poly f, ideal & mipos, intvec ** exps, int & numFactors, const ring r)
 {
   p_Test(f, r);
@@ -1714 +1714 @@
   CanonicalForm F( convSingTrPFactoryP( f, r) );
 
-  if (getNumVars (F) > 2)
-  {
-    WerrorS( feNotImplemented );
-    return res;
-  }
+  bool isRat= isOn (SW_RATIONAL);
+  if (!isRat)
+    On (SW_RATIONAL);
+
   CFAFList absFactors= absFactorize (F);
 
@@ -1740 +1739 @@
     iter++;
   }
-  bool isRat= isOn (SW_RATIONAL);
-  if (!isRat)
-    On (SW_RATIONAL);
   for (; iter.hasItem(); iter++, i++)
   {

libpolys/polys/clapsing.h

@@ -58 +58 @@
 intvec* singntl_LLL(intvec* A, const ring r);
 
-ideal singclap_absBiFactorize ( poly f, ideal & mipos, intvec ** exps, int & n, const ring r);
+ideal singclap_absFactorize ( poly f, ideal & mipos, intvec ** exps, int & n, const ring r);
 #  endif
 # endif