Changeset 70bf04b in git

Timestamp:

Mar 21, 2013, 11:39:03 AM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

675c62cd9015e53f77b1f57146d0d5098bcb42e1

Parents:

2d35fe77fb45655052d739f5e90e572b52fe709f

git-author:

Martin Lee <martinlee84@web.de>2013-03-21 11:39:03+01:00

git-committer:

Martin Lee <martinlee84@web.de>2013-03-22 15:53:43+01:00

Message:

fix: bug in hensel lifting part1

File:

• factory/facHensel.cc (modified) (6 diffs)

factory/facHensel.cc

@@ -7 +7 @@
  *
  * ABSTRACT: Hensel lifting is described in "Efficient Multivariate
- * Factorization over Finite Fields" by L. Bernardin & M. Monagon. Division with
- * remainder is described in "Fast Recursive Division" by C. Burnikel and
- * J. Ziegler. Karatsuba multiplication is described in "Modern Computer
- * Algebra" by J. von zur Gathen and J. Gerhard.
+ * Factorization over Finite Fields" by L. Bernardin & M. Monagon.
  *
  * @author Martin Lee
@@ -1758 +1755 @@
       M (j + 2, 1)= mulNTL (bufFactors[0] [j + 1], bufFactors[1] [j + 1]);
   }
+  else
+    M (j + 1, 1)= 0;
+
   CanonicalForm uIZeroJ;
   if (degBuf0 > 0 && degBuf1 > 0)
-    uIZeroJ= mulNTL(bufFactors[0][0],buf[1])+mulNTL (bufFactors[1][0], buf[0]);
+    uIZeroJ= mulNTL(bufFactors[0][0], buf[1]) +
+             mulNTL (bufFactors[1][0], buf[0]);
   else if (degBuf0 > 0)
-    uIZeroJ= mulNTL (buf[0], bufFactors[1]);
+    uIZeroJ= mulNTL (buf[0], bufFactors[1]) +
+             mulNTL (buf[1], bufFactors[0][0]);
   else if (degBuf1 > 0)
-    uIZeroJ= mulNTL (bufFactors[0], buf [1]);
+    uIZeroJ= mulNTL (bufFactors[0], buf[1]) +
+             mulNTL (buf[0], bufFactors[1][0]);
   else
-    uIZeroJ= 0;
+    uIZeroJ= mulNTL (bufFactors[0], buf[1]) +
+             mulNTL (buf[0], bufFactors[1]);
+
   Pi [0] += xToJ*uIZeroJ;
 
@@ -1781 +1786 @@
     for (k= 1; k <= (int) ceil (j/2.0); k++)
     {
-      if (one.hasTerms() && two.hasTerms())
-      {
-        if (k != j - k + 1)
-        {
-          if ((one.hasTerms() && one.exp() == j - k + 1) && +
-              (two.hasTerms() && two.exp() == j - k + 1))
+      if (k != j - k + 1)
+      {
+        if ((one.hasTerms() && one.exp() == j - k + 1) && +
+            (two.hasTerms() && two.exp() == j - k + 1))
         {
           tmp[0] += mulNTL ((bufFactors[0][k]+one.coeff()),(bufFactors[1][k] +
-                      two.coeff())) - M (k + 1, 1) - M (j - k + 2, 1);
+                    two.coeff())) - M (k + 1, 1) - M (j - k + 2, 1);
           one++;
           two++;
@@ -1796 +1799 @@
         {
           tmp[0] += mulNTL ((bufFactors[0][k]+one.coeff()), bufFactors[1] [k]) -
-                      M (k + 1, 1);
+                    M (k + 1, 1);
           one++;
         }
@@ -1808 +1811 @@
       else
         tmp[0] += M (k + 1, 1);
-      }
     }
   }
@@ -1847 +1849 @@
         M (j + 2, l + 1)= mulNTL (Pi [l - 1][j + 1], bufFactors[l + 1] [j + 1]);
     }
+    else
+      M (j + 1, l + 1)= 0;
 
     if (degPi > 0 && degBuf > 0)
-      uIZeroJ= mulNTL (Pi[l -1] [0], buf[l + 1]) +
+      uIZeroJ= mulNTL (Pi[l - 1] [0], buf[l + 1]) +
                mulNTL (uIZeroJ, bufFactors[l+1] [0]);
     else if (degPi > 0)
-      uIZeroJ= mulNTL (uIZeroJ, bufFactors[l + 1]);
+      uIZeroJ= mulNTL (uIZeroJ, bufFactors[l + 1]) +
+               mulNTL (Pi[l - 1][0], buf[l + 1]);
     else if (degBuf > 0)
-      uIZeroJ= mulNTL (Pi[l - 1], buf[l+1]);
-    else
-      uIZeroJ= 0;
+      uIZeroJ= mulNTL (uIZeroJ, bufFactors[l + 1][0]) +
+               mulNTL (Pi[l - 1], buf[l + 1]);
+    else
+      uIZeroJ= mulNTL (uIZeroJ, bufFactors[l + 1]) +
+               mulNTL (Pi[l - 1], buf[l + 1]);
 
     Pi [l] += xToJ*uIZeroJ;