Changeset 1bc7201 in git for factory

Timestamp:

Oct 19, 2012, 6:38:35 PM (12 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', '2a584933abf2a2d3082034c7586d38bb6de1a30a')

Children:

c879eea1669e963fb4c7287a3963abb287d00a49

Parents:

b37b3984a12e1552c7bafc9fd5a7849240ea79806bbe944402dfca102dcc3e036c4f2f119be41e44

Message:

Merge pull request #192 from mmklee/algExtGCD_sw

Alg ext gcd sw

Location:

factory

Files:

• algext.cc (modified) (6 diffs)
• cf_chinese.cc (modified) (1 diff)
• cf_gcd_smallp.cc (modified) (1 diff)
• facFqBivarUtil.cc (modified) (1 diff)
• facFqSquarefree.h (modified) (1 diff)
• facHensel.cc (modified) (5 diffs)
• facMul.cc (modified) (1 diff)
• fac_ezgcd.cc (modified) (1 diff)

factory/algext.cc

@@ -548 +548 @@
         return;
       m *= (x - alpha);
-      if(gnew == gm) // gnew did not change
-      {
-        cf = tryvcontent(gm, Variable(2), M, fail);
+      if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
+      {
+        cf = tryvcontent(gnew, Variable(2), M, fail);
         if(fail)
           return;
         divides = true;
-        g_image= gm;
+        g_image= gnew;
         g_image.tryDiv (cf, M, fail);
         if(fail)
@@ -692 +692 @@
   }
   // here: a is the biggest alg. var in f and g AND some of f,g is in extension
-  // (in the sequel b is used to swap alg/poly vars)
   setReduce(a,false); // do not reduce expressions modulo mipo
   tmp = getMipo(a);
@@ -703 +702 @@
     mv = i;
   // here: mv is level of the largest variable in f, g
-  b = Variable(mv+1);
   bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
   other = new int[mv+1];
@@ -750 +748 @@
     if(isEqual(bound, other, 1, mv)) // equal
     {
-      chineseRemainder( D, q, replacevar( mapinto(Dp), a, b ), p, tmp, newq );
+      chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
       // tmp = Dp mod p
       // tmp = D mod q
@@ -758 +756 @@
         D = tmp;
       On( SW_RATIONAL );
-      tmp = replacevar( Farey( D, q ), b, a ); // Farey and switch back to alg var
+      tmp = Farey( D, q ); // Farey
+      tmp *= bCommonDen (tmp);
       setReduce(a,true); // reduce expressions modulo mipo
       On( SW_RATIONAL ); // needed by fdivides
@@ -780 +779 @@
     // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
     q = p;
-    D = replacevar( mapinto(Dp), a, b ); // shortcut CRA // shortcut CRA
+    D = mapinto(Dp); // shortcut CRA // shortcut CRA
     for(int i=1; i<=mv; i++) // tighten bound
       bound[i] = other[i];

factory/cf_chinese.cc

@@ -227 +227 @@
           }
           else
+            result += power( x, i.exp() ) * Farey(c,q);
+#else
+          if (c.inZ())
+            result += power( x, i.exp() ) * Farey_n(c,q);
+          else
+            result += power( x, i.exp() ) * Farey(c,q);
 #endif
-            result += power( x, i.exp() ) * Farey_n(c,q);
         }
         else

factory/cf_gcd_smallp.cc

@@ -4229 +4229 @@
   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;

factory/facFqBivarUtil.cc

@@ -519 +519 @@
   }
 
-  q= newtonDiv (bufF, G, xToLOldL);
+  if (l-oldL > 0)
+    q= newtonDiv (bufF, G, xToLOldL);
+  else
+    q= 0;
   q *= xToOldL;
   q += oldQ;

factory/facFqSquarefree.h

@@ -18 +18 @@
 #include "cf_factory.h"
 #include "fac_sqrfree.h"
+#include "cf_factory.h"
 
 /// squarefree factorization over a finite field

factory/facHensel.cc

@@ -544 +544 @@
   }
 
+  setReduce (alpha, false);
   for (k= 0; k < factors.length(); k++)
   {
@@ -554 +555 @@
     }
   }
+  setReduce (alpha, true);
   setCharacteristic(0);
 
@@ -591 +593 @@
   }
   setCharacteristic (p);
+  setReduce (alpha, false);
   recResult= mapinto (recResult);
+  setReduce (alpha, true);
   if (mipoHasDen)
   {
@@ -606 +610 @@
     coeffE= div (e, modulus);
     setCharacteristic (p);
+    if (mipoHasDen)
+      setReduce (gamma, false);
+    else
+      setReduce (alpha, false);
     coeffE= coeffE.mapinto();
+    if (mipoHasDen)
+      setReduce (gamma, true);
+    else
+      setReduce (alpha, true);
     if (mipoHasDen)
       coeffE= replacevar (coeffE, gamma, beta);
@@ -619 +631 @@
       {
         setCharacteristic (p);
+        setReduce (alpha, false);
         g= mulNTL (coeffE, j.getItem());
         g= modNTL (g, bufFactors[ii]);
+        setReduce (alpha, true);
         setCharacteristic (0);
         if (mipoHasDen)
         {
+          setReduce (beta, false);
           k.getItem() += replacevar (g.mapinto()*modulus, beta, gamma);
           e -= mulNTL (replacevar (g.mapinto(), beta, gamma)*modulus,
                                    l.getItem(), b);
+          setReduce (beta, true);
         }
         else

factory/facMul.cc

@@ -404 +404 @@
       {
         ZZ_p::init (convertFacCF2NTLZZ (b.getpk()));
-        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (getMipo (alpha)));
+        CanonicalForm mipo= getMipo (alpha);
+        bool is_rat= isOn (SW_RATIONAL);
+        if (!is_rat)
+          On (SW_RATIONAL);
+        mipo *=bCommonDen (mipo);
+        if (!is_rat)
+          Off (SW_RATIONAL);
+        ZZ_pX NTLmipo= to_ZZ_pX (convertFacCF2NTLZZX (mipo));
         ZZ_pE::init (NTLmipo);
         ZZ_pEX NTLg= convertFacCF2NTLZZ_pEX (G, NTLmipo);

factory/fac_ezgcd.cc

@@ -215 +215 @@
   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;