My Project  debian-1:4.1.1-p2+ds-4build1
Functions | Variables
cfEzgcd.cc File Reference
#include "config.h"
#include "timing.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cfEzgcd.h"
#include "cfModGcd.h"
#include "cf_util.h"
#include "cf_map_ext.h"
#include "cf_algorithm.h"
#include "cf_reval.h"
#include "cf_random.h"
#include "cf_primes.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "facHensel.h"
#include "NTLconvert.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (ez_eval) TIMING_DEFINE_PRINT(ez_compress) TIMING_DEFINE_PRINT(ez_hensel_lift) TIMING_DEFINE_PRINT(ez_content) TIMING_DEFINE_PRINT(ez_termination) static int compress4EZGCD(const CanonicalForm &F
 
 for (int i=0;i<=n;i++) degsf[i]
 
 if (both_non_zero==0)
 
 while (k > 0)
 
 DELETE_ARRAY (degsf)
 
 DELETE_ARRAY (degsg)
 
static CanonicalForm myShift2Zero (const CanonicalForm &F, CFList &Feval, const CFList &evaluation)
 
static CanonicalForm myReverseShift (const CanonicalForm &F, const CFList &evaluation)
 
static Evaluation optimize4Lift (const CanonicalForm &F, CFMap &M, CFMap &N, const Evaluation &A)
 
