 |
My Project
UNKNOWN_GIT_VERSION
|
Go to the documentation of this file.
41 int M = 0,
i,
k =
f.level();
63 if (!
f.inBaseDomain() )
100 int M = 0,
i,
k =
f.level();
102 for (
i = 1;
i <=
k;
i++ )
130 result.append (
i.getItem().factor());
192 bool extension= (
v.
level() != 1);
203 if (
A.isUnivariate())
211 if (
result.getFirst().inCoeffDomain())
226 A=
A/(contentAx*contentAy);
227 CFFList contentAxFactors, contentAyFactors;
234 if (contentAxFactors.
getFirst().factor().inCoeffDomain())
240 if (contentAyFactors.
getFirst().factor().inCoeffDomain())
248 contentAxFactors=
factorize (contentAx,
true);
249 if (contentAxFactors.
getFirst().factor().inCoeffDomain())
254 contentAyFactors=
factorize (contentAy,
true);
255 if (contentAyFactors.
getFirst().factor().inCoeffDomain())
268 conv (contentAyFactors),
false,
false,
N);
276 if (
A.inCoeffDomain())
283 else if (
A.isUnivariate())
301 conv (contentAyFactors),
false,
false,
N);
314 CFList uniFactors, list, bufUniFactors;
319 CFList bufUniFactors2, list2, uniFactors2;
331 int evaluation, evaluation2, bufEvaluation= 0, bufEvaluation2= 0;
332 for (
int i= 0;
i < factorNums;
i++)
343 "time for eval point over Q in y: ");
352 "time for univariate factorization over Q: ");
353 DEBOUTLN (cerr,
"prod (bufUniFactors)== bufAeval " <<
354 (
prod (bufUniFactors) == bufAeval));
359 if (bufUniFactors.
length() == 1)
364 conv (contentAyFactors),
swap, swap2,
N);
377 "time for univariate factorization in y over Q: ");
378 DEBOUTLN (cerr,
"prod (bufuniFactors2)== bufAeval2 " <<
379 (
prod (bufUniFactors2) == bufAeval2));
383 if (bufUniFactors2.
length() == 1)
388 conv (contentAyFactors),
swap, swap2,
N);
401 if (subCheck > 1 && (subCheck1%subCheck == 0))
404 subst (bufA, bufA, subCheck,
x);
408 conv (contentAyFactors),
swap, swap2,
N);
419 if (subCheck > 1 && (subCheck2%subCheck == 0))
422 subst (bufA, bufA, subCheck,
y);
426 conv (contentAyFactors),
swap, swap2,
N);
442 uniFactors= bufUniFactors;
445 evaluation2= bufEvaluation2;
446 uniFactors2= bufUniFactors2;
455 uniFactors2= bufUniFactors2;
457 evaluation2= bufEvaluation2;
461 uniFactors= bufUniFactors;
466 if (bufEvaluation > 0)
469 bufEvaluation= -bufEvaluation + 1;
470 if (bufEvaluation > 0)
473 bufEvaluation2= -bufEvaluation2 + 1;
481 uniFactors= uniFactors2;
492 conv (contentAyFactors),
swap, swap2,
N);
504 bool mipoHasDen=
false;
514 printf (
"out of primes\n");
519 if (bb.
getk() >
b.getk() )
b=bb;
521 if (bb.
getk() >
b.getk() )
b=bb;
531 ZZ NTLD= discriminant (NTLmipo);
554 if (bb.
getk() >
b.getk() )
b=bb;
556 if (bb.
getk() >
b.getk() )
b=bb;
562 bool earlySuccess=
false;
566 (
A, earlySuccess, earlyFactors, degs, liftBound,
569 "time for bivariate hensel lifting over Q: ");
570 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
593 "time for bivariate factor recombination over Q: ");
598 factors=
Union (earlyFactors, factors);
599 else if (!earlySuccess && degs.
getLength() == 1)
600 factors= earlyFactors;
603 conv (contentAyFactors),
swap, swap2,
N);
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) modpk coeffBound(const CanonicalForm &f
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
static const int SW_RATIONAL
set to 1 for computations over Q
class to iterate through CanonicalForm's
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList const Variable & y
DegreePattern provides a functionality to create, intersect and refine degree patterns.
const CanonicalForm CFMap CFMap & N
bool testPoint(const CanonicalForm &F, CanonicalForm &G, int i)
int cf_getBigPrime(int i)
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
const CanonicalForm int const CFList & evaluation
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Rational abs(const Rational &a)
int status int void * buf
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...
TIMING_START(fac_alg_resultant)
CFList *& Aeval
<[in] poly
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern °s, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
void intersect(const DegreePattern °Pat)
intersect two degree patterns
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
declarations of higher level algorithms.
void prune(Variable &alpha)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
class to do operations mod p^k for int's p and k
int getLength() const
getter
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
factory's class for variables
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)
ExtensionInfo contains information about extension.
This file defines functions for Hensel lifting.
bivariate factorization over Q(a)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const Variable & v
< [in] a sqrfree bivariate poly
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
CFList biFactorize(const CanonicalForm &F, const Variable &v)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm evalPoint(const CanonicalForm &F, int &i)
bool irreducibilityTest(const CanonicalForm &F)
computes the Newton polygon of F and checks if it satisfies the irreducibility criterion from S....
functions to print debug output
This file defines functions for fast multiplication and division with remainder.
This file provides functions for factorizing a bivariate polynomial over , or GF.