45 if (!
i.getItem().inCoeffDomain())
54 i.getItem()=
N (
i.getItem());
60 i.getItem()=
CFFactor (N (
i.getItem().factor()),
i.getItem().exp());
66 i.getItem()=
CFAFactor (N (
i.getItem().factor()),
i.getItem().minpoly(),
71 const CFList& factors3,
const bool swap1,
72 const bool swap2,
const CFMap&
N)
88 i.getItem()=
N (
i.getItem());
91 factors1.
append (N (
i.getItem()));
93 factors1.
append (N (
i.getItem()));
105 i.getItem()=
N (
i.getItem());
113 if (F.
isOne())
return false;
193 int order=
ipower (p, k) - 1;
194 int number= orderFieldExtension/order;
220 return mapDown (F, imPrimElem, primElem, beta, source, dest);
233 if (!k && beta.
level() == 1)
235 else if (!k && beta.
level() != 1)
250 else if (!k && beta ==
Variable (1))
252 if (
degree (g, alpha) < degMipoBeta)
255 else if (!k && beta !=
Variable (1))
259 g=
mapDown (g, delta, gamma, alpha, source, dest);
279 else if (!k && beta ==
Variable (1))
281 else if (!k && beta !=
Variable (1))
282 factors.
append (
mapDown (g, delta, gamma, alpha, source, dest));
291 lcinv= 1/
Lc (
i.getItem());
292 i.getItem() *= lcinv;
302 lcinv= 1/
Lc (
i.getItem().factor());
303 i.getItem()=
CFFactor (
i.getItem().factor()*lcinv,
312 int r= elements.
size();
316 if (index[s - 1] == 0)
321 result.
append (elements[i]);
329 if (index[s - 1] == r)
331 if (index[0] == r - s + 1)
337 while (found ==
false)
339 if (index[s - 2 - i] < r - i - 1)
343 buf= index[s - i - 1];
345 while (s - i - 1 + k < s)
347 index[s - i - 1 +
k]= buf + k + 1;
351 for (
int j= 0;
j <
s;
j++)
352 result.
append (elements[index[
j] - 1]);
358 for (
int j= 0;
j <
s;
j++)
359 result.
append (elements[index[
j] - 1]);
369 array[j]=
i.getItem();
377 if (subsetSize > setSize)
382 int *
v=
new int [setSize];
383 for (
int i= 0;
i < setSize;
i++)
397 if (v[subsetSize - 1] - v[0] + 1 == subsetSize && v[0] > 1)
399 if (v[0] + subsetSize - 1 > setSize)
406 for (
int i= 1;
i < subsetSize - 1;
i++)
408 v[subsetSize - 1]= v[subsetSize - 2];
412 if (v[0] + subsetSize - 1 > setSize)
418 for (
int i= 1;
i < subsetSize - 1;
i++)
420 v[subsetSize - 1]= v[subsetSize - 2];
423 for (
int i= 0;
i < setSize;
i++)
477 if (
degree (logDeriv, x) == 0)
483 int j=
degree (logDeriv, y) + 1;
488 if (
i.coeff().inCoeffDomain())
489 result[0] +=
i.coeff()*
power (x,
i.exp());
515 if ((oldL > 100 && l - oldL < 50) || (oldL < 100 && l - oldL < 30))
520 bufF=
div (bufF, xToOldL);
535 Mid=
mulMod2 (G1, oldQ1*x, xToLOldL);
537 Mid=
mulMod2 (G1, oldQ1, xToLOldL);
541 Low=
mod (Low, xToLOldL);
543 bufF=
div (F, xToOldL);
561 if (
degree (logDeriv, x) == 0)
567 int j=
degree (logDeriv,y) + 1;
572 if (
i.coeff().inCoeffDomain())
573 result[0] +=
i.coeff()*
power (x,
i.exp());
590 ASSERT (A.
size () - startIndex >= 0,
"wrong starting index");
591 ASSERT (A.
size () - startIndex <= M.
rows(),
"wrong starting index");
592 ASSERT (column > 0 && column <= M.
columns(),
"wrong column");
593 if (A.
size() - startIndex <= 0)
return;
595 for (
int i= startIndex;
i < A.
size();
i++, j++)
596 M (j, column)= A [
i];
642 result [(
i -
k)*d +
l]= iter.
coeff();
654 for (
int l= 0;
l < d;
l++)
655 result[(
i - k)*d +
l]= 0;
673 F= F (
power (y, degMipo), y);
676 NTLF.rep.SetLength (l*degMipo);
677 NTLF.rep= M*NTLF.rep;
715 F= F (
power (y, degMipo), y);
719 nmod_mat_t MFLINTF, mulResult;
730 for (i= 0; i < FLINTF->length; i++)
731 nmod_mat_entry (MFLINTF, i, 0)= FLINTF->coeffs[
i];
733 for (; i < MFLINTF->r; i++)
734 nmod_mat_entry (MFLINTF, i, 0)= 0;
736 nmod_mat_mul (mulResult, M, MFLINTF);
739 for (i= 0; i < mulResult->r; i++)
742 nmod_mat_clear (MFLINTF);
743 nmod_mat_clear (mulResult);
751 for (
int i=
degree (F); i >=
k; i--)
755 result [i -
k]= j.
coeff();
771 int sizeOfNewtonPolygon;
774 isIrreducible=
false;
775 if (sizeOfNewtonPolygon == 3)
778 (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
782 (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
796 tmp=
gcd (tmp, newtonPolyg[1][0]);
797 tmp=
gcd (tmp, newtonPolyg[1][1]);
798 tmp=
gcd (tmp, newtonPolyg[2][0]);
799 tmp=
gcd (tmp, newtonPolyg[2][1]);
800 isIrreducible= (tmp==1);
809 int minX, minY, maxX, maxY;
810 minX= newtonPolyg [0] [0];
811 minY= newtonPolyg [0] [1];
815 for (
int i= 1;
i < sizeOfNewtonPolygon;
i++)
817 if (newtonPolyg[
i][1] == 0)
819 if (newtonPolyg[indZero][1] == 0)
821 if (newtonPolyg[indZero][0] < newtonPolyg[
i][0])
827 if (minX > newtonPolyg [
i] [0])
828 minX= newtonPolyg [
i] [0];
829 if (maxX < newtonPolyg [i] [0])
830 maxX= newtonPolyg [
i] [0];
831 if (minY > newtonPolyg [i] [1])
832 minY= newtonPolyg [
i] [1];
833 if (maxY < newtonPolyg [i] [1])
834 maxY= newtonPolyg [
i] [1];
837 int slopeNum, slopeDen, constTerm;
838 bool negativeSlope=
false;
839 if (indZero != sizeOfNewtonPolygon - 1)
841 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
842 slopeDen= newtonPolyg[indZero+1][1];
843 constTerm= newtonPolyg[indZero][0];
847 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
848 slopeDen= newtonPolyg[0][1];
849 constTerm= newtonPolyg[indZero][0];
857 int* point=
new int [2];
858 for (
int i= 0;
i <
n;
i++)
860 if (((indZero+1) < sizeOfNewtonPolygon && (
i+1) > newtonPolyg[indZero+1][1])
861 || ((indZero+1) >= sizeOfNewtonPolygon && (
i+1) > newtonPolyg[0][1]))
863 if (indZero + 1 != sizeOfNewtonPolygon)
867 if (indZero != sizeOfNewtonPolygon - 1)
869 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
870 slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
871 constTerm= newtonPolyg[indZero][0];
875 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
876 slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
877 constTerm= newtonPolyg[indZero][0];
882 slopeNum= - slopeNum;
883 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
884 slopeDen) + constTerm;
887 k= (int) (((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen)
893 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
894 slopeDen) + constTerm;
896 k= (int) ((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen
899 if (
i + 1 > maxY ||
i + 1 < minY)
906 if (!
isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
913 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
914 delete [] newtonPolyg[
i];
915 delete [] newtonPolyg;
926 int sizeOfNewtonPolygon;
929 isIrreducible=
false;
930 if (sizeOfNewtonPolygon == 3)
933 (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
937 (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
951 tmp=
gcd (tmp, newtonPolyg[1][0]);
952 tmp=
gcd (tmp, newtonPolyg[1][1]);
953 tmp=
gcd (tmp, newtonPolyg[2][0]);
954 tmp=
gcd (tmp, newtonPolyg[2][1]);
955 isIrreducible= (tmp==1);
965 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
967 swap= newtonPolyg[
i][1];
968 newtonPolyg[
i][1]=newtonPolyg[
i][0];
969 newtonPolyg[
i][0]=
swap;
972 sizeOfNewtonPolygon=
polygon(newtonPolyg, sizeOfNewtonPolygon);
974 int minX, minY, maxX, maxY;
975 minX= newtonPolyg [0] [0];
976 minY= newtonPolyg [0] [1];
980 for (
int i= 1;
i < sizeOfNewtonPolygon;
i++)
982 if (newtonPolyg[
i][1] == 0)
984 if (newtonPolyg[indZero][1] == 0)
986 if (newtonPolyg[indZero][0] < newtonPolyg[
i][0])
992 if (minX > newtonPolyg [
i] [0])
993 minX= newtonPolyg [
i] [0];
994 if (maxX < newtonPolyg [i] [0])
995 maxX= newtonPolyg [
i] [0];
996 if (minY > newtonPolyg [i] [1])
997 minY= newtonPolyg [
i] [1];
998 if (maxY < newtonPolyg [i] [1])
999 maxY= newtonPolyg [
i] [1];
1002 int slopeNum, slopeDen, constTerm;
1003 bool negativeSlope=
false;
1004 if (indZero != sizeOfNewtonPolygon - 1)
1006 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
1007 slopeDen= newtonPolyg[indZero+1][1];
1008 constTerm= newtonPolyg[indZero][0];
1012 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
1013 slopeDen= newtonPolyg[0][1];
1014 constTerm= newtonPolyg[indZero][0];
1018 slopeNum= -slopeNum;
1019 negativeSlope=
true;
1023 int* point=
new int [2];
1024 for (
int i= 0;
i <
n;
i++)
1026 if (((indZero+1) < sizeOfNewtonPolygon && (
i+1) > newtonPolyg[indZero+1][1])
1027 || ((indZero+1) >= sizeOfNewtonPolygon && (
i+1) > newtonPolyg[0][1]))
1029 if (indZero + 1 != sizeOfNewtonPolygon)
1033 if (indZero != sizeOfNewtonPolygon - 1)
1035 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
1036 slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
1037 constTerm= newtonPolyg[indZero][0];
1041 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
1042 slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
1043 constTerm= newtonPolyg[indZero][0];
1047 negativeSlope=
true;
1048 slopeNum= - slopeNum;
1049 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
1050 slopeDen) + constTerm;
1053 k= (int) (((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen)
1059 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
1060 slopeDen) + constTerm;
1062 k= (int) ((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen
1065 if (
i + 1 > maxY ||
i + 1 < minY)
1073 if (!
isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
1080 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
1081 delete [] newtonPolyg[
i];
1082 delete [] newtonPolyg;
1101 int * expf=
new int [sizef];
1106 int indf= sizef - 1;
1107 if (expf[indf] == 0)
1111 for (
int i= indf - 1;
i >= 0;
i--)
1113 if (expf [
i]%result != 0)
1146 int * expf=
new int [sizef];
1147 int * expg=
new int [sizeg];
1159 int indf= sizef - 1;
1160 int indg= sizeg - 1;
1161 if (expf[indf] == 0)
1163 if (expg[indg] == 0)
1166 if ((expg[indg]%expf [indf] != 0 && expf[indf]%expg[indg] != 0) ||
1167 (expg[indg] == 1 && expf[indf] == 1))
1175 if (expg [indg]%expf [indf] == 0)
1179 for (
int i= indf - 1;
i >= 0;
i--)
1181 if (expf [
i]%result != 0)
1189 for (
int i= indg - 1;
i >= 0;
i--)
1191 if (expg [
i]%result != 0)
1218 int * expf=
new int [sizef];
1225 int indf= sizef - 1;
1226 if (expf[indf] == 0)
1229 if ((d%expf [indf] != 0 && expf[indf]%d != 0) || (expf[indf] == 1))
1236 if (d%expf [indf] == 0)
1240 for (
int i= indf - 1;
i >= 0;
i--)
1242 if (expf [
i]%result != 0)
1255 ASSERT (L.
length() > 1,
"expected a list of at least two elements");
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
const CanonicalForm int s
CanonicalForm mapDown(const CanonicalForm &F, const ExtensionInfo &info, CFList &source, CFList &dest)
map a poly into a subfield of the current field, no testing is performed!
const CanonicalForm int const CFList const Variable & y
CFArray copy(const CFList &list)
write elements of list into an array
This file defines functions for Hensel lifting.
int recSubstituteCheck(const CanonicalForm &F, const int d)
static CanonicalForm bound(const CFMatrix &M)
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Variable getBeta() const
getter
This file provides functions to compute the Newton polygon of a bivariate polynomial.
some useful template functions.
#define TIMING_END_AND_PRINT(t, msg)
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
factory's class for variables
void normalize(CFList &factors)
normalize factors, i.e. make factors monic
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) ...
const CanonicalForm CFMap CFMap int &both_non_zero int n
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CFFList multiplicity(CanonicalForm &F, const CFList &factors)
determine multiplicity of the factors
const CanonicalForm int const CFList & evaluation
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...
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Variable getAlpha() const
getter
bool delta(X x, Y y, D d)
virtual class for internal CanonicalForm's
This file implements functions to map between extensions of finite fields.
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
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...
ExtensionInfo contains information about extension.
int getGFDegree() const
getter
const CanonicalForm CFMap CFMap & N
convertFacCF2nmod_poly_t(FLINTmipo, M)
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
int status int void * buf
This file defines functions for fast multiplication and division with remainder.
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
CanonicalForm getGamma() const
getter
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
int polygon(int **points, int sizePoints)
compute a polygon
Iterators for CanonicalForm's.
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
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
declarations of higher level algorithms.
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 newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
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 ...
static int index(p_Length length, p_Ord ord)
class to iterate through CanonicalForm's
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
This file provides utility functions for bivariate factorization.
const Variable & v
< [in] a sqrfree bivariate poly
long imm2int(const InternalCF *const imm)
int ipower(int b, int m)
int ipower ( int b, int m )
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
CanonicalForm getDelta() const
getter
CF_NO_INLINE int exp() const
get the current exponent
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
TIMING_DEFINE_PRINT(fac_log_deriv_div) TIMING_DEFINE_PRINT(fac_log_deriv_mul) TIMING_DEFINE_PRINT(fac_log_deriv_pre) void append(CFList &factors1
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int...
#define GaloisFieldDomain
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
#define ASSERT(expression, message)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global fields
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
This file provides a class to store information about finite fields and extensions thereof...
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N