Changeset c1f4d51 in git


Ignore:
Timestamp:
Jul 1, 2020, 4:16:14 PM (4 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '3720ae8bfcff4a4649ee98a15552089151d2d59b')
Children:
2ce3bf354077ca50ab9dbbed78c68d8e279f1297
Parents:
f542551517fde5e0e330f2a5f4ae6e3fdfd32454
Message:
factory: implement findMinPoly/mapPrimElem and related
Location:
factory
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • factory/cfGcdUtil.cc

    rf542551 rc1f4d51  
    2222/// result is false, d is set to the degree of the gcd of f and g evaluated at a
    2323/// random point in K^n-1. This gcd is a gcd of univariate polynomials.
    24 #ifdef HAVE_NTL // mapPrimElem
    2524bool
    2625gcd_test_one ( const CanonicalForm & f, const CanonicalForm & g, bool swap, int & d )
     
    245244    return result;
    246245}
    247 #endif
    248246
    249247/**
  • factory/cfModResultant.cc

    rf542551 rc1f4d51  
    345345}
    346346
    347 #ifdef HAVE_NTL // mapPrimElem
    348347CanonicalForm
    349348resultantFp (const CanonicalForm& A, const CanonicalForm& B, const Variable& x,
     
    522521  return N (H);
    523522}
    524 #endif
    525523
    526524static inline
  • factory/cf_map_ext.cc

    rf542551 rc1f4d51  
    440440}
    441441
    442 #ifdef HAVE_NTL // findMinPoly
    443442CanonicalForm
    444443mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
     
    491490  }
    492491}
    493 #endif
    494492
    495493CanonicalForm
     
    576574}
    577575
    578 #ifdef HAVE_NTL
     576#ifdef HAVE_FLINT
     577/*
     578    g is in Fp[x]
     579    F is in Fp[t]
     580    h is in Fp[t]
     581    In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
     582        g(F(t)) = 0 mod h(t)
     583    i.e. g is the minpoly of the element F(t) of the finite field.
     584*/
     585static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
     586{
     587    slong i;
     588    slong d = nmod_poly_degree(h);
     589    mp_limb_t p = h->mod.n;
     590    nmod_poly_t Fpow;
     591    nmod_berlekamp_massey_t bma;
     592
     593    nmod_poly_init(Fpow, p);
     594    nmod_berlekamp_massey_init(bma, p);
     595
     596    nmod_poly_one(Fpow);
     597    for (i = 0; i < 2*d; i++)
     598    {
     599        nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
     600        nmod_poly_mulmod(Fpow, Fpow, F, h);
     601    }
     602
     603    nmod_berlekamp_massey_reduce(bma);
     604
     605    /* something went horribly wrong if V does not kill the whole sequence */
     606    FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
     607                 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
     608
     609    nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
     610#if WANT_ASSERT
     611    {
     612        nmod_poly_t z;
     613        nmod_poly_init(z, p);
     614        nmod_poly_compose_mod(z, g, F, h);
     615        FLINT_ASSERT(nmod_poly_is_zero(z));
     616        nmod_poly_clear(z);
     617    }
     618#endif
     619    nmod_poly_clear(Fpow);
     620    nmod_berlekamp_massey_clear(bma);
     621}
     622#endif
     623
     624
     625#if defined(HAVE_NTL) || defined(HAVE_FLINT)
    579626CanonicalForm
    580627findMinPoly (const CanonicalForm& F, const Variable& alpha)
     
    582629  ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
    583630
     631  #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
    584632  if (fac_NTL_char != getCharacteristic())
    585633  {
     
    611659
    612660  return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
    613 }
    614 
     661  #elif defined(HAVE_FLINT)
     662  nmod_poly_t FLINT_F,FLINT_alpha,g;
     663  nmod_poly_init(g,getCharacteristic());
     664  convertFacCF2nmod_poly_t(FLINT_F,F);
     665  convertFacCF2nmod_poly_t(FLINT_alpha,getMipo(alpha));
     666  minpoly(g,FLINT_F,FLINT_alpha);
     667  nmod_poly_clear(FLINT_alpha);
     668  nmod_poly_clear(FLINT_F);
     669  CanonicalForm res=convertnmod_poly_t2FacCF(g,Variable(1));
     670  nmod_poly_clear(g);
     671  return res;
     672  #endif
     673}
    615674#endif
  • factory/facFqBivar.cc

    rf542551 rc1f4d51  
    89228922#endif
    89238923
    8924 #ifdef HAVE_NTL // primitiveElement
    89258924CFList
    89268925extBiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
     
    90979096}
    90989097#endif
    9099 #endif
  • factory/facFqFactorize.cc

    rf542551 rc1f4d51  
    3333#include "facMul.h"
    3434#include "cfUnivarGcd.h"
    35 
    36 #ifdef HAVE_NTL
    37 #include "NTLconvert.h"
    3835
    3936TIMING_DEFINE_PRINT(fac_fq_bi_factorizer)
     
    736733}
    737734
     735#if defined(HAVE_NTL) || defined(HAVE_FLINT)
    738736#define CHAR_THRESHOLD 8
    739737CFList
     
    909907  return result;
    910908}
     909#endif
    911910
    912911static inline
     
    19931992}
    19941993
    1995 #endif
    1996 
    19971994static inline
    19981995CanonicalForm prodEval (const CFList& l, const CanonicalForm& evalPoint,
     
    21652162}
    21662163
    2167 #ifdef HAVE_NTL
     2164#if defined(HAVE_NTL) || defined(HAVE_FLINT)
    21682165void
    21692166factorizationWRTDifferentSecondVars (const CanonicalForm& A, CFList*& Aeval,
     
    22042201  }
    22052202}
     2203#endif
    22062204
    22072205CFList conv (const CFArray & A)
     
    29042902}
    29052903
     2904#if defined(HAVE_NTL) || defined(HAVE_FLINT)
    29062905CFList
    29072906extFactorize (const CanonicalForm& F, const ExtensionInfo& info);
     
    38283827  }
    38293828}
    3830 
    38313829#endif
    3832 /* HAVE_NTL */
Note: See TracChangeset for help on using the changeset viewer.