 |
My Project
debian-1:4.1.1-p2+ds-4
|
Go to the documentation of this file.
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;
220 return mapDown (F, imPrimElem, primElem,
beta, 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();
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);
int getGFDegree() const
getter
Variable getBeta() const
getter
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
class to iterate through CanonicalForm's
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
nmod_poly_clear(FLINTmipo)
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
CFFList multiplicity(CanonicalForm &F, const CFList &factors)
determine multiplicity of the factors
const CanonicalForm CFMap CFMap & N
virtual class for internal CanonicalForm's
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 delta(X x, Y y, D d)
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
void normalize(CFList &factors)
normalize factors, i.e. make factors monic
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
const CanonicalForm int const CFList & evaluation
#define GaloisFieldDomain
convertFacCF2nmod_poly_t(FLINTmipo, M)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
#define ASSERT(expression, message)
int status int void * buf
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
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
CF_NO_INLINE int exp() const
get the current exponent
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
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 subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
int ipower(int b, int m)
int ipower ( int b, int m )
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm getDelta() const
getter
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
gmp_float exp(const gmp_float &a)
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
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
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
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
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
static long imm2int(const InternalCF *const imm)
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
int findItem(const CFList &list, const CanonicalForm &item)
helper function
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
int polygon(int **points, int sizePoints)
compute a polygon
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 Variable & v
< [in] a sqrfree bivariate poly
int recSubstituteCheck(const CanonicalForm &F, const int d)
const CanonicalForm int s
CFArray copy(const CFList &list)
write elements of list into an array
Variable getAlpha() const
getter
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
static int index(p_Length length, p_Ord ord)
const ExtensionInfo & info
< [in] sqrfree poly
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)