My Project  debian-1:4.1.1-p2+ds-4build1
Functions
cfModGcd.h File Reference
#include "cf_assert.h"
#include "cf_factory.h"

Go to the source code of this file.

Functions

CanonicalForm modGCDFq (const CanonicalForm &F, const CanonicalForm &G, Variable &alpha, CFList &l, bool &top_level)
 
static CanonicalForm modGCDFq (const CanonicalForm &A, const CanonicalForm &B, Variable &alpha)
 GCD of A and B over $ F_{p}(\alpha ) $. More...
 
CanonicalForm modGCDFp (const CanonicalForm &F, const CanonicalForm &G, bool &top_level, CFList &l)
 
CanonicalForm modGCDFp (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
 
static CanonicalForm modGCDFp (const CanonicalForm &A, const CanonicalForm &B)
 GCD of A and B over $ F_{p} $. More...
 
static CanonicalForm modGCDFp (const CanonicalForm &A, const CanonicalForm &B, CanonicalForm &coA, CanonicalForm &coB)
 
CanonicalForm modGCDGF (const CanonicalForm &F, const CanonicalForm &G, CFList &l, bool &top_level)
 
static CanonicalForm modGCDGF (const CanonicalForm &A, const CanonicalForm &B)
 GCD of A and B over GF. More...
 
CanonicalForm sparseGCDFp (const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
 
static CanonicalForm sparseGCDFp (const CanonicalForm &A, const CanonicalForm &B)
 Zippel's sparse GCD over Fp. More...
 
CanonicalForm sparseGCDFq (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
 
static CanonicalForm sparseGCDFq (const CanonicalForm &A, const CanonicalForm &B, const Variable &alpha)
 Zippel's sparse GCD over Fq. More...
 
CFArray getMonoms (const CanonicalForm &F)
 extract monomials of F, parts in algebraic variable are considered coefficients More...
 
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 More...
 

Detailed Description

modular and sparse modular GCD algorithms over finite fields and Z.

Author
Martin Lee
Date
22.10.2009
Copyright:
(c) by The SINGULAR Team, see LICENSE file

Definition in file cfModGcd.h.

Function Documentation

◆ getMonoms()

CFArray getMonoms ( const CanonicalForm F)

extract monomials of F, parts in algebraic variable are considered coefficients

Parameters
[in]Fsome poly

Definition at line 1898 of file cfModGcd.cc.

1899 {
1900  if (F.inCoeffDomain())
1901  {
1902  CFArray result= CFArray (1);
1903  result [0]= 1;
1904  return result;
1905  }
1906  if (F.isUnivariate())
1907  {
1908  CFArray result= CFArray (size(F));
1909  int j= 0;
1910  for (CFIterator i= F; i.hasTerms(); i++, j++)
1911  result[j]= power (F.mvar(), i.exp());
1912  return result;
1913  }
1914  int numMon= size (F);
1915  CFArray result= CFArray (numMon);
1916  int j= 0;
1917  CFArray recResult;
1918  Variable x= F.mvar();
1919  CanonicalForm powX;
1920  for (CFIterator i= F; i.hasTerms(); i++)
1921  {
1922  powX= power (x, i.exp());
1923  recResult= getMonoms (i.coeff());
1924  for (int k= 0; k < recResult.size(); k++)
1925  result[j+k]= powX*recResult[k];
1926  j += recResult.size();
1927  }
1928  return result;
1929 }

◆ modGCDFp() [1/4]

static CanonicalForm modGCDFp ( const CanonicalForm A,
const CanonicalForm B 
)
inlinestatic

GCD of A and B over $ F_{p} $.

Parameters
[in]Apoly over F_p
[in]Bpoly over F_p

Definition at line 50 of file cfModGcd.h.

53 {
54  CFList list;
55  bool top_level= true;
56  return modGCDFp (A, B, top_level, list);
57 }

◆ modGCDFp() [2/4]

static CanonicalForm modGCDFp ( const CanonicalForm A,
const CanonicalForm B,
CanonicalForm coA,
CanonicalForm coB 
)
inlinestatic

Definition at line 60 of file cfModGcd.h.

62 {
63  CFList list;
64  bool top_level= true;
65  return modGCDFp (A, B, coA, coB, top_level, list);
66 }

◆ modGCDFp() [3/4]

CanonicalForm modGCDFp ( const CanonicalForm F,
const CanonicalForm G,
bool &  top_level,
CFList l 
)

Definition at line 1197 of file cfModGcd.cc.

1199 {
1200  CanonicalForm dummy1, dummy2;
1201  CanonicalForm result= modGCDFp (F, G, dummy1, dummy2, topLevel, l);
1202  return result;
1203 }

◆ modGCDFp() [4/4]

CanonicalForm modGCDFp ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm coF,
CanonicalForm coG,
bool &  topLevel,
CFList l 
)

Definition at line 1206 of file cfModGcd.cc.

1209 {
1210  CanonicalForm A= F;
1211  CanonicalForm B= G;
1212  if (F.isZero() && degree(G) > 0)
1213  {
1214  coF= 0;
1215  coG= Lc (G);
1216  return G/Lc(G);
1217  }
1218  else if (G.isZero() && degree (F) > 0)
1219  {
1220  coF= Lc (F);
1221  coG= 0;
1222  return F/Lc(F);
1223  }
1224  else if (F.isZero() && G.isZero())
1225  {
1226  coF= coG= 0;
1227  return F.genOne();
1228  }
1229  if (F.inBaseDomain() || G.inBaseDomain())
1230  {
1231  coF= F;
1232  coG= G;
1233  return F.genOne();
1234  }
1235  if (F.isUnivariate() && fdivides(F, G, coG))
1236  {
1237  coF= Lc (F);
1238  return F/Lc(F);
1239  }
1240  if (G.isUnivariate() && fdivides(G, F, coF))
1241  {
1242  coG= Lc (G);
1243  return G/Lc(G);
1244  }
1245  if (F == G)
1246  {
1247  coF= coG= Lc (F);
1248  return F/Lc(F);
1249  }
1250  CFMap M,N;
1251  int best_level= myCompress (A, B, M, N, topLevel);
1252 
1253  if (best_level == 0)
1254  {
1255  coF= F;
1256  coG= G;
1257  return B.genOne();
1258  }
1259 
1260  A= M(A);
1261  B= M(B);
1262 
1263  Variable x= Variable (1);
1264 
1265  //univariate case
1266  if (A.isUnivariate() && B.isUnivariate())
1267  {
1268  CanonicalForm result= gcd (A, B);
1269  coF= N (A/result);
1270  coG= N (B/result);
1271  return N (result);
1272  }
1273 
1274  CanonicalForm cA, cB; // content of A and B
1275  CanonicalForm ppA, ppB; // primitive part of A and B
1276  CanonicalForm gcdcAcB;
1277 
1278  cA = uni_content (A);
1279  cB = uni_content (B);
1280  gcdcAcB= gcd (cA, cB);
1281  ppA= A/cA;
1282  ppB= B/cB;
1283 
1284  CanonicalForm lcA, lcB; // leading coefficients of A and B
1285  CanonicalForm gcdlcAlcB;
1286  lcA= uni_lcoeff (ppA);
1287  lcB= uni_lcoeff (ppB);
1288 
1289  gcdlcAlcB= gcd (lcA, lcB);
1290 
1291  int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
1292  int d0;
1293 
1294  if (d == 0)
1295  {
1296  coF= N (ppA*(cA/gcdcAcB));
1297  coG= N (ppB*(cB/gcdcAcB));
1298  return N(gcdcAcB);
1299  }
1300 
1301  d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
1302 
1303  if (d0 < d)
1304  d= d0;
1305 
1306  if (d == 0)
1307  {
1308  coF= N (ppA*(cA/gcdcAcB));
1309  coG= N (ppB*(cB/gcdcAcB));
1310  return N(gcdcAcB);
1311  }
1312 
1313  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH;
1314  CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1315  coF_m, coG_m, ppCoF, ppCoG;
1316 
1317  newtonPoly= 1;
1318  m= gcdlcAlcB;
1319  H= 0;
1320  coF= 0;
1321  coG= 0;
1322  G_m= 0;
1323  Variable alpha, V_buf, cleanUp;
1324  bool fail= false;
1325  bool inextension= false;
1326  topLevel= false;
1327  CFList source, dest;
1328  int bound1= degree (ppA, 1);
1329  int bound2= degree (ppB, 1);
1330  do
1331  {
1332  if (inextension)
1333  random_element= randomElement (m*lcA*lcB, V_buf, l, fail);
1334  else
1335  random_element= FpRandomElement (m*lcA*lcB, l, fail);
1336 
1337  if (!fail && !inextension)
1338  {
1339  CFList list;
1340  TIMING_START (gcd_recursion);
1341  G_random_element=
1342  modGCDFp (ppA (random_element,x), ppB (random_element,x),
1343  coF_random_element, coG_random_element, topLevel,
1344  list);
1345  TIMING_END_AND_PRINT (gcd_recursion,
1346  "time for recursive call: ");
1347  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1348  }
1349  else if (!fail && inextension)
1350  {
1351  CFList list;
1352  TIMING_START (gcd_recursion);
1353  G_random_element=
1354  modGCDFq (ppA (random_element, x), ppB (random_element, x),
1355  coF_random_element, coG_random_element, V_buf,
1356  list, topLevel);
1357  TIMING_END_AND_PRINT (gcd_recursion,
1358  "time for recursive call: ");
1359  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1360  }
1361  else if (fail && !inextension)
1362  {
1363  source= CFList();
1364  dest= CFList();
1365  CFList list;
1367  int deg= 2;
1368  bool initialized= false;
1369  do
1370  {
1371  mipo= randomIrredpoly (deg, x);
1372  if (initialized)
1373  setMipo (alpha, mipo);
1374  else
1375  alpha= rootOf (mipo);
1376  inextension= true;
1377  initialized= true;
1378  fail= false;
1379  random_element= randomElement (m*lcA*lcB, alpha, l, fail);
1380  deg++;
1381  } while (fail);
1382  list= CFList();
1383  V_buf= alpha;
1384  cleanUp= alpha;
1385  TIMING_START (gcd_recursion);
1386  G_random_element=
1387  modGCDFq (ppA (random_element, x), ppB (random_element, x),
1388  coF_random_element, coG_random_element, alpha,
1389  list, topLevel);
1390  TIMING_END_AND_PRINT (gcd_recursion,
1391  "time for recursive call: ");
1392  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1393  }
1394  else if (fail && inextension)
1395  {
1396  source= CFList();
1397  dest= CFList();
1398 
1399  Variable V_buf3= V_buf;
1400  V_buf= chooseExtension (V_buf);
1401  bool prim_fail= false;
1402  Variable V_buf2;
1403  CanonicalForm prim_elem, im_prim_elem;
1404  prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
1405 
1406  if (V_buf3 != alpha)
1407  {
1408  m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
1409  G_m= mapDown (G_m, prim_elem, im_prim_elem, alpha, source, dest);
1410  coF_m= mapDown (coF_m, prim_elem, im_prim_elem, alpha, source, dest);
1411  coG_m= mapDown (coG_m, prim_elem, im_prim_elem, alpha, source, dest);
1412  newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha,
1413  source, dest);
1414  ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
1415  ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
1416  gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha, source,
1417  dest);
1418  lcA= mapDown (lcA, prim_elem, im_prim_elem, alpha, source, dest);
1419  lcB= mapDown (lcB, prim_elem, im_prim_elem, alpha, source, dest);
1420  for (CFListIterator i= l; i.hasItem(); i++)
1421  i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
1422  source, dest);
1423  }
1424 
1425  ASSERT (!prim_fail, "failure in integer factorizer");
1426  if (prim_fail)
1427  ; //ERROR
1428  else
1429  im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
1430 
1431  DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
1432  DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
1433 
1434  for (CFListIterator i= l; i.hasItem(); i++)
1435  i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
1436  im_prim_elem, source, dest);
1437  m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1438  G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1439  coF_m= mapUp (coF_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1440  coG_m= mapUp (coG_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1441  newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
1442  source, dest);
1443  ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1444  ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1445  gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
1446  source, dest);
1447  lcA= mapUp (lcA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1448  lcB= mapUp (lcB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1449  fail= false;
1450  random_element= randomElement (m*lcA*lcB, V_buf, l, fail );
1451  DEBOUTLN (cerr, "fail= " << fail);
1452  CFList list;
1453  TIMING_START (gcd_recursion);
1454  G_random_element=
1455  modGCDFq (ppA (random_element, x), ppB (random_element, x),
1456  coF_random_element, coG_random_element, V_buf,
1457  list, topLevel);
1458  TIMING_END_AND_PRINT (gcd_recursion,
1459  "time for recursive call: ");
1460  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1461  alpha= V_buf;
1462  }
1463 
1464  if (!G_random_element.inCoeffDomain())
1465  d0= totaldegree (G_random_element, Variable(2),
1466  Variable (G_random_element.level()));
1467  else
1468  d0= 0;
1469 
1470  if (d0 == 0)
1471  {
1472  if (inextension)
1473  prune (cleanUp);
1474  coF= N (ppA*(cA/gcdcAcB));
1475  coG= N (ppB*(cB/gcdcAcB));
1476  return N(gcdcAcB);
1477  }
1478 
1479  if (d0 > d)
1480  {
1481  if (!find (l, random_element))
1482  l.append (random_element);
1483  continue;
1484  }
1485 
1486  G_random_element= (gcdlcAlcB(random_element,x)/uni_lcoeff(G_random_element))
1487  *G_random_element;
1488 
1489  coF_random_element= (lcA(random_element,x)/uni_lcoeff(coF_random_element))
1490  *coF_random_element;
1491  coG_random_element= (lcB(random_element,x)/uni_lcoeff(coG_random_element))
1492  *coG_random_element;
1493 
1494  if (!G_random_element.inCoeffDomain())
1495  d0= totaldegree (G_random_element, Variable(2),
1496  Variable (G_random_element.level()));
1497  else
1498  d0= 0;
1499 
1500  if (d0 < d)
1501  {
1502  m= gcdlcAlcB;
1503  newtonPoly= 1;
1504  G_m= 0;
1505  d= d0;
1506  coF_m= 0;
1507  coG_m= 0;
1508  }
1509 
1510  TIMING_START (newton_interpolation);
1511  H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
1512  coF= newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,x);
1513  coG= newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,x);
1514  TIMING_END_AND_PRINT (newton_interpolation,
1515  "time for newton_interpolation: ");
1516 
1517  //termination test
1518  if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
1519  {
1520  TIMING_START (termination_test);
1521  if (gcdlcAlcB.isOne())
1522  cH= 1;
1523  else
1524  cH= uni_content (H);
1525  ppH= H/cH;
1526  ppH /= Lc (ppH);
1527  CanonicalForm lcppH= gcdlcAlcB/cH;
1528  CanonicalForm ccoF= lcppH/Lc (lcppH);
1529  CanonicalForm ccoG= lcppH/Lc (lcppH);
1530  ppCoF= coF/ccoF;
1531  ppCoG= coG/ccoG;
1532  DEBOUTLN (cerr, "ppH= " << ppH);
1533  if (((degree (ppCoF,1)+degree (ppH,1) == bound1) &&
1534  (degree (ppCoG,1)+degree (ppH,1) == bound2) &&
1535  terminationTest (ppA, ppB, ppCoF, ppCoG, ppH)) ||
1536  (fdivides (ppH, ppA, ppCoF) && fdivides (ppH, ppB, ppCoG)))
1537  {
1538  if (inextension)
1539  prune (cleanUp);
1540  coF= N ((cA/gcdcAcB)*ppCoF);
1541  coG= N ((cB/gcdcAcB)*ppCoG);
1542  TIMING_END_AND_PRINT (termination_test,
1543  "time for successful termination Fp: ");
1544  return N(gcdcAcB*ppH);
1545  }
1546  TIMING_END_AND_PRINT (termination_test,
1547  "time for unsuccessful termination Fp: ");
1548  }
1549 
1550  G_m= H;
1551  coF_m= coF;
1552  coG_m= coG;
1553  newtonPoly= newtonPoly*(x - random_element);
1554  m= m*(x - random_element);
1555  if (!find (l, random_element))
1556  l.append (random_element);
1557  } while (1);
1558 }

