My Project
Loading...
Searching...
No Matches
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.
 
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.
 
void getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result)
 get_Terms: Split the polynomial in the containing terms.
 
CFList get_Terms (const CanonicalForm &f)
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x
 
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 $
 
CFFList factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $
 
CFFList sqrFree (const CanonicalForm &f, bool sort)
 squarefree factorization
 

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 398 of file cf_factor.cc.

399{
400 if (f.exp() > g.exp()) return 1;
401 if (f.exp() < g.exp()) return 0;
402 if (f.factor() > g.factor()) return 1;
403 return 0;
404}
g
Definition cfModGcd.cc:4098
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 409 of file cf_factor.cc.

410{
411 if ( f.inCoeffDomain() )
412 return CFFList( f );
413#ifndef NOASSERT
414 Variable a;
415 ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
416 ( const CanonicalForm & f, const Variable & alpha ) instead");
417#endif
418 //out_cf("factorize:",f,"==================================\n");
419 if (! f.isUnivariate() ) // preprocess homog. polys
420 {
421 if ( singular_homog_flag && f.isHomogeneous())
422 {
424 int d_xn = degree(f,xn);
425 CFMap n;
426 CanonicalForm F = compress(f(1,xn),n);
427 CFFList Intermediatelist;
428 Intermediatelist = factorize(F);
429 CFFList Homoglist;
431 for ( j=Intermediatelist; j.hasItem(); j++ )
432 {
433 Homoglist.append(
434 CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
435 }
436 CFFList Unhomoglist;
437 CanonicalForm unhomogelem;
438 for ( j=Homoglist; j.hasItem(); j++ )
439 {
440 unhomogelem= homogenize(j.getItem().factor(),xn);
441 Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
442 d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
443 }
444 if ( d_xn != 0 ) // have to append xn^(d_xn)
445 Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
446 if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
447 return Unhomoglist;
448 }
449 }
450 CFFList F;
451 if ( getCharacteristic() > 0 )
452 {
453 if (f.isUnivariate())
454 {
455#ifdef HAVE_FLINT
456#ifdef HAVE_NTL
457 if (degree (f) < 300)
458#endif
459 {
460 // use FLINT: char p, univariate
461 nmod_poly_t f1;
463 nmod_poly_factor_t result;
464 nmod_poly_factor_init (result);
465 mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
466 F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
467 nmod_poly_factor_clear (result);
468 nmod_poly_clear (f1);
470 return F;
471 }
472#endif
473#ifdef HAVE_NTL
474 { // NTL char 2, univariate
475 if (getCharacteristic()==2)
476 {
477 // Specialcase characteristic==2
478 if (fac_NTL_char != 2)
479 {
480 fac_NTL_char = 2;
481 zz_p::init(2);
482 }
483 // convert to NTL using the faster conversion routine for characteristic 2
484 GF2X f1=convertFacCF2NTLGF2X(f);
485 // no make monic necessary in GF2
486 //factorize
487 vec_pair_GF2X_long factors;
488 CanZass(factors,f1);
489
490 // convert back to factory again using the faster conversion routine for vectors over GF2X
491 F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
493 return F;
494 }
495 }
496#endif
497#ifdef HAVE_NTL
498 {
499 // use NTL char p, univariate
501 {
503 zz_p::init(getCharacteristic());
504 }
505
506 // convert to NTL
507 zz_pX f1=convertFacCF2NTLzzpX(f);
508 zz_p leadcoeff = LeadCoeff(f1);
509
510 //make monic
511 f1=f1 / LeadCoeff(f1);
512 // factorize
513 vec_pair_zz_pX_long factors;
514 CanZass(factors,f1);
515
516 F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
517 //test_cff(F,f);
519 return F;
520 }
521#endif
522#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
523 // Use Factory without NTL and without FLINT: char p, univariate
524 {
525 if ( isOn( SW_BERLEKAMP ) )
526 F=FpFactorizeUnivariateB( f, issqrfree );
527 else
528 F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
529 return F;
530 }
531#endif
532 }
533 else // char p, multivariate
534 {
536 {
537 #if defined(HAVE_NTL)
538 if (issqrfree)
539 {
540 CFList factors;
542 factors= GFSqrfFactorize (f);
543 for (CFListIterator i= factors; i.hasItem(); i++)
544 F.append (CFFactor (i.getItem(), 1));
545 }
546 else
547 {
549 F= GFFactorize (f);
550 }
551 #else
552 factoryError ("multivariate factorization over GF depends on NTL(missing)");
553 return CFFList (CFFactor (f, 1));
554 #endif
555 }
556 else
557 {
558 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
559 if (!isOn(SW_USE_FL_FAC_P))
560 {
561 #endif
562 #if defined(HAVE_NTL)
563 if (issqrfree)
564 {
565 CFList factors;
567 factors= FpSqrfFactorize (f);
568 for (CFListIterator i= factors; i.hasItem(); i++)
569 F.append (CFFactor (i.getItem(), 1));
570 goto end_charp;
571 }
572 else
573 {
575 F= FpFactorize (f);
576 goto end_charp;
577 }
578 #endif
579 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
580 }
581 #endif
582 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
583 nmod_mpoly_ctx_t ctx;
584 nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
585 nmod_mpoly_t Flint_f;
586 nmod_mpoly_init(Flint_f,ctx);
587 convFactoryPFlintMP(f,Flint_f,ctx,f.level());
588 nmod_mpoly_factor_t factors;
589 nmod_mpoly_factor_init(factors,ctx);
590 int okay;
591 if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
592 else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
593 nmod_mpoly_t fac;
594 nmod_mpoly_init(fac,ctx);
595 CanonicalForm cf_fac;
596 int cf_exp;
597 cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
598 F.append(CFFactor(cf_fac,1));
599 for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
600 {
601 nmod_mpoly_factor_get_base(fac,factors,i,ctx);
602 cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
603 cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
604 F.append(CFFactor(cf_fac,cf_exp));
605 }
606 nmod_mpoly_factor_clear(factors,ctx);
607 nmod_mpoly_clear(Flint_f,ctx);
608 nmod_mpoly_ctx_clear(ctx);
609 if (okay==0)
610 {
613 F=factorize(f,issqrfree);
616 }
617 #endif
618 #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
619 #ifndef HAVE_NTL
620 factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
621 return CFFList (CFFactor (f, 1));
622 #endif
623 #endif
624 }
625 }
626 }
627 else // char 0
628 {
629 bool on_rational = isOn(SW_RATIONAL);
632 CanonicalForm fz = f * cd;
634 if ( f.isUnivariate() )
635 {
636 CanonicalForm ic=icontent(fz);
637 fz/=ic;
638 if (fz.degree()==1)
639 {
640 F=CFFList(CFFactor(fz,1));
641 F.insert(CFFactor(ic,1));
642 }
643 else
644 #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
645 {
646 // FLINT 2.6.0 has a bug:
647 // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
648 // use FLINT: char 0, univariate
649 fmpz_poly_t f1;
651 fmpz_poly_factor_t result;
652 fmpz_poly_factor_init (result);
653 fmpz_poly_factor(result, f1);
655 fmpz_poly_factor_clear (result);
656 fmpz_poly_clear (f1);
657 if ( ! ic.isOne() )
658 {
659 // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
660 // first entry is in CoeffDomain
661 CFFactor new_first( F.getFirst().factor() * ic );
662 F.removeFirst();
663 F.insert( new_first );
664 }
665 }
666 goto end_char0;
667 #elif defined(HAVE_NTL)
668 {
669 //use NTL
670 ZZ c;
671 vec_pair_ZZX_long factors;
672 //factorize the converted polynomial
673 factor(c,factors,convertFacCF2NTLZZX(fz));
674
675 //convert the result back to Factory
677 if ( ! ic.isOne() )
678 {
679 // according to convertNTLvec_pair_ZZX_long2FacCFFList
680 // first entry is in CoeffDomain
681 CFFactor new_first( F.getFirst().factor() * ic );
682 F.removeFirst();
683 F.insert( new_first );
684 }
685 }
686 goto end_char0;
687 #else
688 {
689 //Use Factory without NTL: char 0, univariate
690 F = ZFactorizeUnivariate( fz, issqrfree );
691 goto end_char0;
692 }
693 #endif
694 }
695 else // multivariate, char 0
696 {
697 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
699 {
700 On (SW_RATIONAL);
701 fmpz_mpoly_ctx_t ctx;
702 fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
703 fmpz_mpoly_t Flint_f;
704 fmpz_mpoly_init(Flint_f,ctx);
705 convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
706 fmpz_mpoly_factor_t factors;
707 fmpz_mpoly_factor_init(factors,ctx);
708 int rr;
709 if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
710 else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
711 if (rr==0) printf("fail\n");
712 fmpz_mpoly_t fac;
713 fmpz_mpoly_init(fac,ctx);
714 CanonicalForm cf_fac;
715 int cf_exp;
716 fmpz_t c;
717 fmpz_init(c);
718 fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
719 cf_fac=convertFmpz2CF(c);
720 fmpz_clear(c);
721 F.append(CFFactor(cf_fac,1));
722 for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
723 {
724 fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
725 cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
726 cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
727 F.append(CFFactor(cf_fac,cf_exp));
728 }
729 fmpz_mpoly_factor_clear(factors,ctx);
730 fmpz_mpoly_clear(Flint_f,ctx);
731 fmpz_mpoly_ctx_clear(ctx);
732 goto end_char0;
733 }
734 #endif
735 #if defined(HAVE_NTL)
736 On (SW_RATIONAL);
737 if (issqrfree)
738 {
739 CFList factors= ratSqrfFactorize (fz);
740 for (CFListIterator i= factors; i.hasItem(); i++)
741 F.append (CFFactor (i.getItem(), 1));
742 }
743 else
744 {
745 F = ratFactorize (fz);
746 }
747 #endif
748 #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
749 #ifndef HAVE_NTL
750 F=ZFactorizeMultivariate(fz, issqrfree);
751 #endif
752 #endif
753 }
754
755end_char0:
756 if ( on_rational )
758 else
760 if ( ! cd.isOne() )
761 {
762 CFFactor new_first( F.getFirst().factor() / cd );
763 F.removeFirst();
764 F.insert( new_first );
765 }
766 }
767
768#if defined(HAVE_NTL)
769end_charp:
770#endif
772 return F;
773}
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.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
VAR long fac_NTL_char
Definition NTLconvert.cc:46
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
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
ListIterator< CFFactor > CFFListIterator
ListIterator< CanonicalForm > CFListIterator
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
List< CanonicalForm > CFList
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
int i
Definition cfEzgcd.cc:132
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
EXTERN_VAR int singular_homog_flag
#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:264
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition cf_factor.cc:398
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition cf_factor.cc:317
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition cf_factor.cc:409
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
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 factor() const
T getFirst() const
void removeFirst()
void sort(int(*)(const T &, const T &))
void append(const T &)
void insert(const T &)
factory's class for variables
Definition factory.h:127
Variable alpha
return result
CanonicalForm factor
Definition facAbsFact.cc:97
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
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:4509

◆ factorize() [2/2]

CFFList factorize ( const CanonicalForm & f,
const Variable & alpha )

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

Definition at line 778 of file cf_factor.cc.

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

◆ find_exp()

void find_exp ( const CanonicalForm & f,
int * exp_f )

Definition at line 66 of file cf_factor.cc.

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

◆ find_mvar()

int find_mvar ( const CanonicalForm & f)

Definition at line 83 of file cf_factor.cc.

84{
85 int mv=f.level();
86 int *exp_f=NEW_ARRAY(int,mv+1);
87 int i;
88 for(i=mv;i>0;i--) exp_f[i]=0;
89 find_exp(f,exp_f);
90 for(i=mv;i>0;i--)
91 {
92 if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
93 {
94 mv=i;
95 }
96 }
97 DELETE_ARRAY(exp_f);
98 return mv;
99}
#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 264 of file cf_factor.cc.

265{
266 ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
267 int max=0, maxlevel=0, n=level(f);
268 for ( int i=1; i<=n; i++ )
269 {
270 if (degree(f,Variable(i)) >= max)
271 {
272 max= degree(f,Variable(i)); maxlevel= i;
273 }
274 }
275 return Variable(maxlevel);
276}
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 293 of file cf_factor.cc.

293 {
294 CFList result,dummy,dummy2;
297
298 if ( getNumVars(f) == 0 ) result.append(f);
299 else{
300 Variable _x(level(f));
301 for ( i=f; i.hasTerms(); i++ ){
302 getTerms(i.coeff(), 1, dummy);
303 for ( j=dummy; j.hasItem(); j++ )
304 result.append(j.getItem() * power(_x, i.exp()));
305
306 dummy= dummy2; // have to initalize new
307 }
308 }
309 return result;
310}
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:283

◆ 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 283 of file cf_factor.cc.

284{
285 if ( getNumVars(f) == 0 ) result.append(f*t);
286 else{
287 Variable x(level(f));
288 for ( CFIterator i=f; i.hasTerms(); i++ )
289 getTerms( i.coeff(), t*power(x,i.exp()), result);
290 }
291}
Variable x
Definition cfModGcd.cc:4090

◆ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm & f,
const Variable & x )

