35#include <NTL/lzz_pEX.h>
41#include "flint/fq_nmod_vec.h"
42#if __FLINT_RELEASE >= 20503
43#include "flint/mpn_extras.h"
44#include "flint/fmpz_mod.h"
49#if defined(HAVE_NTL) || defined(HAVE_FLINT)
60 if (
i.coeff().inBaseDomain())
63 for (
j=
i.coeff();
j.hasTerms();
j++)
253 if (
G.inCoeffDomain())
288 while (d -
i.exp() < 0)
291 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
308 ASSERT (F.
mvar() ==
x,
"main variable of F and x differ");
309 ASSERT (!
g.isZero(),
"expected a unit");
322 for (
int i= 1;
i <=
l;
i++)
355 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
388 ASSERT (F.
level() ==
G.level(),
"F and G have different level");
436#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
448 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
468 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
505 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
513 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
546#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
562 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
614 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
661 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
663#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
682#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
704#elif defined(AHVE_NTL)
774 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
782 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
812#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
830 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
850 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
879 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
880#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
891#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
959#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
970 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
990 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1008 return b(
div (F,
G));
1016 if (!
G.inBaseDomain())
1020#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1032 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1053 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1070 return b(
div (F,
G));
1090 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1098 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1128#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1139 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1159 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
1187 ASSERT (F.
level() ==
G.level(),
"expected polys of same level");
1188#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
1199#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
1275#if ( __FLINT_RELEASE >= 20400)
1293 if (
i.coeff().inCoeffDomain())
1371 if (
i.coeff().inCoeffDomain())
1380 for (
j=
i.coeff();
j.hasTerms();
j++)
1433#if ( __FLINT_RELEASE >= 20400)
1455 if (
i.coeff().inCoeffDomain())
1785#if ( __FLINT_RELEASE >= 20400)
2023#if ( __FLINT_RELEASE >= 20400)
2164#if ( __FLINT_RELEASE >= 20400)
2391 if (
i.coeff().inCoeffDomain())
2408#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2426 if (
i.coeff().inCoeffDomain())
2466 if (
i.coeff().inCoeffDomain())
2524#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2544 if (
f.rep.
length() < (
long) d*(
k+1))
2545 f.rep.SetLength ((
long)d*(
k+1));
2658 if (
f.rep.
length() < (
long) d*(
k+1))
2659 f.rep.SetLength ((
long)d*(
k+1));
2752#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2891#if (!(HAVE_FLINT && __FLINT_RELEASE >= 20400))
2941#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
2998 ASSERT (
M.isUnivariate(),
"M must be univariate");
3004 if (
G.inCoeffDomain())
3012 (F.
level() ==
G.level()))
3030 return mod (
G*F,
M);
3032 return mod (F*
G,
M);
3100 if (
G.inCoeffDomain())
3119 (
degG <= 1 &&
G.level() <=
M.level()))
3203 for (
int j= 1;
j <=
l;
j++,
i++)
3217 else if (L.
length() == 1)
3219 else if (L.
length() == 2)
3227 for (
int j= 1;
j <=
l;
j++,
i++)
3252 while (d -
i.exp() < 0)
3255 for (;
i.hasTerms() && (d -
i.exp() >= 0);
i++)
3270 ASSERT (!
g.isZero(),
"expected a unit");
3286 for (
int i= 1;
i <=
l;
i++)
3355#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3378 bool zz_pEbak= zz_pE::initialized();
3438#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
3482 else if (
x.
level() !=
A.level())
3493 while (
i.hasTerms() &&
i.exp() -
j*
m >= 0)
3536 int m= (
int) ceil ((
double) (
degB + 1)/2.0) + 1;
3537 ASSERT (4*
m >=
degA,
"expected degree (F, 1) < 2*degree (G, 1)");
3607 int m= (
int) ceil ((
double) (
degB + 1)/ 2.0);
3608 ASSERT (3*
m >
degA,
"expected degree (F, 1) < 3*degree (G, 1)");
3776 if (
A.inCoeffDomain())
3783#if (!defined(HAVE_FLINT) || __FLINT_RELEASE < 20400)
3793#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
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....
void convertFacCF2Fq_t(fq_t result, const CanonicalForm &f, const fq_ctx_t ctx)
conversion of a factory element of F_q (for non-word size p) to a FLINT fq_t
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...
CanonicalForm convertFq_t2FacCF(const fq_t poly, const Variable &alpha)
conversion of a FLINT element of F_q with non-word size p to a CanonicalForm with alg....
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
CanonicalForm convertFmpz_mod_poly_t2FacCF(const fmpz_mod_poly_t poly, const Variable &x, const modpk &b)
conversion of a FLINT poly over Z/p (for non word size p) to a CanonicalForm over Z
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
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
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_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 convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm convertNTLZZpX2CF(const ZZ_pX &poly, const Variable &x)
NAME: convertNTLZZpX2CF.
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
CanonicalForm convertNTLZZ_pEX2CF(const ZZ_pEX &f, const Variable &x, const Variable &alpha)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
ZZ_pX convertFacCF2NTLZZpX(const CanonicalForm &f)
NAME: convertFacCF2NTLZZpX.
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Conversion to and from NTL.
CanonicalForm cd(bCommonDen(FF))
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( 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
#define GaloisFieldDomain
Iterators for CanonicalForm's.
class to iterate through CanonicalForm's
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 const CFList const Variable & y
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
const Variable & v
< [in] a sqrfree bivariate poly
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_init(prod, fq_con)
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm mod(const CanonicalForm &F, const CFList &M)
reduce F modulo elements in M.
CanonicalForm uniReverse(const CanonicalForm &F, int d, const Variable &x)
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
void kronSubFq(fq_nmod_poly_t result, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
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),...
void divrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &MOD)
division with remainder of F by G wrt Variable (1) modulo MOD. Uses an algorithm based on Burnikel,...
bool uniFdivides(const CanonicalForm &A, const CanonicalForm &B)
divisibility test for univariate polys
CanonicalForm divFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
void kronSubQa(fmpz_poly_t result, const CanonicalForm &A, int d)
CanonicalForm reverseSubstFp(const nmod_poly_t F, int d)
static CFList split(const CanonicalForm &F, const int m, const Variable &x)
static void divrem32(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
CanonicalForm mulMod2FLINTQ(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm reverse(const CanonicalForm &F, int d)
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
CanonicalForm mulMod2FLINTFqReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm mulFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
CanonicalForm mulMod2FLINTFpReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mulMod2FLINTFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm reverseSubstReciproFq(const fq_nmod_poly_t F, const fq_nmod_poly_t G, int d, int k, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm modFLINTQ(const CanonicalForm &F, const CanonicalForm &G)
void kronSubReciproQ(fmpz_poly_t subA1, fmpz_poly_t subA2, const CanonicalForm &A, int d)
void kronSubReciproFq(fq_nmod_poly_t subA1, fq_nmod_poly_t subA2, const CanonicalForm &A, int d, const fq_nmod_ctx_t fq_con)
CanonicalForm reverseSubstQ(const fmpz_poly_t F, int d)
CanonicalForm mulMod2FLINTQReci(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm reverseSubstFq(const fq_nmod_poly_t F, int d, const Variable &alpha, const fq_nmod_ctx_t fq_con)
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
CanonicalForm mulFLINTQTrunc(const CanonicalForm &F, const CanonicalForm &G, int m)
CanonicalForm mulFLINTQa(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha)
CanonicalForm reverseSubstReciproQ(const fmpz_poly_t F, const fmpz_poly_t G, int d, int k)
static void divrem21(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CFList &M)
CanonicalForm newtonInverse(const CanonicalForm &F, const int n, const Variable &x)
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
void divrem2(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R, const CanonicalForm &M)
division with remainder of F by G wrt Variable (1) modulo M. Uses an algorithm based on Burnikel,...
CanonicalForm reverseSubstQa(const fmpz_poly_t F, int d, const Variable &x, const Variable &alpha, const CanonicalForm &den)
void kronSubReciproFp(nmod_poly_t subA1, nmod_poly_t subA2, const CanonicalForm &A, int d)
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 mulFLINTQaTrunc(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, int m)
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),...
CanonicalForm prodMod(const CFList &L, const CanonicalForm &M)
product of all elements in L modulo M via divide-and-conquer.
CanonicalForm reverseSubstReciproFp(const nmod_poly_t F, const nmod_poly_t G, int d, int k)
void kronSubFp(nmod_poly_t result, const CanonicalForm &A, int d)
CanonicalForm mulMod2FLINTFp(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mulMod2NTLFq(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
CanonicalForm mulMod2FLINTQa(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M)
This file defines functions for fast multiplication and division with remainder.
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
void rem(unsigned long *a, unsigned long *q, unsigned long p, int °a, int degq)
gmp_float exp(const gmp_float &a)
The main handler for Singular numbers which are suitable for Singular polynomials.
int status int void * buf
bool getReduce(const Variable &alpha)