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

1959{
1960 if (F.inCoeffDomain())
1961 {
1962 CFArray result= CFArray (1);
1963 result [0]= 1;
1964 return result;
1965 }
1966 if (F.isUnivariate())
1967 {
1968 CFArray result= CFArray (size(F));
1969 int j= 0;
1970 for (CFIterator i= F; i.hasTerms(); i++, j++)
1971 result[j]= power (F.mvar(), i.exp());
1972 return result;
1973 }
1974 int numMon= size (F);
1976 int j= 0;
1978 Variable x= F.mvar();
1980 for (CFIterator i= F; i.hasTerms(); i++)
1981 {
1982 powX= power (x, i.exp());
1983 recResult= getMonoms (i.coeff());
1984 for (int k= 0; k < recResult.size(); k++)
1985 result[j+k]= powX*recResult[k];
1986 j += recResult.size();
1987 }
1988 return result;
1989}
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:1958
Variable x
Definition cfModGcd.cc:4083
int i
Definition cfModGcd.cc:4079
class to iterate through CanonicalForm's
Definition cf_iter.h:44
factory's main class
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
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:1213
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 1213 of file cfModGcd.cc.

1215{
1218 return result;
1219}
int l
Definition cfEzgcd.cc:100
const CanonicalForm CFMap CFMap bool topLevel
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition cfModGcd.cc:1224
const CanonicalForm & G
Definition cfModGcd.cc:67

◆ modGCDFp() [4/4]

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

Definition at line 1224 of file cfModGcd.cc.

