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());
105 i.getItem()=
N (
i.getItem());
113 if (F.
isOne())
return false;
194 int number= orderFieldExtension/order;
209 int k=
info.getGFDegree();
220 return mapDown (F, imPrimElem, primElem,
beta, source, dest);
226 int k=
info.getGFDegree();
270 int k=
info.getGFDegree();
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();
331 if (
index[0] == r -
s + 1)
337 while (
found ==
false)
345 while (
s -
i - 1 +
k <
s)
351 for (
int j= 0;
j <
s;
j++)
358 for (
int j= 0;
j <
s;
j++)
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++)
488 if (
i.coeff().inCoeffDomain())
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);
572 if (
i.coeff().inCoeffDomain())
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];
644 if (!
iter.hasTerms())
654 for (
int l= 0;
l < d;
l++)
667 ASSERT (
G.isUnivariate() ||
G.inCoeffDomain(),
"univariate input expected");
676 NTLF.rep.SetLength (
l*degMipo);
677 NTLF.rep=
M*NTLF.rep;
709 ASSERT (
G.isUnivariate() ||
G.inCoeffDomain(),
"univariate input expected");
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);
772 int sizeOfNewtonPolygon;
776 if (sizeOfNewtonPolygon == 3)
779 (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
783 (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
797 tmp=
gcd (tmp, newtonPolyg[1][0]);
798 tmp=
gcd (tmp, newtonPolyg[1][1]);
799 tmp=
gcd (tmp, newtonPolyg[2][0]);
800 tmp=
gcd (tmp, newtonPolyg[2][1]);
810 int minX, minY, maxX, maxY;
811 minX= newtonPolyg [0] [0];
812 minY= newtonPolyg [0] [1];
816 for (
int i= 1;
i < sizeOfNewtonPolygon;
i++)
818 if (newtonPolyg[
i][1] == 0)
820 if (newtonPolyg[indZero][1] == 0)
822 if (newtonPolyg[indZero][0] < newtonPolyg[
i][0])
828 if (minX > newtonPolyg [
i] [0])
829 minX= newtonPolyg [
i] [0];
830 if (maxX < newtonPolyg [
i] [0])
831 maxX= newtonPolyg [
i] [0];
832 if (minY > newtonPolyg [
i] [1])
833 minY= newtonPolyg [
i] [1];
834 if (maxY < newtonPolyg [
i] [1])
835 maxY= newtonPolyg [
i] [1];
838 int slopeNum, slopeDen, constTerm;
839 bool negativeSlope=
false;
840 if (indZero != sizeOfNewtonPolygon - 1)
842 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
843 slopeDen= newtonPolyg[indZero+1][1];
844 constTerm= newtonPolyg[indZero][0];
848 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
849 slopeDen= newtonPolyg[0][1];
850 constTerm= newtonPolyg[indZero][0];
858 int* point=
new int [2];
859 for (
int i= 0;
i < n;
i++)
861 if (((indZero+1) < sizeOfNewtonPolygon && (
i+1) > newtonPolyg[indZero+1][1])
862 || ((indZero+1) >= sizeOfNewtonPolygon && (
i+1) > newtonPolyg[0][1]))
864 if (indZero + 1 != sizeOfNewtonPolygon)
868 if (indZero != sizeOfNewtonPolygon - 1)
870 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
871 slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
872 constTerm= newtonPolyg[indZero][0];
876 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
877 slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
878 constTerm= newtonPolyg[indZero][0];
883 slopeNum= - slopeNum;
884 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
885 slopeDen) + constTerm;
888 k= (int) (((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen)
894 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
895 slopeDen) + constTerm;
897 k= (int) ((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen
900 if (
i + 1 > maxY ||
i + 1 < minY)
907 if (!
isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) &&
k > 0)
914 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
915 delete [] newtonPolyg[
i];
916 delete [] newtonPolyg;
927 int sizeOfNewtonPolygon;
931 if (sizeOfNewtonPolygon == 3)
934 (newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
938 (newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
952 tmp=
gcd (tmp, newtonPolyg[1][0]);
953 tmp=
gcd (tmp, newtonPolyg[1][1]);
954 tmp=
gcd (tmp, newtonPolyg[2][0]);
955 tmp=
gcd (tmp, newtonPolyg[2][1]);
966 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
968 swap= newtonPolyg[
i][1];
969 newtonPolyg[
i][1]=newtonPolyg[
i][0];
970 newtonPolyg[
i][0]=
swap;
973 sizeOfNewtonPolygon=
polygon(newtonPolyg, sizeOfNewtonPolygon);
975 int minX, minY, maxX, maxY;
976 minX= newtonPolyg [0] [0];
977 minY= newtonPolyg [0] [1];
981 for (
int i= 1;
i < sizeOfNewtonPolygon;
i++)
983 if (newtonPolyg[
i][1] == 0)
985 if (newtonPolyg[indZero][1] == 0)
987 if (newtonPolyg[indZero][0] < newtonPolyg[
i][0])
993 if (minX > newtonPolyg [
i] [0])
994 minX= newtonPolyg [
i] [0];
995 if (maxX < newtonPolyg [
i] [0])
996 maxX= newtonPolyg [
i] [0];
997 if (minY > newtonPolyg [
i] [1])
998 minY= newtonPolyg [
i] [1];
999 if (maxY < newtonPolyg [
i] [1])
1000 maxY= newtonPolyg [
i] [1];
1003 int slopeNum, slopeDen, constTerm;
1004 bool negativeSlope=
false;
1005 if (indZero != sizeOfNewtonPolygon - 1)
1007 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
1008 slopeDen= newtonPolyg[indZero+1][1];
1009 constTerm= newtonPolyg[indZero][0];
1013 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
1014 slopeDen= newtonPolyg[0][1];
1015 constTerm= newtonPolyg[indZero][0];
1019 slopeNum= -slopeNum;
1020 negativeSlope=
true;
1024 int* point=
new int [2];
1025 for (
int i= 0;
i < n;
i++)
1027 if (((indZero+1) < sizeOfNewtonPolygon && (
i+1) > newtonPolyg[indZero+1][1])
1028 || ((indZero+1) >= sizeOfNewtonPolygon && (
i+1) > newtonPolyg[0][1]))
1030 if (indZero + 1 != sizeOfNewtonPolygon)
1034 if (indZero != sizeOfNewtonPolygon - 1)
1036 slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
1037 slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
1038 constTerm= newtonPolyg[indZero][0];
1042 slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
1043 slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
1044 constTerm= newtonPolyg[indZero][0];
1048 negativeSlope=
true;
1049 slopeNum= - slopeNum;
1050 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
1051 slopeDen) + constTerm;
1054 k= (int) (((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen)
1060 k= (int) -(((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
1061 slopeDen) + constTerm;
1063 k= (int) ((
long) slopeNum*((
i+1)-newtonPolyg[indZero][1])) / slopeDen
1066 if (
i + 1 > maxY ||
i + 1 < minY)
1074 if (!
isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) &&
k > 0)
1081 for (
int i= 0;
i < sizeOfNewtonPolygon;
i++)
1082 delete [] newtonPolyg[
i];
1083 delete [] newtonPolyg;
1102 int * expf=
new int [sizef];
1107 int indf= sizef - 1;
1108 if (expf[indf] == 0)
1112 for (
int i= indf - 1;
i >= 0;
i--)
1147 int * expf=
new int [sizef];
1148 int * expg=
new int [sizeg];
1160 int indf= sizef - 1;
1161 int indg= sizeg - 1;
1162 if (expf[indf] == 0)
1164 if (expg[indg] == 0)
1167 if ((expg[indg]%expf [indf] != 0 && expf[indf]%expg[indg] != 0) ||
1168 (expg[indg] == 1 && expf[indf] == 1))
1176 if (expg [indg]%expf [indf] == 0)
1180 for (
int i= indf - 1;
i >= 0;
i--)
1190 for (
int i= indg - 1;
i >= 0;
i--)
1219 int * expf=
new int [sizef];
1226 int indf= sizef - 1;
1227 if (expf[indf] == 0)
1230 if ((d%expf [indf] != 0 && expf[indf]%d != 0) || (expf[indf] == 1))
1237 if (d%expf [indf] == 0)
1241 for (
int i= indf - 1;
i >= 0;
i--)
1256 ASSERT (L.
length() > 1,
"expected a list of at least two elements");
1265 for (;
i.hasItem();
i++)
1290 C +=
i.coeff()*
power (
f.mvar(),
i.exp()/ d);
This file provides a class to store information about finite fields and extensions thereof.
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
int polygon(int **points, int sizePoints)
compute a polygon
This file provides functions to compute the Newton polygon of a bivariate polynomial.
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
#define ASSERT(expression, message)
#define GaloisFieldDomain
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
This file implements functions to map between extensions of finite fields.
int ipower(int b, int m)
int ipower ( int b, int m )
class to iterate through CanonicalForm's
CF_NO_INLINE int exp() const
get the current exponent
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
ExtensionInfo contains information about extension.
virtual class for internal CanonicalForm's
factory's class for variables
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)
const Variable & v
< [in] a sqrfree bivariate poly
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
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...
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!
void normalize(CFList &factors)
normalize factors, i.e. make factors monic
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
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
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
int recSubstituteCheck(const CanonicalForm &F, const int d)
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
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)
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
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
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
This file provides utility functions for bivariate factorization.
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
This file defines functions for Hensel lifting.
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
This file defines functions for fast multiplication and division with remainder.
some useful template functions.
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
STATIC_VAR int * multiplicity
gmp_float exp(const gmp_float &a)
static int index(p_Length length, p_Ord ord)
int status int void * buf
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)