Changeset c1f4d51 in git

Timestamp:

Jul 1, 2020, 4:16:14 PM (3 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

2ce3bf354077ca50ab9dbbed78c68d8e279f1297

Parents:

f542551517fde5e0e330f2a5f4ae6e3fdfd32454

Message:

factory: implement findMinPoly/mapPrimElem and related

Location:

factory

Files:

• cfGcdUtil.cc (modified) (2 diffs)
• cfModResultant.cc (modified) (2 diffs)
• cf_map_ext.cc (modified) (5 diffs)
• facFqBivar.cc (modified) (2 diffs)
• facFqFactorize.cc (modified) (8 diffs)

factory/cfGcdUtil.cc

@@ -22 +22 @@
 /// result is false, d is set to the degree of the gcd of f and g evaluated at a
 /// random point in K^n-1. This gcd is a gcd of univariate polynomials.
-#ifdef HAVE_NTL // mapPrimElem
 bool
 gcd_test_one ( const CanonicalForm & f, const CanonicalForm & g, bool swap, int & d )
@@ -245 +244 @@
     return result;
 }
-#endif
 
 /**

factory/cfModResultant.cc

@@ -345 +345 @@
 }
 
-#ifdef HAVE_NTL // mapPrimElem
 CanonicalForm
 resultantFp (const CanonicalForm& A, const CanonicalForm& B, const Variable& x,
@@ -522 +521 @@
   return N (H);
 }
-#endif
 
 static inline

factory/cf_map_ext.cc

@@ -440 +440 @@
 }
 
-#ifdef HAVE_NTL // findMinPoly
 CanonicalForm
 mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
@@ -491 +490 @@
   }
 }
-#endif
 
 CanonicalForm
@@ -576 +574 @@
 }
 
-#ifdef HAVE_NTL
+#ifdef HAVE_FLINT
+/*
+    g is in Fp[x]
+    F is in Fp[t]
+    h is in Fp[t]
+    In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
+        g(F(t)) = 0 mod h(t)
+    i.e. g is the minpoly of the element F(t) of the finite field.
+*/
+static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
+{
+    slong i;
+    slong d = nmod_poly_degree(h);
+    mp_limb_t p = h->mod.n;
+    nmod_poly_t Fpow;
+    nmod_berlekamp_massey_t bma;
+
+    nmod_poly_init(Fpow, p);
+    nmod_berlekamp_massey_init(bma, p);
+
+    nmod_poly_one(Fpow);
+    for (i = 0; i < 2*d; i++)
+    {
+        nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
+        nmod_poly_mulmod(Fpow, Fpow, F, h);
+    }
+
+    nmod_berlekamp_massey_reduce(bma);
+
+    /* something went horribly wrong if V does not kill the whole sequence */
+    FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
+                 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
+
+    nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
+#if WANT_ASSERT
+    {
+        nmod_poly_t z;
+        nmod_poly_init(z, p);
+        nmod_poly_compose_mod(z, g, F, h);
+        FLINT_ASSERT(nmod_poly_is_zero(z));
+        nmod_poly_clear(z);
+    }
+#endif
+    nmod_poly_clear(Fpow);
+    nmod_berlekamp_massey_clear(bma);
+}
+#endif
+
+
+#if defined(HAVE_NTL) || defined(HAVE_FLINT)
 CanonicalForm
 findMinPoly (const CanonicalForm& F, const Variable& alpha)
@@ -582 +629 @@
   ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
 
+  #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
   if (fac_NTL_char != getCharacteristic())
   {
@@ -611 +659 @@
 
   return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
-}
-
+  #elif defined(HAVE_FLINT)
+  nmod_poly_t FLINT_F,FLINT_alpha,g;
+  nmod_poly_init(g,getCharacteristic());
+  convertFacCF2nmod_poly_t(FLINT_F,F);
+  convertFacCF2nmod_poly_t(FLINT_alpha,getMipo(alpha));
+  minpoly(g,FLINT_F,FLINT_alpha);
+  nmod_poly_clear(FLINT_alpha);
+  nmod_poly_clear(FLINT_F);
+  CanonicalForm res=convertnmod_poly_t2FacCF(g,Variable(1));
+  nmod_poly_clear(g);
+  return res;
+  #endif
+}
 #endif

factory/facFqBivar.cc

@@ -8922 +8922 @@
 #endif
 
-#ifdef HAVE_NTL // primitiveElement
 CFList
 extBiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
@@ -9097 +9096 @@
 }
 #endif
-#endif

factory/facFqFactorize.cc

@@ -33 +33 @@
 #include "facMul.h"
 #include "cfUnivarGcd.h"
-
-#ifdef HAVE_NTL
-#include "NTLconvert.h"
 
 TIMING_DEFINE_PRINT(fac_fq_bi_factorizer)
@@ -736 +733 @@
 }
 
+#if defined(HAVE_NTL) || defined(HAVE_FLINT)
 #define CHAR_THRESHOLD 8
 CFList
@@ -909 +907 @@
   return result;
 }
+#endif
 
 static inline
@@ -1993 +1992 @@
 }
 
-#endif
-
 static inline
 CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
@@ -2165 +2162 @@
 }
 
-#ifdef HAVE_NTL
+#if defined(HAVE_NTL) || defined(HAVE_FLINT)
 void
 factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
@@ -2204 +2201 @@
   }
 }
+#endif
 
 CFList conv (const CFArray & A)
@@ -2904 +2902 @@
 }
 
+#if defined(HAVE_NTL) || defined(HAVE_FLINT)
 CFList
 extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
@@ -3828 +3827 @@
   }
 }
-
 #endif
-/* HAVE_NTL */