 |
My Project
debian-1:4.1.1-p2+ds-4
|
Go to the documentation of this file.
14 #ifndef FAC_FQ_BIVAR_H
15 #define FAC_FQ_BIVAR_H
34 static const double log2exp= 1.442695041;
59 F /= (contentX*contentY);
60 CFFList contentXFactors, contentYFactors;
73 CFList bufContentX, bufContentY;
82 if (contentXFactors.
getFirst().factor().inCoeffDomain())
84 if (contentYFactors.
getFirst().factor().inCoeffDomain())
90 result.append (
N (
i.getItem().factor()));
92 result.append (
N (
i.getItem().factor()));
97 mpz_t *
M=
new mpz_t [4];
103 mpz_t * S=
new mpz_t [2];
112 result.append (
N(
i.getItem().factor()));
114 result.append (
N (
i.getItem().factor()));
168 "GF as base field expected");
181 bool substCheck=
true
190 bool foundOne=
false;
195 if (substDegree [
i-1] > 1)
210 tmp2=
i.getItem().factor();
213 if (substDegree[
j-1] > 1)
220 j.getItem().exp()*
i.getItem().exp()));
232 F /= (contentX*contentY);
233 CFFList contentXFactors, contentYFactors;
236 if (contentXFactors.
getFirst().factor().inCoeffDomain())
238 if (contentYFactors.
getFirst().factor().inCoeffDomain())
250 mpz_t *
M=
new mpz_t [4];
256 mpz_t * S=
new mpz_t [2];
265 "time for bivariate sqrf factors over Fp: ");
274 "time to factor bivariate sqrf factors over Fp: ");
275 for (
i= bufResult;
i.hasItem();
i++)
307 bool substCheck=
true
316 bool foundOne=
false;
321 if (substDegree [
i-1] > 1)
336 tmp2=
i.getItem().factor();
339 if (substDegree[
j-1] > 1)
346 j.getItem().exp()*
i.getItem().exp()));
358 F /= (contentX*contentY);
359 CFFList contentXFactors, contentYFactors;
362 if (contentXFactors.
getFirst().factor().inCoeffDomain())
364 if (contentYFactors.
getFirst().factor().inCoeffDomain())
377 mpz_t *
M=
new mpz_t [4];
383 mpz_t * S=
new mpz_t [2];
392 "time for bivariate sqrf factors over Fq: ");
401 "time to factor bivariate sqrf factors over Fq: ");
402 for (
i= bufResult;
i.hasItem();
i++)
433 bool substCheck=
true
437 "GF as base field expected");
444 bool foundOne=
false;
449 if (substDegree [
i-1] > 1)
464 tmp2=
i.getItem().factor();
467 if (substDegree[
j-1] > 1)
474 j.getItem().exp()*
i.getItem().exp()));
486 F /= (contentX*contentY);
487 CFFList contentXFactors, contentYFactors;
490 if (contentXFactors.
getFirst().factor().inCoeffDomain())
492 if (contentYFactors.
getFirst().factor().inCoeffDomain())
505 mpz_t *
M=
new mpz_t [4];
511 mpz_t * S=
new mpz_t [2];
520 "time for bivariate sqrf factors over GF: ");
529 "time to factor bivariate sqrf factors over GF: ");
530 for (
i= bufResult;
i.hasItem();
i++)
666 CFList& reconstructedFactors,
674 int& adaptedLiftBound,
675 int*& factorsFoundIndex,
691 CFList& reconstructedFactors,
699 int& adaptedLiftBound,
700 int*& factorsFoundIndex,
int getGFDegree() const
getter
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
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.
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 .
const CanonicalForm CFMap CFMap & N
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
#define GaloisFieldDomain
#define ASSERT(expression, message)
TIMING_START(fac_alg_resultant)
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 ...
TIMING_DEFINE_PRINT(fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
static const double log2exp
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
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...
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
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
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
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
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 GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const CanonicalForm int s
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
Variable getAlpha() const
getter
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
const ExtensionInfo & info
< [in] sqrfree poly
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
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...