88#if defined(HAVE_NTL)|| defined(HAVE_FLINT)
99 for (
int i = n;
i >= 0;
i--)
112 for (
int i= 1;
i <= n;
i++)
141 for (
int i= 1;
i <= n;
i++)
184 for (
int j=
i + 1;
j <=
m;
j++)
232 for (
int i= 1;
i <= n;
i++)
299 for (;
i.hasTerms();
i++)
322 for (
int i= 1;
i <= d;
i++)
391 double bound=
pow ((
double)
p, (
double) d);
394 if (list.length() ==
bound)
399 if (list.length() <
p)
454#if defined(HAVE_NTL) || defined(HAVE_FLINT)
461#if defined(HAVE_NTL) || defined(HAVE_FLINT)
477#if defined(HAVE_NTL) || defined(HAVE_FLINT)
679 "time for recursive call: ");
692 "time for recursive call: ");
751 "time for newton interpolation: ");
784 "time for successful termination test Fq: ");
797 "time for successful termination test Fq: ");
801 "time for unsuccessful termination test Fq: ");
831 if (list.length() ==
bound)
836 if (list.length() < 1)
1010 ASSERT (
expon >= 2,
"not enough points in modGCDGF");
1035 "time for recursive call: ");
1046 "time for recursive call: ");
1105 "time for newton interpolation: ");
1138 "time for successful termination GF: ");
1152 "time for successful termination GF: ");
1157 "time for unsuccessful termination GF: ");
1182 if (list.length() ==
bound)
1187 if (list.length() < 1)
1204#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1211#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1222#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1364 "time for recursive call: ");
1376 "time for recursive call: ");
1386 bool initialized=
false;
1409 "time for recursive call: ");
1477 "time for recursive call: ");
1533 "time for newton_interpolation: ");
1561 "time for successful termination Fp: ");
1565 "time for unsuccessful termination Fp: ");
1583 ASSERT (
A.size() == r,
"vector does not have right size");
1593 for (
int i= 0;
i < r - 1;
i++)
1595 for (
int j=
i + 1;
j < r;
j++)
1609 for (
int i= 0;
i < r;
i++)
1613 for (
int i= 0;
i < r;
i++)
1622 for (
int i= 1;
i <= r;
i++,
j++)
1625 for (
int l= 0;
l <
A.size();
l++)
1636 ASSERT (
A.size() == r,
"vector does not have right size");
1645 for (
int i= 0;
i < r - 1;
i++)
1647 for (
int j=
i + 1;
j < r;
j++)
1661 for (
int i= 0;
i < r;
i++)
1666 for (
int i= 0;
i < r;
i++)
1676 for (
int i= 1;
i <= r;
i++,
j++)
1680 for (
int l= 1;
l <=
A.size();
l++)
1681 tmp +=
A[
l - 1]*
j.getItem()[
l];
1693 for (
int i=
rk;
i >= 1;
i--)
1697 for (
int j=
M.columns() - 1;
j >= 1;
j--)
1716 for (
int i=
M.rows();
i >= 1;
i--)
1721 for (
int j=
M.columns();
j >= 1;
j--,
k++)
1742 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1746 for (
int i= 1;
i <=
M.rows();
i++)
1747 for (
int j= 1;
j <=
M.columns();
j++)
1751 for (
int i= 0;
i < L.
size();
i++,
j++)
1752 (*
N) (
j,
M.columns() + 1)= L[
i];
1777 for (
int i= 0;
i <
M.rows();
i++)
1778 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1779 M= (*N) (1,
M.rows(), 1,
M.columns());
1787 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1791 for (
int i= 1;
i <=
M.rows();
i++)
1792 for (
int j= 1;
j <=
M.columns();
j++)
1796 for (
int i= 0;
i < L.
size();
i++,
j++)
1797 (*
N) (
j,
M.columns() + 1)= L[
i];
1809 #if __FLINT_RELEASE >= 30100
1817 #elif defined(HAVE_NTL)
1834 M= (*N) (1,
M.rows(), 1,
M.columns());
1836 for (
int i= 0;
i <
M.rows();
i++)
1837 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1846 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1850 for (
int i= 1;
i <=
M.rows();
i++)
1851 for (
int j= 1;
j <=
M.columns();
j++)
1855 for (
int i= 0;
i < L.
size();
i++,
j++)
1856 (*
N) (
j,
M.columns() + 1)= L[
i];
1873 if (
rk !=
M.columns())
1898 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1902 for (
int i= 1;
i <=
M.rows();
i++)
1903 for (
int j= 1;
j <=
M.columns();
j++)
1906 for (
int i= 0;
i < L.
size();
i++,
j++)
1907 (*
N) (
j,
M.columns() + 1)= L[
i];
1919 #if __FLINT_RELEASE >= 30100
1924 #elif defined(HAVE_NTL)
1940 if (
rk !=
M.columns())
1942 #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
1952 #elif defined(HAVE_NTL)
1998#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2011 "expected an eval point with only one component");
2044 for (
int i= 0;
i <
A.size();
i++)
2091 if (list.length() >=
bound)
2096 for (
int i= 0;
i <
k;
i++)
2114 if (
result.getLast().isOne() ||
result.getLast().isZero())
2173 if (list.length() >=
bound)
2190 i.getItem() *=
j.getItem();
2220 if (F ==
G)
return F/
Lc(F);
2302 if (
V_buf.level() != 1)
2335 for (
int k= 0;
k <
i;
k++)
2359 bool initialized=
false;
2391 if (
k.exp() !=
l.exp())
2428 pL[
k] [
i]=
l.coeff();
2504 if (F ==
G)
return F/
Lc(F);
2598 if (
V_buf.level() != 1)
2646 bool initialized=
false;
2684 if (
k.exp() !=
l.exp())
2748 pL[
k] [
i]=
l.coeff();
2759 if (
pMat[
k].rows() >=
i + 1)
2767 if (
pMat[1].rows() >=
i + 1)
2786 for (
int j= 1;
j <=
pMat[1].columns();
j++)
2797 for (
int i= 0;
i <
pMat[0].rows();
i++)
2808 if (
V_buf.level() != 1)
2857 if (
k.exp() !=
l.exp())
2887 if (
pMat[
k].rows() >=
i + 1)
2896 for (
int j= 1;
j <=
Mat.rows();
j++)
2897 for (
int k= 1;
k <=
Mat.columns();
k++)
2900 for (
int j= 1;
j <=
Mat.rows();
j++)
2901 for (
int k= 1;
k <=
Mat.columns();
k++)
2932 for (
int j= 2;
j <=
pMat[
i].rows();
j++)
2942 if (
V_buf.level() == 1)
2989 for (
int k= 1;
k <=
bufMat.columns();
k++)
2992 for (
int j= 1;
j <=
pMat[
i].rows();
j++)
3004 if (
V_buf.level() != 1)
3058 int ind2= 0,
ind3= 2;
3063 l++, ind2++,
ind3++)
3066 for (
int i= 0;
i <
pMat[0].rows();
i++)
3149 if (F ==
G)
return F/
Lc(F);
3291 "time for recursive call: ");
3303 "time for recursive call: ");
3466 "time for recursive call: ");
3487 "time for recursive call: ");
3531 "time for newton interpolation: ");
3581 if (F ==
G)
return F/
Lc(F);
3671 "time for recursive call: ");
3682 "time for recursive call: ");
3692 bool initialized=
false;
3714 "time for recursive call: ");
3773 "time for recursive call: ");
3873 "time for recursive call: ");
3891 "time for recursive call: ");
3901 bool initialized=
false;
3930 "time for recursive call: ");
3996 "time for recursive call: ");
4044 "time for newton interpolation: ");
4154#if defined(HAVE_NTL) || defined(HAVE_FLINT)
4169 "time for gcd mod p in modular gcd: ");
4248 "time for successful termination in modular gcd: ");
4253 "time for unsuccessful termination in modular gcd: ");
CFMatrix * convertNmod_mat_t2FacCFMatrix(const nmod_mat_t m)
conversion of a FLINT matrix over Z/p to a factory matrix
void convertFacCFMatrix2nmod_mat_t(nmod_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z/p to a nmod_mat_t
void convertFacCFMatrix2Fq_nmod_mat_t(fq_nmod_mat_t M, const fq_nmod_ctx_t fq_con, const CFMatrix &m)
conversion of a factory matrix over F_q to a fq_nmod_mat_t
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CFMatrix * convertFq_nmod_mat_t2FacCFMatrix(const fq_nmod_mat_t m, const fq_nmod_ctx_t &fq_con, const Variable &alpha)
conversion of a FLINT matrix over F_q to a factory matrix
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)
CFMatrix * convertNTLmat_zz_p2FacCFMatrix(const mat_zz_p &m)
CFMatrix * convertNTLmat_zz_pE2FacCFMatrix(const mat_zz_pE &m, const Variable &alpha)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
Conversion to and from NTL.
const CanonicalForm CFMap CFMap & N
const CanonicalForm CFMap CFMap int & both_non_zero
const CanonicalForm CFMap CFMap bool topLevel
coprimality check and change of representation mod n
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
CFArray readOffSolution(const CFMatrix &M, const long rk)
M in row echolon form, rk rank of M.
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
static CanonicalForm GFRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
compute a random element a of GF, s.t. F(a) , F is a univariate polynomial, returns fail if there ar...
CFArray evaluateMonom(const CanonicalForm &F, const CFList &evalPoints)
const CanonicalForm const CanonicalForm const CanonicalForm & coG
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
void mult(CFList &L1, const CFList &L2)
multiply two lists componentwise
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
long gaussianElimFq(CFMatrix &M, CFArray &L, const Variable &alpha)
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
static Variable chooseExtension(const Variable &alpha)
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
CanonicalForm monicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
long gaussianElimFp(CFMatrix &M, CFArray &L)
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
CFArray solveGeneralVandermonde(const CFArray &M, const CFArray &A)
CanonicalForm extractContents(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &contentF, CanonicalForm &contentG, CanonicalForm &ppF, CanonicalForm &ppG, const int d)
static CanonicalForm uni_lcoeff(const CanonicalForm &F)
compute the leading coefficient of F, where F is considered as an element of , order on is dp.
CFArray solveVandermonde(const CFArray &M, const CFArray &A)
const CanonicalForm const CanonicalForm & coF
CanonicalForm cd(bCommonDen(FF))
CanonicalForm nonMonicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CFArray solveSystemFp(const CFMatrix &M, const CFArray &L)
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
static CanonicalForm randomElement(const CanonicalForm &F, const Variable &alpha, CFList &list, bool &fail)
compute a random element a of , s.t. F(a) , F is a univariate polynomial, returns fail if there are...
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
Newton interpolation - Incremental algorithm. Given a list of values alpha_i and a list of polynomial...
CFArray solveSystemFq(const CFMatrix &M, const CFArray &L, const Variable &alpha)
CFList evaluationPoints(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Feval, CanonicalForm &Geval, const CanonicalForm &LCF, const bool &GF, const Variable &alpha, bool &fail, CFList &list)
modular and sparse modular GCD algorithms over finite fields and Z.
bool terminationTest(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &coF, const CanonicalForm &coG, const CanonicalForm &cand)
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
#define ASSERT(expression, message)
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
static CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
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
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
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
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 GFMapUp(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 cf_getBigPrime(int i)
GLOBAL_VAR flint_rand_t FLINTrandom
generate random integers, random elements of finite fields
generate random evaluation points
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
generate random elements in F_p
generate random elements in GF
factory's class for variables
functions to print debug output
#define DEBOUTLN(stream, objects)
const Variable & v
< [in] a sqrfree bivariate poly
CFList *& Aeval
<[in] poly
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
This file defines functions for Hensel lifting.
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
void prune1(const Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
gmp_float log(const gmp_float &a)
int status int void * buf
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)