My Project
Loading...
Searching...
No Matches
Functions | Variables
cf_factor.cc File Reference

Interface to factorization and square free factorization algorithms. More...

#include "config.h"
#include "cf_assert.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "fac_sqrfree.h"
#include "cf_algorithm.h"
#include "facFqFactorize.h"
#include "facFqSquarefree.h"
#include "cf_map.h"
#include "facAlgExt.h"
#include "facFactorize.h"
#include "singext.h"
#include "cf_util.h"
#include "fac_berlekamp.h"
#include "fac_cantzass.h"
#include "fac_univar.h"
#include "fac_multivar.h"
#include "int_int.h"
#include "NTLconvert.h"
#include "factory/cf_gmp.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Functions

void find_exp (const CanonicalForm &f, int *exp_f)
 
int find_mvar (const CanonicalForm &f)
 
void out_cf (const char *s1, const CanonicalForm &f, const char *s2)
 cf_algorithm.cc - simple mathematical algorithms. More...
 
void out_cff (CFFList &L)
 
void test_cff (CFFList &L, const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
bool isPurePoly (const CanonicalForm &f)
 
Variable get_max_degree_Variable (const CanonicalForm &f)
 get_max_degree_Variable returns Variable with highest degree. More...
 
void getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result)
 get_Terms: Split the polynomial in the containing terms. More...
 
CFList get_Terms (const CanonicalForm &f)
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x More...
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x, const Variable &v1, const Variable &v2)
 
int cmpCF (const CFFactor &f, const CFFactor &g)
 
CFFList factorize (const CanonicalForm &f, bool issqrfree)
 factorization over $ F_p $ or $ Q $ More...
 
CFFList factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $ More...
 
CFFList sqrFree (const CanonicalForm &f, bool sort)
 squarefree factorization More...
 

Variables

VAR int singular_homog_flag =1
 

Detailed Description

Interface to factorization and square free factorization algorithms.

Used by: cf_irred.cc

Header file: cf_algorithm.h

Definition in file cf_factor.cc.

Function Documentation

◆ cmpCF()

int cmpCF ( const CFFactor f,
const CFFactor g 
)

Definition at line 394 of file cf_factor.cc.

395{
396 if (f.exp() > g.exp()) return 1;
397 if (f.exp() < g.exp()) return 0;
398 if (f.factor() > g.factor()) return 1;
399 return 0;
400}
g
Definition: cfModGcd.cc:4090
FILE * f
Definition: checklibs.c:9

◆ factorize() [1/2]

CFFList factorize ( const CanonicalForm f,
bool  issqrfree 
)

factorization over $ F_p $ or $ Q $

Definition at line 405 of file cf_factor.cc.

