![]() |
My Project
|
This file provides functions for factorizing a multivariate polynomial over
#include "timing.h"
#include "facFqBivar.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "facFqBivarUtil.h"
Go to the source code of this file.
Functions | |
TIMING_DEFINE_PRINT (fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F | |
Factorization over a finite field. | |
CFList | FpSqrfFactorize (const CanonicalForm &F) |
factorize a squarefree multivariate polynomial over ![]() | |
CFList | FqSqrfFactorize (const CanonicalForm &F, const Variable &alpha) |
factorize a squarefree multivariate polynomial over ![]() | |
CFList | GFSqrfFactorize (const CanonicalForm &F) |
factorize a squarefree multivariate polynomial over GF | |
CFFList | FpFactorize (const CanonicalForm &G, bool substCheck=true) |
factorize a multivariate polynomial over ![]() | |
CFFList | FqFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true) |
factorize a multivariate polynomial over ![]() | |
CFFList | GFFactorize (const CanonicalForm &G, bool substCheck=true) |
factorize a multivariate polynomial over GF | |
CFList | extFactorRecombination (const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation) |
Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations. | |
CFList | factorRecombination (const CanonicalForm &F, const CFList &factors, const CFList &M) |
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations. | |
CFList | recombination (const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x) |
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with factors2 | |
int | liftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound) |
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted. | |
int | extLiftBoundAdaption (const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound) |
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted. | |
CFList | earlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound) |
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted. | |
CFList | extEarlyFactorDetect (CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound) |
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted. | |
CFList | evalPoints (const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail) |
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials. | |
CFList | henselLiftAndEarly (CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info) |
hensel Lifting and early factor detection | |
CFList | extFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
Factorization over an extension of initial field. | |
CanonicalForm | lcmContent (const CanonicalForm &A, CFList &contentAi) |
compute the LCM of the contents of A wrt to each variable occuring in A. | |
CanonicalForm | myCompress (const CanonicalForm &F, CFMap &N) |
compress a polynomial s.t. ![]() | |
void | evaluationWRTDifferentSecondVars (CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A) |
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty | |
void | refineBiFactors (const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength) |
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible | |
CFList | buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y) |
plug in evalPoint for y in a list of polys | |
void | sortByUniFactors (CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation) |
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary | |
void | getLeadingCoeffs (const CanonicalForm &A, CFList *&Aeval) |
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables | |
void | prepareLeadingCoeffs (CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation) |
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly | |
CFList | leadingCoeffReconstruction (const CanonicalForm &F, const CFList &factors, const CFList &M) |
obtain factors of F by reconstructing their leading coeffs | |
CFList | distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length) |
distribute content | |
void | gcdFreeBasis (CFFList &factors1, CFFList &factors2) |
gcd free basis of two lists of factors | |
CFList | precomputeLeadingCoeff (const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y) |
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations. | |
void | changeSecondVariable (CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w) |
changes the second variable to be w and updates all relevant data | |
void | distributeLCmultiplier (CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler) |
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients | |
void | LCHeuristic (CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors) |
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors | |
void | LCHeuristicCheck (const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier) |
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true | |
void | LCHeuristic2 (const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier) |
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content | |
void | LCHeuristic3 (const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier) |
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. | |
void | LCHeuristic4 (const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier) |
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful. | |
Variables | |
const ExtensionInfo & | info |
< [in] sqrfree poly | |
This file provides functions for factorizing a multivariate polynomial over
Definition in file facFqFactorize.h.
CFList buildUniFactors | ( | const CFList & | biFactors, |
const CanonicalForm & | evalPoint, | ||
const Variable & | y ) |
plug in evalPoint for y in a list of polys
[in] | biFactors | a list of polys |
[in] | evalPoint | some evaluation point |
[in] | y | some variable |
Definition at line 2321 of file facFqFactorize.cc.
void changeSecondVariable | ( | CanonicalForm & | A, |
CFList & | biFactors, | ||
CFList & | evaluation, | ||
CFList *& | oldAeval, | ||
int | lengthAeval2, | ||
const CFList & | uniFactors, | ||
const Variable & | w ) |
changes the second variable to be w and updates all relevant data
A | [in,out] a multivariate poly | |
biFactors | [in,out] bivariate factors | |
evaluation | [in,out] evaluation point | |
oldAeval | [in,out] old bivariate factors wrt. different second vars | |
[in] | lengthAeval2 | length of oldAeval |
[in] | uniFactors | univariate factors |
[in] | w | some variable |
Definition at line 2544 of file facFqFactorize.cc.
distribute content
[in] | L | list of polys, first entry the content to be distributed |
[in] | differentSecondVarFactors | factorization wrt different second vars |
[in] | length | length ofdifferentSecondVarFactors |
Definition at line 1295 of file facFqFactorize.cc.
void distributeLCmultiplier | ( | CanonicalForm & | A, |
CFList & | leadingCoeffs, | ||
CFList & | biFactors, | ||
const CFList & | evaluation, | ||
const CanonicalForm & | LCmultipler ) |
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients
A | [in,out] some poly | |
leadingCoeffs | [in,out] leading coefficients | |
biFactors | [in,out] bivariate factors | |
[in] | evaluation | eval. point |
[in] | LCmultipler | multiplier |
Definition at line 2591 of file facFqFactorize.cc.
CFList earlyFactorDetect | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int & | adaptedLiftBound, | ||
bool & | success, | ||
const int | deg, | ||
const CFList & | MOD, | ||
const int | bound ) |
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.
F | [in,out] poly to be factored, returns poly divided by detected factors in case of success | |
factors | [in,out] list of factors lifted up to deg, returns a list of factors without detected factors | |
adaptedLiftBound | [in,out] adapted lift bound | |
success | [in,out] indicating success | |
[in] | deg | stage of Hensel lifting |
[in] | MOD | a list of powers of Variables |
[in] | bound | initial lift bound |
Definition at line 612 of file facFqFactorize.cc.
CFList evalPoints | ( | const CanonicalForm & | F, |
CFList & | eval, | ||
const Variable & | alpha, | ||
CFList & | list, | ||
const bool & | GF, | ||
bool & | fail ) |
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that the resulting univariate polynomial has main variable Variable (1), is squarefree and its degree coincides with degree(F) and the bivariate one is primitive wrt. Variable(1), and successively evaluated polynomials have the same degree in their main variable as F has, fails if there are no valid evaluation points, eval contains the intermediate evaluated polynomials.
[in] | F | a compressed poly |
eval | [in,out] an empty list, returns F successive evaluated | |
[in] | alpha | algebraic variable |
list | [in,out] a list of points already considered, a point is encoded as a poly of degree F.level()-1 in Variable(1) | |
[in] | GF | GF? |
fail | [in,out] indicates failure |
Definition at line 751 of file facFqFactorize.cc.
void evaluationWRTDifferentSecondVars | ( | CFList *& | Aeval, |
const CFList & | evaluation, | ||
const CanonicalForm & | A ) |
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different second variables. If this evaluation is valid (see evalPoints) then Aeval contains A successively evaluated at this point, otherwise this entry is empty
Aeval | [in,out] an array of length n-2 if variable at level i > 2 admits a valid evaluation this entry contains A successively evaluated at this point otherwise an empty list | |
[in] | evaluation | a valid evaluation point for main variable at level 1 and second variable at level 2 |
[in] | A | some poly |
Definition at line 1966 of file facFqFactorize.cc.
CFList extEarlyFactorDetect | ( | CanonicalForm & | F, |
CFList & | factors, | ||
int & | adaptedLiftBound, | ||
bool & | success, | ||
const ExtensionInfo & | info, | ||
const CFList & | eval, | ||
const int | deg, | ||
const CFList & | MOD, | ||
const int | bound ) |
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.
F | [in,out] poly to be factored, returns poly divided by detected factors in case of success | |
factors | [in,out] list of factors lifted up to deg, returns a list of factors without detected factors | |
adaptedLiftBound | [in,out] adapted lift bound | |
success | [in,out] indicating succes | |
[in] | info | info about extension |
[in] | eval | evaluation point |
[in] | deg | stage of Hensel lifting |
[in] | MOD | a list of powers of Variables |
[in] | bound | initial lift bound |
Definition at line 665 of file facFqFactorize.cc.
CFList extFactorize | ( | const CanonicalForm & | F, |
const ExtensionInfo & | info ) |
Factorization over an extension of initial field.
Factorization over an extension of initial field.
[in] | F | poly to be factored |
[in] | info | info about extension |
Definition at line 3661 of file facFqFactorize.cc.
CFList extFactorRecombination | ( | const CFList & | factors, |
const CanonicalForm & | F, | ||
const CFList & | M, | ||
const ExtensionInfo & | info, | ||
const CFList & | evaluation ) |
Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations.
[in] | factors | list of lifted factors that are monic wrt Variable (1) |
[in] | F | poly to be factored |
[in] | M | a list of powers of Variables |
[in] | info | info about extension |
[in] | evaluation | evaluation point |
Definition at line 216 of file facFqFactorize.cc.
int extLiftBoundAdaption | ( | const CanonicalForm & | F, |
const CFList & | factors, | ||
bool & | success, | ||
const ExtensionInfo & | info, | ||
const CFList & | eval, | ||
const int | deg, | ||
const CFList & | MOD, | ||
const int | bound ) |
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted.
[in] | F | a poly |
[in] | factors | list of list of lifted factors that are monic wrt |
success | [in,out] indicates that no further lifting is necessary | |
[in] | info | info about extension |
[in] | eval | evaluation point |
[in] | deg | stage of Hensel lifting |
[in] | MOD | a list of powers of Variables |
[in] | bound | initial lift bound |
Definition at line 514 of file facFqFactorize.cc.
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.
[in] | F | poly to be factored |
[in] | factors | list of lifted factors that are monic wrt Variable (1) |
[in] | M | a list of powers of Variables |
Definition at line 361 of file facFqFactorize.cc.
|
inline |
factorize a multivariate polynomial over
[in] | G | a multivariate poly |
[in] | substCheck | enables substitute check |
Definition at line 101 of file facFqFactorize.h.
|
inline |
factorize a squarefree multivariate polynomial over
[in] | F | a multivariate poly |
Definition at line 47 of file facFqFactorize.h.
|
inline |
factorize a multivariate polynomial over
[in] | G | a multivariate poly |
[in] | alpha | algebraic variable |
[in] | substCheck | enables substitute check |
Definition at line 184 of file facFqFactorize.h.
|
inline |
factorize a squarefree multivariate polynomial over
[in] | F | a multivariate poly |
[in] | alpha | algebraic variable |
Definition at line 64 of file facFqFactorize.h.
gcd free basis of two lists of factors
factors1 | [in,out] list of factors, returns gcd free factors |
factors2 | [in,out] list of factors, returns gcd free factors |
Definition at line 1269 of file facFqFactorize.cc.
void getLeadingCoeffs | ( | const CanonicalForm & | A, |
CFList *& | Aeval ) |
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables
[in] | A | some poly |
Aeval | [in,out] array of bivariate factors, returns the leading coefficients of these factors |
Definition at line 2233 of file facFqFactorize.cc.
|
inline |
factorize a multivariate polynomial over GF
[in] | G | a multivariate poly |
[in] | substCheck | enables substitute check |
Definition at line 267 of file facFqFactorize.h.
|
inline |
factorize a squarefree multivariate polynomial over GF
[in] | F | a multivariate poly |
Definition at line 82 of file facFqFactorize.h.
CFList henselLiftAndEarly | ( | CanonicalForm & | A, |
CFList & | MOD, | ||
int *& | liftBounds, | ||
bool & | earlySuccess, | ||
CFList & | earlyFactors, | ||
const CFList & | Aeval, | ||
const CFList & | biFactors, | ||
const CFList & | evaluation, | ||
const ExtensionInfo & | info ) |
hensel Lifting and early factor detection
A | [in,out] poly to be factored, returns poly divided by detected factors, in case of success | |
MOD | [in,out] a list of powers of Variables | |
liftBounds | [in,out] initial lift bounds, returns adapted lift bounds | |
earlySuccess | [in,out] indicating success | |
earlyFactors | [in,out] early factors | |
[in] | Aeval | A successively evaluated at elements of evaluation |
[in] | biFactors | bivariate factors |
[in] | evaluation | evaluation point |
[in] | info | info about extension |
Definition at line 985 of file facFqFactorize.cc.
void LCHeuristic | ( | CanonicalForm & | A, |
const CanonicalForm & | LCmultiplier, | ||
CFList & | biFactors, | ||
CFList *& | leadingCoeffs, | ||
const CFList * | oldAeval, | ||
int | lengthAeval, | ||
const CFList & | evaluation, | ||
const CFList & | oldBiFactors ) |
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors
A | [in,out] a poly | |
LCmultiplier | [in,out] divisor of LC (A,1) | |
biFactors | [in,out] bivariate factors | |
leadingCoeffs | [in,out] leading coeffs | |
[in] | oldAeval | bivariate factors wrt. different second vars |
[in] | lengthAeval | length of oldAeval |
[in] | evaluation | evaluation point |
[in] | oldBiFactors | bivariate factors without LCmultiplier distributed on them |
Definition at line 2615 of file facFqFactorize.cc.
void LCHeuristic2 | ( | const CanonicalForm & | LCmultiplier, |
const CFList & | factors, | ||
CFList & | leadingCoeffs, | ||
CFList & | contents, | ||
CFList & | LCs, | ||
bool & | foundTrueMultiplier ) |
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
[in] | LCmultiplier | divisor of LC (A,1) |
[in] | factors | result of LucksWangSparseHeuristic |
leadingCoeffs | [in,out] leading coeffs | |
contents | [in,out] content of factors | |
LCs | [in,out] LC of factors divided by content of factors | |
foundTrueMultiplier | [in,out] success? |
Definition at line 2779 of file facFqFactorize.cc.
void LCHeuristic3 | ( | const CanonicalForm & | LCmultiplier, |
const CFList & | factors, | ||
const CFList & | oldBiFactors, | ||
const CFList & | contents, | ||
const CFList * | oldAeval, | ||
CanonicalForm & | A, | ||
CFList *& | leadingCoeffs, | ||
int | lengthAeval, | ||
bool & | foundMultiplier ) |
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic.
[in] | LCmultiplier | divisor of LC (A,1) |
[in] | factors | result of LucksWangSparseHeuristic |
[in] | oldBiFactors | bivariate factors without LCmultiplier distributed on them |
[in] | contents | content of factors |
[in] | oldAeval | bivariate factors wrt. different second vars |
A | [in,out] poly | |
leadingCoeffs | [in,out] leading coeffs | |
[in] | lengthAeval | length of oldAeval |
foundMultiplier | [in,out] success? |
Definition at line 2809 of file facFqFactorize.cc.
void LCHeuristic4 | ( | const CFList & | oldBiFactors, |
const CFList * | oldAeval, | ||
const CFList & | contents, | ||
const CFList & | factors, | ||
const CanonicalForm & | testVars, | ||
int | lengthAeval, | ||
CFList *& | leadingCoeffs, | ||
CanonicalForm & | A, | ||
CanonicalForm & | LCmultiplier, | ||
bool & | foundMultiplier ) |
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of contents divide LCmultiplier. Assumes LCHeuristic3 is run before it and was successful.
[in] | oldBiFactors | bivariate factors without LCmultiplier distributed on them |
[in] | oldAeval | bivariate factors wrt. different second vars |
[in] | contents | content of factors |
[in] | factors | result of LucksWangSparseHeuristic |
[in] | testVars | product of second vars that occur among oldAeval |
[in] | lengthAeval | length of oldAeval |
leadingCoeffs | [in,out] leading coeffs | |
A | [in,out] poly | |
LCmultiplier | [in,out] divisor of LC (A,1) | |
[in] | foundMultiplier | success? |
Definition at line 2857 of file facFqFactorize.cc.
void LCHeuristicCheck | ( | const CFList & | LCs, |
const CFList & | contents, | ||
CanonicalForm & | A, | ||
const CanonicalForm & | oldA, | ||
CFList & | leadingCoeffs, | ||
bool & | foundTrueMultiplier ) |
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents, sets A to oldA and sets foundTrueMultiplier to true
[in] | LCs | leading coeffs computed |
[in] | contents | content of factors |
A | [in,out] oldA*LCmultiplier^m | |
[in] | oldA | some poly |
leadingCoeffs | [in,out] leading coefficients | |
foundTrueMultiplier | [in,out] success? |
Definition at line 2763 of file facFqFactorize.cc.
CanonicalForm lcmContent | ( | const CanonicalForm & | A, |
CFList & | contentAi ) |
compute the LCM of the contents of A wrt to each variable occuring in A.
[in] | A | a compressed multivariate poly |
contentAi | [in,out] an empty list, returns a list of the contents of A wrt to each variable occuring in A starting from A.mvar(). |
Definition at line 966 of file facFqFactorize.cc.
CFList leadingCoeffReconstruction | ( | const CanonicalForm & | F, |
const CFList & | factors, | ||
const CFList & | M ) |
obtain factors of F by reconstructing their leading coeffs
[in] | F | poly to be factored |
[in] | factors | factors of f monic wrt Variable (1) |
[in] | M | a list of powers of Variables |
int liftBoundAdaption | ( | const CanonicalForm & | F, |
const CFList & | factors, | ||
bool & | success, | ||
const int | deg, | ||
const CFList & | MOD, | ||
const int | bound ) |
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
[in] | F | a poly |
[in] | factors | list of list of lifted factors that are monic wrt Variable (1) |
success | [in,out] indicates that no further lifting is necessary | |
[in] | deg | stage of Hensel lifting |
[in] | MOD | a list of powers of Variables |
[in] | bound | initial lift bound |
Definition at line 448 of file facFqFactorize.cc.
CanonicalForm myCompress | ( | const CanonicalForm & | F, |
CFMap & | N ) |
compress a polynomial s.t.
[in] | F | a poly |
N | [in,out] a map to decompress |
Definition at line 134 of file facFqFactorize.cc.
CFList precomputeLeadingCoeff | ( | const CanonicalForm & | LCF, |
const CFList & | LCFFactors, | ||
const Variable & | alpha, | ||
const CFList & | evaluation, | ||
CFList *& | differentSecondVarLCs, | ||
int | lSecondVarLCs, | ||
Variable & | y ) |
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
[in] | LCF | a multivariate poly |
[in] | LCFFactors | a list of univariate factors of LCF of level 2 |
[in] | alpha | algebraic var. |
[in] | evaluation | an evaluation point having lSecondVarLCs+1 components |
[in] | differentSecondVarLCs | LCs of factors of f wrt different second variables |
[in] | lSecondVarLCs | length of the above |
y | [in,out] if y.level() is not 1 on output the second variable has been changed to y |
Definition at line 1479 of file facFqFactorize.cc.
void prepareLeadingCoeffs | ( | CFList *& | LCs, |
CanonicalForm & | A, | ||
CFList & | Aeval, | ||
int | n, | ||
const CFList & | leadingCoeffs, | ||
const CFList & | biFactors, | ||
const CFList & | evaluation ) |
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in K^(n-2) equal the leading coeffs wrt Variable(1) of bivariate factors and change A and Aeval accordingly
LCs | [in,out] | |
A | [in,out] | |
Aeval | [in,out] | |
[in] | n | level of poly to be factored |
[in] | leadingCoeffs | precomputed leading coeffs |
[in] | biFactors | bivariate factors |
[in] | evaluation | evaluation point |
Definition at line 2382 of file facFqFactorize.cc.
CFList recombination | ( | const CFList & | factors1, |
const CFList & | factors2, | ||
int | s, | ||
int | thres, | ||
const CanonicalForm & | evalPoint, | ||
const Variable & | x ) |
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with factors2
[in] | factors1 | list of bivariate factors |
[in] | factors2 | list univariate factors |
[in] | s | algorithm starts checking subsets of size s |
[in] | thres | threshold for the size of subsets which are checked |
[in] | evalPoint | evaluation point |
[in] | x | second variable of bivariate factors |
Definition at line 2114 of file facFqFactorize.cc.
void refineBiFactors | ( | const CanonicalForm & | A, |
CFList & | biFactors, | ||
CFList *const & | factors, | ||
const CFList & | evaluation, | ||
int | minFactorsLength ) |
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
[in] | A | some poly |
biFactors | [in,out] list of bivariate to be refined, returns refined factors | |
[in] | factors | list of bivariate factorizations of A wrt different second variables |
[in] | evaluation | the evaluation point |
[in] | minFactorsLength | the minimal number of factors |
Definition at line 2335 of file facFqFactorize.cc.
void sortByUniFactors | ( | CFList *& | Aeval, |
int | AevalLength, | ||
CFList & | uniFactors, | ||
CFList & | biFactors, | ||
const CFList & | evaluation ) |
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary
Aeval | [in,out] array of bivariate factors | |
[in] | AevalLength | length of Aeval |
uniFactors | [in,out] univariate factors | |
biFactors | [in,out] bivariate factors | |
[in] | evaluation | evaluation point |
Definition at line 2251 of file facFqFactorize.cc.
TIMING_DEFINE_PRINT | ( | fac_fq_squarefree | ) | const & |
Factorization over a finite field.
const ExtensionInfo& info |