static int Hensel (const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
 
static bool findeval (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Fb, CanonicalForm &Gb, CanonicalForm &Db, REvaluation &b, int delta, int degF, int degG, int maxeval, int &count, int &k, int bound, int &l)
 
static CanonicalForm ezgcd (const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
 real implementation of EZGCD over Z More...
 
CanonicalForm ezgcd (const CanonicalForm &FF, const CanonicalForm &GG)
 Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm. More...
 
CanonicalForm EZGCD_P (const CanonicalForm &FF, const CanonicalForm &GG)
 Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm. More...
 

Variables

static const double log2exp = 1.442695041
 
const CanonicalFormG
 
const CanonicalForm CFMapM
 
const CanonicalForm CFMap CFMapN
 
const CanonicalForm CFMap CFMap int & both_non_zero
 
int * degsf = NEW_ARRAY(int,n + 1)
 
int * degsg = NEW_ARRAY(int,n + 1)
 
int f_zero = 0
 
int g_zero = 0
 
int k = 1
 
int l = 1
 
int Flevel =F.level()
 
int Glevel =G.level()
 
int m = tmin (Flevel, Glevel)
 
int max_min_deg
 
int i = 1
 
static int maxNumEval = 200
 
static int sizePerVars1 = 500
 

Detailed Description

This file implements the GCD of two multivariate polynomials over Q or F_q using EZ-GCD as described in "Algorithms for Computer Algebra" by Geddes, Czapor, Labahnn

Author
Martin Lee

Definition in file cfEzgcd.cc.

Function Documentation

◆ DELETE_ARRAY() [1/2]

DELETE_ARRAY ( degsf  )

◆ DELETE_ARRAY() [2/2]

DELETE_ARRAY ( degsg  )

◆ ezgcd() [1/2]

CanonicalForm ezgcd ( const CanonicalForm FF,
const CanonicalForm GG 
)

Extended Zassenhaus GCD over Z. In case things become too dense we switch to a modular algorithm.

Definition at line 796 of file cfEzgcd.cc.

797 {
798 #ifdef HAVE_NTL
799  REvaluation b;
800  return ezgcd( FF, GG, b, false );
801 #else
802  Off (SW_USE_EZGCD);
803  return gcd (FF, GG);
804  On (SW_USE_EZGCD);
805 #endif
806 }

◆ ezgcd() [2/2]

static CanonicalForm ezgcd ( const CanonicalForm FF,
const CanonicalForm GG,
REvaluation b,
bool  internal 
)
static

real implementation of EZGCD over Z

—> A2

—> A3

—> A4

—> A5

—> A6

—> A7

—> A8 (gcdfound)

—> A9

Definition at line 441 of file cfEzgcd.cc.

443 {
444  bool isRat= isOn (SW_RATIONAL);
445 
446  int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
447  int sizeF= size (FF);
448  int sizeG= size (GG);
449 
450 
451  if ((sizeF==1) || (sizeG==1))
452  {
453  Off(SW_USE_EZGCD);
454  CanonicalForm result=gcd( FF, GG );
455  On(SW_USE_EZGCD);
456  return result;
457  }
458  if (!isRat)
459  On (SW_RATIONAL);
460  if (sizeF/maxNumVars > 500 && sizeG/maxNumVars > 500)
461  {
462  Off(SW_USE_EZGCD);
463  CanonicalForm result=gcd( FF, GG );
464  On(SW_USE_EZGCD);
465  if (!isRat)
466  Off (SW_RATIONAL);
467  result /= icontent (result);
468  DEBDECLEVEL( cerr, "ezgcd" );
469  return result;
470  }
471 
472 
473  CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
474  lcD, cand, contcand, result;
475  CFArray DD( 1, 2 ), lcDD( 1, 2 );
476  int degF, degG, delta, t, count, maxeval;
477  REvaluation bt;
478  int gcdfound = 0;
479  Variable x = Variable(1);
480  count= 0;
481  maxeval= 200;
482  int o, l;
483  o= 0;
484  l= 1;
485 
486  if (!isRat)
487  On (SW_RATIONAL);
488  F= FF*bCommonDen (FF);
489  G= GG*bCommonDen (GG);
490  if (!isRat)
491  Off (SW_RATIONAL);
492 
493  TIMING_START (ez_compress)
494  CFMap M,N;
495  int smallestDegLev;
496  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
497 
498  if (best_level == 0)
499  {
500  DEBDECLEVEL( cerr, "ezgcd" );
501  return G.genOne();
502  }
503 
504  F= M (F);
505  G= M (G);
506  TIMING_END_AND_PRINT (ez_compress, "time for compression in EZ: ")
507 
508  DEBINCLEVEL( cerr, "ezgcd" );
509  DEBOUTLN( cerr, "FF = " << FF );
510  DEBOUTLN( cerr, "GG = " << GG );
511  TIMING_START (ez_content)
512  f = content( F, x ); g = content( G, x ); d = gcd( f, g );
513  DEBOUTLN( cerr, "f = " << f );
514  DEBOUTLN( cerr, "g = " << g );
515  F /= f; G /= g;
516  TIMING_END_AND_PRINT (ez_content, "time to extract content in EZ: ")
517  if ( F.isUnivariate() )
518  {
519  if ( G.isUnivariate() )
520  {
521  DEBDECLEVEL( cerr, "ezgcd" );
522  if(F.mvar()==G.mvar())
523  d*=gcd(F,G);
524  else
525  return N (d);
526  return N (d);
527  }
528  else
529  {
530  g= content (G,G.mvar());
531  return N(d*gcd(F,g));
532  }
533  }
534  if ( G.isUnivariate())
535  {
536  f= content (F,F.mvar());
537  return N(d*gcd(G,f));
538  }
539 
541  sizeF= size (F);
542  sizeG= size (G);
543 
544  if (!isRat)
545  On (SW_RATIONAL);
546  if (sizeF/maxNumVars > 500 && sizeG/maxNumVars > 500)
547  {
548  Off(SW_USE_EZGCD);
549  result=gcd( F, G );
550  On(SW_USE_EZGCD);
551  if (!isRat)
552  Off (SW_RATIONAL);
553  result /= icontent (result);
554  DEBDECLEVEL( cerr, "ezgcd" );
555  return N (d*result);
556  }
557 
558  int dummy= 0;
559  if ( gcd_test_one( F, G, false, dummy ) )
560  {
561  DEBDECLEVEL( cerr, "ezgcd" );
562  if (!isRat)
563  Off (SW_RATIONAL);
564  return N (d);
565  }
566  lcF = LC( F, x ); lcG = LC( G, x );
567  lcD = gcd( lcF, lcG );
568  delta = 0;
569  degF = degree( F, x ); degG = degree( G, x );
570  t = tmax( F.level(), G.level() );
571  if ( ! internal )
572  b = REvaluation( 2, t, IntRandom( 25 ) );
573  while ( ! gcdfound )
574  {
575  /// ---> A2
576  DEBOUTLN( cerr, "search for evaluation, delta = " << delta );
577  DEBOUTLN( cerr, "F = " << F );
578  DEBOUTLN( cerr, "G = " << G );
579  TIMING_START (ez_eval)
580  if (!findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count,
581  o, 25, l))
582  {
583  Off(SW_USE_EZGCD);
584  result=gcd( F, G );
585  On(SW_USE_EZGCD);
586  if (!isRat)
587  Off (SW_RATIONAL);
588  DEBDECLEVEL( cerr, "ezgcd" );
589  result /= icontent (result);
590  return N (d*result);
591  }
592  TIMING_END_AND_PRINT (ez_eval, "time to find eval point in EZ1: ")
593  DEBOUTLN( cerr, "found evaluation b = " << b );
594  DEBOUTLN( cerr, "F(b) = " << Fb );
595  DEBOUTLN( cerr, "G(b) = " << Gb );
596  DEBOUTLN( cerr, "D(b) = " << Db );
597  delta = degree( Db );
598  /// ---> A3
599  if (delta == degF)
600  {
601  if (degF <= degG && fdivides (F, G))
602  {
603  DEBDECLEVEL( cerr, "ezgcd" );
604  if (!isRat)
605  Off (SW_RATIONAL);
606  return N (d*F);
607  }
608  else
609  delta--;
610  }
611  else if (delta == degG)
612  {
613  if (degG <= degF && fdivides( G, F ))
614  {
615  DEBDECLEVEL( cerr, "ezgcd" );
616  if (!isRat)
617  Off (SW_RATIONAL);
618  return N (d*G);
619  }
620  else
621  delta--;
622  }
623  if ( delta == 0 )
624  {
625  DEBDECLEVEL( cerr, "ezgcd" );
626  if (!isRat)
627  Off (SW_RATIONAL);
628  return N (d);
629  }
630  /// ---> A4
631  //deltaold = delta;
632  while ( 1 )
633  {
634  bt = b;
635  TIMING_START (ez_eval)
636  if (!findeval( F, G, Fbt, Gbt, Dbt, bt, delta, degF, degG, maxeval, count,
637  o, 25,l ))
638  {
639  Off(SW_USE_EZGCD);
640  result=gcd( F, G );
641  On(SW_USE_EZGCD);
642  if (!isRat)
643  Off (SW_RATIONAL);
644  DEBDECLEVEL( cerr, "ezgcd" );
645  result /= icontent (result);
646  return N (d*result);
647  }
648  TIMING_END_AND_PRINT (ez_eval, "time to find eval point in EZ2: ")
649  int dd=degree( Dbt );
650  if ( dd /*degree( Dbt )*/ == 0 )
651  {
652  DEBDECLEVEL( cerr, "ezgcd" );
653  if (!isRat)
654  Off (SW_RATIONAL);
655  return N (d);
656  }
657  if ( dd /*degree( Dbt )*/ == delta )
658  break;
659  else if ( dd /*degree( Dbt )*/ < delta )
660  {
661  delta = dd /*degree( Dbt )*/;
662  b = bt;
663  Db = Dbt; Fb = Fbt; Gb = Gbt;
664  }
665  DEBOUTLN( cerr, "now after A4, delta = " << delta );
666  /// ---> A5
667  if (delta == degF)
668  {
669  if (degF <= degG && fdivides (F, G))
670  {
671  DEBDECLEVEL( cerr, "ezgcd" );
672  if (!isRat)
673  Off (SW_RATIONAL);
674  return N (d*F);
675  }
676  else
677  delta--;
678  }
679  else if (delta == degG)
680  {
681  if (degG <= degF && fdivides( G, F ))
682  {
683  DEBDECLEVEL( cerr, "ezgcd" );
684  if (!isRat)
685  Off (SW_RATIONAL);
686  return N (d*G);
687  }
688  else
689  delta--;
690  }
691  if ( delta == 0 )
692  {
693  DEBDECLEVEL( cerr, "ezgcd" );
694  if (!isRat)
695  Off (SW_RATIONAL);
696  return N (d);
697  }
698  }
699  if ( delta != degF && delta != degG )
700  {
701  /// ---> A6
702  bool B_is_F;
703  CanonicalForm xxx1, xxx2;
705  DD[1] = Fb / Db;
706  buf= Gb/Db;
707  xxx1 = gcd( DD[1], Db );
708  xxx2 = gcd( buf, Db );
709  if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
710  (size (F) <= size (G)))
711  || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
712  {
713  B = F;
714  DD[2] = Db;
715  lcDD[1] = lcF;
716  lcDD[2] = lcD;
717  B_is_F = true;
718  }
719  else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
720  (size (G) < size (F)))
721  || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
722  {
723  DD[1] = buf;
724  B = G;
725  DD[2] = Db;
726  lcDD[1] = lcG;
727  lcDD[2] = lcD;
728  B_is_F = false;
729  }
730  else
731  {
732  //special case
733  Off(SW_USE_EZGCD);
734  result=gcd( F, G );
735  On(SW_USE_EZGCD);
736  if (!isRat)
737  Off (SW_RATIONAL);
738  DEBDECLEVEL( cerr, "ezgcd" );
739  result /= icontent (result);
740  return N (d*result);
741  }
742  /// ---> A7
743  DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
744  DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
745  DEBOUTLN( cerr, "(hensel) B = " << B );
746  DEBOUTLN( cerr, "(hensel) lcB = " << LC( B, Variable(1) ) );
747  DEBOUTLN( cerr, "(hensel) b(B) = " << b(B) );
748  DEBOUTLN( cerr, "(hensel) DD = " << DD );
749  DEBOUTLN( cerr, "(hensel) lcDD = " << lcDD );
750  TIMING_START (ez_hensel_lift)
751  gcdfound= Hensel (B*lcD, DD, b, lcDD);
752  TIMING_END_AND_PRINT (ez_hensel_lift, "time to hensel lift in EZ: ")
753  DEBOUTLN( cerr, "(hensel finished) DD = " << DD );
754 
755  if (gcdfound == -1)
756  {
757  Off (SW_USE_EZGCD);
758  result= gcd (F,G);
759  On (SW_USE_EZGCD);
760  if (!isRat)
761  Off (SW_RATIONAL);
762  DEBDECLEVEL( cerr, "ezgcd" );
763  result /= icontent (result);
764  return N (d*result);
765  }
766 
767  if (gcdfound)
768  {
769  TIMING_START (ez_termination)
770  contcand= content (DD[2], Variable (1));
771  cand = DD[2] / contcand;
772  if (B_is_F)
773  gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
774  else
775  gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
776  TIMING_END_AND_PRINT (ez_termination,
777  "time for termination test in EZ: ")
778  }
779  /// ---> A8 (gcdfound)
780  }
781  delta--;
782  }
783  /// ---> A9
784  DEBDECLEVEL( cerr, "ezgcd" );
785  cand *= bCommonDen (cand);
786  if (!isRat)
787  Off (SW_RATIONAL);
788  cand /= icontent (cand);
789  return N (d*cand);
790 }

