52 for (
int i = 0;
i <= n;
i++)
53 degsf[
i]= degsg[
i]= 0;
66 int xlevel= x.
level();
68 for (
int i= 1;
i <= n;
i++)
70 if (degsf[
i] != 0 && degsg[
i] != 0)
75 if (degsf[
i] == 0 && degsg[
i] != 0 &&
i <= G.
level())
80 if (degsg[
i] == 0 && degsf[
i] &&
i <= F.
level())
89 degsfx= degsf [xlevel];
90 degsgx= degsg [xlevel];
99 for (
int i= 1;
i <= n;
i++)
103 if (
i != pos && (degsf[
i] != 0 || degsg [
i] != 0))
116 if (both_non_zero == 0)
126 for (
int i= 1;
i <= n;
i++)
130 if (degsf[
i] != 0 && degsg[
i] == 0 &&
i <= F.
level())
132 if (k + both_non_zero !=
i)
139 if (degsf[
i] == 0 && degsg[
i] != 0 &&
i <= G.
level())
141 if (l + g_zero + both_non_zero !=
i)
157 if (degsf [i] != 0 && degsg [i] != 0)
158 min_max_deg= degsgx*degsf[
i] + degsfx*degsg[
i];
161 while (min_max_deg == 0 && i < m + 1)
164 if (degsf [i] != 0 && degsg [i] != 0)
165 min_max_deg= degsgx*degsf[
i] + degsfx*degsg[
i];
169 for (
int j= i + 1;
j <=
m;
j++)
171 if (degsgx*degsf[
j] + degsfx*degsg[
j] <= min_max_deg &&
172 degsf[
j] != 0 && degsg [
j] != 0)
174 min_max_deg= degsgx*degsf[
j] + degsfx*degsg[
j];
180 if (l != k && l != xlevel && k != 1)
197 if (i != k && i != xlevel && k != 1)
217 for (
int i= 1;
i <= n;
i++)
219 if (degsf[
i] == 0 && degsg[
i] == 0)
226 if (both_zero != 0 &&
i != 1)
266 nmod_poly_t FLINTF, FLINTG;
269 mp_limb_t FLINTresult= nmod_poly_resultant (FLINTF, FLINTG);
297 zz_pE::init (NTLMipo);
321 FEval= F (evalPoint.
item(), 2);
322 GEval=
G (evalPoint.
item(), 2);
323 if (
degree (FEval, 1) < degF ||
degree (GEval, 1) < degG)
341 interPoly= oldInterPoly+((u - oldInterPoly (alpha, x))/newtonPoly (alpha, x))
358 return power (A, degBx);
360 return power (B, degAx);
363 return power (A, degBx);
365 return power (B, degAx);
393 bool extOfExt=
false;
397 if (!algExt && (p < (1 << 28)))
401 int deg= ceil (29.0*((
double)
log (2)/
log (p)))+1;
405 gen= AlgExtGen.
clone();
406 for (
int i= 0;
i <
p;
i++)
416 int deg= ceil (29.0*((
double)
log (2)/
log (p)));
420 mpz_init (field_size);
421 mpz_ui_pow_ui (field_size, p,
425 if (mpz_fits_sint_p (field_size))
431 bool primFail=
false;
434 ASSERT (!primFail,
"failure in integer factorizer");
438 imPrimElemAlpha=
mapPrimElem (primElemAlpha, alpha, v);
439 F=
mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
440 G=
mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
445 mpz_ui_pow_ui (field_size, p, deg);
446 while (deg /
degree (
getMipo (alpha)) >= 2 && !mpz_fits_sint_p (field_size))
449 mpz_ui_pow_ui (field_size, p, deg);
456 bool primFail=
false;
459 ASSERT (!primFail,
"failure in integer factorizer");
463 imPrimElemAlpha=
mapPrimElem (primElemAlpha, alpha, v);
464 F=
mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
465 G=
mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
468 mpz_clear (field_size);
471 gen= AlgExtGen.
clone();
472 for (
int i= 0;
i <
p;
i++)
484 H=
newtonInterp ((*gen).item(), recResult, newtonPoly, modResult,
y);
492 if (count > bound || (prob && equalCount == 2 && !H.
inCoeffDomain()))
494 if (!algExt &&
degree (H, alpha) <= 0)
498 if (extOfExt && !
isInExtension (H, imPrimElemAlpha, 1, primElemAlpha,
501 H=
mapDown (H, primElemAlpha, imPrimElemAlpha, alpha, dest, source);
511 newtonPoly *= (y - (*gen).item());
512 if ((*gen).hasItems())
534 result +=
power( x, i.
exp() ) * (c - q);
574 return power (A, degBx);
576 return power (B, degAx);
579 return power (A, degBx);
581 return power (B, degAx);
605 d= (buf > d) ? buf : d;
611 e= (buf > e) ? buf : e;
616 for (
int i= degBx + degAx;
i > 1;
i--)
636 while ( i >= 0 &&
mod( l, p ) == 0)
672 if (newQ > bound || (prob && equalCount == 2))
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
int status int void size_t count
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 ...
generate all elements in F_p(alpha) starting from 0
const CanonicalForm int const CFList const Variable & y
Conversion to and from NTL.
static CanonicalForm bound(const CFMatrix &M)
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
TIMING_START(fac_alg_resultant)
const CanonicalForm CFMap CFMap const Variable & x
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 ...
factory's class for variables
virtual class for generators
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case) ...
generate all elements in F_p starting from 0
gmp_float log(const gmp_float &a)
nmod_poly_clear(FLINTmipo)
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 ...
TIMING_DEFINE_PRINT(fac_resultant_p) static inline void myCompress(const CanonicalForm &F
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Rational abs(const Rational &a)
void prune(Variable &alpha)
This file implements functions to map between extensions of finite fields.
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
generate integers, elements of finite fields
convertFacCF2nmod_poly_t(FLINTmipo, M)
int status int void * buf
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
const CanonicalForm CFMap CFMap & N
virtual bool hasItems() const
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
static const int SW_RATIONAL
set to 1 for computations over Q
const CanonicalForm CFMap & M
Iterators for CanonicalForm's.
generate random integers, random elements of finite fields
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
class to iterate through CanonicalForm's
void 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...
This file provides utility functions for bivariate factorization.
const Variable & v
< [in] a sqrfree bivariate poly
modular resultant algorithm as described by G.
generate random irreducible univariate polynomials
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
#define STICKYASSERT(expression, message)
static CanonicalForm uniResultant(const CanonicalForm &F, const CanonicalForm &G)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
CFGenerator * clone() const
int cf_getBigPrime(int i)
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
#define ASSERT(expression, message)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
CF_NO_INLINE int exp() const
get the current exponent
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
CFGenerator * clone() const
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
static CanonicalForm oneNorm(const CanonicalForm &F)
virtual CanonicalForm item() const
static CanonicalForm balanceUni(const CanonicalForm &f, const CanonicalForm &q)