406{
407 if ( f.inCoeffDomain() )
408 return CFFList( f );
409#ifndef NOASSERT
410 Variable a;
411 ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
412 ( const CanonicalForm & f, const Variable & alpha ) instead");
413#endif
414 //out_cf("factorize:",f,"==================================\n");
415 if (! f.isUnivariate() ) // preprocess homog. polys
416 {
417 if ( singular_homog_flag && f.isHomogeneous())
418 {
420 int d_xn = degree(f,xn);
421 CFMap n;
422 CanonicalForm F = compress(f(1,xn),n);
423 CFFList Intermediatelist;
424 Intermediatelist = factorize(F);
425 CFFList Homoglist;
427 for ( j=Intermediatelist; j.hasItem(); j++ )
428 {
429 Homoglist.append(
430 CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
431 }
432 CFFList Unhomoglist;
433 CanonicalForm unhomogelem;
434 for ( j=Homoglist; j.hasItem(); j++ )
435 {
436 unhomogelem= homogenize(j.getItem().factor(),xn);
437 Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
438 d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
439 }
440 if ( d_xn != 0 ) // have to append xn^(d_xn)
441 Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
442 if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
443 return Unhomoglist;
444 }
445 }
446 CFFList F;
447 if ( getCharacteristic() > 0 )
448 {
449 if (f.isUnivariate())
450 {
451#ifdef HAVE_FLINT
452#ifdef HAVE_NTL
453 if (degree (f) < 300)
454#endif
455 {
456 // use FLINT: char p, univariate
457 nmod_poly_t f1;
459 nmod_poly_factor_t result;
460 nmod_poly_factor_init (result);
461 mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
462 F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
463 nmod_poly_factor_clear (result);
464 nmod_poly_clear (f1);
466 return F;
467 }
468#endif
469#ifdef HAVE_NTL
470 { // NTL char 2, univariate
471 if (getCharacteristic()==2)
472 {
473 // Specialcase characteristic==2
474 if (fac_NTL_char != 2)
475 {
476 fac_NTL_char = 2;
477 zz_p::init(2);
478 }
479 // convert to NTL using the faster conversion routine for characteristic 2
480 GF2X f1=convertFacCF2NTLGF2X(f);
481 // no make monic necessary in GF2
482 //factorize
483 vec_pair_GF2X_long factors;
484 CanZass(factors,f1);
485
486 // convert back to factory again using the faster conversion routine for vectors over GF2X
487 F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
489 return F;
490 }
491 }
492#endif
493#ifdef HAVE_NTL
494 {
495 // use NTL char p, univariate
497 {
499 zz_p::init(getCharacteristic());
500 }
501
502 // convert to NTL
503 zz_pX f1=convertFacCF2NTLzzpX(f);
504 zz_p leadcoeff = LeadCoeff(f1);
505
506 //make monic
507 f1=f1 / LeadCoeff(f1);
508 // factorize
509 vec_pair_zz_pX_long factors;
510 CanZass(factors,f1);
511
512 F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
513 //test_cff(F,f);
515 return F;
516 }
517#endif
518#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
519 // Use Factory without NTL and without FLINT: char p, univariate
520 {
521 if ( isOn( SW_BERLEKAMP ) )
522 F=FpFactorizeUnivariateB( f, issqrfree );
523 else
524 F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
525 return F;
526 }
527#endif
528 }
529 else // char p, multivariate
530 {
532 {
533 #if defined(HAVE_NTL)
534 if (issqrfree)
535 {
536 CFList factors;
538 factors= GFSqrfFactorize (f);
539 for (CFListIterator i= factors; i.hasItem(); i++)
540 F.append (CFFactor (i.getItem(), 1));
541 }
542 else
543 {
545 F= GFFactorize (f);
546 }
547 #else
548 factoryError ("multivariate factorization over GF depends on NTL(missing)");
549 return CFFList (CFFactor (f, 1));
550 #endif
551 }
552 else
553 {
554 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
555 if (!isOn(SW_USE_FL_FAC_P))
556 {
557 #endif
558 #if defined(HAVE_NTL)
559 if (issqrfree)
560 {
561 CFList factors;
563 factors= FpSqrfFactorize (f);
564 for (CFListIterator i= factors; i.hasItem(); i++)
565 F.append (CFFactor (i.getItem(), 1));
566 goto end_charp;
567 }
568 else
569 {
571 F= FpFactorize (f);
572 goto end_charp;
573 }
574 #endif
575 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
576 }
577 #endif
578 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
579 nmod_mpoly_ctx_t ctx;
580 nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
581 nmod_mpoly_t Flint_f;
582 nmod_mpoly_init(Flint_f,ctx);
583 convFactoryPFlintMP(f,Flint_f,ctx,f.level());
584 nmod_mpoly_factor_t factors;
585 nmod_mpoly_factor_init(factors,ctx);
586 int okay;
587 if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
588 else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
589 nmod_mpoly_t fac;
590 nmod_mpoly_init(fac,ctx);
591 CanonicalForm cf_fac;
592 int cf_exp;
593 cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
594 F.append(CFFactor(cf_fac,1));
595 for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
596 {
597 nmod_mpoly_factor_get_base(fac,factors,i,ctx);
598 cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
599 cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
600 F.append(CFFactor(cf_fac,cf_exp));
601 }
602 nmod_mpoly_factor_clear(factors,ctx);
603 nmod_mpoly_clear(Flint_f,ctx);
604 nmod_mpoly_ctx_clear(ctx);
605 if (okay==0)
606 {
609 F=factorize(f,issqrfree);
612 }
613 #endif
614 #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
615 #ifndef HAVE_NTL
616 factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
617 return CFFList (CFFactor (f, 1));
618 #endif
619 #endif
620 }
621 }
622 }
623 else // char 0
624 {
625 bool on_rational = isOn(SW_RATIONAL);
628 CanonicalForm fz = f * cd;
630 if ( f.isUnivariate() )
631 {
632 CanonicalForm ic=icontent(fz);
633 fz/=ic;
634 if (fz.degree()==1)
635 {
636 F=CFFList(CFFactor(fz,1));
637 F.insert(CFFactor(ic,1));
638 }
639 else
640 #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
641 {
642 // FLINT 2.6.0 has a bug:
643 // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
644 // use FLINT: char 0, univariate
645 fmpz_poly_t f1;
647 fmpz_poly_factor_t result;
648 fmpz_poly_factor_init (result);
649 fmpz_poly_factor(result, f1);
651 fmpz_poly_factor_clear (result);
652 fmpz_poly_clear (f1);
653 if ( ! ic.isOne() )
654 {
655 // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
656 // first entry is in CoeffDomain
657 CFFactor new_first( F.getFirst().factor() * ic );
658 F.removeFirst();
659 F.insert( new_first );
660 }
661 }
662 goto end_char0;
663 #elif defined(HAVE_NTL)
664 {
665 //use NTL
666 ZZ c;
667 vec_pair_ZZX_long factors;
668 //factorize the converted polynomial
669 factor(c,factors,convertFacCF2NTLZZX(fz));
670
671 //convert the result back to Factory
673 if ( ! ic.isOne() )
674 {
675 // according to convertNTLvec_pair_ZZX_long2FacCFFList
676 // first entry is in CoeffDomain
677 CFFactor new_first( F.getFirst().factor() * ic );
678 F.removeFirst();
679 F.insert( new_first );
680 }
681 }
682 goto end_char0;
683 #else
684 {
685 //Use Factory without NTL: char 0, univariate
686 F = ZFactorizeUnivariate( fz, issqrfree );
687 goto end_char0;
688 }
689 #endif
690 }
691 else // multivariate, char 0
692 {
693 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
695 {
696 On (SW_RATIONAL);
697 fmpz_mpoly_ctx_t ctx;
698 fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
699 fmpz_mpoly_t Flint_f;
700 fmpz_mpoly_init(Flint_f,ctx);
701 convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
702 fmpz_mpoly_factor_t factors;
703 fmpz_mpoly_factor_init(factors,ctx);
704 int rr;
705 if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
706 else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
707 if (rr==0) printf("fail\n");
708 fmpz_mpoly_t fac;
709 fmpz_mpoly_init(fac,ctx);
710 CanonicalForm cf_fac;
711 int cf_exp;
712 fmpz_t c;
713 fmpz_init(c);
714 fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
715 cf_fac=convertFmpz2CF(c);
716 fmpz_clear(c);
717 F.append(CFFactor(cf_fac,1));
718 for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
719 {
720 fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
721 cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
722 cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
723 F.append(CFFactor(cf_fac,cf_exp));
724 }
725 fmpz_mpoly_factor_clear(factors,ctx);
726 fmpz_mpoly_clear(Flint_f,ctx);
727 fmpz_mpoly_ctx_clear(ctx);
728 goto end_char0;
729 }
730 #endif
731 #if defined(HAVE_NTL)
732 On (SW_RATIONAL);
733 if (issqrfree)
734 {
735 CFList factors= ratSqrfFactorize (fz);
736 for (CFListIterator i= factors; i.hasItem(); i++)
737 F.append (CFFactor (i.getItem(), 1));
738 }
739 else
740 {
741 F = ratFactorize (fz);
742 }
743 #endif
744 #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
745 #ifndef HAVE_NTL
746 F=ZFactorizeMultivariate(fz, issqrfree);
747 #endif
748 #endif
749 }
750
751end_char0:
752 if ( on_rational )
754 else
756 if ( ! cd.isOne() )
757 {
758 CFFactor new_first( F.getFirst().factor() / cd );
759 F.removeFirst();
760 F.insert( new_first );
761 }
762 }
763
764#if defined(HAVE_NTL)
765end_charp:
766#endif
768 return F;
769}
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:446
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition: NTLconvert.cc:399
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:184
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:753
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int degree(const CanonicalForm &f)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: cf_defs.h:47
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:39
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:57
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:55
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition: cf_defs.h:51
#define GaloisFieldDomain
Definition: cf_defs.h:18
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:260
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:394
VAR int singular_homog_flag
Definition: cf_factor.cc:392
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:313
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:405
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
int level() const
level() returns the level of CO.
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: variable.h:33
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
CanonicalForm factor
Definition: facAbsFact.cc:97
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:79
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
int j
Definition: facHensel.cc:110
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
VAR int xn
Definition: walk.cc:4508

◆ factorize() [2/2]

CFFList factorize ( const CanonicalForm f,
const Variable alpha 
)

factorization over $ F_p(\alpha) $ or $ Q(\alpha) $

Definition at line 774 of file cf_factor.cc.

775{
776 if ( f.inCoeffDomain() )
777 return CFFList( f );
778 //out_cf("factorize:",f,"==================================\n");
779 //out_cf("mipo:",getMipo(alpha),"\n");
780
781 CFFList F;
782 ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
783#ifndef NOASSERT
785 if (hasFirstAlgVar(f, beta))
786 ASSERT (beta == alpha, "f has an algebraic variable that \
787 does not coincide with alpha");
788#endif
789 int ch=getCharacteristic();
790 if (ch>0)
791 {
792 if (f.isUnivariate())
793 {
794#ifdef HAVE_NTL
795 if (/*getCharacteristic()*/ch==2)
796 {
797 // special case : GF2
798
799 // remainder is two ==> nothing to do
800
801 // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
802 GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
803 GF2E::init (minPo);
804
805 // convert to NTL again using the faster conversion routines
806 GF2EX f1;
807 if (isPurePoly(f))
808 {
809 GF2X f_tmp=convertFacCF2NTLGF2X(f);
810 f1=to_GF2EX(f_tmp);
811 }
812 else
813 f1=convertFacCF2NTLGF2EX(f,minPo);
814
815 // make monic (in Z/2(a))
816 GF2E f1_coef=LeadCoeff(f1);
817 MakeMonic(f1);
818
819 // factorize using NTL
820 vec_pair_GF2EX_long factors;
821 CanZass(factors,f1);
822
823 // return converted result
824 F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
826 return F;
827 }
828#endif
829#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
830 {
831 // use FLINT
832 nmod_poly_t FLINTmipo, leadingCoeff;
833 fq_nmod_ctx_t fq_con;
834
835 nmod_poly_init (FLINTmipo, ch);
836 nmod_poly_init (leadingCoeff, ch);
838
839 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
840 fq_nmod_poly_t FLINTF;
842 fq_nmod_poly_factor_t res;
843 fq_nmod_poly_factor_init (res, fq_con);
844 fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
846 F.insert (CFFactor (Lc (f), 1));
847
848 fq_nmod_poly_factor_clear (res, fq_con);
849 fq_nmod_poly_clear (FLINTF, fq_con);
850 nmod_poly_clear (FLINTmipo);
851 nmod_poly_clear (leadingCoeff);
854 return F;
855 }
856#endif
857#ifdef HAVE_NTL
858 {
859 // use NTL
860 if (fac_NTL_char != ch)
861 {
862 fac_NTL_char = ch;
863 zz_p::init(ch);
864 }
865
866 // set minimal polynomial in NTL
867 zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
868 zz_pE::init (minPo);
869
870 // convert to NTL
871 zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
872 zz_pE leadcoeff= LeadCoeff(f1);
873
874 //make monic
875 f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
876
877 // factorize
878 vec_pair_zz_pEX_long factors;
879 CanZass(factors,f1);
880
881 // return converted result
882 F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
883 //test_cff(F,f);
885 return F;
886 }
887#endif
888#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
889 // char p, extension, univariate
890 CanonicalForm c=Lc(f);
891 CanonicalForm fc=f/c;
892 F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
893 F.insert (CFFactor (c, 1));
894#endif
895 }
896 else // char p, multivariate
897 {
898 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
899 // use FLINT
900 nmod_poly_t FLINTmipo;
901 fq_nmod_ctx_t fq_con;
902 fq_nmod_mpoly_ctx_t ctx;
903
904 nmod_poly_init (FLINTmipo, ch);
906
907 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
908 fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
909
910 fq_nmod_mpoly_t FLINTF;
911 fq_nmod_mpoly_init(FLINTF,ctx);
912 convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
913 fq_nmod_mpoly_factor_t res;
914 fq_nmod_mpoly_factor_init (res, ctx);
915 fq_nmod_mpoly_factor (res, FLINTF, ctx);
916 F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
917 //F.insert (CFFactor (Lc (f), 1));
918
919 fq_nmod_mpoly_factor_clear (res, ctx);
920 fq_nmod_mpoly_clear (FLINTF, ctx);
921 nmod_poly_clear (FLINTmipo);
922 fq_nmod_mpoly_ctx_clear (ctx);
925 return F;
926 #elif defined(HAVE_NTL)
927 F= FqFactorize (f, alpha);
928 #else
929 factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
930 return CFFList (CFFactor (f, 1));
931 #endif
932 }
933 }
934 else // Q(a)[x]
935 {
936 if (f.isUnivariate())
937 {
938 F= AlgExtFactorize (f, alpha);
939 }
940 else //Q(a)[x1,...,xn]
941 {
942 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
943 F= ratFactorize (f, alpha);
944 #else
945 factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
946 return CFFList (CFFactor (f, 1));
947 #endif
948 }
949 }
951 return F;
952}
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:870
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:959
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1007
CanonicalForm Lc(const CanonicalForm &f)
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
int level() const
Definition: variable.h:49
CanonicalForm res
Definition: facAbsFact.cc:60
Variable beta
Definition: facAbsFact.cc:95
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:370
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear(prod, fq_con)
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207

◆ find_exp()

void find_exp ( const CanonicalForm f,
int *  exp_f 
)

Definition at line 62 of file cf_factor.cc.

63{
64 if ( ! f.inCoeffDomain() )
65 {
66 int e=f.level();
67 CFIterator i = f;
68 if (e>=0)
69 {
70 if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
71 }
72 for (; i.hasTerms(); i++ )
73 {
74 find_exp(i.coeff(), exp_f);
75 }
76 }
77}
void find_exp(const CanonicalForm &f, int *exp_f)
Definition: cf_factor.cc:62
class to iterate through CanonicalForm's
Definition: cf_iter.h:44

◆ find_mvar()

int find_mvar ( const CanonicalForm f)

Definition at line 79 of file cf_factor.cc.

80{
81 int mv=f.level();
82 int *exp_f=NEW_ARRAY(int,mv+1);
83 int i;
84 for(i=mv;i>0;i--) exp_f[i]=0;
85 find_exp(f,exp_f);
86 for(i=mv;i>0;i--)
87 {
88 if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
89 {
90 mv=i;
91 }
92 }
93 DELETE_ARRAY(exp_f);
94 return mv;
95}
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64

◆ get_max_degree_Variable()

Variable get_max_degree_Variable ( const CanonicalForm f)

get_max_degree_Variable returns Variable with highest degree.

We assume f is not a constant!

Definition at line 260 of file cf_factor.cc.

261{
262 ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
263 int max=0, maxlevel=0, n=level(f);
264 for ( int i=1; i<=n; i++ )
265 {
266 if (degree(f,Variable(i)) >= max)
267 {
268 max= degree(f,Variable(i)); maxlevel= i;
269 }
270 }
271 return Variable(maxlevel);
272}
int level(const CanonicalForm &f)
static int max(int a, int b)
Definition: fast_mult.cc:264

◆ get_Terms()

CFList get_Terms ( const CanonicalForm f)

Definition at line 289 of file cf_factor.cc.

289 {
290 CFList result,dummy,dummy2;
293
294 if ( getNumVars(f) == 0 ) result.append(f);
295 else{
296 Variable _x(level(f));
297 for ( i=f; i.hasTerms(); i++ ){
298 getTerms(i.coeff(), 1, dummy);
299 for ( j=dummy; j.hasItem(); j++ )
300 result.append(j.getItem() * power(_x, i.exp()));
301
302 dummy= dummy2; // have to initalize new
303 }
304 }
305 return result;
306}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:279

◆ getTerms()

void getTerms ( const CanonicalForm f,
const CanonicalForm t,
CFList result 
)

get_Terms: Split the polynomial in the containing terms.

getTerms: the real work is done here.

Definition at line 279 of file cf_factor.cc.

280{
281 if ( getNumVars(f) == 0 ) result.append(f*t);
282 else{
283 Variable x(level(f));
284 for ( CFIterator i=f; i.hasTerms(); i++ )
285 getTerms( i.coeff(), t*power(x,i.exp()), result);
286 }
287}
Variable x
Definition: cfModGcd.cc:4082

◆ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x 
)

