35static const double log2exp= 1.442695041;
37#if defined(HAVE_NTL) || defined(HAVE_FLINT)
61 F /= (contentX*contentY);
62 CFFList contentXFactors, contentYFactors;
63 if (
info.getAlpha().level() != 1)
68 else if (
info.getAlpha().level() == 1 &&
info.getGFDegree() == 1)
73 else if (
info.getAlpha().level() == 1 &&
info.getGFDegree() != 1)
75 CFList bufContentX, bufContentY;
84 if (contentXFactors.
getFirst().factor().inCoeffDomain())
86 if (contentYFactors.
getFirst().factor().inCoeffDomain())
92 result.append (
N (
i.getItem().factor()));
94 result.append (
N (
i.getItem().factor()));
99 mpz_t *
M=
new mpz_t [4];
105 mpz_t * S=
new mpz_t [2];
114 result.append (
N(
i.getItem().factor()));
116 result.append (
N (
i.getItem().factor()));
176 "GF as base field expected");
191 bool substCheck=
true
200 bool foundOne=
false;
205 if (substDegree [
i-1] > 1)
220 tmp2=
i.getItem().factor();
223 if (substDegree[
j-1] > 1)
230 j.getItem().exp()*
i.getItem().exp()));
242 F /= (contentX*contentY);
243 CFFList contentXFactors, contentYFactors;
246 if (contentXFactors.
getFirst().factor().inCoeffDomain())
248 if (contentYFactors.
getFirst().factor().inCoeffDomain())
260 mpz_t *
M=
new mpz_t [4];
266 mpz_t * S=
new mpz_t [2];
275 "time for bivariate sqrf factors over Fp: ");
284 "time to factor bivariate sqrf factors over Fp: ");
285 for (
i= bufResult;
i.hasItem();
i++)
319 bool substCheck=
true
328 bool foundOne=
false;
333 if (substDegree [
i-1] > 1)
348 tmp2=
i.getItem().factor();
351 if (substDegree[
j-1] > 1)
358 j.getItem().exp()*
i.getItem().exp()));
370 F /= (contentX*contentY);
371 CFFList contentXFactors, contentYFactors;
374 if (contentXFactors.
getFirst().factor().inCoeffDomain())
376 if (contentYFactors.
getFirst().factor().inCoeffDomain())
389 mpz_t *
M=
new mpz_t [4];
395 mpz_t * S=
new mpz_t [2];
404 "time for bivariate sqrf factors over Fq: ");
413 "time to factor bivariate sqrf factors over Fq: ");
414 for (
i= bufResult;
i.hasItem();
i++)
447 bool substCheck=
true
451 "GF as base field expected");
458 bool foundOne=
false;
463 if (substDegree [
i-1] > 1)
478 tmp2=
i.getItem().factor();
481 if (substDegree[
j-1] > 1)
488 j.getItem().exp()*
i.getItem().exp()));
500 F /= (contentX*contentY);
501 CFFList contentXFactors, contentYFactors;
504 if (contentXFactors.
getFirst().factor().inCoeffDomain())
506 if (contentYFactors.
getFirst().factor().inCoeffDomain())
519 mpz_t *
M=
new mpz_t [4];
525 mpz_t * S=
new mpz_t [2];
534 "time for bivariate sqrf factors over GF: ");
543 "time to factor bivariate sqrf factors over GF: ");
544 for (
i= bufResult;
i.hasItem();
i++)
681 CFList& reconstructedFactors,
689 int& adaptedLiftBound,
690 int*& factorsFoundIndex,
706 CFList& reconstructedFactors,
714 int& adaptedLiftBound,
715 int*& factorsFoundIndex,
This file provides a class to handle degree patterns.
This file provides a class to store information about finite fields and extensions thereof.
const CanonicalForm CFMap CFMap & N
static const double log2exp
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
This file provides functions to compute the Newton polygon of a bivariate polynomial.
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
#define ASSERT(expression, message)
#define GaloisFieldDomain
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
DegreePattern provides a functionality to create, intersect and refine degree patterns.
ExtensionInfo contains information about extension.
factory's class for variables
class to do operations mod p^k for int's p and k
const CanonicalForm int s
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
This file provides utility functions for bivariate factorization.
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, 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...
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern °s, 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.
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
CFList extFactorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &M, const ExtensionInfo &info, DegreePattern °s, const CanonicalForm &eval, int s, int thres)
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude c...
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
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 .
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 GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
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 ...
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
void earlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, 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...
This file provides functions for squarefrees factorizing over , or GF.
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
operations mod p^k and some other useful functions for factorization
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)