My Project  UNKNOWN_GIT_VERSION
Functions
cfGcdAlgExt.h File Reference

GCD over Q(a) More...

#include "canonicalform.h"
#include "variable.h"

Go to the source code of this file.

Functions

CanonicalForm QGCD (const CanonicalForm &, const CanonicalForm &)
 gcd over Q(a) More...
 
void tryInvert (const CanonicalForm &, const CanonicalForm &, CanonicalForm &, bool &)
 
void tryBrownGCD (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel=true)
 modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true. More...
 
int * leadDeg (const CanonicalForm &f, int *degs)
 
bool isLess (int *a, int *b, int lower, int upper)
 
bool isEqual (int *a, int *b, int lower, int upper)
 
CanonicalForm firstLC (const CanonicalForm &f)
 

Detailed Description

GCD over Q(a)

ABSTRACT: Implementation of Encarnacion's GCD algorithm over number fields, see M.J. Encarnacion "Computing GCDs of polynomials over number fields", extended to the multivariate case.

See also
cfNTLzzpEXGCD.h

Definition in file cfGcdAlgExt.h.

Function Documentation

◆ firstLC()

CanonicalForm firstLC ( const CanonicalForm f)

Definition at line 956 of file cfGcdAlgExt.cc.

957 { // returns the leading coefficient (LC) of level <= 1
958  CanonicalForm ret = f;
959  while(ret.level() > 1)
960  ret = LC(ret);
961  return ret;
962 }
CanonicalForm LC(const CanonicalForm &f)
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:83
int level() const
level() returns the level of CO.

◆ isEqual()

bool isEqual ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 947 of file cfGcdAlgExt.cc.

948 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
949  for(int i=lower; i<=upper; i++)
950  if(a[i] != b[i])
951  return false;
952  return true;
953 }
int i
Definition: cfEzgcd.cc:125
CanonicalForm b
Definition: cfModGcd.cc:4044

◆ isLess()

bool isLess ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 936 of file cfGcdAlgExt.cc.

937 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
938  for(int i=upper; i>=lower; i--)
939  if(a[i] == b[i])
940  continue;
941  else
942  return a[i] < b[i];
943  return true;
944 }

◆ leadDeg()

int* leadDeg ( const CanonicalForm f,
int *  degs 
)

Definition at line 919 of file cfGcdAlgExt.cc.

920 { // leading degree vector w.r.t. lex. monomial order x(i+1) > x(i)
921  // if f is in a coeff domain, the zero pointer is returned
922  // 'a' should point to an array of sufficient size level(f)+1
923  if(f.inCoeffDomain())
924  return 0;
925  CanonicalForm tmp = f;
926  do
927  {
928  degs[tmp.level()] = tmp.degree();
929  tmp = LC(tmp);
930  }
931  while(!tmp.inCoeffDomain());
932  return degs;
933 }
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
bool inCoeffDomain() const

◆ QGCD()

gcd over Q(a)

Definition at line 715 of file cfGcdAlgExt.cc.