1227{
1228 CanonicalForm A= F;
1229 CanonicalForm B= G;
1230 if (F.isZero() && degree(G) > 0)
1231 {
1232 coF= 0;
1233 coG= Lc (G);
1234 return G/Lc(G);
1235 }
1236 else if (G.isZero() && degree (F) > 0)
1237 {
1238 coF= Lc (F);
1239 coG= 0;
1240 return F/Lc(F);
1241 }
1242 else if (F.isZero() && G.isZero())
1243 {
1244 coF= coG= 0;
1245 return F.genOne();
1246 }
1247 if (F.inBaseDomain() || G.inBaseDomain())
1248 {
1249 coF= F;
1250 coG= G;
1251 return F.genOne();
1252 }
1253 if (F.isUnivariate() && fdivides(F, G, coG))
1254 {
1255 coF= Lc (F);
1256 return F/Lc(F);
1257 }
1258 if (G.isUnivariate() && fdivides(G, F, coF))
1259 {
1260 coG= Lc (G);
1261 return G/Lc(G);
1262 }
1263 if (F == G)
1264 {
1265 coF= coG= Lc (F);
1266 return F/Lc(F);
1267 }
1268 CFMap M,N;
1269 int best_level= myCompress (A, B, M, N, topLevel);
1270
1271 if (best_level == 0)
1272 {
1273 coF= F;
1274 coG= G;
1275 return B.genOne();
1276 }
1277
1278 A= M(A);
1279 B= M(B);
1280
1281 Variable x= Variable (1);
1282
1283 //univariate case
1284 if (A.isUnivariate() && B.isUnivariate())
1285 {
1287 coF= N (A/result);
1288 coG= N (B/result);
1289 return N (result);
1290 }
1291
1292 CanonicalForm cA, cB; // content of A and B
1293 CanonicalForm ppA, ppB; // primitive part of A and B
1295
1296 cA = uni_content (A);
1297 cB = uni_content (B);
1298 gcdcAcB= gcd (cA, cB);
1299 ppA= A/cA;
1300 ppB= B/cB;
1301
1302 CanonicalForm lcA, lcB; // leading coefficients of A and B
1304 lcA= uni_lcoeff (ppA);
1305 lcB= uni_lcoeff (ppB);
1306
1307 gcdlcAlcB= gcd (lcA, lcB);
1308
1309 int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
1310 int d0;
1311
1312 if (d == 0)
1313 {
1314 coF= N (ppA*(cA/gcdcAcB));
1315 coG= N (ppB*(cB/gcdcAcB));
1316 return N(gcdcAcB);
1317 }
1318
1319 d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
1320
1321 if (d0 < d)
1322 d= d0;
1323
1324 if (d == 0)
1325 {
1326 coF= N (ppA*(cA/gcdcAcB));
1327 coG= N (ppB*(cB/gcdcAcB));
1328 return N(gcdcAcB);
1329 }
1330
1334
1335 newtonPoly= 1;
1336 m= gcdlcAlcB;
1337 H= 0;
1338 coF= 0;
1339 coG= 0;
1340 G_m= 0;
1342 bool fail= false;
1343 bool inextension= false;
1344 topLevel= false;
1345 CFList source, dest;
1346 int bound1= degree (ppA, 1);
1347 int bound2= degree (ppB, 1);
1348 do
1349 {
1350 if (inextension)
1352 else
1354
1355 if (!fail && !inextension)
1356 {
1357 CFList list;
1362 list);
1364 "time for recursive call: ");
1365 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1366 }
1367 else if (!fail && inextension)
1368 {
1369 CFList list;
1374 list, topLevel);
1376 "time for recursive call: ");
1377 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1378 }
1379 else if (fail && !inextension)
1380 {
1381 source= CFList();
1382 dest= CFList();
1383 CFList list;
1385 int deg= 2;
1386 bool initialized= false;
1387 do
1388 {
1389 mipo= randomIrredpoly (deg, x);
1390 if (initialized)
1391 setMipo (alpha, mipo);
1392 else
1393 alpha= rootOf (mipo);
1394 inextension= true;
1395 initialized= true;
1396 fail= false;
1398 deg++;
1399 } while (fail);
1400 list= CFList();
1401 V_buf= alpha;
1402 cleanUp= alpha;
1407 list, topLevel);
1409 "time for recursive call: ");
1410 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1411 }
1412 else if (fail && inextension)
1413 {
1414 source= CFList();
1415 dest= CFList();
1416
1419 bool prim_fail= false;
1423
1424 if (V_buf3 != alpha)
1425 {
1431 source, dest);
1435 dest);
1438 for (CFListIterator i= l; i.hasItem(); i++)
1439 i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
1440 source, dest);
1441 }
1442
1443 ASSERT (!prim_fail, "failure in integer factorizer");
1444 if (prim_fail)
1445 ; //ERROR
1446 else
1448
1449 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
1450 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
1451
1452 for (CFListIterator i= l; i.hasItem(); i++)
1453 i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
1454 im_prim_elem, source, dest);
1460 source, dest);
1464 source, dest);
1467 fail= false;
1469 DEBOUTLN (cerr, "fail= " << fail);
1470 CFList list;
1475 list, topLevel);
1477 "time for recursive call: ");
1478 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
1479 alpha= V_buf;
1480 }
1481
1482 if (!G_random_element.inCoeffDomain())
1484 Variable (G_random_element.level()));
1485 else
1486 d0= 0;
1487
1488 if (d0 == 0)
1489 {
1490 if (inextension)
1491 prune (cleanUp);
1492 coF= N (ppA*(cA/gcdcAcB));
1493 coG= N (ppB*(cB/gcdcAcB));
1494 return N(gcdcAcB);
1495 }
1496
1497 if (d0 > d)
1498 {
1499 if (!find (l, random_element))
1501 continue;
1502 }
1503
1506
1511
1512 if (!G_random_element.inCoeffDomain())
1514 Variable (G_random_element.level()));
1515 else
1516 d0= 0;
1517
1518 if (d0 < d)
1519 {
1520 m= gcdlcAlcB;
1521 newtonPoly= 1;
1522 G_m= 0;
1523 d= d0;
1524 coF_m= 0;
1525 coG_m= 0;
1526 }
1527
1533 "time for newton_interpolation: ");
1534
1535 //termination test
1536 if ((uni_lcoeff (H) == gcdlcAlcB) || (G_m == H))
1537 {
1539 if (gcdlcAlcB.isOne())
1540 cH= 1;
1541 else
1542 cH= uni_content (H);
1543 ppH= H/cH;
1544 ppH /= Lc (ppH);
1548 ppCoF= coF/ccoF;
1549 ppCoG= coG/ccoG;
1550 DEBOUTLN (cerr, "ppH= " << ppH);
1551 if (((degree (ppCoF,1)+degree (ppH,1) == bound1) &&
1552 (degree (ppCoG,1)+degree (ppH,1) == bound2) &&
1554 (fdivides (ppH, ppA, ppCoF) && fdivides (ppH, ppB, ppCoG)))
1555 {
1556 if (inextension)
1557 prune (cleanUp);
1558 coF= N ((cA/gcdcAcB)*ppCoF);
1559 coG= N ((cB/gcdcAcB)*ppCoG);
1561 "time for successful termination Fp: ");
1562 return N(gcdcAcB*ppH);
1563 }
1565 "time for unsuccessful termination Fp: ");
1566 }
1567
1568 G_m= H;
1569 coF_m= coF;
1570 coG_m= coG;
1572 m= m*(x - random_element);
1573 if (!find (l, random_element))
1575 } while (1);
1576}
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:479
const CanonicalForm const CanonicalForm const CanonicalForm & coG
Definition cfModGcd.cc:68
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:92
static Variable chooseExtension(const Variable &alpha)
Definition cfModGcd.cc:421
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
Definition cfModGcd.cc:282
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:340
const CanonicalForm const CanonicalForm & coF
Definition cfModGcd.cc:68
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:380
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
Definition cfModGcd.cc:1172
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:365
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 .
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
class CFMap
Definition cf_map.h:85
CanonicalForm genOne() const
CF_NO_INLINE bool isZero() const
bool inBaseDomain() const
void append(const T &)
#define DEBOUTLN(stream, objects)
Definition debug.h:49
Variable alpha
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)

