87#if defined(HAVE_NTL)|| defined(HAVE_FLINT)
98 for (
int i = n;
i >= 0;
i--)
111 for (
int i= 1;
i <= n;
i++)
140 for (
int i= 1;
i <= n;
i++)
175 while (min_max_deg == 0)
183 for (
int j=
i + 1;
j <=
m;
j++)
231 for (
int i= 1;
i <= n;
i++)
298 for (;
i.hasTerms();
i++)
321 for (
int i= 1;
i <= d;
i++)
325 gcdcFcG=
gcd (uniContentF, uniContentG);
326 contentF *= uniContentF;
327 contentG *= uniContentG;
370 interPoly= oldInterPoly + ((u - oldInterPoly(
alpha,
x))/newtonPoly(
alpha,
x))
390 double bound=
pow ((
double)
p, (
double) d);
401 while (
find (list, random))
407 while (
find (list, random))
410 if (F (random,
x) == 0)
415 }
while (
find (list, random));
435 nmod_poly_t Irredpoly;
437 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom,
i*
m+1);
447 BuildIrred (NTLIrredpoly,
i*
m);
453#if defined(HAVE_NTL) || defined(HAVE_FLINT)
460#if defined(HAVE_NTL) || defined(HAVE_FLINT)
476#if defined(HAVE_NTL) || defined(HAVE_FLINT)
553 gcdcAcB=
gcd (cA, cB);
563 gcdlcAlcB=
gcd (lcA, lcB);
569 coF=
N (ppA*(cA/gcdcAcB));
570 coG=
N (ppB*(cB/gcdcAcB));
579 coF=
N (ppA*(cA/gcdcAcB));
580 coG=
N (ppB*(cB/gcdcAcB));
585 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
596 bool inextension=
false;
601 int bound1=
degree (ppA, 1);
602 int bound2=
degree (ppB, 1);
613 bool prim_fail=
false;
617 prim_elem_alpha= prim_elem;
619 if (V_buf3 != V_buf4)
621 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
622 G_m=
mapDown (G_m, prim_elem, im_prim_elem, V_buf4, source, dest);
623 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem, V_buf4, source, dest);
624 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem, V_buf4, source, dest);
625 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
627 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
628 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
629 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
631 lcA=
mapDown (lcA, prim_elem, im_prim_elem, V_buf4, source, dest);
632 lcB=
mapDown (lcB, prim_elem, im_prim_elem, V_buf4, source, dest);
634 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
638 ASSERT (!prim_fail,
"failure in integer factorizer");
642 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
645 im_prim_elem_alpha= im_prim_elem;
647 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
648 im_prim_elem, source, dest);
653 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
654 im_prim_elem, source, dest);
655 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
656 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
657 coF_m=
mapUp (coF_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
658 coG_m=
mapUp (coG_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
659 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
661 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
662 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
663 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
665 lcA=
mapUp (lcA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
666 lcB=
mapUp (lcB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
674 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
675 coF_random_element, coG_random_element, V_buf,
678 "time for recursive call: ");
679 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
687 modGCDFq (ppA(random_element,
x), ppB(random_element,
x),
688 coF_random_element, coG_random_element, V_buf,
691 "time for recursive call: ");
692 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
706 ppA=
mapDown (ppA, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
707 ppB=
mapDown (ppB, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
710 coF=
N (ppA*(cA/gcdcAcB));
711 coG=
N (ppB*(cB/gcdcAcB));
716 if (!
find (
l, random_element))
717 l.append (random_element);
722 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
724 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
726 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
746 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
747 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
748 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
750 "time for newton interpolation: ");
756 if (gcdlcAlcB.
isOne())
775 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
776 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
777 ppCoF=
mapDown (ppCoF, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
778 ppCoG=
mapDown (ppCoG, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
779 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
780 coF=
N ((cA/gcdcAcB)*ppCoF);
781 coG=
N ((cB/gcdcAcB)*ppCoG);
783 "time for successful termination test Fq: ");
785 return N(gcdcAcB*ppH);
788 else if (((
degree (ppCoF,1)+
degree (ppH,1) == bound1) &&
793 coF=
N ((cA/gcdcAcB)*ppCoF);
794 coG=
N ((cB/gcdcAcB)*ppCoG);
796 "time for successful termination test Fq: ");
797 return N(gcdcAcB*ppH);
800 "time for unsuccessful termination test Fq: ");
806 newtonPoly= newtonPoly*(
x - random_element);
807 m=
m*(
x - random_element);
808 if (!
find (
l, random_element))
809 l.append (random_element);
840 while (
find (list, random))
843 if (F (random,
x) == 0)
848 }
while (
find (list, random));
947 gcdcAcB=
gcd (cA, cB);
957 gcdlcAlcB=
gcd (lcA, lcB);
962 coF=
N (ppA*(cA/gcdcAcB));
963 coG=
N (ppB*(cB/gcdcAcB));
971 coF=
N (ppA*(cA/gcdcAcB));
972 coG=
N (ppB*(cB/gcdcAcB));
977 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
988 bool inextension=
false;
994 int bound1=
degree (ppA, 1);
995 int bound2=
degree (ppB, 1);
1004 if (
ipower (
p, kk*expon) < (1 << 16))
1008 expon= (int) floor((
log ((
double)((1<<16) - 1)))/(
log((
double)
p)*kk));
1009 ASSERT (expon >= 2,
"not enough points in modGCDGF");
1018 newtonPoly=
GFMapUp (newtonPoly, kk);
1023 gcdlcAlcB=
GFMapUp (gcdlcAlcB, kk);
1030 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1031 coF_random_element, coG_random_element,
1034 "time for recursive call: ");
1035 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1041 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1042 coF_random_element, coG_random_element,
1045 "time for recursive call: ");
1046 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1063 coF=
N (ppA*(cA/gcdcAcB));
1064 coG=
N (ppB*(cB/gcdcAcB));
1069 if (!
find (
l, random_element))
1070 l.append (random_element);
1075 (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element)) *
1078 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1079 *coF_random_element;
1080 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1081 *coG_random_element;
1100 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1101 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1102 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1104 "time for newton interpolation: ");
1110 if (gcdlcAlcB.
isOne())
1128 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
1132 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
1133 coF=
N ((cA/gcdcAcB)*ppCoF);
1134 coG=
N ((cB/gcdcAcB)*ppCoG);
1137 "time for successful termination GF: ");
1138 return N(gcdcAcB*ppH);
1148 coF=
N ((cA/gcdcAcB)*ppCoF);
1149 coG=
N ((cB/gcdcAcB)*ppCoG);
1151 "time for successful termination GF: ");
1152 return N(gcdcAcB*ppH);
1156 "time for unsuccessful termination GF: ");
1162 newtonPoly= newtonPoly*(
x - random_element);
1163 m=
m*(
x - random_element);
1164 if (!
find (
l, random_element))
1165 l.append (random_element);
1191 while (
find (list, random))
1194 if (F (random,
x) == 0)
1199 }
while (
find (list, random));
1203#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1210#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1221#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1270 if (best_level == 0)
1297 gcdcAcB=
gcd (cA, cB);
1306 gcdlcAlcB=
gcd (lcA, lcB);
1313 coF=
N (ppA*(cA/gcdcAcB));
1314 coG=
N (ppB*(cB/gcdcAcB));
1325 coF=
N (ppA*(cA/gcdcAcB));
1326 coG=
N (ppB*(cB/gcdcAcB));
1331 CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1332 coF_m, coG_m, ppCoF, ppCoG;
1342 bool inextension=
false;
1345 int bound1=
degree (ppA, 1);
1346 int bound2=
degree (ppB, 1);
1354 if (!fail && !inextension)
1359 modGCDFp (ppA (random_element,
x), ppB (random_element,
x),
1360 coF_random_element, coG_random_element,
topLevel,
1363 "time for recursive call: ");
1364 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1366 else if (!fail && inextension)
1371 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1372 coF_random_element, coG_random_element, V_buf,
1375 "time for recursive call: ");
1376 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1378 else if (fail && !inextension)
1385 bool initialized=
false;
1404 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1405 coF_random_element, coG_random_element,
alpha,
1408 "time for recursive call: ");
1409 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1411 else if (fail && inextension)
1418 bool prim_fail=
false;
1423 if (V_buf3 !=
alpha)
1426 G_m=
mapDown (G_m, prim_elem, im_prim_elem,
alpha, source, dest);
1427 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem,
alpha, source, dest);
1428 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem,
alpha, source, dest);
1429 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
1431 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
1432 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
1433 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
1435 lcA=
mapDown (lcA, prim_elem, im_prim_elem,
alpha, source, dest);
1436 lcB=
mapDown (lcB, prim_elem, im_prim_elem,
alpha, source, dest);
1438 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
1442 ASSERT (!prim_fail,
"failure in integer factorizer");
1452 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
1453 im_prim_elem, source, dest);
1454 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1455 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1456 coF_m=
mapUp (coF_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1457 coG_m=
mapUp (coG_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1458 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
1460 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1461 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1462 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
1464 lcA=
mapUp (lcA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1465 lcB=
mapUp (lcB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1472 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1473 coF_random_element, coG_random_element, V_buf,
1476 "time for recursive call: ");
1477 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1491 coF=
N (ppA*(cA/gcdcAcB));
1492 coG=
N (ppB*(cB/gcdcAcB));
1498 if (!
find (
l, random_element))
1499 l.append (random_element);
1503 G_random_element= (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element))
1506 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1507 *coF_random_element;
1508 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1509 *coG_random_element;
1528 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1529 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1530 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1532 "time for newton_interpolation: ");
1538 if (gcdlcAlcB.
isOne())
1557 coF=
N ((cA/gcdcAcB)*ppCoF);
1558 coG=
N ((cB/gcdcAcB)*ppCoG);
1560 "time for successful termination Fp: ");
1561 return N(gcdcAcB*ppH);
1564 "time for unsuccessful termination Fp: ");
1570 newtonPoly= newtonPoly*(
x - random_element);
1571 m=
m*(
x - random_element);
1572 if (!
find (
l, random_element))
1573 l.append (random_element);
1582 ASSERT (
A.size() == r,
"vector does not have right size");
1591 bool notDistinct=
false;
1592 for (
int i= 0;
i < r - 1;
i++)
1594 for (
int j=
i + 1;
j < r;
j++)
1608 for (
int i= 0;
i < r;
i++)
1609 master *=
x -
M [
i];
1612 for (
int i= 0;
i < r;
i++)
1614 tmp= master/(
x -
M [
i]);
1615 tmp /= tmp (
M [
i], 1);
1621 for (
int i= 1;
i <= r;
i++,
j++)
1624 for (
int l= 0;
l <
A.size();
l++)
1625 tmp +=
A[
l]*
j.getItem()[
l];
1635 ASSERT (
A.size() == r,
"vector does not have right size");
1643 bool notDistinct=
false;
1644 for (
int i= 0;
i < r - 1;
i++)
1646 for (
int j=
i + 1;
j < r;
j++)
1660 for (
int i= 0;
i < r;
i++)
1661 master *=
x -
M [
i];
1665 for (
int i= 0;
i < r;
i++)
1667 tmp= master/(
x -
M [
i]);
1668 tmp /= tmp (
M [
i], 1);
1675 for (
int i= 1;
i <= r;
i++,
j++)
1679 for (
int l= 1;
l <=
A.size();
l++)
1680 tmp +=
A[
l - 1]*
j.getItem()[
l];
1692 for (
int i= rk;
i >= 1;
i--)
1696 for (
int j=
M.columns() - 1;
j >= 1;
j--)
1715 for (
int i=
M.rows();
i >= 1;
i--)
1720 for (
int j=
M.columns();
j >= 1;
j--,
k++)
1727 if (
k > partialSol.
size() - 1)
1730 tmp3 +=
tmp2*partialSol[partialSol.
size() -
k - 1];
1741 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1745 for (
int i= 1;
i <=
M.rows();
i++)
1746 for (
int j= 1;
j <=
M.columns();
j++)
1750 for (
int i= 0;
i < L.
size();
i++,
j++)
1751 (*
N) (
j,
M.columns() + 1)= L[
i];
1755 long rk= nmod_mat_rref (FLINTN);
1759 nmod_mat_clear (FLINTN);
1769 long rk= gauss (*NTLN);
1776 for (
int i= 0;
i <
M.rows();
i++)
1777 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1778 M= (*N) (1,
M.rows(), 1,
M.columns());
1786 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1790 for (
int i= 1;
i <=
M.rows();
i++)
1791 for (
int j= 1;
j <=
M.columns();
j++)
1795 for (
int i= 0;
i < L.
size();
i++,
j++)
1796 (*
N) (
j,
M.columns() + 1)= L[
i];
1805 fq_nmod_mat_t FLINTN;
1808 long rk= fq_nmod_mat_rref (FLINTN,ctx);
1810 fq_nmod_mat_clear (FLINTN,ctx);
1812 #elif defined(HAVE_NTL)
1820 zz_pE::init (NTLMipo);
1822 long rk= gauss (*NTLN);
1829 M= (*N) (1,
M.rows(), 1,
M.columns());
1831 for (
int i= 0;
i <
M.rows();
i++)
1832 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1841 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1845 for (
int i= 1;
i <=
M.rows();
i++)
1846 for (
int j= 1;
j <=
M.columns();
j++)
1850 for (
int i= 0;
i < L.
size();
i++,
j++)
1851 (*
N) (
j,
M.columns() + 1)= L[
i];
1856 long rk= nmod_mat_rref (FLINTN);
1865 long rk= gauss (*NTLN);
1868 if (rk !=
M.columns())
1871 nmod_mat_clear (FLINTN);
1879 nmod_mat_clear (FLINTN);
1893 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1897 for (
int i= 1;
i <=
M.rows();
i++)
1898 for (
int j= 1;
j <=
M.columns();
j++)
1901 for (
int i= 0;
i < L.
size();
i++,
j++)
1902 (*
N) (
j,
M.columns() + 1)= L[
i];
1911 fq_nmod_mat_t FLINTN;
1914 long rk= fq_nmod_mat_rref (FLINTN,ctx);
1915 #elif defined(HAVE_NTL)
1923 zz_pE::init (NTLMipo);
1925 long rk= gauss (*NTLN);
1931 if (rk !=
M.columns())
1933 #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
1941 fq_nmod_mat_clear (FLINTN,ctx);
1943 #elif defined(HAVE_NTL)
1972 int numMon=
size (F);
1982 for (
int k= 0;
k < recResult.
size();
k++)
1984 j += recResult.
size();
1989#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2002 "expected an eval point with only one component");
2010 int numMon=
size (F);
2022 for (
int k= 0;
k < recResult.
size();
k++)
2024 j += recResult.
size();
2035 for (
int i= 0;
i <
A.size();
i++)
2040 tmp= tmp (
j.getItem(),
k);
2075 bool zeroOneOccured=
false;
2076 bool allEqual=
false;
2087 for (
int i= 0;
i <
k;
i++)
2105 if (
result.getLast().isOne() ||
result.getLast().isZero())
2106 zeroOneOccured=
true;
2108 if (
find (list, random))
2110 zeroOneOccured=
false;
2118 zeroOneOccured=
false;
2138 zeroOneOccured=
false;
2150 Geval= Geval (
i.getItem(),
j);
2151 LCeval= LCeval (
i.getItem(),
j);
2156 if (!
find (list, random))
2158 zeroOneOccured=
false;
2169 }
while (
find (list, random));
2181 i.getItem() *=
j.getItem();
2193 Beval= Beval (
i.getItem(),
j);
2211 if (F ==
G)
return F/
Lc(F);
2219 if (best_level == 0)
2237 gcdcAcB=
gcd (cA, cB);
2257 gcdlcAlcB=
gcd (lcA, lcB);
2258 int skelSize=
size (skel, skel.
mvar());
2264 biggestSize=
tmax (biggestSize,
size (
i.coeff()));
2269 bool evalFail=
false;
2280 for (
int i= 0;
i < biggestSize;
i++)
2293 if (V_buf.
level() != 1)
2302 bool prim_fail=
false;
2306 prim_elem_alpha= prim_elem;
2308 ASSERT (!prim_fail,
"failure in integer factorizer");
2312 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2318 im_prim_elem_alpha= im_prim_elem;
2320 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2321 prim_elem, im_prim_elem, source, dest);
2324 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2325 im_prim_elem, source, dest);
2326 for (
int k= 0;
k <
i;
k++)
2329 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2330 im_prim_elem, source, dest);
2331 gcds[
k]=
mapUp (gcds[
k], V_buf4, V_buf, prim_elem, im_prim_elem,
2337 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2338 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2350 bool initialized=
false;
2373 delete[] pEvalPoints;
2382 if (
k.exp() !=
l.exp())
2384 delete[] pEvalPoints;
2401 if (Monoms.
size() == 0)
2404 coeffMonoms=
new CFArray [skelSize];
2411 for (
int i= 0;
i < biggestSize;
i++)
2415 for (
int k= 0;
k < skelSize;
k++,
l++)
2419 pL[
k] [
i]=
l.coeff();
2431 for (
int k= 0;
k < skelSize;
k++)
2433 if (biggestSize != coeffMonoms[
k].
size())
2436 for (
int i= 0;
i < coeffMonoms[
k].
size();
i++)
2437 bufArray [
i]= pL[
k] [
i];
2443 if (solution.
size() == 0)
2445 delete[] pEvalPoints;
2448 delete[] coeffMonoms;
2454 for (
int l= 0;
l < solution.
size();
l++)
2455 result += solution[
l]*Monoms [ind +
l];
2456 ind += solution.
size();
2459 delete[] pEvalPoints;
2462 delete[] coeffMonoms;
2495 if (F ==
G)
return F/
Lc(F);
2503 if (best_level == 0)
2522 gcdcAcB=
gcd (cA, cB);
2542 gcdlcAlcB=
gcd (lcA, lcB);
2543 int skelSize=
size (skel, skel.
mvar());
2551 bufSize=
size (
i.coeff());
2552 biggestSize=
tmax (biggestSize, bufSize);
2553 numberUni += bufSize;
2556 numberUni= (int) ceil ( (
double) numberUni / (skelSize - 1));
2557 biggestSize=
tmax (biggestSize , numberUni);
2559 numberUni= biggestSize +
size (
LC(skel)) - 1;
2560 int biggestSize2=
tmax (numberUni, biggestSize);
2566 bool evalFail=
false;
2577 for (
int i= 0;
i < biggestSize;
i++)
2589 if (V_buf.
level() != 1)
2598 bool prim_fail=
false;
2602 prim_elem_alpha= prim_elem;
2604 ASSERT (!prim_fail,
"failure in integer factorizer");
2608 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2614 im_prim_elem_alpha= im_prim_elem;
2616 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2617 prim_elem, im_prim_elem, source, dest);
2620 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
2621 im_prim_elem, source, dest);
2624 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2625 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2637 bool initialized=
false;
2666 delete[] pEvalPoints;
2675 if (
k.exp() !=
l.exp())
2677 delete[] pEvalPoints;
2694 if (Monoms.
size() == 0)
2697 coeffMonoms=
new CFArray [skelSize];
2703 int minimalColumnsIndex;
2705 minimalColumnsIndex= 1;
2707 minimalColumnsIndex= 0;
2708 int minimalColumns=-1;
2713 for (
int i= 0;
i < skelSize;
i++)
2717 minimalColumns= coeffMonoms[
i].
size();
2720 if (minimalColumns > coeffMonoms[
i].
size())
2722 minimalColumns= coeffMonoms[
i].
size();
2723 minimalColumnsIndex=
i;
2728 pMat[0]=
CFMatrix (biggestSize, coeffMonoms[0].
size());
2729 pMat[1]=
CFMatrix (biggestSize, coeffMonoms[minimalColumnsIndex].
size());
2731 for (
int i= 0;
i < biggestSize;
i++)
2735 for (
int k= 0;
k < skelSize;
k++,
l++)
2739 pL[
k] [
i]=
l.coeff();
2741 if (
i == 0 &&
k != 0 &&
k != minimalColumnsIndex)
2743 else if (
i == 0 && (
k == 0 ||
k == minimalColumnsIndex))
2745 if (
i > 0 && (
k == 0 ||
k == minimalColumnsIndex))
2750 if (pMat[
k].rows() >=
i + 1)
2752 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2753 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2756 if (
k == minimalColumnsIndex)
2758 if (pMat[1].rows() >=
i + 1)
2760 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2761 pMat[1] (
i + 1, ind)= coeffEval[ind - 1];
2770 int matRows, matColumns;
2771 matRows= pMat[1].
rows();
2772 matColumns= pMat[0].
columns() - 1;
2773 matColumns += pMat[1].
columns();
2775 Mat=
CFMatrix (matRows, matColumns);
2776 for (
int i= 1;
i <= matRows;
i++)
2778 Mat (
i,
j)= pMat[1] (
i,
j);
2780 for (
int j= pMat[1].columns() + 1;
j <= matColumns;
2783 for (
int i= 1;
i <= matRows;
i++)
2784 Mat (
i,
j)= (-pMat [0] (
i, ind + 1))*pL[minimalColumnsIndex] [
i - 1];
2788 for (
int i= 0;
i < pMat[0].
rows();
i++)
2789 firstColumn [
i]= pMat[0] (
i + 1, 1);
2791 CFArray bufArray= pL[minimalColumnsIndex];
2793 for (
int i= 0;
i < biggestSize;
i++)
2794 pL[minimalColumnsIndex] [
i] *= firstColumn[
i];
2799 if (V_buf.
level() != 1)
2801 pL[minimalColumnsIndex], V_buf);
2804 pL[minimalColumnsIndex]);
2806 if (solution.
size() == 0)
2811 pL[minimalColumnsIndex]= bufArray;
2814 if (biggestSize != biggestSize2)
2816 bufpEvalPoints= pEvalPoints;
2817 pEvalPoints=
new CFList [biggestSize2];
2820 for (
int i= 0;
i < biggestSize;
i++)
2822 pEvalPoints[
i]= bufpEvalPoints [
i];
2823 gcds[
i]= bufGcds[
i];
2825 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2833 delete[] pEvalPoints;
2836 delete[] coeffMonoms;
2838 if (bufpEvalPoints !=
NULL)
2839 delete [] bufpEvalPoints;
2848 if (
k.exp() !=
l.exp())
2850 delete[] pEvalPoints;
2853 delete[] coeffMonoms;
2855 if (bufpEvalPoints !=
NULL)
2856 delete [] bufpEvalPoints;
2864 gcds[
i + biggestSize]=
g;
2867 for (
int i= 0;
i < biggestSize;
i++)
2871 for (
int k= 1;
k < skelSize;
k++,
l++)
2874 pMat[
k]=
CFMatrix (biggestSize2,coeffMonoms[
k].
size()+biggestSize2-1);
2875 if (
k == minimalColumnsIndex)
2878 if (pMat[
k].rows() >=
i + 1)
2880 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2881 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2886 pMat[0]=
CFMatrix (biggestSize2, coeffMonoms[0].
size() + biggestSize2 - 1);
2887 for (
int j= 1;
j <= Mat.
rows();
j++)
2889 pMat [0] (
j,
k)= Mat (
j,
k);
2891 for (
int j= 1;
j <= Mat.
rows();
j++)
2893 pMat [minimalColumnsIndex] (
j,
k)= Mat (
j,
k);
2895 for (
int i= 0;
i < skelSize;
i++)
2899 for (
int j= 0;
j < bufArray.
size();
j++)
2900 pL[
i] [
j]= bufArray [
j];
2903 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2907 for (
int k= 0;
k < skelSize;
k++,
l++)
2909 pL[
k] [
i + biggestSize]=
l.coeff();
2911 if (pMat[
k].rows() >=
i + biggestSize + 1)
2913 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2914 pMat[
k] (
i + biggestSize + 1, ind)= coeffEval[ind - 1];
2919 for (
int i= 0;
i < skelSize;
i++)
2921 if (pL[
i].
size() > 1)
2923 for (
int j= 2;
j <= pMat[
i].
rows();
j++)
2924 pMat[
i] (
j, coeffMonoms[
i].
size() +
j - 1)=
2929 matColumns= biggestSize2 - 1;
2931 for (
int i= 0;
i < skelSize;
i++)
2933 if (V_buf.
level() == 1)
2938 if (pMat[
i] (coeffMonoms[
i].
size(), coeffMonoms[
i].
size()) == 0)
2940 delete[] pEvalPoints;
2943 delete[] coeffMonoms;
2945 if (bufpEvalPoints !=
NULL)
2946 delete [] bufpEvalPoints;
2952 matRows += pMat[
i].
rows() - coeffMonoms[
i].
size();
2956 Mat=
CFMatrix (matRows, matColumns);
2960 for (
int i= 0;
i < skelSize;
i++)
2962 if (coeffMonoms[
i].
size() + 1 >= pMat[
i].rows() || coeffMonoms[
i].
size() + 1 >= pMat[
i].columns())
2964 delete[] pEvalPoints;
2967 delete[] coeffMonoms;
2969 if (bufpEvalPoints !=
NULL)
2970 delete [] bufpEvalPoints;
2976 bufMat= pMat[
i] (coeffMonoms[
i].
size() + 1, pMat[
i].
rows(),
2979 for (
int j= 1;
j <= bufMat.
rows();
j++)
2981 Mat (
j + ind,
k)= bufMat(
j,
k);
2982 bufArray2= coeffMonoms[
i].
size();
2983 for (
int j= 1;
j <= pMat[
i].
rows();
j++)
2985 if (
j > coeffMonoms[
i].
size())
2986 bufArray [
j-coeffMonoms[
i].
size() + ind - 1]= pL[
i] [
j - 1];
2988 bufArray2 [
j - 1]= pL[
i] [
j - 1];
2991 ind += bufMat.
rows();
2995 if (V_buf.
level() != 1)
3000 if (solution.
size() == 0)
3002 delete[] pEvalPoints;
3005 delete[] coeffMonoms;
3007 if (bufpEvalPoints !=
NULL)
3008 delete [] bufpEvalPoints;
3018 for (
int i= 0;
i < skelSize;
i++)
3021 for (
int i= 0;
i < bufSolution.
size();
i++, ind++)
3022 result += Monoms [ind]*bufSolution[
i];
3031 delete[] pEvalPoints;
3034 delete[] coeffMonoms;
3037 if (bufpEvalPoints !=
NULL)
3038 delete [] bufpEvalPoints;
3049 int ind2= 0, ind3= 2;
3051 for (
int l= 0;
l < minimalColumnsIndex;
l++)
3052 ind += coeffMonoms[
l].
size();
3054 l++,
ind2++, ind3++)
3057 for (
int i= 0;
i < pMat[0].
rows();
i++)
3058 firstColumn[
i] += solution[
l]*pMat[0] (
i + 1, ind3);
3060 for (
int l= 0;
l < solution.
size() + 1 - pMat[0].columns();
l++)
3061 result += solution[
l]*Monoms [ind +
l];
3062 ind= coeffMonoms[0].
size();
3063 for (
int k= 1;
k < skelSize;
k++)
3065 if (
k == minimalColumnsIndex)
3067 ind += coeffMonoms[
k].
size();
3070 if (
k != minimalColumnsIndex)
3072 for (
int i= 0;
i < biggestSize;
i++)
3073 pL[
k] [
i] *= firstColumn [
i];
3076 if (biggestSize != coeffMonoms[
k].
size() &&
k != minimalColumnsIndex)
3079 for (
int i= 0;
i < bufArray.
size();
i++)
3080 bufArray [
i]= pL[
k] [
i];
3086 if (solution.
size() == 0)
3088 delete[] pEvalPoints;
3091 delete[] coeffMonoms;
3098 if (
k != minimalColumnsIndex)
3100 for (
int l= 0;
l < solution.
size();
l++)
3101 result += solution[
l]*Monoms [ind +
l];
3102 ind += solution.
size();
3106 delete[] pEvalPoints;
3110 delete[] coeffMonoms;
3140 if (F ==
G)
return F/
Lc(F);
3145 if (best_level == 0)
return B.
genOne();
3162 gcdcAcB=
gcd (cA, cB);
3182 gcdlcAlcB=
gcd (lcA, lcB);
3197 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3204 bool inextension=
false;
3212 if (random_element == 0 && !fail)
3214 if (!
find (
l, random_element))
3215 l.append (random_element);
3225 bool prim_fail=
false;
3228 if (V_buf4 ==
alpha)
3229 prim_elem_alpha= prim_elem;
3231 if (V_buf3 != V_buf4)
3233 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3234 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3235 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3237 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3238 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3239 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4, source,
3242 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3246 ASSERT (!prim_fail,
"failure in integer factorizer");
3250 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3252 if (V_buf4 ==
alpha)
3253 im_prim_elem_alpha= im_prim_elem;
3255 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
3256 im_prim_elem, source, dest);
3262 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3263 im_prim_elem, source, dest);
3264 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3265 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3266 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3268 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3269 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3270 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3279 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3282 "time for recursive call: ");
3283 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3291 sparseGCDFq (ppA(random_element,
x), ppB(random_element,
x), V_buf,
3294 "time for recursive call: ");
3295 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3312 if (!
find (
l, random_element))
3313 l.append (random_element);
3318 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3321 skeleton= G_random_element;
3336 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3348 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3349 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3351 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3353 return N(gcdcAcB*ppH);
3357 return N(gcdcAcB*ppH);
3360 newtonPoly= newtonPoly*(
x - random_element);
3361 m=
m*(
x - random_element);
3362 if (!
find (
l, random_element))
3363 l.append (random_element);
3372 if (random_element == 0 && !fail)
3374 if (!
find (
l, random_element))
3375 l.append (random_element);
3385 bool prim_fail=
false;
3388 if (V_buf4 ==
alpha)
3389 prim_elem_alpha= prim_elem;
3391 if (V_buf3 != V_buf4)
3393 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3394 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3395 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3397 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3398 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3399 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
3402 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3406 ASSERT (!prim_fail,
"failure in integer factorizer");
3410 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3412 if (V_buf4 ==
alpha)
3413 im_prim_elem_alpha= im_prim_elem;
3415 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
3416 prim_elem, im_prim_elem, source, dest);
3422 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3423 im_prim_elem, source, dest);
3424 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3425 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3426 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3428 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3429 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3431 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3443 bool sparseFail=
false;
3444 if (
LC (skeleton).inCoeffDomain())
3447 skeleton,V_buf, sparseFail, coeffMonoms,Monoms);
3451 skeleton, V_buf, sparseFail, coeffMonoms,
3457 "time for recursive call: ");
3458 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3464 bool sparseFail=
false;
3465 if (
LC (skeleton).inCoeffDomain())
3468 skeleton,V_buf, sparseFail,coeffMonoms, Monoms);
3472 skeleton, V_buf, sparseFail, coeffMonoms,
3478 "time for recursive call: ");
3479 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3496 if (!
find (
l, random_element))
3497 l.append (random_element);
3502 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3520 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3522 "time for newton interpolation: ");
3536 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3537 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3539 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3541 return N(gcdcAcB*ppH);
3546 return N(gcdcAcB*ppH);
3551 newtonPoly= newtonPoly*(
x - random_element);
3552 m=
m*(
x - random_element);
3553 if (!
find (
l, random_element))
3554 l.append (random_element);
3572 if (F ==
G)
return F/
Lc(F);
3577 if (best_level == 0)
return B.
genOne();
3594 gcdcAcB=
gcd (cA, cB);
3614 gcdlcAlcB=
gcd (lcA, lcB);
3630 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3637 bool inextension=
false;
3647 if (random_element == 0 && !fail)
3649 if (!
find (
l, random_element))
3650 l.append (random_element);
3654 if (!fail && !inextension)
3662 "time for recursive call: ");
3663 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3665 else if (!fail && inextension)
3673 "time for recursive call: ");
3674 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3676 else if (fail && !inextension)
3683 bool initialized=
false;
3705 "time for recursive call: ");
3706 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3708 else if (fail && inextension)
3715 bool prim_fail=
false;
3720 if (V_buf3 !=
alpha)
3723 G_m=
mapDown (
m, prim_elem, im_prim_elem,
alpha, source, dest);
3724 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha, source,
3726 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
3727 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
3728 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
3731 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3735 ASSERT (!prim_fail,
"failure in integer factorizer");
3745 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3746 im_prim_elem, source, dest);
3747 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3748 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3749 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
3751 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3752 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3753 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
3761 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3764 "time for recursive call: ");
3765 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3783 if (!
find (
l, random_element))
3784 l.append (random_element);
3789 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3792 skeleton= G_random_element;
3808 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3821 return N(gcdcAcB*ppH);
3825 newtonPoly= newtonPoly*(
x - random_element);
3826 m=
m*(
x - random_element);
3827 if (!
find (
l, random_element))
3828 l.append (random_element);
3841 if (random_element == 0 && !fail)
3843 if (!
find (
l, random_element))
3844 l.append (random_element);
3848 bool sparseFail=
false;
3849 if (!fail && !inextension)
3853 if (
LC (skeleton).inCoeffDomain())
3856 skeleton,
x, sparseFail, coeffMonoms,
3861 skeleton,
x, sparseFail,
3862 coeffMonoms, Monoms);
3864 "time for recursive call: ");
3865 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3867 else if (!fail && inextension)
3871 if (
LC (skeleton).inCoeffDomain())
3874 skeleton,
alpha, sparseFail, coeffMonoms,
3879 skeleton,
alpha, sparseFail, coeffMonoms,
3882 "time for recursive call: ");
3883 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3885 else if (fail && !inextension)
3892 bool initialized=
false;
3910 if (
LC (skeleton).inCoeffDomain())
3913 skeleton,
alpha, sparseFail, coeffMonoms,
3918 skeleton,
alpha, sparseFail, coeffMonoms,
3921 "time for recursive call: ");
3922 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3924 else if (fail && inextension)
3931 bool prim_fail=
false;
3936 if (V_buf3 !=
alpha)
3939 G_m=
mapDown (
m, prim_elem, im_prim_elem,
alpha, source, dest);
3940 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
3942 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
3943 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
3944 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha,
3947 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3951 ASSERT (!prim_fail,
"failure in integer factorizer");
3961 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3962 im_prim_elem, source, dest);
3963 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3964 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3965 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
3967 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3968 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3969 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
3976 if (
LC (skeleton).inCoeffDomain())
3979 skeleton, V_buf, sparseFail, coeffMonoms,
3984 skeleton, V_buf, sparseFail,
3985 coeffMonoms, Monoms);
3987 "time for recursive call: ");
3988 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
4009 if (!
find (
l, random_element))
4010 l.append (random_element);
4015 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
4033 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
4035 "time for newton interpolation: ");
4048 return N(gcdcAcB*ppH);
4053 newtonPoly= newtonPoly*(
x - random_element);
4054 m=
m*(
x - random_element);
4055 if (!
find (
l, random_element))
4056 l.append (random_element);
4145#if defined(HAVE_NTL) || defined(HAVE_FLINT)
4160 "time for gcd mod p in modular gcd: ");
4239 "time for successful termination in modular gcd: ");
4244 "time for unsuccessful termination in modular gcd: ");
CFMatrix * convertNmod_mat_t2FacCFMatrix(const nmod_mat_t m)
conversion of a FLINT matrix over Z/p to a factory matrix
void convertFacCFMatrix2nmod_mat_t(nmod_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z/p to a nmod_mat_t
void convertFacCFMatrix2Fq_nmod_mat_t(fq_nmod_mat_t M, const fq_nmod_ctx_t fq_con, const CFMatrix &m)
conversion of a factory matrix over F_q to a fq_nmod_mat_t
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CFMatrix * convertFq_nmod_mat_t2FacCFMatrix(const fq_nmod_mat_t m, const fq_nmod_ctx_t &fq_con, const Variable &alpha)
conversion of a FLINT matrix over F_q to a factory matrix
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
Rational pow(const Rational &a, int e)
Rational abs(const Rational &a)
CFMatrix * convertNTLmat_zz_p2FacCFMatrix(const mat_zz_p &m)
CFMatrix * convertNTLmat_zz_pE2FacCFMatrix(const mat_zz_pE &m, const Variable &alpha)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
mat_zz_pE * convertFacCFMatrix2NTLmat_zz_pE(const CFMatrix &m)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
mat_zz_p * convertFacCFMatrix2NTLmat_zz_p(const CFMatrix &m)
Conversion to and from NTL.
const CanonicalForm CFMap CFMap & N
const CanonicalForm CFMap CFMap int & both_non_zero
const CanonicalForm CFMap CFMap bool topLevel
coprimality check and change of representation mod n
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
CFArray readOffSolution(const CFMatrix &M, const long rk)
M in row echolon form, rk rank of M.
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....
static CanonicalForm GFRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
compute a random element a of GF, s.t. F(a) , F is a univariate polynomial, returns fail if there ar...
CFArray evaluateMonom(const CanonicalForm &F, const CFList &evalPoints)
const CanonicalForm const CanonicalForm const CanonicalForm & coG
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
void mult(CFList &L1, const CFList &L2)
multiply two lists componentwise
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
long gaussianElimFq(CFMatrix &M, CFArray &L, const Variable &alpha)
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 Variable chooseExtension(const Variable &alpha)
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
CanonicalForm monicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
long gaussianElimFp(CFMatrix &M, CFArray &L)
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
CFArray solveGeneralVandermonde(const CFArray &M, const CFArray &A)
CanonicalForm extractContents(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &contentF, CanonicalForm &contentG, CanonicalForm &ppF, CanonicalForm &ppG, const int d)
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.
CFArray solveVandermonde(const CFArray &M, const CFArray &A)
const CanonicalForm const CanonicalForm & coF
CanonicalForm cd(bCommonDen(FF))
CanonicalForm nonMonicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CFArray solveSystemFp(const CFMatrix &M, const CFArray &L)
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
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...
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
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...
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...
CFArray solveSystemFq(const CFMatrix &M, const CFArray &L, const Variable &alpha)
CFList evaluationPoints(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Feval, CanonicalForm &Geval, const CanonicalForm &LCF, const bool &GF, const Variable &alpha, bool &fail, CFList &list)
modular and sparse modular GCD algorithms over finite fields and Z.
bool terminationTest(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &coF, const CanonicalForm &coG, const CanonicalForm &cand)
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
This file provides functions to compute the Newton polygon of a bivariate polynomial.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
void FACTORY_PUBLIC 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,...
#define ASSERT(expression, message)
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
static CanonicalForm balance_p(const CanonicalForm &f, const CanonicalForm &q, const CanonicalForm &qh)
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
generate random irreducible univariate polynomials
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
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)
CanonicalForm generate() const
class to iterate through CanonicalForm's
generate random elements in F_p
CanonicalForm generate() const
generate random elements in GF
CanonicalForm generate() const
factory's class for variables
functions to print debug output
#define DEBOUTLN(stream, objects)
const Variable & v
< [in] a sqrfree bivariate poly
CFList *& Aeval
<[in] poly
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
This file defines functions for Hensel lifting.
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)
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
static long ind2(long arg)
gmp_float log(const gmp_float &a)
int status int void * buf
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)