◆ modGCDFq() [1/2]

static CanonicalForm modGCDFq ( const CanonicalForm A,
const CanonicalForm B,
Variable alpha 
)
inlinestatic

GCD of A and B over $ F_{p}(\alpha ) $.

Parameters
[in]Apoly over F_q
[in]Bpoly over F_q
[in]alphaalgebraic variable

Definition at line 28 of file cfModGcd.h.

32 {
33  CFList list;
34  bool top_level= true;
35  return modGCDFq (A, B, alpha, list, top_level);
36 }

◆ modGCDFq() [2/2]

CanonicalForm modGCDFq ( const CanonicalForm F,
const CanonicalForm G,
Variable alpha,
CFList l,
bool &  top_level 
)

Definition at line 453 of file cfModGcd.cc.

455 {
456  CanonicalForm dummy1, dummy2;
457  CanonicalForm result= modGCDFq (F, G, dummy1, dummy2, alpha, l,
458  topLevel);
459  return result;
460 }

◆ modGCDGF() [1/2]

static CanonicalForm modGCDGF ( const CanonicalForm A,
const CanonicalForm B 
)
inlinestatic

GCD of A and B over GF.

Parameters
[in]Apoly over GF
[in]Bpoly over GF

Definition at line 74 of file cfModGcd.h.