homogenize homogenizes f with Variable x

Definition at line 317 of file cf_factor.cc.

318{
319#if 0
320 int maxdeg=totaldegree(f), deg;
322 CanonicalForm elem, result(0);
323
324 for (i=f; i.hasTerms(); i++)
325 {
326 elem= i.coeff()*power(f.mvar(),i.exp());
327 deg = totaldegree(elem);
328 if ( deg < maxdeg )
329 result += elem * power(x,maxdeg-deg);
330 else
331 result+=elem;
332 }
333 return result;
334#else
335 CFList Newlist, Termlist= get_Terms(f);
336 int maxdeg=totaldegree(f), deg;
338 CanonicalForm elem, result(0);
339
340 for (i=Termlist; i.hasItem(); i++)
341 {
342 elem= i.getItem();
343 deg = totaldegree(elem);
344 if ( deg < maxdeg )
345 Newlist.append(elem * power(x,maxdeg-deg));
346 else
347 Newlist.append(elem);
348 }
349 for (i=Newlist; i.hasItem(); i++) // rebuild
350 result += i.getItem();
351
352 return result;
353#endif
354}
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:293

◆ homogenize() [2/2]

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

Definition at line 357 of file cf_factor.cc.

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

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm & f)

Definition at line 248 of file cf_factor.cc.

