62 for (
int i = 0;
i <= n;
i++)
72 for (
int i= 1;
i <= n;
i++)
103 for (
int i= 1;
i <= n;
i++)
141 for (
int j=
i + 1;
j <=
m;
j++)
221 for (
int i= 2;
i <
l + 1;
i++,
j++)
237 for (
int i = n;
i >= 0;
i--)
243 ASSERT (
A.min() == 2,
"expected A.min() == 2");
258 for (
int j=
i + 1;
j <= n;
j++)
276 if (
k == 2 && n == 3)
320 for (
int i=
A.min();
i <=
A.max();
i++)
365 for (
int i= 1;
i <
U.level() - 1;
i++)
391 if(
count == 0 && delta != 0)
456 for(
int i=pl-1;
i>0;
i--)
exp[
i]=0;
486 for(
int i=0;
i<=
ll;
i++)
537 CanonicalForm F,
G,
f,
g, d,
Fb,
Gb,
Db,
Fbt,
Gbt,
Dbt,
B0,
B,
D0,
lcF,
lcG,
595 return N(d*
gcd(F,
g));
640 DEBOUTLN(
cerr,
"search for evaluation, delta = " << delta );
644 if (!
findeval( F,
G,
Fb,
Gb,
Db,
b, delta,
degF,
degG,
maxeval,
count,
675 else if (delta ==
degG)
700 if (!
findeval( F,
G,
Fbt,
Gbt,
Dbt,
bt, delta,
degF,
degG,
maxeval,
count,
723 else if (
dd < delta )
743 else if (delta ==
degG)
763 if ( delta !=
degF && delta !=
degG )
773 if (((
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()) &&
775 || (
xxx1.inCoeffDomain() && !
xxx2.inCoeffDomain()))
783 else if (((
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()) &&
785 || (!
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()))
841 "time for termination test in EZ: ")
868#if defined(HAVE_NTL) || defined(HAVE_FLINT)
880 else if (
FF.isZero() &&
GG.
isZero())
return FF.genOne();
910 CanonicalForm F,
G,
f,
g, d,
Fb,
Gb,
Db,
Fbt,
Gbt,
Dbt,
B0,
B,
D0,
lcF,
lcG,
956 return N(d*
gcd(F,
g));
997 else if (
p == 5 ||
p == 7)
1023 if (
p == 2 && d < 6)
1037 #elif defined(HAVE_NTL)
1059 #elif defined(HAVE_NTL)
1076 else if ((
p == 3 && d < 4) || ((
p == 5 ||
p == 7) && d < 3))
1088 #elif defined(HAVE_NTL)
1139 if( !
findeval( F,
G,
Fb,
Gb,
Db,
b, delta,
degF,
degG,
maxeval,
count, o,
1194 else if (delta ==
degG)
1233 if( !
findeval(F,
G,
Fbt,
Gbt,
Dbt,
bt, delta,
degF,
degG,
maxeval,
count, o,
1309 else if (delta ==
degG)
1345 if( delta !=
degF && delta !=
degG )
1354 if (((
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()) &&
1356 || (
xxx1.inCoeffDomain() && !
xxx2.inCoeffDomain()))
1364 else if (((
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()) &&
1366 || (!
xxx1.inCoeffDomain() &&
xxx2.inCoeffDomain()))
1492 "time for termination test EZ_P: ");
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Conversion to and from NTL.
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
const CanonicalForm CFMap CFMap & N
static CanonicalForm myShift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation)
STATIC_VAR int maxNumEval
static CanonicalForm gcd_mon(CanonicalForm F, CanonicalForm G)
static const double log2exp
static Evaluation optimize4Lift(const CanonicalForm &F, CFMap &M, CFMap &N, const Evaluation &A)
static void gcd_mon_rec(CanonicalForm G, CanonicalForm &cf, int *exp, int pl)
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
const CanonicalForm CFMap CFMap int & both_non_zero
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
const CanonicalForm CFMap & M
STATIC_VAR int sizePerVars1
static CanonicalForm myReverseShift(const CanonicalForm &F, const CFList &evaluation)
static bool findeval(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Fb, CanonicalForm &Gb, CanonicalForm &Db, REvaluation &b, int delta, int degF, int degG, int maxeval, int &count, int &k, int bound, int &l)
Extended Zassenhaus GCD over finite fields and Z.
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
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....
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
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...
modular and sparse modular GCD algorithms over finite fields and Z.
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_USE_EZGCD_P
set to 1 to use EZGCD over F_q
static const int SW_RATIONAL
set to 1 for computations over Q
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
#define GaloisFieldDomain
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
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
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
class to evaluate a polynomial at points
generate random elements in F_p
generate random elements in GF
class to generate random evaluation points
factory's class for variables
functions to print debug output
#define DEBINCLEVEL(stream, msg)
#define DEBOUTLN(stream, objects)
#define DEBDECLEVEL(stream, msg)
const CanonicalForm int const CFList & evaluation
nmod_poly_init(FLINTmipo, getCharacteristic())
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 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.
nmod_poly_clear(FLINTmipo)
This file defines functions for Hensel lifting.
bool isZero(const CFArray &A)
checks if entries of A are zero
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)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
INST_VAR CanonicalForm gf_mipo
gmp_float exp(const gmp_float &a)
int status int void size_t count
int status int void * buf
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)