 |
My Project
UNKNOWN_GIT_VERSION
|
Go to the source code of this file.
|
| TIMING_DEFINE_PRINT (fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F |
| Factorization over a finite field. More...
|
|
CFList | FpSqrfFactorize (const CanonicalForm &F) |
| factorize a squarefree multivariate polynomial over More...
|
|
CFList | FqSqrfFactorize (const CanonicalForm &F, const Variable &alpha) |
| factorize a squarefree multivariate polynomial over More...
|
|
CFList | GFSqrfFactorize (const CanonicalForm &F) |
| factorize a squarefree multivariate polynomial over GF More...
|
|
CFFList | FpFactorize (const CanonicalForm &G, bool substCheck=true) |
| factorize a multivariate polynomial over More...
|
|
CFFList | FqFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true) |
| factorize a multivariate polynomial over More...
|
|
CFFList | GFFactorize (const CanonicalForm &G, bool substCheck=true) |
| factorize a multivariate polynomial over GF More...
|
|
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. More...
|
|
CFList | factorRecombination (const CanonicalForm &F, const CFList &factors, const CFList &M) |
| Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations. More...
|
|
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 More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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 More...
|
|
CFList | extFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
| Factorization over an extension of initial field. More...
|
|
CanonicalForm | lcmContent (const CanonicalForm &A, CFList &contentAi) |
| compute the LCM of the contents of A wrt to each variable occuring in A. More...
|
|
CanonicalForm | myCompress (const CanonicalForm &F, CFMap &N) |
| compress a polynomial s.t. and no gaps between the variables occur More...
|
|
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 More...
|
|
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 More...
|
|
CFList | buildUniFactors (const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y) |
| plug in evalPoint for y in a list of polys More...
|
|
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 More...
|
|
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 More...
|
|
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 More...
|
|
CFList | leadingCoeffReconstruction (const CanonicalForm &F, const CFList &factors, const CFList &M) |
| obtain factors of F by reconstructing their leading coeffs More...
|
|
CFList | distributeContent (const CFList &L, const CFList *differentSecondVarFactors, int length) |
| distribute content More...
|
|
void | gcdFreeBasis (CFFList &factors1, CFFList &factors2) |
| gcd free basis of two lists of factors More...
|
|
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. More...
|
|
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 More...
|
|
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 More...
|
|
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 More...
|
|
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 More...
|
|
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 More...
|
|
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. More...
|
|
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. More...
|
|
This file provides functions for factorizing a multivariate polynomial over
,
or GF.
- Author
- Martin Lee
Definition in file facFqFactorize.h.
◆ buildUniFactors()
plug in evalPoint for y in a list of polys
- Returns
- returns a list of the evaluated polys, these evaluated polys are made monic
- Parameters
-
[in] | biFactors | [in] a list of polys |
[in] | evalPoint | [in] some evaluation point |
[in] | y | [in] some variable |
Definition at line 2304 of file facFqFactorize.cc.
◆ changeSecondVariable()
changes the second variable to be w and updates all relevant data
- Parameters
-
[in,out] | A | [in,out] a multivariate poly |
[in,out] | biFactors | [in,out] bivariate factors |
[in,out] | evaluation | [in,out] evaluation point |
[in,out] | oldAeval | [in,out] old bivariate factors wrt. different second vars |
[in] | lengthAeval2 | [in] length of oldAeval |
[in] | uniFactors | [in] univariate factors |
[in] | w | [in] some variable |
Definition at line 2527 of file facFqFactorize.cc.
2546 for (
i= 0;
i < lengthAeval2;
i++)
2548 if (oldAeval[
i].isEmpty())
2553 oldAeval[
i]= biFactors;
2556 for (
int ii= 0; ii < tmp.
size(); ii++)
2560 for (
int ii= 0; ii < tmp.
size(); ii++)
2567 for (
int j= 0;
j <
tmp2.size();
j++)
◆ distributeContent()
distribute content
- Returns
- returns a list result of polys such that prod (result)= prod (L) but the first entry of L may be (partially) factorized and these factors are distributed onto other entries in L
- Parameters
-
[in] | L | [in] list of polys, first entry the content to be distributed |
[in] | differentSecondVarFactors | [in] factorization wrt different second vars |
[in] | length | [in] length ofdifferentSecondVarFactors |
Definition at line 1281 of file facFqFactorize.cc.
1291 if (
l.length() == 1)
1296 if (differentSecondVarFactors[
i].isEmpty())
1300 result= differentSecondVarFactors[
i];
1310 iter1.
getItem() *= iter2.getItem();
1325 if (differentSecondVarFactors[
i].isEmpty())
1331 for (iter2= differentSecondVarFactors[
i]; iter2.
hasItem();
1334 if (iter2.
getItem().inCoeffDomain())
1346 if (!
g.inCoeffDomain())
1359 for (iter2= multiplier; iter2.
hasItem(); iter1++, iter2++)
◆ distributeLCmultiplier()
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading coefficients
- Parameters
-
[in,out] | A | [in,out] some poly |
[in,out] | leadingCoeffs | [in,out] leading coefficients |
[in,out] | biFactors | [in,out] bivariate factors |
[in] | evaluation | [in] eval. point |
[in] | LCmultipler | [in] multiplier |
Definition at line 2574 of file facFqFactorize.cc.
2585 for (
int i=
A.level();
i > 2;
i--,
iter++)
2591 i.getItem() *= tmp/
LC (
i.getItem(), 1);
2592 i.getItem() /=
Lc (
i.getItem());
◆ earlyFactorDetect()
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.
- Returns
- earlyFactorDetect returns a list of factors of F (possibly incomplete), in case of success. Otherwise an empty list.
- See also
- factorRecombination(), extEarlyFactorDetect()
- Parameters
-
[in,out] | F | [in,out] poly to be factored, returns poly divided by detected factors in case of success |
[in,out] | factors | [in,out] list of factors lifted up to deg, returns a list of factors without detected factors |
[in,out] | adaptedLiftBound | [in,out] adapted lift bound |
[in,out] | success | [in,out] indicating success |
[in] | deg | [in] stage of Hensel lifting |
[in] | MOD | [in] a list of powers of Variables |
[in] | bound | [in] initial lift bound |
Definition at line 605 of file facFqFactorize.cc.
639 if (adaptedLiftBound < deg)
641 if (adaptedLiftBound <
degree (F) + 1)
644 adaptedLiftBound=
tmin (e + 1, deg);
646 adaptedLiftBound= deg;
◆ evalPoints()
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.
- Returns
- evalPoints returns an evaluation point, which is valid if and only if fail == false.
- Parameters
-
[in] | F | [in] a compressed poly |
[in,out] | eval | [in,out] an empty list, returns F successive evaluated |
[in] | alpha | [in] algebraic variable |
[in,out] | 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 | [in] GF? |
[in,out] | fail | [in,out] indicates failure |
Definition at line 740 of file facFqFactorize.cc.
795 for (
int i= 0;
i <
k;
i++)
807 result.append (genAlgExt.generate());
816 if (
find (list, random))
831 if (!
find (list, random))
841 if (!
find (list, random))
856 if (!
find (list, random))
868 if (!
find (list, random))
880 if (!
find (list, random))
891 if (!
find (list, random))
904 }
while (
find (list, random));
◆ evaluationWRTDifferentSecondVars()
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
- Parameters
-
[in,out] | 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 | [in] a valid evaluation point for main variable at level 1 and second variable at level 2 |
[in] | A | [in] some poly |
Definition at line 1950 of file facFqFactorize.cc.
1956 bool preserveDegree=
true;
1959 for (
int i=
A.level();
i > 2;
i--)
1964 preserveDegree=
true;
1966 for (
j=
A.level();
j > 1;
j--,
iter++)
1974 if ((
degree (tmp,
i) != degAi) ||
1975 (
degree (tmp, 1) != degA1))
1977 preserveDegree=
false;
1982 if (!
content(tmp,1).inCoeffDomain())
1983 preserveDegree=
false;
1984 if (!
content(tmp).inCoeffDomain())
1985 preserveDegree=
false;
1986 if (!(
gcd (
deriv (tmp,
x), tmp)).inCoeffDomain())
1987 preserveDegree=
false;
◆ extEarlyFactorDetect()
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound is adapted.
- Returns
- extEarlyFactorDetect returns a list of factors of F (possibly incomplete), whose shift to zero is reversed, in case of success. Otherwise an empty list.
- See also
- factorRecombination(), earlyFactorDetection()
- Parameters
-
[in,out] | F | [in,out] poly to be factored, returns poly divided by detected factors in case of success |
[in,out] | factors | [in,out] list of factors lifted up to deg, returns a list of factors without detected factors |
[in,out] | adaptedLiftBound | [in,out] adapted lift bound |
[in,out] | success | [in,out] indicating succes |
[in] | info | [in] info about extension |
[in] | eval | [in] evaluation point |
[in] | deg | [in] stage of Hensel lifting |
[in] | MOD | [in] a list of powers of Variables |
[in] | bound | [in] initial lift bound |
Definition at line 656 of file facFqFactorize.cc.
722 if (adaptedLiftBound < deg)
724 if (adaptedLiftBound <
degree (F) + 1)
727 adaptedLiftBound=
tmin (e + 1, deg);
729 adaptedLiftBound= deg;
◆ extFactorize()
Factorization over an extension of initial field.
- Returns
- extFactorize returns factorization of F over initial field
- See also
- extBiFactorize(), multiFactorize()
Factorization over an extension of initial field.
Definition at line 3640 of file facFqFactorize.cc.
3656 bool extension=
true;
3677 else if (
p >= 7 &&
p*
p < (1<<16))
3701 else if (!GF && (
alpha !=
w))
3719 bool primFail=
false;
3722 ASSERT (!primFail,
"failure in integer factorizer");
3739 bool primFail=
false;
3741 ASSERT (!primFail,
"failure in integer factorizer");
3763 bool extension=
true;
3767 if (
pow ((
double)
p, (
double) extensionDeg) < (1<<16))
3793 if (
pow ((
double)
p, (
double) 2*extensionDeg) < (1<<16))
3809 bool primFail=
false;
◆ extFactorRecombination()
Naive factor recombination for multivariate factorization over an extension of the initial field. No precomputed is used to exclude combinations.
- Returns
- extFactorRecombination returns a list of factors of F, whose shift to zero is reversed.
- See also
- factorRecombination()
- Parameters
-
[in] | factors | [in] list of lifted factors that are monic wrt Variable (1) |
[in] | F | [in] poly to be factored |
[in] | M | [in] a list of powers of Variables |
[in] | info | [in] info about extension |
[in] | evaluation | [in] evaluation point |
Definition at line 217 of file facFqFactorize.cc.
227 if (factors.
length() == 1)
251 int *
v=
new int [
T.length()];
252 for (
int i= 0;
i <
T.length();
i++)
254 bool noSubset=
false;
258 bool trueFactor=
false;
259 while (
T.length() >= 2*
s)
261 while (noSubset ==
false)
322 if (
T.length() < 2*
s ||
T.length() ==
s)
338 if (
T.length() < 2*
s ||
T.length() ==
s)
345 for (
int i= 0;
i <
T.length();
i++)
349 if (
T.length() < 2*
s)
◆ extLiftBoundAdaption()
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but only the lift bound is adapted.
- Returns
- liftBoundAdaption returns an adapted lift bound.
- See also
- earlyFactorDetect(), earlyFactorDetection()
- Parameters
-
[in] | F | [in] a poly |
[in] | factors | [in] list of list of lifted factors that are monic wrt |
[in,out] | success | [in,out] indicates that no further lifting is necessary |
[in] | info | [in] info about extension |
[in] | eval | [in] evaluation point |
[in] | deg | [in] stage of Hensel lifting |
[in] | MOD | [in] a list of powers of Variables |
[in] | bound | [in] initial lift bound |
Definition at line 509 of file facFqFactorize.cc.
518 int adaptedLiftBound= 0;
569 if (adaptedLiftBound < deg)
571 if (adaptedLiftBound <
degree (F) + 1)
577 adaptedLiftBound= deg;
583 if (e + 1 <
degree (F) + 1)
584 adaptedLiftBound= deg;
586 adaptedLiftBound= e + 1;
592 adaptedLiftBound= deg;
601 return adaptedLiftBound;
◆ factorRecombination()
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinations.
- Returns
- factorRecombination returns a list of factors of F
- See also
- extFactorRecombination()
- Parameters
-
[in] | F | [in] poly to be factored |
[in] | factors | [in] list of lifted factors that are monic wrt Variable (1) |
[in] | M | [in] a list of powers of Variables |
Definition at line 360 of file facFqFactorize.cc.
363 if (factors.
length() == 1)
376 int *
v=
new int [
T.length()];
377 for (
int i= 0;
i <
T.length();
i++)
379 bool noSubset=
false;
385 while (
T.length() >= 2*
s)
387 while (noSubset ==
false)
415 if (
T.length() < 2*
s ||
T.length() ==
s)
427 if (
T.length() < 2*
s ||
T.length() ==
s)
433 for (
int i= 0;
i <
T.length();
i++)
437 if (
T.length() < 2*
s)
◆ FpFactorize()
factorize a multivariate polynomial over
- Returns
- FpFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
- See also
- FqFactorize(), GFFactorize()
- Parameters
-
[in] | G | [in] a multivariate poly |
[in] | substCheck | [in] enables substitute check |
Definition at line 101 of file facFqFactorize.h.
111 bool foundOne=
false;
118 if (substDegree [
i-1] > 1)
125 substDegree[
i-1]= -1;
136 tmp2=
i.getItem().factor();
137 for (
int j= 1;
j <=
G.level();
j++)
139 if (substDegree[
j-1] > 1)
146 j.getItem().exp()*
i.getItem().exp()));
160 "time for squarefree factorization over Fq: ");
170 "time to factorize sqrfree factor over Fq: ");
171 for (
i= bufResult;
i.hasItem();
i++)
◆ FpSqrfFactorize()
factorize a squarefree multivariate polynomial over
- Returns
- FpSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
- See also
- FqSqrfFactorize(), GFSqrfFactorize()
- Parameters
-
[in] | F | [in] a multivariate poly |
Definition at line 47 of file facFqFactorize.h.
◆ FqFactorize()
factorize a multivariate polynomial over
- Returns
- FqFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
- See also
- FpFactorize(), GFFactorize()
- Parameters
-
[in] | G | [in] a multivariate poly |
[in] | alpha | [in] algebraic variable |
[in] | substCheck | [in] enables substitute check |
Definition at line 184 of file facFqFactorize.h.
195 bool foundOne=
false;
202 if (substDegree [
i-1] > 1)
209 substDegree[
i-1]= -1;
220 tmp2=
i.getItem().factor();
221 for (
int j= 1;
j <=
G.level();
j++)
223 if (substDegree[
j-1] > 1)
230 j.getItem().exp()*
i.getItem().exp()));
243 "time for squarefree factorization over Fq: ");
253 "time to factorize sqrfree factor over Fq: ");
254 for (
i= bufResult;
i.hasItem();
i++)
◆ FqSqrfFactorize()
factorize a squarefree multivariate polynomial over
- Returns
- FqSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
- See also
- FpSqrfFactorize(), GFSqrfFactorize()
- Parameters
-
[in] | F | [in] a multivariate poly |
[in] | alpha | [in] algebraic variable |
Definition at line 64 of file facFqFactorize.h.
◆ gcdFreeBasis()
gcd free basis of two lists of factors
- Parameters
-
[in,out] | factors1 | [in,out] list of factors, returns gcd free factors |
[in,out] | factors2 | [in,out] list of factors, returns gcd free factors |
Definition at line 1255 of file facFqFactorize.cc.
1268 g=
gcd (
i.getItem().factor(),
j.getItem().factor());
1271 j.getItem()=
CFFactor (
j.getItem().factor()/
g,
j.getItem().exp());
1272 i.getItem()=
CFFactor (
i.getItem().factor()/
g,
i.getItem().exp());
◆ getLeadingCoeffs()
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A wrt different second variables
- Parameters
-
[in] | A | [in] some poly |
[in,out] | Aeval | [in,out] array of bivariate factors, returns the leading coefficients of these factors |
Definition at line 2216 of file facFqFactorize.cc.
2221 for (
int j= 0;
j <
A.level() - 2;
j++)
◆ GFFactorize()
factorize a multivariate polynomial over GF
- Returns
- GFFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
- See also
- FpFactorize(), FqFactorize()
- Parameters
-
[in] | G | [in] a multivariate poly |
[in] | substCheck | [in] enables substitute check |
Definition at line 267 of file facFqFactorize.h.
272 "GF as base field expected");
279 bool foundOne=
false;
286 if (substDegree [
i-1] > 1)
293 substDegree[
i-1]= -1;
304 tmp2=
i.getItem().factor();
305 for (
int j= 1;
j <=
G.level();
j++)
307 if (substDegree[
j-1] > 1)
314 j.getItem().exp()*
i.getItem().exp()));
333 for (
i= bufResult;
i.hasItem();
i++)
◆ GFSqrfFactorize()
factorize a squarefree multivariate polynomial over GF
- Returns
- GFSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
- See also
- FpSqrfFactorize(), FqSqrfFactorize()
- Parameters
-
[in] | F | [in] a multivariate poly |
Definition at line 82 of file facFqFactorize.h.
86 "GF as base field expected");
◆ henselLiftAndEarly()
hensel Lifting and early factor detection
- Returns
- henselLiftAndEarly returns monic (wrt Variable (1)) lifted factors without factors which have been detected at an early stage of Hensel lifting
- See also
- earlyFactorDetectn(), extEarlyFactorDetect()
- Parameters
-
[in,out] | A | [in,out] poly to be factored, returns poly divided by detected factors, in case of success |
[in,out] | MOD | [in,out] a list of powers of Variables |
[in,out] | liftBounds | [in,out] initial lift bounds, returns adapted lift bounds |
[in,out] | earlySuccess | [in,out] indicating success |
[in,out] | earlyFactors | [in,out] early factors |
[in] | Aeval | [in] A successively evaluated at elements of evaluation |
[in] | biFactors | [in] bivariate factors |
[in] | evaluation | [in] evaluation point |
[in] | info | [in] info about extension |
Definition at line 972 of file facFqFactorize.cc.
978 CFList bufFactors= biFactors;
985 int smallFactorDeg= 11;
987 int adaptedLiftBound= 0;
988 int liftBound= liftBounds[1];
991 CFList earlyReconstFactors;
997 if (smallFactorDeg >= liftBound)
1001 else if (smallFactorDeg >=
degree (
buf) + 1)
1009 (
buf,
result, adaptedLiftBound, earlySuccess,
1013 (
buf,
result, adaptedLiftBound, earlySuccess,
1015 (
buf) + 1, MOD, liftBound);
1030 liftBounds[1]= adaptedLiftBound;
1031 liftBound= adaptedLiftBound;
1033 Pi, diophant, Mat, MOD);
1036 liftBounds[1]= adaptedLiftBound;
1038 else if (smallFactorDeg <
degree (
buf) + 1)
1040 liftBounds[1]= smallFactorDeg;
1046 earlySuccess, smallFactorDeg, MOD,
1051 smallFactorDeg, MOD, liftBound);
1057 smallFactorDeg, MOD, liftBound);
1068 Pi, diophant, Mat, MOD);
1095 liftBounds[1]= adaptedLiftBound;
1096 liftBound= adaptedLiftBound;
1098 Pi, diophant, Mat, MOD);
1101 liftBounds[1]= adaptedLiftBound;
1104 liftBounds[1]= adaptedLiftBound;
1117 for (
int i= 2;
i <= liftBoundsLength &&
j.hasItem();
i++,
j++)
1119 earlySuccess=
false;
1122 liftBound= liftBounds[
i];
1126 if (smallFactorDeg >= liftBound)
1128 liftBounds[
i - 1], liftBounds[
i]);
1129 else if (smallFactorDeg >=
degree (
buf) + 1)
1138 (
buf,
result, adaptedLiftBound, earlySuccess,
1142 (
buf,
result, adaptedLiftBound, earlySuccess,
1150 + 1, MOD, liftBound);
1160 liftBounds[
i]= adaptedLiftBound;
1161 liftBound= adaptedLiftBound;
1163 Pi, diophant, Mat, MOD);
1167 liftBounds[
i]= adaptedLiftBound;
1170 else if (smallFactorDeg <
degree (
buf) + 1)
1173 liftBounds[
i - 1], smallFactorDeg);
1179 (
buf,
result, adaptedLiftBound, earlySuccess,
1180 smallFactorDeg, MOD, liftBound);
1183 (
buf,
result, adaptedLiftBound, earlySuccess,
1191 smallFactorDeg, MOD, liftBound);
1195 smallFactorDeg, MOD, liftBound);
1202 degree (
buf) + 1, Pi, diophant, Mat, MOD);
1207 (
buf,
result, adaptedLiftBound, earlySuccess,
1211 (
buf,
result, adaptedLiftBound, earlySuccess,
1220 (
buf) + 1, MOD, liftBound);
1230 liftBounds[
i]= adaptedLiftBound;
1231 liftBound= adaptedLiftBound;
1233 Pi, diophant, Mat, MOD);
1236 liftBounds[
i]= adaptedLiftBound;
1239 liftBounds[
i]= adaptedLiftBound;
◆ LCHeuristic()
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier and in the leading coeffs of bivariate factors
- Parameters
-
[in,out] | A | [in,out] a poly |
[in,out] | LCmultiplier | [in,out] divisor of LC (A,1) |
[in,out] | biFactors | [in,out] bivariate factors |
[in,out] | leadingCoeffs | [in,out] leading coeffs |
[in] | oldAeval | [in] bivariate factors wrt. different second vars |
[in] | lengthAeval | [in] length of oldAeval |
[in] | evaluation | [in] evaluation point |
[in] | oldBiFactors | [in] bivariate factors without LCmultiplier distributed on them |
Definition at line 2598 of file facFqFactorize.cc.
2608 if (sqrfMultiplier.
getFirst().factor().inCoeffDomain())
2614 for (
int i= 0;
i < lengthAeval;
i++)
2616 if (oldAeval[
i].isEmpty())
2628 for (
int i=1;
i <= tmp.
level();
i++)
2644 tmp /=
myGetVars (ii.getItem().factor());
2647 if (multi == ii.getItem().exp())
2655 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.
hasItem();iter2++,
2658 if (index2 ==
index)
2662 tmp= ii.getItem().factor();
2666 for (
int jj=
A.level(); jj > 2; jj--, iter3++)
2667 tmp= tmp (iter3.
getItem(), jj);
2671 for (iter3= biFactors; iter3.
hasItem(); iter3++, index3++)
2673 if (index3 == index2)
2677 if (
fdivides (ii.getItem().factor(),
A, quot3))
2704 for (iter2= leadingCoeffs[lengthAeval-1];iter2.
hasItem();iter2++,
2707 if (index2 ==
index)
2709 tmp=
power (ii.getItem().factor(), ii.getItem().exp());
2715 for (
int jj=
A.level(); jj > 2; jj--, iter3++)
2716 tmp= tmp (iter3.
getItem(), jj);
2720 for (iter3= biFactors; iter3.
hasItem(); iter3++, index3++)
2722 if (index3 == index2)
◆ LCHeuristic2()
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
- Parameters
-
[in] | LCmultiplier | [in] divisor of LC (A,1) |
[in] | factors | [in] result of LucksWangSparseHeuristic |
[in,out] | leadingCoeffs | [in,out] leading coeffs |
[in,out] | contents | [in,out] content of factors |
[in,out] | LCs | [in,out] LC of factors divided by content of factors |
[in,out] | foundTrueMultiplier | [in,out] success? |
Definition at line 2762 of file facFqFactorize.cc.
2772 cont=
gcd (cont, LCmultiplier);
2776 foundTrueMultiplier=
true;
2778 for (iter2= leadingCoeffs; iter2.
hasItem(); iter2++, index2++)
2780 if (index2 ==
index)
2782 iter2.
getItem() /= LCmultiplier;
◆ LCHeuristic3()
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic.
- Parameters
-
[in] | LCmultiplier | [in] divisor of LC (A,1) |
[in] | factors | [in] result of LucksWangSparseHeuristic |
[in] | oldBiFactors | [in] bivariate factors without LCmultiplier distributed on them |
[in] | contents | [in] content of factors |
[in] | oldAeval | [in] bivariate factors wrt. different second vars |
[in,out] | A | [in,out] poly |
[in,out] | leadingCoeffs | [in,out] leading coeffs |
[in] | lengthAeval | [in] length of oldAeval |
[in,out] | foundMultiplier | [in,out] success? |
Definition at line 2792 of file facFqFactorize.cc.
2803 if ((LCmultiplier/
iter.
getItem()).inCoeffDomain() &&
2810 for (
int i= 0;
i < lengthAeval;
i++)
2812 if (oldAeval[
i].isEmpty())
2818 if (vars.
level() <= 2)
2822 iter3.
hasItem(); iter3++, index2++)
2824 if (index2 ==
index)
2826 iter3.getItem() /= LCmultiplier;
2831 foundMultiplier=
true;
◆ LCHeuristic4()
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.
- Parameters
-
[in] | oldBiFactors | [in] bivariate factors without LCmultiplier distributed on them |
[in] | oldAeval | [in] bivariate factors wrt. different second vars |
[in] | contents | [in] content of factors |
[in] | factors | [in] result of LucksWangSparseHeuristic |
[in] | testVars | [in] product of second vars that occur among oldAeval |
[in] | lengthAeval | [in] length of oldAeval |
[in,out] | leadingCoeffs | [in,out] leading coeffs |
[in,out] | A | [in,out] poly |
[in,out] | LCmultiplier | [in,out] divisor of LC (A,1) |
[in] | foundMultiplier | [in] success? |
Definition at line 2840 of file facFqFactorize.cc.
2856 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2859 if (index2 ==
index)
2862 foundMultiplier=
true;
2876 for (
int i= 0;
i < lengthAeval;
i++)
2878 if (oldAeval[
i].isEmpty())
2888 for (iter2= leadingCoeffs[lengthAeval-1]; iter2.hasItem();
2891 if (index2 ==
index)
2893 iter2.getItem() /= LCmultiplier;
2894 foundMultiplier=
true;
◆ LCHeuristicCheck()
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
- Parameters
-
[in] | LCs | [in] leading coeffs computed |
[in] | contents | [in] content of factors |
[in,out] | A | [in,out] oldA*LCmultiplier^m |
[in] | oldA | [in] some poly |
[in,out] | leadingCoeffs | [in,out] leading coefficients |
[in,out] | foundTrueMultiplier | [in,out] success? |
Definition at line 2746 of file facFqFactorize.cc.
2751 if (
fdivides (pLCs,
LC (oldA,1)) && (
LC(oldA,1)/pLCs).inCoeffDomain())
2757 foundTrueMultiplier=
true;
◆ lcmContent()
compute the LCM of the contents of A wrt to each variable occuring in A.
- Returns
- lcmContent returns the LCM of the contents of A wrt to each variable occuring in A.
- Parameters
-
[in] | A | [in] a compressed multivariate poly |
[in,out] | 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 954 of file facFqFactorize.cc.
962 for (
i=
i - 2;
i > 0;
i--)
◆ leadingCoeffReconstruction()
obtain factors of F by reconstructing their leading coeffs
- Returns
- returns the reconstructed factors
- See also
- factorRecombination()
- Parameters
-
[in] | F | [in] poly to be factored |
[in] | factors | [in] factors of f monic wrt Variable (1) |
[in] | M | [in] a list of powers of Variables |
◆ liftBoundAdaption()
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
- Returns
- liftBoundAdaption returns an adapted lift bound.
- See also
- earlyFactorDetect(), earlyFactorDetection()
- Parameters
-
[in] | F | [in] a poly |
[in] | factors | [in] list of list of lifted factors that are monic wrt Variable (1) |
[in,out] | success | [in,out] indicates that no further lifting is necessary |
[in] | deg | [in] stage of Hensel lifting |
[in] | MOD | [in] a list of powers of Variables |
[in] | bound | [in] initial lift bound |
Definition at line 445 of file facFqFactorize.cc.
448 int adaptedLiftBound= 0;
474 if (adaptedLiftBound < deg)
476 if (adaptedLiftBound <
degree (F) + 1)
482 adaptedLiftBound= deg;
488 if (e + 1 <
degree (F) + 1)
489 adaptedLiftBound= deg;
491 adaptedLiftBound= e + 1;
497 adaptedLiftBound= deg;
505 return adaptedLiftBound;
◆ myCompress()
compress a polynomial s.t.
and no gaps between the variables occur
- Returns
- a compressed poly with the above properties
- Parameters
-
[in] | F | [in] a poly |
[in,out] | N | [in,out] a map to decompress |
Definition at line 136 of file facFqFactorize.cc.
140 int **
swap=
new int* [n + 1];
141 for (
int i= 0;
i <= n;
i++)
144 swap [
i]=
new int [3];
168 for (
i= 1;
i < n;
i++)
170 for (
int j= 1;
j < n -
i + 1;
j++)
176 buf3=
swap [
j + 1] [2];
189 buf3=
swap [
j + 1] [2];
201 for (
i= n;
i > 0;
i--)
◆ precomputeLeadingCoeff()
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.
- Returns
- see above
- Parameters
-
[in] | LCF | [in] a multivariate poly |
[in] | LCFFactors | [in] a list of univariate factors of LCF of level 2 |
[in] | alpha | [in] algebraic var. |
[in] | evaluation | [in] an evaluation point having lSecondVarLCs+1 components |
[in] | differentSecondVarLCs | [in] LCs of factors of f wrt different second variables |
[in] | lSecondVarLCs | [in] length of the above |
[in,out] | y | [in,out] if y.level() is not 1 on output the second variable has been changed to y |
Definition at line 1464 of file facFqFactorize.cc.
1474 for (
int i= 1;
i <= LCFFactors.
length() + 1;
i++)
1499 for (
int i= 0;
i < lSecondVarLCs;
i++)
1501 for (
j= differentSecondVarLCs[
i];
j.hasItem();
j++)
1503 if (
j.getItem().level() == LCFLevel)
1511 result= differentSecondVarLCs [
i];
1526 CFList factors= LCFFactors;
1529 i.getItem()=
M (
i.getItem());
1533 CFList evalSqrfPartF, bufFactors;
1550 bufFactors, bufSqrfFactors, evalSqrfPartF,
evalPoint);
1552 bool foundDifferent=
false;
1561 for (
int i= 0;
i < lSecondVarLCs;
i++)
1563 if (!differentSecondVarLCs [
i].isEmpty())
1565 bool allConstant=
true;
1578 bufFactors= differentSecondVarLCs [
i];
1584 bufBufFactors= bufFactors;
1594 bufSqrfFactors, evalSqrfPartF,
evalPoint);
1597 foundDifferent=
true;
1602 differentSecondVarLCs [
i]=
l;
1606 if (!pass &&
i == lSecondVarLCs - 1)
1610 for (
int j= 1;
j <= factors.
length();
j++)
1614 delete [] bufSqrfFactors;
1624 for (
int j= 1;
j <= factors.
length();
j++)
1628 delete [] bufSqrfFactors;
1632 factors= bufFactors;
1634 bufFactors= factors;
1637 dummy [0]= sqrfPartF;
1640 sqrfPartF= MM (sqrfPartF);
1646 for (
int i= 2;
i <= varsSqrfPartF.
level();
i++)
1651 sqrfPartF=
shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2);
1652 if (factors.
length() > 1)
1656 for (
int i= 0;
i < factors.
length();
i++)
1657 leadingCoeffs.
append (LC1);
1660 CFList oldFactors= factors;
1664 bool success=
false;
1667 if (
size (oldSqrfPartFPowLC)/
getNumVars (oldSqrfPartFPowLC) < 500 &&
1669 oldFactors, 2, leadingCoeffs, heuResult))
1680 for (
int i= 0;
i < factors.
length();
i++)
1681 leadingCoeffs[
i]= LC1;
1684 i.getItem() *= LC1 (0,2)/
Lc (
i.getItem());
1690 int liftBound=
degree (newSqrfPartF,2) + 1;
1696 leadingCoeffs,
false);
1698 if (sqrfPartF.
level() > 2)
1700 int* liftBounds=
new int [sqrfPartF.
level() - 1];
1701 bool noOneToOne=
false;
1705 for (
int i= 0;
i < factors.
length();
i++)
1707 leadingCoeffs2 [sqrfPartF.
level() - 3]= LCs;
1708 for (
int i= sqrfPartF.
level() - 1;
i > 2;
i--)
1711 j.getItem()=
j.getItem() (0,
i + 1);
1712 leadingCoeffs2 [
i - 3]= LCs;
1716 int liftBoundsLength= sqrfPartF.
level() - 1;
1717 for (
int i= 0;
i < liftBoundsLength;
i++)
1718 liftBounds [
i]=
degree (sqrfPartF,
i + 2) + 1;
1722 diophant, Pi, liftBounds, sqrfPartF.
level() - 1, noOneToOne);
1723 delete [] leadingCoeffs2;
1724 delete [] liftBounds;
1737 factors=
CFList (oldSqrfPartF/contF);
1746 for (
int i= 0;
i < LCFFactors.
length();
i++)
1749 for (
k= bufSqrfFactors[
i];
k.hasItem();
k++)
1751 int pos=
findItem (bufFactors,
k.getItem().factor());
1753 tmp *=
power (
getItem (interMedResult, pos),
k.getItem().exp());
1763 i.getItem()=
N (
i.getItem());
1768 CFList l= differentSecondVarLCs [
j];
1771 differentSecondVarLCs [
j]=
l;
1779 if (!
result.getFirst().inCoeffDomain())
1786 CFList l= differentSecondVarLCs [
j];
1789 differentSecondVarLCs [
j]=
l;
1809 if (lSecondVarLCs -
level > 0)
1812 int j= lSecondVarLCs+2;
1815 for (
i= evaluation2;
i.hasItem();
i++,
j--)
1820 i.getItem()= evaluation2.
getLast();
1831 delete [] bufSqrfFactors;
1858 for (
int j=
level+1;
j < lSecondVarLCs;
j++)
1862 if (!differentSecondVarLCs[
j].isEmpty())
1864 differentSecondVarLCs2[
j -
level - 1]= differentSecondVarLCs[
j];
1865 i= differentSecondVarLCs2[
j-
level - 1];
1894 for (
i=newLCs;
i.hasItem();
i++)
1896 for (
int j= 1;
j < lSecondVarLCs-
level;
j++)
1898 for (
i= differentSecondVarLCs2[
j-1];
i.hasItem();
i++)
1906 differentSecondVarLCs2, lSecondVarLCs -
level - 1,
1909 if (dummyvar.
level() != 1)
1911 for (
i= recursiveResult;
i.hasItem();
i++)
1914 for (
i= recursiveResult;
i.hasItem();
i++)
1916 for (
int j= lSecondVarLCs-
level-1;
j > 0;
j--)
1924 delete [] bufSqrfFactors;
1925 delete [] differentSecondVarLCs2;
1930 iter=recursiveResult;
1935 for (;
i.hasItem();
i++,
iter++)
1937 delete [] differentSecondVarLCs2;
1944 delete [] bufSqrfFactors;
◆ prepareLeadingCoeffs()
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
- Parameters
-
[in,out] | LCs | [in,out] |
[in,out] | A | [in,out] |
[in,out] | Aeval | [in,out] |
[in] | n | [in] level of poly to be factored |
[in] | leadingCoeffs | [in] precomputed leading coeffs |
[in] | biFactors | [in] bivariate factors |
[in] | evaluation | [in] evaluation point |
Definition at line 2365 of file facFqFactorize.cc.
2373 for (
int i= n - 1;
i > 2;
i--,
iter++)
2375 for (
j=
l;
j.hasItem();
j++)
2386 for (
int i= 0;
i < n-2;
i++)
2388 ii= normalizeFactor;
2389 for (
j= LCs [
i];
j.hasItem();
j++, ii++)
◆ recombination()
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with factors2
- Parameters
-
[in] | factors1 | [in] list of bivariate factors |
[in] | factors2 | [in] list univariate factors |
[in] | s | [in] algorithm starts checking subsets of size s |
[in] | thres | [in] threshold for the size of subsets which are checked |
[in] | evalPoint | [in] evaluation point |
[in] | x | [in] second variable of bivariate factors |
Definition at line 2100 of file facFqFactorize.cc.
2108 int *
v=
new int [
T.length()];
2109 for (
int i= 0;
i <
T.length();
i++)
2111 bool nosubset=
false;
2113 TT=
copy (factors1);
2114 int recombinations= 0;
2115 while (
T.length() >= 2*
s &&
s <= thres)
2117 while (nosubset ==
false)
2119 if (
T.length() ==
s)
2129 if (nosubset)
break;
2139 if (nosubset)
break;
2143 if (
T.length() < 2*
s ||
T.length() ==
s)
2152 for (
int i= 0;
i <
T.length();
i++)
2158 if (
T.length() < 2*
s)
◆ refineBiFactors()
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
- Parameters
-
[in] | A | [in] some poly |
[in,out] | biFactors | [in,out] list of bivariate to be refined, returns refined factors |
[in] | factors | [in] list of bivariate factorizations of A wrt different second variables |
[in] | evaluation | [in] the evaluation point |
[in] | minFactorsLength | [in] the minimal number of factors |
Definition at line 2318 of file facFqFactorize.cc.
2328 bool leaveLoop=
false;
2329 for (
int j= 0;
j <
A.level() - 2;
j++)
◆ sortByUniFactors()
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFactors, uniFactors and biFactors may get recombined if necessary
- Parameters
-
[in,out] | Aeval | [in,out] array of bivariate factors |
[in] | AevalLength | [in] length of Aeval |
[in,out] | uniFactors | [in,out] univariate factors |
[in,out] | biFactors | [in,out] bivariate factors |
[in] | evaluation | [in] evaluation point |
Definition at line 2234 of file facFqFactorize.cc.
2245 int pos,
index, checklength;
2246 bool leaveLoop=
false;
2248 for (
int j= 0;
j < AevalLength;
j++)
2277 checklength= biFactors.
length();
2279 if (checklength > biFactors.
length())
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
fac_fq_squarefree |
| ) |
const & |
◆ info
< [in] sqrfree poly
< [in] info about extension
Definition at line 38 of file facFqFactorize.h.
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
int getGFDegree() const
getter
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 test...
static CanonicalForm myContent(const CanonicalForm &F)
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
generate random elements in F_p
Variable getBeta() const
getter
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
bool isInExtension() const
getter
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 test...
const CanonicalForm int const CFList const Variable & y
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
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 fa...
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
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.
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
static BOOLEAN length(leftv result, leftv arg)
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
generate random elements in F_p(alpha)
CanonicalForm generate() const
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
const CanonicalForm CFMap CFMap & N
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
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 primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
bool delta(X x, Y y, D d)
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
const CanonicalForm int const CFList & evaluation
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
#define GaloisFieldDomain
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
#define ASSERT(expression, message)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int status int void * buf
TIMING_START(fac_alg_resultant)
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
CanonicalForm getGamma() const
getter
CFList *& Aeval
<[in] poly
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
CFList conv(const CFArray &A)
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
char getGFName() const
getter
void prune(Variable &alpha)
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
generate random elements in GF
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm getDelta() const
getter
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
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
int testFactors(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, CanonicalForm &sqrfPartF, CFList &factors, CFFList *&bufSqrfFactors, CFList &evalSqrfPartF, const CFArray &evalPoint)
CFList multiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
static CanonicalForm prodEval(const CFList &l, const CanonicalForm &evalPoint, const Variable &v)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
int findItem(const CFList &list, const CanonicalForm &item)
helper function
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
Rational pow(const Rational &a, int e)
CanonicalForm generate() const
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const Variable & v
< [in] a sqrfree bivariate poly
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...
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
const CanonicalForm int s
int status int void size_t count
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
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,...
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CFArray copy(const CFList &list)
write elements of list into an array
Variable getAlpha() const
getter
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CFList checkOneToOne(const CFList &factors1, const CFList &factors2, CFList &factors3, const CanonicalForm &evalPoint, const Variable &x)
check if univariate factors factors2 of factors3 coincide with univariate factors of factors1 and rec...
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
static int index(p_Length length, p_Ord ord)
const ExtensionInfo & info
< [in] sqrfree poly
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
static Variable chooseExtension(const Variable &alpha)
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...