77 {
79  "GF as base field expected");
80  CFList list;
81  bool top_level= true;
82  return modGCDGF (A, B, list, top_level);
83 }

◆ modGCDGF() [2/2]

CanonicalForm modGCDGF ( const CanonicalForm F,
const CanonicalForm G,
CFList l,
bool &  top_level 
)

Definition at line 846 of file cfModGcd.cc.

848 {
849  CanonicalForm dummy1, dummy2;
850  CanonicalForm result= modGCDGF (F, G, dummy1, dummy2, l, topLevel);
851  return result;
852 }

◆ modGCDZ()

CanonicalForm modGCDZ ( const CanonicalForm FF,
const CanonicalForm GG 
)

modular GCD over Z

Parameters
[in]FFpoly over Z
[in]GGpoly over Z

◆ sparseGCDFp() [1/2]

static CanonicalForm sparseGCDFp ( const CanonicalForm A,
const CanonicalForm B 
)
inlinestatic

Zippel's sparse GCD over Fp.

Parameters
[in]Apoly over F_p
[in]Bpoly over F_p

Definition at line 90 of file cfModGcd.h.

93 {
95  "Fp as base field expected");
96  CFList list;
97  bool topLevel= true;
98  return sparseGCDFp (A, B, topLevel, list);
99 }

◆ sparseGCDFp() [2/2]

CanonicalForm sparseGCDFp ( const CanonicalForm F,
const CanonicalForm G,
bool &  topLevel,
CFList l 
)

Definition at line 3503 of file cfModGcd.cc.

