My Project
Loading...
Searching...
No Matches
Functions
cfModGcd.h File Reference

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

#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 ) $.
 
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} $.
 
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.
 
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.
 
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.
 
CFArray getMonoms (const CanonicalForm &F)
 extract monomials of F, parts in algebraic variable are considered coefficients
 
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
 

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 1956 of file cfModGcd.cc.

1957{
1958 if (F.inCoeffDomain())
1959 {
1960 CFArray result= CFArray (1);
1961 result [0]= 1;
1962 return result;
1963 }
1964 if (F.isUnivariate())
1965 {
1966 CFArray result= CFArray (size(F));
1967 int j= 0;
1968 for (CFIterator i= F; i.hasTerms(); i++, j++)
1969 result[j]= power (F.mvar(), i.exp());
1970 return result;
1971 }
1972 int numMon= size (F);
1973 CFArray result= CFArray (numMon);
1974 int j= 0;
1975 CFArray recResult;
1976 Variable x= F.mvar();
1977 CanonicalForm powX;
1978 for (CFIterator i= F; i.hasTerms(); i++)
1979 {
1980 powX= power (x, i.exp());
1981 recResult= getMonoms (i.coeff());
1982 for (int k= 0; k < recResult.size(); k++)
1983 result[j+k]= powX*recResult[k];
1984 j += recResult.size();
1985 }
1986 return result;
1987}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:99
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition: cfModGcd.cc:1956
Variable x
Definition: cfModGcd.cc:4081
int i
Definition: cfModGcd.cc:4077
int size() const
Definition: ftmpl_array.cc:92
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
bool isUnivariate() const
factory's class for variables
Definition: factory.h:127
return result
Definition: facAbsBiFact.cc:75
int j
Definition: facHensel.cc:110

◆ 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}
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &top_level, CFList &l)
Definition: cfModGcd.cc:1212
b *CanonicalForm B
Definition: facBivar.cc:52
#define A
Definition: sirandom.c:24

◆ 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 1212 of file cfModGcd.cc.

1214{
1215 CanonicalForm dummy1, dummy2;
1216 CanonicalForm result= modGCDFp (F, G, dummy1, dummy2, topLevel, l);
1217 return result;
1218}
int l
Definition: cfEzgcd.cc:100
const CanonicalForm CFMap CFMap bool topLevel
Definition: cfGcdAlgExt.cc:57
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1223
const CanonicalForm & G
Definition: cfModGcd.cc:66

◆ modGCDFp() [4/4]

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

Definition at line 1223 of file cfModGcd.cc.