◆ 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:463

◆ modGCDFq() [2/2]

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

Definition at line 463 of file cfModGcd.cc.

465{
468 topLevel);
469 return result;
470}

◆ 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:859
#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 859 of file cfModGcd.cc.

861{
864 return result;
865}
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:873

◆ 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:3563
#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 3563 of file cfModGcd.cc.

3565{
3566 CanonicalForm A= F;
3567 CanonicalForm B= G;
3568 if (F.isZero() && degree(G) > 0) return G/Lc(G);
3569 else if (G.isZero() && degree (F) > 0) return F/Lc(F);
3570 else if (F.isZero() && G.isZero()) return F.genOne();
3571 if (F.inBaseDomain() || G.inBaseDomain()) return F.genOne();
3572 if (F.isUnivariate() && fdivides(F, G)) return F/Lc(F);
3573 if (G.isUnivariate() && fdivides(G, F)) return G/Lc(G);
3574 if (F == G) return F/Lc(F);
3575
3576 CFMap M,N;
3577 int best_level= myCompress (A, B, M, N, topLevel);
3578
3579 if (best_level == 0) return B.genOne();
3580
3581 A= M(A);
3582 B= M(B);
3583
3584 Variable x= Variable (1);
3585
3586 //univariate case
3587 if (A.isUnivariate() && B.isUnivariate())
3588 return N (gcd (A, B));
3589
3590 CanonicalForm cA, cB; // content of A and B
3591 CanonicalForm ppA, ppB; // primitive part of A and B
3593
3594 cA = uni_content (A);
3595 cB = uni_content (B);
3596 gcdcAcB= gcd (cA, cB);
3597 ppA= A/cA;
3598 ppB= B/cB;
3599
3600 CanonicalForm lcA, lcB; // leading coefficients of A and B
3602 lcA= uni_lcoeff (ppA);
3603 lcB= uni_lcoeff (ppB);
3604
3605 if (fdivides (lcA, lcB))
3606 {
3607 if (fdivides (A, B))
3608 return F/Lc(F);
3609 }
3610 if (fdivides (lcB, lcA))
3611 {
3612 if (fdivides (B, A))
3613 return G/Lc(G);
3614 }
3615
3616 gcdlcAlcB= gcd (lcA, lcB);
3617
3618 int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
3619 int d0;
3620
3621 if (d == 0)
3622 return N(gcdcAcB);
3623
3624 d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
3625
3626 if (d0 < d)
3627 d= d0;
3628
3629 if (d == 0)
3630 return N(gcdcAcB);
3631
3634 m= gcdlcAlcB;
3635 G_m= 0;
3636 H= 0;
3637 bool fail= false;
3638 topLevel= false;
3639 bool inextension= false;
3642 CFList source, dest;
3643 do //first do
3644 {
3645 if (inextension)
3647 else
3649 if (random_element == 0 && !fail)
3650 {
3651 if (!find (l, random_element))
3653 continue;
3654 }
3655
3656 if (!fail && !inextension)
3657 {
3658 CFList list;
3662 list);
3664 "time for recursive call: ");
3665 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3666 }
3667 else if (!fail && inextension)
3668 {
3669 CFList list;
3673 list, topLevel);
3675 "time for recursive call: ");
3676 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3677 }
3678 else if (fail && !inextension)
3679 {
3680 source= CFList();
3681 dest= CFList();
3682 CFList list;
3684 int deg= 2;
3685 bool initialized= false;
3686 do
3687 {
3688 mipo= randomIrredpoly (deg, x);
3689 if (initialized)
3690 setMipo (alpha, mipo);
3691 else
3692 alpha= rootOf (mipo);
3693 inextension= true;
3694 fail= false;
3695 initialized= true;
3697 deg++;
3698 } while (fail);
3699 cleanUp= alpha;
3700 V_buf= alpha;
3701 list= CFList();
3705 list, topLevel);
3707 "time for recursive call: ");
3708 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3709 }
3710 else if (fail && inextension)
3711 {
3712 source= CFList();
3713 dest= CFList();
3714
3717 bool prim_fail= false;
3721
3722 if (V_buf3 != alpha)
3723 {
3727 dest);
3731 dest);
3732 for (CFListIterator i= l; i.hasItem(); i++)
3733 i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
3734 source, dest);
3735 }
3736
3737 ASSERT (!prim_fail, "failure in integer factorizer");
3738 if (prim_fail)
3739 ; //ERROR
3740 else
3742
3743 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
3744 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
3745
3746 for (CFListIterator i= l; i.hasItem(); i++)
3747 i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
3748 im_prim_elem, source, dest);
3752 source, dest);
3756 source, dest);
3757 fail= false;
3759 DEBOUTLN (cerr, "fail= " << fail);
3760 CFList list;
3764 list, topLevel);
3766 "time for recursive call: ");
3767 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3768 alpha= V_buf;
3769 }
3770
3771 if (!G_random_element.inCoeffDomain())
3773 Variable (G_random_element.level()));
3774 else
3775 d0= 0;
3776
3777 if (d0 == 0)
3778 {
3779 if (inextension)
3780 prune (cleanUp);
3781 return N(gcdcAcB);
3782 }
3783 if (d0 > d)
3784 {
3785 if (!find (l, random_element))
3787 continue;
3788 }
3789
3793
3795
3796 if (!G_random_element.inCoeffDomain())
3798 Variable (G_random_element.level()));
3799 else
3800 d0= 0;
3801
3802 if (d0 < d)
3803 {
3804 m= gcdlcAlcB;
3805 newtonPoly= 1;
3806 G_m= 0;
3807 d= d0;
3808 }
3809
3811
3812 if (uni_lcoeff (H) == gcdlcAlcB)
3813 {
3814 cH= uni_content (H);
3815 ppH= H/cH;
3816 ppH /= Lc (ppH);
3817 DEBOUTLN (cerr, "ppH= " << ppH);
3818
3819 if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3820 {
3821 if (inextension)
3822 prune (cleanUp);
3823 return N(gcdcAcB*ppH);
3824 }
3825 }
3826 G_m= H;
3828 m= m*(x - random_element);
3829 if (!find (l, random_element))
3831
3832 if ((getCharacteristic() > 3 && size (skeleton) < 200))
3833 {
3836
3837 do //second do
3838 {
3839 if (inextension)
3841 else
3843 if (random_element == 0 && !fail)
3844 {
3845 if (!find (l, random_element))
3847 continue;
3848 }
3849
3850 bool sparseFail= false;
3851 if (!fail && !inextension)
3852 {
3853 CFList list;
3855 if (LC (skeleton).inCoeffDomain())
3859 Monoms);
3860 else
3866 "time for recursive call: ");
3867 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3868 }
3869 else if (!fail && inextension)
3870 {
3871 CFList list;
3873 if (LC (skeleton).inCoeffDomain())
3877 Monoms);
3878 else
3882 Monoms);
3884 "time for recursive call: ");
3885 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3886 }
3887 else if (fail && !inextension)
3888 {
3889 source= CFList();
3890 dest= CFList();
3891 CFList list;
3893 int deg= 2;
3894 bool initialized= false;
3895 do
3896 {
3897 mipo= randomIrredpoly (deg, x);
3898 if (initialized)
3899 setMipo (alpha, mipo);
3900 else
3901 alpha= rootOf (mipo);
3902 inextension= true;
3903 fail= false;
3904 initialized= true;
3906 deg++;
3907 } while (fail);
3908 cleanUp= alpha;
3909 V_buf= alpha;
3910 list= CFList();
3912 if (LC (skeleton).inCoeffDomain())
3916 Monoms);
3917 else
3921 Monoms);
3923 "time for recursive call: ");
3924 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3925 }
3926 else if (fail && inextension)
3927 {
3928 source= CFList();
3929 dest= CFList();
3930
3933 bool prim_fail= false;
3937
3938 if (V_buf3 != alpha)
3939 {
3943 source, dest);
3947 source, dest);
3948 for (CFListIterator i= l; i.hasItem(); i++)
3949 i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, alpha,
3950 source, dest);
3951 }
3952
3953 ASSERT (!prim_fail, "failure in integer factorizer");
3954 if (prim_fail)
3955 ; //ERROR
3956 else
3958
3959 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha));
3960 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (V_buf2));
3961
3962 for (CFListIterator i= l; i.hasItem(); i++)
3963 i.getItem()= mapUp (i.getItem(), alpha, V_buf, prim_elem,
3964 im_prim_elem, source, dest);
3968 source, dest);
3972 source, dest);
3973 fail= false;
3975 DEBOUTLN (cerr, "fail= " << fail);
3976 CFList list;
3978 if (LC (skeleton).inCoeffDomain())
3982 Monoms);
3983 else
3989 "time for recursive call: ");
3990 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3991 alpha= V_buf;
3992 }
3993
3994 if (sparseFail)
3995 break;
3996
3997 if (!G_random_element.inCoeffDomain())
3999 Variable (G_random_element.level()));
4000 else
4001 d0= 0;
4002
4003 if (d0 == 0)
4004 {
4005 if (inextension)
4006 prune (cleanUp);
4007 return N(gcdcAcB);
4008 }
4009 if (d0 > d)
4010 {
4011 if (!find (l, random_element))
4013 continue;
4014 }
4015
4019
4020 if (!G_random_element.inCoeffDomain())
4022 Variable (G_random_element.level()));
4023 else
4024 d0= 0;
4025
4026 if (d0 < d)
4027 {
4028 m= gcdlcAlcB;
4029 newtonPoly= 1;
4030 G_m= 0;
4031 d= d0;
4032 }
4033
4037 "time for newton interpolation: ");
4038
4039 //termination test
4040 if (uni_lcoeff (H) == gcdlcAlcB)
4041 {
4042 cH= uni_content (H);
4043 ppH= H/cH;
4044 ppH /= Lc (ppH);
4045 DEBOUTLN (cerr, "ppH= " << ppH);
4046 if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
4047 {
4048 if (inextension)
4049 prune (cleanUp);
4050 return N(gcdcAcB*ppH);
4051 }
4052 }
4053
4054 G_m= H;
4056 m= m*(x - random_element);
4057 if (!find (l, random_element))
4059
4060 } while (1); //end of second do
4061 }
4062 else
4063 {
4064 if (inextension)
4065 prune (cleanUp);
4066 return N(gcdcAcB*modGCDFp (ppA, ppB));
4067 }
4068 } while (1); //end of first do
4069}
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:3131
CanonicalForm monicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
Definition cfModGcd.cc:2200
CanonicalForm nonMonicSparseInterpol(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &skeleton, const Variable &alpha, bool &fail, CFArray *&coeffMonoms, CFArray &Monoms)
Definition cfModGcd.cc:2484
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition cfModGcd.cc:3563