◆ EZGCD_P()

CanonicalForm EZGCD_P ( const CanonicalForm FF,
const CanonicalForm GG 
)

Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular algorithm.

Definition at line 815 of file cfEzgcd.cc.

816 {
817  if (FF.isZero() && degree(GG) > 0) return GG/Lc(GG);
818  else if (GG.isZero() && degree (FF) > 0) return FF/Lc(FF);
819  else if (FF.isZero() && GG.isZero()) return FF.genOne();
820  if (FF.inBaseDomain() || GG.inBaseDomain()) return FF.genOne();
821  if (FF.isUnivariate() && fdivides(FF, GG)) return FF/Lc(FF);
822  if (GG.isUnivariate() && fdivides(GG, FF)) return GG/Lc(GG);
823  if (FF == GG) return FF/Lc(FF);
824 
825  int maxNumVars= tmax (getNumVars (FF), getNumVars (GG));
826  Variable a, oldA;
827  int sizeF= size (FF);
828  int sizeG= size (GG);
829 
830  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
831  {
832  if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
833  return modGCDFq (FF, GG, a);
835  return modGCDGF (FF, GG);
836  else
837  return modGCDFp (FF, GG);
838  }
839 
840  CanonicalForm F, G, f, g, d, Fb, Gb, Db, Fbt, Gbt, Dbt, B0, B, D0, lcF, lcG,
841  lcD;
842  CFArray DD( 1, 2 ), lcDD( 1, 2 );
843  int degF, degG, delta, count;
844  int maxeval;
845  maxeval= tmin((getCharacteristic()/
846  (int)(ilog2(getCharacteristic())*log2exp))*2, maxNumEval);
847  count= 0; // number of eval. used
848  REvaluation b, bt;
849  int gcdfound = 0;
850  Variable x = Variable(1);
851 
852  F= FF;
853  G= GG;
854 
855  CFMap M,N;
856  int smallestDegLev;
857  TIMING_DEFINE(ez_p_compress);
858  TIMING_START (ez_p_compress);
859  int best_level= compress4EZGCD (F, G, M, N, smallestDegLev);
860 
861  if (best_level == 0) return G.genOne();
862 
863  F= M (F);
864  G= M (G);
865  TIMING_END_AND_PRINT (ez_p_compress, "time for compression in EZ_P: ")
866 
867  TIMING_DEFINE (ez_p_content)
868  TIMING_START (ez_p_content)
869  f = content( F, x ); g = content( G, x );
870  d = gcd( f, g );
871  F /= f; G /= g;
872  TIMING_END_AND_PRINT (ez_p_content, "time to extract content in EZ_P: ")
873 
874  if( F.isUnivariate() && G.isUnivariate() )
875  {
876  if( F.mvar() == G.mvar() )
877  d *= gcd( F, G );
878  else
879  return N (d);
880  return N (d);
881  }
882  if ( F.isUnivariate())
883  {
884  g= content (G,G.mvar());
885  return N(d*gcd(F,g));
886  }
887  if ( G.isUnivariate())
888  {
889  f= content (F,F.mvar());
890  return N(d*gcd(G,f));
891  }
892 
894  sizeF= size (F);
895  sizeG= size (G);
896 
897  if (sizeF/maxNumVars > sizePerVars1 && sizeG/maxNumVars > sizePerVars1)
898  {
899  if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
900  return N (d*modGCDFq (F, G, a));
902  return N (d*modGCDGF (F, G));
903  else
904  return N (d*modGCDFp (F, G));
905  }
906 
907  int dummy= 0;
908  if( gcd_test_one( F, G, false, dummy ) )
909  {
910  return N (d);
911  }
912 
913  bool passToGF= false;
914  bool extOfExt= false;
915  int p= getCharacteristic();
916  bool algExtension= (hasFirstAlgVar(F,a) || hasFirstAlgVar(G,a));
917  int k= 1;
918  CanonicalForm primElem, imPrimElem;
919  CFList source, dest;
920  if (p < 50 && CFFactory::gettype() != GaloisFieldDomain && !algExtension)
921  {
922  if (p == 2)
923  setCharacteristic (2, 12, 'Z');
924  else if (p == 3)
925  setCharacteristic (3, 4, 'Z');
926  else if (p == 5 || p == 7)
927  setCharacteristic (p, 3, 'Z');
928  else
929  setCharacteristic (p, 2, 'Z');
930  passToGF= true;
931  F= F.mapinto();
932  G= G.mapinto();
933  maxeval= 2*ipower (p, getGFDegree());
934  }
935  else if (CFFactory::gettype() == GaloisFieldDomain &&
936  ipower (p , getGFDegree()) < 50)
937  {
938  k= getGFDegree();
939  if (ipower (p, 2*k) > 50)
941  else
943  F= GFMapUp (F, k);
944  G= GFMapUp (G, k);
945  maxeval= tmin (2*ipower (p, getGFDegree()), maxNumEval);
946  }
947  else if (p < 50 && algExtension && CFFactory::gettype() != GaloisFieldDomain)
948  {
949  int d= degree (getMipo (a));
950  oldA= a;
951  Variable v2;
952  if (p == 2 && d < 6)
953  {
954  if (fac_NTL_char != p)
955  {
956  fac_NTL_char= p;
957  zz_p::init (p);
958  }
959  bool primFail= false;
960  Variable vBuf;
961  primElem= primitiveElement (a, vBuf, primFail);
962  ASSERT (!primFail, "failure in integer factorizer");
963  if (d < 3)
964  {
965  zz_pX NTLIrredpoly;
966  BuildIrred (NTLIrredpoly, d*3);
967  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
968  v2= rootOf (newMipo);
969  }
970  else
971  {
972  zz_pX NTLIrredpoly;
973  BuildIrred (NTLIrredpoly, d*2);
974  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
975  v2= rootOf (newMipo);
976  }
977  imPrimElem= mapPrimElem (primElem, a, v2);
978  extOfExt= true;
979  }
980  else if ((p == 3 && d < 4) || ((p == 5 || p == 7) && d < 3))
981  {
982  if (fac_NTL_char != p)
983  {
984  fac_NTL_char= p;
985  zz_p::init (p);
986  }
987  bool primFail= false;
988  Variable vBuf;
989  primElem= primitiveElement (a, vBuf, primFail);
990  ASSERT (!primFail, "failure in integer factorizer");
991  zz_pX NTLIrredpoly;
992  BuildIrred (NTLIrredpoly, d*2);
993  CanonicalForm newMipo= convertNTLzzpX2CF (NTLIrredpoly, Variable (1));
994  v2= rootOf (newMipo);
995  imPrimElem= mapPrimElem (primElem, a, v2);
996  extOfExt= true;
997  }
998  if (extOfExt)
999  {
1000  maxeval= tmin (2*ipower (p, degree (getMipo (v2))), maxNumEval);
1001  F= mapUp (F, a, v2, primElem, imPrimElem, source, dest);
1002  G= mapUp (G, a, v2, primElem, imPrimElem, source, dest);
1003  a= v2;
1004  }
1005  }
1006 
1007  lcF = LC( F, x ); lcG = LC( G, x );
1008  lcD = gcd( lcF, lcG );
1009 
1010  delta = 0;
1011  degF = degree( F, x ); degG = degree( G, x );
1012 
1013  if (algExtension)
1014  b = REvaluation( 2, tmax(F.level(), G.level()), AlgExtRandomF( a ) );
1015  else
1016  { // both not in extension given by algebraic variable
1018  b = REvaluation( 2, tmax(F.level(), G.level()), FFRandom() );
1019  else
1020  b = REvaluation( 2, tmax(F.level(), G.level()), GFRandom() );
1021  }
1022 
1023  CanonicalForm cand, contcand;
1025  int o, t;
1026  o= 0;
1027  t= 1;
1028  int goodPointCount= 0;
1029  TIMING_DEFINE(ez_p_eval);
1030  while( !gcdfound )
1031  {
1032  TIMING_START (ez_p_eval);
1033  if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,
1034  maxeval/maxNumVars, t ))
1035  { // too many eval. used --> try another method
1036  Off (SW_USE_EZGCD_P);
1037  result= gcd (F,G);
1038  On (SW_USE_EZGCD_P);
1039  if (passToGF)
1040  {
1042  setCharacteristic (p);
1045  prune (alpha);
1046  }
1047  if (k > 1)
1048  {
1049  result= GFMapDown (result, k);
1051  }
1052  if (extOfExt)
1053  {
1054  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1055  prune1 (oldA);
1056  }
1057  return N (d*result);
1058  }
1059  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P1: ");
1060  delta = degree( Db );
1061  if (delta == degF)
1062  {
1063  if (degF <= degG && fdivides (F, G))
1064  {
1065  if (passToGF)
1066  {
1068  setCharacteristic (p);
1070  F= GF2FalphaRep (F, alpha);
1071  prune (alpha);
1072  }
1073  if (k > 1)
1074  {
1075  F= GFMapDown (F, k);
1077  }
1078  if (extOfExt)
1079  {
1080  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1081  prune1 (oldA);
1082  }
1083  return N (d*F);
1084  }
1085  else
1086  delta--;
1087  }
1088  else if (delta == degG)
1089  {
1090  if (degG <= degF && fdivides (G, F))
1091  {
1092  if (passToGF)
1093  {
1095  setCharacteristic (p);
1097  G= GF2FalphaRep (G, alpha);
1098  prune (alpha);
1099  }
1100  if (k > 1)
1101  {
1102  G= GFMapDown (G, k);
1104  }
1105  if (extOfExt)
1106  {
1107  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1108  prune1 (oldA);
1109  }
1110  return N (d*G);
1111  }
1112  else
1113  delta--;
1114  }
1115  if( delta == 0 )
1116  {
1117  if (passToGF)
1118  setCharacteristic (p);
1119  if (k > 1)
1121  return N (d);
1122  }
1123  while( true )
1124  {
1125  bt = b;
1126  TIMING_START (ez_p_eval);
1127  if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,
1128  maxeval/maxNumVars, t ))
1129  { // too many eval. used --> try another method
1130  Off (SW_USE_EZGCD_P);
1131  result= gcd (F,G);
1132  On (SW_USE_EZGCD_P);
1133  if (passToGF)
1134  {
1136  setCharacteristic (p);
1139  prune (alpha);
1140  }
1141  if (k > 1)
1142  {
1143  result= GFMapDown (result, k);
1145  }
1146  if (extOfExt)
1147  {
1148  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1149  prune1 (oldA);
1150  }
1151  return N (d*result);
1152  }
1153  TIMING_END_AND_PRINT (ez_p_eval, "time for eval point search in EZ_P2: ");
1154  int dd = degree( Dbt );
1155  if( dd == 0 )
1156  {
1157  if (passToGF)
1158  setCharacteristic (p);
1159  if (k > 1)
1161  return N (d);
1162  }
1163  if( dd == delta )
1164  {
1165  goodPointCount++;
1166  if (goodPointCount == 5)
1167  break;
1168  }
1169  if( dd < delta )
1170  {
1171  goodPointCount= 0;
1172  delta = dd;
1173  b = bt;
1174  Db = Dbt; Fb = Fbt; Gb = Gbt;
1175  }
1176  if (delta == degF)
1177  {
1178  if (degF <= degG && fdivides (F, G))
1179  {
1180  if (passToGF)
1181  {
1183  setCharacteristic (p);
1185  F= GF2FalphaRep (F, alpha);
1186  prune (alpha);
1187  }
1188  if (k > 1)
1189  {
1190  F= GFMapDown (F, k);
1192  }
1193  if (extOfExt)
1194  {
1195  F= mapDown (F, primElem, imPrimElem, oldA, dest, source);
1196  prune1 (oldA);
1197  }
1198  return N (d*F);
1199  }
1200  else
1201  delta--;
1202  }
1203  else if (delta == degG)
1204  {
1205  if (degG <= degF && fdivides (G, F))
1206  {
1207  if (passToGF)
1208  {
1210  setCharacteristic (p);
1212  G= GF2FalphaRep (G, alpha);
1213  prune (alpha);
1214  }
1215  if (k > 1)
1216  {
1217  G= GFMapDown (G, k);
1219  }
1220  if (extOfExt)
1221  {
1222  G= mapDown (G, primElem, imPrimElem, oldA, dest, source);
1223  prune1 (oldA);
1224  }
1225  return N (d*G);
1226  }
1227  else
1228  delta--;
1229  }
1230  if( delta == 0 )
1231  {
1232  if (passToGF)
1233  setCharacteristic (p);
1234  if (k > 1)
1236  return N (d);
1237  }
1238  }
1239  if( delta != degF && delta != degG )
1240  {
1241  bool B_is_F;
1242  CanonicalForm xxx1, xxx2;
1244  DD[1] = Fb / Db;
1245  buf= Gb/Db;
1246  xxx1 = gcd( DD[1], Db );
1247  xxx2 = gcd( buf, Db );
1248  if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1249  (size (F) <= size (G)))
1250  || (xxx1.inCoeffDomain() && !xxx2.inCoeffDomain()))
1251  {
1252  B = F;
1253  DD[2] = Db;
1254  lcDD[1] = lcF;
1255  lcDD[2] = lcD;
1256  B_is_F = true;
1257  }
1258  else if (((xxx1.inCoeffDomain() && xxx2.inCoeffDomain()) &&
1259  (size (G) < size (F)))
1260  || (!xxx1.inCoeffDomain() && xxx2.inCoeffDomain()))
1261  {
1262  DD[1] = buf;
1263  B = G;
1264  DD[2] = Db;
1265  lcDD[1] = lcG;
1266  lcDD[2] = lcD;
1267  B_is_F = false;
1268  }
1269  else // special case handling
1270  {
1271  Off (SW_USE_EZGCD_P);
1272  result= gcd (F,G);
1273  On (SW_USE_EZGCD_P);
1274  if (passToGF)
1275  {
1277  setCharacteristic (p);
1280  prune (alpha);
1281  }
1282  if (k > 1)
1283  {
1284  result= GFMapDown (result, k);
1286  }
1287  if (extOfExt)
1288  {
1289  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1290  prune1 (oldA);
1291  }
1292  return N (d*result);
1293  }
1294  DD[2] = DD[2] * ( b( lcDD[2] ) / lc( DD[2] ) );
1295  DD[1] = DD[1] * ( b( lcDD[1] ) / lc( DD[1] ) );
1296 
1297  if (size (B*lcDD[2])/maxNumVars > sizePerVars1)
1298  {
1299  if (algExtension)
1300  {
1301  result= modGCDFq (F, G, a);
1302  if (extOfExt)
1303  {
1304  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1305  prune1 (oldA);
1306  }
1307  return N (d*result);
1308  }
1310  {
1311  result= modGCDGF (F, G);
1312  if (passToGF)
1313  {
1315  setCharacteristic (p);
1318  prune (alpha);
1319  }
1320  if (k > 1)
1321  {
1322  result= GFMapDown (result, k);
1324  }
1325  return N (d*result);
1326  }
1327  else
1328  return N (d*modGCDFp (F,G));
1329  }
1330 
1331  TIMING_DEFINE(ez_p_hensel_lift);
1332  TIMING_START (ez_p_hensel_lift);
1333  gcdfound= Hensel (B*lcD, DD, b, lcDD);
1334  TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: ");
1335 
1336  if (gcdfound == -1) //things became dense
1337  {
1338  if (algExtension)
1339  {
1340  result= modGCDFq (F, G, a);
1341  if (extOfExt)
1342  {
1343  result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
1344  prune1 (oldA);
1345  }
1346  return N (d*result);
1347  }
1349  {
1350  result= modGCDGF (F, G);
1351  if (passToGF)
1352  {
1354  setCharacteristic (p);
1357  prune (alpha);
1358  }
1359  if (k > 1)
1360  {
1361  result= GFMapDown (result, k);
1363  }
1364  return N (d*result);
1365  }
1366  else
1367  {
1368  if (p >= cf_getBigPrime(0))
1369  return N (d*sparseGCDFp (F,G));
1370  else
1371  return N (d*modGCDFp (F,G));
1372  }
1373  }
1374 
1375  if (gcdfound == 1)
1376  {
1377  TIMING_DEFINE(termination_test);
1378  TIMING_START (termination_test);
1379  contcand= content (DD[2], Variable (1));
1380  cand = DD[2] / contcand;
1381  if (B_is_F)
1382  gcdfound = fdivides( cand, G ) && cand*(DD[1]/(lcD/contcand)) == F;
1383  else
1384  gcdfound = fdivides( cand, F ) && cand*(DD[1]/(lcD/contcand)) == G;
1385  TIMING_END_AND_PRINT (termination_test,
1386  "time for termination test EZ_P: ");
1387 
1388  if (passToGF && gcdfound)
1389  {
1391  setCharacteristic (p);
1394  prune (alpha);
1395  }
1396  if (k > 1 && gcdfound)
1397  {
1398  cand= GFMapDown (cand, k);
1400  }
1401  if (extOfExt && gcdfound)
1402  {
1403  cand= mapDown (cand, primElem, imPrimElem, oldA, dest, source);
1404  prune1 (oldA);
1405  }
1406  }
1407  }
1408  delta--;
1409  goodPointCount= 0;
1410  }
1411  return N (d*cand);
1412 }

