Loading...
Searching...
No Matches
facFqBivar.h
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqBivar.h
*
* This file provides functions for factorizing a bivariate polynomial over
* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#ifndef FAC_FQ_BIVAR_H
#define FAC_FQ_BIVAR_H
// #include "config.h"
#include "timing.h"
#include "cf_assert.h"
#include "facFqBivarUtil.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "cf_map.h"
#include "cfNewtonPolygon.h"
#include "fac_util.h"
#include "cf_algorithm.h"
TIMING_DEFINE_PRINT(fac_fq_bi_sqrf)
TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf)
static const double log2exp= 1.442695041;
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
/// Factorization of a squarefree bivariate polynomials over an arbitrary finite
/// field, information on the current field we work over is in @a info. @a info
/// may also contain information about the initial field if initial and current
/// field do not coincide. In this case the current field is an extension of the
/// initial field and the factors returned are factors of F over the initial
/// field.
///
/// @return @a biFactorize returns a list of factors of F. If F is not monic
/// its leading coefficient is not outputted.
/// @sa extBifactorize()
CFList
biFactorize (const CanonicalForm& F, ///< [in] a sqrfree bivariate poly
const ExtensionInfo& info ///< [in] information about extension
);
#ifdef HAVE_NTL // biFactorize
inline CFList
biSqrfFactorizeHelper (const CanonicalForm& G, const ExtensionInfo& info)
{
CFMap N;
CanonicalForm F= compress (G, N);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
if (info.getAlpha().level() != 1)
{
contentXFactors= factorize (contentX, info.getAlpha());
contentYFactors= factorize (contentY, info.getAlpha());
}
else if (info.getAlpha().level() == 1 && info.getGFDegree() == 1)
{
contentXFactors= factorize (contentX);
contentYFactors= factorize (contentY);
}
else if (info.getAlpha().level() == 1 && info.getGFDegree() != 1)
{
CFList bufContentX, bufContentY;
bufContentX= biFactorize (contentX, info);
bufContentY= biFactorize (contentY, info);
for (CFListIterator iter= bufContentX; iter.hasItem(); iter++)
contentXFactors.append (CFFactor (iter.getItem(), 1));
for (CFListIterator iter= bufContentY; iter.hasItem(); iter++)
contentYFactors.append (CFFactor (iter.getItem(), 1));
}
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
if (F.inCoeffDomain())
{
CFList result;
for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
result.append (N (i.getItem().factor()));
for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
result.append (N (i.getItem().factor()));
normalize (result);
result.insert (Lc (G));
return result;
}
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);
CFList result= biFactorize (F, info);
for (CFListIterator i= result; i.hasItem(); i++)
i.getItem()= N (decompress (i.getItem(), M, S));
for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
result.append (N(i.getItem().factor()));
for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
result.append (N (i.getItem().factor()));
normalize (result);
result.insert (Lc(G));
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;
}
#endif
/// factorize a squarefree bivariate polynomial over \f$ F_{p} \f$.
///
/// @return @a FpBiSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
/// @sa FqBiSqrfFactorize(), GFBiSqrfFactorize()
#ifdef HAVE_NTL // biSqrfFactorizeHelper, biFactorize
inline
CFList FpBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
)
{
ExtensionInfo info= ExtensionInfo (false);
return biSqrfFactorizeHelper (G, info);
}
#endif
/// factorize a squarefree bivariate polynomial over \f$ F_{p}(\alpha ) \f$.
///
/// @return @a FqBiSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
/// @sa FpBiSqrfFactorize(), GFBiSqrfFactorize()
#ifdef HAVE_NTL // biSqrfFactorizeHelper, biFactorize
inline
CFList FqBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
const Variable& alpha ///< [in] algebraic variable
)
{
ExtensionInfo info= ExtensionInfo (alpha, false);
return biSqrfFactorizeHelper (G, info);
}
#endif
/// factorize a squarefree bivariate polynomial over GF
///
/// @return @a GFBiSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
/// @sa FpBiSqrfFactorize(), FqBiSqrfFactorize()
#ifdef HAVE_NTL // biSqrfFactorizeHelper, biFactorize
inline
CFList GFBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
)
{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
return biSqrfFactorizeHelper (G, info);
}
#endif
/// factorize a bivariate polynomial over \f$ F_{p} \f$
///
/// @return @a FpBiFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
/// @sa FqBiFactorize(), GFBiFactorize()
#ifdef HAVE_NTL // biFactorize
inline
CFFList
FpBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
bool substCheck= true ///< [in] enables substitute check
)
{
ExtensionInfo info= ExtensionInfo (false);
CFMap N;
CanonicalForm F= compress (G, N);
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(int,F.level());
for (int i= 1; i <= F.level(); i++)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
if (foundOne)
{
CFFList result= FpBiFactorize (F, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= F.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= FpBiFactorize (tmp2, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
decompress (newResult, N);
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
CanonicalForm LcF= Lc (F);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
contentXFactors= factorize (contentX);
contentYFactors= factorize (contentY);
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
decompress (contentXFactors, N);
decompress (contentYFactors, N);
CFFList result;
if (F.inCoeffDomain())
{
result= Union (contentXFactors, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
return result;
}
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);
TIMING_START (fac_fq_bi_sqrf);
CFFList sqrf= FpSqrf (F, false);
TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
"time for bivariate sqrf factors over Fp: ");
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_bi_factor_sqrf);
bufResult= biFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
"time to factor bivariate sqrf factors over Fp: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (N (decompress (i.getItem(), M, S)),
iter.getItem().exp()));
}
result= Union (result, contentXFactors);
result= Union (result, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 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;
return result;
}
#endif
/// factorize a bivariate polynomial over \f$ F_{p}(\alpha ) \f$
///
/// @return @a FqBiFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
/// @sa FpBiFactorize(), FqBiFactorize()
#ifdef HAVE_NTL // biFactorize
inline
CFFList
FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
const Variable & alpha, ///< [in] algebraic variable
bool substCheck= true ///< [in] enables substitute check
)
{
ExtensionInfo info= ExtensionInfo (alpha, false);
CFMap N;
CanonicalForm F= compress (G, N);
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(int,F.level());
for (int i= 1; i <= F.level(); i++)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
if (foundOne)
{
CFFList result= FqBiFactorize (F, alpha, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= F.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= FqBiFactorize (tmp2, alpha, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
decompress (newResult, N);
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
CanonicalForm LcF= Lc (F);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
contentXFactors= factorize (contentX, alpha);
contentYFactors= factorize (contentY, alpha);
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
decompress (contentXFactors, N);
decompress (contentYFactors, N);
CFFList result;
if (F.inCoeffDomain())
{
result= Union (contentXFactors, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
return result;
}
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);
TIMING_START (fac_fq_bi_sqrf);
CFFList sqrf= FqSqrf (F, alpha, false);
TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
"time for bivariate sqrf factors over Fq: ");
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_bi_factor_sqrf);
bufResult= biFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
"time to factor bivariate sqrf factors over Fq: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (N (decompress (i.getItem(), M, S)),
iter.getItem().exp()));
}
result= Union (result, contentXFactors);
result= Union (result, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 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;
return result;
}
#endif
/// factorize a bivariate polynomial over GF
///
/// @return @a GFBiFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
/// @sa FpBiFactorize(), FqBiFactorize()
#ifdef HAVE_NTL // biFactorize
inline
CFFList
GFBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
bool substCheck= true ///< [in] enables substitute check
)
{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
CFMap N;
CanonicalForm F= compress (G, N);
if (substCheck)
{
bool foundOne= false;
int * substDegree=NEW_ARRAY(int,F.level());
for (int i= 1; i <= F.level(); i++)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
if (foundOne)
{
CFFList result= GFBiFactorize (F, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= F.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= GFBiFactorize (tmp2, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
decompress (newResult, N);
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
CanonicalForm LcF= Lc (F);
CanonicalForm contentX= content (F, 1);
CanonicalForm contentY= content (F, 2);
F /= (contentX*contentY);
CFFList contentXFactors, contentYFactors;
contentXFactors= factorize (contentX);
contentYFactors= factorize (contentY);
if (contentXFactors.getFirst().factor().inCoeffDomain())
contentXFactors.removeFirst();
if (contentYFactors.getFirst().factor().inCoeffDomain())
contentYFactors.removeFirst();
decompress (contentXFactors, N);
decompress (contentYFactors, N);
CFFList result;
if (F.inCoeffDomain())
{
result= Union (contentXFactors, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 1));
return result;
}
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);
TIMING_START (fac_fq_bi_sqrf);
CFFList sqrf= GFSqrf (F, false);
TIMING_END_AND_PRINT (fac_fq_bi_sqrf,
"time for bivariate sqrf factors over GF: ");
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_bi_factor_sqrf);
bufResult= biFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_bi_factor_sqrf,
"time to factor bivariate sqrf factors over GF: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (N (decompress (i.getItem(), M, S)),
iter.getItem().exp()));
}
result= Union (result, contentXFactors);
result= Union (result, contentYFactors);
normalize (result);
result.insert (CFFactor (LcF, 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;
return result;
}
#endif
/// \f$ \prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer
///
/// @return @a prodMod0 computes the above defined product
/// @sa prodMod()
CanonicalForm prodMod0 (const CFList& L, ///< [in] a list of compressed,
///< bivariate polynomials
const CanonicalForm& M,///< [in] a power of Variable (2)
const modpk& b= modpk()///< [in] coeff bound
);
/// find an evaluation point p, s.t. F(p,y) is squarefree and
/// \f$ deg_{y} (F(p,y))= deg_{y} (F(x,y)) \f$.
///
/// @return @a evalPoint returns an evaluation point, which is valid if and only
/// if fail == false.
CanonicalForm
evalPoint (const CanonicalForm& F, ///< [in] compressed, bivariate poly
CanonicalForm & eval, ///< [in,out] F (p, y)
const Variable& alpha, ///< [in] algebraic variable
CFList& list, ///< [in] list of points already considered
const bool& GF, ///< [in] GaloisFieldDomain?
bool& fail ///< [in,out] equals true, if there is no
///< valid evaluation point
);
/// Univariate factorization of squarefree monic polys over finite fields via
/// NTL. If the characteristic is even special GF2 routines of NTL are used.
///
/// @return @a uniFactorizer returns a list of monic factors
CFList
uniFactorizer (const CanonicalForm& A, ///< [in] squarefree univariate poly
const Variable& alpha, ///< [in] algebraic variable
const bool& GF ///< [in] GaloisFieldDomain?
);
/// naive factor recombination over an extension of the initial field.
/// Uses precomputed data to exclude combinations that are not possible.
///
/// @return @a extFactorRecombination returns a list of factors over the initial
/// field, whose shift to zero is reversed.
/// @sa factorRecombination(), extEarlyFactorDetection()
CFList
extFactorRecombination (
CFList& factors, ///< [in,out] list of lifted factors that are
///< monic wrt Variable (1),
///< original factors-factors found
CanonicalForm& F, ///< [in,out] poly to be factored,
///< F/factors found
const CanonicalForm& M, ///< [in] Variable (2)^liftBound
const ExtensionInfo& info,///< [in] contains information about
///< extension
DegreePattern& degs,
const CanonicalForm& eval,///< [in] evaluation point
int s, ///< [in] algorithm starts checking subsets
///< of size s
int thres ///< [in] threshold for the size of subsets
///< which are checked, for a full factor
///< recombination choose
///< thres= factors.length()/2
);
/// naive factor recombination.
/// Uses precomputed data to exclude combinations that are not possible.
///
/// @return @a factorRecombination returns a list of factors of F.
/// @sa extFactorRecombination(), earlyFactorDetectection()
CFList
factorRecombination (
CFList& factors, ///< [in,out] list of lifted factors
///< that are monic wrt Variable (1)
CanonicalForm& F, ///< [in,out] poly to be factored
const CanonicalForm& M, ///< [in] Variable (2)^liftBound
DegreePattern& degs, ///< [in] degree pattern
const CanonicalForm& eval, ///< [in] evaluation point
int s, ///< [in] algorithm starts checking
///< subsets of size s
int thres, ///< [in] threshold for the size of
///< subsets which are checked, for a
///< full factor recombination choose
///< thres= factors.length()/2
const modpk& b=modpk(), ///< [in] coeff bound
const CanonicalForm& den= 1 ///< [in] bound on the den if over Q (a)
);
/// chooses a field extension.
///
/// @return @a chooseExtension returns an extension specified by @a beta of
/// appropiate size
Variable chooseExtension (
const Variable & alpha, ///< [in] some algebraic variable
const Variable & beta, ///< [in] some algebraic variable
int k ///< [in] some int
);
/// compute lifting precisions from the shape of the Newton polygon of F
///
/// @return @a getLiftPrecisions returns lifting precisions computed from the
/// shape of the Newton polygon of F
int *
getLiftPrecisions (const CanonicalForm& F, ///< [in] a bivariate poly
int& sizeOfOutput, ///< [in,out] size of the output
int degreeLC ///< [in] degree of the leading coeff
///< [in] of F wrt. Variable (1)
);
/// detects factors of @a F at stage @a deg of Hensel lifting.
/// No combinations of more than one factor are tested. Lift bound and possible
/// degree pattern are updated.
///
/// @sa factorRecombination(), extEarlyFactorDetection()
void
earlyFactorDetection (
CFList& reconstructedFactors, ///< [in,out] list of reconstructed
///< factors
CanonicalForm& F, ///< [in,out] poly to be factored, returns
///< poly divided by detected factors in case
///< of success
CFList& factors, ///< [in,out] list of factors lifted up to
///< @a deg, returns a list of factors
///< without detected factors
int& adaptedLiftBound, ///< [in,out] adapted lift bound
int*& factorsFoundIndex,///< [in,out] factors already considered
DegreePattern& degs, ///< [in,out] degree pattern, is updated
///< whenever we find a factor
bool& success, ///< [in,out] indicating success
int deg, ///< [in] stage of Hensel lifting
const CanonicalForm& eval, ///<[in] evaluation point
const modpk& b= modpk()///< [in] coeff bound
);
/// detects factors of @a F at stage @a deg of Hensel lifting.
/// No combinations of more than one factor are tested. Lift bound and possible
/// degree pattern are updated.
///
/// @sa factorRecombination(), earlyFactorDetection()
void
extEarlyFactorDetection (
CFList& reconstructedFactors, ///< [in,out] list of reconstructed
///< factors
CanonicalForm& F, ///< [in,out] poly to be factored, returns
///< poly divided by detected factors in case
///< of success
CFList& factors, ///< [in,out] list of factors lifted up to
///< @a deg, returns a list of factors
///< without detected factors
int& adaptedLiftBound, ///< [in,out] adapted lift bound
int*& factorsFoundIndex, ///< [in,out] factors already considered
DegreePattern& degs, ///< [in,out] degree pattern, is updated
///< whenever we find a factor
bool& success, ///< [in,out] indicating success
const ExtensionInfo& info, ///< [in] information about extension
const CanonicalForm& eval, ///< [in] evaluation point
int deg ///< [in] stage of Hensel lifting
);
/// hensel Lifting and early factor detection
///
/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
/// factors without factors which have been detected at an early stage
/// of Hensel lifting
/// @sa earlyFactorDetection(), extEarlyFactorDetection()
CFList
henselLiftAndEarly (
CanonicalForm& A, ///< [in,out] poly to be factored,
///< returns poly divided by detected factors
///< in case of success
bool& earlySuccess, ///< [in,out] indicating success
CFList& earlyFactors, ///< [in,out] list of factors detected
///< at early stage of Hensel lifting
DegreePattern& degs, ///< [in,out] degree pattern
int& liftBound, ///< [in,out] (adapted) lift bound
const CFList& uniFactors, ///< [in] univariate factors
const ExtensionInfo& info, ///< [in] information about extension
const CanonicalForm& eval, ///< [in] evaluation point
modpk& b, ///< [in] coeff bound
CanonicalForm& den ///< [in] bound on the den if over Q(a)
);
/// hensel Lifting and early factor detection
///
/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
/// factors without factors which have been detected at an early stage
/// of Hensel lifting
/// @sa earlyFactorDetection(), extEarlyFactorDetection()
CFList
henselLiftAndEarly (
CanonicalForm& A, ///< [in,out] poly to be factored,
///< returns poly divided by detected factors
///< in case of success
bool& earlySuccess, ///< [in,out] indicating success
CFList& earlyFactors, ///< [in,out] list of factors detected
///< at early stage of Hensel lifting
DegreePattern& degs, ///< [in,out] degree pattern
int& liftBound, ///< [in,out] (adapted) lift bound
const CFList& uniFactors, ///< [in] univariate factors
const ExtensionInfo& info, ///< [in] information about extension
const CanonicalForm& eval ///< [in] evaluation point
);
/// Factorization over an extension of initial field
///
/// @return @a extBiFactorize returns factorization of F over initial field
/// @sa biFactorize()
CFList
extBiFactorize (const CanonicalForm& F, ///< [in] poly to be factored
const ExtensionInfo& info ///< [in] info about extension
);
#endif
#endif
/* FAC_FQ_BIVAR_H */
DegreePattern.h
This file provides a class to handle degree patterns.
ExtensionInfo.h
This file provides a class to store information about finite fields and extensions thereof.
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
den
CanonicalForm den(const CanonicalForm &f)
Definition canonicalform.h:340
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
log2exp
static const double log2exp
Definition cfEzgcd.cc:45
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
b
CanonicalForm b
Definition cfModGcd.cc:4111
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition cfNewtonPolygon.cc:853
cfNewtonPolygon.h
This file provides functions to compute the Newton polygon of a bivariate polynomial.
cf_algorithm.h
declarations of higher level algorithms.
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
cf_assert.h
assertions for Factory
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
cf_map.h
map polynomials
cf_util.h
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::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
DegreePattern
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition DegreePattern.h:32
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
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::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
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
alpha
Variable alpha
Definition facAbsBiFact.cc:52
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
result
return result
Definition facAbsBiFact.cc:76
s
const CanonicalForm int s
Definition facAbsFact.cc:51
beta
Variable beta
Definition facAbsFact.cc:95
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition facAlgFuncUtil.cc:120
modpk
return modpk(p, k)
eval
CFList & eval
Definition facFactorize.cc:47
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition facFqBivarUtil.cc:1295
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition facFqBivarUtil.cc:1089
facFqBivarUtil.h
This file provides utility functions for bivariate factorization.
tmp2
CFList tmp2
Definition facFqBivar.cc:75
FqBiFactorize
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:317
biFactorize
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
Definition facFqBivar.cc:8306
extEarlyFactorDetection
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition facFqBivar.cc:985
factorRecombination
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1)
naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
Definition facFqBivar.cc:589
FpBiFactorize
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:190
extFactorRecombination
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &M, const ExtensionInfo &info, DegreePattern &degs, const CanonicalForm &eval, int s, int thres)
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude c...
Definition facFqBivar.cc:373
GFBiFactorize
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition facFqBivar.h:446
FqBiSqrfFactorize
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:156
prodMod0
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
biSqrfFactorizeHelper
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
Definition facFqBivar.h:55
extBiFactorize
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition facFqBivar.cc:8931
getLiftPrecisions
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
Definition facFqBivar.cc:1123
FpBiSqrfFactorize
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:141
evalPoint
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
Definition facFqBivar.cc:87
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
GFBiSqrfFactorize
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition facFqBivar.h:172
uniFactorizer
CFList uniFactorizer(const CanonicalForm &A, const Variable &alpha, const bool &GF)
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic ...
Definition facFqBivar.cc:163
chooseExtension
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
Definition facFqBivar.cc:809
earlyFactorDetection
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern &degs, bool &success, int deg, const CanonicalForm &eval, const modpk &b=modpk())
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition facFqBivar.cc:974
facFqSquarefree.h
This file provides functions for squarefrees factorizing over , or GF.
GFSqrf
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:116
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
j
int j
Definition facHensel.cc:110
fac_util.h
operations mod p^k and some other useful functions for factorization
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gf_name
VAR char gf_name
Definition gfops.cc:52
G
STATIC_VAR TreeM * G
Definition janet.cc:31
info
#define info
Definition libparse.cc:1256
A
#define A
Definition sirandom.c:24
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.h
TIMING_DEFINE_PRINT
#define TIMING_DEFINE_PRINT(t)
Definition timing.h:95
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