88#if defined(HAVE_NTL)|| defined(HAVE_FLINT)
99 for (
int i = n;
i >= 0;
i--)
112 for (
int i= 1;
i <= n;
i++)
141 for (
int i= 1;
i <= n;
i++)
176 while (min_max_deg == 0)
184 for (
int j=
i + 1;
j <=
m;
j++)
232 for (
int i= 1;
i <= n;
i++)
299 for (;
i.hasTerms();
i++)
322 for (
int i= 1;
i <= d;
i++)
326 gcdcFcG=
gcd (uniContentF, uniContentG);
327 contentF *= uniContentF;
328 contentG *= uniContentG;
371 interPoly= oldInterPoly + ((u - oldInterPoly(
alpha,
x))/newtonPoly(
alpha,
x))
391 double bound=
pow ((
double)
p, (
double) d);
402 while (
find (list, random))
408 while (
find (list, random))
411 if (F (random,
x) == 0)
416 }
while (
find (list, random));
425 if (
alpha.level() == 1)
430 if (
alpha.level() != 1)
436 nmod_poly_t Irredpoly;
438 nmod_poly_randtest_monic_irreducible(Irredpoly,
FLINTrandom,
i*
m+1);
448 BuildIrred (NTLIrredpoly,
i*
m);
454#if defined(HAVE_NTL) || defined(HAVE_FLINT)
461#if defined(HAVE_NTL) || defined(HAVE_FLINT)
477#if defined(HAVE_NTL) || defined(HAVE_FLINT)
491 else if (
G.isZero() &&
degree (F) > 0)
497 else if (F.
isZero() &&
G.isZero())
540 if (
A.isUnivariate() &&
B.isUnivariate())
554 gcdcAcB=
gcd (cA, cB);
564 gcdlcAlcB=
gcd (lcA, lcB);
570 coF=
N (ppA*(cA/gcdcAcB));
571 coG=
N (ppB*(cB/gcdcAcB));
580 coF=
N (ppA*(cA/gcdcAcB));
581 coG=
N (ppB*(cB/gcdcAcB));
586 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
597 bool inextension=
false;
602 int bound1=
degree (ppA, 1);
603 int bound2=
degree (ppB, 1);
614 bool prim_fail=
false;
618 prim_elem_alpha= prim_elem;
620 if (V_buf3 != V_buf4)
622 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
623 G_m=
mapDown (G_m, prim_elem, im_prim_elem, V_buf4, source, dest);
624 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem, V_buf4, source, dest);
625 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem, V_buf4, source, dest);
626 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
628 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
629 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
630 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
632 lcA=
mapDown (lcA, prim_elem, im_prim_elem, V_buf4, source, dest);
633 lcB=
mapDown (lcB, prim_elem, im_prim_elem, V_buf4, source, dest);
635 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
639 ASSERT (!prim_fail,
"failure in integer factorizer");
643 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
646 im_prim_elem_alpha= im_prim_elem;
648 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
649 im_prim_elem, source, dest);
654 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
655 im_prim_elem, source, dest);
656 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
657 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
658 coF_m=
mapUp (coF_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
659 coG_m=
mapUp (coG_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
660 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
662 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
663 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
664 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
666 lcA=
mapUp (lcA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
667 lcB=
mapUp (lcB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
675 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
676 coF_random_element, coG_random_element, V_buf,
679 "time for recursive call: ");
680 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
688 modGCDFq (ppA(random_element,
x), ppB(random_element,
x),
689 coF_random_element, coG_random_element, V_buf,
692 "time for recursive call: ");
693 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
707 ppA=
mapDown (ppA, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
708 ppB=
mapDown (ppB, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
711 coF=
N (ppA*(cA/gcdcAcB));
712 coG=
N (ppB*(cB/gcdcAcB));
717 if (!
find (
l, random_element))
718 l.append (random_element);
723 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
725 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
727 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
747 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
748 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
749 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
751 "time for newton interpolation: ");
757 if (gcdlcAlcB.
isOne())
776 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
777 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
778 ppCoF=
mapDown (ppCoF, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
779 ppCoG=
mapDown (ppCoG, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
780 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
781 coF=
N ((cA/gcdcAcB)*ppCoF);
782 coG=
N ((cB/gcdcAcB)*ppCoG);
784 "time for successful termination test Fq: ");
786 return N(gcdcAcB*ppH);
789 else if (((
degree (ppCoF,1)+
degree (ppH,1) == bound1) &&
794 coF=
N ((cA/gcdcAcB)*ppCoF);
795 coG=
N ((cB/gcdcAcB)*ppCoG);
797 "time for successful termination test Fq: ");
798 return N(gcdcAcB*ppH);
801 "time for unsuccessful termination test Fq: ");
807 newtonPoly= newtonPoly*(
x - random_element);
808 m=
m*(
x - random_element);
809 if (!
find (
l, random_element))
810 l.append (random_element);
841 while (
find (list, random))
844 if (F (random,
x) == 0)
849 }
while (
find (list, random));
885 else if (
G.isZero() &&
degree (F) > 0)
891 else if (F.
isZero() &&
G.isZero())
934 if (
A.isUnivariate() &&
B.isUnivariate())
948 gcdcAcB=
gcd (cA, cB);
958 gcdlcAlcB=
gcd (lcA, lcB);
963 coF=
N (ppA*(cA/gcdcAcB));
964 coG=
N (ppB*(cB/gcdcAcB));
972 coF=
N (ppA*(cA/gcdcAcB));
973 coG=
N (ppB*(cB/gcdcAcB));
978 CanonicalForm newtonPoly, coF_random_element, coG_random_element, coF_m,
989 bool inextension=
false;
995 int bound1=
degree (ppA, 1);
996 int bound2=
degree (ppB, 1);
1005 if (
ipower (
p, kk*expon) < (1 << 16))
1009 expon= (int) floor((
log ((
double)((1<<16) - 1)))/(
log((
double)
p)*kk));
1010 ASSERT (expon >= 2,
"not enough points in modGCDGF");
1019 newtonPoly=
GFMapUp (newtonPoly, kk);
1024 gcdlcAlcB=
GFMapUp (gcdlcAlcB, kk);
1031 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1032 coF_random_element, coG_random_element,
1035 "time for recursive call: ");
1036 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1042 G_random_element=
modGCDGF (ppA(random_element,
x), ppB(random_element,
x),
1043 coF_random_element, coG_random_element,
1046 "time for recursive call: ");
1047 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1064 coF=
N (ppA*(cA/gcdcAcB));
1065 coG=
N (ppB*(cB/gcdcAcB));
1070 if (!
find (
l, random_element))
1071 l.append (random_element);
1076 (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element)) *
1079 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1080 *coF_random_element;
1081 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1082 *coG_random_element;
1101 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1102 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1103 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1105 "time for newton interpolation: ");
1111 if (gcdlcAlcB.
isOne())
1129 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
1133 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
1134 coF=
N ((cA/gcdcAcB)*ppCoF);
1135 coG=
N ((cB/gcdcAcB)*ppCoG);
1138 "time for successful termination GF: ");
1139 return N(gcdcAcB*ppH);
1149 coF=
N ((cA/gcdcAcB)*ppCoF);
1150 coG=
N ((cB/gcdcAcB)*ppCoG);
1152 "time for successful termination GF: ");
1153 return N(gcdcAcB*ppH);
1157 "time for unsuccessful termination GF: ");
1163 newtonPoly= newtonPoly*(
x - random_element);
1164 m=
m*(
x - random_element);
1165 if (!
find (
l, random_element))
1166 l.append (random_element);
1192 while (
find (list, random))
1195 if (F (random,
x) == 0)
1200 }
while (
find (list, random));
1204#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1211#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1222#if defined(HAVE_NTL) || defined(HAVE_FLINT)
1236 else if (
G.isZero() &&
degree (F) > 0)
1242 else if (F.
isZero() &&
G.isZero())
1271 if (best_level == 0)
1284 if (
A.isUnivariate() &&
B.isUnivariate())
1298 gcdcAcB=
gcd (cA, cB);
1307 gcdlcAlcB=
gcd (lcA, lcB);
1314 coF=
N (ppA*(cA/gcdcAcB));
1315 coG=
N (ppB*(cB/gcdcAcB));
1326 coF=
N (ppA*(cA/gcdcAcB));
1327 coG=
N (ppB*(cB/gcdcAcB));
1332 CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1333 coF_m, coG_m, ppCoF, ppCoG;
1343 bool inextension=
false;
1346 int bound1=
degree (ppA, 1);
1347 int bound2=
degree (ppB, 1);
1355 if (!fail && !inextension)
1360 modGCDFp (ppA (random_element,
x), ppB (random_element,
x),
1361 coF_random_element, coG_random_element,
topLevel,
1364 "time for recursive call: ");
1365 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1367 else if (!fail && inextension)
1372 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1373 coF_random_element, coG_random_element, V_buf,
1376 "time for recursive call: ");
1377 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1379 else if (fail && !inextension)
1386 bool initialized=
false;
1405 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1406 coF_random_element, coG_random_element,
alpha,
1409 "time for recursive call: ");
1410 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1412 else if (fail && inextension)
1419 bool prim_fail=
false;
1424 if (V_buf3 !=
alpha)
1427 G_m=
mapDown (G_m, prim_elem, im_prim_elem,
alpha, source, dest);
1428 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem,
alpha, source, dest);
1429 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem,
alpha, source, dest);
1430 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
1432 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
1433 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
1434 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
1436 lcA=
mapDown (lcA, prim_elem, im_prim_elem,
alpha, source, dest);
1437 lcB=
mapDown (lcB, prim_elem, im_prim_elem,
alpha, source, dest);
1439 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
1443 ASSERT (!prim_fail,
"failure in integer factorizer");
1453 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
1454 im_prim_elem, source, dest);
1455 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1456 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1457 coF_m=
mapUp (coF_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1458 coG_m=
mapUp (coG_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1459 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
1461 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1462 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1463 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
1465 lcA=
mapUp (lcA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1466 lcB=
mapUp (lcB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1473 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1474 coF_random_element, coG_random_element, V_buf,
1477 "time for recursive call: ");
1478 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1492 coF=
N (ppA*(cA/gcdcAcB));
1493 coG=
N (ppB*(cB/gcdcAcB));
1499 if (!
find (
l, random_element))
1500 l.append (random_element);
1504 G_random_element= (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element))
1507 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1508 *coF_random_element;
1509 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1510 *coG_random_element;
1529 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1530 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1531 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1533 "time for newton_interpolation: ");
1539 if (gcdlcAlcB.
isOne())
1558 coF=
N ((cA/gcdcAcB)*ppCoF);
1559 coG=
N ((cB/gcdcAcB)*ppCoG);
1561 "time for successful termination Fp: ");
1562 return N(gcdcAcB*ppH);
1565 "time for unsuccessful termination Fp: ");
1571 newtonPoly= newtonPoly*(
x - random_element);
1572 m=
m*(
x - random_element);
1573 if (!
find (
l, random_element))
1574 l.append (random_element);
1583 ASSERT (
A.size() == r,
"vector does not have right size");
1592 bool notDistinct=
false;
1593 for (
int i= 0;
i < r - 1;
i++)
1595 for (
int j=
i + 1;
j < r;
j++)
1609 for (
int i= 0;
i < r;
i++)
1610 master *=
x -
M [
i];
1613 for (
int i= 0;
i < r;
i++)
1615 tmp= master/(
x -
M [
i]);
1616 tmp /= tmp (
M [
i], 1);
1622 for (
int i= 1;
i <= r;
i++,
j++)
1625 for (
int l= 0;
l <
A.size();
l++)
1626 tmp +=
A[
l]*
j.getItem()[
l];
1636 ASSERT (
A.size() == r,
"vector does not have right size");
1644 bool notDistinct=
false;
1645 for (
int i= 0;
i < r - 1;
i++)
1647 for (
int j=
i + 1;
j < r;
j++)
1661 for (
int i= 0;
i < r;
i++)
1662 master *=
x -
M [
i];
1666 for (
int i= 0;
i < r;
i++)
1668 tmp= master/(
x -
M [
i]);
1669 tmp /= tmp (
M [
i], 1);
1676 for (
int i= 1;
i <= r;
i++,
j++)
1680 for (
int l= 1;
l <=
A.size();
l++)
1681 tmp +=
A[
l - 1]*
j.getItem()[
l];
1693 for (
int i= rk;
i >= 1;
i--)
1697 for (
int j=
M.columns() - 1;
j >= 1;
j--)
1716 for (
int i=
M.rows();
i >= 1;
i--)
1721 for (
int j=
M.columns();
j >= 1;
j--,
k++)
1728 if (
k > partialSol.
size() - 1)
1731 tmp3 +=
tmp2*partialSol[partialSol.
size() -
k - 1];
1742 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1746 for (
int i= 1;
i <=
M.rows();
i++)
1747 for (
int j= 1;
j <=
M.columns();
j++)
1751 for (
int i= 0;
i < L.
size();
i++,
j++)
1752 (*
N) (
j,
M.columns() + 1)= L[
i];
1756 long rk= nmod_mat_rref (FLINTN);
1760 nmod_mat_clear (FLINTN);
1770 long rk= gauss (*NTLN);
1777 for (
int i= 0;
i <
M.rows();
i++)
1778 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1779 M= (*N) (1,
M.rows(), 1,
M.columns());
1787 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1791 for (
int i= 1;
i <=
M.rows();
i++)
1792 for (
int j= 1;
j <=
M.columns();
j++)
1796 for (
int i= 0;
i < L.
size();
i++,
j++)
1797 (*
N) (
j,
M.columns() + 1)= L[
i];
1806 fq_nmod_mat_t FLINTN;
1809 #if __FLINT_RELEASE >= 30100
1810 long rk= fq_nmod_mat_rref (FLINTN,FLINTN,ctx);
1812 long rk= fq_nmod_mat_rref (FLINTN,ctx);
1815 fq_nmod_mat_clear (FLINTN,ctx);
1817 #elif defined(HAVE_NTL)
1825 zz_pE::init (NTLMipo);
1827 long rk= gauss (*NTLN);
1834 M= (*N) (1,
M.rows(), 1,
M.columns());
1836 for (
int i= 0;
i <
M.rows();
i++)
1837 L[
i]= (*
N) (
i + 1,
M.columns() + 1);
1846 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1850 for (
int i= 1;
i <=
M.rows();
i++)
1851 for (
int j= 1;
j <=
M.columns();
j++)
1855 for (
int i= 0;
i < L.
size();
i++,
j++)
1856 (*
N) (
j,
M.columns() + 1)= L[
i];
1861 long rk= nmod_mat_rref (FLINTN);
1870 long rk= gauss (*NTLN);
1873 if (rk !=
M.columns())
1876 nmod_mat_clear (FLINTN);
1884 nmod_mat_clear (FLINTN);
1898 ASSERT (L.
size() <=
M.rows(),
"dimension exceeded");
1902 for (
int i= 1;
i <=
M.rows();
i++)
1903 for (
int j= 1;
j <=
M.columns();
j++)
1906 for (
int i= 0;
i < L.
size();
i++,
j++)
1907 (*
N) (
j,
M.columns() + 1)= L[
i];
1916 fq_nmod_mat_t FLINTN;
1919 #if __FLINT_RELEASE >= 30100
1920 long rk= fq_nmod_mat_rref (FLINTN,FLINTN,ctx);
1922 long rk= fq_nmod_mat_rref (FLINTN,ctx);
1924 #elif defined(HAVE_NTL)
1932 zz_pE::init (NTLMipo);
1934 long rk= gauss (*NTLN);
1940 if (rk !=
M.columns())
1942 #if defined(HAVE_NTL) && !defined(HAVE_FLINT)
1950 fq_nmod_mat_clear (FLINTN,ctx);
1952 #elif defined(HAVE_NTL)
1981 int numMon=
size (F);
1991 for (
int k= 0;
k < recResult.
size();
k++)
1993 j += recResult.
size();
1998#if defined(HAVE_NTL) || defined(HAVE_FLINT)
2011 "expected an eval point with only one component");
2019 int numMon=
size (F);
2031 for (
int k= 0;
k < recResult.
size();
k++)
2033 j += recResult.
size();
2044 for (
int i= 0;
i <
A.size();
i++)
2049 tmp= tmp (
j.getItem(),
k);
2084 bool zeroOneOccured=
false;
2085 bool allEqual=
false;
2096 for (
int i= 0;
i <
k;
i++)
2103 else if (
alpha.level() != 1)
2114 if (
result.getLast().isOne() ||
result.getLast().isZero())
2115 zeroOneOccured=
true;
2117 if (
find (list, random))
2119 zeroOneOccured=
false;
2127 zeroOneOccured=
false;
2147 zeroOneOccured=
false;
2159 Geval= Geval (
i.getItem(),
j);
2160 LCeval= LCeval (
i.getItem(),
j);
2165 if (!
find (list, random))
2167 zeroOneOccured=
false;
2178 }
while (
find (list, random));
2190 i.getItem() *=
j.getItem();
2202 Beval= Beval (
i.getItem(),
j);
2215 else if (
G.isZero() &&
degree (F) > 0)
return F/
Lc(F);
2220 if (F ==
G)
return F/
Lc(F);
2228 if (best_level == 0)
2237 if (
A.isUnivariate() &&
B.isUnivariate())
2246 gcdcAcB=
gcd (cA, cB);
2266 gcdlcAlcB=
gcd (lcA, lcB);
2267 int skelSize=
size (skel, skel.
mvar());
2273 biggestSize=
tmax (biggestSize,
size (
i.coeff()));
2278 bool evalFail=
false;
2289 for (
int i= 0;
i < biggestSize;
i++)
2302 if (V_buf.
level() != 1)
2311 bool prim_fail=
false;
2315 prim_elem_alpha= prim_elem;
2317 ASSERT (!prim_fail,
"failure in integer factorizer");
2321 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2327 im_prim_elem_alpha= im_prim_elem;
2328 else if (
alpha.level() != 1)
2329 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2330 prim_elem, im_prim_elem, source, dest);
2333 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2334 im_prim_elem, source, dest);
2335 for (
int k= 0;
k <
i;
k++)
2338 j.getItem()=
mapUp (
j.getItem(), V_buf4, V_buf, prim_elem,
2339 im_prim_elem, source, dest);
2340 gcds[
k]=
mapUp (gcds[
k], V_buf4, V_buf, prim_elem, im_prim_elem,
2344 if (
alpha.level() != 1)
2346 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2347 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2359 bool initialized=
false;
2382 delete[] pEvalPoints;
2391 if (
k.exp() !=
l.exp())
2393 delete[] pEvalPoints;
2410 if (Monoms.
size() == 0)
2413 coeffMonoms=
new CFArray [skelSize];
2420 for (
int i= 0;
i < biggestSize;
i++)
2424 for (
int k= 0;
k < skelSize;
k++,
l++)
2428 pL[
k] [
i]=
l.coeff();
2440 for (
int k= 0;
k < skelSize;
k++)
2442 if (biggestSize != coeffMonoms[
k].
size())
2445 for (
int i= 0;
i < coeffMonoms[
k].
size();
i++)
2446 bufArray [
i]= pL[
k] [
i];
2452 if (solution.
size() == 0)
2454 delete[] pEvalPoints;
2457 delete[] coeffMonoms;
2463 for (
int l= 0;
l < solution.
size();
l++)
2464 result += solution[
l]*Monoms [ind +
l];
2465 ind += solution.
size();
2468 delete[] pEvalPoints;
2471 delete[] coeffMonoms;
2499 else if (
G.isZero() &&
degree (F) > 0)
return F/
Lc(F);
2504 if (F ==
G)
return F/
Lc(F);
2512 if (best_level == 0)
2521 if (
A.isUnivariate() &&
B.isUnivariate())
2531 gcdcAcB=
gcd (cA, cB);
2551 gcdlcAlcB=
gcd (lcA, lcB);
2552 int skelSize=
size (skel, skel.
mvar());
2560 bufSize=
size (
i.coeff());
2561 biggestSize=
tmax (biggestSize, bufSize);
2562 numberUni += bufSize;
2565 numberUni= (int) ceil ( (
double) numberUni / (skelSize - 1));
2566 biggestSize=
tmax (biggestSize , numberUni);
2568 numberUni= biggestSize +
size (
LC(skel)) - 1;
2569 int biggestSize2=
tmax (numberUni, biggestSize);
2575 bool evalFail=
false;
2586 for (
int i= 0;
i < biggestSize;
i++)
2598 if (V_buf.
level() != 1)
2607 bool prim_fail=
false;
2611 prim_elem_alpha= prim_elem;
2613 ASSERT (!prim_fail,
"failure in integer factorizer");
2617 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
2623 im_prim_elem_alpha= im_prim_elem;
2624 else if (
alpha.level() != 1)
2625 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
2626 prim_elem, im_prim_elem, source, dest);
2629 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
2630 im_prim_elem, source, dest);
2631 if (
alpha.level() != 1)
2633 A=
mapUp (
A, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2634 B=
mapUp (
B, V_buf4, V_buf, prim_elem, im_prim_elem, source,dest);
2646 bool initialized=
false;
2675 delete[] pEvalPoints;
2684 if (
k.exp() !=
l.exp())
2686 delete[] pEvalPoints;
2703 if (Monoms.
size() == 0)
2706 coeffMonoms=
new CFArray [skelSize];
2712 int minimalColumnsIndex;
2714 minimalColumnsIndex= 1;
2716 minimalColumnsIndex= 0;
2717 int minimalColumns=-1;
2722 for (
int i= 0;
i < skelSize;
i++)
2726 minimalColumns= coeffMonoms[
i].
size();
2729 if (minimalColumns > coeffMonoms[
i].
size())
2731 minimalColumns= coeffMonoms[
i].
size();
2732 minimalColumnsIndex=
i;
2737 pMat[0]=
CFMatrix (biggestSize, coeffMonoms[0].
size());
2738 pMat[1]=
CFMatrix (biggestSize, coeffMonoms[minimalColumnsIndex].
size());
2740 for (
int i= 0;
i < biggestSize;
i++)
2744 for (
int k= 0;
k < skelSize;
k++,
l++)
2748 pL[
k] [
i]=
l.coeff();
2750 if (
i == 0 &&
k != 0 &&
k != minimalColumnsIndex)
2752 else if (
i == 0 && (
k == 0 ||
k == minimalColumnsIndex))
2754 if (
i > 0 && (
k == 0 ||
k == minimalColumnsIndex))
2759 if (pMat[
k].rows() >=
i + 1)
2761 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2762 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2765 if (
k == minimalColumnsIndex)
2767 if (pMat[1].rows() >=
i + 1)
2769 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2770 pMat[1] (
i + 1, ind)= coeffEval[ind - 1];
2779 int matRows, matColumns;
2780 matRows= pMat[1].
rows();
2781 matColumns= pMat[0].
columns() - 1;
2782 matColumns += pMat[1].
columns();
2784 Mat=
CFMatrix (matRows, matColumns);
2785 for (
int i= 1;
i <= matRows;
i++)
2787 Mat (
i,
j)= pMat[1] (
i,
j);
2789 for (
int j= pMat[1].columns() + 1;
j <= matColumns;
2792 for (
int i= 1;
i <= matRows;
i++)
2793 Mat (
i,
j)= (-pMat [0] (
i, ind + 1))*pL[minimalColumnsIndex] [
i - 1];
2797 for (
int i= 0;
i < pMat[0].
rows();
i++)
2798 firstColumn [
i]= pMat[0] (
i + 1, 1);
2800 CFArray bufArray= pL[minimalColumnsIndex];
2802 for (
int i= 0;
i < biggestSize;
i++)
2803 pL[minimalColumnsIndex] [
i] *= firstColumn[
i];
2808 if (V_buf.
level() != 1)
2810 pL[minimalColumnsIndex], V_buf);
2813 pL[minimalColumnsIndex]);
2815 if (solution.
size() == 0)
2820 pL[minimalColumnsIndex]= bufArray;
2823 if (biggestSize != biggestSize2)
2825 bufpEvalPoints= pEvalPoints;
2826 pEvalPoints=
new CFList [biggestSize2];
2829 for (
int i= 0;
i < biggestSize;
i++)
2831 pEvalPoints[
i]= bufpEvalPoints [
i];
2832 gcds[
i]= bufGcds[
i];
2834 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2842 delete[] pEvalPoints;
2845 delete[] coeffMonoms;
2847 if (bufpEvalPoints !=
NULL)
2848 delete [] bufpEvalPoints;
2857 if (
k.exp() !=
l.exp())
2859 delete[] pEvalPoints;
2862 delete[] coeffMonoms;
2864 if (bufpEvalPoints !=
NULL)
2865 delete [] bufpEvalPoints;
2873 gcds[
i + biggestSize]=
g;
2876 for (
int i= 0;
i < biggestSize;
i++)
2880 for (
int k= 1;
k < skelSize;
k++,
l++)
2883 pMat[
k]=
CFMatrix (biggestSize2,coeffMonoms[
k].
size()+biggestSize2-1);
2884 if (
k == minimalColumnsIndex)
2887 if (pMat[
k].rows() >=
i + 1)
2889 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2890 pMat[
k] (
i + 1, ind)= coeffEval[ind - 1];
2895 pMat[0]=
CFMatrix (biggestSize2, coeffMonoms[0].
size() + biggestSize2 - 1);
2896 for (
int j= 1;
j <= Mat.
rows();
j++)
2898 pMat [0] (
j,
k)= Mat (
j,
k);
2900 for (
int j= 1;
j <= Mat.
rows();
j++)
2902 pMat [minimalColumnsIndex] (
j,
k)= Mat (
j,
k);
2904 for (
int i= 0;
i < skelSize;
i++)
2908 for (
int j= 0;
j < bufArray.
size();
j++)
2909 pL[
i] [
j]= bufArray [
j];
2912 for (
int i= 0;
i < biggestSize2 - biggestSize;
i++)
2916 for (
int k= 0;
k < skelSize;
k++,
l++)
2918 pL[
k] [
i + biggestSize]=
l.coeff();
2920 if (pMat[
k].rows() >=
i + biggestSize + 1)
2922 for (
int ind= 1; ind < coeffEval.
size() + 1; ind++)
2923 pMat[
k] (
i + biggestSize + 1, ind)= coeffEval[ind - 1];
2928 for (
int i= 0;
i < skelSize;
i++)
2930 if (pL[
i].
size() > 1)
2932 for (
int j= 2;
j <= pMat[
i].
rows();
j++)
2933 pMat[
i] (
j, coeffMonoms[
i].
size() +
j - 1)=
2938 matColumns= biggestSize2 - 1;
2940 for (
int i= 0;
i < skelSize;
i++)
2942 if (V_buf.
level() == 1)
2947 if (pMat[
i] (coeffMonoms[
i].
size(), coeffMonoms[
i].
size()) == 0)
2949 delete[] pEvalPoints;
2952 delete[] coeffMonoms;
2954 if (bufpEvalPoints !=
NULL)
2955 delete [] bufpEvalPoints;
2961 matRows += pMat[
i].
rows() - coeffMonoms[
i].
size();
2965 Mat=
CFMatrix (matRows, matColumns);
2969 for (
int i= 0;
i < skelSize;
i++)
2971 if (coeffMonoms[
i].
size() + 1 >= pMat[
i].rows() || coeffMonoms[
i].
size() + 1 >= pMat[
i].columns())
2973 delete[] pEvalPoints;
2976 delete[] coeffMonoms;
2978 if (bufpEvalPoints !=
NULL)
2979 delete [] bufpEvalPoints;
2985 bufMat= pMat[
i] (coeffMonoms[
i].
size() + 1, pMat[
i].rows(),
2986 coeffMonoms[
i].
size() + 1, pMat[
i].columns());
2988 for (
int j= 1;
j <= bufMat.
rows();
j++)
2990 Mat (
j + ind,
k)= bufMat(
j,
k);
2991 bufArray2= coeffMonoms[
i].
size();
2992 for (
int j= 1;
j <= pMat[
i].
rows();
j++)
2994 if (
j > coeffMonoms[
i].
size())
2995 bufArray [
j-coeffMonoms[
i].
size() + ind - 1]= pL[
i] [
j - 1];
2997 bufArray2 [
j - 1]= pL[
i] [
j - 1];
3000 ind += bufMat.
rows();
3001 pMat[
i]= pMat[
i] (1, coeffMonoms[
i].
size(), 1, pMat[
i].columns());
3004 if (V_buf.
level() != 1)
3009 if (solution.
size() == 0)
3011 delete[] pEvalPoints;
3014 delete[] coeffMonoms;
3016 if (bufpEvalPoints !=
NULL)
3017 delete [] bufpEvalPoints;
3027 for (
int i= 0;
i < skelSize;
i++)
3030 for (
int i= 0;
i < bufSolution.
size();
i++, ind++)
3031 result += Monoms [ind]*bufSolution[
i];
3040 delete[] pEvalPoints;
3043 delete[] coeffMonoms;
3046 if (bufpEvalPoints !=
NULL)
3047 delete [] bufpEvalPoints;
3058 int ind2= 0, ind3= 2;
3060 for (
int l= 0;
l < minimalColumnsIndex;
l++)
3061 ind += coeffMonoms[
l].
size();
3063 l++, ind2++, ind3++)
3065 result += solution[
l]*Monoms [1 + ind2];
3066 for (
int i= 0;
i < pMat[0].
rows();
i++)
3067 firstColumn[
i] += solution[
l]*pMat[0] (
i + 1, ind3);
3069 for (
int l= 0;
l < solution.
size() + 1 - pMat[0].columns();
l++)
3070 result += solution[
l]*Monoms [ind +
l];
3071 ind= coeffMonoms[0].
size();
3072 for (
int k= 1;
k < skelSize;
k++)
3074 if (
k == minimalColumnsIndex)
3076 ind += coeffMonoms[
k].
size();
3079 if (
k != minimalColumnsIndex)
3081 for (
int i= 0;
i < biggestSize;
i++)
3082 pL[
k] [
i] *= firstColumn [
i];
3085 if (biggestSize != coeffMonoms[
k].
size() &&
k != minimalColumnsIndex)
3088 for (
int i= 0;
i < bufArray.
size();
i++)
3089 bufArray [
i]= pL[
k] [
i];
3095 if (solution.
size() == 0)
3097 delete[] pEvalPoints;
3100 delete[] coeffMonoms;
3107 if (
k != minimalColumnsIndex)
3109 for (
int l= 0;
l < solution.
size();
l++)
3110 result += solution[
l]*Monoms [ind +
l];
3111 ind += solution.
size();
3115 delete[] pEvalPoints;
3119 delete[] coeffMonoms;
3144 else if (
G.isZero() &&
degree (F) > 0)
return F/
Lc(F);
3149 if (F ==
G)
return F/
Lc(F);
3154 if (best_level == 0)
return B.genOne();
3162 if (
A.isUnivariate() &&
B.isUnivariate())
3171 gcdcAcB=
gcd (cA, cB);
3191 gcdlcAlcB=
gcd (lcA, lcB);
3206 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3213 bool inextension=
false;
3221 if (random_element == 0 && !fail)
3223 if (!
find (
l, random_element))
3224 l.append (random_element);
3234 bool prim_fail=
false;
3237 if (V_buf4 ==
alpha)
3238 prim_elem_alpha= prim_elem;
3240 if (V_buf3 != V_buf4)
3242 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3243 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3244 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3246 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3247 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3248 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4, source,
3251 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3255 ASSERT (!prim_fail,
"failure in integer factorizer");
3259 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3261 if (V_buf4 ==
alpha)
3262 im_prim_elem_alpha= im_prim_elem;
3264 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
3265 im_prim_elem, source, dest);
3271 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3272 im_prim_elem, source, dest);
3273 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3274 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3275 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3277 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3278 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3279 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3288 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3291 "time for recursive call: ");
3292 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3300 sparseGCDFq (ppA(random_element,
x), ppB(random_element,
x), V_buf,
3303 "time for recursive call: ");
3304 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3321 if (!
find (
l, random_element))
3322 l.append (random_element);
3327 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3330 skeleton= G_random_element;
3345 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3357 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3358 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3360 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3362 return N(gcdcAcB*ppH);
3366 return N(gcdcAcB*ppH);
3369 newtonPoly= newtonPoly*(
x - random_element);
3370 m=
m*(
x - random_element);
3371 if (!
find (
l, random_element))
3372 l.append (random_element);
3381 if (random_element == 0 && !fail)
3383 if (!
find (
l, random_element))
3384 l.append (random_element);
3394 bool prim_fail=
false;
3397 if (V_buf4 ==
alpha)
3398 prim_elem_alpha= prim_elem;
3400 if (V_buf3 != V_buf4)
3402 m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3403 G_m=
mapDown (
m, prim_elem, im_prim_elem, V_buf4, source, dest);
3404 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3406 ppA=
mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3407 ppB=
mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3408 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
3411 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem, V_buf4,
3415 ASSERT (!prim_fail,
"failure in integer factorizer");
3419 im_prim_elem=
mapPrimElem (prim_elem, V_buf4, V_buf);
3421 if (V_buf4 ==
alpha)
3422 im_prim_elem_alpha= im_prim_elem;
3424 im_prim_elem_alpha=
mapUp (im_prim_elem_alpha, V_buf4, V_buf,
3425 prim_elem, im_prim_elem, source, dest);
3431 i.getItem()=
mapUp (
i.getItem(), V_buf4, V_buf, prim_elem,
3432 im_prim_elem, source, dest);
3433 m=
mapUp (
m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3434 G_m=
mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3435 newtonPoly=
mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3437 ppA=
mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3438 ppB=
mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3440 gcdlcAlcB=
mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3452 bool sparseFail=
false;
3453 if (
LC (skeleton).inCoeffDomain())
3456 skeleton,V_buf, sparseFail, coeffMonoms,Monoms);
3460 skeleton, V_buf, sparseFail, coeffMonoms,
3466 "time for recursive call: ");
3467 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3473 bool sparseFail=
false;
3474 if (
LC (skeleton).inCoeffDomain())
3477 skeleton,V_buf, sparseFail,coeffMonoms, Monoms);
3481 skeleton, V_buf, sparseFail, coeffMonoms,
3487 "time for recursive call: ");
3488 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3505 if (!
find (
l, random_element))
3506 l.append (random_element);
3511 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3529 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3531 "time for newton interpolation: ");
3545 DEBOUTLN (cerr,
"ppH before mapDown= " << ppH);
3546 ppH=
mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha,
alpha, u,
v);
3548 DEBOUTLN (cerr,
"ppH after mapDown= " << ppH);
3550 return N(gcdcAcB*ppH);
3555 return N(gcdcAcB*ppH);
3560 newtonPoly= newtonPoly*(
x - random_element);
3561 m=
m*(
x - random_element);
3562 if (!
find (
l, random_element))
3563 l.append (random_element);
3576 else if (
G.isZero() &&
degree (F) > 0)
return F/
Lc(F);
3581 if (F ==
G)
return F/
Lc(F);
3586 if (best_level == 0)
return B.genOne();
3594 if (
A.isUnivariate() &&
B.isUnivariate())
3603 gcdcAcB=
gcd (cA, cB);
3623 gcdlcAlcB=
gcd (lcA, lcB);
3639 CanonicalForm m, random_element, G_m, G_random_element,
H, cH, ppH, skeleton;
3646 bool inextension=
false;
3656 if (random_element == 0 && !fail)
3658 if (!
find (
l, random_element))
3659 l.append (random_element);
3663 if (!fail && !inextension)
3671 "time for recursive call: ");
3672 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3674 else if (!fail && inextension)
3682 "time for recursive call: ");
3683 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3685 else if (fail && !inextension)
3692 bool initialized=
false;
3714 "time for recursive call: ");
3715 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3717 else if (fail && inextension)
3724 bool prim_fail=
false;
3729 if (V_buf3 !=
alpha)
3732 G_m=
mapDown (
m, prim_elem, im_prim_elem,
alpha, source, dest);
3733 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha, source,
3735 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
3736 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
3737 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
3740 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3744 ASSERT (!prim_fail,
"failure in integer factorizer");
3754 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3755 im_prim_elem, source, dest);
3756 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3757 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3758 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
3760 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3761 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3762 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
3770 sparseGCDFq (ppA (random_element,
x), ppB (random_element,
x), V_buf,
3773 "time for recursive call: ");
3774 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3792 if (!
find (
l, random_element))
3793 l.append (random_element);
3798 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
3801 skeleton= G_random_element;
3817 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
3830 return N(gcdcAcB*ppH);
3834 newtonPoly= newtonPoly*(
x - random_element);
3835 m=
m*(
x - random_element);
3836 if (!
find (
l, random_element))
3837 l.append (random_element);
3850 if (random_element == 0 && !fail)
3852 if (!
find (
l, random_element))
3853 l.append (random_element);
3857 bool sparseFail=
false;
3858 if (!fail && !inextension)
3862 if (
LC (skeleton).inCoeffDomain())
3865 skeleton,
x, sparseFail, coeffMonoms,
3870 skeleton,
x, sparseFail,
3871 coeffMonoms, Monoms);
3873 "time for recursive call: ");
3874 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3876 else if (!fail && inextension)
3880 if (
LC (skeleton).inCoeffDomain())
3883 skeleton,
alpha, sparseFail, coeffMonoms,
3888 skeleton,
alpha, sparseFail, coeffMonoms,
3891 "time for recursive call: ");
3892 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3894 else if (fail && !inextension)
3901 bool initialized=
false;
3919 if (
LC (skeleton).inCoeffDomain())
3922 skeleton,
alpha, sparseFail, coeffMonoms,
3927 skeleton,
alpha, sparseFail, coeffMonoms,
3930 "time for recursive call: ");
3931 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
3933 else if (fail && inextension)
3940 bool prim_fail=
false;
3945 if (V_buf3 !=
alpha)
3948 G_m=
mapDown (
m, prim_elem, im_prim_elem,
alpha, source, dest);
3949 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
3951 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
3952 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
3953 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha,
3956 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
3960 ASSERT (!prim_fail,
"failure in integer factorizer");
3970 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
3971 im_prim_elem, source, dest);
3972 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3973 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3974 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
3976 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3977 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3978 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
3985 if (
LC (skeleton).inCoeffDomain())
3988 skeleton, V_buf, sparseFail, coeffMonoms,
3993 skeleton, V_buf, sparseFail,
3994 coeffMonoms, Monoms);
3996 "time for recursive call: ");
3997 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
4018 if (!
find (
l, random_element))
4019 l.append (random_element);
4024 (gcdlcAlcB(random_element,
x)/
uni_lcoeff (G_random_element))
4042 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
4044 "time for newton interpolation: ");
4057 return N(gcdcAcB*ppH);
4062 newtonPoly= newtonPoly*(
x - random_element);
4063 m=
m*(
x - random_element);
4064 if (!
find (
l, random_element))
4065 l.append (random_element);
4154#if defined(HAVE_NTL) || defined(HAVE_FLINT)
4169 "time for gcd mod p in modular gcd: ");
4248 "time for successful termination in modular gcd: ");
4253 "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 forComputer Algebra" by Geddes...
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 &)
gmp_float log(const gmp_float &a)
int status int void * buf
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)