46#include "flint/nmod_poly_factor.h"
47#include "flint/fq_nmod_poly_factor.h"
76 for (
int j= 1;
j <=
l;
j++,
i++)
85#if defined(HAVE_NTL) || defined(HAVE_FLINT)
115 if (list.length() >=
bound)
124 if (list.length() == 1)
131 else if (
alpha !=
x && list.length() >=
p)
133 if (list.length() ==
p)
160#if defined(HAVE_NTL) || defined(HAVE_FLINT)
165 if (
A.inCoeffDomain())
168 "univariate polynomial expected or constant expected");
184#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
257#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
368#if defined(HAVE_NTL) || defined(HAVE_FLINT)
389 int k=
info.getGFDegree();
403 DEBOUTLN (
cerr,
"LC (F, 1)*prodMod (factors, M) == F " <<
418 int *
v=
new int [
T.length()];
419 for (
int i= 0;
i <
T.length();
i++)
432 while (
T.length() >= 2*
s &&
s <=
thres)
513 if (
T.length() < 2*
s ||
T.length() ==
s ||
543 if (
T.length() < 2*
s ||
T.length() ==
s)
561 for (
int i= 0;
i <
T.length();
i++)
565 if (
T.length() < 2*
s)
610 DEBOUTLN (
cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
613 DEBOUTLN (
cerr,
"LC (F, 1)*prodMod (factors, N) == F " <<
627 int *
v=
new int [
T.length()];
628 for (
int i= 0;
i <
T.length();
i++)
645 while (
T.length() >= 2*
s &&
s <=
thres)
709 if (!
Lc (
g).inBaseDomain())
742 if (
T.length() < 2*
s ||
T.length() ==
s ||
769 if (
T.length() < 2*
s ||
T.length() ==
s)
785 for (
int i= 0;
i <
T.length();
i++)
790 if (
T.length() < 2*
s)
807#if defined(HAVE_NTL) || defined(HAVE_FLINT)
832 #if defined(HAVE_FLINT)
837 #elif defined(HAVE_NTL)
911 if (!
Lc (
g).inBaseDomain())
948 if (!
buf.inCoeffDomain())
994 int k=
info.getGFDegree();
1059 if (!
buf.inCoeffDomain())
1105 ASSERT (
j > 1,
"j > 1 expected" );
1107 int*
result =
new int [
j - 1];
1152#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1175 if (!
Lc (
A).inBaseDomain())
1473 for (
i = 1;
i <=
M.NumRows();
i++)
1476 for (
j = 1;
j <=
M.NumCols();
j++)
1511 for (
i = 1;
i <=
M.NumRows();
i++)
1514 for (
j = 1;
j <=
M.NumCols();
j++)
1531 int *
result=
new int [
M.NumCols()];
1532 for (
i = 1;
i <=
M.NumCols();
i++)
1534 for (
j = 1;
j <=
M.NumRows();
j++)
1583 int *
result=
new int [
M.NumCols()];
1584 for (
i = 1;
i <=
M.NumCols();
i++)
1586 for (
j = 1;
j <=
M.NumRows();
j++)
1639 for (
long i= 1;
i <=
N.NumCols();
i++)
1657 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1723 for (
long i= 1;
i <=
N.NumCols();
i++)
1741 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1870 for (
long i= 1;
i <=
N.NumCols();
i++)
1877 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1922 for (
long i= 1;
i <=
N.NumCols();
i++)
1929 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
1971 int k=
info.getGFDegree();
1981 for (
long i= 1;
i <=
N.NumCols();
i++)
1988 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2052 int k=
info.getGFDegree();
2136 for (
long i= 1;
i <=
N.NumCols();
i++)
2143 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2236 int k=
info.getGFDegree();
2283 for (
long i= 1;
i <=
N.NumCols();
i++)
2301 for (
long j= 1;
j <=
N.NumRows();
j++,
iter++)
2366 int k=
info.getGFDegree();
2523 "time to lift in compute lattice: ");
2540 "time to compute logarithmic derivative: ");
2565 if (
NTLN.NumCols() == 1)
2649 "time to lift in compute lattice: ");
2666 "time to compute logarithmic derivative: ");
2804 "time to lift in compute lattice: ");
2843 "time to compute logarithmic derivative: ");
2897 if (
NTLN.NumCols() == 1)
2912 if (
NTLN.NumCols() == 1)
3195 "time to lift in compute lattice: ");
3217 "time to compute logarithmic derivative: ");
3244 if (
NTLN.NumCols() == 1)
3257 if (
NTLN.NumCols() == 1)
3346 "time to lift in compute lattice: ");
3368 "time to compute logarithmic derivative: ");
3419 if (
NTLN.NumCols() == 1)
3440 if (
NTLN.NumCols() == 1)
3505 for (
int i= 1;
i < d;
i++)
3542 for (
int i= 0;
i < d;
i++)
3590 if (
NTLN.NumCols() == 1)
3615 for (
long i= 0;
i <
NTLN.NumCols();
i++)
3707 for (
int i= 1;
i < d;
i++)
3739 for (
int i= 0;
i < d;
i++)
3760 if (
NTLN.NumCols() == 1)
3776 for (
long i= 0;
i <
NTLN.NumCols();
i++)
3868 for (
int i= 1;
i < d;
i++)
3937 for (
int i= 0;
i < d;
i++)
4024 if (
NTLN.NumCols() == 1)
4060 for (
long i= 0;
i <
NTLN.NumCols();
i++)
4159 for (
int i= 1;
i < d;
i++)
4190 for (
int i= 0;
i < d;
i++)
4212 if (
NTLN.NumCols() == 1)
4298 for (
int i= 1;
i < d;
i++)
4335 for (
int i= 0;
i < d;
i++)
4383 if (
NTLN.NumCols() == 1)
4408 for (
long i= 0;
i <
NTLN.NumCols();
i++)
4543 for (
int i= 0;
i < d;
i++)
4589 if (
NTLN.NumCols() == 1)
4600 if (
NTLN.NumCols() == 1)
4686 for (
int i= 0;
i < d;
i++)
4708 if (
NTLN.NumCols() == 1)
4715 if (
NTLN.NumCols() == 1)
4851 for (
int i= 0;
i < d;
i++)
4937 if (
NTLN.NumCols() == 1)
4961 if (
NTLN.NumCols() == 1)
5076 for (
int i= 0;
i < d;
i++)
5122 if (
NTLN.NumCols() == 1)
5243 for (
int i= 0;
i < d;
i++)
5289 if (
NTLN.NumCols() == 1)
5301 if (
NTLN.NumCols() == 1)
5347 for (
long i= 0;
i <
NTLN.NumCols();
i++)
5453 for (
int i= 0;
i < d;
i++)
5474 if (
NTLN.NumCols() == 1)
5481 if (
NTLN.NumCols() == 1)
5510 for (
long i= 0;
i <
NTLN.NumCols();
i++)
5664 for (
int i= 0;
i < d;
i++)
5747 if (
NTLN.NumCols() == 1)
5762 if (
NTLN.NumCols() == 1)
5809 for (
long i= 0;
i <
NTLN.NumCols();
i++)
5944 for (
int i= 0;
i < d;
i++)
5991 if (
NTLN.NumCols() == 1)
6002 if (
NTLN.NumCols() == 1)
6048 for (
long i= 0;
i <
NTLN.NumCols();
i++)
6119 for (
long i= 1;
i <=
NTLN.NumCols();
i++)
6185 for (
long i= 1;
i <=
NTLN.NumCols();
i++)
6239 for (
long i= 0;
i <
NTLN.NumCols();
i++)
6338 LC (F,1).inCoeffDomain() &&
6437 for (
long i= 0;
i <
NTLN.NumCols();
i++)
6513 LC (F,1).inCoeffDomain() &&
6614 for (
long i= 0;
i <
NTLN.NumCols();
i++)
6784 if (
degs.getLength() == 1)
6833 if (
degs.getLength() == 1)
6880 for (
int i= 1;
i < d;
i++)
6894 bool success=
false;
6909 if (
degs.getLength() <= 1)
6956 for (
int i= 1;
i < d;
i++)
6968 if (
degs.getLength() <= 1)
7093 "time to compute a reduced lattice: ");
7134 for (
long i= 0;
i <
NTLN.NumCols();
i++)
7141 for (
long i= 0;
i <
NTLNe.NumCols();
i++)
7195 for (
long i= 0;
i <
NTLN.NumCols();
i++)
7202 for (
long i= 0;
i <
NTLNe.NumCols();
i++)
7260 refineAndRestartLift (F, NTLN, liftBound, l, bufUniFactors, M, Pi,
7271 refineAndRestartLift (F, NTLNe, liftBound, l, bufUniFactors, M, Pi,
7284 result= earlyReconstructionAndLifting (F, FLINTN, bufF, bufUniFactors, l,
7286 result= earlyReconstructionAndLifting (F, NTLN, bufF, bufUniFactors, l,
7288 factorsFound, beenInThres, M, Pi,
7289 diophant, symmetric, eval
7293 if (result.length() == nmod_mat_ncols (FLINTN))
7295 nmod_mat_clear (FLINTN);
7297 if (result.length() == NTLN.NumCols())
7301 return Union (result, smallFactors);
7306 result= earlyReconstructionAndLifting (F, NTLNe, bufF, bufUniFactors, l,
7307 factorsFound, beenInThres, M, Pi,
7308 diophant, symmetric, eval
7311 if (result.length() == NTLNe.NumCols())
7314 return Union (result, smallFactors);
7323 for (CFListIterator i= result; i.hasItem(); i++)
7326 tmp1= mod (i.getItem(), y-eval);
7328 for (CFListIterator j= bufUniFactors; j.hasItem(); j++, index++)
7330 tmp2= mod (j.getItem(), y);
7344 long numCols, numRows;
7345 if (alpha.level() == 1 || (alpha.level() != 1 && reduceFq2Fp))
7348 numCols= nmod_mat_ncols (FLINTN);
7349 numRows= nmod_mat_nrows (FLINTN);
7350 zeroOne= extractZeroOneVecs (FLINTN);
7352 numCols= NTLN.NumCols();
7353 numRows= NTLN.NumRows();
7354 zeroOne= extractZeroOneVecs (NTLN);
7359 numCols= NTLNe.NumCols();
7360 numRows= NTLNe.NumRows();
7361 zeroOne= extractZeroOneVecs (NTLNe);
7627 for (
int i= 1;
i < d;
i++)
7747 for (
int i= 1;
i < d;
i++)
7762 bool success=
false;
7780 if (
degs.getLength() <= 1)
7830 for (
int i= 1;
i < d;
i++)
7843 if (
degs.getLength() <= 1)
7911 "time to compute a reduced lattice: ");
7953 for (
long i= 0;
i <
NTLN.NumCols();
i++)
7993 for (
long i= 0;
i <
NTLN.NumCols();
i++)
8106 for (
int i= 0;
i <
NTLN.NumCols();
i++)
8267 for (
int i= 1;
i < d;
i++)
8317 int k=
info.getGFDegree();
8319 if (
A.isUnivariate())
8353 if (
A.inCoeffDomain())
8360 else if (
A.isUnivariate())
8513 "time to find eval point wrt y: ");
8516 if (
fail && (
i == 0))
8536 if (
fail && (
i == 0))
8549 if (
fail && (
i != 0))
8556 "time for univariate factorization over Fq: ");
8557 DEBOUTLN (
cerr,
"Lc (bufAeval)*prod (bufUniFactors)== bufAeval " <<
8565 "time for univariate factorization in y over Fq: ");
8566 DEBOUTLN (
cerr,
"Lc (bufAeval2)*prod (bufUniFactors2)== bufAeval2 " <<
8678 "total time for univariate factorizations: ");
8695 if (
degs.getLength() == 1)
8725 "time to shift eval to zero: ");
8742 "time for bivariate hensel lifting over Fq: ");
8755 "time for naive bivariate factor recombi over Fq: ");
8785 "time to bivar lift and LLL recombi over Fq: ");
8797 "time for bivar hensel lifting over Fq: ");
8806 "time for small subset naive recombi over Fq: ");
8829 "time to increase precision: ");
8936 int k=
info.getGFDegree();
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 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
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
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
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
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational pow(const Rational &a, int e)
Rational abs(const Rational &a)
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Conversion to and from NTL.
static bool irreducible(const CFList &AS)
const CanonicalForm CFMap CFMap & N
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 decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
#define GaloisFieldDomain
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
generate random irreducible univariate polynomials
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
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 findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
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 ,...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
This file implements functions to map between extensions of finite fields.
GLOBAL_VAR flint_rand_t FLINTrandom
generate random integers, random elements of finite fields
VAR void(* factoryError)(const char *s)
int ipower(int b, int m)
int ipower ( int b, int m )
generate random elements in F_p(alpha)
class to iterate through CanonicalForm's
DegreePattern provides a functionality to create, intersect and refine degree patterns.
ExtensionInfo contains information about extension.
generate random elements in F_p
generate random elements in GF
factory's class for variables
class to do operations mod p^k for int's p and k
functions to print debug output
#define DEBOUTLN(stream, objects)
const CanonicalForm int const CFList & evaluation
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
const Variable & v
< [in] a sqrfree bivariate poly
CFList *& Aeval
<[in] poly
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
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
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
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...
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
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
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
CFArray copy(const CFList &list)
write elements of list into an array
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
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)
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
This file provides utility functions for bivariate factorization.
CFList biFactorize(const CanonicalForm &F, const ExtensionInfo &info)
bivariate factorization over finite fields as decribed in "Factoring multivariate polynomials over a ...
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...
CFList increasePrecision(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, int precision, 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)
return mod(mulNTL(buf1, buf2, b), M)
CFList extHenselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const ExtensionInfo &extInfo, const DegreePattern °Pat, const CanonicalForm &eval)
int * getCombinations(int *rightSide, int sizeOfRightSide, int &sizeOfOutput, int degreeLC)
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 deleteFactors(CFList &factors, int *factorsFoundIndex)
void extReconstructionTry(CFList &reconstructedFactors, CanonicalForm &F, const CFList &factors, const int liftBound, int &factorsFound, int *&factorsFoundIndex, mat_zz_p &N, bool beenInThres, const ExtensionInfo &info, const CanonicalForm &evaluation)
CFList extBiFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
int * getLiftPrecisions(const CanonicalForm &F, int &sizeOfOutput, int degreeLC)
compute lifting precisions from the shape of the Newton polygon of F
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 extReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_p &N, const ExtensionInfo &info, const CanonicalForm &evaluation)
int liftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int start, int liftBound, int minBound, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible)
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)
int * extractZeroOneVecs(const mat_zz_p &M)
CFList increasePrecisionFq2Fp(CanonicalForm &F, CFList &factors, int factorsFound, int oldNumCols, int oldL, const Variable &alpha, 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 monicReconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N)
CFList henselLiftAndLatticeRecombi(const CanonicalForm &G, const CFList &uniFactors, const Variable &alpha, const DegreePattern °Pat, bool symmetric, const CanonicalForm &eval)
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, 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 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...
CanonicalForm evalPoint(const CanonicalForm &F, CanonicalForm &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
find an evaluation point p, s.t. F(p,y) is squarefree and .
CFList 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
CFList sieveSmallFactors(const CanonicalForm &G, CFList &uniFactors, DegreePattern °Pat, CanonicalForm &H, CFList &diophant, CFArray &Pi, CFMatrix &M, bool &success, int d, 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 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 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)
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 ...
long isReduced(const mat_zz_p &M)
Variable chooseExtension(const Variable &alpha, const Variable &beta, int k)
chooses a field extension.
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...
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)
int extLiftAndComputeLattice(const CanonicalForm &F, int *bounds, int sizeBounds, int liftBound, int minBound, int start, CFList &factors, mat_zz_p &NTLN, CFList &diophant, CFMatrix &M, CFArray &Pi, CFArray &bufQ, bool &irreducible, const CanonicalForm &evaluation, const ExtensionInfo &info, CFList &source, CFList &dest)
ExtensionInfo init4ext(const ExtensionInfo &info, const CanonicalForm &evaluation, int °Mipo)
const CanonicalForm const modpk & b
CFList increasePrecision2(const CanonicalForm &F, CFList &factors, const Variable &alpha, int precision)
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)
This file provides functions for factorizing a bivariate polynomial over , or GF.
CanonicalForm prodMod0(const CFList &L, const CanonicalForm &M, const modpk &b=modpk())
via divide-and-conquer
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...
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
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.
convertFacCF2nmod_poly_t(FLINTmipo, M)
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)...
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
This file defines functions for Hensel lifting.
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),...
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
This file defines functions for fast multiplication and division with remainder.
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
static BOOLEAN IsOne(number a, const coeffs)
static BOOLEAN IsZero(number a, const coeffs)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
INST_VAR CanonicalForm gf_mipo
static int index(p_Length length, p_Ord ord)
int status int void size_t count
int status int void * buf
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)