3514 if (F == G)
return F/
Lc(F);
3519 if (best_level == 0)
return B.
genOne();
3528 return N (
gcd (A, B));
3536 gcdcAcB=
gcd (cA, cB);
3556 gcdlcAlcB=
gcd (lcA, lcB);
3572 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3579 bool inextension=
false;
3589 if (random_element == 0 && !fail)
3591 if (!
find (l, random_element))
3592 l.
append (random_element);
3596 if (!fail && !inextension)
3604 "time for recursive call: ");
3605 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3607 else if (!fail && inextension)
3612 sparseGCDFq (ppA (random_element, x), ppB (random_element, x), alpha,
3615 "time for recursive call: ");
3616 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3618 else if (fail && !inextension)
3625 bool initialized=
false;
3644 sparseGCDFq (ppA (random_element, x), ppB (random_element, x), alpha,
3647 "time for recursive call: ");
3648 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3650 else if (fail && inextension)
3657 bool prim_fail=
false;
3662 if (V_buf3 != alpha)
3664 m=
mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3665 G_m=
mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3666 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, alpha, source,
3668 ppA=
mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
3669 ppB=
mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
3670 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha, source,
3673 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3677 ASSERT (!prim_fail,
"failure in integer factorizer");
3681 im_prim_elem=
mapPrimElem (prim_elem, alpha, V_buf);
3687 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3688 im_prim_elem, source, dest);
3689 m=
mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3690 G_m=
mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3691 newtonPoly=
mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
3693 ppA=
mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3694 ppB=
mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3695 gcdlcAlcB=
mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
3703 sparseGCDFq (ppA (random_element, x), ppB (random_element, x), V_buf,
3706 "time for recursive call: ");
3707 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3725 if (!
find (l, random_element))
3726 l.
append (random_element);
3731 (gcdlcAlcB(random_element, x)/
uni_lcoeff (G_random_element))
3734 skeleton= G_random_element;
3750 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
3763 return N(gcdcAcB*ppH);
3767 newtonPoly= newtonPoly*(x - random_element);
3768 m= m*(x - random_element);
3769 if (!
find (l, random_element))
3770 l.
append (random_element);
3783 if (random_element == 0 && !fail)
3785 if (!
find (l, random_element))
3786 l.
append (random_element);
3790 bool sparseFail=
false;
3791 if (!fail && !inextension)
3795 if (
LC (skeleton).inCoeffDomain())
3798 skeleton, x, sparseFail, coeffMonoms,
3803 skeleton, x, sparseFail,
3804 coeffMonoms, Monoms);
3806 "time for recursive call: ");
3807 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3809 else if (!fail && inextension)
3813 if (
LC (skeleton).inCoeffDomain())
3816 skeleton, alpha, sparseFail, coeffMonoms,
3821 skeleton, alpha, sparseFail, coeffMonoms,
3824 "time for recursive call: ");
3825 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3827 else if (fail && !inextension)
3834 bool initialized=
false;
3852 if (
LC (skeleton).inCoeffDomain())
3855 skeleton, alpha, sparseFail, coeffMonoms,
3860 skeleton, alpha, sparseFail, coeffMonoms,
3863 "time for recursive call: ");
3864 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3866 else if (fail && inextension)
3873 bool prim_fail=
false;
3878 if (V_buf3 != alpha)
3880 m=
mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3881 G_m=
mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3882 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, alpha,
3884 ppA=
mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
3885 ppB=
mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
3886 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha,
3889 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3893 ASSERT (!prim_fail,
"failure in integer factorizer");
3897 im_prim_elem=
mapPrimElem (prim_elem, alpha, V_buf);
3903 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3904 im_prim_elem, source, dest);
3905 m=
mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3906 G_m=
mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3907 newtonPoly=
mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
3909 ppA=
mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3910 ppB=
mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3911 gcdlcAlcB=
mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
3918 if (
LC (skeleton).inCoeffDomain())
3921 skeleton, V_buf, sparseFail, coeffMonoms,
3926 skeleton, V_buf, sparseFail,
3927 coeffMonoms, Monoms);
3929 "time for recursive call: ");
3930 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3951 if (!
find (l, random_element))
3952 l.
append (random_element);
3957 (gcdlcAlcB(random_element, x)/
uni_lcoeff (G_random_element))
3975 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
3977 "time for newton interpolation: ");
3990 return N(gcdcAcB*ppH);
3995 newtonPoly= newtonPoly*(x - random_element);
3996 m= m*(x - random_element);
3997 if (!
find (l, random_element))
3998 l.
append (random_element);
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)
#define TIMING_END_AND_PRINT(t, msg)
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...
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
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 &)
void prune(Variable &alpha)
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
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
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
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)
#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 .