3505 {
3506  CanonicalForm A= F;
3507  CanonicalForm B= G;
3508  if (F.isZero() && degree(G) > 0) return G/Lc(G);
3509  else if (G.isZero() && degree (F) > 0) return F/Lc(F);
3510  else if (F.isZero() && G.isZero()) return F.genOne();
3511  if (F.inBaseDomain() || G.inBaseDomain()) return F.genOne();
3512  if (F.isUnivariate() && fdivides(F, G)) return F/Lc(F);
3513  if (G.isUnivariate() && fdivides(G, F)) return G/Lc(G);
3514  if (F == G) return F/Lc(F);
3515 
3516  CFMap M,N;
3517  int best_level= myCompress (A, B, M, N, topLevel);
3518 
3519  if (best_level == 0) return B.genOne();
3520 
3521  A= M(A);
3522  B= M(B);
3523 
3524  Variable x= Variable (1);
3525 
3526  //univariate case
3527  if (A.isUnivariate() && B.isUnivariate())
3528  return N (gcd (A, B));
3529 
3530  CanonicalForm cA, cB; // content of A and B
3531  CanonicalForm ppA, ppB; // primitive part of A and B
3532  CanonicalForm gcdcAcB;
3533 
3534  cA = uni_content (A);
3535  cB = uni_content (B);
3536  gcdcAcB= gcd (cA, cB);
3537  ppA= A/cA;
3538  ppB= B/cB;
3539 
3540  CanonicalForm lcA, lcB; // leading coefficients of A and B
3541  CanonicalForm gcdlcAlcB;
3542  lcA= uni_lcoeff (ppA);
3543  lcB= uni_lcoeff (ppB);
3544 
3545  if (fdivides (lcA, lcB))
3546  {
3547  if (fdivides (A, B))
3548  return F/Lc(F);
3549  }
3550  if (fdivides (lcB, lcA))
3551  {
3552  if (fdivides (B, A))
3553  return G/Lc(G);
3554  }
3555 
3556  gcdlcAlcB= gcd (lcA, lcB);
3557 
3558  int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
3559  int d0;
3560 
3561  if (d == 0)
3562  return N(gcdcAcB);
3563 
3564  d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
3565 
3566  if (d0 < d)
3567  d= d0;
3568 
3569  if (d == 0)
3570  return N(gcdcAcB);
3571 
3572  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton;
3573  CanonicalForm newtonPoly= 1;
3574  m= gcdlcAlcB;
3575  G_m= 0;
3576  H= 0;
3577  bool fail= false;
3578  topLevel= false;
3579  bool inextension= false;
3580  Variable V_buf, alpha, cleanUp;
3581  CanonicalForm prim_elem, im_prim_elem;
3582  CFList source, dest;
3583  do //first do
3584  {
3585  if (inextension)
3586  random_element= randomElement (m, V_buf, l, fail);
3587  else
3588  random_element= FpRandomElement (m, l, fail);
3589  if (random_element == 0 && !fail)
3590  {
3591  if (!find (l, random_element))
3592  l.append (random_element);
3593  continue;
3594  }
3595 
3596  if (!fail && !inextension)
3597  {
3598  CFList list;
3599  TIMING_START (gcd_recursion);
3600  G_random_element=
3601  sparseGCDFp (ppA (random_element,x), ppB (random_element,x), topLevel,
3602  list);
3603  TIMING_END_AND_PRINT (gcd_recursion,
3604  "time for recursive call: ");
3605  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3606  }
3607  else if (!fail && inextension)
3608  {
3609  CFList list;
3610  TIMING_START (gcd_recursion);
3611  G_random_element=
3612  sparseGCDFq (ppA (random_element, x), ppB (random_element, x), alpha,
3613  list, topLevel);
3614  TIMING_END_AND_PRINT (gcd_recursion,
3615  "time for recursive call: ");
3616  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3617  }
3618  else if (fail && !inextension)
3619  {
3620  source= CFList();
3621  dest= CFList();
3622  CFList list;
3624  int deg= 2;
3625  bool initialized= false;
3626  do
3627  {
3628  mipo= randomIrredpoly (deg, x);
3629  if (initialized)
3630  setMipo (alpha, mipo);
3631  else
3632  alpha= rootOf (mipo);
3633  inextension= true;
3634  fail= false;
3635  initialized= true;
3636  random_element= randomElement (m, alpha, l, fail);
3637  deg++;
3638  } while (fail);
3639  cleanUp= alpha;
3640  V_buf= alpha;
3641  list= CFList();
3642  TIMING_START (gcd_recursion);
3643  G_random_element=
3644  sparseGCDFq (ppA (random_element, x), ppB (random_element, x), alpha,
3645  list, topLevel);
3646  TIMING_END_AND_PRINT (gcd_recursion,
3647  "time for recursive call: ");
3648  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3649  }
3650  else if (fail && inextension)
3651  {
3652  source= CFList();
3653  dest= CFList();
3654 
3655  Variable V_buf3= V_buf;
3656  V_buf= chooseExtension (V_buf);
3657  bool prim_fail= false;
3658  Variable V_buf2;
3659  CanonicalForm prim_elem, im_prim_elem;
3660  prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
3661 
3662  if (V_buf3 != alpha)
3663  {
3664  m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3665  G_m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3666  newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha, source,
3667  dest);
3668  ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
3669  ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
3670  gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha, source,
3671  dest);
3672  for (CFListIterator i= l; i.hasItem(); i++)
3673  i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
3674  source, dest);
3675  }
3676 
3677  ASSERT (!prim_fail, "failure in integer factorizer");
3678  if (prim_fail)
3679  ; //ERROR
3680  else
3681  im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
3682 
3683  DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
3684  DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
3685 
3686  for (CFListIterator i= l; i.hasItem(); i++)
3687  i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
3688  im_prim_elem, source, dest);
3689  m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3690  G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3691  newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
3692  source, dest);
3693  ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3694  ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3695  gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
3696  source, dest);
3697  fail= false;
3698  random_element= randomElement (m, V_buf, l, fail );
3699  DEBOUTLN (cerr, "fail= " << fail);
3700  CFList list;
3701  TIMING_START (gcd_recursion);
3702  G_random_element=
3703  sparseGCDFq (ppA (random_element, x), ppB (random_element, x), V_buf,
3704  list, topLevel);
3705  TIMING_END_AND_PRINT (gcd_recursion,
3706  "time for recursive call: ");
3707  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3708  alpha= V_buf;
3709  }
3710 
3711  if (!G_random_element.inCoeffDomain())
3712  d0= totaldegree (G_random_element, Variable(2),
3713  Variable (G_random_element.level()));
3714  else
3715  d0= 0;
3716 
3717  if (d0 == 0)
3718  {
3719  if (inextension)
3720  prune (cleanUp);
3721  return N(gcdcAcB);
3722  }
3723  if (d0 > d)
3724  {
3725  if (!find (l, random_element))
3726  l.append (random_element);
3727  continue;
3728  }
3729 
3730  G_random_element=
3731  (gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
3732  * G_random_element;
3733 
3734  skeleton= G_random_element;
3735 
3736  if (!G_random_element.inCoeffDomain())
3737  d0= totaldegree (G_random_element, Variable(2),
3738  Variable (G_random_element.level()));
3739  else
3740  d0= 0;
3741 
3742  if (d0 < d)
3743  {
3744  m= gcdlcAlcB;
3745  newtonPoly= 1;
3746  G_m= 0;
3747  d= d0;
3748  }
3749 
3750  H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
3751 
3752  if (uni_lcoeff (H) == gcdlcAlcB)
3753  {
3754  cH= uni_content (H);
3755  ppH= H/cH;
3756  ppH /= Lc (ppH);
3757  DEBOUTLN (cerr, "ppH= " << ppH);
3758 
3759  if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3760  {
3761  if (inextension)
3762  prune (cleanUp);
3763  return N(gcdcAcB*ppH);
3764  }
3765  }
3766  G_m= H;
3767  newtonPoly= newtonPoly*(x - random_element);
3768  m= m*(x - random_element);
3769  if (!find (l, random_element))
3770  l.append (random_element);
3771 
3772  if ((getCharacteristic() > 3 && size (skeleton) < 200))
3773  {
3774  CFArray Monoms;
3775  CFArray* coeffMonoms;
3776 
3777  do //second do
3778  {
3779  if (inextension)
3780  random_element= randomElement (m, alpha, l, fail);
3781  else
3782  random_element= FpRandomElement (m, l, fail);
3783  if (random_element == 0 && !fail)
3784  {
3785  if (!find (l, random_element))
3786  l.append (random_element);
3787  continue;
3788  }
3789 
3790  bool sparseFail= false;
3791  if (!fail && !inextension)
3792  {
3793  CFList list;
3794  TIMING_START (gcd_recursion);
3795  if (LC (skeleton).inCoeffDomain())
3796  G_random_element=
3797  monicSparseInterpol(ppA(random_element, x), ppB (random_element, x),
3798  skeleton, x, sparseFail, coeffMonoms,
3799  Monoms);
3800  else
3801  G_random_element=
3802  nonMonicSparseInterpol(ppA(random_element,x), ppB(random_element,x),
3803  skeleton, x, sparseFail,
3804  coeffMonoms, Monoms);
3805  TIMING_END_AND_PRINT (gcd_recursion,
3806  "time for recursive call: ");
3807  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3808  }
3809  else if (!fail && inextension)
3810  {
3811  CFList list;
3812  TIMING_START (gcd_recursion);
3813  if (LC (skeleton).inCoeffDomain())
3814  G_random_element=
3815  monicSparseInterpol(ppA (random_element,x), ppB (random_element, x),
3816  skeleton, alpha, sparseFail, coeffMonoms,
3817  Monoms);
3818  else
3819  G_random_element=
3820  nonMonicSparseInterpol(ppA(random_element,x), ppB(random_element,x),
3821  skeleton, alpha, sparseFail, coeffMonoms,
3822  Monoms);
3823  TIMING_END_AND_PRINT (gcd_recursion,
3824  "time for recursive call: ");
3825  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3826  }
3827  else if (fail && !inextension)
3828  {
3829  source= CFList();
3830  dest= CFList();
3831  CFList list;
3833  int deg= 2;
3834  bool initialized= false;
3835  do
3836  {
3837  mipo= randomIrredpoly (deg, x);
3838  if (initialized)
3839  setMipo (alpha, mipo);
3840  else
3841  alpha= rootOf (mipo);
3842  inextension= true;
3843  fail= false;
3844  initialized= true;
3845  random_element= randomElement (m, alpha, l, fail);
3846  deg++;
3847  } while (fail);
3848  cleanUp= alpha;
3849  V_buf= alpha;
3850  list= CFList();
3851  TIMING_START (gcd_recursion);
3852  if (LC (skeleton).inCoeffDomain())
3853  G_random_element=
3854  monicSparseInterpol (ppA (random_element,x), ppB (random_element,x),
3855  skeleton, alpha, sparseFail, coeffMonoms,
3856  Monoms);
3857  else
3858  G_random_element=
3859  nonMonicSparseInterpol(ppA(random_element,x), ppB(random_element,x),
3860  skeleton, alpha, sparseFail, coeffMonoms,
3861  Monoms);
3862  TIMING_END_AND_PRINT (gcd_recursion,
3863  "time for recursive call: ");
3864  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3865  }
3866  else if (fail && inextension)
3867  {
3868  source= CFList();
3869  dest= CFList();
3870 
3871  Variable V_buf3= V_buf;
3872  V_buf= chooseExtension (V_buf);
3873  bool prim_fail= false;
3874  Variable V_buf2;
3875  CanonicalForm prim_elem, im_prim_elem;
3876  prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
3877 
3878  if (V_buf3 != alpha)
3879  {
3880  m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3881  G_m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
3882  newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha,
3883  source, dest);
3884  ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
3885  ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
3886  gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha,
3887  source, dest);
3888  for (CFListIterator i= l; i.hasItem(); i++)
3889  i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
3890  source, dest);
3891  }
3892 
3893  ASSERT (!prim_fail, "failure in integer factorizer");
3894  if (prim_fail)
3895  ; //ERROR
3896  else
3897  im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
3898 
3899  DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
3900  DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
3901 
3902  for (CFListIterator i= l; i.hasItem(); i++)
3903  i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
3904  im_prim_elem, source, dest);
3905  m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3906  G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3907  newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
3908  source, dest);
3909  ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3910  ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
3911  gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
3912  source, dest);
3913  fail= false;
3914  random_element= randomElement (m, V_buf, l, fail );
3915  DEBOUTLN (cerr, "fail= " << fail);
3916  CFList list;
3917  TIMING_START (gcd_recursion);
3918  if (LC (skeleton).inCoeffDomain())
3919  G_random_element=
3920  monicSparseInterpol (ppA (random_element, x), ppB (random_element, x),
3921  skeleton, V_buf, sparseFail, coeffMonoms,
3922  Monoms);
3923  else
3924  G_random_element=
3925  nonMonicSparseInterpol (ppA(random_element,x), ppB(random_element,x),
3926  skeleton, V_buf, sparseFail,
3927  coeffMonoms, Monoms);
3928  TIMING_END_AND_PRINT (gcd_recursion,
3929  "time for recursive call: ");
3930  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3931  alpha= V_buf;
3932  }
3933 
3934  if (sparseFail)
3935  break;
3936 
3937  if (!G_random_element.inCoeffDomain())
3938  d0= totaldegree (G_random_element, Variable(2),
3939  Variable (G_random_element.level()));
3940  else
3941  d0= 0;
3942 
3943  if (d0 == 0)
3944  {
3945  if (inextension)
3946  prune (cleanUp);
3947  return N(gcdcAcB);
3948  }
3949  if (d0 > d)
3950  {
3951  if (!find (l, random_element))
3952  l.append (random_element);
3953  continue;
3954  }
3955 
3956  G_random_element=
3957  (gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
3958  * G_random_element;
3959 
3960  if (!G_random_element.inCoeffDomain())
3961  d0= totaldegree (G_random_element, Variable(2),
3962  Variable (G_random_element.level()));
3963  else
3964  d0= 0;
3965 
3966  if (d0 < d)
3967  {
3968  m= gcdlcAlcB;
3969  newtonPoly= 1;
3970  G_m= 0;
3971  d= d0;
3972  }
3973 
3974  TIMING_START (newton_interpolation);
3975  H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
3976  TIMING_END_AND_PRINT (newton_interpolation,
3977  "time for newton interpolation: ");
3978 
3979  //termination test
3980  if (uni_lcoeff (H) == gcdlcAlcB)
3981  {
3982  cH= uni_content (H);
3983  ppH= H/cH;
3984  ppH /= Lc (ppH);
3985  DEBOUTLN (cerr, "ppH= " << ppH);
3986  if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3987  {
3988  if (inextension)
3989  prune (cleanUp);
3990  return N(gcdcAcB*ppH);
3991  }
3992  }
3993 
3994  G_m= H;
3995  newtonPoly= newtonPoly*(x - random_element);
3996  m= m*(x - random_element);
3997  if (!find (l, random_element))
3998  l.append (random_element);
3999 
4000  } while (1); //end of second do
4001  }
4002  else
4003  {
4004  if (inextension)
4005  prune (cleanUp);
4006  return N(gcdcAcB*modGCDFp (ppA, ppB));
4007  }
4008  } while (1); //end of first do
4009 }

