14 #ifndef FAC_FQ_BIVAR_H
15 #define FAC_FQ_BIVAR_H
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;
191 int * substDegree=
new int [F.
level()];
195 if (substDegree [
i-1] > 1)
210 tmp2=
i.getItem().factor();
213 if (substDegree[
j-1] > 1)
220 j.getItem().exp()*
i.getItem().exp()));
223 delete [] substDegree;
226 delete [] substDegree;
232 F /= (contentX*contentY);
233 CFFList contentXFactors, contentYFactors;
236 if (contentXFactors.
getFirst().factor().inCoeffDomain())
238 if (contentYFactors.
getFirst().factor().inCoeffDomain())
245 result=
Union (contentXFactors, contentYFactors);
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++)
280 result=
Union (result, contentXFactors);
281 result=
Union (result, contentYFactors);
307 bool substCheck=
true
316 bool foundOne=
false;
317 int * substDegree=
new int [F.
level()];
321 if (substDegree [
i-1] > 1)
336 tmp2=
i.getItem().factor();
339 if (substDegree[
j-1] > 1)
346 j.getItem().exp()*
i.getItem().exp()));
349 delete [] substDegree;
352 delete [] substDegree;
358 F /= (contentX*contentY);
359 CFFList contentXFactors, contentYFactors;
360 contentXFactors=
factorize (contentX, alpha);
361 contentYFactors=
factorize (contentY, alpha);
362 if (contentXFactors.
getFirst().factor().inCoeffDomain())
364 if (contentYFactors.
getFirst().factor().inCoeffDomain())
371 result=
Union (contentXFactors, contentYFactors);
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++)
407 result=
Union (result, contentXFactors);
408 result=
Union (result, contentYFactors);
433 bool substCheck=
true
437 "GF as base field expected");
444 bool foundOne=
false;
445 int * substDegree=
new int [F.
level()];
449 if (substDegree [
i-1] > 1)
464 tmp2=
i.getItem().factor();
467 if (substDegree[
j-1] > 1)
474 j.getItem().exp()*
i.getItem().exp()));
477 delete [] substDegree;
480 delete [] substDegree;
486 F /= (contentX*contentY);
487 CFFList contentXFactors, contentYFactors;
490 if (contentXFactors.
getFirst().factor().inCoeffDomain())
492 if (contentYFactors.
getFirst().factor().inCoeffDomain())
499 result=
Union (contentXFactors, contentYFactors);
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++)
535 result=
Union (result, contentXFactors);
536 result=
Union (result, contentYFactors);
666 CFList& reconstructedFactors,
674 int& adaptedLiftBound,
675 int*& factorsFoundIndex,
691 CFList& reconstructedFactors,
699 int& adaptedLiftBound,
700 int*& factorsFoundIndex,
const CanonicalForm int s
DegreePattern provides a functionality to create, intersect and refine degree patterns.
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
This file provides functions to compute the Newton polygon of a bivariate polynomial.
#define TIMING_END_AND_PRINT(t, msg)
factory's class for variables
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
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 FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
static const double log2exp
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
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 getAlpha() const
getter
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
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 .
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
This file provides functions for squarefrees factorizing over , or GF.
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
ExtensionInfo contains information about extension.
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped ...
TIMING_DEFINE_PRINT(fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp
int getGFDegree() const
getter
const CanonicalForm CFMap CFMap & N
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 FpBiFactorize(const CanonicalForm &G, 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
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
This file provides utility functions for bivariate factorization.
#define GaloisFieldDomain
This file provides a class to handle degree patterns.
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
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...
#define ASSERT(expression, message)
operations mod p^k and some other useful functions for factorization
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. 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.
class to do operations mod p^k for int's p and k
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...
This file provides a class to store information about finite fields and extensions thereof...