1226{
1227 CanonicalForm A= F;
1228 CanonicalForm B= G;
1229 if (F.isZero() && degree(G) > 0)
1230 {
1231 coF= 0;
1232 coG= Lc (G);
1233 return G/Lc(G);
1234 }
1235 else if (G.isZero() && degree (F) > 0)
1236 {
1237 coF= Lc (F);
1238 coG= 0;
1239 return F/Lc(F);
1240 }
1241 else if (F.isZero() && G.isZero())
1242 {
1243 coF= coG= 0;
1244 return F.genOne();
1245 }
1246 if (F.inBaseDomain() || G.inBaseDomain())
1247 {
1248 coF= F;
1249 coG= G;
1250 return F.genOne();
1251 }
1252 if (F.isUnivariate() && fdivides(F, G, coG))
1253 {
1254 coF= Lc (F);
1255 return F/Lc(F);
1256 }
1257 if (G.isUnivariate() && fdivides(G, F, coF))
1258 {
1259 coG= Lc (G);
1260 return G/Lc(G);
1261 }
1262 if (F == G)
1263 {
1264 coF= coG= Lc (F);
1265 return F/Lc(F);
1266 }
1267 CFMap M,N;
1268 int best_level= myCompress (A, B, M, N, topLevel);
1269
1270 if (best_level == 0)
1271 {
1272 coF= F;
1273 coG= G;
1274 return B.genOne();
1275 }
1276
1277 A= M(A);
1278 B= M(B);
1279
1280 Variable x= Variable (1);
1281
1282 //univariate case
1283 if (A.isUnivariate() && B.isUnivariate())
1284 {
1286 coF= N (A/result);
1287 coG= N (B/result);
1288 return N (result);
1289 }
1290
1291 CanonicalForm cA, cB; // content of A and B
1292 CanonicalForm ppA, ppB; // primitive part of A and B
1293 CanonicalForm gcdcAcB;
1294
1295 cA = uni_content (A);
1296 cB = uni_content (B);
1297 gcdcAcB= gcd (cA, cB);
1298 ppA= A/cA;
1299 ppB= B/cB;
1300
1301 CanonicalForm lcA, lcB; // leading coefficients of A and B
1302 CanonicalForm gcdlcAlcB;
1303 lcA= uni_lcoeff (ppA);
1304 lcB= uni_lcoeff (ppB);
1305
1306 gcdlcAlcB= gcd (lcA, lcB);
1307
1308 int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
1309 int d0;
1310
1311 if (d == 0)
1312 {
1313 coF= N (ppA*(cA/gcdcAcB));
1314 coG= N (ppB*(cB/gcdcAcB));
1315 return N(gcdcAcB);
1316 }
1317
1318 d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
1319
1320 if (d0 < d)
1321 d= d0;
1322
1323 if (d == 0)
1324 {
1325 coF= N (ppA*(cA/gcdcAcB));
1326 coG= N (ppB*(cB/gcdcAcB));
1327 return N(gcdcAcB);
1328 }
1329
1330 CanonicalForm m, random_element, G_m, G_random_element, H, cH, ppH;
1331 CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1332 coF_m, coG_m, ppCoF, ppCoG;
1333
1334 newtonPoly= 1;
1335 m= gcdlcAlcB;
1336 H= 0;
1337 coF= 0;
1338 coG= 0;
1339 G_m= 0;
1340 Variable alpha, V_buf, cleanUp;
1341 bool fail= false;
1342 bool inextension= false;
1343 topLevel= false;
1344 CFList source, dest;
1345 int bound1= degree (ppA, 1);
1346 int bound2= degree (ppB, 1);
1347 do
1348 {
1349 if (inextension)
1350 random_element= randomElement (m*lcA*lcB, V_buf, l, fail);
1351 else
1352 random_element= FpRandomElement (m*lcA*lcB, l, fail);
1353
1354 if (!fail && !inextension)
1355 {
1356 CFList list;
1357 TIMING_START (gcd_recursion);
1358 G_random_element=
1359 modGCDFp (ppA (random_element,x), ppB (random_element,x),
1360 coF_random_element, coG_random_element, topLevel,
1361 list);
1362 TIMING_END_AND_PRINT (gcd_recursion,
1363 "time for recursive call: ");
1364 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1365 }
1366 else if (!fail && inextension)
1367 {
1368 CFList list;
1369 TIMING_START (gcd_recursion);
1370 G_random_element=
1371 modGCDFq (ppA (random_element, x), ppB (random_element, x),
1372 coF_random_element, coG_random_element, V_buf,
1373 list, topLevel);
1374 TIMING_END_AND_PRINT (gcd_recursion,
1375 "time for recursive call: ");
1376 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1377 }
1378 else if (fail && !inextension)
1379 {
1380 source= CFList();
1381 dest= CFList();
1382 CFList list;
1384 int deg= 2;
1385 bool initialized= false;
1386 do
1387 {
1388 mipo= randomIrredpoly (deg, x);
1389 if (initialized)
1390 setMipo (alpha, mipo);
1391 else
1392 alpha= rootOf (mipo);
1393 inextension= true;
1394 initialized= true;
1395 fail= false;
1396 random_element= randomElement (m*lcA*lcB, alpha, l, fail);
1397 deg++;
1398 } while (fail);
1399 list= CFList();
1400 V_buf= alpha;
1401 cleanUp= alpha;
1402 TIMING_START (gcd_recursion);
1403 G_random_element=
1404 modGCDFq (ppA (random_element, x), ppB (random_element, x),
1405 coF_random_element, coG_random_element, alpha,
1406 list, topLevel);
1407 TIMING_END_AND_PRINT (gcd_recursion,
1408 "time for recursive call: ");
1409 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1410 }
1411 else if (fail && inextension)
1412 {
1413 source= CFList();
1414 dest= CFList();
1415
1416 Variable V_buf3= V_buf;
1417 V_buf= chooseExtension (V_buf);
1418 bool prim_fail= false;
1419 Variable V_buf2;
1420 CanonicalForm prim_elem, im_prim_elem;
1421 prim_elem= primitiveElement (alpha, V_buf2, prim_fail);
1422
1423 if (V_buf3 != alpha)
1424 {
1425 m= mapDown (m, prim_elem, im_prim_elem, alpha, source, dest);
1426 G_m= mapDown (G_m, prim_elem, im_prim_elem, alpha, source, dest);
1427 coF_m= mapDown (coF_m, prim_elem, im_prim_elem, alpha, source, dest);
1428 coG_m= mapDown (coG_m, prim_elem, im_prim_elem, alpha, source, dest);
1429 newtonPoly= mapDown (newtonPoly, prim_elem, im_prim_elem, alpha,
1430 source, dest);
1431 ppA= mapDown (ppA, prim_elem, im_prim_elem, alpha, source, dest);
1432 ppB= mapDown (ppB, prim_elem, im_prim_elem, alpha, source, dest);
1433 gcdlcAlcB= mapDown (gcdlcAlcB, prim_elem, im_prim_elem, alpha, source,
1434 dest);
1435 lcA= mapDown (lcA, prim_elem, im_prim_elem, alpha, source, dest);
1436 lcB= mapDown (lcB, prim_elem, im_prim_elem, alpha, source, dest);
1437 for (CFListIterator i= l; i.hasItem(); i++)
1438 i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
1439 source, dest);
1440 }
1441
1442 ASSERT (!prim_fail, "failure in integer factorizer");
1443 if (prim_fail)
1444 ; //ERROR
1445 else
1446 im_prim_elem= mapPrimElem (prim_elem, alpha, V_buf);
1447
1448 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
1449 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
1450
1451 for (CFListIterator i= l; i.hasItem(); i++)
1452 i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
1453 im_prim_elem, source, dest);
1454 m= mapUp (m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1455 G_m= mapUp (G_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1456 coF_m= mapUp (coF_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1457 coG_m= mapUp (coG_m, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1458 newtonPoly= mapUp (newtonPoly, alpha, V_buf, prim_elem, im_prim_elem,
1459 source, dest);
1460 ppA= mapUp (ppA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1461 ppB= mapUp (ppB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1462 gcdlcAlcB= mapUp (gcdlcAlcB, alpha, V_buf, prim_elem, im_prim_elem,
1463 source, dest);
1464 lcA= mapUp (lcA, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1465 lcB= mapUp (lcB, alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1466 fail= false;
1467 random_element= randomElement (m*lcA*lcB, V_buf, l, fail );
1468 DEBOUTLN (cerr, "fail= " << fail);
1469 CFList list;
1470 TIMING_START (gcd_recursion);
1471 G_random_element=
1472 modGCDFq (ppA (random_element, x), ppB (random_element, x),
1473 coF_random_element, coG_random_element, V_buf,
1474 list, topLevel);
1475 TIMING_END_AND_PRINT (gcd_recursion,
1476 "time for recursive call: ");
1477 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1478 alpha= V_buf;
1479 }
1480
1481 if (!G_random_element.inCoeffDomain())
1482 d0= totaldegree (G_random_element, Variable(2),
1483 Variable (G_random_element.level()));
1484 else
1485 d0= 0;
1486
1487 if (d0 == 0)
1488 {
1489 if (inextension)
1490 prune (cleanUp);
1491 coF= N (ppA*(cA/gcdcAcB));
1492 coG= N (ppB*(cB/gcdcAcB));
1493 return N(gcdcAcB);
1494 }
1495
1496 if (d0 > d)
1497 {
1498 if (!find (l, random_element))
1499 l.append (random_element);
1500 continue;
1501 }
1502
1503 G_random_element= (gcdlcAlcB(random_element,x)/uni_lcoeff(G_random_element))
1504 *G_random_element;
1505
1506 coF_random_element= (lcA(random_element,x)/uni_lcoeff(coF_random_element))
1507 *coF_random_element;
1508 coG_random_element= (lcB(random_element,x)/uni_lcoeff(coG_random_element))
1509 *coG_random_element;
1510
1511 if (!G_random_element.inCoeffDomain())
1512 d0= totaldegree (G_random_element, Variable(2),
1513 Variable (G_random_element.level()));
1514 else
1515 d0= 0;
1516
1517 if (d0 < d)
1518 {
1519 m= gcdlcAlcB;
1520 newtonPoly= 1;
1521 G_m= 0;
1522 d= d0;
1523 coF_m= 0;
1524 coG_m= 0;
1525 }
1526
1527 TIMING_START (newton_interpolation);
1528 H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
1529 coF= newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,x);
1530 coG= newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,x);
1531 TIMING_END_AND_PRINT (newton_interpolation,
1532 "time for newton_interpolation: ");
1533
1534 //termination test
1535 if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
1536 {
1537 TIMING_START (termination_test);
1538 if (gcdlcAlcB.isOne())
1539 cH= 1;
1540 else
1541 cH= uni_content (H);
1542 ppH= H/cH;
1543 ppH /= Lc (ppH);
1544 CanonicalForm lcppH= gcdlcAlcB/cH;
1545 CanonicalForm ccoF= lcppH/Lc (lcppH);
1546 CanonicalForm ccoG= lcppH/Lc (lcppH);
1547 ppCoF= coF/ccoF;
1548 ppCoG= coG/ccoG;
1549 DEBOUTLN (cerr, "ppH= " << ppH);
1550 if (((degree (ppCoF,1)+degree (ppH,1) == bound1) &&
1551 (degree (ppCoG,1)+degree (ppH,1) == bound2) &&
1552 terminationTest (ppA, ppB, ppCoF, ppCoG, ppH)) ||
1553 (fdivides (ppH, ppA, ppCoF) && fdivides (ppH, ppB, ppCoG)))
1554 {
1555 if (inextension)
1556 prune (cleanUp);
1557 coF= N ((cA/gcdcAcB)*ppCoF);
1558 coG= N ((cB/gcdcAcB)*ppCoG);
1559 TIMING_END_AND_PRINT (termination_test,
1560 "time for successful termination Fp: ");
1561 return N(gcdcAcB*ppH);
1562 }
1563 TIMING_END_AND_PRINT (termination_test,
1564 "time for unsuccessful termination Fp: ");
1565 }
1566
1567 G_m= H;
1568 coF_m= coF;
1569 coG_m= coG;
1570 newtonPoly= newtonPoly*(x - random_element);
1571 m= m*(x - random_element);
1572 if (!find (l, random_element))
1573 l.append (random_element);
1574 } while (1);
1575}
int degree(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm Lc(const CanonicalForm &f)
List< CanonicalForm > CFList
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int m
Definition: cfEzgcd.cc:128
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:478
const CanonicalForm const CanonicalForm const CanonicalForm & coG
Definition: cfModGcd.cc:67
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:91
static Variable chooseExtension(const Variable &alpha)
Definition: cfModGcd.cc:420
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
Definition: cfModGcd.cc:281
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:339
const CanonicalForm const CanonicalForm & coF
Definition: cfModGcd.cc:67
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:379
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
Definition: cfModGcd.cc:1171
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:364
bool terminationTest(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &coF, const CanonicalForm &coG, const CanonicalForm &cand)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition: cf_irred.cc:26
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:450
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:342
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:123
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
class CFMap
Definition: cf_map.h:85
CanonicalForm genOne() const
CF_NO_INLINE bool isZero() const
CF_NO_INLINE bool isOne() const
int level() const
level() returns the level of CO.
bool inBaseDomain() const
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm H
Definition: facAbsFact.cc:60
CanonicalForm mipo
Definition: facAlgExt.cc:57
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
#define M
Definition: sirandom.c:25
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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}
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, Variable &alpha, CFList &l, bool &top_level)
Definition: cfModGcd.cc:462

◆ modGCDFq() [2/2]

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

Definition at line 462 of file cfModGcd.cc.

464{
465 CanonicalForm dummy1, dummy2;
466 CanonicalForm result= modGCDFq (F, G, dummy1, dummy2, alpha, l,
467 topLevel);
468 return result;
469}

◆ 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}
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CFList &l, bool &top_level)
Definition: cfModGcd.cc:858
#define GaloisFieldDomain
Definition: cf_defs.h:18
static int gettype()
Definition: cf_factory.h:28

◆ modGCDGF() [2/2]

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

Definition at line 858 of file cfModGcd.cc.

860{
861 CanonicalForm dummy1, dummy2;
862 CanonicalForm result= modGCDGF (F, G, dummy1, dummy2, l, topLevel);
863 return result;
864}
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:872

◆ 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}
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3561
#define FiniteFieldDomain
Definition: cf_defs.h:19

◆ sparseGCDFp() [2/2]

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

Definition at line 3561 of file cfModGcd.cc.

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

◆ 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}
CanonicalForm sparseGCDFq(const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, CFList &l, bool &topLevel)
Definition: cfModGcd.cc:3129

◆ sparseGCDFq() [2/2]

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

Definition at line 3129 of file cfModGcd.cc.

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

◆ terminationTest()

bool terminationTest ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm coF,
const CanonicalForm coG,
const CanonicalForm cand 
)