homogenize homogenizes f with Variable x

Definition at line 313 of file cf_factor.cc.

314{
315#if 0
316 int maxdeg=totaldegree(f), deg;
318 CanonicalForm elem, result(0);
319
320 for (i=f; i.hasTerms(); i++)
321 {
322 elem= i.coeff()*power(f.mvar(),i.exp());
323 deg = totaldegree(elem);
324 if ( deg < maxdeg )
325 result += elem * power(x,maxdeg-deg);
326 else
327 result+=elem;
328 }
329 return result;
330#else
331 CFList Newlist, Termlist= get_Terms(f);
332 int maxdeg=totaldegree(f), deg;
334 CanonicalForm elem, result(0);
335
336 for (i=Termlist; i.hasItem(); i++)
337 {
338 elem= i.getItem();
339 deg = totaldegree(elem);
340 if ( deg < maxdeg )
341 Newlist.append(elem * power(x,maxdeg-deg));
342 else
343 Newlist.append(elem);
344 }
345 for (i=Newlist; i.hasItem(); i++) // rebuild
346 result += i.getItem();
347
348 return result;
349#endif
350}
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:289

◆ homogenize() [2/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x,
const Variable v1,
const Variable v2 
)

Definition at line 353 of file cf_factor.cc.

354{
355#if 0
356 int maxdeg=totaldegree(f), deg;
358 CanonicalForm elem, result(0);
359
360 for (i=f; i.hasTerms(); i++)
361 {
362 elem= i.coeff()*power(f.mvar(),i.exp());
363 deg = totaldegree(elem);
364 if ( deg < maxdeg )
365 result += elem * power(x,maxdeg-deg);
366 else
367 result+=elem;
368 }
369 return result;
370#else
371 CFList Newlist, Termlist= get_Terms(f);
372 int maxdeg=totaldegree(f), deg;
374 CanonicalForm elem, result(0);
375
376 for (i=Termlist; i.hasItem(); i++)
377 {
378 elem= i.getItem();
379 deg = totaldegree(elem,v1,v2);
380 if ( deg < maxdeg )
381 Newlist.append(elem * power(x,maxdeg-deg));
382 else
383 Newlist.append(elem);
384 }
385 for (i=Newlist; i.hasItem(); i++) // rebuild
386 result += i.getItem();
387
388 return result;
389#endif
390}

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 244 of file cf_factor.cc.

