My Project
factory.h
Go to the documentation of this file.
1 /* factory.h automatically generated by makeheader from factory.template */
2 /* emacs edit mode for this file is -*- C++ -*- */
3 
4 #ifndef INCL_FACTORY_H
5 #define INCL_FACTORY_H
6 
7 /* factory.template is a template to generate `factory.h' */
8 
9 /**
10 *
11 * @file factory.h
12 *
13 * `factory.h' is the user interface to Factory. Created
14 * automatically by `makeheader', it collects all important
15 * declarations from all important Factory header files into one
16 * overall header file leaving out all boring Factory internal
17 * stuff. See `./bin/makeheader' for an explanation of the syntax
18 * of this file.
19 *
20 * Note: In this file the order of "includes" matters (since this
21 * are not real includes)! In general, files at the end depend
22 * on files at the beginning.
23 *
24 **/
25 
26 #include "factory/factoryconf.h"
27 #include "factory/globaldefs.h"
28 #include <stdint.h>
29 #include "factory/si_log2.h"
30 #ifdef HAVE_OMALLOC
31 #include "omalloc/omalloc.h"
32 #ifndef XMEMORY_H
33 #include "omalloc/omallocClass.h"
34 #endif
35 #endif
36 
37 #ifndef NOSTREAMIO
38 # ifdef HAVE_IOSTREAM
39 # include <iostream>
40 # define OSTREAM std::ostream
41 # define ISTREAM std::istream
42 # elif defined(HAVE_IOSTREAM_H)
43 # include <iostream.h>
44 # define OSTREAM ostream
45 # define ISTREAM istream
46 # endif
47 #endif /* ! NOSTREAMIO */
48 
49 #include "factory/cf_gmp.h"
50 
56 
57 /* stuff included from ./cf_globals.h */
58 
59 
60 extern const char factoryConfiguration[];
61 
62 
63 /* stuff included from ./cf_primes.h */
64 
65 
66 int FACTORY_PUBLIC cf_getPrime( int i );
67 
69 
71 
73 
75 
77 
78 
79 /* stuff included from ./cf_defs.h */
80 
81 
82 #define LEVELBASE -1000000
83 #define LEVELTRANS -500000
84 #define LEVELQUOT 1000000
85 #define LEVELEXPR 1000001
86 
87 /// set to 1 for computations over Q
88 static const int SW_RATIONAL = 0;
89 /// set to 1 for symmetric representation over F_q
90 static const int SW_SYMMETRIC_FF = 1;
91 /// set to 1 to use EZGCD over Z
92 static const int SW_USE_EZGCD = 2;
93 /// set to 1 to use EZGCD over F_q
94 static const int SW_USE_EZGCD_P = 3;
95 /// set to 1 to sort factors in a factorization
96 static const int SW_USE_NTL_SORT=4;
97 /// set to 1 to use modular gcd over Z
98 static const int SW_USE_CHINREM_GCD=5;
99 /// set to 1 to use Encarnacion GCD over Q(a)
100 static const int SW_USE_QGCD=6;
101 /// set to 1 to use modular GCD over F_q
102 static const int SW_USE_FF_MOD_GCD=7;
103 /// set to 1 to use Flints gcd over F_p
104 static const int SW_USE_FL_GCD_P=8;
105 /// set to 1 to use Flints gcd over Q/Z
106 static const int SW_USE_FL_GCD_0=9;
107 /// set to 1 to use Factorys Berlekamp alg.
108 static const int SW_BERLEKAMP=10;
109 
110 static const int SW_FAC_QUADRATICLIFT=11;
111 /// set to 1 to prefer flints multivariate factorization over Z/p
112 static const int SW_USE_FL_FAC_P=12;
113 /// set to 1 to prefer flints multivariate factorization over Z/p
114 static const int SW_USE_FL_FAC_0=13;
115 /// set to 1 to prefer flints multivariate factorization over Z/p(a)
116 static const int SW_USE_FL_FAC_0A=14;
117 
118 /* stuff included from ./variable.h */
119 
120 
121 class CanonicalForm;
122 
123 /**
124  * factory's class for variables
125 **/
127 {
128 private:
129  int _level;
130  Variable( int l, bool flag );
131 public:
132  Variable() : _level(LEVELBASE) {}
133  Variable( int l );
134  Variable( char name );
135  Variable( int l, char name );
136  Variable( const Variable & v ) : _level(v._level) {}
137  ~Variable() {};
138  Variable& operator= ( const Variable & v )
139  {
140  _level = v._level;
141  return *this;
142  }
143  int level() const { return _level; }
144  char name() const;
145  static Variable highest() { return Variable( LEVELQUOT-1 ); }
146  Variable next() const { return Variable( _level+1 ); }
147  friend bool operator == ( const Variable & lhs, const Variable & rhs )
148  {
149  return lhs._level == rhs._level;
150  }
151  friend bool operator != ( const Variable & lhs, const Variable & rhs )
152  {
153  return lhs._level != rhs._level;
154  }
155  friend bool operator > ( const Variable & lhs, const Variable & rhs )
156  {
157  return lhs._level > rhs._level;
158  }
159  friend bool operator < ( const Variable & lhs, const Variable & rhs )
160  {
161  return lhs._level < rhs._level;
162  }
163  friend bool operator >= ( const Variable & lhs, const Variable & rhs )
164  {
165  return lhs._level >= rhs._level;
166  }
167  friend bool operator <= ( const Variable & lhs, const Variable & rhs )
168  {
169  return lhs._level <= rhs._level;
170  }
171 #ifndef NOSTREAMIO
172  friend OSTREAM & operator << ( OSTREAM & os, const Variable & v );
173 #endif /* NOSTREAMIO */
174  friend void swap_levels();
175  /** returns a symbolic root of polynomial with name @a name.
176  * Use it to define algebraic variables
177  * @note: algebraic variables have a level < 0
178  **/
179  friend Variable rootOf( const CanonicalForm &, char name );
180 };
181 
182 /** returns a symbolic root of polynomial with name @a name
183  * Use it to define algebraic variables
184  * @note: algebraic variables have a level < 0
185 **/
186 Variable FACTORY_PUBLIC rootOf( const CanonicalForm &, char name = '@' );
187 
188 inline int level( const Variable & v ) { return v.level(); }
189 inline char name( const Variable & v ) { return v.name(); }
190 
191 void setReduce( const Variable & alpha, bool reduce );
192 void setMipo ( const Variable & alpha, const CanonicalForm & mipo);
193 CanonicalForm getMipo( const Variable & alpha, const Variable & x );
194 bool hasMipo( const Variable & alpha );
195 
196 char getDefaultVarName();
197 char getDefaultExtName();
198 
200 void prune1 (const Variable& alpha);
201 int ExtensionLevel();
202 
203 
204 /* stuff included from ./canonicalform.h */
205 
206 
207 #undef CF_INLINE
208 #define CF_INLINE
209 #undef CF_NO_INLINE
210 #define CF_NO_INLINE
211 
212 
213 class InternalCF;
214 
215 inline int is_imm ( const InternalCF * const ptr )
216 {
217  // returns 0 if ptr is not immediate
218  return ( ((int)((intptr_t)ptr)) & 3 );
219 }
220 
221 
222 /**
223  * factory's main class
224  *
225  * a CanonicalForm can represent a polynomial over or a constant in F_p,
226  * F_p(alpha), GF (F_p[t]/(Conway polynomial)), Z, or Q
227  *
228  * @sa int_poly.h, variable.h, ffops.h, gfops.h, imm.h, int_int.h, int_rat.h
229 **/
231 #ifdef HAVE_OMALLOC
232 #ifndef XMEMORY_H
233  : public omallocClass
234 #endif
235 #endif
236 {
237 private:
238  InternalCF *value;
239 public:
240  // constructors, destructors, selectors
244  CF_INLINE CanonicalForm( const int );
245  CF_INLINE CanonicalForm( const long );
248  CanonicalForm( const char *, const int base=10 ); // use with caution - does only handle integers !!!
249 
251 
252  InternalCF* getval() const; // use with caution !!!
253 
255 
256  void mpzval(mpz_t val) const;
257  // predicates
258  CF_NO_INLINE bool isOne() const;
259  CF_NO_INLINE bool isZero() const;
260  inline bool isImm() const { return is_imm( value ); };
261 
262  bool inZ() const;
263  bool inQ() const;
264  bool inFF() const;
265  bool inGF() const;
266  bool inBaseDomain() const;
267  bool inExtension() const;
268  bool inCoeffDomain() const;
269  bool inPolyDomain() const;
270  bool inQuotDomain() const;
271 
272  bool isFFinGF() const;
273  bool isUnivariate() const;
274  bool isHomogeneous() const;
275 
276  // conversion functions
277  long intval() const;
279 
280  CanonicalForm lc () const;
281  CanonicalForm Lc () const;
282  CanonicalForm LC () const;
283  CanonicalForm LC ( const Variable & v ) const;
284 
285  int degree () const;
286  int degree ( const Variable & v ) const;
287 
289  CanonicalForm tailcoeff ( const Variable & v ) const;
290  int taildegree () const;
291 
292  int level () const;
293  Variable mvar () const;
294 
295  CanonicalForm num () const;
296  CanonicalForm den () const;
297 
298  // assignment operators
299  CF_NO_INLINE CanonicalForm& operator = ( const CanonicalForm& );
300  CF_NO_INLINE CanonicalForm& operator = ( const long );
301 
306  CanonicalForm& operator %= ( const CanonicalForm& );
308  CanonicalForm& tryDiv (const CanonicalForm&, const CanonicalForm&, bool& );
310 
311  // evaluation operators
312  CanonicalForm operator () ( const CanonicalForm & f ) const;
313  CanonicalForm operator () ( const CanonicalForm & f, const Variable & v ) const;
314 
315  CanonicalForm operator [] ( int i ) const;
316 
318  CanonicalForm deriv( const Variable & x ) const;
319 
320  int sign() const;
322  int ilog2() const;
323 
324  // comparison operators
325  friend FACTORY_PUBLIC bool operator == ( const CanonicalForm&, const CanonicalForm& );
326  friend FACTORY_PUBLIC bool operator != ( const CanonicalForm&, const CanonicalForm& );
327  friend FACTORY_PUBLIC bool operator > ( const CanonicalForm&, const CanonicalForm& );
328  friend FACTORY_PUBLIC bool operator < ( const CanonicalForm&, const CanonicalForm& );
329 
330  // arithmetic operators
332 
333  friend FACTORY_PUBLIC void divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
335  friend FACTORY_PUBLIC bool tryDivremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm&, const CanonicalForm&, bool& );
336 
337  friend FACTORY_PUBLIC CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
339 
340  // input/output
341 #ifndef NOSTREAMIO
342  void print( OSTREAM&, char * ) const;
343  void print( OSTREAM& ) const;
346 #endif /* NOSTREAMIO */
347 
348  // obsolete methods
351 
352  friend class CFIterator;
353 };
354 
356 operator + ( const CanonicalForm&, const CanonicalForm& );
357 
360 
362 operator * ( const CanonicalForm&, const CanonicalForm& );
363 
366 
369 
371 div ( const CanonicalForm&, const CanonicalForm& );
372 
374 mod ( const CanonicalForm&, const CanonicalForm& );
375 
376 
377 //{{{ function declarations from canonicalform.cc
379 
381 
382 CanonicalForm FACTORY_PUBLIC power ( const Variable & v, int n );
383 //}}}
384 
385 //{{{ function declarations from cf_gcd.cc
387 
389 
391 
393 
395 
397 
399 
401 //}}}
402 
403 //{{{ function declarations from cf_ops.cc
404 CanonicalForm FACTORY_PUBLIC swapvar ( const CanonicalForm &, const Variable &, const Variable & );
405 
407 
408 int getNumVars( const CanonicalForm & f );
409 
411 
412 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) );
413 
414 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) );
415 
416 int * degrees ( const CanonicalForm & f, int * degs = 0 );
417 
418 int totaldegree ( const CanonicalForm & f );
419 
420 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 );
421 
422 int size ( const CanonicalForm & f, const Variable & v );
423 
424 int size ( const CanonicalForm & f );
425 
426 int size_maxexp ( const CanonicalForm & f, int& maxexp );
427 
429 
430 bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
431 
432 CanonicalForm leftShift (const CanonicalForm& F, int n);
433 //}}}
434 
435 //{{{ inline functions corresponding to CanonicalForm methods
436 //{{{ docu
437 //
438 // - inline functions corresponding to CanonicalForm methods.
439 //
440 // These function exist for convenience only and because it is
441 // more beautiful to write 'degree( f )' than 'f.degree()'.
442 //
443 //}}}
444 inline CanonicalForm
445 lc ( const CanonicalForm & f ) { return f.lc(); }
446 
447 inline CanonicalForm
448 Lc ( const CanonicalForm & f ) { return f.Lc(); }
449 
450 inline CanonicalForm
451 LC ( const CanonicalForm & f ) { return f.LC(); }
452 
453 inline CanonicalForm
454 LC ( const CanonicalForm & f, const Variable & v ) { return f.LC( v ); }
455 
456 inline int
457 degree ( const CanonicalForm & f ) { return f.degree(); }
458 
459 inline int
460 degree ( const CanonicalForm & f, const Variable & v ) { return f.degree( v ); }
461 
462 inline int
463 taildegree ( const CanonicalForm & f ) { return f.taildegree(); }
464 
465 inline CanonicalForm
466 tailcoeff ( const CanonicalForm & f ) { return f.tailcoeff(); }
467 
468 inline CanonicalForm
469 tailcoeff (const CanonicalForm& f, const Variable& v) { return f.tailcoeff(v); }
470 
471 inline int
472 level ( const CanonicalForm & f ) { return f.level(); }
473 
474 inline Variable
475 mvar ( const CanonicalForm & f ) { return f.mvar(); }
476 
477 inline CanonicalForm
478 num ( const CanonicalForm & f ) { return f.num(); }
479 
480 inline CanonicalForm
481 den ( const CanonicalForm & f ) { return f.den(); }
482 
483 inline int
484 sign ( const CanonicalForm & a ) { return a.sign(); }
485 
486 inline CanonicalForm
487 deriv ( const CanonicalForm & f, const Variable & x ) { return f.deriv( x ); }
488 
489 inline CanonicalForm
490 sqrt ( const CanonicalForm & a ) { return a.sqrt(); }
491 
492 inline int
493 ilog2 ( const CanonicalForm & a ) { return a.ilog2(); }
494 
495 inline CanonicalForm
496 mapinto ( const CanonicalForm & f ) { return f.mapinto(); }
497 //}}}
498 
499 //{{{ inline functions
500 inline CanonicalForm
501 head ( const CanonicalForm & f )
502 {
503  if ( f.level() > 0 )
504  return power( f.mvar(), f.degree() ) * f.LC();
505  else
506  return f;
507 }
508 
509 inline int
510 headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
511 
512 
513 //}}}
514 
515 //{{{ other function declarations
516 void FACTORY_PUBLIC setCharacteristic( int c ); // -> Fp && Q
517 void setCharacteristic( int c, int n ); // -> PrimePower
518 void setCharacteristic( int c, int n, char name ); // -> GF(q)
519 
521 int getGFDegree();
523 
524 void FACTORY_PUBLIC On( int );
525 void FACTORY_PUBLIC Off( int );
526 bool FACTORY_PUBLIC isOn( int );
527 //}}}
528 
529 //{{{ type definitions
547 //}}}
548 
549 
550 /* stuff included from ./cf_algorithm.h */
551 
552 
553 //{{{ function declarations from cf_algorithm.cc
554 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
555 
556 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
557 
558 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x );
559 
561 
562 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
563 
564 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot );
565 
566 bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );
567 
569 
571 //}}}
572 
573 //{{{ function declarations from cf_chinese.cc
574 void FACTORY_PUBLIC chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew );
575 
576 void FACTORY_PUBLIC chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );
577 
578 void FACTORY_PUBLIC chineseRemainderCached ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew, CFArray &inv );
580 
581 
582 CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
583 //}}}
584 
585 //{{{ function declarations from cf_factor.cc
587 
588 bool isPurePoly(const CanonicalForm & f);
589 
590 bool isPurePoly_m(const CanonicalForm & f);
591 
592 CFFList FACTORY_PUBLIC factorize ( const CanonicalForm & f, bool issqrfree = false );
593 
595 
596 CFFList FACTORY_PUBLIC sqrFree ( const CanonicalForm & f, bool sort= false );
597 
598 CanonicalForm homogenize( const CanonicalForm & f, const Variable & x);
600  const Variable & v1, const Variable & v2);
602 CFList get_Terms( const CanonicalForm & f );
603 void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
604 
605 
606 //}}}
607 
608 //{{{ function declarations from cf_linsys.cc
609 bool linearSystemSolve ( CFMatrix & M );
610 
612 //}}}
613 
614 //{{{ function declarations from cf_resultant.cc
615 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
616 
618 //}}}
619 
620 /** inline CanonicalForm abs ( const CanonicalForm & f )
621  *
622  * abs() - return absolute value of `f'.
623  *
624  * The absolute value is defined in terms of the function
625  * `sign()'. If it reports negative sign for `f' than -`f' is
626  * returned, otherwise `f'.
627  *
628  * This behaviour is most useful for integers and rationals. But
629  * it may be used to sign-normalize the leading coefficient of
630  * arbitrary polynomials, too.
631  *
632  * Type info:
633  * ----------
634  * f: CurrentPP
635  *
636 **/
637 inline CanonicalForm
638 abs ( const CanonicalForm & f )
639 {
640  // it is not only more general to use `sign()' instead of a
641  // direct comparison `f < 0', it is faster, too
642  if ( sign( f ) < 0 )
643  return -f;
644  else
645  return f;
646 }
647 //}}}
648 
649 
650 /* stuff included from ./cf_eval.h */
651 
652 
653 /**
654  * class to evaluate a polynomial at points
655 **/
656 class Evaluation
657 {
658 protected:
659  CFArray values;
660 public:
662  Evaluation( int min0, int max0 ) : values( min0, max0 ) {}
663  Evaluation( const Evaluation & e ) : values( e.values ) {}
664  virtual ~Evaluation() {}
666  int min() const { return values.min(); }
667  int max() const { return values.max(); }
668  CanonicalForm operator[] ( int i ) const { return values[i]; }
669  CanonicalForm operator[] ( const Variable & v ) const { return operator[](v.level()); }
671  CanonicalForm operator() ( const CanonicalForm & f, int i, int j ) const;
672  void setValue (int i, const CanonicalForm& f);
673  virtual void nextpoint();
674 #ifndef NOSTREAMIO
675  friend OSTREAM& operator<< ( OSTREAM& s, const Evaluation &e );
676 #endif /* NOSTREAMIO */
677 };
678 
679 
680 /* stuff included from ./cf_generator.h */
681 
682 
683 /**
684  * virtual class for generators
685 **/
686 class CFGenerator
687 {
688 public:
690  virtual ~CFGenerator() {}
691  virtual bool hasItems() const { return false; }
692  virtual void reset() {};
693  virtual CanonicalForm item() const { return 0; }
694  virtual void next() {};
695  virtual CFGenerator * clone() const { return new CFGenerator();}
696 };
697 
698 /**
699  * generate integers starting from 0
700 **/
701 class IntGenerator : public CFGenerator
702 {
703 private:
704  int current;
705 public:
708  bool hasItems() const;
709  void reset() { current = 0; }
711  void next();
712  void operator++ () { next(); }
713  void operator++ ( int ) { next(); }
714  CFGenerator * clone() const;
715 };
716 
717 /**
718  * generate all elements in F_p starting from 0
719 **/
720 class FFGenerator : public CFGenerator
721 {
722 private:
723  int current;
724 public:
727  bool hasItems() const;
728  void reset() { current = 0; }
730  void next();
731  void operator++ () { next(); }
732  void operator++ ( int ) { next(); }
733  CFGenerator * clone() const;
734 };
735 
736 /**
737  * generate all elements in GF starting from 0
738 **/
739 class GFGenerator : public CFGenerator
740 {
741 private:
742  int current;
743 public:
746  bool hasItems() const;
747  void reset();
749  void next();
750  void operator++ () { next(); }
751  void operator++ ( int ) { next(); }
752  CFGenerator * clone() const;
753 };
754 
755 /**
756  * generate all elements in F_p(alpha) starting from 0
757 **/
758 class AlgExtGenerator: public CFGenerator
759 {
760 private:
762  FFGenerator **gensf;
763  GFGenerator **gensg;
764  int n;
765  bool nomoreitems;
769 public:
770  AlgExtGenerator( const Variable & a );
772 
773  bool hasItems() const { return ! nomoreitems; }
774  void reset();
776  void next();
777  void operator++ () { next(); }
778  void operator++ ( int ) { next(); }
779  CFGenerator * clone() const;
780 };
781 
782 class CFGenFactory
783 {
784 public:
786 };
787 
788 
789 /* stuff included from ./cf_iter.h */
790 
791 
792 #undef CF_INLINE
793 #define CF_INLINE
794 #undef CF_NO_INLINE
795 #define CF_NO_INLINE
796 
797 
798 class term;
799 typedef term * termList;
800 
801 /**
802  * class to iterate through CanonicalForm's
803  *
804  * @note a (multivariate) polynomial is viewed as a univariate poly in its main
805  * variable
806 **/
808 private:
809  CanonicalForm data;
810  termList cursor;
811  bool ispoly, hasterms;
812 public:
814  CFIterator ( const CFIterator& );
816  CFIterator ( const CanonicalForm&, const Variable& );
817 
819 
820  CFIterator& operator= ( const CFIterator& );
821  CFIterator& operator= ( const CanonicalForm& );
822 
823  CF_NO_INLINE CFIterator& operator++ ();
824  CF_NO_INLINE CFIterator& operator++ ( int );
825  CF_NO_INLINE int hasTerms () const; ///< check if iterator has reached
826  ///< the end of CanonicalForm
827  CF_NO_INLINE CanonicalForm coeff () const;///< get the current coefficient
828  CF_NO_INLINE int exp () const; ///< get the current exponent
829 };
830 
831 
832 /* stuff included from ./cf_random.h */
833 
834 
835 /**
836  * virtual class for random element generation
837 **/
838 class CFRandom {
839 public:
840  virtual ~CFRandom() {}
841  virtual CanonicalForm generate() const { return 0; }
842  virtual CFRandom * clone() const { return new CFRandom(); }
843 };
844 
845 /**
846  * generate random elements in GF
847 **/
848 class GFRandom : public CFRandom
849 {
850 public:
851  GFRandom() {};
854  CFRandom * clone() const;
855 };
856 
857 /**
858  * generate random elements in F_p
859 **/
860 class FFRandom : public CFRandom
861 {
862 public:
863  FFRandom() {}
866  CFRandom * clone() const;
867 };
868 
869 /**
870  * generate random integers
871 **/
872 class IntRandom : public CFRandom
873 {
874 private:
875  int max;
876 public:
878  IntRandom( int m );
881  CFRandom * clone() const;
882 };
883 
884 /**
885  * generate random elements in F_p(alpha)
886 **/
887 class AlgExtRandomF : public CFRandom {
888 private:
890  CFRandom * gen;
891  int n;
893  AlgExtRandomF( const Variable & v, CFRandom * g, int nn );
895 public:
898  AlgExtRandomF( const Variable & v1, const Variable & v2 );
901  CFRandom * clone() const;
902 };
903 
904 class CFRandomFactory {
905 public:
906  static CFRandom * generate();
907 };
908 
909 /// random integers with abs less than n
910 int factoryrandom( int n );
911 
912 /// random seed initializer
913 void FACTORY_PUBLIC factoryseed( int s );
914 
915 
916 /* stuff included from ./fac_util.h */
917 
918 
919 /**
920  * class to do operations mod p^k for int's p and k
921 **/
922 class modpk
923 {
924 private:
927  int p;
928  int k;
929 public:
930  modpk();
931  modpk( int q, int l );
932  modpk( const modpk & m );
933  modpk& operator= ( const modpk& m );
934  ~modpk() {}
935  int getp() const { return p; }
936  int getk() const { return k; }
937  CanonicalForm inverse( const CanonicalForm & f, bool symmetric = true ) const;
938  CanonicalForm getpk() const { return pk; }
939  CanonicalForm operator() ( const CanonicalForm & f, bool symmetric = true ) const;
940 };
941 
942 
943 CanonicalForm replaceLc( const CanonicalForm & f, const CanonicalForm & c );
944 
945 
946 /* stuff included from ./cf_map.h */
947 
948 
949 /** class MapPair
950  *
951  * class MapPair - stores one mapping pair (Variable -> CanonicalForm).
952  *
953  * This class is only used to store such pairs. It has no
954  * methods to transform a CanonicalForm as the class CFMap has.
955  *
956  * V, S: the pair (V -> S)
957  *
958 **/
959 /** inline method
960  *
961  * Variable var () const
962  * CanonicalForm subst () const
963  *
964  * var(), subst() - selectors, return V and P, resp.
965  *
966 **/
967 class MapPair
968 {
969 private:
970  Variable V;
972 public:
973  MapPair ( const Variable & v, const CanonicalForm & s ) : V(v), S(s) {}
974  MapPair () : V(), S(1) {}
975  MapPair ( const MapPair & p ) : V(p.V), S(p.S) {}
976  ~MapPair () {}
977  MapPair & operator = ( const MapPair & p );
978  Variable var () const { return V; }
979  CanonicalForm subst () const { return S; }
980 #ifndef NOSTREAMIO
981  void print( OSTREAM&) const;
982  friend OSTREAM & operator << ( OSTREAM & s, const MapPair & p );
983 #endif /* NOSTREAMIO */
984 };
985 
988 
989 /** class CFMap
990  *
991  * class CFMap - class to map canonical forms.
992  *
993  * Use an object of class CFMap to insert 'values' into canonical
994  * form. Such a mapping is defined by a list of MapPairs (V -> S)
995  * describing which canonical form S to insert for variable V.
996  * Hereby, the substituted canonical forms are not subject to
997  * further substitutions.
998  *
999  * P: list of MapPairs, sorted by level in descending order
1000  *
1001 **/
1002 class CFMap
1003 {
1004 private:
1005  MPList P;
1006 public:
1007  CFMap () {}
1008  CFMap ( const CanonicalForm & s ) : P( MapPair( Variable(), s ) ) {}
1009  CFMap ( const Variable & v ) : P( MapPair( v, 1 ) ) {}
1010  CFMap ( const Variable & v, const CanonicalForm & s ) : P( MapPair( v, s ) ) {}
1011  ~CFMap () {}
1012  CFMap ( const CFList & L );
1013  CFMap ( const CFMap & m ) : P( m.P ) {}
1014  CFMap & operator = ( const CFMap & m );
1015  void newpair ( const Variable & v, const CanonicalForm & s );
1017 #ifndef NOSTREAMIO
1018  friend OSTREAM & operator << ( OSTREAM & s, const CFMap & m );
1019 #endif /* NOSTREAMIO */
1020 };
1021 
1022 CanonicalForm compress ( const CanonicalForm & f, CFMap & m );
1023 void compress ( const CFArray & a, CFMap & M, CFMap & N );
1024 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N );
1025 
1026 
1027 /* stuff included from ./cf_reval.h */
1028 
1029 
1030 /**
1031  * class to generate random evaluation points
1032  *
1033  * @sa cf_eval.h
1034 **/
1035 class REvaluation : public Evaluation
1036 {
1037 protected: // neeeded in FFREvaluation
1038  CFRandom * gen;
1039 public:
1041  REvaluation( int min0, int max0, const CFRandom & sample ) : Evaluation( min0, max0 ), gen( sample.clone() ) {}
1042  REvaluation( const REvaluation & e );
1045  void nextpoint();
1046  void nextpoint(int n);
1047 };
1048 
1049 
1050 /* stuff included from ./fac_sqrfree.h */
1051 
1052 
1053 /* stuff included from ./gfops.h */
1054 
1055 
1056 long gf_gf2ff ( long a );
1057 int gf_gf2ff ( int a );
1058 
1059 bool gf_isff ( long a );
1060 bool gf_isff ( int a );
1061 
1062 
1063 /* stuff included from ./cf_hnf.h */
1064 
1065 
1066 /**
1067  *
1068  * The input matrix A is square matrix of integers
1069  * output: the Hermite Normal Form of A; that is,
1070  * the unique m x m matrix whose rows span L, such that
1071  *
1072  * - lower triangular,
1073  * - the diagonal entries are positive,
1074  * - any entry below the diagonal is a non-negative number
1075  * strictly less than the diagonal entry in its column.
1076  *
1077  * @note: uses NTL
1078  *
1079 **/
1080 
1082 
1083 /**
1084  * performs LLL reduction.
1085  *
1086  * B is an m x n matrix, viewed as m rows of n-vectors. m may be less
1087  * than, equal to, or greater than n, and the rows need not be
1088  * linearly independent. B is transformed into an LLL-reduced basis,
1089  * and the return value is the rank r of B. The first m-r rows of B
1090  * are zero.
1091  *
1092  * More specifically, elementary row transformations are performed on
1093  * B so that the non-zero rows of new-B form an LLL-reduced basis
1094  * for the lattice spanned by the rows of old-B.
1095  * The default reduction parameter is delta=3/4, which means
1096  * that the squared length of the first non-zero basis vector
1097  * is no more than 2^{r-1} times that of the shortest vector in
1098  * the lattice.
1099  *
1100  * @note: uses NTL or FLINT
1101 **/
1102 
1104 
1105 
1106 /* stuff included from ./singext.h */
1107 
1108 
1109 void FACTORY_PUBLIC gmp_numerator ( const CanonicalForm & f, mpz_ptr result );
1110 
1111 void FACTORY_PUBLIC gmp_denominator ( const CanonicalForm & f, mpz_ptr result );
1112 
1113 int gf_value (const CanonicalForm & f );
1114 
1115 CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n );
1116 
1117 CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n, const mpz_ptr d, bool normalize );
1118 
1119 CanonicalForm make_cf_from_gf ( const int z );
1120 
1121 
1122 /* stuff included from ./cf_util.h */
1123 
1124 int igcd (int a, int b);
1125 int FACTORY_PUBLIC ipower ( int b, int n );
1126 void factoryError_intern(const char *s);
1127 EXTERN_VAR void (*factoryError)(const char *s);
1128 
1129 /* stuff included from ./facIrredTest.h */
1130 
1131 
1132 /// given some error probIrredTest detects irreducibility or reducibility of F
1133 /// with confidence level 1-error
1134 ///
1135 /// @return probIrredTest returns 1 for irreducibility, -1 for reducibility
1136 /// or 0 if the test is not applicable
1137 int FACTORY_PUBLIC probIrredTest (const CanonicalForm& F, ///< [in] some poly over Z/p
1138  double error ///< [in] 0 < error < 1
1139  );
1140 
1141 
1142 /* stuff included from ./facAbsFact.h */
1143 
1144 /// absolute factorization of a multivariate poly over Q
1145 ///
1146 /// @return absFactorize returns a list whose entries contain three
1147 /// entities:
1148 /// an absolute irreducible factor, an irreducible univariate polynomial
1149 /// that defines the minimal field extension over which the irreducible
1150 /// factor is defined (note: in case the factor is already defined over
1151 /// Q[t]/(t), 1 is returned), and the multiplicity of the
1152 /// absolute irreducible factor
1153 CFAFList FACTORY_PUBLIC absFactorize (const CanonicalForm& G ///<[in] poly over Q
1154  );
1155 
1156 /* stuff included from ./cfModResultant.h */
1157 
1158 /// modular resultant algorihtm over Z
1159 ///
1160 /// @return @a resultantZ returns the resultant of A and B wrt. x
1162 resultantZ (const CanonicalForm& A, ///<[in] some poly
1163  const CanonicalForm& B, ///<[in] some poly
1164  const Variable& x, ///<[in] some polynomial variable
1165  bool prob= true ///<[in] if true use probabilistic algorithm
1166  );
1167 
1168 /* stuff included from ./facAlgFunc.h */
1169 
1170 
1171 /// factorize a polynomial @a f that is irreducible over the ground field modulo
1172 /// an extension given by an irreducible characteristic set @a as, @a f is
1173 /// assumed to be integral, i.e. \f$ f\in K[x_1,\ldots,x_n]/(as) \f$, and each
1174 /// element of @a as is assumed to be integral as well. \f$ K \f$ must be either
1175 /// \f$ F_p \f$ or \f$ Q \f$.
1176 ///
1177 /// @return the returned factors are not necessarily monic but only primitive
1178 /// and the product of the factors equals @a f up to a unit.
1179 CFFList facAlgFunc2 (const CanonicalForm & f,///<[in] univariate poly
1180  const CFList & as ///<[in] irreducible characteristic
1181  ///< set
1182  );
1183 
1184 /// factorize a polynomial @a f modulo an extension given by an irreducible
1185 /// characteristic set as, @a f is assumed to be integral, i.e.
1186 /// \f$ f\in K[x_1,\ldots,x_n]/(as) \f$, and each element of @a as is assumed to
1187 /// be integral as well. \f$ K \f$ must be either \f$ F_p \f$ or \f$ Q \f$.
1188 ///
1189 /// @return the returned factors are not necessarily monic but only primitive
1190 /// and the product of the factors equals @a f up to a unit.
1191 CFFList facAlgFunc (const CanonicalForm & f, ///<[in] univariate poly
1192  const CFList & as ///<[in] irreducible characteristic
1193  ///< set
1194  );
1195 
1196 /* stuff included from ./cfCharSetsUtil.h */
1197 
1198 /**
1199  * class to store factors that get removed during char set computation
1200 **/
1201 class StoreFactors
1202 {
1203  public:
1204  CFList FS1; ///< factors that were removed
1205  CFList FS2; ///< candidate factors that might get removed
1206  inline StoreFactors& operator= (const StoreFactors& value)
1207  {
1208  if ( this != &value )
1209  {
1210  FS1 = value.FS1;
1211  FS2 = value.FS2;
1212  }
1213  return *this;
1214  }
1215 };
1216 
1218 Prem (const CanonicalForm& F, const CanonicalForm& G);
1219 
1220 
1221 /* stuff included from ./cfCharSets.h */
1222 
1223 
1224 /// basic set in the sense of Wang a.k.a. minimal ascending set in the sense of
1225 /// Greuel/Pfister
1226 CFList
1227 basicSet (const CFList& PS);
1228 
1229 /// characteristic set
1230 CFList
1231 charSet (const CFList& PS);
1232 
1233 /// modified medial set
1234 CFList
1235 modCharSet (const CFList& PS, StoreFactors& StoredFactors,
1236  bool removeContents= true);
1237 
1238 CFList
1239 modCharSet (const CFList& PS, bool removeContents);
1240 
1241 CFList
1242 charSetViaCharSetN (const CFList& PS);
1243 
1244 CFList
1245 charSetN (const CFList &PS);
1246 
1247 /// modified characteristic set, i.e. a characteristic set with certain
1248 /// factors removed
1249 CFList
1250 charSetViaModCharSet (const CFList& PS, StoreFactors& StoredFactors,
1251  bool removeContents= true);
1252 
1253 /// modified characteristic set, i.e. a characteristic set with certain
1254 /// factors removed
1255 CFList
1256 charSetViaModCharSet (const CFList& PS, bool removeContents= true);
1257 
1258 /// characteristic series
1259 ListCFList
1260 charSeries (const CFList& L);
1261 
1262 /// irreducible characteristic series
1264 irrCharSeries (const CFList & PS);
1265 
1266 // the next three give you a heuristically optimal reorderd list of the
1267 // variables. For internal and external (e.g. Singular/Macaulay2) library use.
1268 // This is really experimental!
1269 // See the comments in reorder.cc.
1270 //
1271 // this gives you a heuristically optimal ordering for the ring variables
1272 // if you use the irreducible characteristic series.
1273 Varlist neworder (const CFList & PolyList);
1274 
1275 // the same as neworder(...) only returning a list of CanonicalForm 's
1276 // (i.e. the variables as CanonicalForms)
1277 CFList newordercf (const CFList & PolyList);
1278 
1279 // the same as neworder(...) only returning a list of int 's (i.e. the levels)
1280 IntList FACTORY_PUBLIC neworderint (const CFList & PolyList);
1281 
1282 // for library internal use only:
1283 // next function reorders the variables in PS:
1284 // a code segment to use:
1285 // ...
1286 // #include "tmpl_inst.h" // for typedef's
1287 // CFList PS= <setup-your-list-of-CanonicalForms>;
1288 // Varlist betterorder= neworder(PS);
1289 // PS= reorder(betterorder,PS); // reorder variables in PS from oldorder
1290 // to betterorder
1291 // ListCFList Q= IrrCharSeries( PS );
1292 // Q= reorder(betterorder,Q); // revert ordering to oldorder
1293 //
1294 CFList reorder (const Varlist & betterorder, const CFList & PS);
1295 CFFList reorder (const Varlist & betterorder, const CFFList & PS);
1296 ListCFList reorder (const Varlist & betterorder, const ListCFList & Q);
1297 
1298 /* stuff included from ./cfUnivarGcd.h */
1299 
1301 extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b );
1302 
1303 
1304 #endif /* ! INCL_FACTORY_H */
bool operator!=(const Rational &a, const Rational &b)
Definition: GMPrat.cc:318
bool operator<(const Rational &a, const Rational &b)
Definition: GMPrat.cc:288
bool operator==(const Rational &a, const Rational &b)
Definition: GMPrat.cc:312
bool operator>(const Rational &a, const Rational &b)
Definition: GMPrat.cc:300
bool operator<=(const Rational &a, const Rational &b)
Definition: GMPrat.cc:294
bool operator>=(const Rational &a, const Rational &b)
Definition: GMPrat.cc:306
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
ISTREAM & operator>>(ISTREAM &is, CanonicalForm &cf)
bool tryDivremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const CanonicalForm &M, bool &fail)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
FILE * f
Definition: checklibs.c:9
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:94
FFGenerator ** gensf
Definition: cf_generator.h:97
CFGenerator * clone() const
GFGenerator ** gensg
Definition: cf_generator.h:98
CanonicalForm item() const
AlgExtGenerator(const Variable &a)
bool hasItems() const
Definition: factory.h:773
AlgExtGenerator(const AlgExtGenerator &)
AlgExtGenerator & operator=(const AlgExtGenerator &)
Variable algext
Definition: cf_generator.h:96
generate random elements in F_p(alpha)
Definition: cf_random.h:70
CFRandom * clone() const
AlgExtRandomF(const Variable &v, CFRandom *g, int nn)
CFRandom * gen
Definition: cf_random.h:73
Variable algext
Definition: cf_random.h:72
AlgExtRandomF & operator=(const AlgExtRandomF &)
Definition: cf_random.cc:123
AlgExtRandomF(const Variable &v1, const Variable &v2)
AlgExtRandomF(const Variable &v)
AlgExtRandomF(const AlgExtRandomF &)
CanonicalForm generate() const
int max() const
Definition: ftmpl_array.cc:104
int min() const
Definition: ftmpl_array.cc:98
static CFGenerator * generate()
virtual class for generators
Definition: cf_generator.h:22
CFGenerator()
Definition: factory.h:689
virtual CanonicalForm item() const
Definition: factory.h:693
virtual ~CFGenerator()
Definition: factory.h:690
virtual bool hasItems() const
Definition: factory.h:691
virtual CFGenerator * clone() const
Definition: factory.h:695
virtual void next()
Definition: factory.h:694
virtual void reset()
Definition: factory.h:692
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CFIterator(const CFIterator &)
CF_NO_INLINE int exp() const
get the current exponent
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CFIterator(const CanonicalForm &, const Variable &)
CFIterator(const CanonicalForm &)
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
class CFMap
Definition: cf_map.h:85
CFMap(const Variable &v)
Definition: factory.h:1009
CanonicalForm operator()(const CanonicalForm &f) const
CanonicalForm CFMap::operator () ( const CanonicalForm & f ) const.
Definition: cf_map.cc:178
CFMap(const CFMap &m)
Definition: factory.h:1013
CFMap(const CFList &L)
void newpair(const Variable &v, const CanonicalForm &s)
CFMap(const Variable &v, const CanonicalForm &s)
Definition: factory.h:1010
MPList P
Definition: cf_map.h:87
~CFMap()
Definition: factory.h:1011
CFMap & operator=(const CFMap &m)
CFMap & CFMap::operator = ( const CFMap & m )
Definition: cf_map.cc:77
CFMap()
Definition: factory.h:1007
friend OSTREAM & operator<<(OSTREAM &s, const CFMap &m)
OSTREAM & operator << ( OSTREAM & s, const CFMap & m )
Definition: cf_map.cc:191
CFMap(const CanonicalForm &s)
Definition: factory.h:1008
static CFRandom * generate()
virtual class for random element generation
Definition: cf_random.h:21
virtual CanonicalForm generate() const
Definition: factory.h:841
virtual CFRandom * clone() const
Definition: factory.h:842
virtual ~CFRandom()
Definition: factory.h:840
factory's main class
Definition: canonicalform.h:86
CanonicalForm den() const
CF_INLINE CanonicalForm(const Variable &)
CanonicalForm genOne() const
CanonicalForm LC() const
bool inGF() const
CF_NO_INLINE bool isZero() const
bool isHomogeneous() const
bool isFFinGF() const
CF_INLINE CanonicalForm(const CanonicalForm &)
CF_NO_INLINE ~CanonicalForm()
bool inFF() const
int degree() const
bool inExtension() const
int sign() const
InternalCF * getval() const
CanonicalForm deepCopy() const
bool inQuotDomain() const
bool inPolyDomain() const
CF_INLINE CanonicalForm()
CanonicalForm Lc() const
Variable mvar() const
bool inQ() const
CF_INLINE CanonicalForm(InternalCF *)
CF_NO_INLINE bool isOne() const
CF_INLINE CanonicalForm(const Variable &, int)
CanonicalForm tailcoeff() const
long intval() const
CanonicalForm genZero() const
CanonicalForm tailcoeff(const Variable &v) const
CanonicalForm deriv() const
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
bool inCoeffDomain() const
void print(OSTREAM &) const
bool inZ() const
CanonicalForm & mod(const CanonicalForm &)
int level() const
CanonicalForm & div(const CanonicalForm &)
CF_INLINE CanonicalForm(const int)
CanonicalForm sqrt() const
bool inBaseDomain() const
bool isImm() const
Definition: factory.h:260
CanonicalForm mapinto() const
int ilog2() const
int degree(const Variable &v) const
CF_INLINE CanonicalForm(const long)
CanonicalForm lc() const
void mpzval(mpz_t val) const
CanonicalForm LC(const Variable &v) const
CanonicalForm deriv(const Variable &x) const
CanonicalForm(const char *, const int base=10)
CanonicalForm num() const
void print(OSTREAM &, char *) const
int taildegree() const
bool isUnivariate() const
class to evaluate a polynomial at points
Definition: cf_eval.h:32
void setValue(int i, const CanonicalForm &f)
CanonicalForm operator[](const Variable &v) const
Definition: factory.h:669
CFArray values
Definition: cf_eval.h:34
Evaluation(int min0, int max0)
Definition: factory.h:662
Evaluation & operator=(const Evaluation &e)
Definition: cf_eval.cc:15
int min() const
Definition: factory.h:666
virtual ~Evaluation()
Definition: factory.h:664
int max() const
Definition: factory.h:667
virtual void nextpoint()
CanonicalForm operator()(const CanonicalForm &f) const
Definition: cf_eval.cc:24
CanonicalForm operator[](int i) const
Definition: cf_eval.h:43
Evaluation(const Evaluation &e)
Definition: factory.h:663
friend OSTREAM & operator<<(OSTREAM &s, const Evaluation &e)
Definition: cf_eval.cc:60
Evaluation()
Definition: factory.h:661
generate all elements in F_p starting from 0
Definition: cf_generator.h:56
CFGenerator * clone() const
FFGenerator()
Definition: factory.h:725
void operator++()
Definition: cf_generator.h:66
~FFGenerator()
Definition: factory.h:726
bool hasItems() const
void reset()
Definition: factory.h:728
CanonicalForm item() const
generate random elements in F_p
Definition: cf_random.h:44
CanonicalForm generate() const
FFRandom()
Definition: factory.h:863
~FFRandom()
Definition: factory.h:864
CFRandom * clone() const
generate all elements in GF starting from 0
Definition: cf_generator.h:75
bool hasItems() const
CanonicalForm item() const
CFGenerator * clone() const
void operator++()
Definition: cf_generator.h:85
~GFGenerator()
Definition: factory.h:745
void reset()
generate random elements in GF
Definition: cf_random.h:32
~GFRandom()
Definition: factory.h:852
CanonicalForm generate() const
GFRandom()
Definition: factory.h:851
CFRandom * clone() const
generate integers starting from 0
Definition: cf_generator.h:37
~IntGenerator()
Definition: factory.h:707
CFGenerator * clone() const
void operator++()
Definition: cf_generator.h:47
void reset()
Definition: factory.h:709
CanonicalForm item() const
bool hasItems() const
IntGenerator()
Definition: factory.h:706
generate random integers
Definition: cf_random.h:56
int max
Definition: cf_random.h:58
CanonicalForm generate() const
IntRandom(int m)
CFRandom * clone() const
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
class MapPair
Definition: cf_map.h:50
Variable var() const
Definition: factory.h:978
CanonicalForm S
Definition: cf_map.h:53
void print(OSTREAM &) const
MapPair(const Variable &v, const CanonicalForm &s)
Definition: factory.h:973
MapPair(const MapPair &p)
Definition: factory.h:975
friend OSTREAM & operator<<(OSTREAM &s, const MapPair &p)
OSTREAM & operator << ( OSTREAM & s, const MapPair & p )
Definition: cf_map.cc:44
Variable V
Definition: cf_map.h:52
MapPair & operator=(const MapPair &p)
MapPair & MapPair::operator = ( const MapPair & p )
Definition: cf_map.cc:28
~MapPair()
Definition: factory.h:976
MapPair()
Definition: factory.h:974
CanonicalForm subst() const
Definition: factory.h:979
class to generate random evaluation points
Definition: cf_reval.h:26
CFRandom * gen
Definition: cf_reval.h:28
REvaluation(const REvaluation &e)
REvaluation(int min0, int max0, const CFRandom &sample)
Definition: factory.h:1041
void nextpoint()
void nextpoint(int n)
REvaluation & operator=(const REvaluation &e)
Definition: cf_reval.cc:31
class to store factors that get removed during char set computation
CFList FS2
candidate factors that might get removed
StoreFactors & operator=(const StoreFactors &value)
CFList FS1
factors that were removed
factory's class for variables
Definition: factory.h:127
Variable(const Variable &v)
Definition: factory.h:136
friend void swap_levels()
Variable()
Definition: factory.h:132
char name() const
Definition: variable.cc:122
int level() const
Definition: factory.h:143
Variable next() const
Definition: factory.h:146
static Variable highest()
Definition: factory.h:145
~Variable()
Definition: factory.h:137
int _level
Definition: factory.h:129
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
CanonicalForm operator()(const CanonicalForm &f, bool symmetric=true) const
Definition: fac_util.cc:79
modpk & operator=(const modpk &m)
Definition: fac_util.cc:47
modpk(int q, int l)
CanonicalForm inverse(const CanonicalForm &f, bool symmetric=true) const
int getk() const
Definition: factory.h:936
CanonicalForm getpk() const
Definition: factory.h:938
int getp() const
Definition: factory.h:935
modpk(const modpk &m)
int p
Definition: fac_util.h:27
CanonicalForm pkhalf
Definition: fac_util.h:26
~modpk()
Definition: factory.h:934
CanonicalForm pk
Definition: fac_util.h:25
int k
Definition: fac_util.h:28
Definition: int_poly.h:33
void error(const char *fmt,...)
Definition: emacs.cc:55
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm mipo
Definition: facAlgExt.cc:57
b *CanonicalForm B
Definition: facBivar.cc:52
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
void sort(CFArray &A, int l=0)
quick sort A
bool FACTORY_PUBLIC isOn(int)
switches
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:260
Array< int > Intarray
Definition: factory.h:546
CFMatrix *FACTORY_PUBLIC cf_HNF(CFMatrix &A)
The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is,...
Definition: cf_hnf.cc:44
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
CF_INLINE CanonicalForm operator+(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs...
Definition: cf_inline.cc:503
#define LEVELBASE
Definition: factory.h:82
int FACTORY_PUBLIC cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
int headdegree(const CanonicalForm &f)
Definition: factory.h:510
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: factory.h:100
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CFMatrix *FACTORY_PUBLIC cf_LLL(CFMatrix &A)
performs LLL reduction.
Definition: cf_hnf.cc:66
CanonicalForm mapinto(const CanonicalForm &f)
Definition: factory.h:496
ListCFList charSeries(const CFList &L)
characteristic series
Definition: cfCharSets.cc:411
AFactor< CanonicalForm > CFAFactor
Definition: factory.h:530
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CanonicalForm FACTORY_PUBLIC blcm(const CanonicalForm &f, const CanonicalForm &g)
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CFList charSet(const CFList &PS)
characteristic set
Definition: cfCharSets.cc:187
CanonicalForm FACTORY_PUBLIC make_cf(const mpz_ptr n)
Definition: singext.cc:66
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm lc(const CanonicalForm &f)
Definition: factory.h:445
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
ListCFList FACTORY_PUBLIC irrCharSeries(const CFList &PS)
irreducible characteristic series
Definition: cfCharSets.cc:568
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: factory.h:98
int ilog2(const CanonicalForm &a)
Definition: factory.h:493
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:697
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CanonicalForm FACTORY_PUBLIC extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:174
#define OSTREAM
Definition: factory.h:40
int level(const Variable &v)
Definition: factory.h:188
IntList FACTORY_PUBLIC neworderint(const CFList &PolyList)
Definition: cfCharSets.cc:88
ListIterator< Variable > VarlistIterator
Definition: factory.h:545
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:234
char name(const Variable &v)
Definition: factory.h:189
void FACTORY_PUBLIC Off(int)
switches
void psqr(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
int sign(const CanonicalForm &a)
Definition: factory.h:484
CanonicalForm FACTORY_PUBLIC gcd(const CanonicalForm &, const CanonicalForm &)
Definition: cf_gcd.cc:685
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
CanonicalForm tailcoeff(const CanonicalForm &f)
Definition: factory.h:466
char getDefaultVarName()
Definition: variable.cc:244
void prune1(const Variable &alpha)
Definition: variable.cc:291
CanonicalForm FACTORY_PUBLIC determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:202
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
EXTERN_VAR void(* factoryError)(const char *s)
Definition: factory.h:1127
int FACTORY_PUBLIC cf_getNumPrimes()
Definition: cf_primes.cc:23
ListIterator< CFAFactor > CFAFListIterator
Definition: factory.h:532
int taildegree(const CanonicalForm &f)
Definition: factory.h:463
CFList charSetN(const CFList &PS)
medial set
Definition: cfCharSets.cc:216
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator%(const CanonicalForm &, const CanonicalForm &)
int FACTORY_PUBLIC probIrredTest(const CanonicalForm &F, double error)
given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-er...
Definition: facIrredTest.cc:63
int degree(const CanonicalForm &f)
Definition: factory.h:457
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: factory.h:487
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957
CanonicalForm make_cf_from_gf(const int z)
Definition: singext.cc:76
CanonicalForm FACTORY_PUBLIC lcm(const CanonicalForm &, const CanonicalForm &)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:763
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:279
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:289
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:42
int size_maxexp(const CanonicalForm &f, int &maxexp)
Definition: cf_ops.cc:641
int getGFDegree()
Definition: cf_char.cc:75
#define CF_INLINE
Definition: factory.h:793
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
Definition: cfCharSets.cc:150
int ExtensionLevel()
Definition: variable.cc:254
int igcd(int a, int b)
Definition: cf_util.cc:56
CFList newordercf(const CFList &PolyList)
Definition: cfCharSets.cc:75
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
Varlist neworder(const CFList &PolyList)
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial f modulo an extension given by an irreducible characteristic set as,...
Definition: facAlgFunc.cc:1043
Array< CanonicalForm > CFArray
Definition: factory.h:538
CanonicalForm FACTORY_PUBLIC bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial f that is irreducible over the ground field modulo an extension given by an ir...
Definition: facAlgFunc.cc:905
int is_imm(const InternalCF *const ptr)
Definition: factory.h:215
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: factory.h:104
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: factory.h:94
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator-(const CanonicalForm &, const CanonicalForm &)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob=true)
modular resultant algorihtm over Z
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition: cf_chinese.cc:57
term * termList
Definition: factory.h:798
ListIterator< CFFactor > CFFListIterator
Definition: factory.h:535
const char factoryConfiguration[]
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void factoryError_intern(const char *s)
Definition: cf_util.cc:75
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
Matrix< CanonicalForm > CFMatrix
Definition: factory.h:539
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: factory.h:88
CanonicalForm abs(const CanonicalForm &f)
inline CanonicalForm abs ( const CanonicalForm & f )
Definition: factory.h:638
int gf_value(const CanonicalForm &f)
Definition: singext.cc:60
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: factory.h:96
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
List< CFList > ListCFList
Definition: factory.h:540
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition: factory.h:114
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:313
bool linearSystemSolve(CFMatrix &M)
Definition: cf_linsys.cc:78
ListIterator< CanonicalForm > CFListIterator
Definition: factory.h:537
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
Definition: cf_ops.cc:440
CanonicalForm num(const CanonicalForm &f)
Definition: factory.h:478
CanonicalForm den(const CanonicalForm &f)
Definition: factory.h:481
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm sqrt(const CanonicalForm &a)
Definition: factory.h:490
List< CFFactor > CFFList
Definition: factory.h:534
CanonicalForm Lc(const CanonicalForm &f)
Definition: factory.h:448
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: factory.h:102
ListIterator< CFList > ListCFListIterator
Definition: factory.h:541
List< int > IntList
Definition: factory.h:542
CanonicalForm psq(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator/(const CanonicalForm &, const CanonicalForm &)
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: factory.h:92
CanonicalForm FACTORY_PUBLIC gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:492
long gf_gf2ff(long a)
Definition: gfops.cc:209
CanonicalForm head(const CanonicalForm &f)
Definition: factory.h:501
CanonicalForm getGFGenerator()
Definition: cf_char.cc:81
#define ISTREAM
Definition: factory.h:41
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: factory.h:90
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition: cfCharSets.cc:101
int FACTORY_PUBLIC cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CanonicalForm FACTORY_PUBLIC power(const CanonicalForm &f, int n)
exponentiation
EXTERN_VAR int singular_homog_flag
Definition: factory.h:586
#define CF_NO_INLINE
Definition: factory.h:795
static const int SW_FAC_QUADRATICLIFT
Definition: factory.h:110
CFList modCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
modified medial set
Definition: cfCharSets.cc:284
int FACTORY_PUBLIC cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
Factor< CanonicalForm > CFFactor
Definition: factory.h:533
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition: cf_ops.cc:660
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition: factory.h:106
#define LEVELQUOT
Definition: factory.h:84
CF_INLINE CanonicalForm operator*(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:524
CanonicalForm euclideanNorm(const CanonicalForm &f)
CanonicalForm euclideanNorm ( const CanonicalForm & f )
CanonicalForm apply(const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) )
Definition: cf_ops.cc:402
CFAFList FACTORY_PUBLIC absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
Definition: facAbsFact.cc:262
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
int FACTORY_PUBLIC cf_getBigPrime(int i)
Definition: cf_primes.cc:39
void FACTORY_PUBLIC gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
static const int SW_USE_FL_FAC_0A
set to 1 to prefer flints multivariate factorization over Z/p(a)
Definition: factory.h:116
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
modified characteristic set, i.e. a characteristic set with certain factors removed
Definition: cfCharSets.cc:356
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
int factoryrandom(int n)
random integers with abs less than n
Definition: cf_random.cc:180
void FACTORY_PUBLIC factoryseed(int s)
random seed initializer
Definition: cf_random.cc:189
void FACTORY_PUBLIC On(int)
switches
List< CanonicalForm > CFList
Definition: factory.h:536
ListIterator< MapPair > MPListIterator
Definition: factory.h:987
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
void FACTORY_PUBLIC gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition: factory.h:112
char getDefaultExtName()
Definition: variable.cc:249
Variable mvar(const CanonicalForm &f)
Definition: factory.h:475
CanonicalForm LC(const CanonicalForm &f)
Definition: factory.h:451
List< MapPair > MPList
Definition: factory.h:986
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition: factory.h:108
ListIterator< int > IntListIterator
Definition: factory.h:543
int FACTORY_PUBLIC cf_getPrime(int i)
Definition: cf_primes.cc:14
int FACTORY_PUBLIC ipower(int b, int n)
int ipower ( int b, int m )
Definition: cf_util.cc:27
List< CFAFactor > CFAFList
Definition: factory.h:531
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226
void FACTORY_PUBLIC chineseRemainderCached(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew, CFArray &inv)
Definition: cf_chinese.cc:308
List< Variable > Varlist
Definition: factory.h:544
bool gf_isff(long a)
Definition: gfops.cc:253
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition: fac_util.cc:90
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
#define EXTERN_VAR
Definition: globaldefs.h:6
#define FACTORY_PUBLIC
Definition: globaldefs.h:25
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR jList * Q
Definition: janet.cc:30
char N base
Definition: ValueTraits.h:144
campf< Precision > & operator-=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1156
campf< Precision > & operator*=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1164
campf< Precision > & operator/=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1200
campf< Precision > & operator+=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1144
ostream & operator<<(ostream &s, const spectrum &spec)
Definition: semic.cc:249
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
int name
New type name for int.
Definition: templateForC.h:21