Loading...
Searching...
No Matches
facBivar.cc
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facBivar.cc
*
* bivariate factorization over Q(a)
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#include "config.h"
#include "cf_assert.h"
#include "cf_util.h"
#include "debug.h"
#include "timing.h"
#include "cf_algorithm.h"
#include "facFqBivar.h"
#include "facBivar.h"
#include "facHensel.h"
#include "facMul.h"
#include "cf_primes.h"
TIMING_DEFINE_PRINT(fac_uni_factorizer)
TIMING_DEFINE_PRINT(fac_bi_hensel_lift)
TIMING_DEFINE_PRINT(fac_bi_factor_recombination)
TIMING_DEFINE_PRINT(fac_bi_evaluation)
TIMING_DEFINE_PRINT(fac_bi_shift_to_zero)
// bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
// Gelfond: Transcendental and Algebraic Numbers)
modpk
coeffBound ( const CanonicalForm & f, int p )
{
int * degs = degrees( f );
int M = 0, i, k = f.level();
CanonicalForm b= 1;
for ( i = 1; i <= k; i++ )
{
M += degs[i];
b *= degs[i] + 1;
}
DELETE_ARRAY(degs);
b /= power (CanonicalForm (2), k);
b= b.sqrt() + 1;
b *= 2 * maxNorm( f ) * power( CanonicalForm( 2 ), M );
CanonicalForm B = p;
k = 1;
while ( B < b ) {
B *= p;
k++;
}
return modpk( p, k );
}
void findGoodPrime(const CanonicalForm &f, int &start)
{
if (! f.inBaseDomain() )
{
CFIterator i = f;
for(;;)
{
if ( i.hasTerms() )
{
findGoodPrime(i.coeff(),start);
if (0==cf_getBigPrime(start)) return;
if((i.exp()!=0) && ((i.exp() % cf_getBigPrime(start))==0))
{
start++;
i=f;
}
else i++;
}
else break;
}
}
else
{
if (f.inZ())
{
if (0==cf_getBigPrime(start)) return;
while((!f.isZero()) && (mod(f,cf_getBigPrime(start))==0))
{
start++;
if (0==cf_getBigPrime(start)) return;
}
}
}
}
modpk
coeffBound ( const CanonicalForm & f, int p, const CanonicalForm& mipo )
{
int * degs = degrees( f );
int M = 0, i, k = f.level();
CanonicalForm K= 1;
for ( i = 1; i <= k; i++ )
{
M += degs[i];
K *= degs[i] + 1;
}
DELETE_ARRAY(degs);
K /= power (CanonicalForm (2), k/2);
K *= power (CanonicalForm (2), M);
int N= degree (mipo);
CanonicalForm b;
b= 2*power (maxNorm (f), N)*power (maxNorm (mipo), 4*N)*K*
power (CanonicalForm (2), N)*
power (CanonicalForm (N+1), 4*N);
b /= power (abs (lc (mipo)), N);
CanonicalForm B = p;
k = 1;
while ( B < b ) {
B *= p;
k++;
}
return modpk( p, k );
}
CFList conv (const CFFList& L)
{
CFList result;
for (CFFListIterator i= L; i.hasItem(); i++)
result.append (i.getItem().factor());
return result;
}
bool testPoint (const CanonicalForm& F, CanonicalForm& G, int i)
{
G= F (i, 2);
if (G.inCoeffDomain() || degree (F, 1) > degree (G, 1))
return false;
if (degree (gcd (deriv (G, G.mvar()), G)) > 0)
return false;
return true;
}
CanonicalForm evalPoint (const CanonicalForm& F, int& i)
{
Variable x= Variable (1);
Variable y= Variable (2);
CanonicalForm result;
int k;
if (i == 0)
{
if (testPoint (F, result, i))
return result;
}
do
{
if (i > 0)
k= 1;
else
k= 2;
while (k < 3)
{
if (k == 1)
{
if (testPoint (F, result, i))
return result;
}
else
{
if (testPoint (F, result, -i))
{
i= -i;
return result;
}
else if (i < 0)
i= -i;
}
k++;
}
i++;
} while (1);
}
#if defined(HAVE_NTL) || defined(HAVE_FLINT) // henselLiftAndEarly
CFList biFactorize (const CanonicalForm& F, const Variable& v)
{
if (F.inCoeffDomain())
return CFList(F);
bool extension= (v.level() != 1);
CanonicalForm A;
if (isOn (SW_RATIONAL))
A= F*bCommonDen (F);
else
A= F;
CanonicalForm mipo;
if (extension)
mipo= getMipo (v);
if (A.isUnivariate())
{
CFFList buf;
if (extension)
buf= factorize (A, v);
else
buf= factorize (A, true);
CFList result= conv (buf);
if (result.getFirst().inCoeffDomain())
result.removeFirst();
return result;
}
CFMap N;
A= compress (A, N);
Variable y= A.mvar();
if (y.level() > 2) return CFList (F);
Variable x= Variable (1);
CanonicalForm contentAx= content (A, x);
CanonicalForm contentAy= content (A);
A= A/(contentAx*contentAy);
CFFList contentAxFactors, contentAyFactors;
if (extension)
{
if (!contentAx.inCoeffDomain())
{
contentAxFactors= factorize (contentAx, v);
if (contentAxFactors.getFirst().factor().inCoeffDomain())
contentAxFactors.removeFirst();
}
if (!contentAy.inCoeffDomain())
{
contentAyFactors= factorize (contentAy, v);
if (contentAyFactors.getFirst().factor().inCoeffDomain())
contentAyFactors.removeFirst();
}
}
else
{
if (!contentAx.inCoeffDomain())
{
contentAxFactors= factorize (contentAx, true);
if (contentAxFactors.getFirst().factor().inCoeffDomain())
contentAxFactors.removeFirst();
}
if (!contentAy.inCoeffDomain())
{
contentAyFactors= factorize (contentAy, true);
if (contentAyFactors.getFirst().factor().inCoeffDomain())
contentAyFactors.removeFirst();
}
}
//check trivial case
if (degree (A) == 1 || degree (A, 1) == 1 ||
(size (A) == 2 && igcd (degree (A), degree (A,1)) == 1))
{
CFList factors;
factors.append (A);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), false, false, N);
normalize (factors);
return factors;
}
//trivial case
CFList factors;
if (A.inCoeffDomain())
{
append (factors, conv (contentAxFactors));
append (factors, conv (contentAyFactors));
decompress (factors, N);
return factors;
}
else if (A.isUnivariate())
{
if (extension)
factors= conv (factorize (A, v));
else
factors= conv (factorize (A, true));
append (factors, conv (contentAxFactors));
append (factors, conv (contentAyFactors));
decompress (factors, N);
return factors;
}
if (irreducibilityTest (A))
{
CFList factors;
factors.append (A);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), false, false, N);
normalize (factors);
return factors;
}
bool swap= false;
if (degree (A) > degree (A, x))
{
A= swapvar (A, y, x);
swap= true;
}
CanonicalForm Aeval, bufAeval, buf;
CFList uniFactors, list, bufUniFactors;
DegreePattern degs;
DegreePattern bufDegs;
CanonicalForm Aeval2, bufAeval2;
CFList bufUniFactors2, list2, uniFactors2;
DegreePattern degs2;
DegreePattern bufDegs2;
bool swap2= false;
// several univariate factorizations to obtain more information about the
// degree pattern therefore usually less combinations have to be tried during
// the recombination process
int factorNums= 2;
int subCheck1= substituteCheck (A, x);
int subCheck2= substituteCheck (A, y);
buf= swapvar (A,x,y);
int evaluation, evaluation2=0, bufEvaluation= 0, bufEvaluation2= 0;
for (int i= 0; i < factorNums; i++)
{
bufAeval= A;
TIMING_START (fac_bi_evaluation);
bufAeval= evalPoint (A, bufEvaluation);
TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
bufAeval2= buf;
TIMING_START (fac_bi_evaluation);
bufAeval2= evalPoint (buf, bufEvaluation2);
TIMING_END_AND_PRINT (fac_bi_evaluation,
"time for eval point over Q in y: ");
// univariate factorization
TIMING_START (fac_uni_factorizer);
if (extension)
bufUniFactors= conv (factorize (bufAeval, v));
else
bufUniFactors= conv (factorize (bufAeval, true));
TIMING_END_AND_PRINT (fac_uni_factorizer,
"time for univariate factorization over Q: ");
DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
(prod (bufUniFactors) == bufAeval));
if (bufUniFactors.getFirst().inCoeffDomain())
bufUniFactors.removeFirst();
if (bufUniFactors.length() == 1)
{
factors.append (A);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), swap, swap2, N);
if (isOn (SW_RATIONAL))
normalize (factors);
return factors;
}
TIMING_START (fac_uni_factorizer);
if (extension)
bufUniFactors2= conv (factorize (bufAeval2, v));
else
bufUniFactors2= conv (factorize (bufAeval2, true));
TIMING_END_AND_PRINT (fac_uni_factorizer,
"time for univariate factorization in y over Q: ");
DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
(prod (bufUniFactors2) == bufAeval2));
if (bufUniFactors2.getFirst().inCoeffDomain())
bufUniFactors2.removeFirst();
if (bufUniFactors2.length() == 1)
{
factors.append (A);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), swap, swap2, N);
if (isOn (SW_RATIONAL))
normalize (factors);
return factors;
}
if (i == 0)
{
if (subCheck1 > 0)
{
int subCheck= substituteCheck (bufUniFactors);
if (subCheck > 1 && (subCheck1%subCheck == 0))
{
CanonicalForm bufA= A;
subst (bufA, bufA, subCheck, x);
factors= biFactorize (bufA, v);
reverseSubst (factors, subCheck, x);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), swap, swap2, N);
if (isOn (SW_RATIONAL))
normalize (factors);
return factors;
}
}
if (subCheck2 > 0)
{
int subCheck= substituteCheck (bufUniFactors2);
if (subCheck > 1 && (subCheck2%subCheck == 0))
{
CanonicalForm bufA= A;
subst (bufA, bufA, subCheck, y);
factors= biFactorize (bufA, v);
reverseSubst (factors, subCheck, y);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), swap, swap2, N);
if (isOn (SW_RATIONAL))
normalize (factors);
return factors;
}
}
}
// degree analysis
bufDegs = DegreePattern (bufUniFactors);
bufDegs2= DegreePattern (bufUniFactors2);
if (i == 0)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
uniFactors= bufUniFactors;
degs= bufDegs;
Aeval2= bufAeval2;
evaluation2= bufEvaluation2;
uniFactors2= bufUniFactors2;
degs2= bufDegs2;
}
else
{
degs.intersect (bufDegs);
degs2.intersect (bufDegs2);
if (bufUniFactors2.length() < uniFactors2.length())
{
uniFactors2= bufUniFactors2;
Aeval2= bufAeval2;
evaluation2= bufEvaluation2;
}
if (bufUniFactors.length() < uniFactors.length())
{
uniFactors= bufUniFactors;
Aeval= bufAeval;
evaluation= bufEvaluation;
}
}
if (bufEvaluation > 0)
bufEvaluation++;
else
bufEvaluation= -bufEvaluation + 1;
if (bufEvaluation > 0)
bufEvaluation2++;
else
bufEvaluation2= -bufEvaluation2 + 1;
}
if (uniFactors.length() > uniFactors2.length() ||
(uniFactors.length() == uniFactors2.length()
&& degs.getLength() > degs2.getLength()))
{
degs= degs2;
uniFactors= uniFactors2;
evaluation= evaluation2;
Aeval= Aeval2;
A= buf;
swap2= true;
}
if (degs.getLength() == 1) // A is irreducible
{
factors.append (A);
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), swap, swap2, N);
if (isOn (SW_RATIONAL))
normalize (factors);
return factors;
}
A *= bCommonDen (A);
A= A (y + evaluation, y);
int liftBound= degree (A, y) + 1;
modpk b= modpk();
bool mipoHasDen= false;
CanonicalForm den= 1;
if (!extension)
{
Off (SW_RATIONAL);
int i= 0;
findGoodPrime(F,i);
findGoodPrime(Aeval,i);
findGoodPrime(A,i);
if (i >= cf_getNumBigPrimes())
printf ("out of primes\n"); //TODO exit
int p=cf_getBigPrime(i);
b = coeffBound( A, p );
modpk bb= coeffBound (Aeval, p);
if (bb.getk() > b.getk() ) b=bb;
bb= coeffBound (F, p);
if (bb.getk() > b.getk() ) b=bb;
}
else
{
A /= Lc (Aeval);
mipoHasDen= !bCommonDen(mipo).isOne();
mipo *= bCommonDen (mipo);
#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 (A*bCommonDen (A)));
// resultant, discriminant
fmpz_poly_resultant(FLINTf,FLINTmipo,FLINTLcf);
fmpz_poly_discriminant(FLINTD,FLINTmipo);
fmpz_mul(FLINTf,FLINTD,FLINTf);
// conversion
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 (A*bCommonDen (A)));
ZZ NTLf= resultant (NTLmipo, NTLLcf);
ZZ NTLD= discriminant (NTLmipo);
den= abs (convertZZ2CF (NTLD*NTLf));
#else
factoryError("NTL/FLINT missing: biFactorize");
#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());
}
A *= multiplier;
A *= bCommonDen (A);
Off (SW_RATIONAL);
int i= 0;
#ifdef HAVE_FLINT
CanonicalForm discMipo= convertFmpz2CF(FLINTD);
fmpz_clear(FLINTD);
#elif defined(HAVE_NTL)
CanonicalForm discMipo= convertZZ2CF (NTLD);
#else
factoryError("NTL/FLINT missing: biFactorize");
#endif
findGoodPrime (F*discMipo,i);
findGoodPrime (Aeval*discMipo,i);
findGoodPrime (A*discMipo,i);
int p=cf_getBigPrime(i);
b = coeffBound( A, p, mipo );
modpk bb= coeffBound (Aeval, p, mipo);
if (bb.getk() > b.getk() ) b=bb;
bb= coeffBound (F, p, mipo);
if (bb.getk() > b.getk() ) b=bb;
}
ExtensionInfo dummy= ExtensionInfo (false);
if (extension)
dummy= ExtensionInfo (v, false);
bool earlySuccess= false;
CFList earlyFactors;
TIMING_START (fac_bi_hensel_lift);
uniFactors= henselLiftAndEarly
(A, earlySuccess, earlyFactors, degs, liftBound,
uniFactors, dummy, evaluation, b, den);
TIMING_END_AND_PRINT (fac_bi_hensel_lift,
"time for bivariate hensel lifting over Q: ");
DEBOUTLN (cerr, "lifted factors= " << uniFactors);
CanonicalForm MODl= power (y, liftBound);
if (mipoHasDen)
{
Variable vv;
for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
if (hasFirstAlgVar (iter.getItem(), vv))
break;
for (CFListIterator iter= uniFactors; iter.hasItem(); iter++)
iter.getItem()= replacevar (iter.getItem(), vv, v);
//prune (vv);
}
On (SW_RATIONAL);
A *= bCommonDen (A);
Off (SW_RATIONAL);
TIMING_START (fac_bi_factor_recombination);
factors= factorRecombination (uniFactors, A, MODl, degs, evaluation, 1,
uniFactors.length()/2, b, den);
TIMING_END_AND_PRINT (fac_bi_factor_recombination,
"time for bivariate factor recombination over Q: ");
On (SW_RATIONAL);
if (earlySuccess)
factors= Union (earlyFactors, factors);
else if (!earlySuccess && degs.getLength() == 1)
factors= earlyFactors;
appendSwapDecompress (factors, conv (contentAxFactors),
conv (contentAyFactors), swap, swap2, N);
if (isOn (SW_RATIONAL))
normalize (factors);
return factors;
}
#endif
convertFmpz2CF
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
Definition FLINTconvert.cc:154
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
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
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
replacevar
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ).
Definition cf_ops.cc:271
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
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
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
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
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
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
irreducibilityTest
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
Definition cfNewtonPolygon.cc:1123
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
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
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
cf_assert.h
assertions for Factory
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
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
cf_getNumBigPrimes
int cf_getNumBigPrimes()
Definition cf_primes.cc:45
cf_primes.h
access to prime tables
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
igcd
int igcd(int a, int b)
Definition cf_util.cc:56
cf_util.h
f
FILE * f
Definition checklibs.c:9
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
DegreePattern
DegreePattern provides a functionality to create, intersect and refine degree patterns.
Definition DegreePattern.h:32
DegreePattern::intersect
void intersect(const DegreePattern &degPat)
intersect two degree patterns
Definition DegreePattern.cc:68
DegreePattern::getLength
int getLength() const
getter
Definition DegreePattern.h:86
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::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::getk
int getk() const
Definition fac_util.h:36
debug.h
functions to print debug output
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
result
return result
Definition facAbsBiFact.cc:76
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
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)
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
evalPoint
CanonicalForm evalPoint(const CanonicalForm &F, int &i)
Definition facBivar.cc:145
testPoint
bool testPoint(const CanonicalForm &F, CanonicalForm &G, int i)
Definition facBivar.cc:134
conv
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition facBivar.cc:126
biFactorize
CFList biFactorize(const CanonicalForm &F, const Variable &v)
Definition facBivar.cc:188
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
facBivar.h
bivariate factorization over Q(a)
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
Aeval
CFList *& Aeval
<[in] poly
Definition facFactorize.h:31
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
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
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
facFqBivar.h
This file provides functions for factorizing a bivariate polynomial over , or GF.
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
facHensel.h
This file defines functions for Hensel lifting.
facMul.h
This file defines functions for fast multiplication and division with remainder.
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
buf
int status int void * buf
Definition si_signals.h:69
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
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836