◆ sparseGCDFq() [1/2]

static CanonicalForm sparseGCDFq ( const CanonicalForm A,
const CanonicalForm B,
const Variable alpha 
)
inlinestatic

Zippel's sparse GCD over Fq.

Parameters
[in]Apoly over F_q
[in]Bpoly over F_q
[in]alphaalgebraic variable

Definition at line 108 of file cfModGcd.h.

112 {
113  CFList list;
114  bool topLevel= true;
115  return sparseGCDFq (A, B, alpha, list, topLevel);
116 }

◆ sparseGCDFq() [2/2]

CanonicalForm sparseGCDFq ( const CanonicalForm F,
const CanonicalForm G,
const Variable alpha,
CFList l,
bool &  topLevel 
)

Definition at line 3071 of file cfModGcd.cc.

3073 {
3074  CanonicalForm A= F;
3075  CanonicalForm B= G;
3076  if (F.isZero() && degree(G) > 0) return G/Lc(G);
3077  else if (G.isZero() && degree (F) > 0) return F/Lc(F);
3078  else if (F.isZero() && G.isZero()) return F.genOne();
3079  if (F.inBaseDomain() || G.inBaseDomain()) return F.genOne();
3080  if (F.isUnivariate() && fdivides(F, G)) return F/Lc(F);
3081  if (G.isUnivariate() && fdivides(G, F)) return G/Lc(G);
3082  if (F == G) return F/Lc(F);
3083 
3084  CFMap M,N;
3085  int best_level= myCompress (A, B, M, N, topLevel);
3086 
3087  if (best_level == 0) return B.genOne();
3088 
3089  A= M(A);
3090  B= M(B);
3091 
3092  Variable x= Variable (1);
3093 
3094  //univariate case
3095  if (A.isUnivariate() && B.isUnivariate())
3096  return N (gcd (A, B));
3097 
3098  CanonicalForm cA, cB; // content of A and B
3099  CanonicalForm ppA, ppB; // primitive part of A and B
3100  CanonicalForm gcdcAcB;
3101 
3102  cA = uni_content (A);
3103  cB = uni_content (B);
3104  gcdcAcB= gcd (cA, cB);
3105  ppA= A/cA;
3106  ppB= B/cB;
3107 
3108  CanonicalForm lcA, lcB; // leading coefficients of A and B
3109  CanonicalForm gcdlcAlcB;
3110  lcA= uni_lcoeff (ppA);
3111  lcB= uni_lcoeff (ppB);
3112 
3113  if (fdivides (lcA, lcB))
3114  {
3115  if (fdivides (A, B))
3116  return F/Lc(F);
3117  }
3118  if (fdivides (lcB, lcA))
3119  {
3120  if (fdivides (B, A))
3121  return G/Lc(G);
3122  }
3123 
3124  gcdlcAlcB= gcd (lcA, lcB);
3125 
3126  int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
3127  int d0;
3128 
3129  if (d == 0)
3130  return N(gcdcAcB);
3131  d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
3132 
3133  if (d0 < d)
3134  d= d0;
3135 
3136  if (d == 0)
3137  return N(gcdcAcB);
3138 
3139  CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH, skeleton;
3140  CanonicalForm newtonPoly= 1;
3141  m= gcdlcAlcB;
3142  G_m= 0;
3143  H= 0;
3144  bool fail= false;
3145  topLevel= false;
3146  bool inextension= false;
3147  Variable V_buf= alpha, V_buf4= alpha;
3148  CanonicalForm prim_elem, im_prim_elem;
3149  CanonicalForm prim_elem_alpha, im_prim_elem_alpha;
3150  CFList source, dest;
3151  do // first do
3152  {
3153  random_element= randomElement (m, V_buf, l, fail);
3154  if (random_element == 0 && !fail)
3155  {
3156  if (!find (l, random_element))
3157  l.append (random_element);
3158  continue;
3159  }
3160  if (fail)
3161  {
3162  source= CFList();
3163  dest= CFList();
3164 
3165  Variable V_buf3= V_buf;
3166  V_buf= chooseExtension (V_buf);
3167  bool prim_fail= false;
3168  Variable V_buf2;
3169  prim_elem= primitiveElement (V_buf4, V_buf2, prim_fail);
3170  if (V_buf4 == alpha)
3171  prim_elem_alpha= prim_elem;
3172 
3173  if (V_buf3 != V_buf4)
3174  {
3175  m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
3176  G_m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
3177  newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3178  source, dest);
3179  ppA= mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3180  ppB= mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3181  gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4, source,
3182  dest);
3183  for (CFListIterator i= l; i.hasItem(); i++)
3184  i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, V_buf4,
3185  source, dest);
3186  }
3187 
3188  ASSERT (!prim_fail, "failure in integer factorizer");
3189  if (prim_fail)
3190  ; //ERROR
3191  else
3192  im_prim_elem= mapPrimElem (prim_elem, V_buf4, V_buf);
3193 
3194  if (V_buf4 == alpha)
3195  im_prim_elem_alpha= im_prim_elem;
3196  else
3197  im_prim_elem_alpha= mapUp (im_prim_elem_alpha, V_buf4, V_buf, prim_elem,
3198  im_prim_elem, source, dest);
3199 
3200  DEBOUTLN (cerr, "getMipo (V_buf4)= " << getMipo (V_buf4));
3201  DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2));
3202  inextension= true;
3203  for (CFListIterator i= l; i.hasItem(); i++)
3204  i.getItem()= mapUp (i.getItem(), V_buf4, V_buf, prim_elem,
3205  im_prim_elem, source, dest);
3206  m= mapUp (m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3207  G_m= mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3208  newtonPoly= mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3209  source, dest);
3210  ppA= mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3211  ppB= mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3212  gcdlcAlcB= mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3213  source, dest);
3214 
3215  fail= false;
3216  random_element= randomElement (m, V_buf, l, fail );
3217  DEBOUTLN (cerr, "fail= " << fail);
3218  CFList list;
3219  TIMING_START (gcd_recursion);
3220  G_random_element=
3221  sparseGCDFq (ppA (random_element, x), ppB (random_element, x), V_buf,
3222  list, topLevel);
3223  TIMING_END_AND_PRINT (gcd_recursion,
3224  "time for recursive call: ");
3225  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3226  V_buf4= V_buf;
3227  }
3228  else
3229  {
3230  CFList list;
3231  TIMING_START (gcd_recursion);
3232  G_random_element=
3233  sparseGCDFq (ppA(random_element, x), ppB(random_element, x), V_buf,
3234  list, topLevel);
3235  TIMING_END_AND_PRINT (gcd_recursion,
3236  "time for recursive call: ");
3237  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3238  }
3239 
3240  if (!G_random_element.inCoeffDomain())
3241  d0= totaldegree (G_random_element, Variable(2),
3242  Variable (G_random_element.level()));
3243  else
3244  d0= 0;
3245 
3246  if (d0 == 0)
3247  {
3248  if (inextension)
3249  prune1 (alpha);
3250  return N(gcdcAcB);
3251  }
3252  if (d0 > d)
3253  {
3254  if (!find (l, random_element))
3255  l.append (random_element);
3256  continue;
3257  }
3258 
3259  G_random_element=
3260  (gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
3261  * G_random_element;
3262 
3263  skeleton= G_random_element;
3264  if (!G_random_element.inCoeffDomain())
3265  d0= totaldegree (G_random_element, Variable(2),
3266  Variable (G_random_element.level()));
3267  else
3268  d0= 0;
3269 
3270  if (d0 < d)
3271  {
3272  m= gcdlcAlcB;
3273  newtonPoly= 1;
3274  G_m= 0;
3275  d= d0;
3276  }
3277 
3278  H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
3279  if (uni_lcoeff (H) == gcdlcAlcB)
3280  {
3281  cH= uni_content (H);
3282  ppH= H/cH;
3283  if (inextension)
3284  {
3285  CFList u, v;
3286  //maybe it's better to test if ppH is an element of F(\alpha) before
3287  //mapping down
3288  if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3289  {
3290  DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
3291  ppH= mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
3292  ppH /= Lc(ppH);
3293  DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
3294  prune1 (alpha);
3295  return N(gcdcAcB*ppH);
3296  }
3297  }
3298  else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3299  return N(gcdcAcB*ppH);
3300  }
3301  G_m= H;
3302  newtonPoly= newtonPoly*(x - random_element);
3303  m= m*(x - random_element);
3304  if (!find (l, random_element))
3305  l.append (random_element);
3306 
3307  if (getCharacteristic () > 3 && size (skeleton) < 100)
3308  {
3309  CFArray Monoms;
3310  CFArray *coeffMonoms;
3311  do //second do
3312  {
3313  random_element= randomElement (m, V_buf, l, fail);
3314  if (random_element == 0 && !fail)
3315  {
3316  if (!find (l, random_element))
3317  l.append (random_element);
3318  continue;
3319  }
3320  if (fail)
3321  {
3322  source= CFList();
3323  dest= CFList();
3324 
3325  Variable V_buf3= V_buf;
3326  V_buf= chooseExtension (V_buf);
3327  bool prim_fail= false;
3328  Variable V_buf2;
3329  prim_elem= primitiveElement (V_buf4, V_buf2, prim_fail);
3330  if (V_buf4 == alpha)
3331  prim_elem_alpha= prim_elem;
3332 
3333  if (V_buf3 != V_buf4)
3334  {
3335  m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
3336  G_m= mapDown (m, prim_elem, im_prim_elem, V_buf4, source, dest);
3337  newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, V_buf4,
3338  source, dest);
3339  ppA= mapDown (ppA, prim_elem, im_prim_elem, V_buf4, source, dest);
3340  ppB= mapDown (ppB, prim_elem, im_prim_elem, V_buf4, source, dest);
3341  gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, V_buf4,
3342  source, dest);
3343  for (CFListIterator i= l; i.hasItem(); i++)
3344  i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, V_buf4,
3345  source, dest);
3346  }
3347 
3348  ASSERT (!prim_fail, "failure in integer factorizer");
3349  if (prim_fail)
3350  ; //ERROR
3351  else
3352  im_prim_elem= mapPrimElem (prim_elem, V_buf4, V_buf);
3353 
3354  if (V_buf4 == alpha)
3355  im_prim_elem_alpha= im_prim_elem;
3356  else
3357  im_prim_elem_alpha= mapUp (im_prim_elem_alpha, V_buf4, V_buf,
3358  prim_elem, im_prim_elem, source, dest);
3359 
3360  DEBOUTLN (cerr, "getMipo (V_buf4)= " << getMipo (V_buf4));
3361  DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2));
3362  inextension= true;
3363  for (CFListIterator i= l; i.hasItem(); i++)
3364  i.getItem()= mapUp (i.getItem(), V_buf4, V_buf, prim_elem,
3365  im_prim_elem, source, dest);
3366  m= mapUp (m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3367  G_m= mapUp (G_m, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3368  newtonPoly= mapUp (newtonPoly, V_buf4, V_buf, prim_elem, im_prim_elem,
3369  source, dest);
3370  ppA= mapUp (ppA, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3371  ppB= mapUp (ppB, V_buf4, V_buf, prim_elem, im_prim_elem, source, dest);
3372 
3373  gcdlcAlcB= mapUp (gcdlcAlcB, V_buf4, V_buf, prim_elem, im_prim_elem,
3374  source, dest);
3375 
3376  fail= false;
3377  random_element= randomElement (m, V_buf, l, fail);
3378  DEBOUTLN (cerr, "fail= " << fail);
3379  CFList list;
3380  TIMING_START (gcd_recursion);
3381 
3382  V_buf4= V_buf;
3383 
3384  //sparseInterpolation
3385  bool sparseFail= false;
3386  if (LC (skeleton).inCoeffDomain())
3387  G_random_element=
3388  monicSparseInterpol (ppA (random_element, x), ppB(random_element,x),
3389  skeleton,V_buf, sparseFail, coeffMonoms,Monoms);
3390  else
3391  G_random_element=
3392  nonMonicSparseInterpol (ppA(random_element,x),ppB(random_element,x),
3393  skeleton, V_buf, sparseFail, coeffMonoms,
3394  Monoms);
3395  if (sparseFail)
3396  break;
3397 
3398  TIMING_END_AND_PRINT (gcd_recursion,
3399  "time for recursive call: ");
3400  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3401  }
3402  else
3403  {
3404  CFList list;
3405  TIMING_START (gcd_recursion);
3406  bool sparseFail= false;
3407  if (LC (skeleton).inCoeffDomain())
3408  G_random_element=
3409  monicSparseInterpol (ppA (random_element, x),ppB(random_element, x),
3410  skeleton,V_buf, sparseFail,coeffMonoms, Monoms);
3411  else
3412  G_random_element=
3413  nonMonicSparseInterpol (ppA(random_element,x),ppB(random_element,x),
3414  skeleton, V_buf, sparseFail, coeffMonoms,
3415  Monoms);
3416  if (sparseFail)
3417  break;
3418 
3419  TIMING_END_AND_PRINT (gcd_recursion,
3420  "time for recursive call: ");
3421  DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3422  }
3423 
3424  if (!G_random_element.inCoeffDomain())
3425  d0= totaldegree (G_random_element, Variable(2),
3426  Variable (G_random_element.level()));
3427  else
3428  d0= 0;
3429 
3430  if (d0 == 0)
3431  {
3432  if (inextension)
3433  prune1 (alpha);
3434  return N(gcdcAcB);
3435  }
3436  if (d0 > d)
3437  {
3438  if (!find (l, random_element))
3439  l.append (random_element);
3440  continue;
3441  }
3442 
3443  G_random_element=
3444  (gcdlcAlcB(random_element, x)/uni_lcoeff (G_random_element))
3445  * G_random_element;
3446 
3447  if (!G_random_element.inCoeffDomain())
3448  d0= totaldegree (G_random_element, Variable(2),
3449  Variable (G_random_element.level()));
3450  else
3451  d0= 0;
3452 
3453  if (d0 < d)
3454  {
3455  m= gcdlcAlcB;
3456  newtonPoly= 1;
3457  G_m= 0;
3458  d= d0;
3459  }
3460 
3461  TIMING_START (newton_interpolation);
3462  H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
3463  TIMING_END_AND_PRINT (newton_interpolation,
3464  "time for newton interpolation: ");
3465 
3466  //termination test
3467  if (uni_lcoeff (H) == gcdlcAlcB)
3468  {
3469  cH= uni_content (H);
3470  ppH= H/cH;
3471  if (inextension)
3472  {
3473  CFList u, v;
3474  //maybe it's better to test if ppH is an element of F(\alpha) before
3475  //mapping down
3476  if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3477  {
3478  DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
3479  ppH= mapDown (ppH, prim_elem_alpha, im_prim_elem_alpha, alpha, u, v);
3480  ppH /= Lc(ppH);
3481  DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
3482  prune1 (alpha);
3483  return N(gcdcAcB*ppH);
3484  }
3485  }
3486  else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3487  {
3488  return N(gcdcAcB*ppH);
3489  }
3490  }
3491 
3492  G_m= H;
3493  newtonPoly= newtonPoly*(x - random_element);
3494  m= m*(x - random_element);
3495  if (!find (l, random_element))
3496  l.append (random_element);
3497 
3498  } while (1);
3499  }
3500  } while (1);
3501 }

