 |
My Project
debian-1:4.1.1-p2+ds-4build1
|
Go to the source code of this file.
|
| TIMING_DEFINE_PRINT (fac_fq_bi_sqrf) TIMING_DEFINE_PRINT(fac_fq_bi_factor_sqrf) static const double log2exp |
|
CFList | biFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
| Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field. More...
|
|
CFList | biSqrfFactorizeHelper (const CanonicalForm &G, const ExtensionInfo &info) |
|
CFList | FpBiSqrfFactorize (const CanonicalForm &G) |
| factorize a squarefree bivariate polynomial over . More...
|
|
CFList | FqBiSqrfFactorize (const CanonicalForm &G, const Variable &alpha) |
| factorize a squarefree bivariate polynomial over . More...
|
|
CFList | GFBiSqrfFactorize (const CanonicalForm &G) |
| factorize a squarefree bivariate polynomial over GF More...
|
|
CFFList | FpBiFactorize (const CanonicalForm &G, bool substCheck=true) |
| factorize a bivariate polynomial over More...
|
|
CFFList | FqBiFactorize (const CanonicalForm &G, const Variable &alpha, bool substCheck=true) |
| factorize a bivariate polynomial over More...
|
|
CFFList | GFBiFactorize (const CanonicalForm &G, bool substCheck=true) |
| factorize a bivariate polynomial over GF More...
|
|
CanonicalForm | prodMod0 (const CFList &L, const CanonicalForm &M, const modpk &b=modpk()) |
| via divide-and-conquer More...
|
|
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 . More...
|
|
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 &M, const ExtensionInfo &info, DegreePattern °s, const CanonicalForm &eval, int s, int thres) |
| naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible. More...
|
|
CFList | factorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &M, DegreePattern °s, const CanonicalForm &eval, int s, int thres, const modpk &b=modpk(), const CanonicalForm &den=1) |
| naive factor recombination. Uses precomputed data to exclude combinations that are not possible. More...
|
|
Variable | chooseExtension (const Variable &alpha, const Variable &beta, int k) |
| chooses a field extension. More...
|
|
int * | getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC) |
| compute lifting precisions from the shape of the Newton polygon of F 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=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. 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...
|
|
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...
|
|
CFList | extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
| Factorization over an extension of initial field. More...
|
|
This file provides functions for factorizing a bivariate polynomial over
,
or GF.
- Author
- Martin Lee
Definition in file facFqBivar.h.
◆ biFactorize()
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.
- Returns
- biFactorize returns a list of factors of F. If F is not monic its leading coefficient is not outputted.
- See also
- extBifactorize()
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.
- Parameters
-
[in] | F | a sqrfree bivariate poly |
[in] | info | information about extension |
Definition at line 8201 of file facFqBivar.cc.
8215 if (
A.isUnivariate())
8217 if (extension ==
false)
8238 A=
A/(contentAx*contentAy);
8239 CFList contentAxFactors, contentAyFactors;
8249 if (
A.inCoeffDomain())
8251 append (factors, contentAxFactors);
8252 append (factors, contentAyFactors);
8256 else if (
A.isUnivariate())
8259 append (factors, contentAxFactors);
8260 append (factors, contentAyFactors);
8281 bool derivXZero=
false;
8288 gcdDerivX=
gcd (
A, derivX);
8289 if (
degree (gcdDerivX) > 0)
8294 append (factorsG, contentAxFactors);
8295 append (factorsG, contentAyFactors);
8302 bool derivYZero=
false;
8309 gcdDerivY=
gcd (
A, derivY);
8310 if (
degree (gcdDerivY) > 0)
8315 append (factorsG, contentAxFactors);
8316 append (factorsG, contentAyFactors);
8331 derivXZero= derivYZero;
8353 int minBound= bounds[0];
8354 for (
int i= 1;
i < boundsLength;
i++)
8357 minBound=
tmin (minBound, bounds[
i]);
8362 int minBound2= bounds2[0];
8363 for (
int i= 1;
i < boundsLength2;
i++)
8365 if (bounds2[
i] != 0)
8366 minBound2=
tmin (minBound2, bounds2[
i]);
8372 CFList uniFactors, list, bufUniFactors;
8377 CanonicalForm Aeval2, evaluation2, bufAeval2, bufEvaluation2;
8378 CFList bufUniFactors2, list2, uniFactors2;
8389 bool symmetric=
false;
8392 for (
int i= 0;
i < factorNums;
i++)
8398 if (!derivXZero && !fail2 && !symmetric)
8409 "time to find eval point wrt y: ");
8412 if (fail && (
i == 0))
8414 if (!derivXZero && !fail2 && !symmetric)
8416 bufEvaluation= bufEvaluation2;
8417 int dummy= subCheck2;
8418 subCheck2= subCheck1;
8423 bufAeval= bufAeval2;
8432 if (fail && (
i == 0))
8445 if (fail && (
i != 0))
8452 "time for univariate factorization over Fq: ");
8453 DEBOUTLN (cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8454 (
prod (bufUniFactors)*
Lc (bufAeval) == bufAeval));
8456 if (!derivXZero && !fail2 && !symmetric)
8461 "time for univariate factorization in y over Fq: ");
8462 DEBOUTLN (cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8463 (
prod (bufUniFactors2)*
Lc (bufAeval2) == bufAeval2));
8466 if (bufUniFactors.
length() == 1 ||
8467 (!fail2 && !derivXZero && !symmetric && (bufUniFactors2.
length() == 1)))
8487 if (
i == 0 && !extension)
8493 if (subCheck > 1 && (subCheck1%subCheck == 0))
8496 subst (bufA, bufA, subCheck,
x);
8509 if (!derivXZero && !fail2 && !symmetric && subCheck2 > 0)
8513 if (subCheck > 1 && (subCheck2%subCheck == 0))
8516 subst (bufA, bufA, subCheck,
y);
8532 if (!derivXZero && !fail2 && !symmetric)
8539 uniFactors= bufUniFactors;
8541 if (!derivXZero && !fail2 && !symmetric)
8544 evaluation2= bufEvaluation2;
8545 uniFactors2= bufUniFactors2;
8552 if (!derivXZero && !fail2 && !symmetric)
8557 uniFactors2= bufUniFactors2;
8559 evaluation2= bufEvaluation2;
8564 uniFactors= bufUniFactors;
8569 list.
append (bufEvaluation);
8570 if (!derivXZero && !fail2 && !symmetric)
8571 list2.
append (bufEvaluation2);
8574 "total time for univariate factorizations: ");
8576 if (!derivXZero && !fail2 && !symmetric)
8578 if ((uniFactors.
length() > uniFactors2.
length() && minBound2 <= minBound)||
8583 uniFactors= uniFactors2;
8615 minBound= minBound2;
8621 "time to shift eval to zero: ");
8627 DEBOUTLN (cerr,
"uniFactors= " << uniFactors);
8629 if ((GF && !extension) || (GF && extension &&
k != 1))
8631 bool earlySuccess=
false;
8635 (
A, earlySuccess, earlyFactors, degs, liftBound,
8638 "time for bivariate hensel lifting over Fq: ");
8639 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8651 "time for naive bivariate factor recombi over Fq: ");
8654 factors=
Union (earlyFactors, factors);
8655 else if (!earlySuccess && degs.
getLength() == 1)
8656 factors= earlyFactors;
8666 factors=
Union (lll, factors);
8672 factors=
Union (lll, factors);
8674 else if (!extension && (
alpha !=
x || GF))
8678 factors=
Union (lll, factors);
8681 "time to bivar lift and LLL recombi over Fq: ");
8682 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8686 bool earlySuccess=
false;
8690 (
A, earlySuccess, earlyFactors, degs, liftBound,
8693 "time for bivar hensel lifting over Fq: ");
8694 DEBOUTLN (cerr,
"lifted factors= " << uniFactors);
8702 "time for small subset naive recombi over Fq: ");
8704 int oldUniFactorsLength= uniFactors.
length();
8725 "time to increase precision: ");
8726 factors=
Union (factors, tmp);
8728 && uniFactors.
length() != oldUniFactorsLength)
8776 int oldUniFactorsLength= uniFactors.
length();
8785 info2, source, dest, liftBound
8787 factors=
Union (factors, tmp);
8789 && uniFactors.
length() != oldUniFactorsLength)
8806 factors=
Union (earlyFactors, factors);
8807 else if (!earlySuccess && degs.
getLength() == 1)
8808 factors= earlyFactors;
◆ biSqrfFactorizeHelper()
Definition at line 53 of file facFqBivar.h.
59 F /= (contentX*contentY);
60 CFFList contentXFactors, contentYFactors;
73 CFList bufContentX, bufContentY;
82 if (contentXFactors.
getFirst().factor().inCoeffDomain())
84 if (contentYFactors.getFirst().factor().inCoeffDomain())
85 contentYFactors.removeFirst();
90 result.append (
N (
i.getItem().factor()));
92 result.append (
N (
i.getItem().factor()));
97 mpz_t *
M=
new mpz_t [4];
103 mpz_t * S=
new mpz_t [2];
112 result.append (
N(
i.getItem().factor()));
114 result.append (
N (
i.getItem().factor()));
◆ chooseExtension()
chooses a field extension.
- Returns
- chooseExtension returns an extension specified by beta of appropiate size
- Parameters
-
[in] | alpha | some algebraic variable |
[in] | beta | some algebraic variable |
[in] | k | some int |
Definition at line 780 of file facFqBivar.cc.
810 BuildIrred (NTLIrredpoly,
i*
m);
◆ earlyFactorDetection()
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.
- See also
- factorRecombination(), extEarlyFactorDetection()
- Parameters
-
[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 935 of file facFqBivar.cc.
942 factorsFoundIndex, degs, success, deg,
eval,
b,
den);
◆ evalPoint()
find an evaluation point p, s.t. F(p,y) is squarefree and
.
- Returns
- evalPoint returns an evaluation point, which is valid if and only if fail == false.
- Parameters
-
[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 81 of file facFqBivar.cc.
133 random= genAlgExt.generate();
136 if (
find (list, random))
continue;
140 if (!
find (list, random))
146 if (!
find (list, random))
150 }
while (
find (list, random));
◆ extBiFactorize()
Factorization over an extension of initial field.
- Returns
- extBiFactorize returns factorization of F over initial field
- See also
- biFactorize()
- Parameters
-
[in] | F | poly to be factored |
[in] | info | info about extension |
Definition at line 8824 of file facFqBivar.cc.
8839 bool extension=
true;
8865 else if (!GF && (
alpha !=
x))
8883 bool primFail=
false;
8886 ASSERT (!primFail,
"failure in integer factorizer");
8903 bool primFail=
false;
8905 ASSERT (!primFail,
"failure in integer factorizer");
8927 bool extension=
true;
8931 if (
ipower (
p, extensionDeg) < (1<<16))
8957 if (
ipower (
p, 2*extensionDeg) < (1<<16))
8973 bool primFail=
false;
8976 ASSERT (!primFail,
"failure in integer factorizer");
◆ extEarlyFactorDetection()
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.
- See also
- factorRecombination(), earlyFactorDetection()
- Parameters
-
[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 946 of file facFqBivar.cc.
965 bool trueFactor=
false;
990 factorsFoundIndex[
l]= 1;
1002 factorsFoundIndex[
l]= 1;
1021 if (!
buf.inCoeffDomain())
1034 adaptedLiftBound= d + 1;
1035 if (adaptedLiftBound < deg)
◆ extFactorRecombination()
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.
- Returns
- extFactorRecombination returns a list of factors over the initial field, whose shift to zero is reversed.
- See also
- factorRecombination(), extEarlyFactorDetection()
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.
- Parameters
-
[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 346 of file facFqBivar.cc.
351 if (factors.
length() == 0)
377 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, M) == F " <<
392 int *
v=
new int [
T.length()];
393 for (
int i= 0;
i <
T.length();
i++)
401 bool nosubset=
false;
403 bool trueFactor=
false;
406 while (
T.length() >= 2*
s &&
s <= thres)
408 while (nosubset ==
false)
436 if (!degs.
find (subsetDeg))
481 buf0=
buf (0,
x)*LCBuf;
487 if (
T.length() < 2*
s ||
T.length() ==
s ||
517 if (
T.length() < 2*
s ||
T.length() ==
s)
535 for (
int i= 0;
i <
T.length();
i++)
539 if (
T.length() < 2*
s)
◆ factorRecombination()
naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
- Returns
- factorRecombination returns a list of factors of F.
- See also
- extFactorRecombination(), earlyFactorDetectection()
naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
- Parameters
-
[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 561 of file facFqBivar.cc.
567 if (factors.
length() == 0)
583 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
586 DEBOUTLN (cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
600 int *
v=
new int [
T.length()];
601 for (
int i= 0;
i <
T.length();
i++)
603 bool nosubset=
false;
618 while (
T.length() >= 2*
s &&
s <= thres)
620 while (nosubset ==
false)
648 if (!degs.
find (subsetDeg))
682 if (!
Lc (
g).inBaseDomain())
699 denom /=
gcd (denom, denQuot);
715 if (
T.length() < 2*
s ||
T.length() ==
s ||
742 if (
T.length() < 2*
s ||
T.length() ==
s)
758 for (
int i= 0;
i <
T.length();
i++)
763 if (
T.length() < 2*
s)
◆ FpBiFactorize()
factorize a bivariate polynomial over
- Returns
- FpBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
- See also
- FqBiFactorize(), GFBiFactorize()
- Parameters
-
[in] | G | a bivariate poly |
[in] | substCheck | enables substitute check |
Definition at line 180 of file facFqBivar.h.
190 bool foundOne=
false;
195 if (substDegree [
i-1] > 1)
210 tmp2=
i.getItem().factor();
213 if (substDegree[
j-1] > 1)
220 j.getItem().exp()*
i.getItem().exp()));
232 F /= (contentX*contentY);
233 CFFList contentXFactors, contentYFactors;
236 if (contentXFactors.
getFirst().factor().inCoeffDomain())
238 if (contentYFactors.
getFirst().factor().inCoeffDomain())
250 mpz_t *
M=
new mpz_t [4];
256 mpz_t * S=
new mpz_t [2];
265 "time for bivariate sqrf factors over Fp: ");
274 "time to factor bivariate sqrf factors over Fp: ");
275 for (
i= bufResult;
i.hasItem();
i++)
◆ FpBiSqrfFactorize()
◆ FqBiFactorize()
factorize a bivariate polynomial over
- Returns
- FqBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
- See also
- FpBiFactorize(), FqBiFactorize()
- Parameters
-
[in] | G | a bivariate poly |
[in] | alpha | algebraic variable |
[in] | substCheck | enables substitute check |
Definition at line 305 of file facFqBivar.h.
316 bool foundOne=
false;
321 if (substDegree [
i-1] > 1)
336 tmp2=
i.getItem().factor();
339 if (substDegree[
j-1] > 1)
346 j.getItem().exp()*
i.getItem().exp()));
358 F /= (contentX*contentY);
359 CFFList contentXFactors, contentYFactors;
362 if (contentXFactors.
getFirst().factor().inCoeffDomain())
364 if (contentYFactors.
getFirst().factor().inCoeffDomain())
377 mpz_t *
M=
new mpz_t [4];
383 mpz_t * S=
new mpz_t [2];
392 "time for bivariate sqrf factors over Fq: ");
401 "time to factor bivariate sqrf factors over Fq: ");
402 for (
i= bufResult;
i.hasItem();
i++)
◆ FqBiSqrfFactorize()
factorize a squarefree bivariate polynomial over
.
- Returns
- FqBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
- See also
- FpBiSqrfFactorize(), GFBiSqrfFactorize()
- Parameters
-
[in] | G | a bivariate poly |
[in] | alpha | algebraic variable |
Definition at line 150 of file facFqBivar.h.
◆ getLiftPrecisions()
compute lifting precisions from the shape of the Newton polygon of F
- Returns
- getLiftPrecisions returns lifting precisions computed from the shape of the Newton polygon of F
- Parameters
-
[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 1084 of file facFqBivar.cc.
1086 int sizeOfNewtonPoly;
1088 int sizeOfRightSide;
1089 int * rightSide=
getRightSide(newtonPolyg, sizeOfNewtonPoly, sizeOfRightSide);
1092 delete [] rightSide;
1093 for (
int i= 0;
i < sizeOfNewtonPoly;
i++)
1094 delete [] newtonPolyg[
i];
1095 delete [] newtonPolyg;
◆ GFBiFactorize()
factorize a bivariate polynomial over GF
- Returns
- GFBiFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
- See also
- FpBiFactorize(), FqBiFactorize()
- Parameters
-
[in] | G | a bivariate poly |
[in] | substCheck | enables substitute check |
Definition at line 432 of file facFqBivar.h.
437 "GF as base field expected");
444 bool foundOne=
false;
449 if (substDegree [
i-1] > 1)
464 tmp2=
i.getItem().factor();
467 if (substDegree[
j-1] > 1)
474 j.getItem().exp()*
i.getItem().exp()));
486 F /= (contentX*contentY);
487 CFFList contentXFactors, contentYFactors;
490 if (contentXFactors.
getFirst().factor().inCoeffDomain())
492 if (contentYFactors.
getFirst().factor().inCoeffDomain())
505 mpz_t *
M=
new mpz_t [4];
511 mpz_t * S=
new mpz_t [2];
520 "time for bivariate sqrf factors over GF: ");
529 "time to factor bivariate sqrf factors over GF: ");
530 for (
i= bufResult;
i.hasItem();
i++)
◆ GFBiSqrfFactorize()
factorize a squarefree bivariate polynomial over GF
- Returns
- GFBiSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
- See also
- FpBiSqrfFactorize(), FqBiSqrfFactorize()
- Parameters
-
Definition at line 164 of file facFqBivar.h.
168 "GF as base field expected");
◆ henselLiftAndEarly() [1/2]
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
- earlyFactorDetection(), extEarlyFactorDetection()
- Parameters
-
[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 1416 of file facFqBivar.cc.
◆ henselLiftAndEarly() [2/2]
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
- earlyFactorDetection(), extEarlyFactorDetection()
- Parameters
-
[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 1115 of file facFqBivar.cc.
1133 CFList bufUniFactors= uniFactors;
1136 if (!
Lc (
A).inBaseDomain())
1151 bool mipoHasDen=
false;
1156 lcA0=
lc (
A (0, 2));
1157 A *=
b.inverse (lcA0);
1178 earlySuccess=
false;
1179 int newLiftBound= 0;
1181 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
1183 int * factorsFoundIndex=
new int [uniFactors.
length()];
1184 for (
int i= 0;
i < uniFactors.
length();
i++)
1185 factorsFoundIndex [
i]= 0;
1189 if (smallFactorDeg >= liftBound ||
degree (
A,
y) <= 4)
1191 else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
1193 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1201 bufBufUniFactors= bufUniFactors;
1212 factorsFoundIndex, degs, earlySuccess,
1216 factorsFoundIndex, degs, earlySuccess,
1221 factorsFoundIndex, degs, earlySuccess,
info,
1222 eval, smallFactorDeg);
1223 if (degs.
getLength() > 1 && !earlySuccess &&
1224 smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
1226 if (newLiftBound >= liftPre[sizeOfLiftPre-1]+1)
1230 liftPre[sizeOfLiftPre-1] + 1, Pi, diophant,
M,
b);
1233 bufBufUniFactors= bufUniFactors;
1241 factorsFoundIndex, degs, earlySuccess,
1242 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1245 factorsFoundIndex, degs, earlySuccess,
1246 liftPre[sizeOfLiftPre-1] + 1,
eval,
b,
den);
1250 factorsFoundIndex, degs, earlySuccess,
info,
1251 eval, liftPre[sizeOfLiftPre-1] + 1);
1254 else if (earlySuccess)
1255 liftBound= newLiftBound;
1257 int i= sizeOfLiftPre - 1;
1258 while (degs.
getLength() > 1 && !earlySuccess &&
i - 1 >= 0)
1260 if (newLiftBound >= liftPre[
i] + 1)
1264 liftPre[
i-1] + 1, Pi, diophant,
M,
b);
1267 bufBufUniFactors= bufUniFactors;
1275 factorsFoundIndex, degs, earlySuccess,
1279 factorsFoundIndex, degs, earlySuccess,
1284 factorsFoundIndex, degs, earlySuccess,
info,
1285 eval, liftPre[
i-1] + 1);
1289 liftBound= newLiftBound;
1295 liftBound= newLiftBound;
1300 henselLift12 (
A, bufUniFactors, smallFactorDeg, Pi, diophant,
M,
b,
true);
1308 bufBufUniFactors= bufUniFactors;
1318 factorsFoundIndex, degs, earlySuccess,
1322 factorsFoundIndex, degs, earlySuccess,
1327 factorsFoundIndex, degs, earlySuccess,
info,
1328 eval, smallFactorDeg);
1330 while ((
degree (
A,
y)/4)*
i + 4 <= smallFactorDeg)
1333 if (degs.
getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
1337 dummy, Pi, diophant,
M,
b);
1340 bufBufUniFactors= bufUniFactors;
1348 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1352 factorsFoundIndex, degs, earlySuccess, dummy,
eval,
1357 factorsFoundIndex, degs, earlySuccess,
info,
1360 while (degs.
getLength() > 1 && !earlySuccess &&
i < 4)
1362 if (newLiftBound >= dummy)
1367 dummy, Pi, diophant,
M,
b);
1370 bufBufUniFactors= bufUniFactors;
1378 factorsFoundIndex, degs, earlySuccess, dummy,
1382 factorsFoundIndex, degs, earlySuccess, dummy,
1387 factorsFoundIndex, degs, earlySuccess,
info,
1392 liftBound= newLiftBound;
1398 liftBound= newLiftBound;
1409 delete [] factorsFoundIndex;
1412 return bufUniFactors;
◆ prodMod0()
via divide-and-conquer
- Returns
- prodMod0 computes the above defined product
- See also
- prodMod()
- Parameters
-
[in] | L | a list of compressed, bivariate polynomials |
[in] | M | a power of Variable (2) |
[in] | b | coeff bound |
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
fac_fq_bi_sqrf |
| ) |
const |
◆ uniFactorizer()
Univariate factorization of squarefree monic polys over finite fields via NTL. If the characteristic is even special GF2 routines of NTL are used.
- Returns
- uniFactorizer returns a list of monic factors
- Parameters
-
[in] | A | squarefree univariate poly |
[in] | alpha | algebraic variable |
[in] | GF | GaloisFieldDomain? |
Definition at line 156 of file facFqBivar.cc.
159 if (
A.inCoeffDomain())
162 "univariate polynomial expected or constant expected");
174 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
175 nmod_poly_t FLINTmipo, leadingCoeff;
177 fq_nmod_poly_t FLINTA;
178 fq_nmod_poly_factor_t FLINTFactorsA;
186 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
188 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
191 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
196 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
208 zz_pE::init (NTLMipo);
211 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
212 zz_pE multi= to_zz_pE (1);
220 GF2E::init (NTLMipo);
223 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
224 GF2E multi= to_GF2E (1);
241 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
242 nmod_poly_t FLINTmipo, leadingCoeff;
244 fq_nmod_poly_t FLINTA;
245 fq_nmod_poly_factor_t FLINTFactorsA;
253 fq_nmod_poly_make_monic (FLINTA, FLINTA,
fq_con);
255 fq_nmod_poly_factor_init (FLINTFactorsA,
fq_con);
258 fq_nmod_poly_factor (FLINTFactorsA, leadingCoeff, FLINTA,
fq_con);
263 fq_nmod_poly_factor_clear (FLINTFactorsA,
fq_con);
275 zz_pE::init (NTLMipo);
278 vec_pair_zz_pEX_long NTLFactorsA= CanZass (NTLA);
279 zz_pE multi= to_zz_pE (1);
287 GF2E::init (NTLMipo);
290 vec_pair_GF2EX_long NTLFactorsA= CanZass (NTLA);
291 GF2E multi= to_GF2E (1);
303 nmod_poly_factor_t
result;
304 nmod_poly_factor_init (
result);
305 mp_limb_t leadingCoeff= nmod_poly_factor (
result, FLINTA);
307 if (factorsA.getFirst().factor().inCoeffDomain())
308 factorsA.removeFirst();
309 nmod_poly_factor_clear (
result);
323 vec_pair_zz_pX_long NTLFactorsA= CanZass (NTLA);
324 zz_p multi= to_zz_p (1);
331 vec_pair_GF2X_long NTLFactorsA= CanZass (NTLA);
332 GF2 multi= to_GF2 (1);
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
int getGFDegree() const
getter
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 .
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
static const int SW_RATIONAL
set to 1 for computations over Q
generate random elements in F_p
Variable getBeta() const
getter
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
bool isInExtension() const
getter
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval)
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList const Variable & y
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
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...
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
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 ...
nmod_poly_clear(FLINTmipo)
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
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
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
int * getRightSide(int **polygon, int sizeOfPolygon, int &sizeOfOutput)
get the y-direction slopes of all edges with positive slope in y-direction of a convex polygon with a...
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
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
bool delta(X x, Y y, D d)
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
const CanonicalForm int const CFList & evaluation
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
#define GaloisFieldDomain
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
convertFacCF2nmod_poly_t(FLINTmipo, M)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
#define ASSERT(expression, message)
fq_nmod_ctx_clear(fq_con)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
Rational abs(const Rational &a)
int status int void * buf
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
TIMING_START(fac_alg_resultant)
CanonicalForm getGamma() const
getter
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
CFList *& Aeval
<[in] poly
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...
void intersect(const DegreePattern °Pat)
intersect two degree patterns
nmod_poly_init(FLINTmipo, getCharacteristic())
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval)
const CanonicalForm const modpk & b
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
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 &)
return mod(mulNTL(buf1, buf2, b), M)
void deleteFactors(CFList &factors, int *factorsFoundIndex)
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
CFList biSqrfFactorizeHelper(const CanonicalForm &G, const ExtensionInfo &info)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
generate random elements in GF
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...
int ipower(int b, int m)
int ipower ( int b, int m )
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval)
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm getDelta() const
getter
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
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
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
class to do operations mod p^k for int's p and k
int getLength() const
getter
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
void extEarlyFactorDetection(CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
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
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
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)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval)
const Variable & v
< [in] a sqrfree bivariate poly
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
const CanonicalForm int s
void subset(std::vector< int > &arr, int size, int left, int index, std::vector< int > &l, std::vector< std::vector< int > > &L)
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
int find(const int x) const
find an element x
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization of a squarefree bivariate polynomials over an arbitrary finite field,...
fq_nmod_poly_clear(prod, fq_con)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
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
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
const ExtensionInfo & info
< [in] sqrfree poly
void refine()
Refine a degree pattern. Assumes that (*this)[0]:= d is the degree of the poly to be factored....
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CFList extIncreasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision)
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 ,...