Changeset e73082 in git

Timestamp:

Jul 10, 2020, 10:59:54 AM (4 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

92ca340b57708a644bf8460eb08f23f4c5a25c1e

Parents:

8ef929c017bd275741976e337ce6a61e6fec53d9

Message:

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

Location:

factory

Files:

• Makefile.am (modified) (4 diffs)
• cf_char.cc (modified) (2 diffs)
• cf_defs.h (modified) (2 diffs)
• cf_factor.cc (modified) (3 diffs)
• cf_switches.h (modified) (1 diff)
• fac_univar.cc (moved) (moved from factory/old/fac_univar.cc) (5 diffs)
• fac_univar.h (moved) (moved from factory/old/fac_univar.h)
• int_pp.cc (moved) (moved from factory/old/int_pp.cc) (2 diffs)
• int_pp.h (moved) (moved from factory/old/int_pp.h)

factory/Makefile.am

@@ -67 +67 @@
                 fac_berlekamp.cc \
                 fac_cantzass.cc \
+                fac_univar.cc \
                 facFqBivar.cc \
                 facFqBivarUtil.cc \
@@ -86 +87 @@
                 int_poly.cc \
                 int_rat.cc \
+                int_pp.cc \
                 variable.cc \
                 NTLconvert.cc \
@@ -149 +151 @@
                 fac_berlekamp.h \
                 fac_cantzass.h \
+                fac_univar.h \
                 facFqBivar.h \
                 facFqBivarUtil.h \
@@ -168 +171 @@
                 int_poly.h \
                 int_rat.h \
+                int_pp.h \
                 timing.h \
                 variable.h \

factory/cf_char.cc

@@ -17 +17 @@
 #include "cf_primes.h"
 #include "cf_util.h"
+#include "int_pp.h"
 
 STATIC_VAR int theCharacteristic = 0;
@@ -43 +44 @@
 }
 
+#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
+void setCharacteristic( int c, int n )
+{
+    ASSERT( c > 1 && n > 0, "illegal characteristic" );
+    setCharacteristic( c );
+    InternalPrimePower::setPrimePower( c, n );
+    CFFactory::settype( PrimePowerDomain );
+}
+#endif
+
+
 void setCharacteristic( int c, int n, char name )
 {

factory/cf_defs.h

@@ -21 +21 @@
 
 #define UndefinedDomain 32000
+#define PrimePowerDomain 5
 #define GaloisFieldDomain 4
 #define FiniteFieldDomain 3
@@ -49 +50 @@
 static const int SW_BERLEKAMP=10;
 
+static const int SW_FAC_QUADRATICLIFT=11;
 /*ENDPUBLIC*/
 

factory/cf_factor.cc

@@ -33 +33 @@
 #include "fac_berlekamp.h"
 #include "fac_cantzass.h"
+#include "fac_univar.h"
 
 #include "int_int.h"
@@ -504 +505 @@
 #endif
 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
-      // Use Factory without NTL
-      {  // Use Factory without NTL
+      // Use Factory without NTL: char p, univariate
+      {
         if ( isOn( SW_BERLEKAMP ) )
           F=FpFactorizeUnivariateB( f, issqrfree );
@@ -601 +602 @@
       goto end_char0;
       #else
-      factoryError ("univariate factorization over Z depends on NTL/FLINT(missing)");
-      return CFFList (CFFactor (f, 1));
+      {
+        //Use Factory without NTL: char 0, univariate
+        F = ZFactorizeUnivariate( fz, issqrfree );
+        goto end_char0;
+      }
       #endif
     }

factory/cf_switches.h

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

factory/fac_univar.cc

@@ -18 +18 @@
 #include "cf_primes.h"
 #include "fac_sqrfree.h"
-
+#include "cfUnivarGcd.h"
+
+#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
 TIMING_DEFINE_PRINT(fac_choosePrimes)
 TIMING_DEFINE_PRINT(fac_facModPrimes)
@@ -215 +217 @@
 }
 
+bool isSqrFreeZ ( const CanonicalForm & f )
+{
+    return gcd( f, f.deriv() ).degree() == 0;
+}
+
+bool isSqrFreeFp( const CanonicalForm & f )
+{
+  CFFList F = sqrFreeFp( f );
+  return ( F.length() == 1 && F.getFirst().exp() == 1 );
+}
+
+bool isSqrFree ( const CanonicalForm & f )
+{
+//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
+    if ( getCharacteristic() == 0 )
+        return isSqrFreeZ( f );
+    else
+        return isSqrFreeFp( f );
+}
+
 
 static int choosePrimes ( int * p, const CanonicalForm & f )
@@ -249 +271 @@
     int i, j, save;
     int p = pk.getp(), k = pk.getk();
-    int no_iter = (int)(log( (double)k )/log(2.0)+2);
+    int no_iter = SI_LOG2(k)+2;
     int * kvals = new int[no_iter];
 
@@ -278 +300 @@
         {
             j--;
-            setCharacteristic( p, kvals[j+1] );
+            setCharacteristic( p, kvals[j+1]);
             DEBOUTLN( cerr, "lifting from p^" << kvals[j+1] << " to p^" << kvals[j] );
             c = mapinto( c );
@@ -542 +564 @@
     return ZF;
 }
+#endif

factory/int_pp.cc

@@ -13 +13 @@
 #include "imm.h"
 
+#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
 mpz_t InternalPrimePower::primepow;
 mpz_t InternalPrimePower::primepowhalf;
@@ -408 +409 @@
 }
 //}}}
+#endif