Loading...
Searching...
No Matches
facAbsBiFact.h File Reference

bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by Bertone, Chèze, Galligo More...

`#include "canonicalform.h"`

Go to the source code of this file.

## Functions

CFAFList | absBiFactorizeMain (const CanonicalForm &F, bool full=false)
| main absolute factorization routine, expects bivariate poly which is irreducible over Q
static void | normalize (CFAFList &L)
| normalize factors, i.e. make factors monic
CFAFList | uniAbsFactorize (const CanonicalForm &F, bool full=false)
| univariate absolute factorization over Q

## Detailed Description

bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Absolute Factorization" by Bertone, Chèze, Galligo

Author
  Martin Lee

Definition in file facAbsBiFact.h.

## Function Documentation

## absBiFactorizeMain()

CFAFList absBiFactorizeMain | ( | const CanonicalForm & | F,
|  | bool | full = false )

main absolute factorization routine, expects bivariate poly which is irreducible over Q

Returns
  absBiFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Parameters

  [in] | F | s.a.
  [in] | full | true if all factors should be returned

Definition at line 212 of file facAbsBiFact.cc.

{
CanonicalForm F= bCommonDen (G)*G;
bool isRat= isOn (SW_RATIONAL);
Off (SW_RATIONAL);
F /= icontent (F);
On (SW_RATIONAL);
mpz_t * M=new mpz_t [4];
mpz_init (M[0]);
mpz_init (M[1]);
mpz_init (M[2]);
mpz_init (M[3]);
mpz_t * S=new mpz_t [2];
mpz_init (S[0]);
mpz_init (S[1]);
F= compress (F, M, S);
if (F.isUnivariate())
{
if (degree (F) == 1)
{
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
if (!isRat)
Off (SW_RATIONAL);
return CFAFList (CFAFactor (G, 1, 1));
}
CFAFList result= uniAbsFactorize (F, full);
if (result.getFirst().factor().inCoeffDomain())
result.removeFirst();
for (CFAFListIterator iter=result; iter.hasItem(); iter++)
iter.getItem()= CFAFactor (decompress (iter.getItem().factor(), M, S),
iter.getItem().minpoly(),iter.getItem().exp());
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
if (!isRat)
Off (SW_RATIONAL);
return result;
}
if (degree (F, 1) == 1 || degree (F, 2) == 1)
{
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
if (!isRat)
Off (SW_RATIONAL);
return CFAFList (CFAFactor (G, 1, 1));
}
int minTdeg, tdegF= totaldegree (F);
CanonicalForm Fp, smallestFactor;
int p;
CFFList factors;
Variable alpha;
bool rec= false;
Variable x= Variable (1);
Variable y= Variable (2);
CanonicalForm bufF= F;
CFFListIterator iter;
CFArray eval= CFArray (2);
int absValue= 1;
differentevalpoint:
while (1)
{
TIMING_START (fac_evalpoint);
p= choosePoint (F, tdegF, eval, rec, absValue);
TIMING_END_AND_PRINT (fac_evalpoint, "time to find eval point: ");
//after here isOn (SW_RATIONAL)==false
setCharacteristic (p);
Fp=F.mapinto();
factors= factorize (Fp);
if (factors.getFirst().factor().inCoeffDomain())
factors.removeFirst();
if (factors.length() == 1 && factors.getFirst().exp() == 1)
{
if (absIrredTest (Fp))
{
if (isRat)
On (SW_RATIONAL);
setCharacteristic(0);
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return CFAFList (CFAFactor (G, 1, 1));
}
else
{
setCharacteristic (0);
if (modularIrredTestWithShift (F))
{
if (isRat)
On (SW_RATIONAL);
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return CFAFList (CFAFactor (G, 1, 1));
}
rec= true;
continue;
}
}
iter= factors;
smallestFactor= iter.getItem().factor();
while (smallestFactor.isUnivariate() && iter.hasItem())
{
iter++;
if (!iter.hasItem())
break;
smallestFactor= iter.getItem().factor();
}
minTdeg= totaldegree (smallestFactor);
if (iter.hasItem())
iter++;
for (; iter.hasItem(); iter++)
{
if (!iter.getItem().factor().isUnivariate() &&
(totaldegree (iter.getItem().factor()) < minTdeg))
{
smallestFactor= iter.getItem().factor();
minTdeg= totaldegree (smallestFactor);
}
}
if (tdegF % minTdeg == 0)
break;
setCharacteristic(0);
rec=true;
}
CanonicalForm Gp= Fp/smallestFactor;
Gp= Gp /Lc (Gp);
CanonicalForm Gpy= Gp (eval[0].mapinto(), 1);
CanonicalForm smallestFactorEvaly= smallestFactor (eval[0].mapinto(),1);
CanonicalForm Gpx= Gp (eval[1].mapinto(), 2);
CanonicalForm smallestFactorEvalx= smallestFactor (eval[1].mapinto(),2);
bool xValid= !(Gpx.inCoeffDomain() || smallestFactorEvalx.inCoeffDomain() ||
!gcd (Gpx, smallestFactorEvalx).inCoeffDomain());
bool yValid= !(Gpy.inCoeffDomain() || smallestFactorEvaly.inCoeffDomain() ||
!gcd (Gpy, smallestFactorEvaly).inCoeffDomain());
if (!xValid || !yValid)
{
rec= true;
setCharacteristic (0);
goto differentevalpoint;
}
setCharacteristic (0);
CanonicalForm mipo;
CFArray mipos= CFArray (2);
CFFList mipoFactors;
for (int i= 1; i < 3; i++)
{
CanonicalForm Fi= F(eval[i-1],i);
int s= tdegF/minTdeg + 1;
CanonicalForm bound= power (maxNorm (Fi), 2*(s-1));
bound *= power (CanonicalForm (s),s-1);
bound *= power (CanonicalForm (2), ((s-1)*(s-1))/2); //possible int overflow
CanonicalForm B = p;
long k = 1L;
while ( B < bound ) {
B *= p;
k++;
}
//TODO take floor (log2(k))
k= k+1;
#ifdef HAVE_FLINT
fmpz_poly_t FLINTFi;
convertFacCF2Fmpz_poly_t (FLINTFi, Fi);
setCharacteristic (p);
nmod_poly_t FLINTFpi, FLINTGpi;
if (i == 2)
{
convertFacCF2nmod_poly_t (FLINTFpi,
smallestFactorEvalx/lc (smallestFactorEvalx));
convertFacCF2nmod_poly_t (FLINTGpi, Gpx/lc (Gpx));
}
else
{
convertFacCF2nmod_poly_t (FLINTFpi,
smallestFactorEvaly/lc (smallestFactorEvaly));
convertFacCF2nmod_poly_t (FLINTGpi, Gpy/lc (Gpy));
}
nmod_poly_factor_t nmodFactors;
nmod_poly_factor_init (nmodFactors);
nmod_poly_factor_insert (nmodFactors, FLINTFpi, 1L);
nmod_poly_factor_insert (nmodFactors, FLINTGpi, 1L);
// the following fix is due to interface changes from FLINT 2.3 -> FLINT 2.4
# ifndef slong
# define slong long
# endif
slong * link= new slong [2];
fmpz_poly_t *v= new fmpz_poly_t[2];
fmpz_poly_t *w= new fmpz_poly_t[2];
fmpz_poly_init(v[0]);
fmpz_poly_init(v[1]);
fmpz_poly_init(w[0]);
fmpz_poly_init(w[1]);
fmpz_poly_factor_t liftedFactors;
fmpz_poly_factor_init (liftedFactors);
_fmpz_poly_hensel_start_lift (liftedFactors, link, v, w, FLINTFi,
nmodFactors, k);
nmod_poly_factor_clear (nmodFactors);
nmod_poly_clear (FLINTFpi);
nmod_poly_clear (FLINTGpi);
setCharacteristic(0);
CanonicalForm liftedSmallestFactor=
convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[0],x);
CanonicalForm otherFactor=
convertFmpz_poly_t2FacCF ((fmpz_poly_t &)liftedFactors->p[1],x);
modpk pk= modpk (p, k);
#elif defined(HAVE_NTL)
modpk pk= modpk (p, k);
ZZX NTLFi=convertFacCF2NTLZZX (pk (Fi*pk.inverse (lc(Fi))));
setCharacteristic (p);
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTLFpi, NTLGpi;
if (i == 2)
{
NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvalx/lc(smallestFactorEvalx));
NTLGpi=convertFacCF2NTLzzpX (Gpx/lc (Gpx));
}
else
{
NTLFpi=convertFacCF2NTLzzpX (smallestFactorEvaly/lc(smallestFactorEvaly));
NTLGpi=convertFacCF2NTLzzpX (Gpy/lc (Gpy));
}
vec_zz_pX modFactors;
modFactors.SetLength(2);
modFactors[0]= NTLFpi;
modFactors[1]= NTLGpi;
vec_ZZX liftedFactors;
MultiLift (liftedFactors, modFactors, NTLFi, (long) k);
setCharacteristic(0);
CanonicalForm liftedSmallestFactor=
convertNTLZZX2CF (liftedFactors[0], x);
CanonicalForm otherFactor=
convertNTLZZX2CF (liftedFactors[1], x);
#else
factoryError("absBiFactorizeMain: NTL/FLINT missing");
#endif
Off (SW_SYMMETRIC_FF);
liftedSmallestFactor= pk (liftedSmallestFactor);
if (i == 2)
liftedSmallestFactor= liftedSmallestFactor (eval[0],1);
else
liftedSmallestFactor= liftedSmallestFactor (eval[1],1);
On (SW_SYMMETRIC_FF);
CFMatrix *M= new CFMatrix (s, s);
(*M)(s,s)= power (CanonicalForm (p), k);
for (int j= 1; j < s; j++)
{
(*M) (j,j)= 1;
(*M) (j+1,j)= -liftedSmallestFactor;
}
#ifdef HAVE_FLINT
fmpz_mat_t FLINTM;
convertFacCFMatrix2Fmpz_mat_t(FLINTM,*M);
fmpq_t delta,eta;
fmpq_init(delta); fmpq_set_si(delta,1,1);
fmpq_init(eta); fmpq_set_si(eta,3,4);
fmpz_mat_transpose(FLINTM,FLINTM);
fmpz_mat_lll_storjohann(FLINTM,delta,eta);
fmpz_mat_transpose(FLINTM,FLINTM);
delete M;
M=convertFmpz_mat_t2FacCFMatrix(FLINTM);
fmpz_mat_clear(FLINTM);
#elif defined(HAVE_NTL)
mat_ZZ * NTLM= convertFacCFMatrix2NTLmat_ZZ (*M);
ZZ det;
transpose (*NTLM, *NTLM);
(void) LLL (det, *NTLM, 1L, 1L); //use floating point LLL ?
transpose (*NTLM, *NTLM);
delete M;
M= convertNTLmat_ZZ2FacCFMatrix (*NTLM);
delete NTLM;
#else
factoryError("NTL/FLINT missing: absBiFactorizeMain");
#endif
mipo= 0;
for (int j= 1; j <= s; j++)
mipo += (*M) (j,1)*power (x,s-j);
delete M;
mipoFactors= factorize (mipo);
if (mipoFactors.getFirst().factor().inCoeffDomain())
mipoFactors.removeFirst();
#ifdef HAVE_FLINT
fmpz_poly_clear (v[0]);
fmpz_poly_clear (v[1]);
fmpz_poly_clear (w[0]);
fmpz_poly_clear (w[1]);
delete [] v;
delete [] w;
delete [] link;
fmpz_poly_factor_clear (liftedFactors);
#endif
if (mipoFactors.length() > 1 ||
(mipoFactors.length() == 1 && mipoFactors.getFirst().exp() > 1) ||
mipo.inCoeffDomain())
{
rec=true;
goto differentevalpoint;
}
else
mipos[i-1]= mipo;
}
if (degree (mipos[0]) != degree (mipos[1]))
{
rec=true;
goto differentevalpoint;
}
On (SW_RATIONAL);
if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
alpha= rootOf (mipos[0]);
else
alpha= rootOf (mipos[1]);
int wrongMipo= 0;
Variable beta;
if (maxNorm (mipos[0]) < maxNorm (mipos[1]))
{
mipoFactors= factorize (mipos[1], alpha);
if (mipoFactors.getFirst().factor().inCoeffDomain())
mipoFactors.removeFirst();
for (iter= mipoFactors; iter.hasItem(); iter++)
{
if (degree (iter.getItem().factor()) > 1)
wrongMipo++;
}
if (wrongMipo == mipoFactors.length())
{
rec=true;
goto differentevalpoint;
}
wrongMipo= 0;
beta= rootOf (mipos[1]);
mipoFactors= factorize (mipos[0], beta);
if (mipoFactors.getFirst().factor().inCoeffDomain())
mipoFactors.removeFirst();
for (iter= mipoFactors; iter.hasItem(); iter++)
{
if (degree (iter.getItem().factor()) > 1)
wrongMipo++;
}
if (wrongMipo == mipoFactors.length())
{
rec=true;
goto differentevalpoint;
}
}
else
{
mipoFactors= factorize (mipos[0], alpha);
if (mipoFactors.getFirst().factor().inCoeffDomain())
mipoFactors.removeFirst();
for (iter= mipoFactors; iter.hasItem(); iter++)
{
if (degree (iter.getItem().factor()) > 1)
wrongMipo++;
}
if (wrongMipo == mipoFactors.length())
{
rec=true;
goto differentevalpoint;
}
wrongMipo= 0;
beta= rootOf (mipos[0]);
mipoFactors= factorize (mipos[1], beta);
if (mipoFactors.getFirst().factor().inCoeffDomain())
mipoFactors.removeFirst();
for (iter= mipoFactors; iter.hasItem(); iter++)
{
if (degree (iter.getItem().factor()) > 1)
wrongMipo++;
}
if (wrongMipo == mipoFactors.length())
{
rec=true;
goto differentevalpoint;
}
}
CanonicalForm F1;
if (degree (F,1) > minTdeg)
F1= F (eval[1], 2);
else
F1= F (eval[0], 1);
CFFList QaF1Factors;
bool swap= false;
if (F1.level() == 2)
{
swap= true;
F1=swapvar (F1, x, y);
F= swapvar (F, x, y);
}
wrongMipo= 0;
QaF1Factors= factorize (F1, alpha);
if (QaF1Factors.getFirst().factor().inCoeffDomain())
QaF1Factors.removeFirst();
for (iter= QaF1Factors; iter.hasItem(); iter++)
{
if (degree (iter.getItem().factor()) > minTdeg)
wrongMipo++;
}
if (wrongMipo == QaF1Factors.length())
{
rec= true;
F= bufF;
goto differentevalpoint;
}
CanonicalForm evaluation;
if (swap)
evaluation= eval[0];
else
evaluation= eval[1];
F *= bCommonDen (F);
F= F (y + evaluation, y);
int liftBound= degree (F,y) + 1;
modpk b= modpk();
CanonicalForm den= 1;
mipo= getMipo (alpha);
CFList uniFactors;
for (iter=QaF1Factors; iter.hasItem(); iter++)
uniFactors.append (iter.getItem().factor());
F /= Lc (F1);
#ifdef HAVE_FLINT
// init
fmpz_t FLINTf,FLINTD;
fmpz_init(FLINTf);
fmpz_init(FLINTD);
fmpz_poly_t FLINTmipo;
fmpz_poly_t FLINTLcf;
//conversion
convertFacCF2Fmpz_poly_t(FLINTmipo,mipo);
convertFacCF2Fmpz_poly_t(FLINTLcf,Lc (F*bCommonDen (F)));
// resultant, discriminant
fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
fmpz_poly_discriminant(FLINTD,FLINTmipo);
fmpz_mul(FLINTf,FLINTD,FLINTf);
den= abs (convertFmpz2CF(FLINTf));
// clean up
fmpz_clear(FLINTf);
// FLINTD is used below
fmpz_poly_clear(FLINTLcf);
fmpz_poly_clear(FLINTmipo);
#elif defined(HAVE_NTL)
ZZX NTLmipo= convertFacCF2NTLZZX (mipo);
ZZX NTLLcf= convertFacCF2NTLZZX (Lc (F*bCommonDen (F)));
ZZ NTLf= resultant (NTLmipo, NTLLcf);
ZZ NTLD= discriminant (NTLmipo);
den= abs (convertZZ2CF (NTLD*NTLf));
#else
factoryError("NTL/FLINT missing: absBiFactorizeMain");
#endif
// make factors elements of Z(a)[x] disable for modularDiophant
CanonicalForm multiplier= 1;
for (CFListIterator i= uniFactors; i.hasItem(); i++)
{
multiplier *= bCommonDen (i.getItem());
i.getItem()= i.getItem()*bCommonDen(i.getItem());
}
F *= multiplier;
F *= bCommonDen (F);
Off (SW_RATIONAL);
int ii= 0;
#ifdef HAVE_FLINT
CanonicalForm discMipo= convertFmpz2CF(FLINTD);
fmpz_clear(FLINTD);
#elif defined(HAVE_NTL)
CanonicalForm discMipo= convertZZ2CF (NTLD);
#endif
findGoodPrime (bufF*discMipo,ii);
findGoodPrime (F1*discMipo,ii);
findGoodPrime (F*discMipo,ii);
int pp=cf_getBigPrime(ii);
b = coeffBound( F, pp, mipo );
modpk bb= coeffBound (F1, pp, mipo);
if (bb.getk() > b.getk() ) b=bb;
bb= coeffBound (F, pp, mipo);
if (bb.getk() > b.getk() ) b=bb;
ExtensionInfo dummy= ExtensionInfo (alpha, false);
DegreePattern degs= DegreePattern (uniFactors);
bool earlySuccess= false;
CFList earlyFactors;
uniFactors= henselLiftAndEarly
(F, earlySuccess, earlyFactors, degs, liftBound,
uniFactors, dummy, evaluation, b, den);
DEBOUTLN (cerr, "lifted factors= " << uniFactors);
CanonicalForm MODl= power (y, liftBound);
On (SW_RATIONAL);
F *= bCommonDen (F);
Off (SW_RATIONAL);
CFList biFactors;
biFactors= factorRecombination (uniFactors, F, MODl, degs, evaluation, 1,
uniFactors.length()/2, b, den);
On (SW_RATIONAL);
if (earlySuccess)
biFactors= Union (earlyFactors, biFactors);
else if (!earlySuccess && degs.getLength() == 1)
biFactors= earlyFactors;
bool swap2= false;
appendSwapDecompress (biFactors, CFList(), CFList(), swap, swap2, CFMap());
if (isOn (SW_RATIONAL))
normalize (biFactors);
CFAFList result;
bool found= false;
for (CFListIterator i= biFactors; i.hasItem(); i++)
{
if (full)
result.append (CFAFactor (decompress (i.getItem(), M, S),
getMipo (alpha), 1));
if (totaldegree (i.getItem()) == minTdeg)
{
if (!full)
result= CFAFList (CFAFactor (decompress (i.getItem(), M, S),
getMipo (alpha), 1));
found= true;
if (!full)
break;
}
}
if (!found)
{
rec= true;
F= bufF;
goto differentevalpoint;
}
if (isRat)
On (SW_RATIONAL);
else
Off (SW_RATIONAL);
mpz_clear (M[0]);
mpz_clear (M[1]);
mpz_clear (M[2]);
mpz_clear (M[3]);
delete [] M;
mpz_clear (S[0]);
mpz_clear (S[1]);
delete [] S;
return result;
}
convertFacCFMatrix2Fmpz_mat_t
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
Definition FLINTconvert.cc:585
convertFmpz_mat_t2FacCFMatrix
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
Definition FLINTconvert.cc:598
convertFmpz2CF
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
Definition FLINTconvert.cc:154
convertFmpz_poly_t2FacCF
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
Definition FLINTconvert.cc:172
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
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
convertZZ2CF
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition NTLconvert.cc:495
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition NTLconvert.cc:691
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition NTLconvert.cc:285
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
convertFacCFMatrix2NTLmat_ZZ
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition NTLconvert.cc:1138
convertNTLmat_ZZ2FacCFMatrix
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition NTLconvert.cc:1153
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
swap
#define swap(_i, _j)
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
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition canonicalform.h:389
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
CFAFListIterator
ListIterator< CFAFactor > CFAFListIterator
Definition canonicalform.h:391
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
den
CanonicalForm den(const CanonicalForm &f)
Definition canonicalform.h:340
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
CFAFList
List< CFAFactor > CFAFList
Definition canonicalform.h:390
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
b
CanonicalForm b
Definition cfModGcd.cc:4111
modularIrredTestWithShift
bool modularIrredTestWithShift(const CanonicalForm &F)
modular absolute irreducibility test with shift as described in "Modular LasVegas Algorithms for Poly...
Definition cfNewtonPolygon.cc:1292
absIrredTest
bool absIrredTest(const CanonicalForm &F)
absolute irreducibility test as described in "Modular Las Vegas Algorithmsfor Polynomial Absolute Fac...
Definition cfNewtonPolygon.cc:1163
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition cfNewtonPolygon.cc:853
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_algorithm.cc:536
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
resultant
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).
Definition cf_resultant.cc:173
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
SW_SYMMETRIC_FF
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition cf_defs.h:33
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
cf_getBigPrime
int cf_getBigPrime(int i)
Definition cf_primes.cc:39
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition canonicalform.cc:210
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
DegreePattern
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition DegreePattern.h:32
DegreePattern::getLength
int getLength() const
getter
Definition DegreePattern.h:86
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
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::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
modpk::inverse
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
Definition fac_util.cc:59
modpk::getk
int getk() const
Definition fac_util.h:36
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
full
bool full
Definition facAbsBiFact.cc:39
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
alpha
Variable alpha
Definition facAbsBiFact.cc:52
choosePoint
int choosePoint(const CanonicalForm &F, int tdegF, CFArray &eval, bool rec, int absValue)
Definition facAbsBiFact.cc:81
result
return result
Definition facAbsBiFact.cc:76
slong
#define slong
uniAbsFactorize
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
s
const CanonicalForm int s
Definition facAbsFact.cc:51
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
beta
Variable beta
Definition facAbsFact.cc:95
w
const CanonicalForm & w
Definition facAbsFact.cc:51
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
modpk
return modpk(p, k)
coeffBound
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
Definition facBivar.cc:97
B
b *CanonicalForm B
Definition facBivar.cc:52
findGoodPrime
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
Definition facBivar.cc:61
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
found
bool found
Definition facFactorize.cc:55
eval
CFList & eval
Definition facFactorize.cc:47
appendSwapDecompress
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
Definition facFqBivarUtil.cc:70
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition facFqBivar.cc:1155
factorRecombination
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoringmultivariate polynomials over a finite field" by ...
Definition facFqBivar.cc:589
j
int j
Definition facHensel.cc:110
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
rootOf
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
G
STATIC_VAR TreeM * G
Definition janet.cc:31
absValue
number absValue(poly p)
Definition linearAlgebra.cc:734
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
M
#define M
Definition sirandom.c:25
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## normalize()

void normalize | ( | CFAFList & | L | ) |

inline static

normalize factors, i.e. make factors monic

Definition at line 37 of file facAbsBiFact.h.

{
for (CFAFListIterator i= L; i.hasItem(); i++)
i.getItem()= CFAFactor (i.getItem().factor()/Lc (i.getItem().factor()),
i.getItem().minpoly(), i.getItem().exp());
}

## uniAbsFactorize()

CFAFList uniAbsFactorize | ( | const CanonicalForm & | F,
|  | bool | full = false )

univariate absolute factorization over Q

Returns
  uniAbsFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Parameters

  [in] | F | univariate poly irreducible over Q
  [in] | full | true if all factors should be returned