3082 if (F ==
G)
return F/
Lc(F);
3087 if (best_level == 0)
return B.
genOne();
3104 gcdcAcB=
gcd (cA, cB);
3124 gcdlcAlcB=
gcd (lcA, lcB);
3139 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3146 bool inextension=
false;
3154 if (random_element == 0 && !fail)
3156 if (!
find (
l, random_element))
3157 l.append (random_element);
3167 bool prim_fail=
false;
3170 if (V_buf4 ==
alpha)
3171 prim_elem_alpha= prim_elem;
3173 if (V_buf3 != V_buf4)
3175 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3176 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3177 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3179 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3180 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3181 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4, source,
3184 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3188 ASSERT (!prim_fail,
"failure in integer factorizer");
3192 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3194 if (V_buf4 ==
alpha)
3195 im_prim_elem_alpha= im_prim_elem;
3197 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
3198 im_prim_elem, source, dest);
3204 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3205 im_prim_elem, source, dest);
3206 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3207 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3208 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3210 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3211 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3212 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3221 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3224 "time for recursive call: ");
3225 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3233 sparseGCDFq (ppA(random_element,
x), ppB(random_element,
x), V_buf,
3236 "time for recursive call: ");
3237 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3254 if (!
find (
l, random_element))
3255 l.append (random_element);
3260 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3263 skeleton= G_random_element;
3278 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3290 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3291 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3293 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3295 return N(gcdcAcB*ppH);
3299 return N(gcdcAcB*ppH);
3302 newtonPoly= newtonPoly*(
x - random_element);
3303 m=
m*(
x - random_element);
3304 if (!
find (
l, random_element))
3305 l.append (random_element);
3314 if (random_element == 0 && !fail)
3316 if (!
find (
l, random_element))
3317 l.append (random_element);
3327 bool prim_fail=
false;
3330 if (V_buf4 ==
alpha)
3331 prim_elem_alpha= prim_elem;
3333 if (V_buf3 != V_buf4)
3335 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3336 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3337 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3339 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3340 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3341 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
3344 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3348 ASSERT (!prim_fail,
"failure in integer factorizer");
3352 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3354 if (V_buf4 ==
alpha)
3355 im_prim_elem_alpha= im_prim_elem;
3357 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
3358 prim_elem, im_prim_elem, source, dest);
3364 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3365 im_prim_elem, source, dest);
3366 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3367 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3368 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3370 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3371 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3373 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3385 bool sparseFail=
false;
3386 if (
LC (skeleton).inCoeffDomain())
3389 skeleton,V_buf, sparseFail, coeffMonoms,Monoms);
3393 skeleton, V_buf, sparseFail, coeffMonoms,
3399 "time for recursive call: ");
3400 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3406 bool sparseFail=
false;
3407 if (
LC (skeleton).inCoeffDomain())
3410 skeleton,V_buf, sparseFail,coeffMonoms, Monoms);
3414 skeleton, V_buf, sparseFail, coeffMonoms,
3420 "time for recursive call: ");
3421 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3438 if (!
find (
l, random_element))
3439 l.append (random_element);
3444 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3462 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3464 "time for newton interpolation: ");
3478 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3479 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3481 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3483 return N(gcdcAcB*ppH);
3488 return N(gcdcAcB*ppH);
3493 newtonPoly= newtonPoly*(
x - random_element);
3494 m=
m*(
x - random_element);
3495 if (!
find (
l, random_element))
3496 l.append (random_element);
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
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 ,...
CanonicalForm monicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
void prune1(const Variable &alpha)
TIMING_START(fac_alg_resultant)
static Variable chooseExtension(const Variable &alpha)
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
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...
CanonicalForm nonMonicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
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 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...
const CanonicalForm CFMap CFMap bool topLevel
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
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.
const CanonicalForm CFMap CFMap & N
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
#define ASSERT(expression, message)
#define DEBOUTLN(stream, objects)
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .