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 946 of file cfGcdAlgExt.cc.

947 { // returns the leading coefficient (LC) of level <= 1
948  CanonicalForm ret = f;
949  while(ret.level() > 1)
950  ret = LC(ret);
951  return ret;
952 }
factory&#39;s main class
Definition: canonicalform.h:75
FILE * f
Definition: checklibs.c:7
int level() const
level() returns the level of CO.
CanonicalForm LC(const CanonicalForm &f)

§ isEqual()

bool isEqual ( 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=lower; i<=upper; i++)
940  if(a[i] != b[i])
941  return false;
942  return true;
943 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213

§ isLess()

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

Definition at line 926 of file cfGcdAlgExt.cc.

927 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
928  for(int i=upper; i>=lower; i--)
929  if(a[i] == b[i])
930  continue;
931  else
932  return a[i] < b[i];
933  return true;
934 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
const poly b
Definition: syzextra.cc:213

§ leadDeg()

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

Definition at line 909 of file cfGcdAlgExt.cc.

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

§ QGCD()

gcd over Q(a)

Definition at line 713 of file cfGcdAlgExt.cc.

714 { // f,g in Q(a)[x1,...,xn]
715  if(F.isZero())
716  {
717  if(G.isZero())
718  return G; // G is zero
719  if(G.inCoeffDomain())
720  return CanonicalForm(1);
721  CanonicalForm lcinv= 1/Lc (G);
722  return G*lcinv; // return monic G
723  }
724  if(G.isZero()) // F is non-zero
725  {
726  if(F.inCoeffDomain())
727  return CanonicalForm(1);
728  CanonicalForm lcinv= 1/Lc (F);
729  return F*lcinv; // return monic F
730  }
731  if(F.inCoeffDomain() || G.inCoeffDomain())
732  return CanonicalForm(1);
733  // here: both NOT inCoeffDomain
734  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
735  int p, i;
736  int *bound, *other; // degree vectors
737  bool fail;
738  bool off_rational=!isOn(SW_RATIONAL);
739  On( SW_RATIONAL ); // needed by bCommonDen
740  f = F * bCommonDen(F);
741  g = G * bCommonDen(G);
743  CanonicalForm contf= myicontent (f);
744  CanonicalForm contg= myicontent (g);
745  f /= contf;
746  g /= contg;
747  CanonicalForm gcdcfcg= myicontent (contf, contg);
748  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
749  Variable a, b;
750  if(hasFirstAlgVar(f,a))
751  {
752  if(hasFirstAlgVar(g,b))
753  {
754  if(b.level() > a.level())
755  a = b;
756  }
757  }
758  else
759  {
760  if(!hasFirstAlgVar(g,a))// both not in extension
761  {
762  Off( SW_RATIONAL );
763  Off( SW_USE_QGCD );
764  tmp = gcdcfcg*gcd( f, g );
765  On( SW_USE_QGCD );
766  if (off_rational) Off(SW_RATIONAL);
767  return tmp;
768  }
769  }
770  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
771  setReduce(a,false); // do not reduce expressions modulo mipo
772  tmp = getMipo(a);
773  M = tmp * bCommonDen(tmp);
774  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
775  Off( SW_RATIONAL ); // needed by mod
776  // calculate upper bound for degree vector of gcd
777  int mv = f.level(); i = g.level();
778  if(i > mv)
779  mv = i;
780  // here: mv is level of the largest variable in f, g
781  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
782  other = new int[mv+1];
783  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
784  bound[i] = other[i] = 0;
785  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
786  other = leadDeg(g,other);
787  for(int i=1; i<=mv; i++) // entry at i=0 not visited
788  if(other[i] < bound[i])
789  bound[i] = other[i];
790  // now 'bound' is the smaller vector
791  cl = lc(M) * lc(f) * lc(g);
792  q = 1;
793  D = 0;
794  CanonicalForm test= 0;
795  bool equal= false;
796  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
797  {
798  p = cf_getBigPrime(i);
799  if( mod( cl, p ).isZero() ) // skip lc-bad primes
800  continue;
801  fail = false;
803  mipo = mapinto(M);
804  mipo /= mipo.lc();
805  // here: mipo is monic
806  TIMING_START (alg_gcd_p)
807  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
808  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
809  if( fail ) // mipo splits in char p
810  {
812  continue;
813  }
814  if( Dp.inCoeffDomain() ) // early termination
815  {
816  tryInvert(Dp,mipo,tmp,fail); // check if zero divisor
818  if(fail)
819  continue;
820  setReduce(a,true);
821  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
822  return gcdcfcg;
823  }
825  // here: Dp NOT inCoeffDomain
826  for(int i=1; i<=mv; i++)
827  other[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
828  other = leadDeg(Dp,other);
829 
830  if(isEqual(bound, other, 1, mv)) // equal
831  {
832  chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
833  // tmp = Dp mod p
834  // tmp = D mod q
835  // newq = p*q
836  q = newq;
837  if( D != tmp )
838  D = tmp;
839  On( SW_RATIONAL );
840  TIMING_START (alg_reconstruction)
841  tmp = Farey( D, q ); // Farey
842  tmp *= bCommonDen (tmp);
843  TIMING_END_AND_PRINT (alg_reconstruction,
844  "time for rational reconstruction in alg gcd: ")
845  setReduce(a,true); // reduce expressions modulo mipo
846  On( SW_RATIONAL ); // needed by fdivides
847  if (test != tmp)
848  test= tmp;
849  else
850  equal= true; // modular image did not add any new information
851  TIMING_START (alg_termination)
852 #ifdef HAVE_NTL
853 #ifdef HAVE_FLINT
854  if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
855  && f.level() == tmp.level() && tmp.level() == g.level())
856  {
857  CanonicalForm Q, R;
858  newtonDivrem (f, tmp, Q, R);
859  if (R.isZero())
860  {
861  newtonDivrem (g, tmp, Q, R);
862  if (R.isZero())
863  {
864  Off (SW_RATIONAL);
865  setReduce (a,true);
866  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
867  TIMING_END_AND_PRINT (alg_termination,
868  "time for successful termination test in alg gcd: ")
869  return tmp*gcdcfcg;
870  }
871  }
872  }
873  else
874 #endif
875 #endif
876  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
877  {
878  Off( SW_RATIONAL );
879  setReduce(a,true);
880  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
881  TIMING_END_AND_PRINT (alg_termination,
882  "time for successful termination test in alg gcd: ")
883  return tmp*gcdcfcg;
884  }
885  TIMING_END_AND_PRINT (alg_termination,
886  "time for unsuccessful termination test in alg gcd: ")
887  Off( SW_RATIONAL );
888  setReduce(a,false); // do not reduce expressions modulo mipo
889  continue;
890  }
891  if( isLess(bound, other, 1, mv) ) // current prime unlucky
892  continue;
893  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
894  q = p;
895  D = mapinto(Dp); // shortcut CRA // shortcut CRA
896  for(int i=1; i<=mv; i++) // tighten bound
897  bound[i] = other[i];
898  }
899  // hopefully, we never reach this point
900  setReduce(a,true);
901  Off( SW_USE_QGCD );
902  D = gcdcfcg*gcd( f, g );
903  On( SW_USE_QGCD );
904  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
905  return D;
906 }
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:654
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
#define D(A)
Definition: gentable.cc:121
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
#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
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
cl
Definition: cfModGcd.cc:4041
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
#define Q
Definition: sirandom.c:25
CanonicalForm Lc(const CanonicalForm &f)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:219
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setCharacteristic(int c)
Definition: cf_char.cc:23
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:55
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:926
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
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:73
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:937
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:193
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:470
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:370
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4042
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:909
const poly b
Definition: syzextra.cc:213
return
Definition: cfGcdAlgExt.cc:216
bool inCoeffDomain() const

§ 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 370 of file cfGcdAlgExt.cc.

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

§ tryInvert()

void tryInvert ( const CanonicalForm ,
const CanonicalForm ,
CanonicalForm ,
bool &   
)

Definition at line 219 of file cfGcdAlgExt.cc.

220 { // F, M are required to be "univariate" polynomials in an algebraic variable
221  // we try to invert F modulo M
222  if(F.inBaseDomain())
223  {
224  if(F.isZero())
225  {
226  fail = true;
227  return;
228  }
229  inv = 1/F;
230  return;
231  }
233  Variable a = M.mvar();
234  Variable x = Variable(1);
235  if(!extgcd( replacevar( F, a, x ), replacevar( M, a, x ), inv, b ).isOne())
236  fail = true;
237  else
238  inv = replacevar( inv, x, a ); // change back to alg var
239 }
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:55
factory&#39;s main class
Definition: canonicalform.h:75
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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