modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true.
388{
389
391 {
393 {
395 return;
396 }
397 if(
G.inCoeffDomain())
398 {
400 if(fail)
401 return;
403 return;
404 }
405
408 if(fail)
409 return;
412 return;
413 }
415 {
417 {
419 if(fail)
420 return;
422 return;
423 }
424
427 if(fail)
428 return;
431 return;
432 }
433
435 {
437 if(fail)
438 return;
440 return;
441 }
442 if(
G.inCoeffDomain())
443 {
445 if(fail)
446 return;
448 return;
449 }
453 if (lev == 0)
454 {
456 return;
457 }
461
462
466
468#ifdef HAVE_NTL
472 {
474 zz_p::init (ch);
475 }
477 zz_pE::init (NTLMipo);
478 zz_pEX NTLResult;
479 zz_pEX NTLF;
480 zz_pEX NTLG;
481#endif
482 if(mv == 1)
483 {
485#ifdef HAVE_NTL
489 if (fail)
490 return;
492#else
494 if(fail)
495 return;
496#endif
500 }
502
510#ifdef HAVE_NTL
514 if (fail)
515 return;
517#else
518 tryEuclid(
cf,
cg,
M,c,fail);
519 if(fail)
520 return;
521#endif
522
523 f.tryDiv (
cf,
M, fail);
524 if(fail)
525 return;
526
527 g.tryDiv (
cg,
M, fail);
528 if(fail)
529 return;
531 if(
f.inCoeffDomain())
532 {
534 if(fail)
535 return;
537 return;
538 }
539 if(
g.inCoeffDomain())
540 {
542 if(fail)
543 return;
545 return;
546 }
547 std::vector<int> L(mv + 1, 0);
548 std::vector<int>
N(mv + 1, 0);
549 for(
int i=2;
i<=mv;
i++)
555#ifdef HAVE_NTL
559 if (fail)
560 return;
562#else
564 if(fail)
565 return;
566#endif
571
572 std::vector<int> dg_im(mv+1);
580 bool divides= true;
582 {
586 continue;
590 "time for recursive calls in alg gcd mod p: ")
594 if(g_image.inCoeffDomain())
595 {
597 if(fail)
598 return;
600 return;
601 }
602 for(
int i=2;
i<=mv;
i++)
604 leadDeg(g_image, dg_im.data());
605 if(
isEqual(dg_im.data(), L.data(), 2, mv))
606 {
609 if (fail)
610 return;
611 g_image *= inv;
612 g_image *= gamma_image;
617 "time for Newton interpolation in alg gcd mod p: ")
618
619
620
624 if((
firstLC(gnew) == gamma) || (gnew == gm))
625 {
628 if(fail)
629 return;
630 divides = true;
631 g_image= gnew;
633 if(fail)
634 return;
636 if(fail)
637 return;
638 if(divides)
639 {
641 if(fail)
642 return;
643 if(divides2)
644 {
647 "time for successful termination test in alg gcd mod p: ")
649 }
650 }
652 "time for unsuccessful termination test in alg gcd mod p: ")
653 }
654 gm = gnew;
655 continue;
656 }
657
658 if(
isLess(L.data(), dg_im.data(), 2, mv))
659 continue;
660
661
663 gm = 0;
666 }
667
668 fail = true;
669}
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
const CanonicalForm CFMap CFMap bool topLevel
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
CanonicalForm firstLC(const CanonicalForm &f)
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
void tryNTLGCD(zz_pEX &x, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the GCD x of a and b, fail is set to true if a zero divisor is encountered
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
generate all elements in F_p starting from 0
const Variable & v
< [in] a sqrfree bivariate poly