◆ findeval()

static bool findeval ( const CanonicalForm F,
const CanonicalForm G,
CanonicalForm Fb,
CanonicalForm Gb,
CanonicalForm Db,
REvaluation b,
int  delta,
int  degF,
int  degG,
int  maxeval,
int &  count,
int &  k,
int  bound,
int &  l 
)
static

Definition at line 374 of file cfEzgcd.cc.

378 {
379  if( count == 0 && delta != 0)
380  {
381  if( count++ > maxeval )
382  return false;
383  }
384  if (count > 0)
385  {
386  b.nextpoint(k);
387  if (k == 0)
388  k++;
389  l++;
390  if (l > bound)
391  {
392  l= 1;
393  k++;
394  if (k > tmax (F.level(), G.level()) - 1)
395  return false;
396  b.nextpoint (k);
397  }
398  if (count++ > maxeval)
399  return false;
400  }
401  while( true )
402  {
403  Fb = b( F );
404  if( degree( Fb, 1 ) == degF )
405  {
406  Gb = b( G );
407  if( degree( Gb, 1 ) == degG )
408  {
409  Db = gcd( Fb, Gb );
410  if( delta > 0 )
411  {
412  if( degree( Db, 1 ) <= delta )
413  return true;
414  }
415  else
416  {
417  k++;
418  return true;
419  }
420  }
421  }
422  if (k == 0)
423  k++;
424  b.nextpoint(k);
425  l++;
426  if (l > bound)
427  {
428  l= 1;
429  k++;
430  if (k > tmax (F.level(), G.level()) - 1)
431  return false;
432  b.nextpoint (k);
433  }
434  if( count++ > maxeval )
435  return false;
436  }
437 }

