100 for (
int i = n;
i >= 0;
i--)
113 for (
int i= 1;
i <= n;
i++)
142 for (
int i= 1;
i <= n;
i++)
177 while (min_max_deg == 0)
185 for (
int j=
i + 1;
j <=
m;
j++)
233 for (
int i= 1;
i <= n;
i++)
300 for (;
i.hasTerms();
i++)
323 for (
int i= 1;
i <= d;
i++)
327 gcdcFcG=
gcd (uniContentF, uniContentG);
328 contentF *= uniContentF;
329 contentG *= uniContentG;
372 interPoly= oldInterPoly + ((u - oldInterPoly(
alpha,
x))/newtonPoly(
alpha,
x))
392 double bound=
pow ((
double)
p, (
double) d);
403 while (
find (list, random))
409 while (
find (list, random))
412 if (F (random,
x) == 0)
417 }
while (
find (list, random));
442 BuildIrred (NTLIrredpoly,
i*
m);
542 gcdcAcB=
gcd (cA, cB);
552 gcdlcAlcB=
gcd (lcA, lcB);
558 coF=
N (ppA*(cA/gcdcAcB));
559 coG=
N (ppB*(cB/gcdcAcB));
568 coF=
N (ppA*(cA/gcdcAcB));
569 coG=
N (ppB*(cB/gcdcAcB));
574 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
585 bool inextension=
false;
590 int bound1=
degree (ppA, 1);
591 int bound2=
degree (ppB, 1);
602 bool prim_fail=
false;
606 prim_elem_alpha= prim_elem;
608 if (V_buf3 != V_buf4)
610 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
611 G_m=
mapDown (G_m, prim_elem, im_prim_elem, V_buf4, source, dest);
612 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem, V_buf4, source, dest);
613 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem, V_buf4, source, dest);
614 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
616 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
617 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
618 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
620 lcA=
mapDown (lcA, prim_elem, im_prim_elem, V_buf4, source, dest);
621 lcB=
mapDown (lcB, prim_elem, im_prim_elem, V_buf4, source, dest);
623 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
627 ASSERT (!prim_fail,
"failure in integer factorizer");
631 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
634 im_prim_elem_alpha= im_prim_elem;
636 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
637 im_prim_elem, source, dest);
642 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
643 im_prim_elem, source, dest);
644 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
645 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
646 coF_m=
mapUp (coF_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
647 coG_m=
mapUp (coG_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
648 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
650 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
651 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
652 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
654 lcA=
mapUp (lcA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
655 lcB=
mapUp (lcB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
663 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
664 coF_random_element, coG_random_element, V_buf,
667 "time for recursive call: ");
668 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
676 modGCDFq (ppA(random_element,
x), ppB(random_element,
x),
677 coF_random_element, coG_random_element, V_buf,
680 "time for recursive call: ");
681 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
695 ppA=
mapDown (ppA, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
696 ppB=
mapDown (ppB, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
699 coF=
N (ppA*(cA/gcdcAcB));
700 coG=
N (ppB*(cB/gcdcAcB));
705 if (!
find (
l, random_element))
706 l.append (random_element);
711 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
713 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
715 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
735 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
736 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
737 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
739 "time for newton interpolation: ");
745 if (gcdlcAlcB.
isOne())
764 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
765 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
766 ppCoF=
mapDown (ppCoF, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
767 ppCoG=
mapDown (ppCoG, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
768 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
769 coF=
N ((cA/gcdcAcB)*ppCoF);
770 coG=
N ((cB/gcdcAcB)*ppCoG);
772 "time for successful termination test Fq: ");
774 return N(gcdcAcB*ppH);
777 else if (((
degree (ppCoF,1)+
degree (ppH,1) == bound1) &&
782 coF=
N ((cA/gcdcAcB)*ppCoF);
783 coG=
N ((cB/gcdcAcB)*ppCoG);
785 "time for successful termination test Fq: ");
786 return N(gcdcAcB*ppH);
789 "time for unsuccessful termination test Fq: ");
795 newtonPoly= newtonPoly*(
x - random_element);
796 m=
m*(
x - random_element);
797 if (!
find (
l, random_element))
798 l.append (random_element);
828 while (
find (list, random))
831 if (F (random,
x) == 0)
836 }
while (
find (list, random));
935 gcdcAcB=
gcd (cA, cB);
945 gcdlcAlcB=
gcd (lcA, lcB);
950 coF=
N (ppA*(cA/gcdcAcB));
951 coG=
N (ppB*(cB/gcdcAcB));
959 coF=
N (ppA*(cA/gcdcAcB));
960 coG=
N (ppB*(cB/gcdcAcB));
965 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
976 bool inextension=
false;
982 int bound1=
degree (ppA, 1);
983 int bound2=
degree (ppB, 1);
992 if (
ipower (
p, kk*expon) < (1 << 16))
996 expon= (int)
floor((
log ((
double)((1<<16) - 1)))/(
log((
double)
p)*kk));
997 ASSERT (expon >= 2,
"not enough points in modGCDGF");
1006 newtonPoly=
GFMapUp (newtonPoly, kk);
1011 gcdlcAlcB=
GFMapUp (gcdlcAlcB, kk);
1018 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1019 coF_random_element, coG_random_element,
1022 "time for recursive call: ");
1023 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1029 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1030 coF_random_element, coG_random_element,
1033 "time for recursive call: ");
1034 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1051 coF=
N (ppA*(cA/gcdcAcB));
1052 coG=
N (ppB*(cB/gcdcAcB));
1057 if (!
find (
l, random_element))
1058 l.append (random_element);
1063 (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element)) *
1066 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1067 *coF_random_element;
1068 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1069 *coG_random_element;
1088 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1089 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1090 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1092 "time for newton interpolation: ");
1098 if (gcdlcAlcB.
isOne())
1116 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
1120 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
1121 coF=
N ((cA/gcdcAcB)*ppCoF);
1122 coG=
N ((cB/gcdcAcB)*ppCoG);
1125 "time for successful termination GF: ");
1126 return N(gcdcAcB*ppH);
1136 coF=
N ((cA/gcdcAcB)*ppCoF);
1137 coG=
N ((cB/gcdcAcB)*ppCoG);
1139 "time for successful termination GF: ");
1140 return N(gcdcAcB*ppH);
1144 "time for unsuccessful termination GF: ");
1150 newtonPoly= newtonPoly*(
x - random_element);
1151 m=
m*(
x - random_element);
1152 if (!
find (
l, random_element))
1153 l.append (random_element);
1179 while (
find (list, random))
1182 if (F (random,
x) == 0)
1187 }
while (
find (list, random));
1253 if (best_level == 0)
1280 gcdcAcB=
gcd (cA, cB);
1289 gcdlcAlcB=
gcd (lcA, lcB);
1296 coF=
N (ppA*(cA/gcdcAcB));
1297 coG=
N (ppB*(cB/gcdcAcB));
1308 coF=
N (ppA*(cA/gcdcAcB));
1309 coG=
N (ppB*(cB/gcdcAcB));
1314 CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1315 coF_m, coG_m, ppCoF, ppCoG;
1325 bool inextension=
false;
1328 int bound1=
degree (ppA, 1);
1329 int bound2=
degree (ppB, 1);
1337 if (!fail && !inextension)
1342 modGCDFp (ppA (random_element,
x), ppB (random_element,
x),
1343 coF_random_element, coG_random_element,
topLevel,
1346 "time for recursive call: ");
1347 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1349 else if (!fail && inextension)
1354 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1355 coF_random_element, coG_random_element, V_buf,
1358 "time for recursive call: ");
1359 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1361 else if (fail && !inextension)
1368 bool initialized=
false;
1387 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1388 coF_random_element, coG_random_element,
alpha,
1391 "time for recursive call: ");
1392 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1394 else if (fail && inextension)
1401 bool prim_fail=
false;
1406 if (V_buf3 !=
alpha)
1409 G_m=
mapDown (G_m, prim_elem, im_prim_elem,
alpha, source, dest);
1410 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem,
alpha, source, dest);
1411 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem,
alpha, source, dest);
1412 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
1414 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
1415 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
1416 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
1418 lcA=
mapDown (lcA, prim_elem, im_prim_elem,
alpha, source, dest);
1419 lcB=
mapDown (lcB, prim_elem, im_prim_elem,
alpha, source, dest);
1421 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
1425 ASSERT (!prim_fail,
"failure in integer factorizer");
1435 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
1436 im_prim_elem, source, dest);
1437 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1438 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1439 coF_m=
mapUp (coF_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1440 coG_m=
mapUp (coG_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1441 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
1443 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1444 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1445 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
1447 lcA=
mapUp (lcA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1448 lcB=
mapUp (lcB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1455 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1456 coF_random_element, coG_random_element, V_buf,
1459 "time for recursive call: ");
1460 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1474 coF=
N (ppA*(cA/gcdcAcB));
1475 coG=
N (ppB*(cB/gcdcAcB));
1481 if (!
find (
l, random_element))
1482 l.append (random_element);
1486 G_random_element= (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element))
1489 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1490 *coF_random_element;
1491 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1492 *coG_random_element;
1511 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1512 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1513 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1515 "time for newton_interpolation: ");
1521 if (gcdlcAlcB.
isOne())
1540 coF=
N ((cA/gcdcAcB)*ppCoF);
1541 coG=
N ((cB/gcdcAcB)*ppCoG);
1543 "time for successful termination Fp: ");
1544 return N(gcdcAcB*ppH);
1547 "time for unsuccessful termination Fp: ");
1553 newtonPoly= newtonPoly*(
x - random_element);
1554 m=
m*(
x - random_element);
1555 if (!
find (
l, random_element))
1556 l.append (random_element);
1564 ASSERT (
A.size() == r,
"vector does not have right size");
1573 bool notDistinct=
false;
1574 for (
int i= 0;
i < r - 1;
i++)
1576 for (
int j=
i + 1;
j < r;
j++)
1590 for (
int i= 0;
i < r;
i++)
1591 master *=
x -
M [
i];
1594 for (
int i= 0;
i < r;
i++)
1596 tmp= master/(
x -
M [
i]);
1597 tmp /= tmp (
M [
i], 1);
1603 for (
int i= 1;
i <= r;
i++,
j++)
1606 for (
int l= 0;
l <
A.size();
l++)
1607 tmp +=
A[
l]*
j.getItem()[
l];
1617 ASSERT (
A.size() == r,
"vector does not have right size");
1625 bool notDistinct=
false;
1626 for (
int i= 0;
i < r - 1;
i++)
1628 for (
int j=
i + 1;
j < r;
j++)
1642 for (
int i= 0;
i < r;
i++)
1643 master *=
x -
M [
i];
1647 for (
int i= 0;
i < r;
i++)
1649 tmp= master/(
x -
M [
i]);
1650 tmp /= tmp (
M [
i], 1);
1657 for (
int i= 1;
i <= r;
i++,
j++)
1661 for (
int l= 1;
l <=
A.size();
l++)
1662 tmp +=
A[
l - 1]*
j.getItem()[
l];
1674 for (
int i= rk;
i >= 1;
i--)
1678 for (
int j=
M.columns() - 1;
j >= 1;
j--)
1697 for (
int i=
M.rows();
i >= 1;
i--)
1702 for (
int j=
M.columns();
j >= 1;
j--,
k++)
1709 if (
k > partialSol.
size() - 1)
1712 tmp3 +=
tmp2*partialSol[partialSol.
size() -
k - 1];
1723 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1727 for (
int i= 1;
i <=
M.rows();
i++)
1728 for (
int j= 1;
j <=
M.columns();
j++)
1732 for (
int i= 0;
i < L.
size();
i++,
j++)
1733 (*
N) (
j,
M.columns() + 1)= L[
i];
1737 long rk= nmod_mat_rref (FLINTN);
1741 nmod_mat_clear (FLINTN);
1751 long rk= gauss (*NTLN);
1758 for (
int i= 0;
i <
M.rows();
i++)
1759 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1760 M= (*N) (1,
M.rows(), 1,
M.columns());
1768 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1772 for (
int i= 1;
i <=
M.rows();
i++)
1773 for (
int j= 1;
j <=
M.columns();
j++)
1777 for (
int i= 0;
i < L.
size();
i++,
j++)
1778 (*
N) (
j,
M.columns() + 1)= L[
i];
1786 zz_pE::init (NTLMipo);
1788 long rk= gauss (*NTLN);
1795 M= (*N) (1,
M.rows(), 1,
M.columns());
1797 for (
int i= 0;
i <
M.rows();
i++)
1798 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1807 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1811 for (
int i= 1;
i <=
M.rows();
i++)
1812 for (
int j= 1;
j <=
M.columns();
j++)
1816 for (
int i= 0;
i < L.
size();
i++,
j++)
1817 (*
N) (
j,
M.columns() + 1)= L[
i];
1822 long rk= nmod_mat_rref (FLINTN);
1831 long rk= gauss (*NTLN);
1834 if (rk !=
M.columns())
1837 nmod_mat_clear (FLINTN);
1845 nmod_mat_clear (FLINTN);
1859 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1863 for (
int i= 1;
i <=
M.rows();
i++)
1864 for (
int j= 1;
j <=
M.columns();
j++)
1867 for (
int i= 0;
i < L.
size();
i++,
j++)
1868 (*
N) (
j,
M.columns() + 1)= L[
i];
1876 zz_pE::init (NTLMipo);
1878 long rk= gauss (*NTLN);
1881 if (rk !=
M.columns())
1914 int numMon=
size (F);
1924 for (
int k= 0;
k < recResult.
size();
k++)
1926 j += recResult.
size();
1944 "expected an eval point with only one component");
1952 int numMon=
size (F);
1964 for (
int k= 0;
k < recResult.
size();
k++)
1966 j += recResult.
size();
1977 for (
int i= 0;
i <
A.size();
i++)
1982 tmp= tmp (
j.getItem(),
k);
2017 bool zeroOneOccured=
false;
2018 bool allEqual=
false;
2029 for (
int i= 0;
i <
k;
i++)
2047 if (
result.getLast().isOne() ||
result.getLast().isZero())
2048 zeroOneOccured=
true;
2050 if (
find (list, random))
2052 zeroOneOccured=
false;
2060 zeroOneOccured=
false;
2080 zeroOneOccured=
false;
2092 Geval= Geval (
i.getItem(),
j);
2093 LCeval= LCeval (
i.getItem(),
j);
2098 if (!
find (list, random))
2100 zeroOneOccured=
false;
2111 }
while (
find (list, random));
2123 i.getItem() *=
j.getItem();
2135 Beval= Beval (
i.getItem(),
j);
2153 if (F ==
G)
return F/
Lc(F);
2161 if (best_level == 0)
2179 gcdcAcB=
gcd (cA, cB);
2199 gcdlcAlcB=
gcd (lcA, lcB);
2200 int skelSize=
size (skel, skel.
mvar());
2206 biggestSize=
tmax (biggestSize,
size (
i.coeff()));
2211 bool evalFail=
false;
2222 for (
int i= 0;
i < biggestSize;
i++)
2235 if (V_buf.
level() != 1)
2244 bool prim_fail=
false;
2248 prim_elem_alpha= prim_elem;
2250 ASSERT (!prim_fail,
"failure in integer factorizer");
2254 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2260 im_prim_elem_alpha= im_prim_elem;
2262 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2263 prim_elem, im_prim_elem, source, dest);
2266 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2267 im_prim_elem, source, dest);
2268 for (
int k= 0;
k <
i;
k++)
2271 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2272 im_prim_elem, source, dest);
2273 gcds[
k]=
mapUp (gcds[
k], V_buf4, V_buf, prim_elem, im_prim_elem,
2279 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2280 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2292 bool initialized=
false;
2315 delete[] pEvalPoints;
2324 if (
k.exp() !=
l.exp())
2326 delete[] pEvalPoints;
2343 if (Monoms.
size() == 0)
2346 coeffMonoms=
new CFArray [skelSize];
2353 for (
int i= 0;
i < biggestSize;
i++)
2357 for (
int k= 0;
k < skelSize;
k++,
l++)
2361 pL[
k] [
i]=
l.coeff();
2373 for (
int k= 0;
k < skelSize;
k++)
2375 if (biggestSize != coeffMonoms[
k].
size())
2378 for (
int i= 0;
i < coeffMonoms[
k].
size();
i++)
2379 bufArray [
i]= pL[
k] [
i];
2385 if (solution.
size() == 0)
2387 delete[] pEvalPoints;
2390 delete[] coeffMonoms;
2396 for (
int l= 0;
l < solution.
size();
l++)
2397 result += solution[
l]*Monoms [ind +
l];
2398 ind += solution.
size();
2401 delete[] pEvalPoints;
2404 delete[] coeffMonoms;
2437 if (F ==
G)
return F/
Lc(F);
2445 if (best_level == 0)
2464 gcdcAcB=
gcd (cA, cB);
2484 gcdlcAlcB=
gcd (lcA, lcB);
2485 int skelSize=
size (skel, skel.
mvar());
2493 bufSize=
size (
i.coeff());
2494 biggestSize=
tmax (biggestSize, bufSize);
2495 numberUni += bufSize;
2498 numberUni= (int)
ceil ( (
double) numberUni / (skelSize - 1));
2499 biggestSize=
tmax (biggestSize , numberUni);
2501 numberUni= biggestSize +
size (
LC(skel)) - 1;
2502 int biggestSize2=
tmax (numberUni, biggestSize);
2508 bool evalFail=
false;
2519 for (
int i= 0;
i < biggestSize;
i++)
2531 if (V_buf.
level() != 1)
2540 bool prim_fail=
false;
2544 prim_elem_alpha= prim_elem;
2546 ASSERT (!prim_fail,
"failure in integer factorizer");
2550 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2556 im_prim_elem_alpha= im_prim_elem;
2558 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2559 prim_elem, im_prim_elem, source, dest);
2562 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
2563 im_prim_elem, source, dest);
2566 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2567 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2579 bool initialized=
false;
2608 delete[] pEvalPoints;
2617 if (
k.exp() !=
l.exp())
2619 delete[] pEvalPoints;
2636 if (Monoms.
size() == 0)
2639 coeffMonoms=
new CFArray [skelSize];
2645 int minimalColumnsIndex;
2647 minimalColumnsIndex= 1;
2649 minimalColumnsIndex= 0;
2650 int minimalColumns=-1;
2655 for (
int i= 0;
i < skelSize;
i++)
2659 minimalColumns= coeffMonoms[
i].
size();
2662 if (minimalColumns > coeffMonoms[
i].
size())
2664 minimalColumns= coeffMonoms[
i].
size();
2665 minimalColumnsIndex=
i;
2670 pMat[0]=
CFMatrix (biggestSize, coeffMonoms[0].
size());
2671 pMat[1]=
CFMatrix (biggestSize, coeffMonoms[minimalColumnsIndex].
size());
2673 for (
int i= 0;
i < biggestSize;
i++)
2677 for (
int k= 0;
k < skelSize;
k++,
l++)
2681 pL[
k] [
i]=
l.coeff();
2683 if (
i == 0 &&
k != 0 &&
k != minimalColumnsIndex)
2685 else if (
i == 0 && (
k == 0 ||
k == minimalColumnsIndex))
2687 if (
i > 0 && (
k == 0 ||
k == minimalColumnsIndex))
2692 if (pMat[
k].rows() >=
i + 1)
2694 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2695 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2698 if (
k == minimalColumnsIndex)
2700 if (pMat[1].rows() >=
i + 1)
2702 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2703 pMat[1] (
i + 1, ind)= coeffEval[ind - 1];
2712 int matRows, matColumns;
2713 matRows= pMat[1].
rows();
2714 matColumns= pMat[0].
columns() - 1;
2715 matColumns += pMat[1].
columns();
2717 Mat=
CFMatrix (matRows, matColumns);
2718 for (
int i= 1;
i <= matRows;
i++)
2720 Mat (
i,
j)= pMat[1] (
i,
j);
2722 for (
int j= pMat[1].columns() + 1;
j <= matColumns;
2725 for (
int i= 1;
i <= matRows;
i++)
2726 Mat (
i,
j)= (-pMat [0] (
i, ind + 1))*pL[minimalColumnsIndex] [
i - 1];
2730 for (
int i= 0;
i < pMat[0].
rows();
i++)
2731 firstColumn [
i]= pMat[0] (
i + 1, 1);
2733 CFArray bufArray= pL[minimalColumnsIndex];
2735 for (
int i= 0;
i < biggestSize;
i++)
2736 pL[minimalColumnsIndex] [
i] *= firstColumn[
i];
2741 if (V_buf.
level() != 1)
2743 pL[minimalColumnsIndex], V_buf);
2746 pL[minimalColumnsIndex]);
2748 if (solution.
size() == 0)
2753 pL[minimalColumnsIndex]= bufArray;
2756 if (biggestSize != biggestSize2)
2758 bufpEvalPoints= pEvalPoints;
2759 pEvalPoints=
new CFList [biggestSize2];
2762 for (
int i= 0;
i < biggestSize;
i++)
2764 pEvalPoints[
i]= bufpEvalPoints [
i];
2765 gcds[
i]= bufGcds[
i];
2767 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2775 delete[] pEvalPoints;
2778 delete[] coeffMonoms;
2780 if (bufpEvalPoints !=
NULL)
2781 delete [] bufpEvalPoints;
2790 if (
k.exp() !=
l.exp())
2792 delete[] pEvalPoints;
2795 delete[] coeffMonoms;
2797 if (bufpEvalPoints !=
NULL)
2798 delete [] bufpEvalPoints;
2806 gcds[
i + biggestSize]=
g;
2809 for (
int i= 0;
i < biggestSize;
i++)
2813 for (
int k= 1;
k < skelSize;
k++,
l++)
2816 pMat[
k]=
CFMatrix (biggestSize2,coeffMonoms[
k].
size()+biggestSize2-1);
2817 if (
k == minimalColumnsIndex)
2820 if (pMat[
k].rows() >=
i + 1)
2822 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2823 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2828 pMat[0]=
CFMatrix (biggestSize2, coeffMonoms[0].
size() + biggestSize2 - 1);
2829 for (
int j= 1;
j <= Mat.
rows();
j++)
2831 pMat [0] (
j,
k)= Mat (
j,
k);
2833 for (
int j= 1;
j <= Mat.
rows();
j++)
2835 pMat [minimalColumnsIndex] (
j,
k)= Mat (
j,
k);
2837 for (
int i= 0;
i < skelSize;
i++)
2841 for (
int j= 0;
j < bufArray.
size();
j++)
2842 pL[
i] [
j]= bufArray [
j];
2845 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2849 for (
int k= 0;
k < skelSize;
k++,
l++)
2851 pL[
k] [
i + biggestSize]=
l.coeff();
2853 if (pMat[
k].rows() >=
i + biggestSize + 1)
2855 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2856 pMat[
k] (
i + biggestSize + 1, ind)= coeffEval[ind - 1];
2861 for (
int i= 0;
i < skelSize;
i++)
2863 if (pL[
i].
size() > 1)
2865 for (
int j= 2;
j <= pMat[
i].
rows();
j++)
2866 pMat[
i] (
j, coeffMonoms[
i].
size() +
j - 1)=
2871 matColumns= biggestSize2 - 1;
2873 for (
int i= 0;
i < skelSize;
i++)
2875 if (V_buf.
level() == 1)
2880 if (pMat[
i] (coeffMonoms[
i].
size(), coeffMonoms[
i].
size()) == 0)
2882 delete[] pEvalPoints;
2885 delete[] coeffMonoms;
2887 if (bufpEvalPoints !=
NULL)
2888 delete [] bufpEvalPoints;
2894 matRows += pMat[
i].
rows() - coeffMonoms[
i].
size();
2898 Mat=
CFMatrix (matRows, matColumns);
2902 for (
int i= 0;
i < skelSize;
i++)
2904 if (coeffMonoms[
i].
size() + 1 >= pMat[
i].rows() || coeffMonoms[
i].
size() + 1 >= pMat[
i].columns())
2906 delete[] pEvalPoints;
2909 delete[] coeffMonoms;
2911 if (bufpEvalPoints !=
NULL)
2912 delete [] bufpEvalPoints;
2918 bufMat= pMat[
i] (coeffMonoms[
i].
size() + 1, pMat[
i].
rows(),
2921 for (
int j= 1;
j <= bufMat.
rows();
j++)
2923 Mat (
j + ind,
k)= bufMat(
j,
k);
2924 bufArray2= coeffMonoms[
i].
size();
2925 for (
int j= 1;
j <= pMat[
i].
rows();
j++)
2927 if (
j > coeffMonoms[
i].
size())
2928 bufArray [
j-coeffMonoms[
i].
size() + ind - 1]= pL[
i] [
j - 1];
2930 bufArray2 [
j - 1]= pL[
i] [
j - 1];
2933 ind += bufMat.
rows();
2937 if (V_buf.
level() != 1)
2942 if (solution.
size() == 0)
2944 delete[] pEvalPoints;
2947 delete[] coeffMonoms;
2949 if (bufpEvalPoints !=
NULL)
2950 delete [] bufpEvalPoints;
2960 for (
int i= 0;
i < skelSize;
i++)
2963 for (
int i= 0;
i < bufSolution.
size();
i++, ind++)
2964 result += Monoms [ind]*bufSolution[
i];
2973 delete[] pEvalPoints;
2976 delete[] coeffMonoms;
2979 if (bufpEvalPoints !=
NULL)
2980 delete [] bufpEvalPoints;
2991 int ind2= 0, ind3= 2;
2993 for (
int l= 0;
l < minimalColumnsIndex;
l++)
2994 ind += coeffMonoms[
l].
size();
2996 l++,
ind2++, ind3++)
2999 for (
int i= 0;
i < pMat[0].
rows();
i++)
3000 firstColumn[
i] += solution[
l]*pMat[0] (
i + 1, ind3);
3002 for (
int l= 0;
l < solution.
size() + 1 - pMat[0].columns();
l++)
3003 result += solution[
l]*Monoms [ind +
l];
3004 ind= coeffMonoms[0].
size();
3005 for (
int k= 1;
k < skelSize;
k++)
3007 if (
k == minimalColumnsIndex)
3009 ind += coeffMonoms[
k].
size();
3012 if (
k != minimalColumnsIndex)
3014 for (
int i= 0;
i < biggestSize;
i++)
3015 pL[
k] [
i] *= firstColumn [
i];
3018 if (biggestSize != coeffMonoms[
k].
size() &&
k != minimalColumnsIndex)
3021 for (
int i= 0;
i < bufArray.
size();
i++)
3022 bufArray [
i]= pL[
k] [
i];
3028 if (solution.
size() == 0)
3030 delete[] pEvalPoints;
3033 delete[] coeffMonoms;
3040 if (
k != minimalColumnsIndex)
3042 for (
int l= 0;
l < solution.
size();
l++)
3043 result += solution[
l]*Monoms [ind +
l];
3044 ind += solution.
size();
3048 delete[] pEvalPoints;
3052 delete[] coeffMonoms;
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);
3514 if (F ==
G)
return F/
Lc(F);
3519 if (best_level == 0)
return B.
genOne();
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)
3615 "time for recursive call: ");
3616 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3618 else if (fail && !inextension)
3625 bool initialized=
false;
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)
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");
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)
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");
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);
4102 "time for gcd mod p in modular gcd: ");
4181 "time for successful termination in modular gcd: ");
4186 "time for unsuccessful termination in modular gcd: ");