My Project
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 957 of file cfGcdAlgExt.cc.

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

◆ isEqual()

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

Definition at line 948 of file cfGcdAlgExt.cc.

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

◆ isLess()

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

Definition at line 937 of file cfGcdAlgExt.cc.

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

◆ leadDeg()

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

Definition at line 920 of file cfGcdAlgExt.cc.

921 { // leading degree vector w.r.t. lex. monomial order x(i+1) > x(i)
922  // if f is in a coeff domain, the zero pointer is returned
923  // 'a' should point to an array of sufficient size level(f)+1
924  if(f.inCoeffDomain())
925  return 0;
926  CanonicalForm tmp = f;
927  do
928  {
929  degs[tmp.level()] = tmp.degree();
930  tmp = LC(tmp);
931  }
932  while(!tmp.inCoeffDomain());
933  return degs;
934 }
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 716 of file cfGcdAlgExt.cc.

717 { // f,g in Q(a)[x1,...,xn]
718  if(F.isZero())
719  {
720  if(G.isZero())
721  return G; // G is zero
722  if(G.inCoeffDomain())
723  return CanonicalForm(1);
724  CanonicalForm lcinv= 1/Lc (G);
725  return G*lcinv; // return monic G
726  }
727  if(G.isZero()) // F is non-zero
728  {
729  if(F.inCoeffDomain())
730  return CanonicalForm(1);
731  CanonicalForm lcinv= 1/Lc (F);
732  return F*lcinv; // return monic F
733  }
734  if(F.inCoeffDomain() || G.inCoeffDomain())
735  return CanonicalForm(1);
736  // here: both NOT inCoeffDomain
737  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
738  int p, i;
739  int *bound, *other; // degree vectors
740  bool fail;
741  bool off_rational=!isOn(SW_RATIONAL);
742  On( SW_RATIONAL ); // needed by bCommonDen
743  f = F * bCommonDen(F);
744  g = G * bCommonDen(G);
746  CanonicalForm contf= myicontent (f);
747  CanonicalForm contg= myicontent (g);
748  f /= contf;
749  g /= contg;
750  CanonicalForm gcdcfcg= myicontent (contf, contg);
751  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
752  Variable a, b;
753  if(hasFirstAlgVar(f,a))
754  {
755  if(hasFirstAlgVar(g,b))
756  {
757  if(b.level() > a.level())
758  a = b;
759  }
760  }
761  else
762  {
763  if(!hasFirstAlgVar(g,a))// both not in extension
764  {
765  Off( SW_RATIONAL );
766  Off( SW_USE_QGCD );
767  tmp = gcdcfcg*gcd( f, g );
768  On( SW_USE_QGCD );
769  if (off_rational) Off(SW_RATIONAL);
770  return tmp;
771  }
772  }
773  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
774  setReduce(a,false); // do not reduce expressions modulo mipo
775  tmp = getMipo(a);
776  M = tmp * bCommonDen(tmp);
777  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
778  Off( SW_RATIONAL ); // needed by mod
779  // calculate upper bound for degree vector of gcd
780  int mv = f.level(); i = g.level();
781  if(i > mv)
782  mv = i;
783  // here: mv is level of the largest variable in f, g
784  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
785  other = new int[mv+1];
786  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
787  bound[i] = other[i] = 0;
788  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
789  other = leadDeg(g,other);
790  for(int i=1; i<=mv; i++) // entry at i=0 not visited
791  if(other[i] < bound[i])
792  bound[i] = other[i];
793  // now 'bound' is the smaller vector
794  cl = lc(M) * lc(f) * lc(g);
795  q = 1;
796  D = 0;
797  CanonicalForm test= 0;
798  bool equal= false;
799  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
800  {
801  p = cf_getBigPrime(i);
802  if( mod( cl, p ).isZero() ) // skip lc-bad primes
803  continue;
804  fail = false;
806  mipo = mapinto(M);
807  mipo /= mipo.lc();
808  // here: mipo is monic
809  TIMING_START (alg_gcd_p)
810  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
811  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
812  if( fail ) // mipo splits in char p
813  {
815  continue;
816  }
817  if( Dp.inCoeffDomain() ) // early termination
818  {
819  tryInvert(Dp,mipo,tmp,fail); // check if zero divisor
821  if(fail)
822  continue;
823  setReduce(a,true);
824  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
825  delete[] other;
826  delete[] bound;
827  return gcdcfcg;
828  }
830  // here: Dp NOT inCoeffDomain
831  for(int i=1; i<=mv; i++)
832  other[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
833  other = leadDeg(Dp,other);
834 
835  if(isEqual(bound, other, 1, mv)) // equal
836  {
837  chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
838  // tmp = Dp mod p
839  // tmp = D mod q
840  // newq = p*q
841  q = newq;
842  if( D != tmp )
843  D = tmp;
844  On( SW_RATIONAL );
845  TIMING_START (alg_reconstruction)
846  tmp = Farey( D, q ); // Farey
847  tmp *= bCommonDen (tmp);
848  TIMING_END_AND_PRINT (alg_reconstruction,
849  "time for rational reconstruction in alg gcd: ")
850  setReduce(a,true); // reduce expressions modulo mipo
851  On( SW_RATIONAL ); // needed by fdivides
852  if (test != tmp)
853  test= tmp;
854  else
855  equal= true; // modular image did not add any new information
856  TIMING_START (alg_termination)
857 #ifdef HAVE_NTL
858 #ifdef HAVE_FLINT
859  if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
860  && f.level() == tmp.level() && tmp.level() == g.level())
861  {
862  CanonicalForm Q, R;
863  newtonDivrem (f, tmp, Q, R);
864  if (R.isZero())
865  {
866  newtonDivrem (g, tmp, Q, R);
867  if (R.isZero())
868  {
869  Off (SW_RATIONAL);
870  setReduce (a,true);
871  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
872  TIMING_END_AND_PRINT (alg_termination,
873  "time for successful termination test in alg gcd: ")
874  delete[] other;
875  delete[] bound;
876  return tmp*gcdcfcg;
877  }
878  }
879  }
880  else
881 #endif
882 #endif
883  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
884  {
885  Off( SW_RATIONAL );
886  setReduce(a,true);
887  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
888  TIMING_END_AND_PRINT (alg_termination,
889  "time for successful termination test in alg gcd: ")
890  delete[] other;
891  delete[] bound;
892  return tmp*gcdcfcg;
893  }
894  TIMING_END_AND_PRINT (alg_termination,
895  "time for unsuccessful termination test in alg gcd: ")
896  Off( SW_RATIONAL );
897  setReduce(a,false); // do not reduce expressions modulo mipo
898  continue;
899  }
900  if( isLess(bound, other, 1, mv) ) // current prime unlucky
901  continue;
902  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
903  q = p;
904  D = mapinto(Dp); // shortcut CRA // shortcut CRA
905  for(int i=1; i<=mv; i++) // tighten bound
906  bound[i] = other[i];
907  }
908  // hopefully, we never reach this point
909  setReduce(a,true);
910  delete[] other;
911  delete[] bound;
912  Off( SW_USE_QGCD );
913  D = gcdcfcg*gcd( f, g );
914  On( SW_USE_QGCD );
915  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
916  return D;
917 }
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 FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm Lc(const CanonicalForm &f)
else
Definition: cfGcdAlgExt.cc:195
bool isLess(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:937
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:920
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:948
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:657
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:72
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:4080
return false
Definition: cfModGcd.cc:84
cl
Definition: cfModGcd.cc:4102
g
Definition: cfModGcd.cc:4092
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4103
bool equal
Definition: cfModGcd.cc:4128
CanonicalForm test
Definition: cfModGcd.cc:4098
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 FACTORY_PUBLIC 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:57
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:42
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
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
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
factory's class for variables
Definition: factory.h:134
int level() const
Definition: factory.h:150
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:346
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, number, const coeffs)
Definition: flintcf_Q.cc:445
#define D(A)
Definition: gentable.cc:131
STATIC_VAR jList * Q
Definition: janet.cc:30
#define R
Definition: sirandom.c:27
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();
455  int ch=getCharacteristic();
456  if (fac_NTL_char != ch)
457  {
458  fac_NTL_char= ch;
459  zz_p::init (ch);
460  }
461  zz_pX NTLMipo= convertFacCF2NTLzzpX (M);
462  zz_pE::init (NTLMipo);
463  zz_pEX NTLResult;
464  zz_pEX NTLF;
465  zz_pEX NTLG;
466 #endif
467  if(mv == 1) // f,g univariate
468  {
469  TIMING_START (alg_euclid_p)
470 #ifdef HAVE_NTL
471  NTLF= convertFacCF2NTLzz_pEX (f, NTLMipo);
472  NTLG= convertFacCF2NTLzz_pEX (g, NTLMipo);
473  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
474  if (fail)
475  return;
476  result= convertNTLzz_pEX2CF (NTLResult, f.mvar(), v);
477 #else
478  tryEuclid(f,g,M,result,fail);
479  if(fail)
480  return;
481 #endif
482  TIMING_END_AND_PRINT (alg_euclid_p, "time for euclidean alg mod p: ")
483  result= NN (reduce (result, M)); // do not forget to map back
484  return;
485  }
486  TIMING_START (alg_content_p)
487  // here: mv > 1
488  CanonicalForm cf = tryvcontent(f, Variable(2), M, fail); // cf is univariate poly in var(1)
489  if(fail)
490  return;
491  CanonicalForm cg = tryvcontent(g, Variable(2), M, fail);
492  if(fail)
493  return;
494  CanonicalForm c;
495 #ifdef HAVE_NTL
496  NTLF= convertFacCF2NTLzz_pEX (cf, NTLMipo);
497  NTLG= convertFacCF2NTLzz_pEX (cg, NTLMipo);
498  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
499  if (fail)
500  return;
501  c= convertNTLzz_pEX2CF (NTLResult, v1, v);
502 #else
503  tryEuclid(cf,cg,M,c,fail);
504  if(fail)
505  return;
506 #endif
507  // f /= cf
508  f.tryDiv (cf, M, fail);
509  if(fail)
510  return;
511  // g /= cg
512  g.tryDiv (cg, M, fail);
513  if(fail)
514  return;
515  TIMING_END_AND_PRINT (alg_content_p, "time for content in alg gcd mod p: ")
516  if(f.inCoeffDomain())
517  {
518  tryInvert(f,M,result,fail);
519  if(fail)
520  return;
521  result = NN(c);
522  return;
523  }
524  if(g.inCoeffDomain())
525  {
526  tryInvert(g,M,result,fail);
527  if(fail)
528  return;
529  result = NN(c);
530  return;
531  }
532  int *L = new int[mv+1]; // L is addressed by i from 2 to mv
533  int *N = new int[mv+1];
534  for(int i=2; i<=mv; i++)
535  L[i] = N[i] = 0;
536  L = leadDeg(f, L);
537  N = leadDeg(g, N);
538  CanonicalForm gamma;
539  TIMING_START (alg_euclid_p)
540 #ifdef HAVE_NTL
541  NTLF= convertFacCF2NTLzz_pEX (firstLC (f), NTLMipo);
542  NTLG= convertFacCF2NTLzz_pEX (firstLC (g), NTLMipo);
543  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
544  if (fail)
545  return;
546  gamma= convertNTLzz_pEX2CF (NTLResult, v1, v);
547 #else
548  tryEuclid( firstLC(f), firstLC(g), M, gamma, fail );
549  if(fail)
550  return;
551 #endif
552  TIMING_END_AND_PRINT (alg_euclid_p, "time for gcd of lcs in alg mod p: ")
553  for(int i=2; i<=mv; i++) // entries at i=0,1 not visited
554  if(N[i] < L[i])
555  L[i] = N[i];
556  // L is now upper bound for degrees of gcd
557  int *dg_im = new int[mv+1]; // for the degree vector of the image we don't need any entry at i=1
558  for(int i=2; i<=mv; i++)
559  dg_im[i] = 0; // initialize
560  CanonicalForm gamma_image, m=1;
561  CanonicalForm gm=0;
562  CanonicalForm g_image, alpha, gnew;
563  FFGenerator gen = FFGenerator();
564  Variable x= Variable (1);
565  bool divides= true;
566  for(FFGenerator gen = FFGenerator(); gen.hasItems(); gen.next())
567  {
568  alpha = gen.item();
569  gamma_image = reduce(gamma(alpha, x),M); // plug in alpha for var(1)
570  if(gamma_image.isZero()) // skip lc-bad points var(1)-alpha
571  continue;
572  TIMING_START (alg_recursion_p)
573  tryBrownGCD( f(alpha, x), g(alpha, x), M, g_image, fail, false ); // recursive call with one var less
574  TIMING_END_AND_PRINT (alg_recursion_p,
575  "time for recursive calls in alg gcd mod p: ")
576  if(fail)
577  return;
578  g_image = reduce(g_image, M);
579  if(g_image.inCoeffDomain()) // early termination
580  {
581  tryInvert(g_image,M,result,fail);
582  if(fail)
583  return;
584  result = NN(c);
585  return;
586  }
587  for(int i=2; i<=mv; i++)
588  dg_im[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
589  dg_im = leadDeg(g_image, dg_im); // dg_im cannot be NIL-pointer
590  if(isEqual(dg_im, L, 2, mv))
591  {
592  CanonicalForm inv;
593  tryInvert (firstLC (g_image), M, inv, fail);
594  if (fail)
595  return;
596  g_image *= inv;
597  g_image *= gamma_image; // multiply by multiple of image lc(gcd)
598  g_image= reduce (g_image, M);
599  TIMING_START (alg_newton_p)
600  gnew= tryNewtonInterp (alpha, g_image, m, gm, x, M, fail);
601  TIMING_END_AND_PRINT (alg_newton_p,
602  "time for Newton interpolation in alg gcd mod p: ")
603  // gnew = gm mod m
604  // gnew = g_image mod var(1)-alpha
605  // mnew = m * (var(1)-alpha)
606  if(fail)
607  return;
608  m *= (x - alpha);
609  if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
610  {
611  TIMING_START (alg_termination_p)
612  cf = tryvcontent(gnew, Variable(2), M, fail);
613  if(fail)
614  return;
615  divides = true;
616  g_image= gnew;
617  g_image.tryDiv (cf, M, fail);
618  if(fail)
619  return;
620  divides= tryFdivides (g_image,f, M, fail); // trial division (f)
621  if(fail)
622  return;
623  if(divides)
624  {
625  bool divides2= tryFdivides (g_image,g, M, fail); // trial division (g)
626  if(fail)
627  return;
628  if(divides2)
629  {
630  result = NN(reduce (c*g_image, M));
631  TIMING_END_AND_PRINT (alg_termination_p,
632  "time for successful termination test in alg gcd mod p: ")
633  return;
634  }
635  }
636  TIMING_END_AND_PRINT (alg_termination_p,
637  "time for unsuccessful termination test in alg gcd mod p: ")
638  }
639  gm = gnew;
640  continue;
641  }
642 
643  if(isLess(L, dg_im, 2, mv)) // dg_im > L --> current point unlucky
644  continue;
645 
646  // here: isLess(dg_im, L, 2, mv) --> all previous points were unlucky
647  m = CanonicalForm(1); // reset
648  gm = 0; // reset
649  for(int i=2; i<=mv; i++) // tighten bound
650  L[i] = dg_im[i];
651  }
652  // we are out of evaluation points
653  fail = true;
654 }
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1092
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
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:660
int level(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int m
Definition: cfEzgcd.cc:128
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:957
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:4084
CanonicalForm cf
Definition: cfModGcd.cc:4085
CanonicalForm cg
Definition: cfModGcd.cc:4085
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:51
return result
Definition: facAbsBiFact.cc:75
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
ListNode * next
Definition: janet.h:31
void init()
Definition: lintree.cc:864

◆ 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 FACTORY_PUBLIC 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:174
bool inBaseDomain() const