◆ for()

for ( int  i = 0; i <= n; i++)

Definition at line 65 of file cfEzgcd.cc.

66  {
67  if (degsf[i] != 0 && degsg[i] != 0)
68  {
69  both_non_zero++;
70  continue;
71  }
72  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
73  {
74  f_zero++;
75  continue;
76  }
77  if (degsg[i] == 0 && degsf[i] && i <= F.level())
78  {
79  g_zero++;
80  continue;
81  }
82  }

◆ Hensel()

static int Hensel ( const CanonicalForm UU,
CFArray G,
const Evaluation AA,
const CFArray LeadCoeffs 
)
inlinestatic

Definition at line 293 of file cfEzgcd.cc.

295 {
296  CFList factors;
297  factors.append (G[1]);
298  factors.append (G[2]);
299 
300  CFMap NN, MM;
301  Evaluation A= optimize4Lift (UU, MM, NN, AA);
302 
303  CanonicalForm U= MM (UU);
304  CFArray LCs= CFArray (1,2);
305  LCs [1]= MM (LeadCoeffs [1]);
306  LCs [2]= MM (LeadCoeffs [2]);
307 
309  long termEstimate= size (U);
310  for (int i= A.min(); i <= A.max(); i++)
311  {
312  if (!A[i].isZero() &&
313  ((getCharacteristic() > degree (U,i)) || getCharacteristic() == 0))
314  {
315  termEstimate *= degree (U,i)*2;
316  termEstimate /= 3;
317  }
318  evaluation.append (A [i]);
319  }
320  if (termEstimate/getNumVars(U) > 500)
321  return -1;
322  CFList UEval;
323  CanonicalForm shiftedU= myShift2Zero (U, UEval, evaluation);
324 
325  if (size (shiftedU)/getNumVars (U) > 500)
326  return -1;
327 
328  CFArray shiftedLCs= CFArray (2);
329  CFList shiftedLCsEval1, shiftedLCsEval2;
330  shiftedLCs[0]= myShift2Zero (LCs[1], shiftedLCsEval1, evaluation);
331  shiftedLCs[1]= myShift2Zero (LCs[2], shiftedLCsEval2, evaluation);
332  factors.insert (1);
333  int liftBound= degree (UEval.getLast(), 2) + 1;
334  CFArray Pi;
335  CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
336  CFList diophant;
337  CFArray lcs= CFArray (2);
338  lcs [0]= shiftedLCsEval1.getFirst();
339  lcs [1]= shiftedLCsEval2.getFirst();
340  nonMonicHenselLift12 (UEval.getFirst(), factors, liftBound, Pi, diophant, M,
341  lcs, false);
342 
343  for (CFListIterator i= factors; i.hasItem(); i++)
344  {
345  if (!fdivides (i.getItem(), UEval.getFirst()))
346  return 0;
347  }
348 
349  int * liftBounds;
350  bool noOneToOne= false;
351  if (U.level() > 2)
352  {
353  liftBounds= NEW_ARRAY(int,U.level() - 1); /* index: 0.. U.level()-2 */
354  liftBounds[0]= liftBound;
355  for (int i= 1; i < U.level() - 1; i++)
356  liftBounds[i]= degree (shiftedU, Variable (i + 2)) + 1;
357  factors= nonMonicHenselLift2 (UEval, factors, liftBounds, U.level() - 1,
358  false, shiftedLCsEval1, shiftedLCsEval2, Pi,
359  diophant, noOneToOne);
360  DELETE_ARRAY(liftBounds);
361  if (noOneToOne)
362  return 0;
363  }
364  G[1]= factors.getFirst();
365  G[2]= factors.getLast();
366  G[1]= myReverseShift (G[1], evaluation);
367  G[2]= myReverseShift (G[2], evaluation);
368  G[1]= NN (G[1]);
369  G[2]= NN (G[2]);
370  return 1;
371 }

◆ if()

if ( both_non_zero  = = 0)

Definition at line 84 of file cfEzgcd.cc.

85  {
88  return 0;
89  }

◆ myReverseShift()

static CanonicalForm myReverseShift ( const CanonicalForm F,
const CFList evaluation 
)
inlinestatic

Definition at line 207 of file cfEzgcd.cc.

208 {
209  int l= evaluation.length() + 1;
212  int Flevel=F.level();
213  for (int i= 2; i < l + 1; i++, j++)
214  {
215  if (Flevel < i)
216  continue;
217  result= result (Variable (i) - j.getItem(), i);
218  }
219  return result;
220 }

◆ myShift2Zero()

static CanonicalForm myShift2Zero ( const CanonicalForm F,
CFList Feval,
const CFList evaluation 
)
inlinestatic

Definition at line 187 of file cfEzgcd.cc.

189 {
190  CanonicalForm A= F;
191  int k= 2;
192  for (CFListIterator i= evaluation; i.hasItem(); i++, k++)
193  A= A (Variable (k) + i.getItem(), k);
194 
196  Feval= CFList();
197  Feval.append (buf);
198  for (k= evaluation.length() + 1; k > 2; k--)
199  {
200  buf= mod (buf, Variable (k));
201  Feval.insert (buf);
202  }
203  return A;
204 }