249{
250 if (f.level()<=0) return false;
251 for (CFIterator i=f;i.hasTerms();i++)
252 {
253 if (!(i.coeff().inBaseDomain())) return false;
254 }
255 return true;
256}

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm & f)

Definition at line 238 of file cf_factor.cc.

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

◆ 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 103 of file cf_factor.cc.

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

◆ out_cff()

void out_cff ( CFFList & L)

Definition at line 206 of file cf_factor.cc.

207{
208 //int n = L.length();
209 CFFListIterator J=L;
210 int j=0;
211 for ( ; J.hasItem(); J++, j++ )
212 {
213 printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
214 printf("%d\n", J.getItem().exp());
215 }
216}
int exp() const
T & getItem() const

◆ sqrFree()

CFFList sqrFree ( const CanonicalForm & f,
bool sort )

squarefree factorization

Definition at line 961 of file cf_factor.cc.

962{
963// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
965
966 if ( getCharacteristic() == 0 )
967 result = sqrFreeZ( f );
968 else
969 {
971 if (hasFirstAlgVar (f, alpha))
972 result = FqSqrf( f, alpha );
973 else
974 result= FpSqrf (f);
975 }
976 if (sort)
977 {
978 CFFactor buf= result.getFirst();
979 result.removeFirst();
981 result.insert (buf);
982 }
983 return result;
984}
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)
CFFList sortCFFList(CFFList &F)
int status int void * buf
Definition si_signals.h:69

◆ test_cff()

void test_cff ( CFFList & L,
const CanonicalForm & f )

Definition at line 217 of file cf_factor.cc.

218{
219 //int n = L.length();
220 CFFListIterator J=L;
221 CanonicalForm t=1;
222 int j=0;
223 if (!(L.getFirst().factor().inCoeffDomain()))
224 printf("first entry is not const\n");
225 for ( ; J.hasItem(); J++, j++ )
226 {
228 if (tt.inCoeffDomain() && (j!=0))
229 printf("other entry is const\n");
230 j=J.getItem().exp();
231 while(j>0) { t*=tt; j--; }
232 }
233 if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
234}
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 396 of file cf_factor.cc.