87#if defined(HAVE_NTL)|| defined(HAVE_FLINT)
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));
437 nmod_poly_t Irredpoly;
439 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom,
i*
m+1);
449 BuildIrred (NTLIrredpoly,
i*
m);
455#if defined(HAVE_NTL) || defined(HAVE_FLINT)
462#if defined(HAVE_NTL) || defined(HAVE_FLINT)
478#if defined(HAVE_NTL) || defined(HAVE_FLINT)
555 gcdcAcB=
gcd (cA, cB);
565 gcdlcAlcB=
gcd (lcA, lcB);
571 coF=
N (ppA*(cA/gcdcAcB));
572 coG=
N (ppB*(cB/gcdcAcB));
581 coF=
N (ppA*(cA/gcdcAcB));
582 coG=
N (ppB*(cB/gcdcAcB));
587 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
598 bool inextension=
false;
603 int bound1=
degree (ppA, 1);
604 int bound2=
degree (ppB, 1);
615 bool prim_fail=
false;
619 prim_elem_alpha= prim_elem;
621 if (V_buf3 != V_buf4)
623 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
624 G_m=
mapDown (G_m, prim_elem, im_prim_elem, V_buf4, source, dest);
625 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem, V_buf4, source, dest);
626 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem, V_buf4, source, dest);
627 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
629 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
630 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
631 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
633 lcA=
mapDown (lcA, prim_elem, im_prim_elem, V_buf4, source, dest);
634 lcB=
mapDown (lcB, prim_elem, im_prim_elem, V_buf4, source, dest);
636 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
640 ASSERT (!prim_fail,
"failure in integer factorizer");
644 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
647 im_prim_elem_alpha= im_prim_elem;
649 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
650 im_prim_elem, source, dest);
655 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
656 im_prim_elem, source, dest);
657 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
658 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
659 coF_m=
mapUp (coF_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
660 coG_m=
mapUp (coG_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
661 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
663 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
664 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
665 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
667 lcA=
mapUp (lcA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
668 lcB=
mapUp (lcB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
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);
689 modGCDFq (ppA(random_element,
x), ppB(random_element,
x),
690 coF_random_element, coG_random_element, V_buf,
693 "time for recursive call: ");
694 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
708 ppA=
mapDown (ppA, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
709 ppB=
mapDown (ppB, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
712 coF=
N (ppA*(cA/gcdcAcB));
713 coG=
N (ppB*(cB/gcdcAcB));
718 if (!
find (
l, random_element))
719 l.append (random_element);
724 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
726 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
728 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
748 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
749 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
750 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
752 "time for newton interpolation: ");
758 if (gcdlcAlcB.
isOne())
777 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
778 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
779 ppCoF=
mapDown (ppCoF, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
780 ppCoG=
mapDown (ppCoG, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
781 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
782 coF=
N ((cA/gcdcAcB)*ppCoF);
783 coG=
N ((cB/gcdcAcB)*ppCoG);
785 "time for successful termination test Fq: ");
787 return N(gcdcAcB*ppH);
790 else if (((
degree (ppCoF,1)+
degree (ppH,1) == bound1) &&
795 coF=
N ((cA/gcdcAcB)*ppCoF);
796 coG=
N ((cB/gcdcAcB)*ppCoG);
798 "time for successful termination test Fq: ");
799 return N(gcdcAcB*ppH);
802 "time for unsuccessful termination test Fq: ");
808 newtonPoly= newtonPoly*(
x - random_element);
809 m=
m*(
x - random_element);
810 if (!
find (
l, random_element))
811 l.append (random_element);
842 while (
find (list, random))
845 if (F (random,
x) == 0)
850 }
while (
find (list, random));
949 gcdcAcB=
gcd (cA, cB);
959 gcdlcAlcB=
gcd (lcA, lcB);
964 coF=
N (ppA*(cA/gcdcAcB));
965 coG=
N (ppB*(cB/gcdcAcB));
973 coF=
N (ppA*(cA/gcdcAcB));
974 coG=
N (ppB*(cB/gcdcAcB));
979 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
990 bool inextension=
false;
996 int bound1=
degree (ppA, 1);
997 int bound2=
degree (ppB, 1);
1006 if (
ipower (
p, kk*expon) < (1 << 16))
1010 expon= (int)
floor((
log ((
double)((1<<16) - 1)))/(
log((
double)
p)*kk));
1011 ASSERT (expon >= 2,
"not enough points in modGCDGF");
1020 newtonPoly=
GFMapUp (newtonPoly, kk);
1025 gcdlcAlcB=
GFMapUp (gcdlcAlcB, kk);
1032 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1033 coF_random_element, coG_random_element,
1036 "time for recursive call: ");
1037 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1043 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1044 coF_random_element, coG_random_element,
1047 "time for recursive call: ");
1048 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1065 coF=
N (ppA*(cA/gcdcAcB));
1066 coG=
N (ppB*(cB/gcdcAcB));
1071 if (!
find (
l, random_element))
1072 l.append (random_element);
1077 (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element)) *
1080 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1081 *coF_random_element;
1082 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1083 *coG_random_element;
1102 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1103 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1104 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1106 "time for newton interpolation: ");
1112 if (gcdlcAlcB.
isOne())
1130 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
1134 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
1135 coF=
N ((cA/gcdcAcB)*ppCoF);
1136 coG=
N ((cB/gcdcAcB)*ppCoG);
1139 "time for successful termination GF: ");
1140 return N(gcdcAcB*ppH);
1150 coF=
N ((cA/gcdcAcB)*ppCoF);
1151 coG=
N ((cB/gcdcAcB)*ppCoG);
1153 "time for successful termination GF: ");
1154 return N(gcdcAcB*ppH);
1158 "time for unsuccessful termination GF: ");
1164 newtonPoly= newtonPoly*(
x - random_element);
1165 m=
m*(
x - random_element);
1166 if (!
find (
l, random_element))
1167 l.append (random_element);
1193 while (
find (list, random))
1196 if (F (random,
x) == 0)
1201 }
while (
find (list, random));
1205#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1212#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1223#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1272 if (best_level == 0)
1299 gcdcAcB=
gcd (cA, cB);
1308 gcdlcAlcB=
gcd (lcA, lcB);
1315 coF=
N (ppA*(cA/gcdcAcB));
1316 coG=
N (ppB*(cB/gcdcAcB));
1327 coF=
N (ppA*(cA/gcdcAcB));
1328 coG=
N (ppB*(cB/gcdcAcB));
1333 CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1334 coF_m, coG_m, ppCoF, ppCoG;
1344 bool inextension=
false;
1347 int bound1=
degree (ppA, 1);
1348 int bound2=
degree (ppB, 1);
1356 if (!fail && !inextension)
1361 modGCDFp (ppA (random_element,
x), ppB (random_element,
x),
1362 coF_random_element, coG_random_element,
topLevel,
1365 "time for recursive call: ");
1366 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1368 else if (!fail && inextension)
1373 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1374 coF_random_element, coG_random_element, V_buf,
1377 "time for recursive call: ");
1378 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1380 else if (fail && !inextension)
1387 bool initialized=
false;
1406 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1407 coF_random_element, coG_random_element,
alpha,
1410 "time for recursive call: ");
1411 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1413 else if (fail && inextension)
1420 bool prim_fail=
false;
1425 if (V_buf3 !=
alpha)
1428 G_m=
mapDown (G_m, prim_elem, im_prim_elem,
alpha, source, dest);
1429 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem,
alpha, source, dest);
1430 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem,
alpha, source, dest);
1431 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
1433 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
1434 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
1435 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
1437 lcA=
mapDown (lcA, prim_elem, im_prim_elem,
alpha, source, dest);
1438 lcB=
mapDown (lcB, prim_elem, im_prim_elem,
alpha, source, dest);
1440 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
1444 ASSERT (!prim_fail,
"failure in integer factorizer");
1454 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
1455 im_prim_elem, source, dest);
1456 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1457 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1458 coF_m=
mapUp (coF_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1459 coG_m=
mapUp (coG_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1460 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
1462 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1463 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1464 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
1466 lcA=
mapUp (lcA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1467 lcB=
mapUp (lcB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1474 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1475 coF_random_element, coG_random_element, V_buf,
1478 "time for recursive call: ");
1479 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1493 coF=
N (ppA*(cA/gcdcAcB));
1494 coG=
N (ppB*(cB/gcdcAcB));
1500 if (!
find (
l, random_element))
1501 l.append (random_element);
1505 G_random_element= (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element))
1508 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1509 *coF_random_element;
1510 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1511 *coG_random_element;
1530 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1531 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1532 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1534 "time for newton_interpolation: ");
1540 if (gcdlcAlcB.
isOne())
1559 coF=
N ((cA/gcdcAcB)*ppCoF);
1560 coG=
N ((cB/gcdcAcB)*ppCoG);
1562 "time for successful termination Fp: ");
1563 return N(gcdcAcB*ppH);
1566 "time for unsuccessful termination Fp: ");
1572 newtonPoly= newtonPoly*(
x - random_element);
1573 m=
m*(
x - random_element);
1574 if (!
find (
l, random_element))
1575 l.append (random_element);
1584 ASSERT (
A.size() == r,
"vector does not have right size");
1593 bool notDistinct=
false;
1594 for (
int i= 0;
i < r - 1;
i++)
1596 for (
int j=
i + 1;
j < r;
j++)
1610 for (
int i= 0;
i < r;
i++)
1611 master *=
x -
M [
i];
1614 for (
int i= 0;
i < r;
i++)
1616 tmp= master/(
x -
M [
i]);
1617 tmp /= tmp (
M [
i], 1);
1623 for (
int i= 1;
i <= r;
i++,
j++)
1626 for (
int l= 0;
l <
A.size();
l++)
1627 tmp +=
A[
l]*
j.getItem()[
l];
1637 ASSERT (
A.size() == r,
"vector does not have right size");
1645 bool notDistinct=
false;
1646 for (
int i= 0;
i < r - 1;
i++)
1648 for (
int j=
i + 1;
j < r;
j++)
1662 for (
int i= 0;
i < r;
i++)
1663 master *=
x -
M [
i];
1667 for (
int i= 0;
i < r;
i++)
1669 tmp= master/(
x -
M [
i]);
1670 tmp /= tmp (
M [
i], 1);
1677 for (
int i= 1;
i <= r;
i++,
j++)
1681 for (
int l= 1;
l <=
A.size();
l++)
1682 tmp +=
A[
l - 1]*
j.getItem()[
l];
1694 for (
int i= rk;
i >= 1;
i--)
1698 for (
int j=
M.columns() - 1;
j >= 1;
j--)
1717 for (
int i=
M.rows();
i >= 1;
i--)
1722 for (
int j=
M.columns();
j >= 1;
j--,
k++)
1729 if (
k > partialSol.
size() - 1)
1732 tmp3 +=
tmp2*partialSol[partialSol.
size() -
k - 1];
1743 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1747 for (
int i= 1;
i <=
M.rows();
i++)
1748 for (
int j= 1;
j <=
M.columns();
j++)
1752 for (
int i= 0;
i < L.
size();
i++,
j++)
1753 (*
N) (
j,
M.columns() + 1)= L[
i];
1757 long rk= nmod_mat_rref (FLINTN);
1761 nmod_mat_clear (FLINTN);
1771 long rk= gauss (*NTLN);
1778 for (
int i= 0;
i <
M.rows();
i++)
1779 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1780 M= (*N) (1,
M.rows(), 1,
M.columns());
1788 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1792 for (
int i= 1;
i <=
M.rows();
i++)
1793 for (
int j= 1;
j <=
M.columns();
j++)
1797 for (
int i= 0;
i < L.
size();
i++,
j++)
1798 (*
N) (
j,
M.columns() + 1)= L[
i];
1807 fq_nmod_mat_t FLINTN;
1810 long rk= fq_nmod_mat_rref (FLINTN,ctx);
1812 fq_nmod_mat_clear (FLINTN,ctx);
1814 #elif defined(HAVE_NTL)
1824 long rk= gauss (*NTLN);
1832 M= (*N) (1,
M.rows(), 1,
M.columns());
1834 for (
int i= 0;
i <
M.rows();
i++)
1835 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1844 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1848 for (
int i= 1;
i <=
M.rows();
i++)
1849 for (
int j= 1;
j <=
M.columns();
j++)
1853 for (
int i= 0;
i < L.
size();
i++,
j++)
1854 (*
N) (
j,
M.columns() + 1)= L[
i];
1859 long rk= nmod_mat_rref (FLINTN);
1868 long rk= gauss (*NTLN);
1871 if (rk !=
M.columns())
1874 nmod_mat_clear (FLINTN);
1882 nmod_mat_clear (FLINTN);
1896 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1900 for (
int i= 1;
i <=
M.rows();
i++)
1901 for (
int j= 1;
j <=
M.columns();
j++)
1904 for (
int i= 0;
i < L.
size();
i++,
j++)
1905 (*
N) (
j,
M.columns() + 1)= L[
i];
1914 fq_nmod_mat_t FLINTN;
1917 long rk= fq_nmod_mat_rref (FLINTN,ctx);
1918 #elif defined(HAVE_NTL)
1928 long rk= gauss (*NTLN);
1934 if (rk !=
M.columns())
1936 #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
1944 fq_nmod_mat_clear (FLINTN,ctx);
1946 #elif defined(HAVE_NTL)
1975 int numMon=
size (F);
1985 for (
int k= 0;
k < recResult.
size();
k++)
1987 j += recResult.
size();
1992#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2005 "expected an eval point with only one component");
2013 int numMon=
size (F);
2025 for (
int k= 0;
k < recResult.
size();
k++)
2027 j += recResult.
size();
2038 for (
int i= 0;
i <
A.size();
i++)
2043 tmp= tmp (
j.getItem(),
k);
2078 bool zeroOneOccured=
false;
2079 bool allEqual=
false;
2090 for (
int i= 0;
i <
k;
i++)
2108 if (
result.getLast().isOne() ||
result.getLast().isZero())
2109 zeroOneOccured=
true;
2111 if (
find (list, random))
2113 zeroOneOccured=
false;
2121 zeroOneOccured=
false;
2141 zeroOneOccured=
false;
2153 Geval= Geval (
i.getItem(),
j);
2154 LCeval= LCeval (
i.getItem(),
j);
2159 if (!
find (list, random))
2161 zeroOneOccured=
false;
2172 }
while (
find (list, random));
2184 i.getItem() *=
j.getItem();
2196 Beval= Beval (
i.getItem(),
j);
2214 if (F ==
G)
return F/
Lc(F);
2222 if (best_level == 0)
2240 gcdcAcB=
gcd (cA, cB);
2260 gcdlcAlcB=
gcd (lcA, lcB);
2261 int skelSize=
size (skel, skel.
mvar());
2267 biggestSize=
tmax (biggestSize,
size (
i.coeff()));
2272 bool evalFail=
false;
2283 for (
int i= 0;
i < biggestSize;
i++)
2296 if (V_buf.
level() != 1)
2305 bool prim_fail=
false;
2309 prim_elem_alpha= prim_elem;
2311 ASSERT (!prim_fail,
"failure in integer factorizer");
2315 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2321 im_prim_elem_alpha= im_prim_elem;
2323 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2324 prim_elem, im_prim_elem, source, dest);
2327 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2328 im_prim_elem, source, dest);
2329 for (
int k= 0;
k <
i;
k++)
2332 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2333 im_prim_elem, source, dest);
2334 gcds[
k]=
mapUp (gcds[
k], V_buf4, V_buf, prim_elem, im_prim_elem,
2340 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2341 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2353 bool initialized=
false;
2376 delete[] pEvalPoints;
2385 if (
k.exp() !=
l.exp())
2387 delete[] pEvalPoints;
2404 if (Monoms.
size() == 0)
2407 coeffMonoms=
new CFArray [skelSize];
2414 for (
int i= 0;
i < biggestSize;
i++)
2418 for (
int k= 0;
k < skelSize;
k++,
l++)
2422 pL[
k] [
i]=
l.coeff();
2434 for (
int k= 0;
k < skelSize;
k++)
2436 if (biggestSize != coeffMonoms[
k].
size())
2439 for (
int i= 0;
i < coeffMonoms[
k].
size();
i++)
2440 bufArray [
i]= pL[
k] [
i];
2446 if (solution.
size() == 0)
2448 delete[] pEvalPoints;
2451 delete[] coeffMonoms;
2457 for (
int l= 0;
l < solution.
size();
l++)
2458 result += solution[
l]*Monoms [ind +
l];
2459 ind += solution.
size();
2462 delete[] pEvalPoints;
2465 delete[] coeffMonoms;
2498 if (F ==
G)
return F/
Lc(F);
2506 if (best_level == 0)
2525 gcdcAcB=
gcd (cA, cB);
2545 gcdlcAlcB=
gcd (lcA, lcB);
2546 int skelSize=
size (skel, skel.
mvar());
2554 bufSize=
size (
i.coeff());
2555 biggestSize=
tmax (biggestSize, bufSize);
2556 numberUni += bufSize;
2559 numberUni= (int)
ceil ( (
double) numberUni / (skelSize - 1));
2560 biggestSize=
tmax (biggestSize , numberUni);
2562 numberUni= biggestSize +
size (
LC(skel)) - 1;
2563 int biggestSize2=
tmax (numberUni, biggestSize);
2569 bool evalFail=
false;
2580 for (
int i= 0;
i < biggestSize;
i++)
2592 if (V_buf.
level() != 1)
2601 bool prim_fail=
false;
2605 prim_elem_alpha= prim_elem;
2607 ASSERT (!prim_fail,
"failure in integer factorizer");
2611 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2617 im_prim_elem_alpha= im_prim_elem;
2619 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2620 prim_elem, im_prim_elem, source, dest);
2623 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
2624 im_prim_elem, source, dest);
2627 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2628 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2640 bool initialized=
false;
2669 delete[] pEvalPoints;
2678 if (
k.exp() !=
l.exp())
2680 delete[] pEvalPoints;
2697 if (Monoms.
size() == 0)
2700 coeffMonoms=
new CFArray [skelSize];
2706 int minimalColumnsIndex;
2708 minimalColumnsIndex= 1;
2710 minimalColumnsIndex= 0;
2711 int minimalColumns=-1;
2716 for (
int i= 0;
i < skelSize;
i++)
2720 minimalColumns= coeffMonoms[
i].
size();
2723 if (minimalColumns > coeffMonoms[
i].
size())
2725 minimalColumns= coeffMonoms[
i].
size();
2726 minimalColumnsIndex=
i;
2731 pMat[0]=
CFMatrix (biggestSize, coeffMonoms[0].
size());
2732 pMat[1]=
CFMatrix (biggestSize, coeffMonoms[minimalColumnsIndex].
size());
2734 for (
int i= 0;
i < biggestSize;
i++)
2738 for (
int k= 0;
k < skelSize;
k++,
l++)
2742 pL[
k] [
i]=
l.coeff();
2744 if (
i == 0 &&
k != 0 &&
k != minimalColumnsIndex)
2746 else if (
i == 0 && (
k == 0 ||
k == minimalColumnsIndex))
2748 if (
i > 0 && (
k == 0 ||
k == minimalColumnsIndex))
2753 if (pMat[
k].rows() >=
i + 1)
2755 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2756 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2759 if (
k == minimalColumnsIndex)
2761 if (pMat[1].rows() >=
i + 1)
2763 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2764 pMat[1] (
i + 1, ind)= coeffEval[ind - 1];
2773 int matRows, matColumns;
2774 matRows= pMat[1].
rows();
2775 matColumns= pMat[0].
columns() - 1;
2776 matColumns += pMat[1].
columns();
2778 Mat=
CFMatrix (matRows, matColumns);
2779 for (
int i= 1;
i <= matRows;
i++)
2781 Mat (
i,
j)= pMat[1] (
i,
j);
2783 for (
int j= pMat[1].columns() + 1;
j <= matColumns;
2786 for (
int i= 1;
i <= matRows;
i++)
2787 Mat (
i,
j)= (-pMat [0] (
i, ind + 1))*pL[minimalColumnsIndex] [
i - 1];
2791 for (
int i= 0;
i < pMat[0].
rows();
i++)
2792 firstColumn [
i]= pMat[0] (
i + 1, 1);
2794 CFArray bufArray= pL[minimalColumnsIndex];
2796 for (
int i= 0;
i < biggestSize;
i++)
2797 pL[minimalColumnsIndex] [
i] *= firstColumn[
i];
2802 if (V_buf.
level() != 1)
2804 pL[minimalColumnsIndex], V_buf);
2807 pL[minimalColumnsIndex]);
2809 if (solution.
size() == 0)
2814 pL[minimalColumnsIndex]= bufArray;
2817 if (biggestSize != biggestSize2)
2819 bufpEvalPoints= pEvalPoints;
2820 pEvalPoints=
new CFList [biggestSize2];
2823 for (
int i= 0;
i < biggestSize;
i++)
2825 pEvalPoints[
i]= bufpEvalPoints [
i];
2826 gcds[
i]= bufGcds[
i];
2828 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2836 delete[] pEvalPoints;
2839 delete[] coeffMonoms;
2841 if (bufpEvalPoints !=
NULL)
2842 delete [] bufpEvalPoints;
2851 if (
k.exp() !=
l.exp())
2853 delete[] pEvalPoints;
2856 delete[] coeffMonoms;
2858 if (bufpEvalPoints !=
NULL)
2859 delete [] bufpEvalPoints;
2867 gcds[
i + biggestSize]=
g;
2870 for (
int i= 0;
i < biggestSize;
i++)
2874 for (
int k= 1;
k < skelSize;
k++,
l++)
2877 pMat[
k]=
CFMatrix (biggestSize2,coeffMonoms[
k].
size()+biggestSize2-1);
2878 if (
k == minimalColumnsIndex)
2881 if (pMat[
k].rows() >=
i + 1)
2883 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2884 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2889 pMat[0]=
CFMatrix (biggestSize2, coeffMonoms[0].
size() + biggestSize2 - 1);
2890 for (
int j= 1;
j <= Mat.
rows();
j++)
2892 pMat [0] (
j,
k)= Mat (
j,
k);
2894 for (
int j= 1;
j <= Mat.
rows();
j++)
2896 pMat [minimalColumnsIndex] (
j,
k)= Mat (
j,
k);
2898 for (
int i= 0;
i < skelSize;
i++)
2902 for (
int j= 0;
j < bufArray.
size();
j++)
2903 pL[
i] [
j]= bufArray [
j];
2906 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2910 for (
int k= 0;
k < skelSize;
k++,
l++)
2912 pL[
k] [
i + biggestSize]=
l.coeff();
2914 if (pMat[
k].rows() >=
i + biggestSize + 1)
2916 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2917 pMat[
k] (
i + biggestSize + 1, ind)= coeffEval[ind - 1];
2922 for (
int i= 0;
i < skelSize;
i++)
2924 if (pL[
i].
size() > 1)
2926 for (
int j= 2;
j <= pMat[
i].
rows();
j++)
2927 pMat[
i] (
j, coeffMonoms[
i].
size() +
j - 1)=
2932 matColumns= biggestSize2 - 1;
2934 for (
int i= 0;
i < skelSize;
i++)
2936 if (V_buf.
level() == 1)
2941 if (pMat[
i] (coeffMonoms[
i].
size(), coeffMonoms[
i].
size()) == 0)
2943 delete[] pEvalPoints;
2946 delete[] coeffMonoms;
2948 if (bufpEvalPoints !=
NULL)
2949 delete [] bufpEvalPoints;
2955 matRows += pMat[
i].
rows() - coeffMonoms[
i].
size();
2959 Mat=
CFMatrix (matRows, matColumns);
2963 for (
int i= 0;
i < skelSize;
i++)
2965 if (coeffMonoms[
i].
size() + 1 >= pMat[
i].rows() || coeffMonoms[
i].
size() + 1 >= pMat[
i].columns())
2967 delete[] pEvalPoints;
2970 delete[] coeffMonoms;
2972 if (bufpEvalPoints !=
NULL)
2973 delete [] bufpEvalPoints;
2979 bufMat= pMat[
i] (coeffMonoms[
i].
size() + 1, pMat[
i].
rows(),
2982 for (
int j= 1;
j <= bufMat.
rows();
j++)
2984 Mat (
j + ind,
k)= bufMat(
j,
k);
2985 bufArray2= coeffMonoms[
i].
size();
2986 for (
int j= 1;
j <= pMat[
i].
rows();
j++)
2988 if (
j > coeffMonoms[
i].
size())
2989 bufArray [
j-coeffMonoms[
i].
size() + ind - 1]= pL[
i] [
j - 1];
2991 bufArray2 [
j - 1]= pL[
i] [
j - 1];
2994 ind += bufMat.
rows();
2998 if (V_buf.
level() != 1)
3003 if (solution.
size() == 0)
3005 delete[] pEvalPoints;
3008 delete[] coeffMonoms;
3010 if (bufpEvalPoints !=
NULL)
3011 delete [] bufpEvalPoints;
3021 for (
int i= 0;
i < skelSize;
i++)
3024 for (
int i= 0;
i < bufSolution.
size();
i++, ind++)
3025 result += Monoms [ind]*bufSolution[
i];
3034 delete[] pEvalPoints;
3037 delete[] coeffMonoms;
3040 if (bufpEvalPoints !=
NULL)
3041 delete [] bufpEvalPoints;
3052 int ind2= 0, ind3= 2;
3054 for (
int l= 0;
l < minimalColumnsIndex;
l++)
3055 ind += coeffMonoms[
l].
size();
3057 l++,
ind2++, ind3++)
3060 for (
int i= 0;
i < pMat[0].
rows();
i++)
3061 firstColumn[
i] += solution[
l]*pMat[0] (
i + 1, ind3);
3063 for (
int l= 0;
l < solution.
size() + 1 - pMat[0].columns();
l++)
3064 result += solution[
l]*Monoms [ind +
l];
3065 ind= coeffMonoms[0].
size();
3066 for (
int k= 1;
k < skelSize;
k++)
3068 if (
k == minimalColumnsIndex)
3070 ind += coeffMonoms[
k].
size();
3073 if (
k != minimalColumnsIndex)
3075 for (
int i= 0;
i < biggestSize;
i++)
3076 pL[
k] [
i] *= firstColumn [
i];
3079 if (biggestSize != coeffMonoms[
k].
size() &&
k != minimalColumnsIndex)
3082 for (
int i= 0;
i < bufArray.
size();
i++)
3083 bufArray [
i]= pL[
k] [
i];
3089 if (solution.
size() == 0)
3091 delete[] pEvalPoints;
3094 delete[] coeffMonoms;
3101 if (
k != minimalColumnsIndex)
3103 for (
int l= 0;
l < solution.
size();
l++)
3104 result += solution[
l]*Monoms [ind +
l];
3105 ind += solution.
size();
3109 delete[] pEvalPoints;
3113 delete[] coeffMonoms;
3143 if (F ==
G)
return F/
Lc(F);
3148 if (best_level == 0)
return B.
genOne();
3165 gcdcAcB=
gcd (cA, cB);
3185 gcdlcAlcB=
gcd (lcA, lcB);
3200 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3207 bool inextension=
false;
3215 if (random_element == 0 && !fail)
3217 if (!
find (
l, random_element))
3218 l.append (random_element);
3228 bool prim_fail=
false;
3231 if (V_buf4 ==
alpha)
3232 prim_elem_alpha= prim_elem;
3234 if (V_buf3 != V_buf4)
3236 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3237 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3238 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3240 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3241 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3242 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4, source,
3245 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3249 ASSERT (!prim_fail,
"failure in integer factorizer");
3253 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3255 if (V_buf4 ==
alpha)
3256 im_prim_elem_alpha= im_prim_elem;
3258 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
3259 im_prim_elem, source, dest);
3265 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3266 im_prim_elem, source, dest);
3267 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3268 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3269 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3271 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3272 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3273 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3282 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3285 "time for recursive call: ");
3286 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3294 sparseGCDFq (ppA(random_element,
x), ppB(random_element,
x), V_buf,
3297 "time for recursive call: ");
3298 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3315 if (!
find (
l, random_element))
3316 l.append (random_element);
3321 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3324 skeleton= G_random_element;
3339 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3351 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3352 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3354 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3356 return N(gcdcAcB*ppH);
3360 return N(gcdcAcB*ppH);
3363 newtonPoly= newtonPoly*(
x - random_element);
3364 m=
m*(
x - random_element);
3365 if (!
find (
l, random_element))
3366 l.append (random_element);
3375 if (random_element == 0 && !fail)
3377 if (!
find (
l, random_element))
3378 l.append (random_element);
3388 bool prim_fail=
false;
3391 if (V_buf4 ==
alpha)
3392 prim_elem_alpha= prim_elem;
3394 if (V_buf3 != V_buf4)
3396 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3397 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3398 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3400 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3401 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3402 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
3405 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3409 ASSERT (!prim_fail,
"failure in integer factorizer");
3413 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3415 if (V_buf4 ==
alpha)
3416 im_prim_elem_alpha= im_prim_elem;
3418 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
3419 prim_elem, im_prim_elem, source, dest);
3425 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3426 im_prim_elem, source, dest);
3427 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3428 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3429 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3431 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3432 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3434 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3446 bool sparseFail=
false;
3447 if (
LC (skeleton).inCoeffDomain())
3450 skeleton,V_buf, sparseFail, coeffMonoms,Monoms);
3454 skeleton, V_buf, sparseFail, coeffMonoms,
3460 "time for recursive call: ");
3461 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3467 bool sparseFail=
false;
3468 if (
LC (skeleton).inCoeffDomain())
3471 skeleton,V_buf, sparseFail,coeffMonoms, Monoms);
3475 skeleton, V_buf, sparseFail, coeffMonoms,
3481 "time for recursive call: ");
3482 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3499 if (!
find (
l, random_element))
3500 l.append (random_element);
3505 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3523 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3525 "time for newton interpolation: ");
3539 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3540 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3542 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3544 return N(gcdcAcB*ppH);
3549 return N(gcdcAcB*ppH);
3554 newtonPoly= newtonPoly*(
x - random_element);
3555 m=
m*(
x - random_element);
3556 if (!
find (
l, random_element))
3557 l.append (random_element);
3575 if (F ==
G)
return F/
Lc(F);
3580 if (best_level == 0)
return B.
genOne();
3597 gcdcAcB=
gcd (cA, cB);
3617 gcdlcAlcB=
gcd (lcA, lcB);
3633 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3640 bool inextension=
false;
3650 if (random_element == 0 && !fail)
3652 if (!
find (
l, random_element))
3653 l.append (random_element);
3657 if (!fail && !inextension)
3665 "time for recursive call: ");
3666 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3668 else if (!fail && inextension)
3676 "time for recursive call: ");
3677 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3679 else if (fail && !inextension)
3686 bool initialized=
false;
3708 "time for recursive call: ");
3709 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3711 else if (fail && inextension)
3718 bool prim_fail=
false;
3723 if (V_buf3 !=
alpha)
3726 G_m=
mapDown (
m, prim_elem, im_prim_elem,
alpha, source, dest);
3727 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha, source,
3729 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
3730 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
3731 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
3734 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3738 ASSERT (!prim_fail,
"failure in integer factorizer");
3748 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3749 im_prim_elem, source, dest);
3750 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3751 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3752 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
3754 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3755 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3756 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
3764 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3767 "time for recursive call: ");
3768 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3786 if (!
find (
l, random_element))
3787 l.append (random_element);
3792 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3795 skeleton= G_random_element;
3811 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3824 return N(gcdcAcB*ppH);
3828 newtonPoly= newtonPoly*(
x - random_element);
3829 m=
m*(
x - random_element);
3830 if (!
find (
l, random_element))
3831 l.append (random_element);
3844 if (random_element == 0 && !fail)
3846 if (!
find (
l, random_element))
3847 l.append (random_element);
3851 bool sparseFail=
false;
3852 if (!fail && !inextension)
3856 if (
LC (skeleton).inCoeffDomain())
3859 skeleton,
x, sparseFail, coeffMonoms,
3864 skeleton,
x, sparseFail,
3865 coeffMonoms, Monoms);
3867 "time for recursive call: ");
3868 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3870 else if (!fail && inextension)
3874 if (
LC (skeleton).inCoeffDomain())
3877 skeleton,
alpha, sparseFail, coeffMonoms,
3882 skeleton,
alpha, sparseFail, coeffMonoms,
3885 "time for recursive call: ");
3886 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3888 else if (fail && !inextension)
3895 bool initialized=
false;
3913 if (
LC (skeleton).inCoeffDomain())
3916 skeleton,
alpha, sparseFail, coeffMonoms,
3921 skeleton,
alpha, sparseFail, coeffMonoms,
3924 "time for recursive call: ");
3925 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3927 else if (fail && inextension)
3934 bool prim_fail=
false;
3939 if (V_buf3 !=
alpha)
3942 G_m=
mapDown (
m, prim_elem, im_prim_elem,
alpha, source, dest);
3943 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
3945 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
3946 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
3947 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha,
3950 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3954 ASSERT (!prim_fail,
"failure in integer factorizer");
3964 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3965 im_prim_elem, source, dest);
3966 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3967 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3968 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
3970 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3971 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3972 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
3979 if (
LC (skeleton).inCoeffDomain())
3982 skeleton, V_buf, sparseFail, coeffMonoms,
3987 skeleton, V_buf, sparseFail,
3988 coeffMonoms, Monoms);
3990 "time for recursive call: ");
3991 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
4012 if (!
find (
l, random_element))
4013 l.append (random_element);
4018 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
4036 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
4038 "time for newton interpolation: ");
4051 return N(gcdcAcB*ppH);
4056 newtonPoly= newtonPoly*(
x - random_element);
4057 m=
m*(
x - random_element);
4058 if (!
find (
l, random_element))
4059 l.append (random_element);
4148#if defined(HAVE_NTL) || defined(HAVE_FLINT)
4163 "time for gcd mod p in modular gcd: ");
4242 "time for successful termination in modular gcd: ");
4247 "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)
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.
TIMING_DEFINE_PRINT(gcd_recursion) TIMING_DEFINE_PRINT(newton_interpolation) TIMING_DEFINE_PRINT(termination_test) TIMING_DEFINE_PRINT(ez_p_compress) TIMING_DEFINE_PRINT(ez_p_hensel_lift) TIMING_DEFINE_PRINT(ez_p_eval) TIMING_DEFINE_PRINT(ez_p_content) bool terminationTest(const CanonicalForm &F
CFArray solveVandermonde(const CFArray &M, const CFArray &A)
static const double log2exp
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)
void eval(const CanonicalForm &A, const CanonicalForm &B, CanonicalForm &Aeval, CanonicalForm &Beval, const CFList &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,...
CanonicalForm abs(const CanonicalForm &f)
inline CanonicalForm abs ( const CanonicalForm & f )
#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)
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
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)
const signed long floor(const ampf< Precision > &x)
const signed long ceil(const ampf< Precision > &x)