716 { // f,g in Q(a)[x1,...,xn]
717  if(F.isZero())
718  {
719  if(G.isZero())
720  return G; // G is zero
721  if(G.inCoeffDomain())
722  return CanonicalForm(1);
723  CanonicalForm lcinv= 1/Lc (G);
724  return G*lcinv; // return monic G
725  }
726  if(G.isZero()) // F is non-zero
727  {
728  if(F.inCoeffDomain())
729  return CanonicalForm(1);
730  CanonicalForm lcinv= 1/Lc (F);
731  return F*lcinv; // return monic F
732  }
733  if(F.inCoeffDomain() || G.inCoeffDomain())
734  return CanonicalForm(1);
735  // here: both NOT inCoeffDomain
736  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
737  int p, i;
738  int *bound, *other; // degree vectors
739  bool fail;
740  bool off_rational=!isOn(SW_RATIONAL);
741  On( SW_RATIONAL ); // needed by bCommonDen
742  f = F * bCommonDen(F);
743  g = G * bCommonDen(G);
745  CanonicalForm contf= myicontent (f);
746  CanonicalForm contg= myicontent (g);
747  f /= contf;
748  g /= contg;
749  CanonicalForm gcdcfcg= myicontent (contf, contg);
750  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
751  Variable a, b;
752  if(hasFirstAlgVar(f,a))
753  {
754  if(hasFirstAlgVar(g,b))
755  {
756  if(b.level() > a.level())
757  a = b;
758  }
759  }
760  else
761  {
762  if(!hasFirstAlgVar(g,a))// both not in extension
763  {
764  Off( SW_RATIONAL );
765  Off( SW_USE_QGCD );
766  tmp = gcdcfcg*gcd( f, g );
767  On( SW_USE_QGCD );
768  if (off_rational) Off(SW_RATIONAL);
769  return tmp;
770  }
771  }
772  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
773  setReduce(a,false); // do not reduce expressions modulo mipo
774  tmp = getMipo(a);
775  M = tmp * bCommonDen(tmp);
776  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
777  Off( SW_RATIONAL ); // needed by mod
778  // calculate upper bound for degree vector of gcd
779  int mv = f.level(); i = g.level();
780  if(i > mv)
781  mv = i;
782  // here: mv is level of the largest variable in f, g
783  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
784  other = new int[mv+1];
785  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
786  bound[i] = other[i] = 0;
787  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
788  other = leadDeg(g,other);
789  for(int i=1; i<=mv; i++) // entry at i=0 not visited
790  if(other[i] < bound[i])
791  bound[i] = other[i];
792  // now 'bound' is the smaller vector
793  cl = lc(M) * lc(f) * lc(g);
794  q = 1;
795  D = 0;
796  CanonicalForm test= 0;
797  bool equal= false;
798  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
799  {
800  p = cf_getBigPrime(i);
801  if( mod( cl, p ).isZero() ) // skip lc-bad primes
802  continue;
803  fail = false;
805  mipo = mapinto(M);
806  mipo /= mipo.lc();
807  // here: mipo is monic
808  TIMING_START (alg_gcd_p)
809  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
810  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
811  if( fail ) // mipo splits in char p
812  {
814  continue;
815  }
816  if( Dp.inCoeffDomain() ) // early termination
817  {
818  tryInvert(Dp,mipo,tmp,fail); // check if zero divisor
820  if(fail)
821  continue;
822  setReduce(a,true);
823  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
824  delete[] other;
825  delete[] bound;
826  return gcdcfcg;
827  }
829  // here: Dp NOT inCoeffDomain
830  for(int i=1; i<=mv; i++)
831  other[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
832  other = leadDeg(Dp,other);
833 
834  if(isEqual(bound, other, 1, mv)) // equal
835  {
836  chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
837  // tmp = Dp mod p
838  // tmp = D mod q
839  // newq = p*q
840  q = newq;
841  if( D != tmp )
842  D = tmp;
843  On( SW_RATIONAL );
844  TIMING_START (alg_reconstruction)
845  tmp = Farey( D, q ); // Farey
846  tmp *= bCommonDen (tmp);
847  TIMING_END_AND_PRINT (alg_reconstruction,
848  "time for rational reconstruction in alg gcd: ")
849  setReduce(a,true); // reduce expressions modulo mipo
850  On( SW_RATIONAL ); // needed by fdivides
851  if (test != tmp)
852  test= tmp;
853  else
854  equal= true; // modular image did not add any new information
855  TIMING_START (alg_termination)
856 #ifdef HAVE_NTL
857 #ifdef HAVE_FLINT
858  if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
859  && f.level() == tmp.level() && tmp.level() == g.level())
860  {
861  CanonicalForm Q, R;
862  newtonDivrem (f, tmp, Q, R);
863  if (R.isZero())
864  {
865  newtonDivrem (g, tmp, Q, R);
866  if (R.isZero())
867  {
868  Off (SW_RATIONAL);
869  setReduce (a,true);
870  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
871  TIMING_END_AND_PRINT (alg_termination,
872  "time for successful termination test in alg gcd: ")
873  delete[] other;
874  delete[] bound;
875  return tmp*gcdcfcg;
876  }
877  }
878  }
879  else
880 #endif
881 #endif
882  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
883  {
884  Off( SW_RATIONAL );
885  setReduce(a,true);
886  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
887  TIMING_END_AND_PRINT (alg_termination,
888  "time for successful termination test in alg gcd: ")
889  delete[] other;
890  delete[] bound;
891  return tmp*gcdcfcg;
892  }
893  TIMING_END_AND_PRINT (alg_termination,
894  "time for unsuccessful termination test in alg gcd: ")
895  Off( SW_RATIONAL );
896  setReduce(a,false); // do not reduce expressions modulo mipo
897  continue;
898  }
899  if( isLess(bound, other, 1, mv) ) // current prime unlucky
900  continue;
901  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
902  q = p;
903  D = mapinto(Dp); // shortcut CRA // shortcut CRA
904  for(int i=1; i<=mv; i++) // tighten bound
905  bound[i] = other[i];
906  }
907  // hopefully, we never reach this point
908  setReduce(a,true);
909  delete[] other;
910  delete[] bound;
911  Off( SW_USE_QGCD );
912  D = gcdcfcg*gcd( f, g );
913  On( SW_USE_QGCD );
914  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
915  return D;
916 }
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm lc(const CanonicalForm &f)
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm Lc(const CanonicalForm &f)
void setCharacteristic(int c)
Definition: cf_char.cc:23
else
Definition: cfGcdAlgExt.cc:195
bool isLess(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:936
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:919
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:947
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:656
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:65
if(topLevel)
Definition: cfGcdAlgExt.cc:75
return
Definition: cfGcdAlgExt.cc:218
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:55
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:221
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
int p
Definition: cfModGcd.cc:4019
return false
Definition: cfModGcd.cc:84
cl
Definition: cfModGcd.cc:4041
g
Definition: cfModGcd.cc:4031
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4042
bool equal
Definition: cfModGcd.cc:4067
CanonicalForm test
Definition: cfModGcd.cc:4037
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition: cf_chinese.cc:52
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
factory's class for variables
Definition: factory.h:118
int level() const
Definition: factory.h:134
CanonicalForm mipo
Definition: facAlgExt.cc:57
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
Definition: facMul.cc:342
bool isZero(const CFArray &A)
checks if entries of A are zero
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
static number Farey(number p, number n, const coeffs)
Definition: flintcf_Q.cc:441
#define D(A)
Definition: gentable.cc:131
#define R
Definition: sirandom.c:26
#define Q
Definition: sirandom.c:25
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ tryBrownGCD()

void tryBrownGCD ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M,
CanonicalForm result,
bool &  fail,
bool  topLevel = true 
)

modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true.

Definition at line 372 of file cfGcdAlgExt.cc.

373 { // assume F,G are multivariate polys over Z/p(a) for big prime p, M "univariate" polynomial in an algebraic variable
374  // M is assumed to be monic
375  if(F.isZero())
376  {
377  if(G.isZero())
378  {
379  result = G; // G is zero
380  return;
381  }
382  if(G.inCoeffDomain())
383  {
384  tryInvert(G,M,result,fail);
385  if(fail)
386  return;
387  result = 1;
388  return;
389  }
390  // try to make G monic modulo M
391  CanonicalForm inv;
392  tryInvert(Lc(G),M,inv,fail);
393  if(fail)
394  return;
395  result = inv*G;
396  result= reduce (result, M);
397  return;
398  }
399  if(G.isZero()) // F is non-zero
400  {
401  if(F.inCoeffDomain())
402  {
403  tryInvert(F,M,result,fail);
404  if(fail)
405  return;
406  result = 1;
407  return;
408  }
409  // try to make F monic modulo M
410  CanonicalForm inv;
411  tryInvert(Lc(F),M,inv,fail);
412  if(fail)
413  return;
414  result = inv*F;
415  result= reduce (result, M);
416  return;
417  }
418  // here: F,G both nonzero
419  if(F.inCoeffDomain())
420  {
421  tryInvert(F,M,result,fail);
422  if(fail)
423  return;
424  result = 1;
425  return;
426  }
427  if(G.inCoeffDomain())
428  {
429  tryInvert(G,M,result,fail);
430  if(fail)
431  return;
432  result = 1;
433  return;
434  }
435  TIMING_START (alg_compress)
436  CFMap MM,NN;
437  int lev= myCompress (F, G, MM, NN, topLevel);
438  if (lev == 0)
439  {
440  result= 1;
441  return;
442  }
443  CanonicalForm f=MM(F);
444  CanonicalForm g=MM(G);
445  TIMING_END_AND_PRINT (alg_compress, "time to compress in alg gcd: ")
446  // here: f,g are compressed
447  // compute largest variable in f or g (least one is Variable(1))
448  int mv = f.level();
449  if(g.level() > mv)
450  mv = g.level();
451  // here: mv is level of the largest variable in f, g
452  Variable v1= Variable (1);
453 #ifdef HAVE_NTL
454  Variable v= M.mvar();
456  {
458  zz_p::init (getCharacteristic());
459  }
460  zz_pX NTLMipo= convertFacCF2NTLzzpX (M);
461  zz_pE::init (NTLMipo);
462  zz_pEX NTLResult;
463  zz_pEX NTLF;
464  zz_pEX NTLG;
465 #endif
466  if(mv == 1) // f,g univariate
467  {
468  TIMING_START (alg_euclid_p)
469 #ifdef HAVE_NTL
470  NTLF= convertFacCF2NTLzz_pEX (f, NTLMipo);
471  NTLG= convertFacCF2NTLzz_pEX (g, NTLMipo);
472  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
473  if (fail)
474  return;
475  result= convertNTLzz_pEX2CF (NTLResult, f.mvar(), v);
476 #else
477  tryEuclid(f,g,M,result,fail);
478  if(fail)
479  return;
480 #endif
481  TIMING_END_AND_PRINT (alg_euclid_p, "time for euclidean alg mod p: ")
482  result= NN (reduce (result, M)); // do not forget to map back
483  return;
484  }
485  TIMING_START (alg_content_p)
486  // here: mv > 1
487  CanonicalForm cf = tryvcontent(f, Variable(2), M, fail); // cf is univariate poly in var(1)
488  if(fail)
489  return;
490  CanonicalForm cg = tryvcontent(g, Variable(2), M, fail);
491  if(fail)
492  return;
493  CanonicalForm c;
494 #ifdef HAVE_NTL
495  NTLF= convertFacCF2NTLzz_pEX (cf, NTLMipo);
496  NTLG= convertFacCF2NTLzz_pEX (cg, NTLMipo);
497  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
498  if (fail)
499  return;
500  c= convertNTLzz_pEX2CF (NTLResult, v1, v);
501 #else
502  tryEuclid(cf,cg,M,c,fail);
503  if(fail)
504  return;
505 #endif
506  // f /= cf
507  f.tryDiv (cf, M, fail);
508  if(fail)
509  return;
510  // g /= cg
511  g.tryDiv (cg, M, fail);
512  if(fail)
513  return;
514  TIMING_END_AND_PRINT (alg_content_p, "time for content in alg gcd mod p: ")
515  if(f.inCoeffDomain())
516  {
517  tryInvert(f,M,result,fail);
518  if(fail)
519  return;
520  result = NN(c);
521  return;
522  }
523  if(g.inCoeffDomain())
524  {
525  tryInvert(g,M,result,fail);
526  if(fail)
527  return;
528  result = NN(c);
529  return;
530  }
531  int *L = new int[mv+1]; // L is addressed by i from 2 to mv
532  int *N = new int[mv+1];
533  for(int i=2; i<=mv; i++)
534  L[i] = N[i] = 0;
535  L = leadDeg(f, L);
536  N = leadDeg(g, N);
537  CanonicalForm gamma;
538  TIMING_START (alg_euclid_p)
539 #ifdef HAVE_NTL
540  NTLF= convertFacCF2NTLzz_pEX (firstLC (f), NTLMipo);
541  NTLG= convertFacCF2NTLzz_pEX (firstLC (g), NTLMipo);
542  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
543  if (fail)
544  return;
545  gamma= convertNTLzz_pEX2CF (NTLResult, v1, v);
546 #else
547  tryEuclid( firstLC(f), firstLC(g), M, gamma, fail );
548  if(fail)
549  return;
550 #endif
551  TIMING_END_AND_PRINT (alg_euclid_p, "time for gcd of lcs in alg mod p: ")
552  for(int i=2; i<=mv; i++) // entries at i=0,1 not visited
553  if(N[i] < L[i])
554  L[i] = N[i];
555  // L is now upper bound for degrees of gcd
556  int *dg_im = new int[mv+1]; // for the degree vector of the image we don't need any entry at i=1
557  for(int i=2; i<=mv; i++)
558  dg_im[i] = 0; // initialize
559  CanonicalForm gamma_image, m=1;
560  CanonicalForm gm=0;
561  CanonicalForm g_image, alpha, gnew;
562  FFGenerator gen = FFGenerator();
563  Variable x= Variable (1);
564  bool divides= true;
565  for(FFGenerator gen = FFGenerator(); gen.hasItems(); gen.next())
566  {
567  alpha = gen.item();
568  gamma_image = reduce(gamma(alpha, x),M); // plug in alpha for var(1)
569  if(gamma_image.isZero()) // skip lc-bad points var(1)-alpha
570  continue;
571  TIMING_START (alg_recursion_p)
572  tryBrownGCD( f(alpha, x), g(alpha, x), M, g_image, fail, false ); // recursive call with one var less
573  TIMING_END_AND_PRINT (alg_recursion_p,
574  "time for recursive calls in alg gcd mod p: ")
575  if(fail)
576  return;
577  g_image = reduce(g_image, M);
578  if(g_image.inCoeffDomain()) // early termination
579  {
580  tryInvert(g_image,M,result,fail);
581  if(fail)
582  return;
583  result = NN(c);
584  return;
585  }
586  for(int i=2; i<=mv; i++)
587  dg_im[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
588  dg_im = leadDeg(g_image, dg_im); // dg_im cannot be NIL-pointer
589  if(isEqual(dg_im, L, 2, mv))
590  {
591  CanonicalForm inv;
592  tryInvert (firstLC (g_image), M, inv, fail);
593  if (fail)
594  return;
595  g_image *= inv;
596  g_image *= gamma_image; // multiply by multiple of image lc(gcd)
597  g_image= reduce (g_image, M);
598  TIMING_START (alg_newton_p)
599  gnew= tryNewtonInterp (alpha, g_image, m, gm, x, M, fail);
600  TIMING_END_AND_PRINT (alg_newton_p,
601  "time for Newton interpolation in alg gcd mod p: ")
602  // gnew = gm mod m
603  // gnew = g_image mod var(1)-alpha
604  // mnew = m * (var(1)-alpha)
605  if(fail)
606  return;
607  m *= (x - alpha);
608  if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
609  {
610  TIMING_START (alg_termination_p)
611  cf = tryvcontent(gnew, Variable(2), M, fail);
612  if(fail)
613  return;
614  divides = true;
615  g_image= gnew;
616  g_image.tryDiv (cf, M, fail);
617  if(fail)
618  return;
619  divides= tryFdivides (g_image,f, M, fail); // trial division (f)
620  if(fail)
621  return;
622  if(divides)
623  {
624  bool divides2= tryFdivides (g_image,g, M, fail); // trial division (g)
625  if(fail)
626  return;
627  if(divides2)
628  {
629  result = NN(reduce (c*g_image, M));
630  TIMING_END_AND_PRINT (alg_termination_p,
631  "time for successful termination test in alg gcd mod p: ")
632  return;
633  }
634  }
635  TIMING_END_AND_PRINT (alg_termination_p,
636  "time for unsuccessful termination test in alg gcd mod p: ")
637  }
638  gm = gnew;
639  continue;
640  }
641 
642  if(isLess(L, dg_im, 2, mv)) // dg_im > L --> current point unlucky
643  continue;
644 
645  // here: isLess(dg_im, L, 2, mv) --> all previous points were unlucky
646  m = CanonicalForm(1); // reset
647  gm = 0; // reset
648  for(int i=2; i<=mv; i++) // tighten bound
649  L[i] = dg_im[i];
650  }
651  // we are out of evaluation points
652  fail = true;
653 }
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
long fac_NTL_char
Definition: NTLconvert.cc:41
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition: cf_ops.cc:646
int level(const CanonicalForm &f)
int m
Definition: cfEzgcd.cc:121
const CanonicalForm CFMap CFMap & N
Definition: cfGcdAlgExt.cc:56
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:357
const CanonicalForm CFMap CFMap bool topLevel
Definition: cfGcdAlgExt.cc:57
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
CanonicalForm firstLC(const CanonicalForm &f)
Definition: cfGcdAlgExt.cc:956
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition: cfModGcd.cc:93
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm cf
Definition: cfModGcd.cc:4024
CanonicalForm cg
Definition: cfModGcd.cc:4024
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
class CFMap
Definition: cf_map.h:85
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
generate all elements in F_p starting from 0
Definition: cf_generator.h:56
Variable alpha
Definition: facAbsBiFact.cc:52
return result
Definition: facAbsBiFact.cc:76
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
ListNode * next
Definition: janet.h:31

◆ tryInvert()

void tryInvert ( const CanonicalForm F,
const CanonicalForm M,
CanonicalForm inv,
bool &  fail 
)

Definition at line 221 of file cfGcdAlgExt.cc.

222 { // F, M are required to be "univariate" polynomials in an algebraic variable
223  // we try to invert F modulo M
224  if(F.inBaseDomain())
225  {
226  if(F.isZero())
227  {
228  fail = true;
229  return;
230  }
231  inv = 1/F;
232  return;
233  }
235  Variable a = M.mvar();
236  Variable x = Variable(1);
237  if(!extgcd( replacevar( F, a, x ), replacevar( M, a, x ), inv, b ).isOne())
238  fail = true;
239  else
240  inv = replacevar( inv, x, a ); // change back to alg var
241 }
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:173
bool inBaseDomain() const