 |
My Project
debian-1:4.1.2-p1+ds-2
|
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "canonicalform.h"
#include "cf_defs.h"
#include "cf_map_ext.h"
#include "cf_random.h"
#include "facHensel.h"
#include "facMul.h"
#include "cf_map.h"
#include "cf_irred.h"
#include "facFqBivarUtil.h"
#include "facFqBivar.h"
#include "cfNewtonPolygon.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
Go to the source code of this file.
|
| TIMING_DEFINE_PRINT (fac_fq_uni_factorizer) TIMING_DEFINE_PRINT(fac_fq_bi_hensel_lift) TIMING_DEFINE_PRINT(fac_fq_bi_factor_recombination) TIMING_DEFINE_PRINT(fac_fq_bi_evaluation) TIMING_DEFINE_PRINT(fac_fq_bi_shift_to_zero) TIMING_DEFINE_PRINT(fac_fq_logarithmic) TIMING_DEFINE_PRINT(fac_fq_compute_lattice_lift) TIMING_DEFINE_PRINT(fac_fq_till_reduced) TIMING_DEFINE_PRINT(fac_fq_reconstruction) TIMING_DEFINE_PRINT(fac_fq_lift) TIMING_DEFINE_PRINT(fac_fq_uni_total) CanonicalForm prodMod0(const CFList &L |
|
else | if (L.length()==1) return mod(L.getFirst()(0 |
|
else L | getLast ()(0 |
|
| for (int j=1;j<=l;j++, i++) tmp1.append(i.getItem()) |
|
return | mod (mulNTL(buf1, buf2, b), M) |
|
CanonicalForm | evalPoint (const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail) |
| find an evaluation point p, s.t. F(p,y) is squarefree and . 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 &N, const ExtensionInfo &info, DegreePattern °s, const CanonicalForm &eval, int s, int thres) |
| naive factor recombination as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin. More...
|
|
CFList | factorRecombination (CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern °s, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den) |
| naive factor recombination as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin. More...
|
|
Variable | chooseExtension (const Variable &alpha, const Variable &beta, int k) |
| chooses a field extension. More...
|
|
void | earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, int deg, const CanonicalForm &eval, const modpk &b, CanonicalForm &den) |
|
void | earlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, int deg, const CanonicalForm &eval, const modpk &b) |
| detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
|
|
void | extEarlyFactorDetection (CFList &reconstructedFactors, CanonicalForm &F, CFList &factors, int &adaptedLiftBound, int *&factorsFoundIndex, DegreePattern °s, bool &success, const ExtensionInfo &info, const CanonicalForm &eval, int deg) |
| detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are tested. Lift bound and possible degree pattern are updated. More...
|
|
int * | getCombinations (int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC) |
|
int * | getLiftPrecisions (const CanonicalForm &F, int &sizeOfOutput, int degreeLC) |
| compute lifting precisions from the shape of the Newton polygon of F More...
|
|
void | deleteFactors (CFList &factors, int *factorsFoundIndex) |
|
CFList | henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den) |
| hensel Lifting and early factor detection More...
|
|
CFList | henselLiftAndEarly (CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval) |
| hensel Lifting and early factor detection More...
|
|
long | isReduced (const nmod_mat_t M) |
|
long | isReduced (const mat_zz_pE &M) |
|
int * | extractZeroOneVecs (const nmod_mat_t M) |
|
int * | extractZeroOneVecs (const mat_zz_pE &M) |
|
void | reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres) |
|
void | reconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, const CanonicalForm &eval, bool beenInThres) |
|
CFList | reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval) |
|
CFList | monicReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N) |
|
CFList | extReconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const ExtensionInfo &info, const CanonicalForm &evaluation) |
|
CFList | reconstruction (CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const CanonicalForm &eval) |
|
void | extReconstructionTry (CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation) |
|
int | liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible) |
|
int | extLiftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
|
int | liftAndComputeLattice (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_pE &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible) |
|
int | liftAndComputeLatticeFq2Fp (const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha) |
|
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, const CanonicalForm &eval) |
|
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &, int precision, const CanonicalForm &eval) |
|
CFList | extIncreasePrecision (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest, int precision) |
|
CFList | increasePrecision2 (const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision) |
|
CFList | increasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, int precision, const CanonicalForm &eval) |
|
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const CanonicalForm &eval) |
|
CFList | increasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, mat_zz_pE &NTLN, const CanonicalForm &eval) |
|
CFList | extIncreasePrecision (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
|
CFList | increasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int oldL, int l, int d, int *bounds, CFArray &bufQ, nmod_mat_t FLINTN, const Variable &alpha, const CanonicalForm &eval) |
|
CFList | furtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval) |
|
CFList | furtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, mat_zz_pE &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval) |
|
CFList | extFurtherLiftingAndIncreasePrecision (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest) |
|
CFList | furtherLiftingAndIncreasePrecisionFq2Fp (CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval) |
|
void | refineAndRestartLift (const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant) |
|
void | refineAndRestartLift (const CanonicalForm &F, const mat_zz_pE &NTLN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant) |
|
CFList | earlyReconstructionAndLifting (const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation) |
|
CFList | earlyReconstructionAndLifting (const CanonicalForm &F, const mat_zz_pE &N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation) |
|
CFList | extEarlyReconstructionAndLifting (const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation) |
|
CFList | sieveSmallFactors (const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval) |
|
CFList | extSieveSmallFactors (const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info) |
|
CFList | henselLiftAndLatticeRecombi (const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval) |
|
ExtensionInfo | init4ext (const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo) |
|
CFList | extHenselLiftAndLatticeRecombi (const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval) |
|
CFList | extBiFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
| Factorization over an extension of initial field. More...
|
|
CFList | biFactorize (const CanonicalForm &F, const ExtensionInfo &info) |
| bivariate factorization over finite fields as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin. More...
|
|
This file provides functions for factorizing a bivariate polynomial over
,
or GF, based on "Modern Computer
Algebra, Chapter 15" by J. von zur Gathen & J. Gerhard and "Factoring
multivariate polynomials over a finite field" by L. Bernardin. Factor Recombination is described in "Factoring polynomials over global
fields" by K. Belabas, M. van Hoeij, J. Klueners, A. Steel
- Author
- Martin Lee
Definition in file facFqBivar.cc.
◆ biFactorize()
bivariate factorization over finite fields as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin.
Factorization of a squarefree bivariate polynomials over an arbitrary finite field, information on the current field we work over is in info. info may also contain information about the initial field if initial and current field do not coincide. In this case the current field is an extension of the initial field and the factors returned are factors of F over the initial field.
- 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;
◆ 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);
◆ deleteFactors()
void deleteFactors |
( |
CFList & |
factors, |
|
|
int * |
factorsFoundIndex |
|
) |
| |
◆ earlyFactorDetection() [1/2]
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);
◆ earlyFactorDetection() [2/2]
void earlyFactorDetection |
( |
CFList & |
reconstructedFactors, |
|
|
CanonicalForm & |
F, |
|
|
CFList & |
factors, |
|
|
int & |
adaptedLiftBound, |
|
|
int *& |
factorsFoundIndex, |
|
|
DegreePattern & |
degs, |
|
|
bool & |
success, |
|
|
int |
deg, |
|
|
const CanonicalForm & |
eval, |
|
|
const modpk & |
b, |
|
|
CanonicalForm & |
den |
|
) |
| |
Definition at line 816 of file facFqBivar.cc.
873 if (!
Lc (
g).inBaseDomain())
884 factorsFoundIndex[
l]= 1;
910 if (!
buf.inCoeffDomain())
924 adaptedLiftBound= d + 1;
925 if (adaptedLiftBound < deg)
◆ earlyReconstructionAndLifting() [1/2]
CFList earlyReconstructionAndLifting |
( |
const CanonicalForm & |
F, |
|
|
const mat_zz_pE & |
N, |
|
|
CanonicalForm & |
bufF, |
|
|
CFList & |
factors, |
|
|
int & |
l, |
|
|
int & |
factorsFound, |
|
|
bool |
beenInThres, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFList & |
diophant, |
|
|
bool |
symmetric, |
|
|
const CanonicalForm & |
evaluation |
|
) |
| |
Definition at line 6330 of file facFqBivar.cc.
6343 int smallFactorDeg= 11;
6345 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6346 for (
long i= 0;
i < NTLN.NumCols();
i++)
6347 factorsFoundIndex [
i]= 0;
6349 if (
degree (F) + 1 > smallFactorDeg)
6351 if (
l < smallFactorDeg)
6361 factorsFoundIndex, NTLN,
evaluation, beenInThres
6364 if (
result.length() == NTLN.NumCols())
6367 delete [] factorsFoundIndex;
6372 int i= sizeOfLiftPre - 1;
6374 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6378 if (
l < liftPre[
i-1] + 1)
6384 l= liftPre[
i-1] + 1;
6394 factorsFoundIndex, NTLN,
evaluation, beenInThres
6397 if (
result.length() == NTLN.NumCols())
6400 delete [] factorsFoundIndex;
6409 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6421 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6436 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6441 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6450 if (check1/
Lc (check1) == check2/
Lc (check2))
6452 result.append (oldcheck1);
6455 delete [] factorsFoundIndex;
6468 factorsFoundIndex, NTLN,
evaluation, beenInThres
6471 if (
result.length() == NTLN.NumCols())
6474 delete [] factorsFoundIndex;
6482 delete [] factorsFoundIndex;
◆ earlyReconstructionAndLifting() [2/2]
CFList earlyReconstructionAndLifting |
( |
const CanonicalForm & |
F, |
|
|
const nmod_mat_t |
N, |
|
|
CanonicalForm & |
bufF, |
|
|
CFList & |
factors, |
|
|
int & |
l, |
|
|
int & |
factorsFound, |
|
|
bool |
beenInThres, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFList & |
diophant, |
|
|
bool |
symmetric, |
|
|
const CanonicalForm & |
evaluation |
|
) |
| |
Definition at line 6117 of file facFqBivar.cc.
6140 int smallFactorDeg=
tmin (11, liftPre [sizeOfLiftPre- 1] + 1);
6143 nmod_mat_init_set (FLINTN,
N);
6144 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6145 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6148 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6149 for (
long i= 0;
i < NTLN.NumCols();
i++)
6151 factorsFoundIndex [
i]= 0;
6153 if (
degree (F) + 1 > smallFactorDeg)
6155 if (
l < smallFactorDeg)
6166 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6169 if (
result.length() == nmod_mat_ncols (FLINTN))
6171 nmod_mat_clear (FLINTN);
6175 factorsFoundIndex, NTLN,
evaluation, beenInThres
6178 if (
result.length() == NTLN.NumCols())
6182 delete [] factorsFoundIndex;
6187 int i= sizeOfLiftPre - 1;
6189 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6193 if (
l < liftPre[
i-1] + 1)
6199 l= liftPre[
i-1] + 1;
6210 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6213 if (
result.length() == nmod_mat_ncols (FLINTN))
6215 nmod_mat_clear (FLINTN);
6219 factorsFoundIndex, NTLN,
evaluation, beenInThres
6222 if (
result.length() == NTLN.NumCols())
6226 delete [] factorsFoundIndex;
6235 while (((
degree (F,
y)/4)*
i+1) + 4 <= smallFactorDeg)
6247 if (
i == 1 &&
degree (F)%4==0 && symmetric && factors.
length() == 2 &&
6262 multiplier1= factors.
getLast()[
m-1][0]/gg[
m-1][0];
6267 multiplier2= factors.
getFirst()[
m-1][0]/hh[
m-1][0];
6276 if (check1/
Lc (check1) == check2/
Lc (check2))
6279 nmod_mat_clear (FLINTN);
6281 result.append (oldcheck1);
6284 delete [] factorsFoundIndex;
6298 factorsFoundIndex, FLINTN,
evaluation, beenInThres
6301 if (
result.length() == nmod_mat_ncols (FLINTN))
6303 nmod_mat_clear (FLINTN);
6307 factorsFoundIndex, NTLN,
evaluation, beenInThres
6310 if (
result.length() == NTLN.NumCols())
6314 delete [] factorsFoundIndex;
6322 nmod_mat_clear (FLINTN);
6325 delete [] factorsFoundIndex;
◆ 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)
◆ extEarlyReconstructionAndLifting()
CFList extEarlyReconstructionAndLifting |
( |
const CanonicalForm & |
F, |
|
|
const nmod_mat_t |
N, |
|
|
CanonicalForm & |
bufF, |
|
|
CFList & |
factors, |
|
|
int & |
l, |
|
|
int & |
factorsFound, |
|
|
bool |
beenInThres, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFList & |
diophant, |
|
|
const ExtensionInfo & |
info, |
|
|
const CanonicalForm & |
evaluation |
|
) |
| |
Definition at line 6489 of file facFqBivar.cc.
6513 int smallFactorDeg= 11;
6516 nmod_mat_init_set (FLINTN,
N);
6517 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
6518 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6521 int * factorsFoundIndex=
new int [NTLN.NumCols()];
6522 for (
long i= 0;
i < NTLN.NumCols();
i++)
6524 factorsFoundIndex [
i]= 0;
6526 if (
degree (F) + 1 > smallFactorDeg)
6528 if (
l < smallFactorDeg)
6539 factorsFoundIndex, FLINTN, beenInThres,
info,
6544 factorsFoundIndex, NTLN, beenInThres,
info,
6550 if (
result.length() == nmod_mat_ncols (FLINTN))
6552 nmod_mat_clear (FLINTN);
6554 if (
result.length() == NTLN.NumCols())
6558 delete [] factorsFoundIndex;
6563 int i= sizeOfLiftPre - 1;
6565 if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
6569 if (
l < liftPre[
i-1] + 1)
6575 l= liftPre[
i-1] + 1;
6586 factorsFoundIndex, FLINTN, beenInThres,
info,
6591 factorsFoundIndex, NTLN, beenInThres,
info,
6597 if (
result.length() == nmod_mat_ncols (FLINTN))
6599 nmod_mat_clear (FLINTN);
6601 if (
result.length() == NTLN.NumCols())
6605 delete [] factorsFoundIndex;
6614 while ((
degree (F,
y)/4+1)*
i + 4 <= smallFactorDeg)
6636 factorsFoundIndex, FLINTN, beenInThres,
info,
6641 factorsFoundIndex, NTLN, beenInThres,
info,
6647 if (
result.length() == nmod_mat_ncols (FLINTN))
6649 nmod_mat_clear (FLINTN);
6651 if (
result.length() == NTLN.NumCols())
6655 delete [] factorsFoundIndex;
6663 nmod_mat_clear (FLINTN);
6666 delete [] factorsFoundIndex;
◆ extFactorRecombination()
naive factor recombination as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin.
naive factor recombination over an extension of the initial field. Uses precomputed data to exclude combinations that are not possible.
- 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)
◆ extFurtherLiftingAndIncreasePrecision()
CFList extFurtherLiftingAndIncreasePrecision |
( |
CanonicalForm & |
F, |
|
|
CFList & |
factors, |
|
|
int |
l, |
|
|
int |
liftBound, |
|
|
int |
d, |
|
|
int * |
bounds, |
|
|
nmod_mat_t |
FLINTN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
const CanonicalForm & |
evaluation, |
|
|
const ExtensionInfo & |
info, |
|
|
CFList & |
source, |
|
|
CFList & |
dest |
|
) |
| |
Definition at line 5476 of file facFqBivar.cc.
5499 CFList bufFactors= factors;
5502 bool useOldQs=
false;
5503 bool hitBound=
false;
5514 nmod_mat_clear (FLINTN);
5516 for (
long i=factors.
length()-1;
i >= 0;
i--)
5517 nmod_mat_entry (FLINTN,
i,
i)= 1;
5519 if (NTLN.NumRows() != factors.
length())
5520 ident (NTLN, factors.
length());
5528 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
5530 mat_zz_p* NTLMat,*NTLC, NTLK;
5534 while (
l <= liftBound)
5544 for (
int i= 0;
i <
l*degMipo;
i++)
5548 imBasis= imBasis (
power (
y, degMipo),
y);
5549 imBasis= imBasis (
y, gamma);
5557 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
5559 nmod_mat_inv (FLINTMatInv, FLINTMat);
5562 *NTLMat= inv (*NTLMat);
5572 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5578 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5581 for (
int i= 0;
i < d;
i++)
5583 if (bounds [
i] + 1 <=
l/2)
5585 int k=
tmin (bounds [
i] + 1,
l/2);
5587 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5589 if (
A[ii].
size() - 1 >=
i)
5597 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5610 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
5630 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5632 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5633 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5635 rank= nmod_mat_nullspace (
null, FLINTK);
5636 nmod_mat_clear (FLINTK);
5637 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5638 nmod_mat_clear (FLINTC);
5639 nmod_mat_init_set (FLINTC, FLINTN);
5640 nmod_mat_clear (FLINTN);
5641 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5643 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5645 nmod_mat_clear (FLINTC);
5646 nmod_mat_window_clear (FLINTK);
5647 nmod_mat_clear (
null);
5651 transpose (NTLK, NTLK);
5652 kernel (NTLK, NTLK);
5653 transpose (NTLK, NTLK);
5662 if (nmod_mat_ncols (FLINTN) == 1)
5664 if (NTLN.NumCols() == 1)
5674 nmod_mat_clear (FLINTMat);
5675 nmod_mat_clear (FLINTMatInv);
5676 if (nmod_mat_ncols (FLINTN) == 1)
5679 if (NTLN.NumCols() == 1)
5687 bufBufFactors= bufFactors;
5699 delete [] zeroOneVecs;
5703 factors= bufFactors;
5710 bufFactors= bufBufFactors;
5719 int factorsFound= 0;
5722 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5723 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5725 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5726 for (
long i= 0;
i < NTLN.NumCols();
i++)
5728 factorsFoundIndex[
i]= 0;
5736 degree (
LCF), factorsFound, factorsFoundIndex,
5739 if (nmod_mat_ncols (FLINTN) ==
result.length())
5747 degree (
LCF), factorsFound, factorsFoundIndex,
5750 if (NTLN.NumCols() ==
result.length())
5754 delete [] factorsFoundIndex;
5757 delete [] factorsFoundIndex;
5784 factors= bufFactors;
◆ extHenselLiftAndLatticeRecombi()
Definition at line 7612 of file facFqBivar.cc.
7624 CFList bufUniFactors= uniFactors;
7644 int minBound= bounds[0];
7645 for (
int i= 1;
i < d;
i++)
7648 minBound=
tmin (minBound, bounds[
i]);
7660 bool success=
false;
7665 if (smallFactors.length() > 0)
7667 if (smallFactors.length() == 1)
7669 if (smallFactors.getFirst() == F)
7681 return smallFactors;
7708 return smallFactors;
7722 smallFactors.append (tmp);
7723 return smallFactors;
7727 minBound= bounds[0];
7728 for (
int i= 1;
i < d;
i++)
7731 minBound=
tmin (minBound, bounds[
i]);
7747 smallFactors.append (tmp);
7748 return smallFactors;
7757 nmod_mat_init (FLINTN, bufUniFactors.
length()-1, bufUniFactors.
length()-1,
7759 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
7760 nmod_mat_entry (FLINTN,
i,
i)= 1;
7770 ident (NTLN, bufUniFactors.
length() - 1);
7782 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
7787 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
7796 minBound+1, bufUniFactors, FLINTN, diophant,
7802 minBound + 1, bufUniFactors, NTLN, diophant,
7809 "time to compute a reduced lattice: ");
7812 if (oldL > liftBound)
7815 nmod_mat_clear (FLINTN);
7830 nmod_mat_clear (FLINTN);
7844 int * factorsFoundIndex;
7847 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7848 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7850 factorsFoundIndex=
new int [NTLN.NumCols()];
7851 for (
long i= 0;
i < NTLN.NumCols();
i++)
7853 factorsFoundIndex[
i]= 0;
7855 int factorsFound= 0;
7860 factorsFound, factorsFoundIndex, FLINTN,
false,
info,
7864 if (
result.length() == nmod_mat_ncols (FLINTN))
7866 nmod_mat_clear (FLINTN);
7869 factorsFound, factorsFoundIndex, NTLN,
false,
info,
7873 if (
result.length() == NTLN.NumCols())
7876 delete [] factorsFoundIndex;
7881 delete [] factorsFoundIndex;
7885 int * factorsFoundIndex;
7887 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7888 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7890 factorsFoundIndex=
new int [NTLN.NumCols()];
7891 for (
long i= 0;
i < NTLN.NumCols();
i++)
7893 factorsFoundIndex[
i]= 0;
7895 int factorsFound= 0;
7899 factorsFound, factorsFoundIndex, FLINTN,
false,
7903 if (
result.length() == nmod_mat_ncols (FLINTN))
7905 nmod_mat_clear (FLINTN);
7908 factorsFound, factorsFoundIndex, NTLN,
false,
7912 if (
result.length() == NTLN.NumCols())
7915 delete [] factorsFoundIndex;
7919 delete [] factorsFoundIndex;
7923 bool beenInThres=
false;
7926 if (
l <= thres && bufUniFactors.
length() > nmod_mat_ncols (FLINTN))
7932 if (
l <= thres && bufUniFactors.
length() > NTLN.NumCols())
7943 int factorsFound= 0;
7947 factorsFound, beenInThres,
M, Pi,
7951 if (
result.length() == nmod_mat_ncols (FLINTN))
7953 nmod_mat_clear (FLINTN);
7956 factorsFound, beenInThres,
M, Pi,
7960 if (
result.length() == NTLN.NumCols())
7997 CFList bufBufUniFactors= bufUniFactors;
8000 CFList factorsConsidered;
8002 for (
int i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
8004 for (
int i= 0;
i < NTLN.NumCols();
i++)
8007 if (zeroOne [
i] == 0)
8009 iter= bufUniFactors;
8011 factorsConsidered=
CFList();
8013 for (
int j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
8015 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
8017 for (
int j= 0;
j < NTLN.NumRows();
j++,
iter++)
8033 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
8038 bufUniFactors= bufBufUniFactors;
8046 #ifdef HAVE_FLINT //TODO
8047 oldNumCols= nmod_mat_ncols (FLINTN);
8052 nmod_mat_clear (FLINTN);
8054 oldNumCols= NTLN.NumCols();
8090 if (
l/degMipo < liftBound)
8097 if (
result.length()== nmod_mat_ncols (FLINTN))
8099 nmod_mat_clear (FLINTN);
8105 if (
result.length()== NTLN.NumCols())
8117 liftBound, d,bounds,FLINTN,
8118 diophant,
M, Pi, bufQ,
8122 if (
result.length()== nmod_mat_ncols (FLINTN))
8124 nmod_mat_clear (FLINTN);
8127 liftBound, d, bounds, NTLN,
8128 diophant,
M, Pi, bufQ,
8132 if (
result.length()== NTLN.NumCols())
8143 nmod_mat_clear (FLINTN);
8146 DEBOUTLN (cerr,
"lattice recombination failed");
8160 smallFactors.append (tmp);
8164 minBound= bounds[0];
8165 for (
int i= 1;
i < d;
i++)
8168 minBound=
tmin (minBound, bounds[
i]);
8171 if (minBound > 16 ||
result.length() == 0)
◆ extIncreasePrecision() [1/2]
Definition at line 3763 of file facFqBivar.cc.
3791 for (
long i=factors.
length()-1;
i >= 0;
i--)
3792 nmod_mat_entry (FLINTN,
i,
i)= 1;
3800 ident (NTLN, factors.
length());
3802 int minBound= bounds[0];
3803 for (
int i= 1;
i < d;
i++)
3806 minBound=
tmin (minBound, bounds[
i]);
3808 int l=
tmax (oldL, 2*((minBound+1)/degMipo+1));
3811 bool useOldQs=
false;
3812 bool hitBound=
false;
3823 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
3825 mat_zz_p* NTLMat,*NTLC, NTLK;
3828 while (
l <= precision)
3835 for (
int i= 0;
i <
l*degMipo;
i++)
3838 imBasis= imBasis (
power (
y, degMipo),
y);
3839 imBasis= imBasis (
y, gamma);
3847 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
3849 nmod_mat_inv (FLINTMatInv, FLINTMat);
3852 *NTLMat= inv (*NTLMat);
3861 for (
int i= 0;
i < factors.
length();
i++,
j++)
3868 for (
int i= 0;
i < factors.
length();
i++,
j++)
3872 for (
int i= 0;
i < d;
i++)
3874 if (bounds [
i] + 1 <= (
l/2)*degMipo)
3876 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
3878 for (
int ii= 0; ii < factors.
length(); ii++)
3880 if (
A[ii].
size() - 1 >=
i)
3888 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3901 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3921 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3923 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3924 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3926 rank= nmod_mat_nullspace (
null, FLINTK);
3927 nmod_mat_clear (FLINTK);
3928 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3929 nmod_mat_clear (FLINTC);
3930 nmod_mat_init_set (FLINTC, FLINTN);
3931 nmod_mat_clear (FLINTN);
3932 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3934 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3936 nmod_mat_clear (FLINTC);
3937 nmod_mat_window_clear (FLINTK);
3938 nmod_mat_clear (
null);
3942 transpose (NTLK, NTLK);
3943 kernel (NTLK, NTLK);
3944 transpose (NTLK, NTLK);
3953 if (nmod_mat_ncols (FLINTN) == 1)
3955 nmod_mat_clear (FLINTMat);
3956 nmod_mat_clear (FLINTMatInv);
3957 nmod_mat_clear (FLINTN);
3959 if (NTLN.NumCols() == 1)
3976 nmod_mat_clear (FLINTMat);
3977 nmod_mat_clear (FLINTMatInv);
3983 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3987 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3988 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3990 if (NTLN.NumCols() < oldNumCols - factorsFound)
3994 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3995 for (
long i= 0;
i < NTLN.NumCols();
i++)
3997 factorsFoundIndex[
i]= 0;
3998 int factorsFound2= 0;
4005 if (
result.length() == nmod_mat_ncols (FLINTN))
4007 nmod_mat_clear (FLINTN);
4012 if (
result.length() == NTLN.NumCols())
4015 delete [] factorsFoundIndex;
4021 delete [] factorsFoundIndex;
4023 else if (
l == precision)
4031 nmod_mat_clear (FLINTN);
4061 nmod_mat_clear (FLINTN);
◆ extIncreasePrecision() [2/2]
CFList extIncreasePrecision |
( |
CanonicalForm & |
F, |
|
|
CFList & |
factors, |
|
|
int |
oldL, |
|
|
int |
l, |
|
|
int |
d, |
|
|
int * |
bounds, |
|
|
CFArray & |
bufQ, |
|
|
nmod_mat_t |
FLINTN, |
|
|
const CanonicalForm & |
evaluation, |
|
|
const ExtensionInfo & |
info, |
|
|
CFList & |
source, |
|
|
CFList & |
dest |
|
) |
| |
Definition at line 4683 of file facFqBivar.cc.
4700 bool hitBound=
false;
4701 bool useOldQs=
false;
4710 nmod_mat_clear (FLINTN);
4712 for (
long i=factors.
length()-1;
i >= 0;
i--)
4713 nmod_mat_entry (FLINTN,
i,
i)= 1;
4715 if (NTLN.NumRows() != factors.
length())
4716 ident (NTLN, factors.
length());
4726 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
4728 mat_zz_p* NTLC, NTLK, *NTLMat;
4737 powX=
power (
y-gamma, oldL);
4738 Mat=
CFMatrix (oldL*degMipo, oldL*degMipo);
4739 for (
int i= 0;
i < oldL*degMipo;
i++)
4742 imBasis= imBasis (
power (
y, degMipo),
y);
4743 imBasis= imBasis (
y, gamma);
4751 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
4753 nmod_mat_inv (FLINTMatInv, FLINTMat);
4756 *NTLMat= inv (*NTLMat);
4765 for (
int i= 0;
i < factors.
length();
i++,
j++)
4771 for (
int i= 0;
i < factors.
length();
i++,
j++)
4776 for (
int i= 0;
i < d;
i++)
4778 if (bounds [
i] + 1 <= oldL/2)
4780 int k=
tmin (bounds [
i] + 1, oldL/2);
4782 for (
int ii= 0; ii < factors.
length(); ii++)
4784 if (
A[ii].
size() - 1 >=
i)
4792 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4805 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
4825 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4827 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4828 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4830 rank= nmod_mat_nullspace (
null, FLINTK);
4831 nmod_mat_clear (FLINTK);
4832 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
4833 nmod_mat_clear (FLINTC);
4834 nmod_mat_init_set (FLINTC, FLINTN);
4835 nmod_mat_clear (FLINTN);
4836 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4838 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4840 nmod_mat_clear (FLINTC);
4841 nmod_mat_window_clear (FLINTK);
4842 nmod_mat_clear (
null);
4846 transpose (NTLK, NTLK);
4847 kernel (NTLK, NTLK);
4848 transpose (NTLK, NTLK);
4857 if (nmod_mat_ncols (FLINTN) == 1)
4859 nmod_mat_clear (FLINTMat);
4860 nmod_mat_clear (FLINTMatInv);
4862 if (NTLN.NumCols() == 1)
4877 nmod_mat_clear (FLINTMat);
4878 nmod_mat_clear (FLINTMatInv);
4884 if (nmod_mat_ncols (FLINTN) == 1)
4886 if (NTLN.NumCols() == 1)
4899 bufUniFactors= factors;
4911 delete [] zeroOneVecs;
4915 factors= bufUniFactors;
◆ extLiftAndComputeLattice()
int extLiftAndComputeLattice |
( |
const CanonicalForm & |
F, |
|
|
int * |
bounds, |
|
|
int |
sizeBounds, |
|
|
int |
liftBound, |
|
|
int |
minBound, |
|
|
int |
start, |
|
|
CFList & |
factors, |
|
|
nmod_mat_t |
FLINTN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
bool & |
irreducible, |
|
|
const CanonicalForm & |
evaluation, |
|
|
const ExtensionInfo & |
info, |
|
|
CFList & |
source, |
|
|
CFList & |
dest |
|
) |
| |
Definition at line 2895 of file facFqBivar.cc.
2906 bool wasInBounds=
false;
2907 bool hitBound=
false;
2918 int l= ((minBound+1)/degMipo+1)*2;
2923 bool reduced=
false;
2931 nmod_mat_t FLINTMat, FLINTMatInv, FLINTC, FLINTK,
null;
2933 while (
l <= liftBound)
2955 for (
int i= 0;
i <
l*degMipo;
i++)
2958 imBasis= imBasis (
power (
y, degMipo),
y);
2959 imBasis= imBasis (
y, gamma);
2966 nmod_mat_init (FLINTMatInv, nmod_mat_nrows (FLINTMat),
2968 nmod_mat_inv (FLINTMatInv, FLINTMat);
2977 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2986 for (
int i= 0;
i < sizeBounds;
i++)
2988 if (bounds [
i] + 1 <= (
l/2)*degMipo)
2991 int k=
tmin (bounds [
i] + 1, (
l/2)*degMipo);
2994 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2996 if (
A[ii].
size() - 1 >=
i)
3004 A [ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3013 A[ii] [
i]=
mapDown (
A[ii] [
i], imPrimElemAlpha, primElemAlpha,
3028 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3030 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3031 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3033 rank= nmod_mat_nullspace (
null, FLINTK);
3034 nmod_mat_clear (FLINTK);
3035 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3036 nmod_mat_clear (FLINTC);
3037 nmod_mat_init_set (FLINTC, FLINTN);
3038 nmod_mat_clear (FLINTN);
3039 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3041 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3043 nmod_mat_clear (FLINTC);
3044 nmod_mat_window_clear (FLINTK);
3045 nmod_mat_clear (
null);
3050 if (nmod_mat_ncols (FLINTN) == 1)
3063 nmod_mat_clear (FLINTMat);
3064 nmod_mat_clear (FLINTMatInv);
3066 if (nmod_mat_ncols (FLINTN) == 1)
◆ extractZeroOneVecs() [1/2]
int* extractZeroOneVecs |
( |
const mat_zz_pE & |
M | ) |
|
Definition at line 1534 of file facFqBivar.cc.
1537 bool nonZeroOne=
false;
1538 int *
result=
new int [
M.NumCols()];
1539 for (
i = 1;
i <=
M.NumCols();
i++)
1541 for (
j = 1;
j <=
M.NumRows();
j++)
◆ extractZeroOneVecs() [2/2]
int* extractZeroOneVecs |
( |
const nmod_mat_t |
M | ) |
|
Definition at line 1509 of file facFqBivar.cc.
1512 bool nonZeroOne=
false;
1513 int *
result=
new int [nmod_mat_ncols (
M)];
1514 for (
i = 0;
i < nmod_mat_ncols (
M);
i++)
1516 for (
j = 0;
j < nmod_mat_nrows (
M);
j++)
1518 if (!((nmod_mat_entry (
M,
j,
i) == 1) || (nmod_mat_entry (
M,
j,
i) == 0)))
◆ extReconstruction()
Definition at line 1991 of file facFqBivar.cc.
2006 CFList bufFactors= factors;
2007 CFList factorsConsidered;
2010 for (
long i= 0;
i < nmod_mat_ncols(
N);
i++)
2012 if (zeroOneVecs [
i] == 0)
2016 factorsConsidered=
CFList();
2017 for (
long j= 0;
j < nmod_mat_nrows(
N);
j++,
iter++)
2019 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2038 bufFactors=
Difference (bufFactors, factorsConsidered);
2053 bufFactors=
Difference (bufFactors, factorsConsidered);
2060 factors= bufFactors;
2065 factors= bufFactors;
◆ extReconstructionTry()
Definition at line 2304 of file facFqBivar.cc.
2319 if (factors.
length() == 2)
2329 if (tmp3/
Lc (tmp3) == F/
Lc (F))
2361 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2363 if (factorsFoundIndex [
i] == 1)
2379 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2381 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2395 factorsFoundIndex[
i]= 1;
2410 factorsFoundIndex[
i]= 1;
2421 if (factorsFound + 1 == nmod_mat_nrows (
N))
2425 reconstructedFactors.
append (tmp);
◆ extSieveSmallFactors()
CFList extSieveSmallFactors |
( |
const CanonicalForm & |
G, |
|
|
CFList & |
uniFactors, |
|
|
DegreePattern & |
degPat, |
|
|
CanonicalForm & |
H, |
|
|
CFList & |
diophant, |
|
|
CFArray & |
Pi, |
|
|
CFMatrix & |
M, |
|
|
bool & |
success, |
|
|
int |
d, |
|
|
const CanonicalForm & |
evaluation, |
|
|
const ExtensionInfo & |
info |
|
) |
| |
Definition at line 6716 of file facFqBivar.cc.
6723 CFList bufUniFactors= uniFactors;
6725 int smallFactorDeg= d;
6727 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6728 int adaptedLiftBound;
6730 int * factorsFoundIndex=
new int [uniFactors.
length()];
6731 for (
int i= 0;
i < uniFactors.
length();
i++)
6732 factorsFoundIndex [
i]= 0;
6737 delete [] factorsFoundIndex;
6741 return earlyFactors;
6746 return earlyFactors;
6749 int sizeOldF=
size (
G);
6750 if (
size (F) < sizeOldF)
6754 return earlyFactors;
6758 uniFactors= bufUniFactors;
◆ factorRecombination()
naive factor recombination as decribed in "Factoring
multivariate polynomials over a finite field" by L Bernardin.
naive factor recombination. Uses precomputed data to exclude combinations that are not possible.
- 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)
◆ for()
for |
( |
int |
j = 1;j<=l;j++ , |
|
|
i++ |
|
|
) |
| |
◆ furtherLiftingAndIncreasePrecision() [1/2]
CFList furtherLiftingAndIncreasePrecision |
( |
CanonicalForm & |
F, |
|
|
CFList & |
factors, |
|
|
int |
l, |
|
|
int |
liftBound, |
|
|
int |
d, |
|
|
int * |
bounds, |
|
|
mat_zz_pE & |
NTLN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
const CanonicalForm & |
eval |
|
) |
| |
Definition at line 5330 of file facFqBivar.cc.
5340 CFList bufFactors= factors;
5343 bool useOldQs=
false;
5344 bool hitBound=
false;
5348 if (NTLN.NumRows() != factors.
length())
5349 ident (NTLN, factors.
length());
5352 mat_zz_pE* NTLC, NTLK;
5355 while (
l <= liftBound)
5363 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5369 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5372 for (
int i= 0;
i < d;
i++)
5374 if (bounds [
i] + 1 <=
l/2)
5376 int k=
tmin (bounds [
i] + 1,
l/2);
5378 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5380 if (
A[ii].
size() - 1 >=
i)
5388 transpose (NTLK, NTLK);
5389 kernel (NTLK, NTLK);
5390 transpose (NTLK, NTLK);
5393 if (NTLN.NumCols() == 1)
5400 if (NTLN.NumCols() == 1)
5408 bufBufFactors= bufFactors;
5410 delete [] zeroOneVecs;
5414 factors= bufFactors;
5421 bufFactors= bufBufFactors;
5426 int factorsFound= 0;
5428 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5429 for (
long i= 0;
i < NTLN.NumCols();
i++)
5430 factorsFoundIndex[
i]= 0;
5433 factorsFoundIndex, NTLN,
eval,
false
5437 degree (
LCF), factorsFound, factorsFoundIndex,
5440 if (NTLN.NumCols() ==
result.length())
5443 delete [] factorsFoundIndex;
5446 delete [] factorsFoundIndex;
5469 factors= bufFactors;
◆ furtherLiftingAndIncreasePrecision() [2/2]
CFList furtherLiftingAndIncreasePrecision |
( |
CanonicalForm & |
F, |
|
|
CFList & |
factors, |
|
|
int |
l, |
|
|
int |
liftBound, |
|
|
int |
d, |
|
|
int * |
bounds, |
|
|
nmod_mat_t |
FLINTN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
const CanonicalForm & |
eval |
|
) |
| |
Definition at line 5097 of file facFqBivar.cc.
5116 CFList bufFactors= factors;
5119 bool useOldQs=
false;
5120 bool hitBound=
false;
5125 if (nmod_mat_nrows (FLINTN) != factors.
length())
5127 nmod_mat_clear (FLINTN);
5129 for (
long i=factors.
length()-1;
i >= 0;
i--)
5130 nmod_mat_entry (FLINTN,
i,
i)= 1;
5133 if (NTLN.NumRows() != factors.
length())
5134 ident (NTLN, factors.
length());
5141 nmod_mat_t FLINTC, FLINTK,
null;
5143 mat_zz_p* NTLC, NTLK;
5147 while (
l <= liftBound)
5155 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5161 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5164 for (
int i= 0;
i < d;
i++)
5166 if (bounds [
i] + 1 <=
l/2)
5168 int k=
tmin (bounds [
i] + 1,
l/2);
5170 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5172 if (
A[ii].
size() - 1 >=
i)
5180 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5182 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5183 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5185 rank= nmod_mat_nullspace (
null, FLINTK);
5186 nmod_mat_clear (FLINTK);
5187 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5188 nmod_mat_clear (FLINTC);
5189 nmod_mat_init_set (FLINTC, FLINTN);
5190 nmod_mat_clear (FLINTN);
5191 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5193 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5195 nmod_mat_clear (FLINTC);
5196 nmod_mat_window_clear (FLINTK);
5197 nmod_mat_clear (
null);
5201 transpose (NTLK, NTLK);
5202 kernel (NTLK, NTLK);
5203 transpose (NTLK, NTLK);
5208 if (nmod_mat_ncols (FLINTN) == 1)
5210 if (NTLN.NumCols() == 1)
5220 if (nmod_mat_ncols (FLINTN) == 1)
5222 if (NTLN.NumCols() == 1)
5235 bufBufFactors= bufFactors;
5241 delete [] zeroOneVecs;
5245 factors= bufFactors;
5252 bufFactors= bufBufFactors;
5261 int factorsFound= 0;
5264 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5265 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5267 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5268 for (
long i= 0;
i < NTLN.NumCols();
i++)
5270 factorsFoundIndex[
i]= 0;
5274 factorsFoundIndex, FLINTN,
eval,
false
5278 degree (
LCF), factorsFound, factorsFoundIndex,
5282 if (nmod_mat_ncols (FLINTN) ==
result.length())
5286 factorsFoundIndex, NTLN,
eval,
false
5290 degree (
LCF), factorsFound, factorsFoundIndex,
5294 if (NTLN.NumCols() ==
result.length())
5298 delete [] factorsFoundIndex;
5301 delete [] factorsFoundIndex;
5324 factors= bufFactors;
◆ furtherLiftingAndIncreasePrecisionFq2Fp()
CFList furtherLiftingAndIncreasePrecisionFq2Fp |
( |
CanonicalForm & |
F, |
|
|
CFList & |
factors, |
|
|
int |
l, |
|
|
int |
liftBound, |
|
|
int |
d, |
|
|
int * |
bounds, |
|
|
nmod_mat_t |
FLINTN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
const Variable & |
alpha, |
|
|
const CanonicalForm & |
eval |
|
) |
| |
Definition at line 5790 of file facFqBivar.cc.
5811 CFList bufFactors= factors;
5814 bool useOldQs=
false;
5816 bool hitBound=
false;
5821 if (nmod_mat_nrows (FLINTN) != factors.
length())
5823 nmod_mat_clear (FLINTN);
5825 for (
long i=factors.
length()-1;
i >= 0;
i--)
5826 nmod_mat_entry (FLINTN,
i,
i)= 1;
5829 if (NTLN.NumRows() != factors.
length())
5830 ident (NTLN, factors.
length());
5836 nmod_mat_t FLINTC, FLINTK,
null;
5838 mat_zz_p* NTLC, NTLK;
5842 while (
l <= liftBound)
5850 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5856 for (
int i= 0;
i < bufFactors.
length();
i++,
j++)
5859 for (
int i= 0;
i < d;
i++)
5861 if (bounds [
i] + 1 <=
l/2)
5863 int k=
tmin (bounds [
i] + 1,
l/2);
5865 for (
int ii= 0; ii < bufFactors.
length(); ii++)
5868 if (
A[ii].
size() - 1 >=
i)
5876 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5878 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5879 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5881 rank= nmod_mat_nullspace (
null, FLINTK);
5882 nmod_mat_clear (FLINTK);
5883 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5884 nmod_mat_clear (FLINTC);
5885 nmod_mat_init_set (FLINTC, FLINTN);
5886 nmod_mat_clear (FLINTN);
5887 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5889 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5891 nmod_mat_clear (FLINTC);
5892 nmod_mat_window_clear (FLINTK);
5893 nmod_mat_clear (
null);
5897 transpose (NTLK, NTLK);
5898 kernel (NTLK, NTLK);
5899 transpose (NTLK, NTLK);
5904 if (nmod_mat_ncols (FLINTN) == 1)
5906 if (NTLN.NumCols() == 1)
5915 if (nmod_mat_ncols (FLINTN) == 1)
5917 if (NTLN.NumCols() == 1)
5930 bufBufFactors= bufFactors;
5936 delete [] zeroOneVecs;
5940 factors= bufFactors;
5947 bufFactors= bufBufFactors;
5956 int factorsFound= 0;
5959 int* factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
5960 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
5962 int* factorsFoundIndex=
new int [NTLN.NumCols()];
5963 for (
long i= 0;
i < NTLN.NumCols();
i++)
5965 factorsFoundIndex[
i]= 0;
5969 factorsFoundIndex, FLINTN,
eval,
false
5973 degree (
LCF), factorsFound, factorsFoundIndex,
5976 if (nmod_mat_ncols (FLINTN) ==
result.length())
5980 factorsFoundIndex, NTLN,
eval,
false
5984 degree (
LCF), factorsFound, factorsFoundIndex,
5987 if (NTLN.NumCols() ==
result.length())
5991 delete [] factorsFoundIndex;
5994 delete [] factorsFoundIndex;
6017 factors= bufFactors;
◆ getCombinations()
int* getCombinations |
( |
int * |
rightSide, |
|
|
int |
sizeOfRightSide, |
|
|
int & |
sizeOfOutput, |
|
|
int |
degreeLC |
|
) |
| |
Definition at line 1045 of file facFqBivar.cc.
1054 for (
int i= 0;
i < sizeOfRightSide;
i++)
1060 if (
i.exp() < degreeLC)
1067 ASSERT (
j > 1,
"j > 1 expected" );
1069 int*
result =
new int [
j - 1];
1070 sizeOfOutput=
j - 1;
◆ getLast()
◆ 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;
◆ 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;
◆ henselLiftAndLatticeRecombi()
Definition at line 6764 of file facFqBivar.cc.
6782 int minBound= bounds[0];
6783 for (
int i= 1;
i < d;
i++)
6786 minBound=
tmin (minBound, bounds[
i]);
6789 CFList bufUniFactors= uniFactors;
6797 bool success=
false;
6799 success, minBound + 1,
eval
6802 if (smallFactors.length() > 0)
6804 if (smallFactors.length() == 1)
6806 if (smallFactors.getFirst() == F)
6815 return smallFactors;
6842 return smallFactors;
6852 smallFactors.append (F (
y-
eval,
y));
6854 return smallFactors;
6858 minBound= bounds[0];
6859 for (
int i= 1;
i < d;
i++)
6862 minBound=
tmin (minBound, bounds[
i]);
6873 smallFactors.append (F (
y-
eval,
y));
6875 return smallFactors;
6897 zz_pE::init (NTLMipo);
6904 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
6905 nmod_mat_entry (FLINTN,
i,
i)= 1;
6907 ident (NTLN, bufUniFactors.
length() - 1);
6916 for (
long i= bufUniFactors.
length()-2;
i >= 0;
i--)
6917 nmod_mat_entry (FLINTN,
i,
i)= 1;
6920 ident (NTLN, bufUniFactors.
length() - 1);
6923 ident (NTLNe, bufUniFactors.
length() - 1);
6936 bufUniFactors, FLINTN, diophant,
M, Pi, bufQ,
6938 bufUniFactors, NTLN, diophant,
M, Pi, bufQ,
6947 minBound, bufUniFactors, FLINTN,
6949 minBound, bufUniFactors, NTLN,
6956 bufUniFactors, NTLNe, diophant,
M, Pi, bufQ,
6967 minBound, bufUniFactors, FLINTN, diophant,
M,
6969 minBound, bufUniFactors, NTLN, diophant,
M,
6978 liftBound, minBound, bufUniFactors,
6980 FLINTN, diophant,
M, Pi, bufQ,
6982 NTLN, diophant,
M, Pi, bufQ,
6988 minBound, bufUniFactors, NTLNe, diophant,
6995 "time to compute a reduced lattice: ");
6996 bufUniFactors.removeFirst();
6997 if (oldL > liftBound)
7001 nmod_mat_clear (FLINTN);
7004 return Union (smallFactors,
7017 nmod_mat_clear (FLINTN);
7028 int * factorsFoundIndex;
7032 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7033 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7035 factorsFoundIndex=
new int [NTLN.NumCols()];
7036 for (
long i= 0;
i < NTLN.NumCols();
i++)
7038 factorsFoundIndex[
i]= 0;
7042 factorsFoundIndex=
new int [NTLNe.NumCols()];
7043 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7044 factorsFoundIndex[
i]= 0;
7046 int factorsFound= 0;
7051 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7053 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7058 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7063 if (
result.length() == nmod_mat_ncols (FLINTN))
7066 nmod_mat_clear (FLINTN);
7068 if (
result.length() == NTLN.NumCols())
7071 delete [] factorsFoundIndex;
7078 if (
result.length() == NTLNe.NumCols())
7080 delete [] factorsFoundIndex;
7085 delete [] factorsFoundIndex;
7089 int * factorsFoundIndex;
7093 factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
7094 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
7096 factorsFoundIndex=
new int [NTLN.NumCols()];
7097 for (
long i= 0;
i < NTLN.NumCols();
i++)
7099 factorsFoundIndex[
i]= 0;
7103 factorsFoundIndex=
new int [NTLNe.NumCols()];
7104 for (
long i= 0;
i < NTLNe.NumCols();
i++)
7105 factorsFoundIndex[
i]= 0;
7108 int factorsFound= 0;
7112 factorsFound, factorsFoundIndex, FLINTN,
eval,
false
7114 factorsFound, factorsFoundIndex, NTLN,
eval,
false
7119 factorsFound, factorsFoundIndex, NTLNe,
eval,
false
7124 if (
result.length() == nmod_mat_ncols(FLINTN))
7126 nmod_mat_clear (FLINTN);
7128 if (
result.length() == NTLN.NumCols())
7131 delete [] factorsFoundIndex;
7138 if (
result.length() == NTLNe.NumCols())
7140 delete [] factorsFoundIndex;
7145 delete [] factorsFoundIndex;
7149 bool beenInThres=
false;
7156 if (nmod_mat_ncols (FLINTN) < bufUniFactors.length())
7160 if (NTLN.NumCols() < bufUniFactors.length())
7171 if (NTLNe.NumCols() < bufUniFactors.length())
7182 int factorsFound= 0;
7190 factorsFound, beenInThres,
M, Pi,
7191 diophant, symmetric,
eval
7195 if (
result.length() == nmod_mat_ncols (FLINTN))
7197 nmod_mat_clear (FLINTN);
7199 if (
result.length() == NTLN.NumCols())
7209 factorsFound, beenInThres,
M, Pi,
7210 diophant, symmetric,
eval
7213 if (
result.length() == NTLNe.NumCols())
7246 long numCols, numRows;
7250 numCols= nmod_mat_ncols (FLINTN);
7251 numRows= nmod_mat_nrows (FLINTN);
7254 numCols= NTLN.NumCols();
7255 numRows= NTLN.NumRows();
7261 numCols= NTLNe.NumCols();
7262 numRows= NTLNe.NumRows();
7265 CFList bufBufUniFactors= bufUniFactors;
7268 CFList factorsConsidered;
7270 for (
int i= 0;
i < numCols;
i++)
7272 if (zeroOne [
i] == 0)
7274 iter= bufUniFactors;
7276 factorsConsidered=
CFList();
7277 for (
int j= 0;
j < numRows;
j++,
iter++)
7282 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
7307 bufBufUniFactors=
Difference (bufBufUniFactors, factorsConsidered);
7312 bufUniFactors= bufBufUniFactors;
7323 oldNumCols= nmod_mat_ncols (FLINTN);
7325 oldNumCols= NTLN.NumCols();
7328 oldNumCols, oldL,
l,
eval
7336 oldNumCols= nmod_mat_ncols (FLINTN);
7338 oldNumCols= NTLN.NumCols();
7347 oldNumCols= NTLNe.NumCols();
7355 if (bufUniFactors.isEmpty() ||
degree (bufF) <= 0)
7359 nmod_mat_clear (FLINTN);
7375 if (degs.
getLength() == 1 || bufUniFactors.length() == 1)
7379 nmod_mat_clear (FLINTN);
7386 nmod_mat_clear (FLINTN);
7389 alpha, degs, symmetric,
7429 if (
result.length()== nmod_mat_ncols (FLINTN))
7431 nmod_mat_clear (FLINTN);
7433 if (
result.length()== NTLN.NumCols())
7443 if (
result.length()== NTLNe.NumCols())
7456 liftBound,d,bounds,FLINTN,
7458 liftBound, d, bounds, NTLN,
7460 diophant,
M, Pi, bufQ,
eval
7466 liftBound, d, bounds,
7468 FLINTN, diophant,
M,
7476 liftBound, d, bounds,
7485 if (
result.length() == nmod_mat_ncols (FLINTN))
7487 nmod_mat_clear (FLINTN);
7489 if (
result.length() == NTLN.NumCols())
7499 if (
result.length() == NTLNe.NumCols())
7509 DEBOUTLN (cerr,
"lattice recombination failed");
7519 nmod_mat_clear (FLINTN);
7528 minBound= bounds[0];
7529 for (
int i= 1;
i < d;
i++)
7532 minBound=
tmin (minBound, bounds[
i]);
7535 if (minBound > 16 ||
result.length() == 0)
7552 degs,symmetric,
eval
◆ if()
else if |
( |
L. |
length() = = 1 | ) |
|
◆ increasePrecision() [1/4]
Definition at line 3623 of file facFqBivar.cc.
3642 ident (NTLN, factors.
length());
3643 int minBound= bounds[0];
3644 for (
int i= 1;
i < d;
i++)
3647 minBound=
tmin (minBound, bounds[
i]);
3649 int l=
tmax (2*(minBound + 1), oldL);
3652 bool useOldQs=
false;
3653 bool hitBound=
false;
3656 mat_zz_pE* NTLC, NTLK;
3659 while (
l <= precision)
3665 for (
int i= 0;
i < factors.
length();
i++,
j++)
3672 for (
int i= 0;
i < factors.
length();
i++,
j++)
3676 for (
int i= 0;
i < d;
i++)
3678 if (bounds [
i] + 1 <=
l/2)
3680 int k=
tmin (bounds [
i] + 1,
l/2);
3682 for (
int ii= 0; ii < factors.
length(); ii++)
3684 if (
A[ii].
size() - 1 >=
i)
3692 transpose (NTLK, NTLK);
3693 kernel (NTLK, NTLK);
3694 transpose (NTLK, NTLK);
3697 if (NTLN.NumCols() == 1)
3708 if (NTLN.NumCols() < oldNumCols - factorsFound)
3712 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3713 for (
long i= 0;
i < NTLN.NumCols();
i++)
3714 factorsFoundIndex[
i]= 0;
3715 int factorsFound2= 0;
3719 factorsFoundIndex, NTLN,
eval,
false);
3720 if (
result.length() == NTLN.NumCols())
3722 delete [] factorsFoundIndex;
3728 delete [] factorsFoundIndex;
3730 else if (
l == precision)
◆ increasePrecision() [2/4]
Definition at line 3416 of file facFqBivar.cc.
3437 for (
long i=factors.
length()-1;
i >= 0;
i--)
3438 nmod_mat_entry (FLINTN,
i,
i)= 1;
3441 ident (NTLN, factors.
length());
3443 int minBound= bounds[0];
3444 for (
int i= 1;
i < d;
i++)
3447 minBound=
tmin (minBound, bounds[
i]);
3449 int l=
tmax (2*(minBound + 1), oldL);
3452 bool useOldQs=
false;
3453 bool hitBound=
false;
3459 nmod_mat_t FLINTC, FLINTK,
null;
3461 mat_zz_p* NTLC, NTLK;
3464 while (
l <= precision)
3470 for (
int i= 0;
i < factors.
length();
i++,
j++)
3477 for (
int i= 0;
i < factors.
length();
i++,
j++)
3481 for (
int i= 0;
i < d;
i++)
3483 if (bounds [
i] + 1 <=
l/2)
3485 int k=
tmin (bounds [
i] + 1,
l/2);
3487 for (
int ii= 0; ii < factors.
length(); ii++)
3489 if (
A[ii].
size() - 1 >=
i)
3497 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3499 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3500 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3502 rank= nmod_mat_nullspace (
null, FLINTK);
3503 nmod_mat_clear (FLINTK);
3504 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3505 nmod_mat_clear (FLINTC);
3506 nmod_mat_init_set (FLINTC, FLINTN);
3507 nmod_mat_clear (FLINTN);
3508 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3510 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3512 nmod_mat_clear (FLINTC);
3513 nmod_mat_window_clear (FLINTK);
3514 nmod_mat_clear (
null);
3518 transpose (NTLK, NTLK);
3519 kernel (NTLK, NTLK);
3520 transpose (NTLK, NTLK);
3525 if (nmod_mat_ncols (FLINTN) == 1)
3527 nmod_mat_clear (FLINTN);
3529 if (NTLN.NumCols() == 1)
3542 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
3546 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
3547 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
3549 if (NTLN.NumCols() < oldNumCols - factorsFound)
3553 int * factorsFoundIndex=
new int [NTLN.NumCols()];
3554 for (
long i= 0;
i < NTLN.NumCols();
i++)
3556 factorsFoundIndex[
i]= 0;
3557 int factorsFound2= 0;
3562 factorsFoundIndex, FLINTN,
eval,
false
3564 if (
result.length() == nmod_mat_ncols (FLINTN))
3566 nmod_mat_clear (FLINTN);
3569 factorsFoundIndex, NTLN,
eval,
false
3571 if (
result.length() == NTLN.NumCols())
3574 delete [] factorsFoundIndex;
3580 delete [] factorsFoundIndex;
3582 else if (
l == precision)
3588 nmod_mat_clear (FLINTN);
3615 nmod_mat_clear (FLINTN);
◆ increasePrecision() [3/4]
Definition at line 4576 of file facFqBivar.cc.
4584 bool hitBound=
false;
4585 bool useOldQs=
false;
4586 if (NTLN.NumRows() != factors.
length())
4587 ident (NTLN, factors.
length());
4591 mat_zz_pE* NTLC, NTLK;
4601 for (
int i= 0;
i < factors.
length();
i++,
j++)
4608 for (
int i= 0;
i < factors.
length();
i++,
j++)
4613 for (
int i= 0;
i < d;
i++)
4615 if (bounds [
i] + 1 <= oldL/2)
4617 int k=
tmin (bounds [
i] + 1, oldL/2);
4619 for (
int ii= 0; ii < factors.
length(); ii++)
4621 if (
A[ii].
size() - 1 >=
i)
4629 transpose (NTLK, NTLK);
4630 kernel (NTLK, NTLK);
4631 transpose (NTLK, NTLK);
4635 if (NTLN.NumCols() == 1)
4642 if (NTLN.NumCols() == 1)
4651 bufUniFactors= factors;
4653 delete [] zeroOneVecs;
4657 factors= bufUniFactors;
◆ increasePrecision() [4/4]
Definition at line 4409 of file facFqBivar.cc.
4424 bool hitBound=
false;
4426 if (nmod_mat_nrows (FLINTN) != factors.
length())
4428 nmod_mat_clear (FLINTN);
4430 for (
long i=factors.
length()-1;
i >= 0;
i--)
4431 nmod_mat_entry (FLINTN,
i,
i)= 1;
4435 if (NTLN.NumRows() != factors.
length())
4437 ident (NTLN, factors.
length());
4441 bool useOldQs=
false;
4447 nmod_mat_t FLINTC, FLINTK,
null;
4449 mat_zz_p* NTLC, NTLK;
4460 for (
int i= 0;
i < factors.
length();
i++,
j++)
4467 for (
int i= 0;
i < factors.
length();
i++,
j++)
4472 for (
int i= 0;
i < d;
i++)
4474 if (bounds [
i] + 1 <= oldL/2)
4476 int k=
tmin (bounds [
i] + 1, oldL/2);
4478 for (
int ii= 0; ii < factors.
length(); ii++)
4480 if (
A[ii].
size() - 1 >=
i)
4488 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4490 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4491 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4493 rank= nmod_mat_nullspace (
null, FLINTK);
4494 nmod_mat_clear (FLINTK);
4495 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
4496 nmod_mat_clear (FLINTC);
4497 nmod_mat_init_set (FLINTC, FLINTN);
4498 nmod_mat_clear (FLINTN);
4499 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4501 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4503 nmod_mat_clear (FLINTC);
4504 nmod_mat_window_clear (FLINTK);
4505 nmod_mat_clear (
null);
4509 transpose (NTLK, NTLK);
4510 kernel (NTLK, NTLK);
4511 transpose (NTLK, NTLK);
4516 if (nmod_mat_ncols (FLINTN) == 1)
4518 if (NTLN.NumCols() == 1)
4527 if (nmod_mat_ncols (FLINTN) == 1)
4529 if (NTLN.NumCols() == 1)
4542 bufUniFactors= factors;
4548 delete [] zeroOneVecs;
4552 factors= bufUniFactors;
◆ increasePrecision2()
Definition at line 4069 of file facFqBivar.cc.
4088 zz_pE::init (NTLMipo);
4090 ident (NTLN, factors.
length());
4091 int minBound= bounds[0];
4092 for (
int i= 1;
i < d;
i++)
4095 minBound=
tmin (minBound, bounds[
i]);
4097 int l=
tmin (2*(minBound + 1), precision);
4100 bool useOldQs=
false;
4101 bool hitBound=
false;
4105 mat_zz_pE* NTLC, NTLK;
4108 while (
l <= precision)
4114 for (
int i= 0;
i < factors.
length();
i++,
j++)
4119 for (
int i= 0;
i < factors.
length();
i++,
j++)
4123 for (
int i= 0;
i < d;
i++)
4125 if (bounds [
i] + 1 <=
l/2)
4127 int k=
tmin (bounds [
i] + 1,
l/2);
4129 for (
int ii= 0; ii < factors.
length(); ii++)
4131 if (
A[ii].
size() - 1 >=
i)
4139 transpose (NTLK, NTLK);
4140 kernel (NTLK, NTLK);
4141 transpose (NTLK, NTLK);
4145 if (NTLN.NumCols() == 1)
4158 CFList bufFactors= factors;
4162 if (
result.length() != NTLN.NumCols() &&
l != precision)
4163 factors= bufFactors;
4164 if (
result.length() == NTLN.NumCols())
◆ increasePrecisionFq2Fp() [1/2]
Definition at line 4200 of file facFqBivar.cc.
4222 for (
long i=factors.
length()-1;
i >= 0;
i--)
4223 nmod_mat_entry (FLINTN,
i,
i)= 1;
4226 ident (NTLN, factors.
length());
4228 int minBound= bounds[0];
4229 for (
int i= 1;
i < d;
i++)
4232 minBound=
tmin (minBound, bounds[
i]);
4234 int l=
tmax (2*(minBound + 1), oldL);
4237 bool useOldQs=
false;
4238 bool hitBound=
false;
4243 nmod_mat_t FLINTC, FLINTK,
null;
4245 mat_zz_p* NTLC, NTLK;
4249 while (
l <= precision)
4255 for (
int i= 0;
i < factors.
length();
i++,
j++)
4262 for (
int i= 0;
i < factors.
length();
i++,
j++)
4266 for (
int i= 0;
i < d;
i++)
4268 if (bounds [
i] + 1 <=
l/2)
4270 int k=
tmin (bounds [
i] + 1,
l/2);
4272 for (
int ii= 0; ii < factors.
length(); ii++)
4274 if (
A[ii].
size() - 1 >=
i)
4282 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
4284 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
4285 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
4287 rank= nmod_mat_nullspace (
null, FLINTK);
4288 nmod_mat_clear (FLINTK);
4289 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
4290 nmod_mat_clear (FLINTC);
4291 nmod_mat_init_set (FLINTC, FLINTN);
4292 nmod_mat_clear (FLINTN);
4293 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
4295 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
4297 nmod_mat_clear (FLINTC);
4298 nmod_mat_window_clear (FLINTK);
4299 nmod_mat_clear (
null);
4303 transpose (NTLK, NTLK);
4304 kernel (NTLK, NTLK);
4305 transpose (NTLK, NTLK);
4310 if (nmod_mat_ncols (FLINTN) == 1)
4312 nmod_mat_clear (FLINTN);
4314 if (NTLN.NumCols() == 1)
4327 if (nmod_mat_ncols (FLINTN) < oldNumCols - factorsFound)
4331 int * factorsFoundIndex=
new int [nmod_mat_ncols (FLINTN)];
4332 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
4334 if (NTLN.NumCols() < oldNumCols - factorsFound)
4338 int * factorsFoundIndex=
new int [NTLN.NumCols()];
4339 for (
long i= 0;
i < NTLN.NumCols();
i++)
4341 factorsFoundIndex[
i]= 0;
4342 int factorsFound2= 0;
4347 factorsFoundIndex, FLINTN,
eval,
false
4349 if (
result.length() == nmod_mat_ncols (FLINTN))
4351 nmod_mat_clear (FLINTN);
4354 factorsFoundIndex, NTLN,
eval,
false
4356 if (
result.length() == NTLN.NumCols())
4359 delete [] factorsFoundIndex;
4365 delete [] factorsFoundIndex;
4367 else if (
l == precision)
4373 nmod_mat_clear (FLINTN);
4400 nmod_mat_clear (FLINTN);
◆ increasePrecisionFq2Fp() [2/2]
Definition at line 4939 of file facFqBivar.cc.
4955 bool hitBound=
false;
4956 bool useOldQs=
false;
4958 if (nmod_mat_nrows (FLINTN) != factors.
length())
4960 nmod_mat_clear (FLINTN);
4962 for (
long i=factors.
length()-1;
i >= 0;
i--)
4963 nmod_mat_entry (FLINTN,
i,
i)= 1;
4966 if (NTLN.NumRows() != factors.
length())
4967 ident (NTLN, factors.
length());
4974 nmod_mat_t FLINTC, FLINTK,
null;
4976 mat_zz_p* NTLC, NTLK;
4987 for (
int i= 0;
i < factors.
length();
i++,
j++)
4994 for (
int i= 0;
i < factors.
length();
i++,
j++)
4999 for (
int i= 0;
i < d;
i++)
5001 if (bounds [
i] + 1 <= oldL/2)
5003 int k=
tmin (bounds [
i] + 1, oldL/2);
5005 for (
int ii= 0; ii < factors.
length(); ii++)
5007 if (
A[ii].
size() - 1 >=
i)
5015 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
5017 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
5018 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
5020 rank= nmod_mat_nullspace (
null, FLINTK);
5021 nmod_mat_clear (FLINTK);
5022 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
5023 nmod_mat_clear (FLINTC);
5024 nmod_mat_init_set (FLINTC, FLINTN);
5025 nmod_mat_clear (FLINTN);
5026 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
5028 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
5030 nmod_mat_clear (FLINTC);
5031 nmod_mat_window_clear (FLINTK);
5032 nmod_mat_clear (
null);
5036 transpose (NTLK, NTLK);
5037 kernel (NTLK, NTLK);
5038 transpose (NTLK, NTLK);
5043 if (nmod_mat_ncols (FLINTN) == 1)
5045 if (NTLN.NumCols() == 1)
5062 bufUniFactors= factors;
5068 delete [] zeroOneVecs;
5072 factors= bufUniFactors;
◆ init4ext()
◆ isReduced() [1/2]
long isReduced |
( |
const mat_zz_pE & |
M | ) |
|
Definition at line 1465 of file facFqBivar.cc.
1468 for (
i = 1;
i <=
M.NumRows();
i++)
1471 for (
j = 1;
j <=
M.NumCols();
j++)
◆ isReduced() [2/2]
long isReduced |
( |
const nmod_mat_t |
M | ) |
|
Definition at line 1447 of file facFqBivar.cc.
1450 for (
i = 1;
i <= nmod_mat_nrows(
M);
i++)
1453 for (
j = 1;
j <= nmod_mat_ncols (
M);
j++)
1455 if (!(nmod_mat_entry (
M,
i-1,
j-1)==0))
◆ liftAndComputeLattice() [1/2]
int liftAndComputeLattice |
( |
const CanonicalForm & |
F, |
|
|
int * |
bounds, |
|
|
int |
sizeBounds, |
|
|
int |
start, |
|
|
int |
liftBound, |
|
|
int |
minBound, |
|
|
CFList & |
factors, |
|
|
mat_zz_pE & |
NTLN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
bool & |
irreducible |
|
) |
| |
Definition at line 3102 of file facFqBivar.cc.
3110 bool wasInBounds=
false;
3111 bool hitBound=
false;
3112 int l= (minBound+1)*2;
3115 bool reduced=
false;
3117 mat_zz_pE* NTLC, NTLK;
3122 while (
l <= liftBound)
3138 "time to lift in compute lattice: ");
3146 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3148 if (
l == (minBound+1)*2)
3160 "time to compute logarithmic derivative: ");
3162 for (
int i= 0;
i < sizeBounds;
i++)
3164 if (bounds [
i] + 1 <=
l/2)
3167 int k=
tmin (bounds [
i] + 1,
l/2);
3169 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3172 if (
A[ii].
size() - 1 >=
i)
3181 transpose (NTLK, NTLK);
3182 kernel (NTLK, NTLK);
3183 transpose (NTLK, NTLK);
3187 if (NTLN.NumCols() == 1)
3200 if (NTLN.NumCols() == 1)
◆ liftAndComputeLattice() [2/2]
int liftAndComputeLattice |
( |
const CanonicalForm & |
F, |
|
|
int * |
bounds, |
|
|
int |
sizeBounds, |
|
|
int |
start, |
|
|
int |
liftBound, |
|
|
int |
minBound, |
|
|
CFList & |
factors, |
|
|
nmod_mat_t |
FLINTN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
bool & |
irreducible |
|
) |
| |
Definition at line 2559 of file facFqBivar.cc.
2567 bool wasInBounds=
false;
2568 bool hitBound=
false;
2569 int l= (minBound+1)*2;
2572 bool reduced=
false;
2574 nmod_mat_t FLINTK, FLINTC,
null;
2580 while (
l <= liftBound)
2596 "time to lift in compute lattice: ");
2604 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
2613 "time to compute logarithmic derivative: ");
2615 for (
int i= 0;
i < sizeBounds;
i++)
2617 if (bounds [
i] + 1 <=
l/2)
2620 int k=
tmin (bounds [
i] + 1,
l/2);
2622 for (
int ii= 0; ii < factors.
length() - 1; ii++)
2624 if (
A[ii].
size() - 1 >=
i)
2632 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
2634 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
2635 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
2637 rank= nmod_mat_nullspace (
null, FLINTK);
2638 nmod_mat_clear (FLINTK);
2639 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
2640 nmod_mat_clear (FLINTC);
2641 nmod_mat_init_set (FLINTC, FLINTN);
2642 nmod_mat_clear (FLINTN);
2643 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
2645 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
2647 nmod_mat_clear (FLINTC);
2648 nmod_mat_window_clear (FLINTK);
2649 nmod_mat_clear (
null);
2650 if (nmod_mat_ncols (FLINTN) == 1)
2655 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
◆ liftAndComputeLatticeFq2Fp()
int liftAndComputeLatticeFq2Fp |
( |
const CanonicalForm & |
F, |
|
|
int * |
bounds, |
|
|
int |
sizeBounds, |
|
|
int |
start, |
|
|
int |
liftBound, |
|
|
int |
minBound, |
|
|
CFList & |
factors, |
|
|
nmod_mat_t |
FLINTN, |
|
|
CFList & |
diophant, |
|
|
CFMatrix & |
M, |
|
|
CFArray & |
Pi, |
|
|
CFArray & |
bufQ, |
|
|
bool & |
irreducible, |
|
|
const Variable & |
alpha |
|
) |
| |
Definition at line 3235 of file facFqBivar.cc.
3253 bool wasInBounds=
false;
3254 int l= (minBound+1)*2;
3257 bool hitBound=
false;
3259 bool reduced=
false;
3265 nmod_mat_t FLINTC, FLINTK,
null;
3267 mat_zz_p* NTLC, NTLK;
3271 while (
l <= liftBound)
3287 "time to lift in compute lattice: ");
3295 for (
int i= 0;
i < factors.
length() - 1;
i++,
j++)
3297 if (
l == (minBound+1)*2)
3309 "time to compute logarithmic derivative: ");
3311 for (
int i= 0;
i < sizeBounds;
i++)
3313 if (bounds [
i] + 1 <=
l/2)
3316 int k=
tmin (bounds [
i] + 1,
l/2);
3318 for (
int ii= 0; ii < factors.
length() - 1; ii++)
3320 if (
A[ii].
size() - 1 >=
i)
3329 nmod_mat_init (FLINTK, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTN),
3331 nmod_mat_mul (FLINTK, FLINTC, FLINTN);
3332 nmod_mat_init (
null, nmod_mat_ncols (FLINTK), nmod_mat_ncols (FLINTK),
3334 rank= nmod_mat_nullspace (
null, FLINTK);
3335 nmod_mat_clear (FLINTK);
3336 nmod_mat_window_init (FLINTK,
null, 0, 0, nmod_mat_nrows(
null), rank);
3337 nmod_mat_clear (FLINTC);
3338 nmod_mat_init_set (FLINTC, FLINTN);
3339 nmod_mat_clear (FLINTN);
3340 nmod_mat_init (FLINTN, nmod_mat_nrows (FLINTC), nmod_mat_ncols (FLINTK),
3342 nmod_mat_mul (FLINTN, FLINTC, FLINTK);
3344 nmod_mat_clear (FLINTC);
3345 nmod_mat_window_clear (FLINTK);
3346 nmod_mat_clear (
null);
3350 transpose (NTLK, NTLK);
3351 kernel (NTLK, NTLK);
3352 transpose (NTLK, NTLK);
3358 if (nmod_mat_nrows (FLINTN) == 1)
3360 if (NTLN.NumCols() == 1)
3367 if (
isReduced (FLINTN) &&
l > (minBound+1)*2)
3379 if (nmod_mat_ncols (FLINTN) == 1)
3381 if (NTLN.NumCols() == 1)
◆ mod()
◆ monicReconstruction()
Definition at line 1858 of file facFqBivar.cc.
1868 CFList bufFactors= factors;
1869 CFList factorsConsidered;
1871 for (
long i= 1;
i <=
N.NumCols();
i++)
1873 if (zeroOneVecs [
i - 1] == 0)
1877 factorsConsidered=
CFList();
1878 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1894 bufFactors=
Difference (bufFactors, factorsConsidered);
1899 factors= bufFactors;
1904 factors= bufFactors;
◆ reconstruction() [1/2]
Definition at line 1809 of file facFqBivar.cc.
1819 CFList bufFactors= factors;
1821 for (
long i= 1;
i <=
N.NumCols();
i++)
1823 if (zeroOneVecs [
i - 1] == 0)
1827 factorsConsidered=
CFList();
1828 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1843 bufFactors=
Difference (bufFactors, factorsConsidered);
1848 factors= bufFactors;
1853 factors= bufFactors;
◆ reconstruction() [2/2]
Definition at line 2123 of file facFqBivar.cc.
2132 CFList bufFactors= factors;
2133 CFList factorsConsidered;
2135 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
2137 if (zeroOneVecs [
i] == 0)
2141 factorsConsidered=
CFList();
2142 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
2144 if (!(nmod_mat_entry (
N,
j,
i) == 0))
2157 bufFactors=
Difference (bufFactors, factorsConsidered);
2162 factors= bufFactors;
2167 factors= bufFactors;
◆ reconstructionTry() [1/2]
Definition at line 1559 of file facFqBivar.cc.
1569 if (factors.
length() == 2)
1581 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1592 for (
long i= 1;
i <=
N.NumCols();
i++)
1594 if (factorsFoundIndex [
i - 1] == 1)
1610 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1621 factorsFoundIndex[
i - 1]= 1;
1629 if (factorsFound + 1 ==
N.NumCols())
1631 reconstructedFactors.
append (bufF);
1636 if (reconstructedFactors.
length() != 0)
◆ reconstructionTry() [2/2]
Definition at line 1726 of file facFqBivar.cc.
1736 if (factors.
length() == 2)
1748 if (tmp3/
Lc (tmp3) == bufF/
Lc (bufF))
1759 for (
long i= 0;
i < nmod_mat_ncols (
N);
i++)
1761 if (factorsFoundIndex [
i] == 1)
1777 for (
long j= 0;
j < nmod_mat_nrows (
N);
j++,
iter++)
1779 if (!(nmod_mat_entry (
N,
j,
i) == 0))
1788 factorsFoundIndex[
i]= 1;
1796 if (factorsFound + 1 == nmod_mat_ncols (
N))
1799 reconstructedFactors.
append (bufF);
1803 if (reconstructedFactors.
length() != 0)
◆ refineAndRestartLift() [1/2]
Definition at line 6086 of file facFqBivar.cc.
6096 for (
long i= 1;
i <= NTLN.NumCols();
i++)
6100 for (
long j= 1;
j <= NTLN.NumRows();
j++,
iter++)
6107 factors= bufFactors;
◆ refineAndRestartLift() [2/2]
Definition at line 6055 of file facFqBivar.cc.
6065 for (
long i= 0;
i < nmod_mat_ncols (FLINTN);
i++)
6069 for (
long j= 0;
j < nmod_mat_nrows (FLINTN);
j++,
iter++)
6071 if (!(nmod_mat_entry (FLINTN,
j,
i) == 0))
6076 factors= bufFactors;
◆ sieveSmallFactors()
Definition at line 6671 of file facFqBivar.cc.
6677 CFList bufUniFactors= uniFactors;
6679 int smallFactorDeg= d;
6681 henselLift12 (F, bufUniFactors, smallFactorDeg, Pi, diophant,
M);
6682 int adaptedLiftBound;
6684 int * factorsFoundIndex=
new int [uniFactors.
length()];
6685 for (
int i= 0;
i < uniFactors.
length();
i++)
6686 factorsFoundIndex [
i]= 0;
6689 factorsFoundIndex, degs, success, smallFactorDeg,
eval);
6690 delete [] factorsFoundIndex;
6694 return earlyFactors;
6699 return earlyFactors;
6701 int sizeOldF=
size (
G);
6702 if (
size (F) < sizeOldF)
6706 return earlyFactors;
6710 uniFactors= bufUniFactors;
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
fac_fq_uni_factorizer |
| ) |
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);
Initial value:{
if (L.isEmpty())
return 1
Definition at line 59 of file facFqBivar.cc.
◆ buf1
◆ buf2
◆ else
◆ tmp1
◆ tmp2
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
CFList furtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &eval)
void reconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_pE &N, const CanonicalForm &eval, bool beenInThres)
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 .
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
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
int liftAndComputeLatticeFq2Fp(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const Variable &alpha)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval)
class to iterate through CanonicalForm's
#define DEBOUTLN(stream, objects)
void refineAndRestartLift(const CanonicalForm &F, const nmod_mat_t FLINTN, int liftBound, int l, CFList &factors, CFMatrix &M, CFArray &Pi, CFList &diophant)
const CanonicalForm int const CFList const Variable & y
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
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...
long isReduced(const nmod_mat_t M)
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)
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
static BOOLEAN IsOne(number a, const coeffs r)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
CFList extReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const nmod_mat_t N, const ExtensionInfo &info, const CanonicalForm &evaluation)
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
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)
CFList sieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &eval)
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)
int liftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
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
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
CFList extSieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, const CanonicalForm &evaluation, const ExtensionInfo &info)
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
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)
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
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFList furtherLiftingAndIncreasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const Variable &alpha, const CanonicalForm &eval)
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
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 ...
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
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
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)
static BOOLEAN IsZero(number a, const coeffs r)
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
CFList monicReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
void extReconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, nmod_mat_t N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
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
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 > &)
int * extractZeroOneVecs(const nmod_mat_t M)
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
static bool irreducible(const CFList &AS)
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)
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
int extLiftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
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)
fq_nmod_poly_clear(prod, fq_con)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
CFList extFurtherLiftingAndIncreasePrecision(CanonicalForm &F, CFList &factors, int l, int liftBound, int d, int *bounds, nmod_mat_t FLINTN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
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
void convertFacCFMatrix2nmod_mat_t(nmod_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z/p to a nmod_mat_t
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)
static int index(p_Length length, p_Ord ord)
const ExtensionInfo & info
< [in] sqrfree poly
CFList earlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, bool symmetric, const CanonicalForm &evaluation)
INST_VAR CanonicalForm gf_mipo
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 ,...
CFList extEarlyReconstructionAndLifting(const CanonicalForm &F, const nmod_mat_t N, CanonicalForm &bufF, CFList &factors, int &l, int &factorsFound, bool beenInThres, CFMatrix &M, CFArray &Pi, CFList &diophant, const ExtensionInfo &info, const CanonicalForm &evaluation)
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)