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)
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 or
CFFList | factorize (const CanonicalForm &f, const Variable &alpha)
| factorization over or
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.

{
if (f.exp() > g.exp()) return 1;
if (f.exp() < g.exp()) return 0;
if (f.factor() > g.factor()) return 1;
return 0;
}
g
g
Definition cfModGcd.cc:4098
f
FILE * f
Definition checklibs.c:9

## factorize() [1/2]

CFFList factorize | ( | const CanonicalForm & | f,
|  | bool | issqrfree )

factorization over or

Definition at line 409 of file cf_factor.cc.

{
if ( f.inCoeffDomain() )
return CFFList( f );
#ifndef NOASSERT
Variable a;
ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
( const CanonicalForm & f, const Variable & alpha ) instead");
#endif
//out_cf("factorize:",f,"==================================\n");
if (! f.isUnivariate() ) // preprocess homog. polys
{
if ( singular_homog_flag && f.isHomogeneous())
{
Variable xn = get_max_degree_Variable(f);
int d_xn = degree(f,xn);
CFMap n;
CanonicalForm F = compress(f(1,xn),n);
CFFList Intermediatelist;
Intermediatelist = factorize(F);
CFFList Homoglist;
CFFListIterator j;
for ( j=Intermediatelist; j.hasItem(); j++ )
{
Homoglist.append(
CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
}
CFFList Unhomoglist;
CanonicalForm unhomogelem;
for ( j=Homoglist; j.hasItem(); j++ )
{
unhomogelem= homogenize(j.getItem().factor(),xn);
Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
}
if ( d_xn != 0 ) // have to append xn^(d_xn)
Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
return Unhomoglist;
}
}
CFFList F;
if ( getCharacteristic() > 0 )
{
if (f.isUnivariate())
{
#ifdef HAVE_FLINT
#ifdef HAVE_NTL
if (degree (f) < 300)
#endif
{
// use FLINT: char p, univariate
nmod_poly_t f1;
convertFacCF2nmod_poly_t (f1, f);
nmod_poly_factor_t result;
nmod_poly_factor_init (result);
mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
nmod_poly_factor_clear (result);
nmod_poly_clear (f1);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#ifdef HAVE_NTL
{ // NTL char 2, univariate
if (getCharacteristic()==2)
{
// Specialcase characteristic==2
if (fac_NTL_char != 2)
{
fac_NTL_char = 2;
zz_p::init(2);
}
// convert to NTL using the faster conversion routine for characteristic 2
GF2X f1=convertFacCF2NTLGF2X(f);
// no make monic necessary in GF2
//factorize
vec_pair_GF2X_long factors;
CanZass(factors,f1);
// convert back to factory again using the faster conversion routine for vectors over GF2X
F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
}
#endif
#ifdef HAVE_NTL
{
// use NTL char p, univariate
if (fac_NTL_char != getCharacteristic())
{
fac_NTL_char = getCharacteristic();
zz_p::init(getCharacteristic());
}
// convert to NTL
zz_pX f1=convertFacCF2NTLzzpX(f);
zz_p leadcoeff = LeadCoeff(f1);
//make monic
f1=f1 / LeadCoeff(f1);
// factorize
vec_pair_zz_pX_long factors;
CanZass(factors,f1);
F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
//test_cff(F,f);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
// Use Factory without NTL and without FLINT: char p, univariate
{
if ( isOn( SW_BERLEKAMP ) )
F=FpFactorizeUnivariateB( f, issqrfree );
else
F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
return F;
}
#endif
}
else // char p, multivariate
{
if (CFFactory::gettype() == GaloisFieldDomain)
{
#if defined(HAVE_NTL)
if (issqrfree)
{
CFList factors;
Variable alpha;
factors= GFSqrfFactorize (f);
for (CFListIterator i= factors; i.hasItem(); i++)
F.append (CFFactor (i.getItem(), 1));
}
else
{
Variable alpha;
F= GFFactorize (f);
}
#else
factoryError ("multivariate factorization over GF depends on NTL(missing)");
return CFFList (CFFactor (f, 1));
#endif
}
else
{
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
if (!isOn(SW_USE_FL_FAC_P))
{
#endif
#if defined(HAVE_NTL)
if (issqrfree)
{
CFList factors;
Variable alpha;
factors= FpSqrfFactorize (f);
for (CFListIterator i= factors; i.hasItem(); i++)
F.append (CFFactor (i.getItem(), 1));
goto end_charp;
}
else
{
Variable alpha;
F= FpFactorize (f);
goto end_charp;
}
#endif
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
}
#endif
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
nmod_mpoly_ctx_t ctx;
nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
nmod_mpoly_t Flint_f;
nmod_mpoly_init(Flint_f,ctx);
convFactoryPFlintMP(f,Flint_f,ctx,f.level());
nmod_mpoly_factor_t factors;
nmod_mpoly_factor_init(factors,ctx);
int okay;
if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
nmod_mpoly_t fac;
nmod_mpoly_init(fac,ctx);
CanonicalForm cf_fac;
int cf_exp;
cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
F.append(CFFactor(cf_fac,1));
for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
{
nmod_mpoly_factor_get_base(fac,factors,i,ctx);
cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
F.append(CFFactor(cf_fac,cf_exp));
}
nmod_mpoly_factor_clear(factors,ctx);
nmod_mpoly_clear(Flint_f,ctx);
nmod_mpoly_ctx_clear(ctx);
if (okay==0)
{
Off(SW_USE_FL_GCD_P);
Off(SW_USE_FL_FAC_P);
F=factorize(f,issqrfree);
On(SW_USE_FL_GCD_P);
On(SW_USE_FL_FAC_P);
}
#endif
#if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
#ifndef HAVE_NTL
factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
return CFFList (CFFactor (f, 1));
#endif
#endif
}
}
}
else // char 0
{
bool on_rational = isOn(SW_RATIONAL);
On(SW_RATIONAL);
CanonicalForm cd = bCommonDen( f );
CanonicalForm fz = f * cd;
Off(SW_RATIONAL);
if ( f.isUnivariate() )
{
CanonicalForm ic=icontent(fz);
fz/=ic;
if (fz.degree()==1)
{
F=CFFList(CFFactor(fz,1));
F.insert(CFFactor(ic,1));
}
else
#if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
{
// FLINT 2.6.0 has a bug:
// factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
// use FLINT: char 0, univariate
fmpz_poly_t f1;
convertFacCF2Fmpz_poly_t (f1, fz);
fmpz_poly_factor_t result;
fmpz_poly_factor_init (result);
fmpz_poly_factor(result, f1);
F= convertFLINTfmpz_poly_factor2FacCFFList (result, fz.mvar());
fmpz_poly_factor_clear (result);
fmpz_poly_clear (f1);
if ( ! ic.isOne() )
{
// according to convertFLINTfmpz_polyfactor2FcaCFFlist,
// first entry is in CoeffDomain
CFFactor new_first( F.getFirst().factor() * ic );
F.removeFirst();
F.insert( new_first );
}
}
goto end_char0;
#elif defined(HAVE_NTL)
{
//use NTL
ZZ c;
vec_pair_ZZX_long factors;
//factorize the converted polynomial
factor(c,factors,convertFacCF2NTLZZX(fz));
//convert the result back to Factory
F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
if ( ! ic.isOne() )
{
// according to convertNTLvec_pair_ZZX_long2FacCFFList
// first entry is in CoeffDomain
CFFactor new_first( F.getFirst().factor() * ic );
F.removeFirst();
F.insert( new_first );
}
}
goto end_char0;
#else
{
//Use Factory without NTL: char 0, univariate
F = ZFactorizeUnivariate( fz, issqrfree );
goto end_char0;
}
#endif
}
else // multivariate, char 0
{
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
if (isOn(SW_USE_FL_FAC_0))
{
On (SW_RATIONAL);
fmpz_mpoly_ctx_t ctx;
fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
fmpz_mpoly_t Flint_f;
fmpz_mpoly_init(Flint_f,ctx);
convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
fmpz_mpoly_factor_t factors;
fmpz_mpoly_factor_init(factors,ctx);
int rr;
if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
if (rr==0) printf("fail\n");
fmpz_mpoly_t fac;
fmpz_mpoly_init(fac,ctx);
CanonicalForm cf_fac;
int cf_exp;
fmpz_t c;
fmpz_init(c);
fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
cf_fac=convertFmpz2CF(c);
fmpz_clear(c);
F.append(CFFactor(cf_fac,1));
for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
{
fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
F.append(CFFactor(cf_fac,cf_exp));
}
fmpz_mpoly_factor_clear(factors,ctx);
fmpz_mpoly_clear(Flint_f,ctx);
fmpz_mpoly_ctx_clear(ctx);
goto end_char0;
}
#endif
#if defined(HAVE_NTL)
On (SW_RATIONAL);
if (issqrfree)
{
CFList factors= ratSqrfFactorize (fz);
for (CFListIterator i= factors; i.hasItem(); i++)
F.append (CFFactor (i.getItem(), 1));
}
else
{
F = ratFactorize (fz);
}
#endif
#if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
#ifndef HAVE_NTL
F=ZFactorizeMultivariate(fz, issqrfree);
#endif
#endif
}
end_char0:
if ( on_rational )
On(SW_RATIONAL);
else
Off(SW_RATIONAL);
if ( ! cd.isOne() )
{
CFFactor new_first( F.getFirst().factor() / cd );
F.removeFirst();
F.insert( new_first );
}
}
#if defined(HAVE_NTL)
end_charp:
#endif
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
convertFmpz2CF
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
Definition FLINTconvert.cc:154
convertFLINTnmod_poly_factor2FacCFFList
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
Definition FLINTconvert.cc:337
convertFacCF2Fmpz_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition FLINTconvert.cc:146
convertFLINTfmpz_poly_factor2FacCFFList
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
convertNTLvec_pair_GF2X_long2FacCFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition NTLconvert.cc:446
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition NTLconvert.cc:691
convertNTLvec_pair_zzpX_long2FacCFFList
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition NTLconvert.cc:399
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
convertFacCF2NTLGF2X
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition NTLconvert.cc:184
convertNTLvec_pair_ZZX_long2FacCFFList
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
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
i
int i
Definition cfEzgcd.cc:132
cd
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
singular_homog_flag
EXTERN_VAR int singular_homog_flag
Definition cf_algorithm.h:65
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_USE_FL_GCD_P
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition cf_defs.h:47
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
SW_USE_NTL_SORT
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition cf_defs.h:39
SW_USE_FL_FAC_0
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition cf_defs.h:57
SW_USE_FL_FAC_P
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition cf_defs.h:55
SW_BERLEKAMP
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition cf_defs.h:51
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
get_max_degree_Variable
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition cf_factor.cc:264
cmpCF
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition cf_factor.cc:398
homogenize
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition cf_factor.cc:317
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition cf_factor.cc:409
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition canonicalform.cc:414
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
result
return result
Definition facAbsBiFact.cc:76
factor
CanonicalForm factor
Definition facAbsFact.cc:97
ratFactorize
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition facFactorize.h:79
ratSqrfFactorize
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition facFactorize.h:53
FpSqrfFactorize
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Definition facFqFactorize.h:47
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition facFqFactorize.h:101
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition facFqFactorize.h:267
GFSqrfFactorize
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
Definition facFqFactorize.h:82
j
int j
Definition facHensel.cc:110
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
FpFactorizeUnivariateB
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
FpFactorizeUnivariateCZ
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
ZFactorizeMultivariate
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
ZFactorizeUnivariate
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
xn
VAR int xn
Definition walk.cc:4509

## factorize() [2/2]

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

factorization over or

Definition at line 778 of file cf_factor.cc.

{
if ( f.inCoeffDomain() )
return CFFList( f );
//out_cf("factorize:",f,"==================================\n");
//out_cf("mipo:",getMipo(alpha),"\n");
CFFList F;
ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
#ifndef NOASSERT
Variable beta;
if (hasFirstAlgVar(f, beta))
ASSERT (beta == alpha, "f has an algebraic variable that \
does not coincide with alpha");
#endif
int ch=getCharacteristic();
if (ch>0)
{
if (f.isUnivariate())
{
#ifdef HAVE_NTL
if (/*getCharacteristic()*/ch==2)
{
// special case : GF2
// remainder is two ==> nothing to do
// set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
GF2E::init (minPo);
// convert to NTL again using the faster conversion routines
GF2EX f1;
if (isPurePoly(f))
{
GF2X f_tmp=convertFacCF2NTLGF2X(f);
f1=to_GF2EX(f_tmp);
}
else
f1=convertFacCF2NTLGF2EX(f,minPo);
// make monic (in Z/2(a))
GF2E f1_coef=LeadCoeff(f1);
MakeMonic(f1);
// factorize using NTL
vec_pair_GF2EX_long factors;
CanZass(factors,f1);
// return converted result
F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
{
// use FLINT
nmod_poly_t FLINTmipo, leadingCoeff;
fq_nmod_ctx_t fq_con;
nmod_poly_init (FLINTmipo, ch);
nmod_poly_init (leadingCoeff, ch);
convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
fq_nmod_poly_t FLINTF;
convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
fq_nmod_poly_factor_t res;
fq_nmod_poly_factor_init (res, fq_con);
fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
F.insert (CFFactor (Lc (f), 1));
fq_nmod_poly_factor_clear (res, fq_con);
fq_nmod_poly_clear (FLINTF, fq_con);
nmod_poly_clear (FLINTmipo);
nmod_poly_clear (leadingCoeff);
fq_nmod_ctx_clear (fq_con);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#ifdef HAVE_NTL
{
// use NTL
if (fac_NTL_char != ch)
{
fac_NTL_char = ch;
zz_p::init(ch);
}
// set minimal polynomial in NTL
zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
zz_pE::init (minPo);
// convert to NTL
zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
zz_pE leadcoeff= LeadCoeff(f1);
//make monic
f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
// factorize
vec_pair_zz_pEX_long factors;
CanZass(factors,f1);
// return converted result
F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
//test_cff(F,f);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
// char p, extension, univariate
CanonicalForm c=Lc(f);
CanonicalForm fc=f/c;
F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
F.insert (CFFactor (c, 1));
#endif
}
else // char p, multivariate
{
#if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
// use FLINT
nmod_poly_t FLINTmipo;
fq_nmod_ctx_t fq_con;
fq_nmod_mpoly_ctx_t ctx;
nmod_poly_init (FLINTmipo, ch);
convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
fq_nmod_mpoly_t FLINTF;
fq_nmod_mpoly_init(FLINTF,ctx);
convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
fq_nmod_mpoly_factor_t res;
fq_nmod_mpoly_factor_init (res, ctx);
fq_nmod_mpoly_factor (res, FLINTF, ctx);
F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
//F.insert (CFFactor (Lc (f), 1));
fq_nmod_mpoly_factor_clear (res, ctx);
fq_nmod_mpoly_clear (FLINTF, ctx);
nmod_poly_clear (FLINTmipo);
fq_nmod_mpoly_ctx_clear (ctx);
fq_nmod_ctx_clear (fq_con);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
#elif defined(HAVE_NTL)
F= FqFactorize (f, alpha);
#else
factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
return CFFList (CFFactor (f, 1));
#endif
}
}
else // Q(a)[x]
{
if (f.isUnivariate())
{
F= AlgExtFactorize (f, alpha);
}
else //Q(a)[x1,...,xn]
{
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
F= ratFactorize (f, alpha);
#else
factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
return CFFList (CFFactor (f, 1));
#endif
}
}
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
convertFLINTFq_nmod_poly_factor2FacCFFList
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
Definition FLINTconvert.cc:379
convertFacCF2Fq_nmod_poly_t
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
Definition FLINTconvert.cc:526
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition NTLconvert.cc:1064
convertNTLvec_pair_zzpEX_long2FacCFFList
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
convertNTLvec_pair_GF2EX_long2FacCFFList
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
convertFacCF2NTLGF2EX
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition NTLconvert.cc:1007
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
res
CanonicalForm res
Definition facAbsFact.cc:60
beta
Variable beta
Definition facAbsFact.cc:95
AlgExtFactorize
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition facAlgExt.cc:370
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition facFqFactorize.h:184
fq_con
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
getReduce
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.

{
if ( ! f.inCoeffDomain() )
{
int e=f.level();
CFIterator i = f;
if (e>=0)
{
if (i.exp() > exp_f[e]) exp_f[e]=i.exp();
}
for (; i.hasTerms(); i++ )
{
find_exp(i.coeff(), exp_f);
}
}
}
find_exp
void find_exp(const CanonicalForm &f, int *exp_f)
Definition cf_factor.cc:66
CFIterator
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.

{
int mv=f.level();
int *exp_f=NEW_ARRAY(int,mv+1);
int i;
for(i=mv;i>0;i--) exp_f[i]=0;
find_exp(f,exp_f);
for(i=mv;i>0;i--)
{
if ((exp_f[i]>0) && (exp_f[i]<exp_f[mv]))
{
mv=i;
}
}
DELETE_ARRAY(exp_f);
return mv;
}
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
NEW_ARRAY
#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.

{
ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
int max=0, maxlevel=0, n=level(f);
for ( int i=1; i<=n; i++ )
{
if (degree(f,Variable(i)) >= max)
{
max= degree(f,Variable(i)); maxlevel= i;
}
}
return Variable(maxlevel);
}
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
max
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.

{
CFList result,dummy,dummy2;
CFIterator i;
CFListIterator j;
if ( getNumVars(f) == 0 ) result.append(f);
else{
Variable _x(level(f));
for ( i=f; i.hasTerms(); i++ ){
getTerms(i.coeff(), 1, dummy);
for ( j=dummy; j.hasItem(); j++ )
result.append(j.getItem() * power(_x, i.exp()));
dummy= dummy2; // have to initalize new
}
}
return result;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
getTerms
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.

{
if ( getNumVars(f) == 0 ) result.append(f*t);
else{
Variable x(level(f));
for ( CFIterator i=f; i.hasTerms(); i++ )
getTerms( i.coeff(), t*power(x,i.exp()), result);
}
}
x
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.

{
#if 0
int maxdeg=totaldegree(f), deg;
CFIterator i;
CanonicalForm elem, result(0);
for (i=f; i.hasTerms(); i++)
{
elem= i.coeff()*power(f.mvar(),i.exp());
deg = totaldegree(elem);
if ( deg < maxdeg )
result += elem * power(x,maxdeg-deg);
else
result+=elem;
}
return result;
#else
CFList Newlist, Termlist= get_Terms(f);
int maxdeg=totaldegree(f), deg;
CFListIterator i;
CanonicalForm elem, result(0);
for (i=Termlist; i.hasItem(); i++)
{
elem= i.getItem();
deg = totaldegree(elem);
if ( deg < maxdeg )
Newlist.append(elem * power(x,maxdeg-deg));
else
Newlist.append(elem);
}
for (i=Newlist; i.hasItem(); i++) // rebuild
result += i.getItem();
return result;
#endif
}
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
get_Terms
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.

{
#if 0
int maxdeg=totaldegree(f), deg;
CFIterator i;
CanonicalForm elem, result(0);
for (i=f; i.hasTerms(); i++)
{
elem= i.coeff()*power(f.mvar(),i.exp());
deg = totaldegree(elem);
if ( deg < maxdeg )
result += elem * power(x,maxdeg-deg);
else
result+=elem;
}
return result;
#else
CFList Newlist, Termlist= get_Terms(f);
int maxdeg=totaldegree(f), deg;
CFListIterator i;
CanonicalForm elem, result(0);
for (i=Termlist; i.hasItem(); i++)
{
elem= i.getItem();
deg = totaldegree(elem,v1,v2);
if ( deg < maxdeg )
Newlist.append(elem * power(x,maxdeg-deg));
else
Newlist.append(elem);
}
for (i=Newlist; i.hasItem(); i++) // rebuild
result += i.getItem();
return result;
#endif
}

## isPurePoly()

bool isPurePoly | ( | const CanonicalForm & | f | ) |

Definition at line 248 of file cf_factor.cc.

{
if (f.level()<=0) return false;
for (CFIterator i=f;i.hasTerms();i++)
{
if (!(i.coeff().inBaseDomain())) return false;
}
return true;
}

## isPurePoly_m()

bool isPurePoly_m | ( | const CanonicalForm & | f | ) |

Definition at line 238 of file cf_factor.cc.

{
if (f.inBaseDomain()) return true;
if (f.level()<0) return false;
for (CFIterator i=f;i.hasTerms();i++)
{
if (!isPurePoly_m(i.coeff())) return false;
}
return true;
}
isPurePoly_m
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 )

Definition at line 103 of file cf_factor.cc.

{
printf("%s",s1);
if (f.isZero()) printf("+0");
//else if (! f.inCoeffDomain() )
else if (! f.inBaseDomain() )
{
int l = f.level();
for ( CFIterator i = f; i.hasTerms(); i++ )
{
int e=i.exp();
if (i.coeff().isOne())
{
printf("+");
if (e==0) printf("1");
else
{
printf("%c",'a'+l-1);
if (e!=1) printf("^%d",e);
}
}
else
{
out_cf("+(",i.coeff(),")");
if (e!=0)
{
printf("*%c",'a'+l-1);
if (e!=1) printf("^%d",e);
}
}
}
}
else
{
if ( f.isImm() )
{
if (CFFactory::gettype()==GaloisFieldDomain)
{
long a= imm2int (f.getval());
if ( a == gf_q )
printf ("+%ld", a);
else if ( a == 0L )
printf ("+1");
else if ( a == 1L )
printf ("+%c",gf_name);
else
{
printf ("+%c",gf_name);
printf ("^%ld",a);
}
}
else
{
long l=f.intval();
if (l<0) printf("%ld",l);
else printf("+%ld",l);
}
}
else
{
#ifdef NOSTREAMIO
if (f.inZ())
{
mpz_t m;
gmp_numerator(f,m);
char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
str = mpz_get_str( str, 10, m );
puts(str);
delete[] str;
mpz_clear(m);
}
else if (f.inQ())
{
mpz_t m;
gmp_numerator(f,m);
char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
str = mpz_get_str( str, 10, m );
while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
puts(str);putchar('/');
delete[] str;
mpz_clear(m);
gmp_denominator(f,m);
str = new char[mpz_sizeinbase( m, 10 ) + 2];
str = mpz_get_str( str, 10, m );
while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
puts(str);
delete[] str;
mpz_clear(m);
}
#else
std::cout << f;
#endif
}
//if (f.inZ()) printf("(Z)");
//else if (f.inQ()) printf("(Q)");
//else if (f.inFF()) printf("(FF)");
//else if (f.inPP()) printf("(PP)");
//else if (f.inGF()) printf("(PP)");
//else
if (f.inExtension()) printf("E(%d)",f.level());
}
printf("%s",s2);
}
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
Definition cf_factor.cc:103
gmp_numerator
void FACTORY_PUBLIC gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition singext.cc:20
gmp_denominator
void FACTORY_PUBLIC gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition singext.cc:40
gf_q
VAR int gf_q
Definition gfops.cc:47
gf_name
VAR char gf_name
Definition gfops.cc:52
imm2int
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
LibThread::str
char * str(leftv arg)
Definition shared.cc:699

## out_cff()

void out_cff | ( | CFFList & | L | ) |

Definition at line 206 of file cf_factor.cc.

{
//int n = L.length();
CFFListIterator J=L;
int j=0;
for ( ; J.hasItem(); J++, j++ )
{
printf("F%d",j);out_cf(":",J.getItem().factor()," ^ ");
printf("%d\n", J.getItem().exp());
}
}
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431

## sqrFree()

CFFList sqrFree | ( | const CanonicalForm & | f,
|  | bool | sort )

squarefree factorization

Definition at line 961 of file cf_factor.cc.

{
// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
CFFList result;
if ( getCharacteristic() == 0 )
result = sqrFreeZ( f );
else
{
Variable alpha;
if (hasFirstAlgVar (f, alpha))
result = FqSqrf( f, alpha );
else
result= FpSqrf (f);
}
if (sort)
{
CFFactor buf= result.getFirst();
result.removeFirst();
result= sortCFFList (result);
result.insert (buf);
}
return result;
}
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:77
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:38
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition fac_sqrfree.cc:49
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition fac_sqrfree.cc:25
buf
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.

{
//int n = L.length();
CFFListIterator J=L;
CanonicalForm t=1;
int j=0;
if (!(L.getFirst().factor().inCoeffDomain()))
printf("first entry is not const\n");
for ( ; J.hasItem(); J++, j++ )
{
CanonicalForm tt=J.getItem().factor();
if (tt.inCoeffDomain() && (j!=0))
printf("other entry is const\n");
j=J.getItem().exp();
while(j>0) { t*=tt; j--; }
}
if (!(f-t).isZero()) { printf("problem:\n");out_cf("factor:",f," has problems\n");}
}
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468

## Variable Documentation

## singular_homog_flag

VAR int singular_homog_flag =1

Definition at line 396 of file cf_factor.cc.