Changeset c1f4d51 in git for factory/cf_map_ext.cc
 Timestamp:
 Jul 1, 2020, 4:16:14 PM (3 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 2ce3bf354077ca50ab9dbbed78c68d8e279f1297
 Parents:
 f542551517fde5e0e330f2a5f4ae6e3fdfd32454
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cf_map_ext.cc
rf542551 rc1f4d51 440 440 } 441 441 442 #ifdef HAVE_NTL // findMinPoly443 442 CanonicalForm 444 443 mapPrimElem (const CanonicalForm& primElem, const Variable& alpha, … … 491 490 } 492 491 } 493 #endif494 492 495 493 CanonicalForm … … 576 574 } 577 575 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 */ 585 static 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) 579 626 CanonicalForm 580 627 findMinPoly (const CanonicalForm& F, const Variable& alpha) … … 582 629 ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)"); 583 630 631 #if defined(HAVE_NTL) && !defined(HAVE_FLINT) 584 632 if (fac_NTL_char != getCharacteristic()) 585 633 { … … 611 659 612 660 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 } 615 674 #endif
Note: See TracChangeset
for help on using the changeset viewer.