245{
246 if (f.level()<=0) return false;
247 for (CFIterator i=f;i.hasTerms();i++)
248 {
249 if (!(i.coeff().inBaseDomain())) return false;
250 }
251 return true;
252}

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm f)

Definition at line 234 of file cf_factor.cc.

235{
236 if (f.inBaseDomain()) return true;
237 if (f.level()<0) return false;
238 for (CFIterator i=f;i.hasTerms();i++)
239 {
240 if (!isPurePoly_m(i.coeff())) return false;
241 }
242 return true;
243}
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:234

◆ out_cf()

void out_cf ( const char *  s1,
const CanonicalForm f,
const char *  s2 
)

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in ‘cf_ops.cc’, which are structural algorithms.

Definition at line 99 of file cf_factor.cc.

100{
101 printf("%s",s1);
102 if (f.isZero()) printf("+0");
103 //else if (! f.inCoeffDomain() )
104 else if (! f.inBaseDomain() )
105 {
106 int l = f.level();
107 for ( CFIterator i = f; i.hasTerms(); i++ )
108 {
109 int e=i.exp();
110 if (i.coeff().isOne())
111 {
112 printf("+");
113 if (e==0) printf("1");
114 else
115 {
116 printf("%c",'a'+l-1);
117 if (e!=1) printf("^%d",e);
118 }
119 }
120 else
121 {
122 out_cf("+(",i.coeff(),")");
123 if (e!=0)
124 {
125 printf("*%c",'a'+l-1);
126 if (e!=1) printf("^%d",e);
127 }
128 }
129 }
130 }
131 else
132 {
133 if ( f.isImm() )
134 {
136 {
137 long a= imm2int (f.getval());
138 if ( a == gf_q )
139 printf ("+%ld", a);
140 else if ( a == 0L )
141 printf ("+1");
142 else if ( a == 1L )
143 printf ("+%c",gf_name);
144 else
145 {
146 printf ("+%c",gf_name);
147 printf ("^%ld",a);
148 }
149 }
150 else
151 {
152 long l=f.intval();
153 if (l<0) printf("%ld",l);
154 else printf("+%ld",l);
155 }
156 }
157 else
158 {
159 #ifdef NOSTREAMIO
160 if (f.inZ())
161 {
162 mpz_t m;
164 char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
165 str = mpz_get_str( str, 10, m );
166 puts(str);
167 delete[] str;
168 mpz_clear(m);
169 }
170 else if (f.inQ())
171 {
172 mpz_t m;
174 char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
175 str = mpz_get_str( str, 10, m );
176 while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
177 puts(str);putchar('/');
178 delete[] str;
179 mpz_clear(m);
181 str = new char[mpz_sizeinbase( m, 10 ) + 2];
182 str = mpz_get_str( str, 10, m );
183 while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
184 puts(str);
185 delete[] str;
186 mpz_clear(m);
187 }
188 #else
189 std::cout << f;
190 #endif
191 }
192 //if (f.inZ()) printf("(Z)");
193 //else if (f.inQ()) printf("(Q)");
194 //else if (f.inFF()) printf("(FF)");
195 //else if (f.inPP()) printf("(PP)");
196 //else if (f.inGF()) printf("(PP)");
197 //else
198 if (f.inExtension()) printf("E(%d)",f.level());
199 }
200 printf("%s",s2);
201}
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:99
VAR int gf_q
Definition: gfops.cc:47
VAR char gf_name
Definition: gfops.cc:52
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
char * str(leftv arg)
Definition: shared.cc:704
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20