◆ terminationTest()

bool terminationTest ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm coF,
const CanonicalForm coG,
const CanonicalForm cand 
)
modGCDFq
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, Variable &alpha, CFList &l, bool &top_level)
Definition: cfModGcd.cc:453
newtonInterp
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...
Definition: cfModGcd.cc:366
j
int j
Definition: facHensel.cc:105
k
int k
Definition: cfEzgcd.cc:92
terminationTest
bool terminationTest(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &coF, const CanonicalForm &coG, const CanonicalForm &cand)
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
uni_content
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
Definition: cfModGcd.cc:283
result
return result
Definition: facAbsBiFact.cc:76
setMipo
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
i
int i
Definition: cfModGcd.cc:4019
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
FpRandomElement
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
Definition: cfModGcd.cc:1159
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
CFMap
class CFMap
Definition: cf_map.h:84
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
randomElement
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...
Definition: cfModGcd.cc:381
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
randomIrredpoly
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL
Definition: cf_irred.cc:42
primitiveElement
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
Definition: cf_map_ext.cc:310
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm
factory's main class
Definition: canonicalform.h:77
getMonoms
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition: cfModGcd.cc:1898
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CanonicalForm::genOne
CanonicalForm genOne() const
Definition: canonicalform.cc:1822
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
Array
Definition: ftmpl_array.h:17
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
M
#define M
Definition: sirandom.c:24
TIMING_START
TIMING_START(fac_alg_resultant)
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
coF
const CanonicalForm const CanonicalForm & coF
Definition: cfModGcd.cc:66
modGCDFq
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....
Definition: cfModGcd.cc:467
uni_lcoeff
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.
Definition: cfModGcd.cc:341
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
prune
void prune(Variable &alpha)
Definition: variable.cc:261
coG
const CanonicalForm const CanonicalForm const CanonicalForm & coG
Definition: cfModGcd.cc:66
FiniteFieldDomain
#define FiniteFieldDomain
Definition: cf_defs.h:23
monicSparseInterpol
CanonicalForm monicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
Definition: cfModGcd.cc:2140
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
sparseGCDFq
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
Definition: cfModGcd.cc:3071
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &top_level, CFList &l)
Definition: cfModGcd.cc:1197
Variable
factory's class for variables
Definition: factory.h:117
nonMonicSparseInterpol
CanonicalForm nonMonicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
Definition: cfModGcd.cc:2424
B
b *CanonicalForm B
Definition: facBivar.cc:52
topLevel
const CanonicalForm CFMap CFMap bool topLevel
Definition: cfGcdAlgExt.cc:57
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
m
int m
Definition: cfEzgcd.cc:121
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
modGCDGF
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CFList &l, bool &top_level)
Definition: cfModGcd.cc:846
l
int l
Definition: cfEzgcd.cc:93
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List< CanonicalForm >
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3503
H
CanonicalForm H
Definition: facAbsFact.cc:64
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
myCompress
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
Definition: cfModGcd.cc:93
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
A
#define A
Definition: sirandom.c:23
prune1
void prune1(const Variable &alpha)
Definition: variable.cc:289
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
G
const CanonicalForm & G
Definition: cfModGcd.cc:66
sparseGCDFq
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
Definition: cfModGcd.cc:3071
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
modGCDGF
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...
Definition: cfModGcd.cc:860
chooseExtension
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:422
mapDown
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 ,...
Definition: cf_map_ext.cc:90
ListIterator
Definition: ftmpl_list.h:17
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3503