◆ optimize4Lift()

static Evaluation optimize4Lift ( const CanonicalForm F,
CFMap M,
CFMap N,
const Evaluation A 
)
inlinestatic

Definition at line 223 of file cfEzgcd.cc.

225 {
226  int n= F.level();
227  int * degsf= NEW_ARRAY(int,n + 1);
228 
229  for (int i = n; i >= 0; i--)
230  degsf[i]= 0;
231 
232  degsf= degrees (F, degsf);
233 
234  Evaluation result= Evaluation (A.min(), A.max());
235  ASSERT (A.min() == 2, "expected A.min() == 2");
236  int max_deg;
237  int k= n;
238  int l= 1;
239  int i= 2;
240  int pos= 2;
241  while (k > 1)
242  {
243  max_deg= degsf [i]; // i is always 2 here, n>=2
244  while ((i<n) &&(max_deg == 0))
245  {
246  i++;
247  max_deg= degsf [i];
248  }
249  l= i;
250  for (int j= i + 1; j <= n; j++)
251  {
252  if (degsf[j] > max_deg)
253  {
254  max_deg= degsf[j];
255  l= j;
256  }
257  }
258 
259  if (l <= n)
260  {
261  if (l != pos)
262  {
263  result.setValue (pos, A [l]);
264  M.newpair (Variable (l), Variable (pos));
265  N.newpair (Variable (pos), Variable (l));
266  degsf[l]= 0;
267  l= 2;
268  if (k == 2 && n == 3)
269  {
270  result.setValue (l, A [pos]);
271  M.newpair (Variable (pos), Variable (l));
272  N.newpair (Variable (l), Variable (pos));
273  degsf[pos]= 0;
274  }
275  }
276  else
277  {
278  result.setValue (l, A [l]);
279  degsf [l]= 0;
280  }
281  }
282  pos++;
283  k--;
284  l= 2;
285  }
286 
288 
289  return result;
290 }

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( ez_eval  ) const &

◆ while()

while ( k  ,
 
)

Definition at line 126 of file cfEzgcd.cc.

127  {
128  max_min_deg= tmin (degsf[i], degsg[i]);
129  while (max_min_deg == 0)
130  {
131  i++;
132  max_min_deg= tmin (degsf[i], degsg[i]);
133  }
134  for (int j= i + 1; j <= m; j++)
135  {
136  if ((tmin (degsf[j],degsg[j]) < max_min_deg) &&
137  (tmin (degsf[j], degsg[j]) != 0))
138  {
139  max_min_deg= tmin (degsf[j], degsg[j]);
140  l= j;
141  }
142  }
143 
144  if (l != 0)
145  {
146  if (l != k)
147  {
148  M.newpair (Variable (l), Variable(k));
149  N.newpair (Variable (k), Variable(l));
150  degsf[l]= 0;
151  degsg[l]= 0;
152  l= 0;
153  }
154  else
155  {
156  degsf[l]= 0;
157  degsg[l]= 0;
158  l= 0;
159  }
160  }
161  else if (l == 0)
162  {
163  if (i != k)
164  {
165  M.newpair (Variable (i), Variable (k));
166  N.newpair (Variable (k), Variable (i));
167  degsf[i]= 0;
168  degsg[i]= 0;
169  }
170  else
171  {
172  degsf[i]= 0;
173  degsg[i]= 0;
174  }
175  i++;
176  }
177  k--;
178  }

Variable Documentation

◆ both_non_zero