◆ out_cff()

void out_cff ( CFFList L)

Definition at line 202 of file cf_factor.cc.

203{
204 //int n = L.length();
205 CFFListIterator J=L;
206 int j=0;
207 for ( ; J.hasItem(); J++, j++ )
208 {
209 printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
210 printf("%d\n", J.getItem().exp());
211 }
212}
T & getItem() const
Definition: ftmpl_list.cc:431

◆ sqrFree()

CFFList sqrFree ( const CanonicalForm f,
bool  sort 
)

squarefree factorization

Definition at line 957 of file cf_factor.cc.

958{
959// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
961
962 if ( getCharacteristic() == 0 )
963 result = sqrFreeZ( f );
964 else
965 {
967 if (hasFirstAlgVar (f, alpha))
968 result = FqSqrf( f, alpha );
969 else
970 result= FpSqrf (f);
971 }
972 if (sort)
973 {
974 CFFactor buf= result.getFirst();
975 result.removeFirst();
977 result.insert (buf);
978 }
979 return result;
980}
static void sort(int **points, int sizePoints)
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:49
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25
int status int void * buf
Definition: si_signals.h:59

◆ test_cff()

void test_cff ( CFFList L,
const CanonicalForm f 
)

Definition at line 213 of file cf_factor.cc.

214{
215 //int n = L.length();
216 CFFListIterator J=L;
217 CanonicalForm t=1;
218 int j=0;
219 if (!(L.getFirst().factor().inCoeffDomain()))
220 printf("first entry is not const\n");
221 for ( ; J.hasItem(); J++, j++ )
222 {
223 CanonicalForm tt=J.getItem().factor();
224 if (tt.inCoeffDomain() && (j!=0))
225 printf("other entry is const\n");
226 j=J.getItem().exp();
227 while(j>0) { t*=tt; j--; }
228 }
229 if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
230}
bool inCoeffDomain() const
bool isZero(const CFArray &A)
checks if entries of A are zero

Variable Documentation

◆ singular_homog_flag

VAR int singular_homog_flag =1

Definition at line 392 of file cf_factor.cc.