![]() |
My Project
|
This file provides functions for factorizing a bivariate polynomial over ,
or GF, based on "Modern Computer
Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring
multivariate polynomials over a finite field" by L.
More...
#include "config.h"
#include "cf_assert.h"
#include "cf_util.h"
#include "debug.h"
#include "timing.h"
#include "canonicalform.h"
#include "cf_defs.h"
#include "cf_map_ext.h"
#include "cf_random.h"
#include "facHensel.h"
#include "facMul.h"
#include "cf_map.h"
#include "cf_irred.h"
#include "facFqBivarUtil.h"
#include "facFqBivar.h"
#include "cfNewtonPolygon.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
#include "flint/nmod_poly_factor.h"
#include "flint/fq_nmod_poly_factor.h"
Go to the source code of this file.
Functions | |
TIMING_DEFINE_PRINT (fac_fq_uni_factorizer) TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_bi_evaluation) TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_logarithmic) TIMING_DEFINE_PRINT(fac_fq_compute_lattice_lift) TIMING_DEFINE_PRINT(fac_fq_till_reduced) TIMING_DEFINE_PRINT(fac_fq_reconstruction) TIMING_DEFINE_PRINT(fac_fq_lift) TIMING_DEFINE_PRINT(fac_fq_uni_total) CanonicalForm prodMod0(const CFList &L | |
else | if (L.length()==1) return mod(L.getFirst()(0 |
else L | getLast ()(0 |
for (int j=1;j<=l;j++, i++) tmp1.append(i.getItem()) | |
return | mod (mulNTL(buf1, buf2, b), 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 ![]() | |
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 is even special GF2 routines of NTL are used. More... | |
CFList | extFactorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &N, const ExtensionInfo &info, DegreePattern °s, const CanonicalForm &eval, int s, int thres) |
naive factor recombination as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin. More... | |
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 L Bernardin. More... | |
Variable | chooseExtension (const Variable &alpha, const Variable &beta, int k) |
chooses a field extension. More... | |
void | earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, int deg, const CanonicalForm &eval, const modpk &b, CanonicalForm &den) |
void | earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, int deg, const CanonicalForm &eval, const modpk &b) |
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More... | |
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 tested. Lift bound and possible degree pattern are updated. More... | |
int * | getCombinations (int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC) |
int * | getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC) |
compute lifting precisions from the shape of the Newton polygon of F More... | |
void | deleteFactors (CFList &factors, int *factorsFoundIndex) |
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 More... | |
CFList | henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval) |
hensel Lifting and early factor detection More... | |
long | isReduced (const mat_zz_p &M) |
long | isReduced (const nmod_mat_t M) |
long | isReduced (const mat_zz_pE &M) |
int * | extractZeroOneVecs (const mat_zz_p &M) |
int * | extractZeroOneVecs (const nmod_mat_t M) |
int * | extractZeroOneVecs (const mat_zz_pE &M) |
void | reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres) |
void | reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, const CanonicalForm &eval, bool beenInThres) |
void | reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, const CanonicalForm &eval, bool beenInThres) |
CFList | reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval) |
CFList | monicReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N) |
CFList | extReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const ExtensionInfo &info, const CanonicalForm &evaluation) |
CFList | extReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const ExtensionInfo &info, const CanonicalForm &evaluation) |
CFList | reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const CanonicalForm &eval) |
CFList | reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const CanonicalForm &eval) |
void | extReconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation) |
void | extReconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation) |
int | liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible) |
int | liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible) |
int | extLiftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
int | extLiftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
int | liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_pE &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible) |
int | liftAndComputeLatticeFq2Fp (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha) |
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval) |
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &, int precision, const CanonicalForm &eval) |
CFList | extIncreasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision) |
CFList | increasePrecision2 (const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision) |
CFList | increasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval) |
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const CanonicalForm &eval) |
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, mat_zz_pE &NTLN, const CanonicalForm &eval) |
CFList | extIncreasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
CFList | increasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const Variable &alpha, const CanonicalForm &eval) |
CFList | furtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval) |
CFList | furtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, mat_zz_pE &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval) |
CFList | extFurtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
CFList | furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval) |
void | refineAndRestartLift (const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant) |
void | refineAndRestartLift (const CanonicalForm &F, const mat_zz_pE &NTLN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant) |
CFList | earlyReconstructionAndLifting (const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation) |
CFList | earlyReconstructionAndLifting (const CanonicalForm &F, const mat_zz_pE &N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation) |
CFList | extEarlyReconstructionAndLifting (const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation) |
CFList | sieveSmallFactors (const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval) |
CFList | extSieveSmallFactors (const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info) |
CFList | henselLiftAndLatticeRecombi (const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval) |
ExtensionInfo | init4ext (const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo) |
CFList | extHenselLiftAndLatticeRecombi (const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval) |
CFList | extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
Factorization over an extension of initial field. More... | |
CFList | biFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
bivariate factorization over finite fields as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin. More... | |
Variables | |
const CanonicalForm & | M |
const CanonicalForm const modpk & | b |
else | |
CFListIterator | i = L |
CFList | tmp1 |
CFList | tmp2 = Difference (L, tmp1) |
CanonicalForm | buf1 = prodMod0 (tmp1, M, b) |
CanonicalForm | buf2 = prodMod0 (tmp2, M, b) |
This file provides functions for factorizing a bivariate polynomial over ,
or GF, based on "Modern Computer
Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring
multivariate polynomials over a finite field" by L.
Bernardin. Factor Recombination is described in "Factoring polynomials over global fields" by K. Belabas, M. van Hoeij, J. Klueners, A. Steel
Definition in file facFqBivar.cc.
CFList biFactorize | ( | const CanonicalForm & | F, |
const ExtensionInfo & | info | ||
) |
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a finite field" by L Bernardin.
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.
[in] | F | a sqrfree bivariate poly |
[in] | info | information about extension |
Definition at line 8305 of file facFqBivar.cc.
chooses a field extension.
[in] | alpha | some algebraic variable |
[in] | beta | some algebraic variable |
[in] | k | some int |
Definition at line 808 of file facFqBivar.cc.
void deleteFactors | ( | CFList & | factors, |
int * | factorsFoundIndex | ||
) |
Definition at line 1138 of file facFqBivar.cc.
void earlyFactorDetection | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
CFList & | factors, | ||
int & | adaptedLiftBound, | ||
int *& | factorsFoundIndex, | ||
DegreePattern & | degs, | ||
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 tested. Lift bound and possible degree pattern are updated.
[in,out] | reconstructedFactors | list of reconstructed factors |
[in,out] | F | poly to be factored, returns poly divided by detected factors in case of success |
[in,out] | factors | list of factors lifted up to deg, returns a list of factors without detected factors |
[in,out] | adaptedLiftBound | adapted lift bound |
[in,out] | factorsFoundIndex | factors already considered |
[in,out] | degs | degree pattern, is updated whenever we find a factor |
[in,out] | success | indicating success |
[in] | deg | stage of Hensel lifting |
[in] | eval | evaluation point |
[in] | b | coeff bound |
Definition at line 973 of file facFqBivar.cc.
void earlyFactorDetection | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
CFList & | factors, | ||
int & | adaptedLiftBound, | ||
int *& | factorsFoundIndex, | ||
DegreePattern & | degs, | ||
bool & | success, | ||
int | deg, | ||
const CanonicalForm & | eval, | ||
const modpk & | b, | ||
CanonicalForm & | den | ||
) |
Definition at line 854 of file facFqBivar.cc.
CFList earlyReconstructionAndLifting | ( | const CanonicalForm & | F, |
const mat_zz_pE & | N, | ||
CanonicalForm & | bufF, | ||
CFList & | factors, | ||
int & | l, | ||
int & | factorsFound, | ||
bool | beenInThres, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFList & | diophant, | ||
bool | symmetric, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 6421 of file facFqBivar.cc.
CFList earlyReconstructionAndLifting | ( | const CanonicalForm & | F, |
const nmod_mat_t | N, | ||
CanonicalForm & | bufF, | ||
CFList & | factors, | ||
int & | l, | ||
int & | factorsFound, | ||
bool | beenInThres, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFList & | diophant, | ||
bool | symmetric, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 6207 of file facFqBivar.cc.
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 .
[in] | F | compressed, bivariate poly |
[in,out] | eval | F (p, y) |
[in] | alpha | algebraic variable |
[in] | list | list of points already considered |
[in] | GF | GaloisFieldDomain? |
[in,out] | fail | equals true, if there is no valid evaluation point |
Definition at line 86 of file facFqBivar.cc.
CFList extBiFactorize | ( | const CanonicalForm & | F, |
const ExtensionInfo & | info | ||
) |
Factorization over an extension of initial field.
[in] | F | poly to be factored |
[in] | info | info about extension |
Definition at line 8930 of file facFqBivar.cc.
void extEarlyFactorDetection | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
CFList & | factors, | ||
int & | adaptedLiftBound, | ||
int *& | factorsFoundIndex, | ||
DegreePattern & | degs, | ||
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 tested. Lift bound and possible degree pattern are updated.
[in,out] | reconstructedFactors | list of reconstructed factors |
[in,out] | F | poly to be factored, returns poly divided by detected factors in case of success |
[in,out] | factors | list of factors lifted up to deg, returns a list of factors without detected factors |
[in,out] | adaptedLiftBound | adapted lift bound |
[in,out] | factorsFoundIndex | factors already considered |
[in,out] | degs | degree pattern, is updated whenever we find a factor |
[in,out] | success | indicating success |
[in] | info | information about extension |
[in] | eval | evaluation point |
[in] | deg | stage of Hensel lifting |
Definition at line 984 of file facFqBivar.cc.
CFList extEarlyReconstructionAndLifting | ( | const CanonicalForm & | F, |
const nmod_mat_t | N, | ||
CanonicalForm & | bufF, | ||
CFList & | factors, | ||
int & | l, | ||
int & | factorsFound, | ||
bool | beenInThres, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFList & | diophant, | ||
const ExtensionInfo & | info, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 6581 of file facFqBivar.cc.
CFList extFactorRecombination | ( | CFList & | factors, |
CanonicalForm & | F, | ||
const CanonicalForm & | N, | ||
const ExtensionInfo & | info, | ||
DegreePattern & | degs, | ||
const CanonicalForm & | eval, | ||
int | s, | ||
int | thres | ||
) |
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by L Bernardin.
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.
[in,out] | factors | list of lifted factors that are monic wrt Variable (1), original factors-factors found |
[in,out] | F | poly to be factored, F/factors found |
[in] | N | Variable (2)^liftBound |
[in] | info | contains information about extension |
[in] | eval | evaluation point |
[in] | s | algorithm starts checking subsets of size s |
[in] | thres | threshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2 |
Definition at line 372 of file facFqBivar.cc.
CFList extFurtherLiftingAndIncreasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | l, | ||
int | liftBound, | ||
int | d, | ||
int * | bounds, | ||
nmod_mat_t | FLINTN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
const CanonicalForm & | evaluation, | ||
const ExtensionInfo & | info, | ||
CFList & | source, | ||
CFList & | dest | ||
) |
Definition at line 5559 of file facFqBivar.cc.
CFList extHenselLiftAndLatticeRecombi | ( | const CanonicalForm & | G, |
const CFList & | uniFactors, | ||
const ExtensionInfo & | extInfo, | ||
const DegreePattern & | degPat, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 7714 of file facFqBivar.cc.
CFList extIncreasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | factorsFound, | ||
int | oldNumCols, | ||
int | oldL, | ||
const CanonicalForm & | evaluation, | ||
const ExtensionInfo & | info, | ||
CFList & | source, | ||
CFList & | dest, | ||
int | precision | ||
) |
Definition at line 3828 of file facFqBivar.cc.
CFList extIncreasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | oldL, | ||
int | l, | ||
int | d, | ||
int * | bounds, | ||
CFArray & | bufQ, | ||
nmod_mat_t | FLINTN, | ||
const CanonicalForm & | evaluation, | ||
const ExtensionInfo & | info, | ||
CFList & | source, | ||
CFList & | dest | ||
) |
Definition at line 4758 of file facFqBivar.cc.
int extLiftAndComputeLattice | ( | const CanonicalForm & | F, |
int * | bounds, | ||
int | sizeBounds, | ||
int | liftBound, | ||
int | minBound, | ||
int | start, | ||
CFList & | factors, | ||
mat_zz_p & | NTLN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
bool & | irreducible, | ||
const CanonicalForm & | evaluation, | ||
const ExtensionInfo & | info, | ||
CFList & | source, | ||
CFList & | dest | ||
) |
Definition at line 2751 of file facFqBivar.cc.
int extLiftAndComputeLattice | ( | const CanonicalForm & | F, |
int * | bounds, | ||
int | sizeBounds, | ||
int | liftBound, | ||
int | minBound, | ||
int | start, | ||
CFList & | factors, | ||
nmod_mat_t | FLINTN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
bool & | irreducible, | ||
const CanonicalForm & | evaluation, | ||
const ExtensionInfo & | info, | ||
CFList & | source, | ||
CFList & | dest | ||
) |
Definition at line 2950 of file facFqBivar.cc.
int * extractZeroOneVecs | ( | const mat_zz_p & | M | ) |
Definition at line 1527 of file facFqBivar.cc.
int * extractZeroOneVecs | ( | const mat_zz_pE & | M | ) |
Definition at line 1579 of file facFqBivar.cc.
int * extractZeroOneVecs | ( | const nmod_mat_t | M | ) |
Definition at line 1553 of file facFqBivar.cc.
CFList extReconstruction | ( | CanonicalForm & | G, |
CFList & | factors, | ||
int * | zeroOneVecs, | ||
int | precision, | ||
const mat_zz_p & | N, | ||
const ExtensionInfo & | info, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 1962 of file facFqBivar.cc.
CFList extReconstruction | ( | CanonicalForm & | G, |
CFList & | factors, | ||
int * | zeroOneVecs, | ||
int | precision, | ||
const nmod_mat_t | N, | ||
const ExtensionInfo & | info, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 2043 of file facFqBivar.cc.
void extReconstructionTry | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
const CFList & | factors, | ||
const int | liftBound, | ||
int & | factorsFound, | ||
int *& | factorsFoundIndex, | ||
mat_zz_p & | N, | ||
bool | beenInThres, | ||
const ExtensionInfo & | info, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 2226 of file facFqBivar.cc.
void extReconstructionTry | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
const CFList & | factors, | ||
const int | liftBound, | ||
int & | factorsFound, | ||
int *& | factorsFoundIndex, | ||
nmod_mat_t | N, | ||
bool | beenInThres, | ||
const ExtensionInfo & | info, | ||
const CanonicalForm & | evaluation | ||
) |
Definition at line 2356 of file facFqBivar.cc.
CFList extSieveSmallFactors | ( | const CanonicalForm & | G, |
CFList & | uniFactors, | ||
DegreePattern & | degPat, | ||
CanonicalForm & | H, | ||
CFList & | diophant, | ||
CFArray & | Pi, | ||
CFMatrix & | M, | ||
bool & | success, | ||
int | d, | ||
const CanonicalForm & | evaluation, | ||
const ExtensionInfo & | info | ||
) |
Definition at line 6811 of file facFqBivar.cc.
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 "Factoring multivariate polynomials over a finite field" by L Bernardin.
naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
[in,out] | factors | list of lifted factors that are monic wrt Variable (1) |
[in,out] | F | poly to be factored |
[in] | N | Variable (2)^liftBound |
[in] | degs | degree pattern |
[in] | eval | evaluation point |
[in] | s | algorithm starts checking subsets of size s |
[in] | thres | threshold for the size of subsets which are checked, for a full factor recombination choose thres= factors.length()/2 |
[in] | b | coeff bound |
[in] | den | bound on the den if over Q (a) |
Definition at line 588 of file facFqBivar.cc.
CFList furtherLiftingAndIncreasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | l, | ||
int | liftBound, | ||
int | d, | ||
int * | bounds, | ||
mat_zz_pE & | NTLN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 5411 of file facFqBivar.cc.
CFList furtherLiftingAndIncreasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | l, | ||
int | liftBound, | ||
int | d, | ||
int * | bounds, | ||
nmod_mat_t | FLINTN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 5176 of file facFqBivar.cc.
CFList furtherLiftingAndIncreasePrecisionFq2Fp | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | l, | ||
int | liftBound, | ||
int | d, | ||
int * | bounds, | ||
nmod_mat_t | FLINTN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
const Variable & | alpha, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 5875 of file facFqBivar.cc.
int * getCombinations | ( | int * | rightSide, |
int | sizeOfRightSide, | ||
int & | sizeOfOutput, | ||
int | degreeLC | ||
) |
Definition at line 1083 of file facFqBivar.cc.
else L getLast | ( | ) |
int * getLiftPrecisions | ( | const CanonicalForm & | F, |
int & | sizeOfOutput, | ||
int | degreeLC | ||
) |
compute lifting precisions from the shape of the Newton polygon of F
[in] | F | a bivariate poly |
[in,out] | sizeOfOutput | size of the output |
[in] | degreeLC | degree of the leading coeff [in] of F wrt. Variable (1) |
Definition at line 1122 of file facFqBivar.cc.
CFList henselLiftAndEarly | ( | CanonicalForm & | A, |
bool & | earlySuccess, | ||
CFList & | earlyFactors, | ||
DegreePattern & | degs, | ||
int & | liftBound, | ||
const CFList & | uniFactors, | ||
const ExtensionInfo & | info, | ||
const CanonicalForm & | eval | ||
) |
hensel Lifting and early factor detection
[in,out] | A | poly to be factored, returns poly divided by detected factors in case of success |
[in,out] | earlySuccess | indicating success |
[in,out] | earlyFactors | list of factors detected at early stage of Hensel lifting |
[in,out] | degs | degree pattern |
[in,out] | liftBound | (adapted) lift bound |
[in] | uniFactors | univariate factors |
[in] | info | information about extension |
[in] | eval | evaluation point |
Definition at line 1457 of file facFqBivar.cc.
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
[in,out] | A | poly to be factored, returns poly divided by detected factors in case of success |
[in,out] | earlySuccess | indicating success |
[in,out] | earlyFactors | list of factors detected at early stage of Hensel lifting |
[in,out] | degs | degree pattern |
[in,out] | liftBound | (adapted) lift bound |
[in] | uniFactors | univariate factors |
[in] | info | information about extension |
[in] | eval | evaluation point |
[in] | b | coeff bound |
[in] | den | bound on the den if over Q(a) |
Definition at line 1154 of file facFqBivar.cc.
CFList henselLiftAndLatticeRecombi | ( | const CanonicalForm & | G, |
const CFList & | uniFactors, | ||
const Variable & | alpha, | ||
const DegreePattern & | degPat, | ||
bool | symmetric, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 6861 of file facFqBivar.cc.
else if | ( | L. | length() = = 1 | ) |
CFList increasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | factorsFound, | ||
int | oldNumCols, | ||
int | oldL, | ||
const Variable & | , | ||
int | precision, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 3686 of file facFqBivar.cc.
CFList increasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | factorsFound, | ||
int | oldNumCols, | ||
int | oldL, | ||
int | precision, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 3477 of file facFqBivar.cc.
CFList increasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | oldL, | ||
int | l, | ||
int | d, | ||
int * | bounds, | ||
CFArray & | bufQ, | ||
mat_zz_pE & | NTLN, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 4649 of file facFqBivar.cc.
CFList increasePrecision | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | oldL, | ||
int | l, | ||
int | d, | ||
int * | bounds, | ||
CFArray & | bufQ, | ||
nmod_mat_t | FLINTN, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 4480 of file facFqBivar.cc.
CFList increasePrecision2 | ( | const CanonicalForm & | F, |
CFList & | factors, | ||
const Variable & | alpha, | ||
int | precision | ||
) |
Definition at line 4136 of file facFqBivar.cc.
CFList increasePrecisionFq2Fp | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | factorsFound, | ||
int | oldNumCols, | ||
int | oldL, | ||
const Variable & | alpha, | ||
int | precision, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 4269 of file facFqBivar.cc.
CFList increasePrecisionFq2Fp | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int | oldL, | ||
int | l, | ||
int | d, | ||
int * | bounds, | ||
CFArray & | bufQ, | ||
nmod_mat_t | FLINTN, | ||
const Variable & | alpha, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 5016 of file facFqBivar.cc.
ExtensionInfo init4ext | ( | const ExtensionInfo & | info, |
const CanonicalForm & | evaluation, | ||
int & | degMipo | ||
) |
Definition at line 7659 of file facFqBivar.cc.
long isReduced | ( | const mat_zz_p & | M | ) |
Definition at line 1470 of file facFqBivar.cc.
long isReduced | ( | const mat_zz_pE & | M | ) |
Definition at line 1508 of file facFqBivar.cc.
long isReduced | ( | const nmod_mat_t | M | ) |
Definition at line 1489 of file facFqBivar.cc.
int liftAndComputeLattice | ( | const CanonicalForm & | F, |
int * | bounds, | ||
int | sizeBounds, | ||
int | start, | ||
int | liftBound, | ||
int | minBound, | ||
CFList & | factors, | ||
mat_zz_p & | NTLN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
bool & | irreducible | ||
) |
Definition at line 2487 of file facFqBivar.cc.
int liftAndComputeLattice | ( | const CanonicalForm & | F, |
int * | bounds, | ||
int | sizeBounds, | ||
int | start, | ||
int | liftBound, | ||
int | minBound, | ||
CFList & | factors, | ||
mat_zz_pE & | NTLN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
bool & | irreducible | ||
) |
Definition at line 3159 of file facFqBivar.cc.
int liftAndComputeLattice | ( | const CanonicalForm & | F, |
int * | bounds, | ||
int | sizeBounds, | ||
int | start, | ||
int | liftBound, | ||
int | minBound, | ||
CFList & | factors, | ||
nmod_mat_t | FLINTN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
bool & | irreducible | ||
) |
Definition at line 2612 of file facFqBivar.cc.
int liftAndComputeLatticeFq2Fp | ( | const CanonicalForm & | F, |
int * | bounds, | ||
int | sizeBounds, | ||
int | start, | ||
int | liftBound, | ||
int | minBound, | ||
CFList & | factors, | ||
nmod_mat_t | FLINTN, | ||
CFList & | diophant, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFArray & | bufQ, | ||
bool & | irreducible, | ||
const Variable & | alpha | ||
) |
Definition at line 3294 of file facFqBivar.cc.
CFList monicReconstruction | ( | CanonicalForm & | G, |
CFList & | factors, | ||
int * | zeroOneVecs, | ||
int | precision, | ||
const mat_zz_pE & | N | ||
) |
Definition at line 1909 of file facFqBivar.cc.
CFList reconstruction | ( | CanonicalForm & | G, |
CFList & | factors, | ||
int * | zeroOneVecs, | ||
int | precision, | ||
const mat_zz_p & | N, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 2124 of file facFqBivar.cc.
CFList reconstruction | ( | CanonicalForm & | G, |
CFList & | factors, | ||
int * | zeroOneVecs, | ||
int | precision, | ||
const mat_zz_pE & | N, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 1858 of file facFqBivar.cc.
CFList reconstruction | ( | CanonicalForm & | G, |
CFList & | factors, | ||
int * | zeroOneVecs, | ||
int | precision, | ||
const nmod_mat_t | N, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 2175 of file facFqBivar.cc.
void reconstructionTry | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
const CFList & | factors, | ||
const int | liftBound, | ||
int & | factorsFound, | ||
int *& | factorsFoundIndex, | ||
mat_zz_p & | N, | ||
const CanonicalForm & | eval, | ||
bool | beenInThres | ||
) |
Definition at line 1690 of file facFqBivar.cc.
void reconstructionTry | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
const CFList & | factors, | ||
const int | liftBound, | ||
int & | factorsFound, | ||
int *& | factorsFoundIndex, | ||
mat_zz_pE & | N, | ||
const CanonicalForm & | eval, | ||
bool | beenInThres | ||
) |
Definition at line 1606 of file facFqBivar.cc.
void reconstructionTry | ( | CFList & | reconstructedFactors, |
CanonicalForm & | F, | ||
const CFList & | factors, | ||
const int | liftBound, | ||
int & | factorsFound, | ||
int *& | factorsFoundIndex, | ||
nmod_mat_t | N, | ||
const CanonicalForm & | eval, | ||
bool | beenInThres | ||
) |
Definition at line 1774 of file facFqBivar.cc.
void refineAndRestartLift | ( | const CanonicalForm & | F, |
const mat_zz_pE & | NTLN, | ||
int | liftBound, | ||
int | l, | ||
CFList & | factors, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFList & | diophant | ||
) |
void refineAndRestartLift | ( | const CanonicalForm & | F, |
const nmod_mat_t | FLINTN, | ||
int | liftBound, | ||
int | l, | ||
CFList & | factors, | ||
CFMatrix & | M, | ||
CFArray & | Pi, | ||
CFList & | diophant | ||
) |
CFList sieveSmallFactors | ( | const CanonicalForm & | G, |
CFList & | uniFactors, | ||
DegreePattern & | degPat, | ||
CanonicalForm & | H, | ||
CFList & | diophant, | ||
CFArray & | Pi, | ||
CFMatrix & | M, | ||
bool & | success, | ||
int | d, | ||
const CanonicalForm & | eval | ||
) |
Definition at line 6764 of file facFqBivar.cc.
TIMING_DEFINE_PRINT | ( | fac_fq_uni_factorizer | ) | const & |
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used.
[in] | A | squarefree univariate poly |
[in] | alpha | algebraic variable |
[in] | GF | GaloisFieldDomain? |
Definition at line 162 of file facFqBivar.cc.
else L b |
Definition at line 62 of file facFqBivar.cc.
else |
Definition at line 70 of file facFqBivar.cc.
CFListIterator i = L |
Definition at line 73 of file facFqBivar.cc.
else L M |
Definition at line 62 of file facFqBivar.cc.
CFList tmp1 |
Definition at line 74 of file facFqBivar.cc.
tmp2 = Difference (L, tmp1) |
Definition at line 74 of file facFqBivar.cc.