return both_non_zero
Initial value:
{
int n= tmax (F.level(), G.level())

Definition at line 50 of file cfEzgcd.cc.

◆ degsf

degsf = NEW_ARRAY(int,n + 1)

Definition at line 52 of file cfEzgcd.cc.

◆ degsg

degsg = NEW_ARRAY(int,n + 1)

Definition at line 53 of file cfEzgcd.cc.

◆ f_zero

int f_zero = 0

Definition at line 62 of file cfEzgcd.cc.

◆ Flevel

int Flevel =F.level()

Definition at line 94 of file cfEzgcd.cc.

◆ G

Definition at line 48 of file cfEzgcd.cc.

◆ g_zero

int g_zero = 0

Definition at line 63 of file cfEzgcd.cc.

◆ Glevel

int Glevel =G.level()

Definition at line 95 of file cfEzgcd.cc.

◆ i

int i = 1

Definition at line 125 of file cfEzgcd.cc.

◆ k

k = 1

Definition at line 92 of file cfEzgcd.cc.

◆ l

l = 1

Definition at line 93 of file cfEzgcd.cc.

◆ log2exp

const double log2exp = 1.442695041
static

Definition at line 39 of file cfEzgcd.cc.

◆ M

Definition at line 48 of file cfEzgcd.cc.

◆ m

int m = tmin (Flevel, Glevel)

Definition at line 121 of file cfEzgcd.cc.

◆ max_min_deg

int max_min_deg

Definition at line 122 of file cfEzgcd.cc.

◆ maxNumEval

int maxNumEval = 200
static

Definition at line 810 of file cfEzgcd.cc.

◆ N

Definition at line 48 of file cfEzgcd.cc.

◆ sizePerVars1

int sizePerVars1 = 500
static

Definition at line 811 of file cfEzgcd.cc.

Matrix
Definition: ftmpl_matrix.h:20
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
max_min_deg
int max_min_deg
Definition: cfEzgcd.cc:122
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
FFRandom
generate random elements in F_p
Definition: cf_random.h:43
if
if(both_non_zero==0)
Definition: cfEzgcd.cc:84
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
icontent
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
sizePerVars1
static int sizePerVars1
Definition: cfEzgcd.cc:811
x
Variable x
Definition: cfModGcd.cc:4023
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
result
return result
Definition: facAbsBiFact.cc:76
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:441
CFMap
class CFMap
Definition: cf_map.h:84
AlgExtRandomF
generate random elements in F_p(alpha)
Definition: cf_random.h:70
g
g
Definition: cfModGcd.cc:4031
Evaluation
class to evaluate a polynomial at points
Definition: cf_eval.h:31
gcd_test_one
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition: cfGcdUtil.cc:21
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
gf_mipo
CanonicalForm gf_mipo
Definition: gfops.cc:56
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition: canonicalform.h:391
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
gf_name
char gf_name
Definition: gfops.cc:52
primitiveElement
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:310
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
M
const CanonicalForm CFMap & M
Definition: cfEzgcd.cc:48
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
degsg
int * degsg
Definition: cfEzgcd.cc:53
GFMapDown
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:243
SW_USE_EZGCD
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:32
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
CanonicalForm::genOne
CanonicalForm genOne() const
Definition: canonicalform.cc:1822
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
mapUp
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:67
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
Array
Definition: ftmpl_array.h:17
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
Flevel
int Flevel
Definition: cfEzgcd.cc:94
nonMonicHenselLift12
void nonMonicHenselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
Hensel lifting from univariate to bivariate, factors need not to be monic.
Definition: facHensel.cc:2018
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
buf
int status int void * buf
Definition: si_signals.h:58
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
optimize4Lift
static Evaluation optimize4Lift(const CanonicalForm &F, CFMap &M, CFMap &N, const Evaluation &A)
Definition: cfEzgcd.cc:223
findeval
static bool findeval(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Fb, CanonicalForm &Gb, CanonicalForm &Db, REvaluation &b, int delta, int degF, int degG, int maxeval, int &count, int &k, int bound, int &l)
Definition: cfEzgcd.cc:374
TIMING_START
TIMING_START(fac_alg_resultant)
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
IntRandom
generate random integers
Definition: cf_random.h:55
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
ilog2
int ilog2(const CanonicalForm &a)
Definition: canonicalform.h:345
D
#define D(A)
Definition: gentable.cc:128
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
modGCDFq
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition: cfModGcd.cc:467
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
log2exp
static const double log2exp
Definition: cfEzgcd.cc:39
DEBINCLEVEL
#define DEBINCLEVEL(stream, msg)
Definition: debug.h:44
prune
void prune(Variable &alpha)
Definition: variable.cc:261
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
DEBDECLEVEL
#define DEBDECLEVEL(stream, msg)
Definition: debug.h:45
GG
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
TIMING_DEFINE
#define TIMING_DEFINE(t)
Definition: timing.h:91
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:25
f_zero
int f_zero
Definition: cfEzgcd.cc:62
Feval
CanonicalForm Feval
Definition: facAbsFact.cc:64
GFRandom
generate random elements in GF
Definition: cf_random.h:31
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
g_zero
int g_zero
Definition: cfEzgcd.cc:63
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
Hensel
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition: cfEzgcd.cc:293
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
both_non_zero
const CanonicalForm CFMap CFMap int & both_non_zero
Definition: cfEzgcd.cc:50
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
getGFDegree
int getGFDegree()
Definition: cf_char.cc:56
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
cand
const CanonicalForm const CanonicalForm const CanonicalForm const CanonicalForm & cand
Definition: cfModGcd.cc:69
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
degsf
int * degsf
Definition: cfEzgcd.cc:52
Variable
factory's class for variables
Definition: factory.h:117
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:34
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
B
b *CanonicalForm B
Definition: facBivar.cc:52
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
mapPrimElem
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:377
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
m
int m
Definition: cfEzgcd.cc:121
myReverseShift
static CanonicalForm myReverseShift(const CanonicalForm &F, const CFList &evaluation)
Definition: cfEzgcd.cc:207
l
int l
Definition: cfEzgcd.cc:93
maxNumVars
int maxNumVars
Definition: cfModGcd.cc:4071
nonMonicHenselLift2
CFList nonMonicHenselLift2(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &LCs1, const CFList &LCs2, bool &bad)
Definition: facHensel.cc:2492
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
myShift2Zero
static CanonicalForm myShift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation)
Definition: cfEzgcd.cc:187
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List< CanonicalForm >
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition: canonicalform.cc:206
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:58
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
GF2FalphaRep
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:162
DELETE_ARRAY
DELETE_ARRAY(degsf)
G
const CanonicalForm & G
Definition: cfEzgcd.cc:48
GFMapUp
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:207
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
A
#define A
Definition: sirandom.c:23
maxNumEval
static int maxNumEval
Definition: cfEzgcd.cc:810
prune1
void prune1(const Variable &alpha)
Definition: variable.cc:289
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
modGCDGF
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
Definition: cfModGcd.cc:860
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
mapDown
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition: cf_map_ext.cc:90
ListIterator
Definition: ftmpl_list.h:17
sparseGCDFp
CanonicalForm sparseGCDFp(const CanonicalForm &F, const CanonicalForm &G, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:3503