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

CanonicalForm firstLC ( const CanonicalForm f)

Definition at line 950 of file cfGcdAlgExt.cc.

951 { // returns the leading coefficient (LC) of level <= 1
952  CanonicalForm ret = f;
953  while(ret.level() > 1)
954  ret = LC(ret);
955  return ret;
956 }
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
FILE * f
Definition: checklibs.c:7
CanonicalForm LC(const CanonicalForm &f)
bool isEqual ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 941 of file cfGcdAlgExt.cc.

942 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
943  for(int i=lower; i<=upper; i++)
944  if(a[i] != b[i])
945  return false;
946  return true;
947 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213
bool isLess ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 930 of file cfGcdAlgExt.cc.

931 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
932  for(int i=upper; i>=lower; i--)
933  if(a[i] == b[i])
934  continue;
935  else
936  return a[i] < b[i];
937  return true;
938 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213
int* leadDeg ( const CanonicalForm f,
int *  degs 
)

Definition at line 913 of file cfGcdAlgExt.cc.

914 { // leading degree vector w.r.t. lex. monomial order x(i+1) > x(i)
915  // if f is in a coeff domain, the zero pointer is returned
916  // 'a' should point to an array of sufficient size level(f)+1
917  if(f.inCoeffDomain())
918  return 0;
919  CanonicalForm tmp = f;
920  do
921  {
922  degs[tmp.level()] = tmp.degree();
923  tmp = LC(tmp);
924  }
925  while(!tmp.inCoeffDomain());
926  return degs;
927 }
bool inCoeffDomain() const
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
FILE * f
Definition: checklibs.c:7
CanonicalForm LC(const CanonicalForm &f)

gcd over Q(a)

Definition at line 720 of file cfGcdAlgExt.cc.

