1227{
1231 {
1235 }
1236 else if (
G.isZero() &&
degree (F) > 0)
1237 {
1241 }
1242 else if (F.
isZero() &&
G.isZero())
1243 {
1246 }
1248 {
1252 }
1254 {
1257 }
1259 {
1262 }
1264 {
1267 }
1270
1271 if (best_level == 0)
1272 {
1276 }
1277
1280
1282
1283
1284 if (
A.isUnivariate() &&
B.isUnivariate())
1285 {
1290 }
1291
1295
1298 gcdcAcB=
gcd (cA, cB);
1301
1306
1307 gcdlcAlcB=
gcd (lcA, lcB);
1308
1310 int d0;
1311
1312 if (d == 0)
1313 {
1314 coF=
N (ppA*(cA/gcdcAcB));
1315 coG=
N (ppB*(cB/gcdcAcB));
1317 }
1318
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));
1329 }
1330
1332 CanonicalForm newtonPoly, coF_random_element, coG_random_element,
1333 coF_m, coG_m, ppCoF, ppCoG;
1334
1335 newtonPoly= 1;
1340 G_m= 0;
1342 bool fail= false;
1343 bool inextension= false;
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 {
1359 G_random_element=
1360 modGCDFp (ppA (random_element,
x), ppB (random_element,
x),
1361 coF_random_element, coG_random_element,
topLevel,
1362 list);
1364 "time for recursive call: ");
1365 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1366 }
1367 else if (!fail && inextension)
1368 {
1371 G_random_element=
1372 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1373 coF_random_element, coG_random_element, V_buf,
1376 "time for recursive call: ");
1377 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1378 }
1379 else if (fail && !inextension)
1380 {
1385 int deg= 2;
1386 bool initialized= false;
1387 do
1388 {
1390 if (initialized)
1392 else
1394 inextension= true;
1395 initialized= true;
1396 fail= false;
1398 deg++;
1399 } while (fail);
1404 G_random_element=
1405 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1406 coF_random_element, coG_random_element,
alpha,
1409 "time for recursive call: ");
1410 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1411 }
1412 else if (fail && inextension)
1413 {
1416
1419 bool prim_fail= false;
1423
1424 if (V_buf3 !=
alpha)
1425 {
1427 G_m=
mapDown (G_m, prim_elem, im_prim_elem,
alpha, source, dest);
1428 coF_m=
mapDown (coF_m, prim_elem, im_prim_elem,
alpha, source, dest);
1429 coG_m=
mapDown (coG_m, prim_elem, im_prim_elem,
alpha, source, dest);
1430 newtonPoly=
mapDown (newtonPoly, prim_elem, im_prim_elem,
alpha,
1431 source, dest);
1432 ppA=
mapDown (ppA, prim_elem, im_prim_elem,
alpha, source, dest);
1433 ppB=
mapDown (ppB, prim_elem, im_prim_elem,
alpha, source, dest);
1434 gcdlcAlcB=
mapDown (gcdlcAlcB, prim_elem, im_prim_elem,
alpha, source,
1435 dest);
1436 lcA=
mapDown (lcA, prim_elem, im_prim_elem,
alpha, source, dest);
1437 lcB=
mapDown (lcB, prim_elem, im_prim_elem,
alpha, source, dest);
1439 i.getItem()=
mapDown (
i.getItem(), prim_elem, im_prim_elem,
alpha,
1440 source, dest);
1441 }
1442
1443 ASSERT (!prim_fail,
"failure in integer factorizer");
1444 if (prim_fail)
1445 ;
1446 else
1448
1451
1453 i.getItem()=
mapUp (
i.getItem(),
alpha, V_buf, prim_elem,
1454 im_prim_elem, source, dest);
1455 m=
mapUp (
m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1456 G_m=
mapUp (G_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1457 coF_m=
mapUp (coF_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1458 coG_m=
mapUp (coG_m,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1459 newtonPoly=
mapUp (newtonPoly,
alpha, V_buf, prim_elem, im_prim_elem,
1460 source, dest);
1461 ppA=
mapUp (ppA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1462 ppB=
mapUp (ppB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1463 gcdlcAlcB=
mapUp (gcdlcAlcB,
alpha, V_buf, prim_elem, im_prim_elem,
1464 source, dest);
1465 lcA=
mapUp (lcA,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1466 lcB=
mapUp (lcB,
alpha, V_buf, prim_elem, im_prim_elem, source, dest);
1467 fail= false;
1472 G_random_element=
1473 modGCDFq (ppA (random_element,
x), ppB (random_element,
x),
1474 coF_random_element, coG_random_element, V_buf,
1477 "time for recursive call: ");
1478 DEBOUTLN (cerr,
"G_random_element= " << G_random_element);
1480 }
1481
1485 else
1486 d0= 0;
1487
1488 if (d0 == 0)
1489 {
1490 if (inextension)
1492 coF=
N (ppA*(cA/gcdcAcB));
1493 coG=
N (ppB*(cB/gcdcAcB));
1495 }
1496
1497 if (d0 > d)
1498 {
1499 if (!
find (
l, random_element))
1500 l.append (random_element);
1501 continue;
1502 }
1503
1504 G_random_element= (gcdlcAlcB(random_element,
x)/
uni_lcoeff(G_random_element))
1505 *G_random_element;
1506
1507 coF_random_element= (lcA(random_element,
x)/
uni_lcoeff(coF_random_element))
1508 *coF_random_element;
1509 coG_random_element= (lcB(random_element,
x)/
uni_lcoeff(coG_random_element))
1510 *coG_random_element;
1511
1515 else
1516 d0= 0;
1517
1518 if (d0 < d)
1519 {
1521 newtonPoly= 1;
1522 G_m= 0;
1523 d= d0;
1524 coF_m= 0;
1525 coG_m= 0;
1526 }
1527
1529 H=
newtonInterp (random_element, G_random_element, newtonPoly, G_m,
x);
1530 coF=
newtonInterp (random_element, coF_random_element, newtonPoly, coF_m,
x);
1531 coG=
newtonInterp (random_element, coG_random_element, newtonPoly, coG_m,
x);
1533 "time for newton_interpolation: ");
1534
1535
1537 {
1539 if (gcdlcAlcB.
isOne())
1540 cH= 1;
1541 else
1555 {
1556 if (inextension)
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
1571 newtonPoly= newtonPoly*(
x - random_element);
1572 m=
m*(
x - random_element);
1573 if (!
find (
l, random_element))
1574 l.append (random_element);
1575 } while (1);
1576}
const CanonicalForm CFMap CFMap & N
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....
const CanonicalForm const CanonicalForm const CanonicalForm & coG
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
static Variable chooseExtension(const Variable &alpha)
static CanonicalForm uni_content(const CanonicalForm &F)
compute the content of F, where F is considered as an element of
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.
const CanonicalForm const CanonicalForm & coF
static CanonicalForm randomElement(const CanonicalForm &F, const Variable &alpha, CFList &list, bool &fail)
compute a random element a of , s.t. F(a) , F is a univariate polynomial, returns fail if there are...
static CanonicalForm FpRandomElement(const CanonicalForm &F, CFList &list, bool &fail)
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...
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)
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
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
#define DEBOUTLN(stream, objects)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
#define TIMING_END_AND_PRINT(t, msg)