My Project
Loading...
Searching...
No Matches
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
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
60extern const char factoryConfiguration[];
61
62
63/* stuff included from ./cf_primes.h */
64
65
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
88static const int SW_RATIONAL = 0;
89/// set to 1 for symmetric representation over F_q
90static const int SW_SYMMETRIC_FF = 1;
91/// set to 1 to use EZGCD over Z
92static const int SW_USE_EZGCD = 2;
93/// set to 1 to use EZGCD over F_q
94static const int SW_USE_EZGCD_P = 3;
95/// set to 1 to sort factors in a factorization
96static const int SW_USE_NTL_SORT=4;
97/// set to 1 to use modular gcd over Z
98static const int SW_USE_CHINREM_GCD=5;
99/// set to 1 to use Encarnacion GCD over Q(a)
100static const int SW_USE_QGCD=6;
101/// set to 1 to use modular GCD over F_q
102static const int SW_USE_FF_MOD_GCD=7;
103/// set to 1 to use Flints gcd over F_p
104static const int SW_USE_FL_GCD_P=8;
105/// set to 1 to use Flints gcd over Q/Z
106static const int SW_USE_FL_GCD_0=9;
107/// set to 1 to use Factorys Berlekamp alg.
108static const int SW_BERLEKAMP=10;
109
110static const int SW_FAC_QUADRATICLIFT=11;
111/// set to 1 to prefer flints multivariate factorization over Z/p
112static const int SW_USE_FL_FAC_P=12;
113/// set to 1 to prefer flints multivariate factorization over Z/p
114static const int SW_USE_FL_FAC_0=13;
115/// set to 1 to prefer flints multivariate factorization over Z/p(a)
116static const int SW_USE_FL_FAC_0A=14;
117
118/* stuff included from ./variable.h */
119
120
121class CanonicalForm;
122
123/**
124 * factory's class for variables
125**/
127{
128private:
129 int _level;
130 Variable( int l, bool flag );
131public:
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) {}
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**/
186Variable FACTORY_PUBLIC rootOf( const CanonicalForm &, char name = '@' );
187
188inline int level( const Variable & v ) { return v.level(); }
189inline char name( const Variable & v ) { return v.name(); }
190
191void setReduce( const Variable & alpha, bool reduce );
192void setMipo ( const Variable & alpha, const CanonicalForm & mipo);
193CanonicalForm getMipo( const Variable & alpha, const Variable & x );
194bool hasMipo( const Variable & alpha );
195
196char getDefaultVarName();
197char getDefaultExtName();
198
200void prune1 (const Variable& alpha);
201int 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
213class InternalCF;
214
215inline 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{
237private:
238 InternalCF *value;
239public:
240 // constructors, destructors, selectors
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
283 CanonicalForm LC ( const Variable & v ) const;
284
285 int degree () const;
286 int degree ( const Variable & v ) const;
287
290 int taildegree () const;
291
292 int level () const;
293 Variable mvar () const;
294
297
298 // assignment operators
300 CF_NO_INLINE CanonicalForm& operator = ( const long );
301
302 CanonicalForm& operator += ( const CanonicalForm& );
303 CanonicalForm& operator -= ( const CanonicalForm& );
304 CanonicalForm& operator *= ( const CanonicalForm& );
305 CanonicalForm& operator /= ( const CanonicalForm& );
306 CanonicalForm& operator %= ( const CanonicalForm& );
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
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
356operator + ( const CanonicalForm&, const CanonicalForm& );
357
360
362operator * ( const CanonicalForm&, const CanonicalForm& );
363
366
369
371div ( const CanonicalForm&, const CanonicalForm& );
372
374mod ( const CanonicalForm&, const CanonicalForm& );
375
376
377//{{{ function declarations from canonicalform.cc
379
381
382CanonicalForm 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
405
407
408int getNumVars( const CanonicalForm & f );
409
411
412CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) );
413
415
416int * degrees ( const CanonicalForm & f, int * degs = 0 );
417
418int totaldegree ( const CanonicalForm & f );
419
420int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 );
421
422int size ( const CanonicalForm & f, const Variable & v );
423
424int size ( const CanonicalForm & f );
425
426int size_maxexp ( const CanonicalForm & f, int& maxexp );
427
429
430bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
431
432CanonicalForm 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//}}}
444inline CanonicalForm
445lc ( const CanonicalForm & f ) { return f.lc(); }
446
447inline CanonicalForm
448Lc ( const CanonicalForm & f ) { return f.Lc(); }
449
450inline CanonicalForm
451LC ( const CanonicalForm & f ) { return f.LC(); }
452
453inline CanonicalForm
454LC ( const CanonicalForm & f, const Variable & v ) { return f.LC( v ); }
455
456inline int
457degree ( const CanonicalForm & f ) { return f.degree(); }
458
459inline int
460degree ( const CanonicalForm & f, const Variable & v ) { return f.degree( v ); }
461
462inline int
463taildegree ( const CanonicalForm & f ) { return f.taildegree(); }
464
465inline CanonicalForm
466tailcoeff ( const CanonicalForm & f ) { return f.tailcoeff(); }
467
468inline CanonicalForm
469tailcoeff (const CanonicalForm& f, const Variable& v) { return f.tailcoeff(v); }
470
471inline int
472level ( const CanonicalForm & f ) { return f.level(); }
473
474inline Variable
475mvar ( const CanonicalForm & f ) { return f.mvar(); }
476
477inline CanonicalForm
478num ( const CanonicalForm & f ) { return f.num(); }
479
480inline CanonicalForm
481den ( const CanonicalForm & f ) { return f.den(); }
482
483inline int
484sign ( const CanonicalForm & a ) { return a.sign(); }
485
486inline CanonicalForm
487deriv ( const CanonicalForm & f, const Variable & x ) { return f.deriv( x ); }
488
489inline CanonicalForm
490sqrt ( const CanonicalForm & a ) { return a.sqrt(); }
491
492inline int
493ilog2 ( const CanonicalForm & a ) { return a.ilog2(); }
494
495inline CanonicalForm
496mapinto ( const CanonicalForm & f ) { return f.mapinto(); }
497//}}}
498
499//{{{ inline functions
500inline CanonicalForm
502{
503 if ( f.level() > 0 )
504 return power( f.mvar(), f.degree() ) * f.LC();
505 else
506 return f;
507}
508
509inline int
510headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
511
512
513//}}}
514
515//{{{ other function declarations
516void FACTORY_PUBLIC setCharacteristic( int c ); // -> Fp && Q
517void setCharacteristic( int c, int n ); // -> PrimePower
518void setCharacteristic( int c, int n, char name ); // -> GF(q)
519
521int getGFDegree();
523
524void FACTORY_PUBLIC On( int );
525void FACTORY_PUBLIC Off( int );
526bool FACTORY_PUBLIC isOn( int );
527//}}}
528
529//{{{ type definitions
531typedef List <CFAFactor> CFAFList;
547//}}}
548
549
550/* stuff included from ./cf_algorithm.h */
551
552
553//{{{ function declarations from cf_algorithm.cc
554CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
555
556CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
557
558void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x );
559
561
562bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
563
564bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot );
565
566bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );
567
569
571//}}}
572
573//{{{ function declarations from cf_chinese.cc
574void FACTORY_PUBLIC chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew );
575
576void FACTORY_PUBLIC chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );
577
578void FACTORY_PUBLIC chineseRemainderCached ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew, CFArray &inv );
580
581
582CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
583//}}}
584
585//{{{ function declarations from cf_factor.cc
587
588bool isPurePoly(const CanonicalForm & f);
589
590bool isPurePoly_m(const CanonicalForm & f);
591
592CFFList FACTORY_PUBLIC factorize ( const CanonicalForm & f, bool issqrfree = false );
593
595
596CFFList FACTORY_PUBLIC sqrFree ( const CanonicalForm & f, bool sort= false );
597
600 const Variable & v1, const Variable & v2);
603void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
604
605
606//}}}
607
608//{{{ function declarations from cf_linsys.cc
609bool linearSystemSolve ( CFMatrix & M );
610
612//}}}
613
614//{{{ function declarations from cf_resultant.cc
615CFArray 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**/
637inline CanonicalForm
638abs ( 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**/
656class Evaluation
657{
658protected:
660public:
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**/
686class CFGenerator
687{
688public:
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**/
701class IntGenerator : public CFGenerator
702{
703private:
704 int current;
705public:
708 bool hasItems() const;
709 void reset() { current = 0; }
711 void next();
712 void operator++ () { next(); }
713 void operator++ ( int ) { next(); }
715};
716
717/**
718 * generate all elements in F_p starting from 0
719**/
720class FFGenerator : public CFGenerator
721{
722private:
723 int current;
724public:
727 bool hasItems() const;
728 void reset() { current = 0; }
730 void next();
731 void operator++ () { next(); }
732 void operator++ ( int ) { next(); }
734};
735
736/**
737 * generate all elements in GF starting from 0
738**/
739class GFGenerator : public CFGenerator
740{
741private:
742 int current;
743public:
746 bool hasItems() const;
747 void reset();
749 void next();
750 void operator++ () { next(); }
751 void operator++ ( int ) { next(); }
753};
754
755/**
756 * generate all elements in F_p(alpha) starting from 0
757**/
758class AlgExtGenerator: public CFGenerator
759{
760private:
764 int n;
765 bool nomoreitems;
769public:
772
773 bool hasItems() const { return ! nomoreitems; }
774 void reset();
776 void next();
777 void operator++ () { next(); }
778 void operator++ ( int ) { next(); }
780};
781
782class CFGenFactory
783{
784public:
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
798class term;
799typedef 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**/
808private:
809 CanonicalForm data;
810 termList cursor;
811 bool ispoly, hasterms;
812public:
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**/
838class CFRandom {
839public:
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**/
848class GFRandom : public CFRandom
849{
850public:
854 CFRandom * clone() const;
855};
856
857/**
858 * generate random elements in F_p
859**/
860class FFRandom : public CFRandom
861{
862public:
866 CFRandom * clone() const;
867};
868
869/**
870 * generate random integers
871**/
872class IntRandom : public CFRandom
873{
874private:
875 int max;
876public:
878 IntRandom( int m );
881 CFRandom * clone() const;
882};
883
884/**
885 * generate random elements in F_p(alpha)
886**/
887class AlgExtRandomF : public CFRandom {
888private:
890 CFRandom * gen;
891 int n;
893 AlgExtRandomF( const Variable & v, CFRandom * g, int nn );
895public:
898 AlgExtRandomF( const Variable & v1, const Variable & v2 );
901 CFRandom * clone() const;
902};
903
904class CFRandomFactory {
905public:
906 static CFRandom * generate();
907};
908
909/// random integers with abs less than n
910int factoryrandom( int n );
911
912/// random seed initializer
913void 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**/
922class modpk
923{
924private:
927 int p;
928 int k;
929public:
931 modpk( int q, int l );
932 modpk( const modpk & m );
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
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**/
967class MapPair
968{
969private:
970 Variable V;
972public:
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) {}
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**/
1002class CFMap
1003{
1004private:
1005 MPList P;
1006public:
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 ) ) {}
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
1023void compress ( const CFArray & a, CFMap & M, CFMap & N );
1024void 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**/
1035class REvaluation : public Evaluation
1036{
1037protected: // neeeded in FFREvaluation
1038 CFRandom * gen;
1039public:
1041 REvaluation( int min0, int max0, const CFRandom & sample ) : Evaluation( min0, max0 ), gen( sample.clone() ) {}
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
1056long gf_gf2ff ( long a );
1057int gf_gf2ff ( int a );
1058
1059bool gf_isff ( long a );
1060bool 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
1109void FACTORY_PUBLIC gmp_numerator ( const CanonicalForm & f, mpz_ptr result );
1110
1111void FACTORY_PUBLIC gmp_denominator ( const CanonicalForm & f, mpz_ptr result );
1112
1113int gf_value (const CanonicalForm & f );
1114
1115CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n );
1116
1117CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n, const mpz_ptr d, bool normalize );
1118
1119CanonicalForm make_cf_from_gf ( const int z );
1120
1121
1122/* stuff included from ./cf_util.h */
1123
1124int igcd (int a, int b);
1125int FACTORY_PUBLIC ipower ( int b, int n );
1126void factoryError_intern(const char *s);
1127EXTERN_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
1137int 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
1153CFAFList 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
1162resultantZ (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.
1179CFFList 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.
1191CFFList 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**/
1201class StoreFactors
1202{
1203 public:
1204 CFList FS1; ///< factors that were removed
1205 CFList FS2; ///< candidate factors that might get removed
1207 {
1208 if ( this != &value )
1209 {
1210 FS1 = value.FS1;
1211 FS2 = value.FS2;
1212 }
1213 return *this;
1214 }
1215};
1216
1218Prem (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
1226CFList
1227basicSet (const CFList& PS);
1228
1229/// characteristic set
1230CFList
1231charSet (const CFList& PS);
1232
1233/// modified medial set
1234CFList
1235modCharSet (const CFList& PS, StoreFactors& StoredFactors,
1236 bool removeContents= true);
1237
1238CFList
1239modCharSet (const CFList& PS, bool removeContents);
1240
1241CFList
1242charSetViaCharSetN (const CFList& PS);
1243
1244CFList
1245charSetN (const CFList &PS);
1246
1247/// modified characteristic set, i.e. a characteristic set with certain
1248/// factors removed
1249CFList
1250charSetViaModCharSet (const CFList& PS, StoreFactors& StoredFactors,
1251 bool removeContents= true);
1252
1253/// modified characteristic set, i.e. a characteristic set with certain
1254/// factors removed
1255CFList
1256charSetViaModCharSet (const CFList& PS, bool removeContents= true);
1257
1258/// characteristic series
1260charSeries (const CFList& L);
1261
1262/// irreducible characteristic series
1264irrCharSeries (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.
1273Varlist neworder (const CFList & PolyList);
1274
1275// the same as neworder(...) only returning a list of CanonicalForm 's
1276// (i.e. the variables as CanonicalForms)
1277CFList newordercf (const CFList & PolyList);
1278
1279// the same as neworder(...) only returning a list of int 's (i.e. the levels)
1280IntList 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//
1294CFList reorder (const Varlist & betterorder, const CFList & PS);
1295CFFList reorder (const Varlist & betterorder, const CFFList & PS);
1296ListCFList reorder (const Varlist & betterorder, const ListCFList & Q);
1297
1298/* stuff included from ./cfUnivarGcd.h */
1299
1301extgcd ( 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,...
#define OSTREAM
Definition: canonicalform.h:16
#define CF_INLINE
Definition: canonicalform.h:54
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:65
#define ISTREAM
Definition: canonicalform.h:17
#define CF_NO_INLINE
Definition: canonicalform.h:47
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:4081
int p
Definition: cfModGcd.cc:4077
g
Definition: cfModGcd.cc:4089
CanonicalForm b
Definition: cfModGcd.cc:4102
static void sort(int **points, int sizePoints)
#define LEVELBASE
Definition: cf_defs.h:25
#define LEVELQUOT
Definition: cf_defs.h:27
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
GFGenerator ** gensg
Definition: cf_generator.h:98
CanonicalForm item() const
CFGenerator * clone() 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 CFGenerator * clone() const
Definition: factory.h:695
virtual CanonicalForm item() const
Definition: factory.h:693
virtual ~CFGenerator()
Definition: factory.h:690
virtual bool hasItems() const
Definition: factory.h:691
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
friend OSTREAM & operator<<(OSTREAM &s, const CFMap &m)
OSTREAM & operator << ( OSTREAM & s, const CFMap & m )
Definition: cf_map.cc:191
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
CFMap(const CanonicalForm &s)
Definition: factory.h:1008
static CFRandom * generate()
virtual class for random element generation
Definition: cf_random.h:21
virtual CFRandom * clone() const
Definition: factory.h:842
virtual CanonicalForm generate() const
Definition: factory.h:841
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
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 *)
InternalCF * getval() const
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
bool inCoeffDomain() const
void print(OSTREAM &) const
bool inZ() const
int level() const
CF_INLINE CanonicalForm(const int)
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
CanonicalForm sqrt() const
bool inBaseDomain() const
bool isImm() const
Definition: factory.h:260
CanonicalForm & mod(const CanonicalForm &)
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
CanonicalForm & div(const CanonicalForm &)
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
friend OSTREAM & operator<<(OSTREAM &s, const Evaluation &e)
Definition: cf_eval.cc:60
Evaluation(const Evaluation &e)
Definition: factory.h:663
Evaluation()
Definition: factory.h:661
generate all elements in F_p starting from 0
Definition: cf_generator.h:56
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
CFGenerator * clone() const
generate random elements in F_p
Definition: cf_random.h:44
CanonicalForm generate() const
CFRandom * clone() const
FFRandom()
Definition: factory.h:863
~FFRandom()
Definition: factory.h:864
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
CFRandom * clone() const
~GFRandom()
Definition: factory.h:852
CanonicalForm generate() const
GFRandom()
Definition: factory.h:851
generate integers starting from 0
Definition: cf_generator.h:37
CFGenerator * clone() const
~IntGenerator()
Definition: factory.h:707
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
friend OSTREAM & operator<<(OSTREAM &s, const MapPair &p)
OSTREAM & operator << ( OSTREAM & s, const MapPair & p )
Definition: cf_map.cc:44
MapPair(const MapPair &p)
Definition: factory.h:975
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
StoreFactors & operator=(const StoreFactors &value)
CFList FS2
candidate factors that might get removed
CFList FS1
factors that were removed
factory's class for variables
Definition: factory.h:127
Variable(char name)
Variable(const Variable &v)
Definition: factory.h:136
Variable(int l, bool flag)
Variable(int l)
friend void swap_levels()
Variable()
Definition: factory.h:132
char name() const
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
Variable(int l, char name)
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
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
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
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
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
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
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
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
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:799
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
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
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
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
CFMatrix *FACTORY_PUBLIC cf_LLL(CFMatrix &A)
performs LLL reduction.
Definition: cf_hnf.cc:66
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
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 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 )
fglmVector operator-(const fglmVector &v)
Definition: fglmvec.cc:398
#define EXTERN_VAR
Definition: globaldefs.h:6
#define FACTORY_PUBLIC
Definition: globaldefs.h:25
#define OSTREAM
Definition: factory.h:40
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define error(a)
Definition: mpr_numeric.cc:966
ostream & operator<<(ostream &s, const spectrum &spec)
Definition: semic.cc:249
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
#define Q
Definition: sirandom.c:26
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026