Changeset c1b52b in git

Timestamp:

Jul 9, 2020, 4:54:28 PM (3 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')

Children:

22f43fd13906a985efeddb80031ed3478830660e412d19ec6555b98b2f553cc1ea8cf1b7115c830e

Parents:

afa77551770f2019ad99556a95d1327e8a25c616

Message:

factory: factorize char p, univariate (w/o FLINT, w/o NTL)

Location:

factory

Files:

• Makefile.am (modified) (2 diffs)
• cf_defs.h (modified) (1 diff)
• cf_factor.cc (modified) (5 diffs)
• cf_switches.h (modified) (1 diff)
• fac_berlekamp.cc (added)
• fac_berlekamp.h (added)
• fac_cantzass.cc (added)
• fac_cantzass.h (added)
• fac_sqrfree.cc (modified) (1 diff)
• fac_sqrfree.h (modified) (1 diff)

factory/Makefile.am

@@ -65 +65 @@
                 fac_sqrfree.cc \
                 fac_util.cc \
+                fac_berlekamp.cc \
+                fac_cantzass.cc \
                 facFqBivar.cc \
                 facFqBivarUtil.cc \
@@ -145 +147 @@
                 fac_sqrfree.h \
                 fac_util.h \
+                fac_berlekamp.h \
+                fac_cantzass.h \
                 facFqBivar.h \
                 facFqBivarUtil.h \

factory/cf_defs.h

@@ -46 +46 @@
 /// set to 1 to use Flints gcd over Q/Z
 static const int SW_USE_FL_GCD_0=9;
+/// set to 1 to use Factorys Berlekamp alg.
+static const int SW_BERLEKAMP=10;
 
 /*ENDPUBLIC*/

factory/cf_factor.cc

@@ -31 +31 @@
 #include "singext.h"
 #include "cf_util.h"
+#include "fac_berlekamp.h"
+#include "fac_cantzass.h"
 
 #include "int_int.h"
@@ -439 +441 @@
 #endif
       {
-        // use FLINT
+        // use FLINT: char p, univariate
         nmod_poly_t f1;
         convertFacCF2nmod_poly_t (f1, f);
@@ -453 +455 @@
 #endif
 #ifdef HAVE_NTL
-      {
+      { // NTL char 2, univariate
         if (getCharacteristic()==2)
         {
@@ -478 +480 @@
 #ifdef HAVE_NTL
       {
-        // use NTL
+        // use NTL char p, univariate
         if (fac_NTL_char != getCharacteristic())
         {
@@ -503 +505 @@
 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
       // Use Factory without NTL
-      factoryError ("univariate factorization depends on FLINT/NTL(missing)");
-      return CFFList (CFFactor (f, 1));
+      {  // Use Factory without NTL
+        if ( isOn( SW_BERLEKAMP ) )
+          F=FpFactorizeUnivariateB( f, issqrfree );
+        else
+          F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
+        return F;
+      }
 #endif
     }

factory/cf_switches.h

@@ -20 +20 @@
  *
 **/
-const int CFSwitchesMax = 10;
+const int CFSwitchesMax = 11;
 
 /** class CFSwitches

factory/fac_sqrfree.cc

@@ -150 +150 @@
 }
 
+#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
+static int divexp = 1;
+
+static void divexpfunc ( CanonicalForm &, int & e )
+{
+    e /= divexp;
+}
+
+CFFList sqrFreeFp ( const CanonicalForm & f )
+{
+    CanonicalForm t0 = f, t, v, w, h;
+    CanonicalForm leadcf = t0.lc();
+    Variable x = f.mvar();
+    CFFList F;
+    int p = getCharacteristic();
+    int k, e = 1;
+
+    if ( ! leadcf.isOne() )
+        t0 /= leadcf;
+
+    divexp = p;
+    while ( t0.degree(x) > 0 )
+    {
+        t = gcd( t0, t0.deriv() );
+        v = t0 / t;
+        k = 0;
+        while ( v.degree(x) > 0 )
+        {
+            k = k+1;
+            if ( k % p == 0 )
+            {
+                t /= v;
+                k = k+1;
+            }
+            w = gcd( t, v );
+            h = v / w;
+            v = w;
+            t /= v;
+            if ( h.degree(x) > 0 )
+                F.append( CFFactor( h/h.lc(), e*k ) );
+        }
+        t0 = apply( t, divexpfunc );
+        e = p * e;
+    }
+    if ( ! leadcf.isOne() )
+    {
+        if ( !F.isEmpty() && (F.getFirst().exp() == 1) )
+        {
+            leadcf = F.getFirst().factor() * leadcf;
+            F.removeFirst();
+        }
+        F.insert( CFFactor( leadcf, 1 ) );
+    }
+    return F;
+}
+#endif

factory/fac_sqrfree.h

@@ -22 +22 @@
                        );
 
+CFFList sqrFreeFp ( const CanonicalForm & f );
 #endif /* ! INCL_FAC_SQRFREE_H */