36#include <NTL/lzz_pEX.h>
52#if defined (HAVE_NTL) || defined(HAVE_FLINT)
54#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
71 if (
i.getItem().inCoeffDomain())
94#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
114 if (
i.getItem().inCoeffDomain())
171 for (;
i.hasItem();
i++)
178#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
216 for (;
i.hasItem();
i++)
235 j.getItem()=
mod (
j.getItem(),
k.getItem());
256 if (
mod (
i.getItem(),
p) == 0)
308 i.getItem() /=
Lc (
i.getItem());
353 ASSERT (
i >= 0,
"ran out of primes");
392 if (
j.getItem() !=
k.getItem())
417 i.getItem() *=
Lc (
j.getItem())*
denf;
464 m.getItem()=
j.getItem();
467 j.getItem()=
m.getItem();
479#if defined(HAVE_NTL) || defined(HAVE_FLINT)
523 e=
b (e -
mulNTL (
i.getItem(),
j.getItem(),
b));
537 for (
int i= 1;
i < d;
i++)
550 for (;
j.hasItem();
j++,
k++,
l++,
ii++)
557 k.getItem() +=
g.mapinto()*modulus;
558 e -=
mulNTL (
g.mapinto(),
b2 (
l.getItem()),
b2)*modulus;
609 if (
bb.getk() >
b.getk() )
b=
bb;
676 for (;
j.hasItem();
j++)
682 j.getItem()=
b(
j.getItem()*
b.inverse(
lc(
j.getItem())));
690 e=
b (e -
mulNTL (
i.getItem(),
j.getItem(),
b));
722 for (
int i= 1;
i < d;
i++)
747 for (;
j.hasItem();
j++,
k++,
l++,
ii++)
759 b2 (
l.getItem()),
b2)*modulus;
767 b2 (
l.getItem()),
b2)*modulus;
786#if defined(HAVE_NTL) || defined(HAVE_FLINT)
835 if (
bb.getk() >
b.getk() )
b=
bb;
864 for (;
i.hasItem();
i++)
897#if __FLINT_RELEASE >= 20700
940 for (;
i.hasItem();
i++)
981 j.getItem()=
modNTL (
j.getItem(),
k.getItem(),
b);
1007#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1044 for (;
i.hasItem();
i++)
1051 j.getItem()=
mulNTL (
j.getItem(), S);
1052 j.getItem()=
modNTL (
j.getItem(),
k.getItem());
1060#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1150 for (
k= 1;
k <= (
j+1)/2;
k++)
1155 && (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
1158 two.coeff()),
b) -
M (
k + 1, 1) -
M (
j -
k + 2, 1);
1168 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
1177 tmp[0] +=
M (
k + 1, 1);
1222 if (
two.hasTerms() &&
two.exp() ==
j + 1)
1237 for (
k= 1;
k <= (
j+1)/2;
k++)
1242 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
1245 two.coeff()),
b) -
M (
k + 1,
l + 1) -
M (
j -
k + 2,
l + 1);
1255 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
1272#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1308 for (;
j.hasItem();
j++,
i++)
1311 M (1,
i + 1)=
Pi [
i];
1322 for (
i= 1;
i <
l;
i++)
1332#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1357 for (
i= start;
i < end;
i++)
1367#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1382 i.getItem()=
mod (
i.getItem(),
y);
1418 e -=
i.getItem()*
j.getItem();
1426 for (
int i= 1;
i < d;
i++)
1438 for (;
j.hasItem();
j++,
k++,
l++,
ii++)
1509 e -=
mulMod (
i.getItem(),
j.getItem(),
M);
1517 for (
int i= 1;
i < d;
i++)
1530 for (;
j.hasItem();
j++,
k++,
l++,
ii++)
1661 for (
k= 1;
k <= (
j+1)/2;
k++)
1666 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
1680 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
1689 tmp[0] +=
M (
k + 1, 1);
1732 if (
two.hasTerms() &&
two.exp() ==
j + 1)
1747 for (
k= 1;
k <= (
j+1)/2;
k++)
1752 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
1756 M (
j -
k + 2,
l + 1);
1766 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
1783#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1811 for (;
i.hasItem();
i++,
k++)
1814 M (1,
k + 1)=
Pi [
k];
1817 for (
int d= 1; d <
l[1]; d++)
1841 for (
i= start;
i < end;
i++)
1878 for (;
i.hasItem();
i++,
k++)
1881 M (1,
k + 1)=
Pi [
k];
1884 for (
int d= 1; d <
lNew; d++)
1892#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1908 for (
int i= 0;
i < 2;
i++)
1973 if (
j + 2 <=
M.rows())
2004 while (
two.hasTerms() &&
two.exp() >
j)
two++;
2005 for (
k= 1;
k <= (
j+1)/2;
k++)
2010 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
2013 two.coeff())) -
M (
k + 1, 1) -
M (
j -
k + 2, 1);
2023 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
2031 tmp[0] +=
M (
k + 1, 1);
2037 if (
j + 2 <=
M.rows())
2040 -
M(1,1) -
M (
j + 2,1);
2067 if (
j + 2 <=
M.rows())
2071 M (
j + 1,
l + 1)= 0;
2093 while (
two.hasTerms() &&
two.exp() >
j)
two++;
2094 for (
k= 1;
k <= (
j+1)/2;
k++)
2099 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
2102 (
Pi[
l - 1] [
k] +
two.coeff())) -
M (
k + 1,
l + 1) -
2103 M (
j -
k + 2,
l + 1);
2110 Pi[
l - 1] [
k]) -
M (
k + 1,
l + 1);
2113 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
2116 (
Pi[
l - 1] [
k] +
two.coeff())) -
M (
k + 1,
l + 1);
2127 if (
j + 2 <=
M.rows())
2130 ) -
M(1,
l+1) -
M (
j + 2,
l+1);
2152#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2196 for (
i= 1;
i <
Pi.size();
i++)
2221 for (
i= 1;
i <
l;
i++)
2245 ASSERT (
E.isUnivariate() ||
E.inCoeffDomain(),
2246 "constant or univariate poly expected");
2247 ASSERT (
i.getItem().isUnivariate() ||
i.getItem().inCoeffDomain(),
2248 "constant or univariate poly expected");
2249 ASSERT (
j.getItem().isUnivariate() ||
j.getItem().inCoeffDomain(),
2250 "constant or univariate poly expected");
2260 i.getItem()=
mod (
i.getItem(),
y);
2263 i.getItem()=
mod (
i.getItem(),
y);
2276 e -=
j.getItem()*
i.getItem();
2281 for (
int i= 1;
i < d;
i++)
2297 k.getItem() +=
j.getItem()*
power (
y,
i);
2298 e -=
l.getItem()*(
j.getItem()*
power (
y,
i));
2312#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2357 buf[
k]=
i.getItem();
2369 if (
j + 2 <=
M.rows())
2399 while (
two.hasTerms() &&
two.exp() >
j)
two++;
2400 for (
k= 1;
k <= (
j+1)/2;
k++)
2405 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
2419 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
2428 tmp[0] +=
M (
k + 1, 1);
2435 if (
j + 2 <=
M.rows())
2438 -
M(1,1) -
M (
j + 2,1);
2465 if (
j + 2 <=
M.rows())
2470 M (
j + 1,
l + 1)= 0;
2492 while (
two.hasTerms() &&
two.exp() >
j)
two++;
2493 for (
k= 1;
k <= (
j+1)/2;
k++)
2498 (
two.hasTerms() &&
two.exp() ==
j -
k + 1))
2502 M (
j -
k + 2,
l + 1);
2512 else if (
two.hasTerms() &&
two.exp() ==
j -
k + 1)
2526 if (
j + 2 <=
M.rows())
2567#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2617 for (
int d= 1; d <
l[1]; d++)
2631#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2681 for (
int d= 1; d <
lNew; d++)
2696#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2716 for (
int i= 0;
i < 2;
i++)
2750#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2760 i.getItem()=
mod (
i.getItem(),
y);
2805 for (
i= 1;
i <
Pi.size();
i++)
2854#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2883 for (
int i= 1;
i <
Pi.size();
i++)
2886 M (1,
i + 1)=
Pi [
i];
2924 for (
int d= 1; d <
lNew; d++)
2939#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2966 for (
int i= 0;
i < 2;
i++)
2974 for (
int i= 2;
i <=
length &&
j.hasItem();
i++,
j++,
k++)
CanonicalForm convertFq_poly_t2FacCF(const fq_poly_t p, const Variable &x, const Variable &alpha, const fq_ctx_t ctx)
conversion of a FLINT poly over Fq (for non-word size p) to a CanonicalForm with alg....
CanonicalForm convertFq_nmod_poly_t2FacCF(const fq_nmod_poly_t p, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t ctx)
conversion of a FLINT poly over Fq to a CanonicalForm with alg. variable alpha and polynomial variabl...
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
void convertFacCF2Fmpz_mod_poly_t(fmpz_mod_poly_t result, const CanonicalForm &f, const fmpz_t p)
conversion of a factory univariate poly over Z to a FLINT poly over Z/p (for non word size p)
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
void convertFacCF2Fq_poly_t(fq_poly_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory univariate poly over F_q (for non-word size p) to a FLINT fq_poly_t
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
ZZ_pEX convertFacCF2NTLZZ_pEX(const CanonicalForm &f, const ZZ_pX &mipo)
CanonicalForm in Z_p(a)[X] to NTL ZZ_pEX.
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Conversion to and from NTL.
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
void tryNTLXGCD(zz_pEX &d, zz_pEX &s, zz_pEX &t, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the extended GCD d=s*a+t*b, fail is set to true if a zero divisor is encountered
This file defines functions for univariate GCD and extended GCD over Z/p[t]/(f)[x] for reducible f.
static void sort(int **points, int sizePoints)
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
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.
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
static CanonicalForm bound(const CFMatrix &M)
int cf_getBigPrime(int i)
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
factory's class for variables
class to do operations mod p^k for int's p and k
functions to print debug output
#define DEBOUTLN(stream, objects)
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
REvaluation E(1, terms.length(), IntRandom(25))
int hasAlgVar(const CanonicalForm &f, const Variable &v)
modpk coeffBound(const CanonicalForm &f, int p, const CanonicalForm &mipo)
compute p^k larger than the bound on the coefficients of a factor of f over Q (mipo)
void findGoodPrime(const CanonicalForm &f, int &start)
find a big prime p from our tables such that no term of f vanishes mod p
bivariate factorization over Q(a)
const Variable & v
< [in] a sqrfree bivariate poly
CFList diophantineHenselQa(const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha)
solve mod over by p-adic lifting
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
static int mod(const CFList &L, const CanonicalForm &p)
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
fq_nmod_ctx_clear(fq_con)
static CFList Farey(const CFList &L, const CanonicalForm &q)
static void chineseRemainder(const CFList &x1, const CanonicalForm &q1, const CFList &x2, const CanonicalForm &q2, CFList &xnew, CanonicalForm &qnew)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
CFList modularDiophant(const CanonicalForm &f, const CFList &factors, const CanonicalForm &M)
fq_nmod_poly_init(prod, fq_con)
CFList nonMonicHenselLift2(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &LCs1, const CFList &LCs2, bool &bad)
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
CanonicalForm replaceLC(const CanonicalForm &F, const CanonicalForm &c)
CFList diophantine(const CanonicalForm &F, const CFList &factors)
static CFList replacevar(const CFList &L, const Variable &a, const Variable &b)
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
CFList diophantineQa(const CanonicalForm &F, const CanonicalForm &G, const CFList &factors, modpk &b, const Variable &alpha)
solve mod over by first computing mod and if no zero divisor occurred compute it mod
void nonMonicHenselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, const CFList &products, int j, const CFList &MOD, bool &noOneToOne)
convertFacCF2nmod_poly_t(FLINTmipo, M)
void henselLiftResume12(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b)
resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)...
CFList nonMonicHenselLift232(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M, const CFList &LCs1, const CFList &LCs2, bool &bad)
static CFList mapinto(const CFList &L)
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
CFList multiRecDiophantine(const CanonicalForm &F, const CFList &factors, const CFList &recResult, const CFList &M, int d)
nmod_poly_clear(FLINTmipo)
static void henselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFList &MOD)
static void tryDiophantine(CFList &result, const CanonicalForm &F, const CFList &factors, const CanonicalForm &M, bool &fail)
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
void henselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const modpk &b)
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
CFList diophantineHensel(const CanonicalForm &F, const CFList &factors, const modpk &b)
fq_nmod_poly_clear(prod, fq_con)
This file defines functions for Hensel lifting.
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CanonicalForm divNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
division of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z,...
CanonicalForm modNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
mod of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f), Z, Q, Q(a),...
This file defines functions for fast multiplication and division with remainder.
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
operations mod p^k and some other useful functions for factorization
void setReduce(const Variable &alpha, bool reduce)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
static BOOLEAN length(leftv result, leftv arg)
int status int void size_t count
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)