721 { // f,g in Q(a)[x1,...,xn]
722  if(F.isZero())
723  {
724  if(G.isZero())
725  return G; // G is zero
726  if(G.inCoeffDomain())
727  return CanonicalForm(1);
728  CanonicalForm lcinv= 1/Lc (G);
729  return G*lcinv; // return monic G
730  }
731  if(G.isZero()) // F is non-zero
732  {
733  if(F.inCoeffDomain())
734  return CanonicalForm(1);
735  CanonicalForm lcinv= 1/Lc (F);
736  return F*lcinv; // return monic F
737  }
738  if(F.inCoeffDomain() || G.inCoeffDomain())
739  return CanonicalForm(1);
740  // here: both NOT inCoeffDomain
741  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
742  int p, i;
743  int *bound, *other; // degree vectors
744  bool fail;
745  bool off_rational=!isOn(SW_RATIONAL);
746  On( SW_RATIONAL ); // needed by bCommonDen
747  f = F * bCommonDen(F);
748  g = G * bCommonDen(G);
750  CanonicalForm contf= myicontent (f);
751  CanonicalForm contg= myicontent (g);
752  f /= contf;
753  g /= contg;
754  CanonicalForm gcdcfcg= myicontent (contf, contg);
755  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
756  Variable a, b;
757  if(hasFirstAlgVar(f,a))
758  {
759  if(hasFirstAlgVar(g,b))
760  {
761  if(b.level() > a.level())
762  a = b;
763  }
764  }
765  else
766  {
767  if(!hasFirstAlgVar(g,a))// both not in extension
768  {
769  Off( SW_RATIONAL );
770  Off( SW_USE_QGCD );
771  tmp = gcdcfcg*gcd( f, g );
772  On( SW_USE_QGCD );
773  if (off_rational) Off(SW_RATIONAL);
774  return tmp;
775  }
776  }
777  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
778  setReduce(a,false); // do not reduce expressions modulo mipo
779  tmp = getMipo(a);
780  M = tmp * bCommonDen(tmp);
781  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
782  Off( SW_RATIONAL ); // needed by mod
783  // calculate upper bound for degree vector of gcd
784  int mv = f.level(); i = g.level();
785  if(i > mv)
786  mv = i;
787  // here: mv is level of the largest variable in f, g
788  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
789  other = new int[mv+1];
790  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
791  bound[i] = other[i] = 0;
792  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
793  other = leadDeg(g,other);
794  for(int i=1; i<=mv; i++) // entry at i=0 not visited
795  if(other[i] < bound[i])
796  bound[i] = other[i];
797  // now 'bound' is the smaller vector
798  cl = lc(M) * lc(f) * lc(g);
799  q = 1;
800  D = 0;
801  CanonicalForm test= 0;
802  bool equal= false;
803  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
804  {
805  p = cf_getBigPrime(i);
806  if( mod( cl, p ).isZero() ) // skip lc-bad primes
807  continue;
808  fail = false;
810  mipo = mapinto(M);
811  mipo /= mipo.lc();
812  // here: mipo is monic
813  TIMING_START (alg_gcd_p)
814  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
815  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
816  if( fail ) // mipo splits in char p
817  continue;
818  if( Dp.inCoeffDomain() ) // early termination
819  {
820  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);
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  return tmp*gcdcfcg;
874  }
875  }
876  }
877  else
878 #endif
879 #endif
880  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
881  {
882  Off( SW_RATIONAL );
883  setReduce(a,true);
884  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
885  TIMING_END_AND_PRINT (alg_termination,
886  "time for successful termination test in alg gcd: ")
887  return tmp*gcdcfcg;
888  }
889  TIMING_END_AND_PRINT (alg_termination,
890  "time for unsuccessful termination test in alg gcd: ")
891  Off( SW_RATIONAL );
892  setReduce(a,false); // do not reduce expressions modulo mipo
893  continue;
894  }
895  if( isLess(bound, other, 1, mv) ) // current prime unlucky
896  continue;
897  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
898  q = p;
899  D = mapinto(Dp); // shortcut CRA // shortcut CRA
900  for(int i=1; i<=mv; i++) // tighten bound
901  bound[i] = other[i];
902  }
903  // hopefully, we never reach this point
904  setReduce(a,true);
905  Off( SW_USE_QGCD );
906  D = gcdcfcg*gcd( f, g );
907  On( SW_USE_QGCD );
908  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
909  return D;
910 }
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:660
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
#define D(A)
Definition: gentable.cc:119
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:66
const poly a
Definition: syzextra.cc:212
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
void Off(int sw)
switches
bool inCoeffDomain() const
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
cl
Definition: cfModGcd.cc:4041
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:56
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
#define Q
Definition: sirandom.c:25
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm Lc(const CanonicalForm &f)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:220
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:56
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CanonicalForm lc(const CanonicalForm &f)
bool equal
Definition: cfModGcd.cc:4067
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
bool isLess(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:930
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
const ring R
Definition: DebugPrint.cc:36
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CFList reconstruction(CanonicalForm &G, CFList &factors, int *zeroOneVecs, int precision, const mat_zz_pE &N, const CanonicalForm &eval)
Definition: facFqBivar.cc:1809
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
return false
Definition: cfModGcd.cc:84
bool isOn(int sw)
switches
void On(int sw)
switches
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:913
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
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, satisfying F=G*Q+R, deg(R) < deg(G)
Definition: facMul.cc:342
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
if(topLevel)
Definition: cfGcdAlgExt.cc:74
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:941
CanonicalForm test
Definition: cfModGcd.cc:4037
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
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
else
Definition: cfGcdAlgExt.cc:194
int gcd(int a, int b)
Definition: walkSupport.cc:839
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
#define TIMING_START(t)
Definition: timing.h:87
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
static number Farey(number p, number n, const coeffs)
Definition: flintcf_Q.cc:473
bool isZero(const CFArray &A)
checks if entries of A are zero
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
Definition: cfGcdAlgExt.cc:376
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4042
const poly b
Definition: syzextra.cc:213
return
Definition: cfGcdAlgExt.cc:217
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 376 of file cfGcdAlgExt.cc.

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

Definition at line 220 of file cfGcdAlgExt.cc.

221 { // F, M are required to be "univariate" polynomials in an algebraic variable
222  // we try to invert F modulo M
223  if(F.inBaseDomain())
224  {
225  if(F.isZero())
226  {
227  fail = true;
228  return;
229  }
230  inv = 1/F;
231  return;
232  }
234  Variable a = M.mvar();
235  Variable x = Variable(1);
236  if(!extgcd( replacevar( F, a, x ), replacevar( M, a, x ), inv, b ).isOne())
237  fail = true;
238  else
239  inv = replacevar( inv, x, a ); // change back to alg var
240 }
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
const poly a
Definition: syzextra.cc:212
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
factory&#39;s class for variables
Definition: factory.h:115
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:56
factory&#39;s main class
Definition: canonicalform.h:75
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
const poly b
Definition: syzextra.cc:213