87#if defined(HAVE_NTL)|| defined(HAVE_FLINT)
98 for (
int i = n;
i >= 0;
i--)
111 for (
int i= 1;
i <= n;
i++)
140 for (
int i= 1;
i <= n;
i++)
183 for (
int j=
i + 1;
j <=
m;
j++)
231 for (
int i= 1;
i <= n;
i++)
298 for (;
i.hasTerms();
i++)
321 for (
int i= 1;
i <= d;
i++)
390 double bound=
pow ((
double)
p, (
double) d);
453#if defined(HAVE_NTL) || defined(HAVE_FLINT)
460#if defined(HAVE_NTL) || defined(HAVE_FLINT)
476#if defined(HAVE_NTL) || defined(HAVE_FLINT)
678 "time for recursive call: ");
691 "time for recursive call: ");
750 "time for newton interpolation: ");
783 "time for successful termination test Fq: ");
796 "time for successful termination test Fq: ");
800 "time for unsuccessful termination test Fq: ");
1009 ASSERT (
expon >= 2,
"not enough points in modGCDGF");
1034 "time for recursive call: ");
1045 "time for recursive call: ");
1104 "time for newton interpolation: ");
1137 "time for successful termination GF: ");
1151 "time for successful termination GF: ");
1156 "time for unsuccessful termination GF: ");
1203#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1210#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1221#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1363 "time for recursive call: ");
1375 "time for recursive call: ");
1385 bool initialized=
false;
1408 "time for recursive call: ");
1476 "time for recursive call: ");
1532 "time for newton_interpolation: ");
1560 "time for successful termination Fp: ");
1564 "time for unsuccessful termination Fp: ");
1582 ASSERT (
A.size() == r,
"vector does not have right size");
1592 for (
int i= 0;
i < r - 1;
i++)
1594 for (
int j=
i + 1;
j < r;
j++)
1608 for (
int i= 0;
i < r;
i++)
1612 for (
int i= 0;
i < r;
i++)
1621 for (
int i= 1;
i <= r;
i++,
j++)
1624 for (
int l= 0;
l <
A.size();
l++)
1635 ASSERT (
A.size() == r,
"vector does not have right size");
1644 for (
int i= 0;
i < r - 1;
i++)
1646 for (
int j=
i + 1;
j < r;
j++)
1660 for (
int i= 0;
i < r;
i++)
1665 for (
int i= 0;
i < r;
i++)
1675 for (
int i= 1;
i <= r;
i++,
j++)
1679 for (
int l= 1;
l <=
A.size();
l++)
1680 tmp +=
A[
l - 1]*
j.getItem()[
l];
1692 for (
int i=
rk;
i >= 1;
i--)
1696 for (
int j=
M.columns() - 1;
j >= 1;
j--)
1715 for (
int i=
M.rows();
i >= 1;
i--)
1720 for (
int j=
M.columns();
j >= 1;
j--,
k++)
1741 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1745 for (
int i= 1;
i <=
M.rows();
i++)
1746 for (
int j= 1;
j <=
M.columns();
j++)
1750 for (
int i= 0;
i < L.
size();
i++,
j++)
1751 (*
N) (
j,
M.columns() + 1)= L[
i];
1776 for (
int i= 0;
i <
M.rows();
i++)
1777 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1778 M= (*N) (1,
M.rows(), 1,
M.columns());
1786 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1790 for (
int i= 1;
i <=
M.rows();
i++)
1791 for (
int j= 1;
j <=
M.columns();
j++)
1795 for (
int i= 0;
i < L.
size();
i++,
j++)
1796 (*
N) (
j,
M.columns() + 1)= L[
i];
1812 #elif defined(HAVE_NTL)
1830 M= (*N) (1,
M.rows(), 1,
M.columns());
1832 for (
int i= 0;
i <
M.rows();
i++)
1833 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1842 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1846 for (
int i= 1;
i <=
M.rows();
i++)
1847 for (
int j= 1;
j <=
M.columns();
j++)
1851 for (
int i= 0;
i < L.
size();
i++,
j++)
1852 (*
N) (
j,
M.columns() + 1)= L[
i];
1869 if (
rk !=
M.columns())
1894 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1898 for (
int i= 1;
i <=
M.rows();
i++)
1899 for (
int j= 1;
j <=
M.columns();
j++)
1902 for (
int i= 0;
i < L.
size();
i++,
j++)
1903 (*
N) (
j,
M.columns() + 1)= L[
i];
1916 #elif defined(HAVE_NTL)
1932 if (
rk !=
M.columns())
1934 #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
1944 #elif defined(HAVE_NTL)
1990#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2003 "expected an eval point with only one component");
2036 for (
int i= 0;
i <
A.size();
i++)
2088 for (
int i= 0;
i <
k;
i++)
2106 if (
result.getLast().isOne() ||
result.getLast().isZero())
2182 i.getItem() *=
j.getItem();
2212 if (F ==
G)
return F/
Lc(F);
2294 if (
V_buf.level() != 1)
2327 for (
int k= 0;
k <
i;
k++)
2351 bool initialized=
false;
2383 if (
k.exp() !=
l.exp())
2420 pL[
k] [
i]=
l.coeff();
2496 if (F ==
G)
return F/
Lc(F);
2590 if (
V_buf.level() != 1)
2638 bool initialized=
false;
2676 if (
k.exp() !=
l.exp())
2740 pL[
k] [
i]=
l.coeff();
2751 if (
pMat[
k].rows() >=
i + 1)
2759 if (
pMat[1].rows() >=
i + 1)
2778 for (
int j= 1;
j <=
pMat[1].columns();
j++)
2789 for (
int i= 0;
i <
pMat[0].rows();
i++)
2800 if (
V_buf.level() != 1)
2849 if (
k.exp() !=
l.exp())
2879 if (
pMat[
k].rows() >=
i + 1)
2888 for (
int j= 1;
j <=
Mat.rows();
j++)
2889 for (
int k= 1;
k <=
Mat.columns();
k++)
2892 for (
int j= 1;
j <=
Mat.rows();
j++)
2893 for (
int k= 1;
k <=
Mat.columns();
k++)
2924 for (
int j= 2;
j <=
pMat[
i].rows();
j++)
2934 if (
V_buf.level() == 1)
2981 for (
int k= 1;
k <=
bufMat.columns();
k++)
2984 for (
int j= 1;
j <=
pMat[
i].rows();
j++)
2996 if (
V_buf.level() != 1)
3050 int ind2= 0,
ind3= 2;
3055 l++, ind2++,
ind3++)
3058 for (
int i= 0;
i <
pMat[0].rows();
i++)
3141 if (F ==
G)
return F/
Lc(F);
3283 "time for recursive call: ");
3295 "time for recursive call: ");
3458 "time for recursive call: ");
3479 "time for recursive call: ");
3523 "time for newton interpolation: ");
3573 if (F ==
G)
return F/
Lc(F);
3663 "time for recursive call: ");
3674 "time for recursive call: ");
3684 bool initialized=
false;
3706 "time for recursive call: ");
3765 "time for recursive call: ");
3865 "time for recursive call: ");
3883 "time for recursive call: ");
3893 bool initialized=
false;
3922 "time for recursive call: ");
3988 "time for recursive call: ");
4036 "time for newton interpolation: ");
4146#if defined(HAVE_NTL) || defined(HAVE_FLINT)
4161 "time for gcd mod p in modular gcd: ");
4240 "time for successful termination in modular gcd: ");
4245 "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)