◆ 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:3131

◆ sparseGCDFq() [2/2]

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

Definition at line 3131 of file cfModGcd.cc.

3133{
3134 CanonicalForm A= F;
3135 CanonicalForm B= G;
3136 if (F.isZero() && degree(G) > 0) return G/Lc(G);
3137 else if (G.isZero() && degree (F) > 0) return F/Lc(F);
3138 else if (F.isZero() && G.isZero()) return F.genOne();
3139 if (F.inBaseDomain() || G.inBaseDomain()) return F.genOne();
3140 if (F.isUnivariate() && fdivides(F, G)) return F/Lc(F);
3141 if (G.isUnivariate() && fdivides(G, F)) return G/Lc(G);
3142 if (F == G) return F/Lc(F);
3143
3144 CFMap M,N;
3145 int best_level= myCompress (A, B, M, N, topLevel);
3146
3147 if (best_level == 0) return B.genOne();
3148
3149 A= M(A);
3150 B= M(B);
3151
3152 Variable x= Variable (1);
3153
3154 //univariate case
3155 if (A.isUnivariate() && B.isUnivariate())
3156 return N (gcd (A, B));
3157
3158 CanonicalForm cA, cB; // content of A and B
3159 CanonicalForm ppA, ppB; // primitive part of A and B
3161
3162 cA = uni_content (A);
3163 cB = uni_content (B);
3164 gcdcAcB= gcd (cA, cB);
3165 ppA= A/cA;
3166 ppB= B/cB;
3167
3168 CanonicalForm lcA, lcB; // leading coefficients of A and B
3170 lcA= uni_lcoeff (ppA);
3171 lcB= uni_lcoeff (ppB);
3172
3173 if (fdivides (lcA, lcB))
3174 {
3175 if (fdivides (A, B))
3176 return F/Lc(F);
3177 }
3178 if (fdivides (lcB, lcA))
3179 {
3180 if (fdivides (B, A))
3181 return G/Lc(G);
3182 }
3183
3184 gcdlcAlcB= gcd (lcA, lcB);
3185
3186 int d= totaldegree (ppA, Variable (2), Variable (ppA.level()));
3187 int d0;
3188
3189 if (d == 0)
3190 return N(gcdcAcB);
3191 d0= totaldegree (ppB, Variable (2), Variable (ppB.level()));
3192
3193 if (d0 < d)
3194 d= d0;
3195
3196 if (d == 0)
3197 return N(gcdcAcB);
3198
3201 m= gcdlcAlcB;
3202 G_m= 0;
3203 H= 0;
3204 bool fail= false;
3205 topLevel= false;
3206 bool inextension= false;
3210 CFList source, dest;
3211 do // first do
3212 {
3214 if (random_element == 0 && !fail)
3215 {
3216 if (!find (l, random_element))
3218 continue;
3219 }
3220 if (fail)
3221 {
3222 source= CFList();
3223 dest= CFList();
3224
3227 bool prim_fail= false;
3230 if (V_buf4 == alpha)
3232
3233 if (V_buf3 != V_buf4)
3234 {
3238 source, dest);
3242 dest);
3243 for (CFListIterator i= l; i.hasItem(); i++)
3244 i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, V_buf4,
3245 source, dest);
3246 }
3247
3248 ASSERT (!prim_fail, "failure in integer factorizer");
3249 if (prim_fail)
3250 ; //ERROR
3251 else
3253
3254 if (V_buf4 == alpha)
3256 else
3258 im_prim_elem, source, dest);
3259
3260 DEBOUTLN (cerr, "getMipo (V_buf4)= " << getMipo (V_buf4));
3261 DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2));
3262 inextension= true;
3263 for (CFListIterator i= l; i.hasItem(); i++)
3264 i.getItem()= mapUp (i.getItem(), V_buf4, V_buf, prim_elem,
3265 im_prim_elem, source, dest);
3269 source, dest);
3273 source, dest);
3274
3275 fail= false;
3277 DEBOUTLN (cerr, "fail= " << fail);
3278 CFList list;
3282 list, topLevel);
3284 "time for recursive call: ");
3285 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3286 V_buf4= V_buf;
3287 }
3288 else
3289 {
3290 CFList list;
3294 list, topLevel);
3296 "time for recursive call: ");
3297 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3298 }
3299
3300 if (!G_random_element.inCoeffDomain())
3302 Variable (G_random_element.level()));
3303 else
3304 d0= 0;
3305
3306 if (d0 == 0)
3307 {
3308 if (inextension)
3309 prune1 (alpha);
3310 return N(gcdcAcB);
3311 }
3312 if (d0 > d)
3313 {
3314 if (!find (l, random_element))
3316 continue;
3317 }
3318
3322
3324 if (!G_random_element.inCoeffDomain())
3326 Variable (G_random_element.level()));
3327 else
3328 d0= 0;
3329
3330 if (d0 < d)
3331 {
3332 m= gcdlcAlcB;
3333 newtonPoly= 1;
3334 G_m= 0;
3335 d= d0;
3336 }
3337
3339 if (uni_lcoeff (H) == gcdlcAlcB)
3340 {
3341 cH= uni_content (H);
3342 ppH= H/cH;
3343 if (inextension)
3344 {
3345 CFList u, v;
3346 //maybe it's better to test if ppH is an element of F(\alpha) before
3347 //mapping down
3348 if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3349 {
3350 DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
3352 ppH /= Lc(ppH);
3353 DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
3354 prune1 (alpha);
3355 return N(gcdcAcB*ppH);
3356 }
3357 }
3358 else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3359 return N(gcdcAcB*ppH);
3360 }
3361 G_m= H;
3363 m= m*(x - random_element);
3364 if (!find (l, random_element))
3366
3367 if (getCharacteristic () > 3 && size (skeleton) < 100)
3368 {
3371 do //second do
3372 {
3374 if (random_element == 0 && !fail)
3375 {
3376 if (!find (l, random_element))
3378 continue;
3379 }
3380 if (fail)
3381 {
3382 source= CFList();
3383 dest= CFList();
3384
3387 bool prim_fail= false;
3390 if (V_buf4 == alpha)
3392
3393 if (V_buf3 != V_buf4)
3394 {
3398 source, dest);
3402 source, dest);
3403 for (CFListIterator i= l; i.hasItem(); i++)
3404 i.getItem()= mapDown (i.getItem(), prim_elem, im_prim_elem, V_buf4,
3405 source, dest);
3406 }
3407
3408 ASSERT (!prim_fail, "failure in integer factorizer");
3409 if (prim_fail)
3410 ; //ERROR
3411 else
3413
3414 if (V_buf4 == alpha)
3416 else
3418 prim_elem, im_prim_elem, source, dest);
3419
3420 DEBOUTLN (cerr, "getMipo (V_buf4)= " << getMipo (V_buf4));
3421 DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2));
3422 inextension= true;
3423 for (CFListIterator i= l; i.hasItem(); i++)
3424 i.getItem()= mapUp (i.getItem(), V_buf4, V_buf, prim_elem,
3425 im_prim_elem, source, dest);
3429 source, dest);
3432
3434 source, dest);
3435
3436 fail= false;
3438 DEBOUTLN (cerr, "fail= " << fail);
3439 CFList list;
3441
3442 V_buf4= V_buf;
3443
3444 //sparseInterpolation
3445 bool sparseFail= false;
3446 if (LC (skeleton).inCoeffDomain())
3450 else
3454 Monoms);
3455 if (sparseFail)
3456 break;
3457
3459 "time for recursive call: ");
3460 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3461 }
3462 else
3463 {
3464 CFList list;
3466 bool sparseFail= false;
3467 if (LC (skeleton).inCoeffDomain())
3471 else
3475 Monoms);
3476 if (sparseFail)
3477 break;
3478
3480 "time for recursive call: ");
3481 DEBOUTLN (cerr, "G_random_element= " << G_random_element);
3482 }
3483
3484 if (!G_random_element.inCoeffDomain())
3486 Variable (G_random_element.level()));
3487 else
3488 d0= 0;
3489
3490 if (d0 == 0)
3491 {
3492 if (inextension)
3493 prune1 (alpha);
3494 return N(gcdcAcB);
3495 }
3496 if (d0 > d)
3497 {
3498 if (!find (l, random_element))
3500 continue;
3501 }
3502
3506
3507 if (!G_random_element.inCoeffDomain())
3509 Variable (G_random_element.level()));
3510 else
3511 d0= 0;
3512
3513 if (d0 < d)
3514 {
3515 m= gcdlcAlcB;
3516 newtonPoly= 1;
3517 G_m= 0;
3518 d= d0;
3519 }
3520
3524 "time for newton interpolation: ");
3525
3526 //termination test
3527 if (uni_lcoeff (H) == gcdlcAlcB)
3528 {
3529 cH= uni_content (H);
3530 ppH= H/cH;
3531 if (inextension)
3532 {
3533 CFList u, v;
3534 //maybe it's better to test if ppH is an element of F(\alpha) before
3535 //mapping down
3536 if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3537 {
3538 DEBOUTLN (cerr, "ppH before mapDown= " << ppH);
3540 ppH /= Lc(ppH);
3541 DEBOUTLN (cerr, "ppH after mapDown= " << ppH);
3542 prune1 (alpha);
3543 return N(gcdcAcB*ppH);
3544 }
3545 }
3546 else if (fdivides (ppH, ppA) && fdivides (ppH, ppB))
3547 {
3548 return N(gcdcAcB*ppH);
3549 }
3550 }
3551
3552 G_m= H;
3554 m= m*(x - random_element);
3555 if (!find (l, random_element))
3557
3558 } while (1);
3559 }
3560 } while (1);
3561}
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 
)