My Project
Data Structures | Macros | Typedefs | Functions | Variables
factory.h File Reference

‘factory.h’ is the user interface to Factory. More...

#include "factory/factoryconf.h"
#include "factory/globaldefs.h"
#include <stdint.h>
#include "factory/si_log2.h"
#include "omalloc/omalloc.h"
#include "omalloc/omallocClass.h"
#include <iostream>
#include "factory/cf_gmp.h"
#include "factory/templates/ftmpl_array.h"
#include "factory/templates/ftmpl_afactor.h"
#include "factory/templates/ftmpl_factor.h"
#include "factory/templates/ftmpl_list.h"
#include "factory/templates/ftmpl_matrix.h"

Go to the source code of this file.

Data Structures

class  Variable
 factory's class for variables More...
 
class  CanonicalForm
 factory's main class More...
 
class  Evaluation
 class to evaluate a polynomial at points More...
 
class  CFGenerator
 virtual class for generators More...
 
class  IntGenerator
 generate integers starting from 0 More...
 
class  FFGenerator
 generate all elements in F_p starting from 0 More...
 
class  GFGenerator
 generate all elements in GF starting from 0 More...
 
class  AlgExtGenerator
 generate all elements in F_p(alpha) starting from 0 More...
 
class  CFGenFactory
 
class  CFIterator
 class to iterate through CanonicalForm's More...
 
class  CFRandom
 virtual class for random element generation More...
 
class  GFRandom
 generate random elements in GF More...
 
class  FFRandom
 generate random elements in F_p More...
 
class  IntRandom
 generate random integers More...
 
class  AlgExtRandomF
 generate random elements in F_p(alpha) More...
 
class  CFRandomFactory
 
class  modpk
 class to do operations mod p^k for int's p and k More...
 
class  MapPair
 class MapPair More...
 
class  CFMap
 class CFMap More...
 
class  REvaluation
 class to generate random evaluation points More...
 
class  StoreFactors
 class to store factors that get removed during char set computation More...
 

Macros

#define OSTREAM   std::ostream
 
#define ISTREAM   std::istream
 
#define LEVELBASE   -1000000
 
#define LEVELTRANS   -500000
 
#define LEVELQUOT   1000000
 
#define LEVELEXPR   1000001
 
#define CF_INLINE
 
#define CF_NO_INLINE
 
#define CF_INLINE
 
#define CF_NO_INLINE
 

Typedefs

typedef AFactor< CanonicalFormCFAFactor
 
typedef List< CFAFactorCFAFList
 
typedef ListIterator< CFAFactorCFAFListIterator
 
typedef Factor< CanonicalFormCFFactor
 
typedef List< CFFactorCFFList
 
typedef ListIterator< CFFactorCFFListIterator
 
typedef List< CanonicalFormCFList
 
typedef ListIterator< CanonicalFormCFListIterator
 
typedef Array< CanonicalFormCFArray
 
typedef Matrix< CanonicalFormCFMatrix
 
typedef List< CFListListCFList
 
typedef ListIterator< CFListListCFListIterator
 
typedef List< int > IntList
 
typedef ListIterator< int > IntListIterator
 
typedef List< VariableVarlist
 
typedef ListIterator< VariableVarlistIterator
 
typedef Array< int > Intarray
 
typedef termtermList
 
typedef List< MapPairMPList
 
typedef ListIterator< MapPairMPListIterator
 

Functions

int FACTORY_PUBLIC cf_getPrime (int i)
 
int FACTORY_PUBLIC cf_getNumPrimes ()
 
int FACTORY_PUBLIC cf_getSmallPrime (int i)
 
int FACTORY_PUBLIC cf_getNumSmallPrimes ()
 
int FACTORY_PUBLIC cf_getBigPrime (int i)
 
int FACTORY_PUBLIC cf_getNumBigPrimes ()
 
Variable FACTORY_PUBLIC rootOf (const CanonicalForm &, char name='@')
 returns a symbolic root of polynomial with name name Use it to define algebraic variables More...
 
int level (const Variable &v)
 
char name (const Variable &v)
 
void setReduce (const Variable &alpha, bool reduce)
 
void setMipo (const Variable &alpha, const CanonicalForm &mipo)
 
CanonicalForm getMipo (const Variable &alpha, const Variable &x)
 
bool hasMipo (const Variable &alpha)
 
char getDefaultVarName ()
 
char getDefaultExtName ()
 
void FACTORY_PUBLIC prune (Variable &alpha)
 
void prune1 (const Variable &alpha)
 
int ExtensionLevel ()
 
int is_imm (const InternalCF *const ptr)
 
CF_INLINE CanonicalForm operator+ (const CanonicalForm &, const CanonicalForm &)
 CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs ) More...
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator- (const CanonicalForm &, const CanonicalForm &)
 
CF_INLINE CanonicalForm operator* (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator/ (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator% (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod (const CanonicalForm &, const CanonicalForm &)
 
CanonicalForm FACTORY_PUBLIC blcm (const CanonicalForm &f, const CanonicalForm &g)
 
CanonicalForm FACTORY_PUBLIC power (const CanonicalForm &f, int n)
 exponentiation More...
 
CanonicalForm FACTORY_PUBLIC power (const Variable &v, int n)
 exponentiation More...
 
CanonicalForm FACTORY_PUBLIC gcd (const CanonicalForm &, const CanonicalForm &)
 
CanonicalForm FACTORY_PUBLIC gcd_poly (const CanonicalForm &f, const CanonicalForm &g)
 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
CanonicalForm FACTORY_PUBLIC lcm (const CanonicalForm &, const CanonicalForm &)
 CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
CanonicalForm FACTORY_PUBLIC pp (const CanonicalForm &)
 CanonicalForm pp ( const CanonicalForm & f ) More...
 
CanonicalForm FACTORY_PUBLIC content (const CanonicalForm &)
 CanonicalForm content ( const CanonicalForm & f ) More...
 
CanonicalForm FACTORY_PUBLIC content (const CanonicalForm &, const Variable &)
 CanonicalForm content ( const CanonicalForm & f, const Variable & x ) More...
 
CanonicalForm FACTORY_PUBLIC icontent (const CanonicalForm &f)
 CanonicalForm icontent ( const CanonicalForm & f ) More...
 
CanonicalForm FACTORY_PUBLIC vcontent (const CanonicalForm &f, const Variable &x)
 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ) More...
 
CanonicalForm FACTORY_PUBLIC swapvar (const CanonicalForm &, const Variable &, const Variable &)
 swapvar() - swap variables x1 and x2 in f. More...
 
CanonicalForm FACTORY_PUBLIC replacevar (const CanonicalForm &, const Variable &, const Variable &)
 CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) More...
 
int getNumVars (const CanonicalForm &f)
 int getNumVars ( const CanonicalForm & f ) More...
 
CanonicalForm getVars (const CanonicalForm &f)
 CanonicalForm getVars ( const CanonicalForm & f ) More...
 
CanonicalForm apply (const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) More...
 
CanonicalForm mapdomain (const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) More...
 
int * degrees (const CanonicalForm &f, int *degs=0)
 int * degrees ( const CanonicalForm & f, int * degs ) More...
 
int totaldegree (const CanonicalForm &f)
 int totaldegree ( const CanonicalForm & f ) More...
 
int totaldegree (const CanonicalForm &f, const Variable &v1, const Variable &v2)
 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 ) More...
 
int size (const CanonicalForm &f, const Variable &v)
 int size ( const CanonicalForm & f, const Variable & v ) More...
 
int size (const CanonicalForm &f)
 int size ( const CanonicalForm & f ) More...
 
int size_maxexp (const CanonicalForm &f, int &maxexp)
 
CanonicalForm reduce (const CanonicalForm &f, const CanonicalForm &M)
 polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M More...
 
bool hasFirstAlgVar (const CanonicalForm &f, Variable &a)
 check if poly f contains an algebraic variable a More...
 
CanonicalForm leftShift (const CanonicalForm &F, int n)
 left shift the main variable of F by n More...
 
CanonicalForm lc (const CanonicalForm &f)
 
CanonicalForm Lc (const CanonicalForm &f)
 
CanonicalForm LC (const CanonicalForm &f)
 
CanonicalForm LC (const CanonicalForm &f, const Variable &v)
 
int degree (const CanonicalForm &f)
 
int degree (const CanonicalForm &f, const Variable &v)
 
int taildegree (const CanonicalForm &f)
 
CanonicalForm tailcoeff (const CanonicalForm &f)
 
CanonicalForm tailcoeff (const CanonicalForm &f, const Variable &v)
 
int level (const CanonicalForm &f)
 
Variable mvar (const CanonicalForm &f)
 
CanonicalForm num (const CanonicalForm &f)
 
CanonicalForm den (const CanonicalForm &f)
 
int sign (const CanonicalForm &a)
 
CanonicalForm deriv (const CanonicalForm &f, const Variable &x)
 
CanonicalForm sqrt (const CanonicalForm &a)
 
int ilog2 (const CanonicalForm &a)
 
CanonicalForm mapinto (const CanonicalForm &f)
 
CanonicalForm head (const CanonicalForm &f)
 
int headdegree (const CanonicalForm &f)
 
void FACTORY_PUBLIC setCharacteristic (int c)
 
void setCharacteristic (int c, int n)
 
void setCharacteristic (int c, int n, char name)
 
int FACTORY_PUBLIC getCharacteristic ()
 
int getGFDegree ()
 
CanonicalForm getGFGenerator ()
 
void FACTORY_PUBLIC On (int)
 switches More...
 
void FACTORY_PUBLIC Off (int)
 switches More...
 
bool FACTORY_PUBLIC isOn (int)
 switches More...
 
CanonicalForm psr (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
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, const Variable & x ) More...
 
CanonicalForm FACTORY_PUBLIC bCommonDen (const CanonicalForm &f)
 CanonicalForm bCommonDen ( const CanonicalForm & f ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g)
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &quot)
 same as fdivides if true returns quotient quot of g by f otherwise quot == 0 More...
 
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 More...
 
CanonicalForm maxNorm (const CanonicalForm &f)
 CanonicalForm maxNorm ( const CanonicalForm & f ) More...
 
CanonicalForm euclideanNorm (const CanonicalForm &f)
 CanonicalForm euclideanNorm ( const CanonicalForm & f ) More...
 
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, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void FACTORY_PUBLIC chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void FACTORY_PUBLIC chineseRemainderCached (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew, CFArray &inv)
 
void FACTORY_PUBLIC chineseRemainderCached (const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
 
CanonicalForm Farey (const CanonicalForm &f, const CanonicalForm &q)
 Farey rational reconstruction. More...
 
bool isPurePoly (const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, bool issqrfree=false)
 factorization over $ F_p $ or $ Q $ More...
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $ More...
 
CFFList FACTORY_PUBLIC sqrFree (const CanonicalForm &f, bool sort=false)
 squarefree factorization More...
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x More...
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x, const Variable &v1, const Variable &v2)
 
Variable get_max_degree_Variable (const CanonicalForm &f)
 get_max_degree_Variable returns Variable with highest degree. More...
 
CFList get_Terms (const CanonicalForm &f)
 
void getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result)
 get_Terms: Split the polynomial in the containing terms. More...
 
bool linearSystemSolve (CFMatrix &M)
 
CanonicalForm FACTORY_PUBLIC determinant (const CFMatrix &M, int n)
 
CFArray subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm FACTORY_PUBLIC resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm abs (const CanonicalForm &f)
 inline CanonicalForm abs ( const CanonicalForm & f ) More...
 
int factoryrandom (int n)
 random integers with abs less than n More...
 
void FACTORY_PUBLIC factoryseed (int s)
 random seed initializer More...
 
CanonicalForm replaceLc (const CanonicalForm &f, const CanonicalForm &c)
 
CanonicalForm compress (const CanonicalForm &f, CFMap &m)
 CanonicalForm compress ( const CanonicalForm & f, CFMap & m ) More...
 
void compress (const CFArray &a, CFMap &M, CFMap &N)
 void compress ( const CFArray & a, CFMap & M, CFMap & N ) More...
 
void compress (const CanonicalForm &f, const CanonicalForm &g, CFMap &M, CFMap &N)
 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N ) More...
 
long gf_gf2ff (long a)
 
int gf_gf2ff (int a)
 
bool gf_isff (long a)
 
bool gf_isff (int a)
 
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, the unique m x m matrix whose rows span L, such that. More...
 
CFMatrix *FACTORY_PUBLIC cf_LLL (CFMatrix &A)
 performs LLL reduction. More...
 
void FACTORY_PUBLIC gmp_numerator (const CanonicalForm &f, mpz_ptr result)
 
void FACTORY_PUBLIC gmp_denominator (const CanonicalForm &f, mpz_ptr result)
 
int gf_value (const CanonicalForm &f)
 
CanonicalForm FACTORY_PUBLIC make_cf (const mpz_ptr n)
 
CanonicalForm FACTORY_PUBLIC make_cf (const mpz_ptr n, const mpz_ptr d, bool normalize)
 
CanonicalForm make_cf_from_gf (const int z)
 
int igcd (int a, int b)
 
int FACTORY_PUBLIC ipower (int b, int n)
 int ipower ( int b, int m ) More...
 
void factoryError_intern (const char *s)
 
int FACTORY_PUBLIC probIrredTest (const CanonicalForm &F, double error)
 given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error More...
 
CFAFList FACTORY_PUBLIC absFactorize (const CanonicalForm &G)
 absolute factorization of a multivariate poly over Q More...
 
CanonicalForm resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob=true)
 modular resultant algorihtm over Z More...
 
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 irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $. More...
 
CFFList facAlgFunc (const CanonicalForm &f, const CFList &as)
 factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $. More...
 
CanonicalForm Prem (const CanonicalForm &F, const CanonicalForm &G)
 pseudo remainder of F by G with certain factors of LC (g) cancelled More...
 
CFList basicSet (const CFList &PS)
 basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister More...
 
CFList charSet (const CFList &PS)
 characteristic set More...
 
CFList modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified medial set More...
 
CFList modCharSet (const CFList &PS, bool removeContents)
 
CFList charSetViaCharSetN (const CFList &PS)
 compute a characteristic set via medial set More...
 
CFList charSetN (const CFList &PS)
 medial set More...
 
CFList charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed More...
 
CFList charSetViaModCharSet (const CFList &PS, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed More...
 
ListCFList charSeries (const CFList &L)
 characteristic series More...
 
ListCFList FACTORY_PUBLIC irrCharSeries (const CFList &PS)
 irreducible characteristic series More...
 
Varlist neworder (const CFList &PolyList)
 
CFList newordercf (const CFList &PolyList)
 
IntList FACTORY_PUBLIC neworderint (const CFList &PolyList)
 
CFList reorder (const Varlist &betterorder, const CFList &PS)
 
CFFList reorder (const Varlist &betterorder, const CFFList &PS)
 
ListCFList reorder (const Varlist &betterorder, const ListCFList &Q)
 
CanonicalForm FACTORY_PUBLIC extgcd (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
 CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) More...
 

Variables

const char factoryConfiguration []
 
static const int SW_RATIONAL = 0
 set to 1 for computations over Q More...
 
static const int SW_SYMMETRIC_FF = 1
 set to 1 for symmetric representation over F_q More...
 
static const int SW_USE_EZGCD = 2
 set to 1 to use EZGCD over Z More...
 
static const int SW_USE_EZGCD_P = 3
 set to 1 to use EZGCD over F_q More...
 
static const int SW_USE_NTL_SORT =4
 set to 1 to sort factors in a factorization More...
 
static const int SW_USE_CHINREM_GCD =5
 set to 1 to use modular gcd over Z More...
 
static const int SW_USE_QGCD =6
 set to 1 to use Encarnacion GCD over Q(a) More...
 
static const int SW_USE_FF_MOD_GCD =7
 set to 1 to use modular GCD over F_q More...
 
static const int SW_USE_FL_GCD_P =8
 set to 1 to use Flints gcd over F_p More...
 
static const int SW_USE_FL_GCD_0 =9
 set to 1 to use Flints gcd over Q/Z More...
 
static const int SW_BERLEKAMP =10
 set to 1 to use Factorys Berlekamp alg. More...
 
static const int SW_FAC_QUADRATICLIFT =11
 
static const int SW_USE_FL_FAC_P =12
 set to 1 to prefer flints multivariate factorization over Z/p More...
 
static const int SW_USE_FL_FAC_0 =13
 set to 1 to prefer flints multivariate factorization over Z/p More...
 
static const int SW_USE_FL_FAC_0A =14
 set to 1 to prefer flints multivariate factorization over Z/p(a) More...
 
EXTERN_VAR int singular_homog_flag
 
EXTERN_VAR void(* factoryError )(const char *s)
 

Detailed Description

‘factory.h’ is the user interface to Factory.

Created automatically by ‘makeheader’, it collects all important declarations from all important Factory header files into one overall header file leaving out all boring Factory internal stuff. See ‘./bin/makeheader’ for an explanation of the syntax of this file.

Note: In this file the order of "includes" matters (since this are not real includes)! In general, files at the end depend on files at the beginning.

Definition in file factory.h.

Macro Definition Documentation

◆ CF_INLINE [1/2]

#define CF_INLINE

Definition at line 793 of file factory.h.

◆ CF_INLINE [2/2]

#define CF_INLINE

Definition at line 793 of file factory.h.

◆ CF_NO_INLINE [1/2]

#define CF_NO_INLINE

Definition at line 795 of file factory.h.

◆ CF_NO_INLINE [2/2]

#define CF_NO_INLINE

Definition at line 795 of file factory.h.

◆ ISTREAM

#define ISTREAM   std::istream

Definition at line 41 of file factory.h.

◆ LEVELBASE

#define LEVELBASE   -1000000

Definition at line 82 of file factory.h.

◆ LEVELEXPR

#define LEVELEXPR   1000001

Definition at line 85 of file factory.h.

◆ LEVELQUOT

#define LEVELQUOT   1000000

Definition at line 84 of file factory.h.

◆ LEVELTRANS

#define LEVELTRANS   -500000

Definition at line 83 of file factory.h.

◆ OSTREAM

#define OSTREAM   std::ostream

Definition at line 40 of file factory.h.

Typedef Documentation

◆ CFAFactor

Definition at line 530 of file factory.h.

◆ CFAFList

Definition at line 531 of file factory.h.

◆ CFAFListIterator

Definition at line 532 of file factory.h.

◆ CFArray

Definition at line 538 of file factory.h.

◆ CFFactor

Definition at line 533 of file factory.h.

◆ CFFList

typedef List<CFFactor> CFFList

Definition at line 534 of file factory.h.

◆ CFFListIterator

Definition at line 535 of file factory.h.

◆ CFList

Definition at line 536 of file factory.h.

◆ CFListIterator

Definition at line 537 of file factory.h.

◆ CFMatrix

Definition at line 539 of file factory.h.

◆ Intarray

typedef Array<int> Intarray

Definition at line 546 of file factory.h.

◆ IntList

typedef List<int> IntList

Definition at line 542 of file factory.h.

◆ IntListIterator

Definition at line 543 of file factory.h.

◆ ListCFList

Definition at line 540 of file factory.h.

◆ ListCFListIterator

Definition at line 541 of file factory.h.

◆ MPList

typedef List<MapPair> MPList

Definition at line 986 of file factory.h.

◆ MPListIterator

Definition at line 987 of file factory.h.

◆ termList

typedef term* termList

Definition at line 799 of file factory.h.

◆ Varlist

typedef List<Variable> Varlist

Definition at line 544 of file factory.h.

◆ VarlistIterator

Definition at line 545 of file factory.h.

Function Documentation

◆ abs()

CanonicalForm abs ( const CanonicalForm f)
inline

inline CanonicalForm abs ( const CanonicalForm & f )

abs() - return absolute value of ‘f’.

The absolute value is defined in terms of the function ‘sign()’. If it reports negative sign for ‘f’ than -‘f’ is returned, otherwise ‘f’.

This behaviour is most useful for integers and rationals. But it may be used to sign-normalize the leading coefficient of arbitrary polynomials, too.

Type info:

f: CurrentPP

Definition at line 638 of file factory.h.

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 }
FILE * f
Definition: checklibs.c:9
int sign(const CanonicalForm &a)
Definition: factory.h:484

◆ absFactorize()

CFAFList FACTORY_PUBLIC absFactorize ( const CanonicalForm G)

absolute factorization of a multivariate poly over Q

Returns
absFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned), and the multiplicity of the absolute irreducible factor
Parameters
[in]Gpoly over Q

Definition at line 262 of file facAbsFact.cc.

264 {
265  //TODO handle homogeneous input, is already done in LIB interface but still...
266  ASSERT (getCharacteristic() == 0, "expected poly over Q");
267 
268  CanonicalForm F= G;
269 
270  CanonicalForm LcF= Lc (F);
271  bool isRat= isOn (SW_RATIONAL);
272  if (isRat)
273  F *= bCommonDen (F);
274 
275  Off (SW_RATIONAL);
276  F /= icontent (F);
277  if (isRat)
278  On (SW_RATIONAL);
279 
280  CFFList rationalFactors= factorize (F);
281 
282  CFAFList result, resultBuf;
283 
285  CFFListIterator i= rationalFactors;
286  i++;
287  for (; i.hasItem(); i++)
288  {
289  resultBuf= absFactorizeMain (i.getItem().factor());
290  for (iter= resultBuf; iter.hasItem(); iter++)
291  iter.getItem()= CFAFactor (iter.getItem().factor(),
292  iter.getItem().minpoly(), i.getItem().exp());
293  result= Union (result, resultBuf);
294  }
295 
296  if (isRat)
297  normalize (result);
298  result.insert (CFAFactor (LcF, 1, 1));
299 
300  return result;
301 }
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
AFactor< CanonicalForm > CFAFactor
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm Lc(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
factory's main class
Definition: canonicalform.h:86
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
CFListIterator iter
Definition: facAbsFact.cc:61
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:303
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition: janet.cc:31
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026

◆ apply()

CanonicalForm apply ( const CanonicalForm f,
void(*)(CanonicalForm &, int &)  mf 
)

CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) )

apply() - apply mf to terms of f.

Calls mf( f[i], i ) for each term f[i]*x^i of f and builds a new term from the result. If f is in a coefficient domain, mf( f, i ) should result in an i == 0, since otherwise it is not clear which variable to use for the resulting term.

An example:

void
diff( CanonicalForm & f, int & i )
{
f = f * i;
if ( i > 0 ) i--;
}
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45

Then apply( f, diff ) is differentation of f with respect to the main variable of f.

Definition at line 402 of file cf_ops.cc.

403 {
404  if ( f.inCoeffDomain() )
405  {
406  int exp = 0;
408  mf( result, exp );
409  ASSERT( exp == 0, "illegal result, do not know what variable to use" );
410  return result;
411  }
412  else
413  {
414  CanonicalForm result, coeff;
415  CFIterator i;
416  int exp;
417  Variable x = f.mvar();
418  for ( i = f; i.hasTerms(); i++ )
419  {
420  coeff = i.coeff();
421  exp = i.exp();
422  mf( coeff, exp );
423  if ( ! coeff.isZero() )
424  result += power( x, exp ) * coeff;
425  }
426  return result;
427  }
428 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable x
Definition: cfModGcd.cc:4082
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE bool isZero() const
factory's class for variables
Definition: factory.h:127
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357

◆ basicSet()

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 at line 150 of file cfCharSets.cc.

151 {
152  CFList QS= PS, BS, RS;
154  int cb, degb;
155 
156  if (PS.length() < 2)
157  return PS;
158 
160 
161  while (!QS.isEmpty())
162  {
163  b= lowestRank (QS);
164  cb= b.level();
165 
166  BS= Union(CFList (b), BS);
167 
168  if (cb <= 0)
169  return CFList();
170  else
171  {
172  degb= degree (b);
173  RS= CFList();
174  for (i= QS; i.hasItem(); i++)
175  {
176  if (degree (i.getItem(), cb) < degb)
177  RS= Union (CFList (i.getItem()), RS);
178  }
179  QS= RS;
180  }
181  }
182 
183  return BS;
184 }
int degree(const CanonicalForm &f)
List< CanonicalForm > CFList
CanonicalForm lowestRank(const CFList &L)
CanonicalForm b
Definition: cfModGcd.cc:4103
int level() const
level() returns the level of CO.
int length() const
Definition: ftmpl_list.cc:273
int isEmpty() const
Definition: ftmpl_list.cc:267

◆ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm & f )

bCommonDen() - calculate multivariate common denominator of coefficients of ‘f’.

The common denominator is calculated with respect to all coefficients of ‘f’ which are in a base domain. In other words, common_den( ‘f’ ) * ‘f’ is guaranteed to have integer coefficients only. The common denominator of zero is one.

Returns something non-trivial iff the current domain is Q.

Type info:

f: CurrentPP

Definition at line 293 of file cf_algorithm.cc.

294 {
295  if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) )
296  {
297  // otherwise `bgcd()' returns one
298  Off( SW_RATIONAL );
300  On( SW_RATIONAL );
301  return result;
302  }
303  else
304  return CanonicalForm( 1 );
305 }
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )

◆ blcm()

Definition at line 1816 of file canonicalform.cc.

1817 {
1818  if ( f.isZero() || g.isZero() )
1819  return CanonicalForm( 0L );
1820 /*
1821  else if (f.isOne())
1822  return g;
1823  else if (g.isOne())
1824  return f;
1825 */
1826  else
1827  return (f / bgcd( f, g )) * g;
1828 }
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
g
Definition: cfModGcd.cc:4090

◆ cf_getBigPrime()

int FACTORY_PUBLIC cf_getBigPrime ( int  i)

Definition at line 39 of file cf_primes.cc.

40 {
41  ASSERT( i >= 0 && i < NUMBIGPRIMES, "index to primes too high" );
42  return bigprimes[i];
43 }
static const int bigprimes[]
Definition: cf_primetab.h:601
#define NUMBIGPRIMES
Definition: cf_primetab.h:9

◆ cf_getNumBigPrimes()

int FACTORY_PUBLIC cf_getNumBigPrimes ( )

Definition at line 45 of file cf_primes.cc.

46 {
47  return NUMBIGPRIMES;
48 }

◆ cf_getNumPrimes()

int FACTORY_PUBLIC cf_getNumPrimes ( )

Definition at line 23 of file cf_primes.cc.

24 {
25  return NUMPRIMES;
26 }
#define NUMPRIMES
Definition: cf_primetab.h:10

◆ cf_getNumSmallPrimes()

int FACTORY_PUBLIC cf_getNumSmallPrimes ( )

Definition at line 34 of file cf_primes.cc.

35 {
36  return NUMSMALLPRIMES;
37 }
#define NUMSMALLPRIMES
Definition: cf_primetab.h:8

◆ cf_getPrime()

int FACTORY_PUBLIC cf_getPrime ( int  i)

Definition at line 14 of file cf_primes.cc.

15 {
16  ASSERT( i >= 0 && i < NUMPRIMES, "index to primes too high" );
17  if ( i >= NUMSMALLPRIMES )
18  return bigprimes[i-NUMSMALLPRIMES];
19  else
20  return smallprimes[i];
21 }
static const int smallprimes[]
Definition: cf_primetab.h:12

◆ cf_getSmallPrime()

int FACTORY_PUBLIC cf_getSmallPrime ( int  i)

Definition at line 28 of file cf_primes.cc.

29 {
30  ASSERT( i >= 0 && i < NUMSMALLPRIMES, "index to primes too high" );
31  return smallprimes[i];
32 }

◆ cf_HNF()

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, the unique m x m matrix whose rows span L, such that.

  • lower triangular,
  • the diagonal entries are positive,
  • any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.
Note
: uses NTL

The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is, the unique m x m matrix whose rows span L, such that.

W is computed as the Hermite Normal Form of A; that is, W is the unique m x m matrix whose rows span L, such that

  • W is lower triangular,
  • the diagonal entries are positive,
  • any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.

Definition at line 44 of file cf_hnf.cc.

45 {
46 #ifdef HAVE_FLINT
47  fmpz_mat_t FLINTM;
49  fmpz_mat_hnf(FLINTM,FLINTM);
51  fmpz_mat_clear(FLINTM);
52  return r;
53 #elif defined(HAVE_NTL)
54  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
55  ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
56  mat_ZZ WW;
57  HNF(WW,*AA,DD);
58  delete AA;
60 #else
61  factoryError("NTL/FLINT missing: cf_HNF");
62  return NULL; // avoid warning
63 #endif
64 }
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1153
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1138
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:670
CanonicalForm FACTORY_PUBLIC determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
#define NULL
Definition: omList.c:12
#define A
Definition: sirandom.c:24

◆ cf_LLL()

CFMatrix* FACTORY_PUBLIC cf_LLL ( CFMatrix A)

performs LLL reduction.

B is an m x n matrix, viewed as m rows of n-vectors. m may be less than, equal to, or greater than n, and the rows need not be linearly independent. B is transformed into an LLL-reduced basis, and the return value is the rank r of B. The first m-r rows of B are zero.

More specifically, elementary row transformations are performed on B so that the non-zero rows of new-B form an LLL-reduced basis for the lattice spanned by the rows of old-B. The default reduction parameter is delta=3/4, which means that the squared length of the first non-zero basis vector is no more than 2^{r-1} times that of the shortest vector in the lattice.

Note
: uses NTL or FLINT

Definition at line 66 of file cf_hnf.cc.

67 {
68 #ifdef HAVE_FLINT
69  fmpz_mat_t FLINTM;
71  fmpq_t delta,eta;
72  fmpq_init(delta); fmpq_set_si(delta,1,1);
73  fmpq_init(eta); fmpq_set_si(eta,3,4);
74  fmpz_mat_lll_storjohann(FLINTM,delta,eta);
76  fmpz_mat_clear(FLINTM);
77  return r;
78 #elif defined(HAVE_NTL)
79  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
80  ZZ det2;
81  LLL(det2,*AA,0L);
83  delete AA;
84  return r;
85 #else
86  factoryError("NTL/FLINT missing: cf_LLL");
87  return NULL; // avoid warning
88 #endif
89 }
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160

◆ charSeries()

ListCFList charSeries ( const CFList L)

characteristic series

Definition at line 411 of file cfCharSets.cc.

412 {
413  ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
414  CFList l, charset, ini;
415 
416  int count= 0;
417  int highestLevel= 1;
419 
420  StoreFactors StoredFactors;
421 
422  l= L;
423 
424  for (iter= l; iter.hasItem(); iter++)
425  {
427  if (highestLevel < iter.getItem().level())
428  highestLevel= iter.getItem().level();
429  }
430 
431  tmp= ListCFList (l);
432 
433  while (!tmp.isEmpty())
434  {
435  sortListCFList (tmp);
436 
437  l= tmp.getFirst();
438 
439  tmp= Difference (tmp, l);
440 
441  select (ppi, l.length(), ppi1, ppi2);
442 
443  inplaceUnion (ppi2, qqi);
444 
445  if (count > 0)
446  ppi= Union (ppi1, ListCFList (l));
447  else
448  ppi= ListCFList();
449 
450  if (l.length() - 3 < highestLevel)
451  charset= charSetViaModCharSet (l, StoredFactors);
452  else
453  charset= charSetViaCharSetN (l);
454 
455  if (charset.length() > 0 && charset.getFirst().level() > 0)
456  {
457  result= Union (ListCFList (charset), result);
458  ini= factorsOfInitials (charset);
459 
460  ini= Union (ini, factorPSet (StoredFactors.FS1));
461  sortCFListByLevel (ini);
462  }
463  else
464  {
465  ini= factorPSet (StoredFactors.FS1);
466  sortCFListByLevel (ini);
467  }
468 
469  tmp2= adjoin (ini, l, qqi);
470  tmp= Union (tmp2, tmp);
471 
472  StoredFactors.FS1= CFList();
473  StoredFactors.FS2= CFList();
474 
475  ppi1= ListCFList();
476  ppi2= ListCFList();
477 
478  count++;
479  }
480 
481  //TODO need to remove superflous components
482 
483  return result;
484 }
List< CFList > ListCFList
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
CFList factorsOfInitials(const CFList &L)
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
CFList factorPSet(const CFList &PS)
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
int l
Definition: cfEzgcd.cc:100
T getFirst() const
Definition: ftmpl_list.cc:279
class to store factors that get removed during char set computation
CFList FS2
candidate factors that might get removed
CFList FS1
factors that were removed
CFFListIterator iter
Definition: facAbsBiFact.cc:53
CFList tmp2
Definition: facFqBivar.cc:72
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int status int void size_t count
Definition: si_signals.h:59

◆ charSet()

CFList charSet ( const CFList PS)

characteristic set

Definition at line 187 of file cfCharSets.cc.

188 {
189  CFList QS= PS, RS= PS, CSet, tmp;
191  CanonicalForm r;
192 
193  while (!RS.isEmpty())
194  {
195  CSet= basicSet (QS);
196 
197  RS= CFList();
198  if (CSet.length() > 0 && CSet.getFirst().level() > 0)
199  {
200  tmp= Difference (QS, CSet);
201  for (i= tmp; i.hasItem(); i++)
202  {
203  r= Prem (i.getItem(), CSet);
204  if (r != 0)
205  RS= Union (RS, CFList (r));
206  }
207  QS= Union (QS, RS);
208  }
209  }
210 
211  return CSet;
212 }
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
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

◆ charSetN()

CFList charSetN ( const CFList PS)

medial set

Definition at line 216 of file cfCharSets.cc.

217 {
218  CFList QS= PS, RS= PS, CSet, tmp;
220  CanonicalForm r;
221 
222  while (!RS.isEmpty())
223  {
224  QS= uniGcd (QS);
225  CSet= basicSet (QS);
226 
227  RS= CFList();
228  if (CSet.length() > 0 && CSet.getFirst().level() > 0)
229  {
230  tmp= Difference (QS, CSet);
231  for (i= tmp; i.hasItem(); i++)
232  {
233  r= Prem (i.getItem(), CSet);
234  if (!r.isZero())
235  RS= Union (RS, CFList (r));
236  }
237  QS= Union (CSet, RS);
238  }
239  }
240 
241  return CSet;
242 }
CFList uniGcd(const CFList &L)

◆ charSetViaCharSetN()

CFList charSetViaCharSetN ( const CFList PS)

compute a characteristic set via medial set

Definition at line 246 of file cfCharSets.cc.

247 {
248  CFList L;
249  CFFList sqrfFactors;
250  CanonicalForm sqrf;
251  CFFListIterator iter2;
252  for (CFListIterator iter= PS; iter.hasItem(); iter++)
253  {
254  sqrf= 1;
255  sqrfFactors= sqrFree (iter.getItem());
256  for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
257  sqrf *= iter2.getItem().factor();
258  L= Union (L, CFList (normalize (sqrf)));
259  }
260 
261  CFList result= charSetN (L);
262 
263  if (result.isEmpty() || result.getFirst().inCoeffDomain())
264  return CFList(1);
265 
266  CanonicalForm r;
267  CFList RS;
268  CFList tmp= Difference (L, result);
269 
270  for (CFListIterator i= tmp; i.hasItem(); i++)
271  {
272  r= Premb (i.getItem(), result);
273  if (!r.isZero())
274  RS= Union (RS, CFList (r));
275  }
276  if (RS.isEmpty())
277  return result;
278 
279  return charSetViaCharSetN (Union (L, Union (RS, result)));
280 }
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
CFList charSetN(const CFList &PS)
medial set
Definition: cfCharSets.cc:216
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957

◆ charSetViaModCharSet() [1/2]

CFList charSetViaModCharSet ( const CFList PS,
bool  removeContents = true 
)

modified characteristic set, i.e. a characteristic set with certain factors removed

Definition at line 397 of file cfCharSets.cc.

398 {
399  StoreFactors tmp;
400  return charSetViaModCharSet (PS, tmp, removeContents);
401 }

◆ charSetViaModCharSet() [2/2]

CFList charSetViaModCharSet ( const CFList PS,
StoreFactors StoredFactors,
bool  removeContents 
)

modified characteristic set, i.e. a characteristic set with certain factors removed

modified characteristic set, i.e. a characteristic set with certain factors removed

Definition at line 356 of file cfCharSets.cc.

358 {
359  CFList L;
360  CFFList sqrfFactors;
361  CanonicalForm sqrf;
362  CFFListIterator iter2;
363  for (CFListIterator iter= PS; iter.hasItem(); iter++)
364  {
365  sqrf= 1;
366  sqrfFactors= sqrFree (iter.getItem());
367  for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
368  sqrf *= iter2.getItem().factor();
369  L= Union (L, CFList (normalize (sqrf)));
370  }
371 
372  L= uniGcd (L);
373 
374  CFList result= modCharSet (L, StoredFactors, removeContents);
375 
376  if (result.isEmpty() || result.getFirst().inCoeffDomain())
377  return CFList(1);
378 
379  CanonicalForm r;
380  CFList RS;
381  CFList tmp= Difference (L, result);
382 
383  for (CFListIterator i= tmp; i.hasItem(); i++)
384  {
385  r= Premb (i.getItem(), result);
386  if (!r.isZero())
387  RS= Union (RS, CFList (r));
388  }
389  if (RS.isEmpty())
390  return result;
391 
392  return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors,
393  removeContents);
394 }
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284

◆ chineseRemainder() [1/2]

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, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )

chineseRemainder - integer chinese remaindering.

Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2) and qnew = q1*q2. q1 and q2 should be positive integers, pairwise prime, x1 and x2 should be polynomials with integer coefficients. If x1 and x2 are polynomials with positive coefficients, the result is guaranteed to have positive coefficients, too.

Note: This algorithm is optimized for the case q1>>q2.

This is a standard algorithm. See, for example, Geddes/Czapor/Labahn - 'Algorithms for Computer Algebra', par. 5.6 and 5.8, or the article of M. Lauer - 'Computing by Homomorphic Images' in B. Buchberger - 'Computer Algebra - Symbolic and Algebraic Computation'.

Note: Be sure you are calculating in Z, and not in Q!

Definition at line 57 of file cf_chinese.cc.

58 {
59  DEBINCLEVEL( cerr, "chineseRemainder" );
60 
61  DEBOUTLN( cerr, "log(q1) = " << q1.ilog2() );
62  DEBOUTLN( cerr, "log(q2) = " << q2.ilog2() );
63 
64  // We calculate xnew as follows:
65  // xnew = v1 + v2 * q1
66  // where
67  // v1 = x1 (mod q1)
68  // v2 = (x2-v1)/q1 (mod q2) (*)
69  //
70  // We do one extra test to check whether x2-v1 vanishes (mod
71  // q2) in (*) since it is not costly and may save us
72  // from calculating the inverse of q1 (mod q2).
73  //
74  // u: v1 (mod q2)
75  // d: x2-v1 (mod q2)
76  // s: 1/q1 (mod q2)
77  //
78  CanonicalForm v2, v1;
79  CanonicalForm u, d, s, dummy;
80 
81  v1 = mod( x1, q1 );
82  u = mod( v1, q2 );
83  d = mod( x2-u, q2 );
84  if ( d.isZero() )
85  {
86  xnew = v1;
87  qnew = q1 * q2;
88  DEBDECLEVEL( cerr, "chineseRemainder" );
89  return;
90  }
91  (void)bextgcd( q1, q2, s, dummy );
92  v2 = mod( d*s, q2 );
93  xnew = v1 + v2*q1;
94 
95  // After all, calculate new modulus. It is important that
96  // this is done at the very end of the algorithm, since q1
97  // and qnew may refer to the same object (same is true for x1
98  // and xnew).
99  qnew = q1 * q2;
100 
101  DEBDECLEVEL( cerr, "chineseRemainder" );
102 }
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int ilog2() const
int CanonicalForm::ilog2 () const
#define DEBINCLEVEL(stream, msg)
Definition: debug.h:44
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
#define DEBDECLEVEL(stream, msg)
Definition: debug.h:45
const CanonicalForm int s
Definition: facAbsFact.cc:51

◆ chineseRemainder() [2/2]

void FACTORY_PUBLIC chineseRemainder ( const CFArray x,
const CFArray q,
CanonicalForm xnew,
CanonicalForm qnew 
)

void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )

chineseRemainder - integer chinese remaindering.

Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the product of all q[i]. q[i] should be positive integers, pairwise prime. x[i] should be polynomials with integer coefficients. If all coefficients of all x[i] are positive integers, the result is guaranteed to have positive coefficients, too.

This is a standard algorithm, too, except for the fact that we use a divide-and-conquer method instead of a linear approach to calculate the remainder.

Note: Be sure you are calculating in Z, and not in Q!

Definition at line 124 of file cf_chinese.cc.

125 {
126  DEBINCLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
127 
128  ASSERT( x.min() == q.min() && x.size() == q.size(), "incompatible arrays" );
129  CFArray X(x), Q(q);
130  int i, j, n = x.size(), start = x.min();
131 
132  DEBOUTLN( cerr, "array size = " << n );
133 
134  while ( n != 1 )
135  {
136  i = j = start;
137  while ( i < start + n - 1 )
138  {
139  // This is a little bit dangerous: X[i] and X[j] (and
140  // Q[i] and Q[j]) may refer to the same object. But
141  // xnew and qnew in the above function are modified
142  // at the very end of the function, so we do not
143  // modify x1 and q1, resp., by accident.
144  chineseRemainder( X[i], Q[i], X[i+1], Q[i+1], X[j], Q[j] );
145  i += 2;
146  j++;
147  }
148 
149  if ( n & 1 )
150  {
151  X[j] = X[i];
152  Q[j] = Q[i];
153  }
154  // Maybe we would get some memory back at this point if
155  // we would set X[j+1, ..., n] and Q[j+1, ..., n] to zero
156  // at this point?
157 
158  n = ( n + 1) / 2;
159  }
160  xnew = X[start];
161  qnew = Q[q.min()];
162 
163  DEBDECLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
164 }
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition: cf_chinese.cc:57
int size() const
Definition: ftmpl_array.cc:92
int min() const
Definition: ftmpl_array.cc:98
int j
Definition: facHensel.cc:110
STATIC_VAR jList * Q
Definition: janet.cc:30

◆ chineseRemainderCached() [1/2]

void FACTORY_PUBLIC chineseRemainderCached ( const CanonicalForm x1,
const CanonicalForm q1,
const CanonicalForm x2,
const CanonicalForm q2,
CanonicalForm xnew,
CanonicalForm qnew,
CFArray inv 
)

Definition at line 308 of file cf_chinese.cc.

309 {
310  CFArray A(2); A[0]=a; A[1]=b;
311  CFArray Q(2); Q[0]=q1; Q[1]=q2;
312  chineseRemainderCached(A,Q,xnew,qnew,inv);
313 }
void chineseRemainderCached(const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
Definition: cf_chinese.cc:290

◆ chineseRemainderCached() [2/2]

void FACTORY_PUBLIC chineseRemainderCached ( const CFArray a,
const CFArray n,
CanonicalForm xnew,
CanonicalForm prod,
CFArray inv 
)

Definition at line 290 of file cf_chinese.cc.

291 {
292  CanonicalForm p, sum=0L; prod=1L;
293  int i;
294  int len=n.size();
295 
296  for (i = 0; i < len; i++) prod *= n[i];
297 
298  for (i = 0; i < len; i++)
299  {
300  p = prod / n[i];
301  sum += a[i] * chin_mul_inv(p, n[i], i, inv) * p;
302  }
303 
304  xnew = mod(sum , prod);
305 }
int p
Definition: cfModGcd.cc:4078
static CanonicalForm chin_mul_inv(const CanonicalForm a, const CanonicalForm b, int ind, CFArray &inv)
Definition: cf_chinese.cc:276
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ compress() [1/3]

CanonicalForm compress ( const CanonicalForm f,
CFMap m 
)

CanonicalForm compress ( const CanonicalForm & f, CFMap & m )

compress() - compress the canonical form f.

Compress the polynomial f such that the levels of its polynomial variables are ordered without any gaps starting from level 1. Return the compressed polynomial and a map m to undo the compression. That is, if f' = compress(f, m), than f = m(f').

Definition at line 210 of file cf_map.cc.

211 {
213  int i, n;
214  int * degs = degrees( f );
215 
216  m = CFMap();
217  n = i = 1;
218  while ( i <= level( f ) ) {
219  while( degs[i] == 0 ) i++;
220  if ( i != n ) {
221  // swap variables and remember the swap in the map
222  m.newpair( Variable( n ), Variable( i ) );
223  result = swapvar( result, Variable( i ), Variable( n ) );
224  }
225  n++; i++;
226  }
227  DELETE_ARRAY(degs);
228  return result;
229 }
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
int level(const CanonicalForm &f)
int m
Definition: cfEzgcd.cc:128
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
class CFMap
Definition: cf_map.h:85

◆ compress() [2/3]

void compress ( const CanonicalForm f,
const CanonicalForm g,
CFMap M,
CFMap N 
)

void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )

compress() - compress the variables occurring in f and g with respect to optimal variables

Compress the polynomial variables occurring in f and g so that the levels of variables common to f and g are ordered without any gaps starting from level 1, whereas the variables occuring in only one of f or g are moved to levels higher than the levels of the common variables. Return the CFMap M to realize the compression and its inverse, the CFMap N. N needs only variables common to f and g.

Definition at line 349 of file cf_map.cc.

350 {
351  int n = tmax( f.level(), g.level() );
352  int i, k, p1, pe;
353  int * degsf = NEW_ARRAY(int,n+1);
354  int * degsg = NEW_ARRAY(int,n+1);
355 
356  for ( i = 0; i <= n; i++ )
357  {
358  degsf[i] = degsg[i] = 0;
359  }
360 
361  degsf = degrees( f, degsf );
362  degsg = degrees( g, degsg );
363  optvalues( degsf, degsg, n, p1, pe );
364 
365  i = 1; k = 1;
366  if ( pe > 1 )
367  {
368  M.newpair( Variable(pe), Variable(k) );
369  N.newpair( Variable(k), Variable(pe) );
370  k++;
371  }
372  while ( i <= n )
373  {
374  if ( degsf[i] > 0 && degsg[i] > 0 )
375  {
376  if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
377  {
378  M.newpair( Variable(i), Variable(k) );
379  N.newpair( Variable(k), Variable(i) );
380  }
381  k++;
382  }
383  i++;
384  }
385  if ( p1 != pe )
386  {
387  M.newpair( Variable(p1), Variable(k) );
388  N.newpair( Variable(k), Variable(p1) );
389  k++;
390  }
391  i = 1;
392  while ( i <= n )
393  {
394  if ( degsf[i] > 0 && degsg[i] == 0 ) {
395  if ( i != k )
396  {
397  M.newpair( Variable(i), Variable(k) );
398  k++;
399  }
400  }
401  else if ( degsf[i] == 0 && degsg[i] > 0 )
402  {
403  if ( i != k )
404  {
405  M.newpair( Variable(i), Variable(k) );
406  k++;
407  }
408  }
409  i++;
410  }
411 
414 }
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int * degsf
Definition: cfEzgcd.cc:59
int k
Definition: cfEzgcd.cc:99
int * degsg
Definition: cfEzgcd.cc:60
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition: cf_map.cc:296
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define M
Definition: sirandom.c:25

◆ compress() [3/3]

void compress ( const CFArray a,
CFMap M,
CFMap N 
)

void compress ( const CFArray & a, CFMap & M, CFMap & N )

compress() - compress the variables occuring in an a.

Compress the polynomial variables occuring in a so that their levels are ordered without any gaps starting from level 1. Return the CFMap M to realize the compression and its inverse, the CFMap N. Note that if you compress a member of a using M the result of the compression is not necessarily compressed, since the map is constructed using all variables occuring in a.

Definition at line 245 of file cf_map.cc.

246 {
247  M = N = CFMap();
248  if ( a.size() == 0 )
249  return;
250  int maxlevel = level( a[a.min()] );
251  int i, j;
252 
253  // get the maximum of levels in a
254  for ( i = a.min() + 1; i <= a.max(); i++ )
255  if ( level( a[i] ) > maxlevel )
256  maxlevel = level( a[i] );
257  if ( maxlevel <= 0 )
258  return;
259 
260  int * degs = NEW_ARRAY(int,maxlevel+1);
261  int * tmp = NEW_ARRAY(int,maxlevel+1);
262  for ( i = maxlevel; i >= 1; i-- )
263  degs[i] = 0;
264 
265  // calculate the union of all levels occuring in a
266  for ( i = a.min(); i <= a.max(); i++ )
267  {
268  tmp = degrees( a[i], tmp );
269  for ( j = 1; j <= level( a[i] ); j++ )
270  if ( tmp[j] != 0 )
271  degs[j] = 1;
272  }
273 
274  // create the maps
275  i = 1; j = 1;
276  while ( i <= maxlevel )
277  {
278  if ( degs[i] != 0 )
279  {
280  M.newpair( Variable(i), Variable(j) );
281  N.newpair( Variable(j), Variable(i) );
282  j++;
283  }
284  i++;
285  }
286  DELETE_ARRAY(degs);
287  DELETE_ARRAY(tmp);
288 }
int max() const
Definition: ftmpl_array.cc:104

◆ content() [1/2]

CanonicalForm content ( const CanonicalForm & f )

content() - return content(f) with respect to main variable.

Normalizes result.

Definition at line 603 of file cf_gcd.cc.

604 {
605  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
606  {
607  CFIterator i = f;
608  CanonicalForm result = abs( i.coeff() );
609  i++;
610  while ( i.hasTerms() && ! result.isOne() )
611  {
612  result = gcd( i.coeff(), result );
613  i++;
614  }
615  return result;
616  }
617  else
618  return abs( f );
619 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:685
bool getReduce(const Variable &alpha)
Definition: variable.cc:232

◆ content() [2/2]

CanonicalForm content ( const CanonicalForm & f, const Variable & x )

content() - return content(f) with respect to x.

x should be a polynomial variable.

Definition at line 629 of file cf_gcd.cc.

630 {
631  if (f.inBaseDomain()) return f;
632  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
633  Variable y = f.mvar();
634 
635  if ( y == x )
636  return cf_content( f, 0 );
637  else if ( y < x )
638  return f;
639  else
640  return swapvar( content( swapvar( f, y, x ), y ), y, x );
641 }
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:578
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int level() const
Definition: factory.h:143
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ degree() [1/2]

int degree ( const CanonicalForm f)
inline

Definition at line 457 of file factory.h.

457 { return f.degree(); }

◆ degree() [2/2]

int degree ( const CanonicalForm f,
const Variable v 
)
inline

Definition at line 460 of file factory.h.

460 { return f.degree( v ); }
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39

◆ degrees()

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

int * degrees ( const CanonicalForm & f, int * degs )

degress() - return the degrees of all polynomial variables in f.

Returns 0 if f is in a coefficient domain, the degrees of f in all its polynomial variables in an array of int otherwise:

degrees( f, 0 )[i] = degree( f, Variable(i) )

If degs is not the zero pointer the degrees are stored in this array. In this case degs should be larger than the level of f. If degs is the zero pointer, an array of sufficient size is allocated automatically.

Definition at line 493 of file cf_ops.cc.

494 {
495  if ( f.inCoeffDomain() )
496  {
497  if (degs != 0)
498  return degs;
499  else
500  return 0;
501  }
502  else
503  {
504  int level = f.level();
505  if ( degs == NULL )
506  degs = NEW_ARRAY(int,level+1);
507  for ( int i = level; i >= 0; i-- )
508  degs[i] = 0;
509  degreesRec( f, degs );
510  return degs;
511  }
512 }
static void degreesRec(const CanonicalForm &f, int *degs)
static void degreesRec ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:463

◆ den()

CanonicalForm den ( const CanonicalForm f)
inline

Definition at line 481 of file factory.h.

481 { return f.den(); }

◆ deriv()

CanonicalForm deriv ( const CanonicalForm f,
const Variable x 
)
inline

Definition at line 487 of file factory.h.

487 { return f.deriv( x ); }

◆ determinant()

CanonicalForm FACTORY_PUBLIC determinant ( const CFMatrix M,
int  n 
)

Definition at line 222 of file cf_linsys.cc.

223 {
224  typedef int* int_ptr;
225 
226  ASSERT( rows <= M.rows() && rows <= M.columns() && rows > 0, "undefined determinant" );
227  if ( rows == 1 )
228  return M(1,1);
229  else if ( rows == 2 )
230  return M(1,1)*M(2,2)-M(2,1)*M(1,2);
231  else if ( matrix_in_Z( M, rows ) )
232  {
233  int ** mm = new int_ptr[rows];
234  CanonicalForm x, q, Qhalf, B;
235  int n, i, intdet, p, pno;
236  for ( i = 0; i < rows; i++ )
237  {
238  mm[i] = new int[rows];
239  }
240  pno = 0; n = 0;
241  TIMING_START(det_bound);
242  B = detbound( M, rows );
243  TIMING_END(det_bound);
244  q = 1;
245  TIMING_START(det_numprimes);
246  while ( B > q && n < cf_getNumBigPrimes() )
247  {
248  q *= cf_getBigPrime( n );
249  n++;
250  }
251  TIMING_END(det_numprimes);
252 
253  CFArray X(1,n), Q(1,n);
254 
255  while ( pno < n )
256  {
257  p = cf_getBigPrime( pno );
258  setCharacteristic( p );
259  // map matrix into char p
260  TIMING_START(det_mapping);
261  fill_int_mat( M, mm, rows );
262  TIMING_END(det_mapping);
263  pno++;
264  DEBOUT( cerr, "." );
265  TIMING_START(det_determinant);
266  intdet = determinant( mm, rows );
267  TIMING_END(det_determinant);
268  setCharacteristic( 0 );
269  X[pno] = intdet;
270  Q[pno] = p;
271  }
272  TIMING_START(det_chinese);
273  chineseRemainder( X, Q, x, q );
274  TIMING_END(det_chinese);
275  Qhalf = q / 2;
276  if ( x > Qhalf )
277  x = x - q;
278  for ( i = 0; i < rows; i++ )
279  delete [] mm[i];
280  delete [] mm;
281  return x;
282  }
283  else
284  {
285  CFMatrix m( M );
286  CanonicalForm divisor = 1, pivot, mji;
287  int i, j, k, sign = 1;
288  for ( i = 1; i <= rows; i++ ) {
289  pivot = m(i,i); k = i;
290  for ( j = i+1; j <= rows; j++ ) {
291  if ( betterpivot( pivot, m(j,i) ) ) {
292  pivot = m(j,i);
293  k = j;
294  }
295  }
296  if ( pivot.isZero() )
297  return 0;
298  if ( i != k )
299  {
300  m.swapRow( i, k );
301  sign = -sign;
302  }
303  for ( j = i+1; j <= rows; j++ )
304  {
305  if ( ! m(j,i).isZero() )
306  {
307  divisor *= pivot;
308  mji = m(j,i);
309  m(j,i) = 0;
310  for ( k = i+1; k <= rows; k++ )
311  m(j,k) = m(j,k) * pivot - m(i,k)*mji;
312  }
313  }
314  }
315  pivot = sign;
316  for ( i = 1; i <= rows; i++ )
317  pivot *= m(i,i);
318  return pivot / divisor;
319  }
320 }
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
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
bool matrix_in_Z(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:39
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
Definition: cf_linsys.cc:61
CanonicalForm detbound(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:486
int determinant(int **extmat, int n)
Definition: cf_linsys.cc:556
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
Definition: cf_linsys.cc:203
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
#define DEBOUT(stream, objects)
Definition: debug.h:47
TIMING_START(fac_alg_resultant)
b *CanonicalForm B
Definition: facBivar.cc:52
bool isZero(const CFArray &A)
checks if entries of A are zero
bool pivot(const matrix aMat, const int r1, const int r2, const int c1, const int c2, int *bestR, int *bestC, const ring R)
This code computes a score for each non-zero matrix entry in aMat[r1..r2, c1..c2].
static int sign(int x)
Definition: ring.cc:3469
int * int_ptr
Definition: structs.h:54
#define TIMING_END(t)
Definition: timing.h:93

◆ div()

◆ euclideanNorm()

CanonicalForm euclideanNorm ( const CanonicalForm f)

CanonicalForm euclideanNorm ( const CanonicalForm & f )

euclideanNorm() - return Euclidean norm of ‘f’.

Returns the largest integer smaller or equal norm(‘f’) = sqrt(sum( ‘f’[i]^2 )).

Type info:

f: UVPoly( Z )

Definition at line 565 of file cf_algorithm.cc.

566 {
567  ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
568  "type error: univariate poly over Z expected" );
569 
570  CanonicalForm result = 0;
571  for ( CFIterator i = f; i.hasTerms(); i++ ) {
572  CanonicalForm coeff = i.coeff();
573  result += coeff*coeff;
574  }
575  return sqrt( result );
576 }
gmp_float sqrt(const gmp_float &a)
Definition: mpr_complex.cc:327

◆ ExtensionLevel()

int ExtensionLevel ( )

Definition at line 254 of file variable.cc.

255 {
256  if( var_names_ext == 0)
257  return 0;
258  return strlen( var_names_ext )-1;
259 }
STATIC_VAR char * var_names_ext
Definition: variable.cc:43

◆ extgcd()

CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )

extgcd() - returns polynomial extended gcd of f and g.

Returns gcd(f, g) and a and b sucht that f*a+g*b=gcd(f, g). The gcd is calculated using an extended euclidean polynomial remainder sequence, so f and g should be polynomials over an euclidean domain. Normalizes result.

Note: be sure that f and g have the same level!

Definition at line 174 of file cfUnivarGcd.cc.

175 {
176  if (f.isZero())
177  {
178  a= 0;
179  b= 1;
180  return g;
181  }
182  else if (g.isZero())
183  {
184  a= 1;
185  b= 0;
186  return f;
187  }
188 #ifdef HAVE_FLINT
190  && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
191  {
192  nmod_poly_t F1, G1, A, B, R;
198  nmod_poly_xgcd (R, A, B, F1, G1);
199  a= convertnmod_poly_t2FacCF (A, f.mvar());
200  b= convertnmod_poly_t2FacCF (B, f.mvar());
202  nmod_poly_clear (F1);
203  nmod_poly_clear (G1);
204  nmod_poly_clear (A);
205  nmod_poly_clear (B);
206  nmod_poly_clear (R);
207  return r;
208  }
209 #elif defined(HAVE_NTL)
211  && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
212  {
214  {
217  }
218  zz_pX F1=convertFacCF2NTLzzpX(f);
219  zz_pX G1=convertFacCF2NTLzzpX(g);
220  zz_pX R;
221  zz_pX A,B;
222  XGCD(R,A,B,F1,G1);
223  a=convertNTLzzpX2CF(A,f.mvar());
224  b=convertNTLzzpX2CF(B,f.mvar());
225  return convertNTLzzpX2CF(R,f.mvar());
226  }
227 #endif
228 #ifdef HAVE_FLINT
229  if (( getCharacteristic() ==0) && (f.level()==g.level())
230  && isPurePoly(f) && isPurePoly(g))
231  {
232  fmpq_poly_t F1, G1;
235  fmpq_poly_t R, A, B;
236  fmpq_poly_init (R);
237  fmpq_poly_init (A);
238  fmpq_poly_init (B);
239  fmpq_poly_xgcd (R, A, B, F1, G1);
240  a= convertFmpq_poly_t2FacCF (A, f.mvar());
241  b= convertFmpq_poly_t2FacCF (B, f.mvar());
243  fmpq_poly_clear (F1);
244  fmpq_poly_clear (G1);
245  fmpq_poly_clear (A);
246  fmpq_poly_clear (B);
247  fmpq_poly_clear (R);
248  return r;
249  }
250 #elif defined(HAVE_NTL)
251  if (( getCharacteristic() ==0)
252  && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
253  {
256  ZZX F1=convertFacCF2NTLZZX(f*fc);
257  ZZX G1=convertFacCF2NTLZZX(g*gc);
258  ZZX R=GCD(F1,G1);
259  CanonicalForm r=convertNTLZZX2CF(R,f.mvar());
260  ZZ RR;
261  ZZX A,B;
262  if (r.inCoeffDomain())
263  {
264  XGCD(RR,A,B,F1,G1,1);
266  if(!rr.isZero())
267  {
268  a=convertNTLZZX2CF(A,f.mvar())*fc/rr;
269  b=convertNTLZZX2CF(B,f.mvar())*gc/rr;
270  return CanonicalForm(1);
271  }
272  else
273  {
274  F1 /= R;
275  G1 /= R;
276  XGCD (RR, A,B,F1,G1,1);
277  rr=convertZZ2CF(RR);
278  a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
279  b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
280  }
281  }
282  else
283  {
284  XGCD(RR,A,B,F1,G1,1);
286  if (!rr.isZero())
287  {
288  a=convertNTLZZX2CF(A,f.mvar())*fc;
289  b=convertNTLZZX2CF(B,f.mvar())*gc;
290  }
291  else
292  {
293  F1 /= R;
294  G1 /= R;
295  XGCD (RR, A,B,F1,G1,1);
296  rr=convertZZ2CF(RR);
297  a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
298  b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
299  }
300  return r;
301  }
302  }
303 #endif
304  // may contain bug in the co-factors, see track 107
305  CanonicalForm contf = content( f );
306  CanonicalForm contg = content( g );
307 
308  CanonicalForm p0 = f / contf, p1 = g / contg;
309  CanonicalForm f0 = 1, f1 = 0, g0 = 0, g1 = 1, q, r;
310 
311  while ( ! p1.isZero() )
312  {
313  divrem( p0, p1, q, r );
314  p0 = p1; p1 = r;
315  r = g0 - g1 * q;
316  g0 = g1; g1 = r;
317  r = f0 - f1 * q;
318  f0 = f1; f1 = r;
319  }
320  CanonicalForm contp0 = content( p0 );
321  a = f0 / ( contf * contp0 );
322  b = g0 / ( contg * contp0 );
323  p0 /= contp0;
324  if ( p0.sign() < 0 )
325  {
326  p0 = -p0;
327  a = -a;
328  b = -b;
329  }
330  return p0;
331 }
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:495
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:285
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
#define GaloisFieldDomain
Definition: cf_defs.h:18
static int gettype()
Definition: cf_factory.h:28
int sign() const
int CanonicalForm::sign () const
bool inCoeffDomain() const
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
void init()
Definition: lintree.cc:864
#define R
Definition: sirandom.c:27

◆ facAlgFunc()

CFFList facAlgFunc ( const CanonicalForm f,
const CFList as 
)

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Returns
the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

1044 {
1045  bool isRat= isOn (SW_RATIONAL);
1046  if (!isRat && getCharacteristic() == 0)
1047  On (SW_RATIONAL);
1048  CFFList Output, output, Factors= factorize(f);
1049  if (Factors.getFirst().factor().inCoeffDomain())
1050  Factors.removeFirst();
1051 
1052  if (as.length() == 0)
1053  {
1054  if (!isRat && getCharacteristic() == 0)
1055  Off (SW_RATIONAL);
1056  return Factors;
1057  }
1058  if (f.level() <= as.getLast().level())
1059  {
1060  if (!isRat && getCharacteristic() == 0)
1061  Off (SW_RATIONAL);
1062  return Factors;
1063  }
1064 
1065  for (CFFListIterator i=Factors; i.hasItem(); i++)
1066  {
1067  if (i.getItem().factor().level() > as.getLast().level())
1068  {
1069  output= facAlgFunc2 (i.getItem().factor(), as);
1070  for (CFFListIterator j= output; j.hasItem(); j++)
1071  Output= append (Output, CFFactor (j.getItem().factor(),
1072  j.getItem().exp()*i.getItem().exp()));
1073  }
1074  }
1075 
1076  if (!isRat && getCharacteristic() == 0)
1077  Off (SW_RATIONAL);
1078  return Output;
1079 }
void removeFirst()
Definition: ftmpl_list.cc:287
T getLast() const
Definition: ftmpl_list.cc:309
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
Definition: facAlgFunc.cc:905

◆ facAlgFunc2()

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 irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Returns
the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

906 {
907  bool isRat= isOn (SW_RATIONAL);
908  if (!isRat && getCharacteristic() == 0)
909  On (SW_RATIONAL);
910  Variable vf=f.mvar();
912  CFFListIterator jj;
913  CFList reduceresult;
914  CFFList result;
915 
916 // F1: [Test trivial cases]
917 // 1) first trivial cases:
918  if (vf.level() <= as.getLast().level())
919  {
920  if (!isRat && getCharacteristic() == 0)
921  Off (SW_RATIONAL);
922  return CFFList(CFFactor(f,1));
923  }
924 
925 // 2) Setup list of those polys in AS having degree > 1
926  CFList Astar;
927  Variable x;
928  CanonicalForm elem;
929  Varlist ord, uord;
930  for (int ii= 1; ii < level (vf); ii++)
931  uord.append (Variable (ii));
932 
933  for (i= as; i.hasItem(); i++)
934  {
935  elem= i.getItem();
936  x= elem.mvar();
937  if (degree (elem, x) > 1) // otherwise it's not an extension
938  {
939  Astar.append (elem);
940  ord.append (x);
941  }
942  }
943  uord= Difference (uord, ord);
944 
945 // 3) second trivial cases: we already proved irr. of f over no extensions
946  if (Astar.length() == 0)
947  {
948  if (!isRat && getCharacteristic() == 0)
949  Off (SW_RATIONAL);
950  return CFFList (CFFactor (f, 1));
951  }
952 
953 // 4) Look if elements in uord actually occur in any of the minimal
954 // polynomials. If no element of uord occures in any of the minimal
955 // polynomials the field is an alg. number field not an alg. function field
956  Varlist newuord= varsInAs (uord, Astar);
957 
958  CFFList Factorlist;
959  Varlist gcdord= Union (ord, newuord);
960  gcdord.append (f.mvar());
961  bool isFunctionField= (newuord.length() > 0);
962 
963  // TODO alg_sqrfree?
964  CanonicalForm Fgcd= 0;
965  if (isFunctionField)
966  Fgcd= alg_gcd (f, f.deriv(), Astar);
967 
968  bool derivZero= f.deriv().isZero();
969  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
970  {
971  CanonicalForm Ggcd= divide(f, Fgcd,Astar);
972  if (getCharacteristic() == 0)
973  {
974  CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
975  multiplicity (result, f, Astar);
976  if (!isRat && getCharacteristic() == 0)
977  Off (SW_RATIONAL);
978  return result;
979  }
980 
981  Fgcd= pp (Fgcd);
982  Ggcd= pp (Ggcd);
983  if (!isRat && getCharacteristic() == 0)
984  Off (SW_RATIONAL);
985  return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
986  }
987 
988  if (getCharacteristic() > 0)
989  {
990  IntList degreelist;
991  Variable vminpoly;
992  for (i= Astar; i.hasItem(); i++)
993  degreelist.append (degree (i.getItem()));
994 
995  int extdeg= getDegOfExt (degreelist, degree (f));
996 
997  if (newuord.length() == 0) // no parameters
998  {
999  if (extdeg > 1)
1000  {
1001  CanonicalForm MIPO= generateMipo (extdeg);
1002  vminpoly= rootOf(MIPO);
1003  }
1004  Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
1005  if (extdeg > 1)
1006  prune (vminpoly);
1007  return Factorlist;
1008  }
1009  else if (isInseparable(Astar) || derivZero) // inseparable case
1010  {
1011  Factorlist= SteelTrager (f, Astar);
1012  return Factorlist;
1013  }
1014  else // separable case
1015  {
1016  if (extdeg > 1)
1017  {
1018  CanonicalForm MIPO=generateMipo (extdeg);
1019  vminpoly= rootOf (MIPO);
1020  }
1021  Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1022  if (extdeg > 1)
1023  prune (vminpoly);
1024  return Factorlist;
1025  }
1026  }
1027  else // char 0
1028  {
1029  Variable vminpoly;
1030  Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1031  if (!isRat && getCharacteristic() == 0)
1032  Off (SW_RATIONAL);
1033  return Factorlist;
1034  }
1035 
1036  return CFFList (CFFactor(f,1));
1037 }
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void append(const T &)
Definition: ftmpl_list.cc:256
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int getDegOfExt(IntList &degreelist, int n)
bool isInseparable(const CFList &Astar)
CanonicalForm generateMipo(int degOfExt)
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
static CFFList Trager(const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.
Definition: facAlgFunc.cc:430
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
void FACTORY_PUBLIC prune(Variable &alpha)
Definition: variable.cc:261
STATIC_VAR int * multiplicity

◆ factorize() [1/2]

CFFList FACTORY_PUBLIC factorize ( const CanonicalForm f,
bool  issqrfree = false 
)

factorization over $ F_p $ or $ Q $

Definition at line 405 of file cf_factor.cc.

406 {
407  if ( f.inCoeffDomain() )
408  return CFFList( f );
409 #ifndef NOASSERT
410  Variable a;
411  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
412  ( const CanonicalForm & f, const Variable & alpha ) instead");
413 #endif
414  //out_cf("factorize:",f,"==================================\n");
415  if (! f.isUnivariate() ) // preprocess homog. polys
416  {
417  if ( singular_homog_flag && f.isHomogeneous())
418  {
420  int d_xn = degree(f,xn);
421  CFMap n;
422  CanonicalForm F = compress(f(1,xn),n);
423  CFFList Intermediatelist;
424  Intermediatelist = factorize(F);
425  CFFList Homoglist;
427  for ( j=Intermediatelist; j.hasItem(); j++ )
428  {
429  Homoglist.append(
430  CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
431  }
432  CFFList Unhomoglist;
433  CanonicalForm unhomogelem;
434  for ( j=Homoglist; j.hasItem(); j++ )
435  {
436  unhomogelem= homogenize(j.getItem().factor(),xn);
437  Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
438  d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
439  }
440  if ( d_xn != 0 ) // have to append xn^(d_xn)
441  Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
442  if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
443  return Unhomoglist;
444  }
445  }
446  CFFList F;
447  if ( getCharacteristic() > 0 )
448  {
449  if (f.isUnivariate())
450  {
451 #ifdef HAVE_FLINT
452 #ifdef HAVE_NTL
453  if (degree (f) < 300)
454 #endif
455  {
456  // use FLINT: char p, univariate
457  nmod_poly_t f1;
459  nmod_poly_factor_t result;
460  nmod_poly_factor_init (result);
461  mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
462  F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
463  nmod_poly_factor_clear (result);
464  nmod_poly_clear (f1);
465  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
466  return F;
467  }
468 #endif
469 #ifdef HAVE_NTL
470  { // NTL char 2, univariate
471  if (getCharacteristic()==2)
472  {
473  // Specialcase characteristic==2
474  if (fac_NTL_char != 2)
475  {
476  fac_NTL_char = 2;
477  zz_p::init(2);
478  }
479  // convert to NTL using the faster conversion routine for characteristic 2
480  GF2X f1=convertFacCF2NTLGF2X(f);
481  // no make monic necessary in GF2
482  //factorize
483  vec_pair_GF2X_long factors;
484  CanZass(factors,f1);
485 
486  // convert back to factory again using the faster conversion routine for vectors over GF2X
487  F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
488  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
489  return F;
490  }
491  }
492 #endif
493 #ifdef HAVE_NTL
494  {
495  // use NTL char p, univariate
497  {
500  }
501 
502  // convert to NTL
503  zz_pX f1=convertFacCF2NTLzzpX(f);
504  zz_p leadcoeff = LeadCoeff(f1);
505 
506  //make monic
507  f1=f1 / LeadCoeff(f1);
508  // factorize
509  vec_pair_zz_pX_long factors;
510  CanZass(factors,f1);
511 
512  F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
513  //test_cff(F,f);
514  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
515  return F;
516  }
517 #endif
518 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
519  // Use Factory without NTL and without FLINT: char p, univariate
520  {
521  if ( isOn( SW_BERLEKAMP ) )
522  F=FpFactorizeUnivariateB( f, issqrfree );
523  else
524  F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
525  return F;
526  }
527 #endif
528  }
529  else // char p, multivariate
530  {
532  {
533  #if defined(HAVE_NTL)
534  if (issqrfree)
535  {
536  CFList factors;
537  Variable alpha;
538  factors= GFSqrfFactorize (f);
539  for (CFListIterator i= factors; i.hasItem(); i++)
540  F.append (CFFactor (i.getItem(), 1));
541  }
542  else
543  {
544  Variable alpha;
545  F= GFFactorize (f);
546  }
547  #else
548  factoryError ("multivariate factorization over GF depends on NTL(missing)");
549  return CFFList (CFFactor (f, 1));
550  #endif
551  }
552  else
553  {
554  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
555  if (!isOn(SW_USE_FL_FAC_P))
556  {
557  #endif
558  #if defined(HAVE_NTL)
559  if (issqrfree)
560  {
561  CFList factors;
562  Variable alpha;
563  factors= FpSqrfFactorize (f);
564  for (CFListIterator i= factors; i.hasItem(); i++)
565  F.append (CFFactor (i.getItem(), 1));
566  goto end_charp;
567  }
568  else
569  {
570  Variable alpha;
571  F= FpFactorize (f);
572  goto end_charp;
573  }
574  #endif
575  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
576  }
577  #endif
578  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
579  nmod_mpoly_ctx_t ctx;
580  nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
581  nmod_mpoly_t Flint_f;
582  nmod_mpoly_init(Flint_f,ctx);
583  convFactoryPFlintMP(f,Flint_f,ctx,f.level());
584  nmod_mpoly_factor_t factors;
585  nmod_mpoly_factor_init(factors,ctx);
586  int okay;
587  if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
588  else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
589  nmod_mpoly_t fac;
590  nmod_mpoly_init(fac,ctx);
591  CanonicalForm cf_fac;
592  int cf_exp;
593  cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
594  F.append(CFFactor(cf_fac,1));
595  for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
596  {
597  nmod_mpoly_factor_get_base(fac,factors,i,ctx);
598  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
599  cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
600  F.append(CFFactor(cf_fac,cf_exp));
601  }
602  nmod_mpoly_factor_clear(factors,ctx);
603  nmod_mpoly_clear(Flint_f,ctx);
604  nmod_mpoly_ctx_clear(ctx);
605  if (okay==0)
606  {
609  F=factorize(f,issqrfree);
612  }
613  #endif
614  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
615  #ifndef HAVE_NTL
616  factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
617  return CFFList (CFFactor (f, 1));
618  #endif
619  #endif
620  }
621  }
622  }
623  else // char 0
624  {
625  bool on_rational = isOn(SW_RATIONAL);
626  On(SW_RATIONAL);
628  CanonicalForm fz = f * cd;
629  Off(SW_RATIONAL);
630  if ( f.isUnivariate() )
631  {
632  CanonicalForm ic=icontent(fz);
633  fz/=ic;
634  if (fz.degree()==1)
635  {
636  F=CFFList(CFFactor(fz,1));
637  F.insert(CFFactor(ic,1));
638  }
639  else
640  #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
641  {
642  // FLINT 2.6.0 has a bug:
643  // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
644  // use FLINT: char 0, univariate
645  fmpz_poly_t f1;
646  convertFacCF2Fmpz_poly_t (f1, fz);
647  fmpz_poly_factor_t result;
648  fmpz_poly_factor_init (result);
649  fmpz_poly_factor(result, f1);
651  fmpz_poly_factor_clear (result);
652  fmpz_poly_clear (f1);
653  if ( ! ic.isOne() )
654  {
655  // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
656  // first entry is in CoeffDomain
657  CFFactor new_first( F.getFirst().factor() * ic );
658  F.removeFirst();
659  F.insert( new_first );
660  }
661  }
662  goto end_char0;
663  #elif defined(HAVE_NTL)
664  {
665  //use NTL
666  ZZ c;
667  vec_pair_ZZX_long factors;
668  //factorize the converted polynomial
669  factor(c,factors,convertFacCF2NTLZZX(fz));
670 
671  //convert the result back to Factory
673  if ( ! ic.isOne() )
674  {
675  // according to convertNTLvec_pair_ZZX_long2FacCFFList
676  // first entry is in CoeffDomain
677  CFFactor new_first( F.getFirst().factor() * ic );
678  F.removeFirst();
679  F.insert( new_first );
680  }
681  }
682  goto end_char0;
683  #else
684  {
685  //Use Factory without NTL: char 0, univariate
686  F = ZFactorizeUnivariate( fz, issqrfree );
687  goto end_char0;
688  }
689  #endif
690  }
691  else // multivariate, char 0
692  {
693  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
694  if (isOn(SW_USE_FL_FAC_0))
695  {
696  On (SW_RATIONAL);
697  fmpz_mpoly_ctx_t ctx;
698  fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
699  fmpz_mpoly_t Flint_f;
700  fmpz_mpoly_init(Flint_f,ctx);
701  convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
702  fmpz_mpoly_factor_t factors;
703  fmpz_mpoly_factor_init(factors,ctx);
704  int rr;
705  if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
706  else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
707  if (rr==0) printf("fail\n");
708  fmpz_mpoly_t fac;
709  fmpz_mpoly_init(fac,ctx);
710  CanonicalForm cf_fac;
711  int cf_exp;
712  fmpz_t c;
713  fmpz_init(c);
714  fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
715  cf_fac=convertFmpz2CF(c);
716  fmpz_clear(c);
717  F.append(CFFactor(cf_fac,1));
718  for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
719  {
720  fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
721  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
722  cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
723  F.append(CFFactor(cf_fac,cf_exp));
724  }
725  fmpz_mpoly_factor_clear(factors,ctx);
726  fmpz_mpoly_clear(Flint_f,ctx);
727  fmpz_mpoly_ctx_clear(ctx);
728  goto end_char0;
729  }
730  #endif
731  #if defined(HAVE_NTL)
732  On (SW_RATIONAL);
733  if (issqrfree)
734  {
735  CFList factors= ratSqrfFactorize (fz);
736  for (CFListIterator i= factors; i.hasItem(); i++)
737  F.append (CFFactor (i.getItem(), 1));
738  }
739  else
740  {
741  F = ratFactorize (fz);
742  }
743  #endif
744  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
745  #ifndef HAVE_NTL
746  F=ZFactorizeMultivariate(fz, issqrfree);
747  #endif
748  #endif
749  }
750 
751 end_char0:
752  if ( on_rational )
753  On(SW_RATIONAL);
754  else
755  Off(SW_RATIONAL);
756  if ( ! cd.isOne() )
757  {
758  CFFactor new_first( F.getFirst().factor() / cd );
759  F.removeFirst();
760  F.insert( new_first );
761  }
762  }
763 
764 #if defined(HAVE_NTL)
765 end_charp:
766 #endif
767  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
768  return F;
769 }
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:446
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition: NTLconvert.cc:399
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:184
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:753
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: cf_defs.h:47
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:39
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:57
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:55
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition: cf_defs.h:51
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:260
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:394
VAR int singular_homog_flag
Definition: cf_factor.cc:392
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:313
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:405
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
CF_NO_INLINE bool isOne() const
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
void insert(const T &)
Definition: ftmpl_list.cc:193
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm factor
Definition: facAbsFact.cc:97
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:79
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
VAR int xn
Definition: walk.cc:4508

◆ factorize() [2/2]

CFFList FACTORY_PUBLIC factorize ( const CanonicalForm f,
const Variable alpha 
)

factorization over $ F_p(\alpha) $ or $ Q(\alpha) $

Definition at line 774 of file cf_factor.cc.

775 {
776  if ( f.inCoeffDomain() )
777  return CFFList( f );
778  //out_cf("factorize:",f,"==================================\n");
779  //out_cf("mipo:",getMipo(alpha),"\n");
780 
781  CFFList F;
782  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
783 #ifndef NOASSERT
784  Variable beta;
785  if (hasFirstAlgVar(f, beta))
786  ASSERT (beta == alpha, "f has an algebraic variable that \
787  does not coincide with alpha");
788 #endif
789  int ch=getCharacteristic();
790  if (ch>0)
791  {
792  if (f.isUnivariate())
793  {
794 #ifdef HAVE_NTL
795  if (/*getCharacteristic()*/ch==2)
796  {
797  // special case : GF2
798 
799  // remainder is two ==> nothing to do
800 
801  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
802  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
803  GF2E::init (minPo);
804 
805  // convert to NTL again using the faster conversion routines
806  GF2EX f1;
807  if (isPurePoly(f))
808  {
809  GF2X f_tmp=convertFacCF2NTLGF2X(f);
810  f1=to_GF2EX(f_tmp);
811  }
812  else
813  f1=convertFacCF2NTLGF2EX(f,minPo);
814 
815  // make monic (in Z/2(a))
816  GF2E f1_coef=LeadCoeff(f1);
817  MakeMonic(f1);
818 
819  // factorize using NTL
820  vec_pair_GF2EX_long factors;
821  CanZass(factors,f1);
822 
823  // return converted result
824  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
825  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
826  return F;
827  }
828 #endif
829 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
830  {
831  // use FLINT
832  nmod_poly_t FLINTmipo, leadingCoeff;
833  fq_nmod_ctx_t fq_con;
834 
835  nmod_poly_init (FLINTmipo, ch);
836  nmod_poly_init (leadingCoeff, ch);
837  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
838 
839  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
840  fq_nmod_poly_t FLINTF;
842  fq_nmod_poly_factor_t res;
843  fq_nmod_poly_factor_init (res, fq_con);
844  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
846  F.insert (CFFactor (Lc (f), 1));
847 
848  fq_nmod_poly_factor_clear (res, fq_con);
849  fq_nmod_poly_clear (FLINTF, fq_con);
850  nmod_poly_clear (FLINTmipo);
851  nmod_poly_clear (leadingCoeff);
853  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
854  return F;
855  }
856 #endif
857 #ifdef HAVE_NTL
858  {
859  // use NTL
860  if (fac_NTL_char != ch)
861  {
862  fac_NTL_char = ch;
863  zz_p::init(ch);
864  }
865 
866  // set minimal polynomial in NTL
867  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
868  zz_pE::init (minPo);
869 
870  // convert to NTL
871  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
872  zz_pE leadcoeff= LeadCoeff(f1);
873 
874  //make monic
875  f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
876 
877  // factorize
878  vec_pair_zz_pEX_long factors;
879  CanZass(factors,f1);
880 
881  // return converted result
882  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
883  //test_cff(F,f);
884  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
885  return F;
886  }
887 #endif
888 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
889  // char p, extension, univariate
890  CanonicalForm c=Lc(f);
891  CanonicalForm fc=f/c;
892  F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
893  F.insert (CFFactor (c, 1));
894 #endif
895  }
896  else // char p, multivariate
897  {
898  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
899  // use FLINT
900  nmod_poly_t FLINTmipo;
901  fq_nmod_ctx_t fq_con;
902  fq_nmod_mpoly_ctx_t ctx;
903 
904  nmod_poly_init (FLINTmipo, ch);
905  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
906 
907  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
908  fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
909 
910  fq_nmod_mpoly_t FLINTF;
911  fq_nmod_mpoly_init(FLINTF,ctx);
912  convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
913  fq_nmod_mpoly_factor_t res;
914  fq_nmod_mpoly_factor_init (res, ctx);
915  fq_nmod_mpoly_factor (res, FLINTF, ctx);
916  F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
917  //F.insert (CFFactor (Lc (f), 1));
918 
919  fq_nmod_mpoly_factor_clear (res, ctx);
920  fq_nmod_mpoly_clear (FLINTF, ctx);
921  nmod_poly_clear (FLINTmipo);
922  fq_nmod_mpoly_ctx_clear (ctx);
924  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
925  return F;
926  #elif defined(HAVE_NTL)
927  F= FqFactorize (f, alpha);
928  #else
929  factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
930  return CFFList (CFFactor (f, 1));
931  #endif
932  }
933  }
934  else // Q(a)[x]
935  {
936  if (f.isUnivariate())
937  {
938  F= AlgExtFactorize (f, alpha);
939  }
940  else //Q(a)[x1,...,xn]
941  {
942  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
943  F= ratFactorize (f, alpha);
944  #else
945  factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
946  return CFFList (CFFactor (f, 1));
947  #endif
948  }
949  }
950  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
951  return F;
952 }
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:870
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:959
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1007
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
CanonicalForm res
Definition: facAbsFact.cc:60
Variable beta
Definition: facAbsFact.cc:95
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:370
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207

◆ factoryError_intern()

void factoryError_intern ( const char *  s)

Definition at line 75 of file cf_util.cc.

76 {
77  fputs(s,stderr);
78  abort();
79 }

◆ factoryrandom()

int factoryrandom ( int  n)

random integers with abs less than n

Definition at line 180 of file cf_random.cc.

181 {
182  if ( n == 0 )
183  return (int)ranGen.generate();
184  else
185  return ranGen.generate() % n;
186 }
INST_VAR RandomGenerator ranGen
Definition: cf_random.cc:66

◆ factoryseed()

void FACTORY_PUBLIC factoryseed ( int  s)

random seed initializer

Definition at line 189 of file cf_random.cc.

190 {
191  ranGen.seed( s );
192 
193 #ifdef HAVE_FLINT
194  flint_randinit(FLINTrandom);
195 #endif
196 }
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
void seed(int ss)
Definition: cf_random.cc:41

◆ Farey()

Farey rational reconstruction.

If NTL is available it uses the fast algorithm from NTL, i.e. Encarnacion, Collins.

Definition at line 202 of file cf_chinese.cc.

203 {
204  int is_rat=isOn(SW_RATIONAL);
205  Off(SW_RATIONAL);
206  Variable x = f.mvar();
207  CanonicalForm result = 0;
208  CanonicalForm c;
209  CFIterator i;
210 #ifdef HAVE_FLINT
211  fmpz_t FLINTq;
212  fmpz_init(FLINTq);
213  convertCF2initFmpz(FLINTq,q);
214  fmpz_t FLINTc;
215  fmpz_init(FLINTc);
216  fmpq_t FLINTres;
217  fmpq_init(FLINTres);
218 #elif defined(HAVE_NTL)
219  ZZ NTLq= convertFacCF2NTLZZ (q);
220  ZZ bound;
221  SqrRoot (bound, NTLq/2);
222 #else
223  factoryError("NTL/FLINT missing:Farey");
224 #endif
225  for ( i = f; i.hasTerms(); i++ )
226  {
227  c = i.coeff();
228  if ( c.inCoeffDomain())
229  {
230 #ifdef HAVE_FLINT
231  if (c.inZ())
232  {
233  convertCF2initFmpz(FLINTc,c);
234  fmpq_reconstruct_fmpz(FLINTres,FLINTc,FLINTq);
235  result += power (x, i.exp())*(convertFmpq2CF(FLINTres));
236  }
237 #elif defined(HAVE_NTL)
238  if (c.inZ())
239  {
240  ZZ NTLc= convertFacCF2NTLZZ (c);
241  bool lessZero= (sign (NTLc) == -1);
242  if (lessZero)
243  NTL::negate (NTLc, NTLc);
244  ZZ NTLnum, NTLden;
245  if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
246  {
247  if (lessZero)
248  NTL::negate (NTLnum, NTLnum);
249  CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
250  CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
251  On (SW_RATIONAL);
252  result += power (x, i.exp())*(num/den);
253  Off (SW_RATIONAL);
254  }
255  }
256 #else
257  if (c.inZ())
258  result += power (x, i.exp()) * Farey_n(c,q);
259 #endif
260  else
261  result += power( x, i.exp() ) * Farey(c,q);
262  }
263  else
264  result += power( x, i.exp() ) * Farey(c,q);
265  }
266  if (is_rat) On(SW_RATIONAL);
267 #ifdef HAVE_FLINT
268  fmpq_clear(FLINTres);
269  fmpz_clear(FLINTc);
270  fmpz_clear(FLINTq);
271 #endif
272  return result;
273 }
CanonicalForm convertFmpq2CF(const fmpq_t q)
conversion of a FLINT rational to CanonicalForm
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
CanonicalForm num(const CanonicalForm &f)
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:202
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
bool inZ() const
predicates

◆ fdivides() [1/2]

bool fdivides ( const CanonicalForm f,
const CanonicalForm g 
)

bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )

fdivides() - check whether ‘f’ divides ‘g’.

Returns true iff ‘f’ divides ‘g’. Uses some extra heuristic to avoid polynomial division. Without the heuristic, the test essentialy looks like ‘divremt(g, f, q, r) && r.isZero()’.

Type info:

f, g: Current

Elements from prime power domains (or polynomials over such domains) are admissible if ‘f’ (or lc(‘f’), resp.) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since divisibility is a well-defined notion in arbitrary rings. Hence, we decided not to declare the weaker type ‘CurrentPP’.

Developers note:

One may consider the the test ‘fdivides( f.LC(), g.LC() )’ in the main ‘if’-test superfluous since ‘divremt()’ in the ‘if’-body repeats the test. However, ‘divremt()’ does not use any heuristic to do so.

It seems not reasonable to call ‘fdivides()’ from ‘divremt()’ to check divisibility of leading coefficients. ‘fdivides()’ is on a relatively high level compared to ‘divremt()’.

Definition at line 340 of file cf_algorithm.cc.

341 {
342  // trivial cases
343  if ( g.isZero() )
344  return true;
345  else if ( f.isZero() )
346  return false;
347 
348  if ( (f.inCoeffDomain() || g.inCoeffDomain())
349  && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
350  || (getCharacteristic() > 0) ))
351  {
352  // if we are in a field all elements not equal to zero are units
353  if ( f.inCoeffDomain() )
354  return true;
355  else
356  // g.inCoeffDomain()
357  return false;
358  }
359 
360  // we may assume now that both levels either equal LEVELBASE
361  // or are greater zero
362  int fLevel = f.level();
363  int gLevel = g.level();
364  if ( (gLevel > 0) && (fLevel == gLevel) )
365  // f and g are polynomials in the same main variable
366  if ( degree( f ) <= degree( g )
367  && fdivides( f.tailcoeff(), g.tailcoeff() )
368  && fdivides( f.LC(), g.LC() ) )
369  {
370  CanonicalForm q, r;
371  return divremt( g, f, q, r ) && r.isZero();
372  }
373  else
374  return false;
375  else if ( gLevel < fLevel )
376  // g is a coefficient w.r.t. f
377  return false;
378  else
379  {
380  // either f is a coefficient w.r.t. polynomial g or both
381  // f and g are from a base domain (should be Z or Z/p^n,
382  // then)
383  CanonicalForm q, r;
384  return divremt( g, f, q, r ) && r.isZero();
385  }
386 }
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )

◆ fdivides() [2/2]

bool fdivides ( const CanonicalForm f,
const CanonicalForm g,
CanonicalForm quot 
)

same as fdivides if true returns quotient quot of g by f otherwise quot == 0

Definition at line 390 of file cf_algorithm.cc.

391 {
392  quot= 0;
393  // trivial cases
394  if ( g.isZero() )
395  return true;
396  else if ( f.isZero() )
397  return false;
398 
399  if ( (f.inCoeffDomain() || g.inCoeffDomain())
400  && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
401  || (getCharacteristic() > 0) ))
402  {
403  // if we are in a field all elements not equal to zero are units
404  if ( f.inCoeffDomain() )
405  {
406  quot= g/f;
407  return true;
408  }
409  else
410  // g.inCoeffDomain()
411  return false;
412  }
413 
414  // we may assume now that both levels either equal LEVELBASE
415  // or are greater zero
416  int fLevel = f.level();
417  int gLevel = g.level();
418  if ( (gLevel > 0) && (fLevel == gLevel) )
419  // f and g are polynomials in the same main variable
420  if ( degree( f ) <= degree( g )
421  && fdivides( f.tailcoeff(), g.tailcoeff() )
422  && fdivides( f.LC(), g.LC() ) )
423  {
424  CanonicalForm q, r;
425  if (divremt( g, f, q, r ) && r.isZero())
426  {
427  quot= q;
428  return true;
429  }
430  else
431  return false;
432  }
433  else
434  return false;
435  else if ( gLevel < fLevel )
436  // g is a coefficient w.r.t. f
437  return false;
438  else
439  {
440  // either f is a coefficient w.r.t. polynomial g or both
441  // f and g are from a base domain (should be Z or Z/p^n,
442  // then)
443  CanonicalForm q, r;
444  if (divremt( g, f, q, r ) && r.isZero())
445  {
446  quot= q;
447  return true;
448  }
449  else
450  return false;
451  }
452 }

◆ gcd()

Definition at line 685 of file cf_gcd.cc.

686 {
687  bool b = f.isZero();
688  if ( b || g.isZero() )
689  {
690  if ( b )
691  return abs( g );
692  else
693  return abs( f );
694  }
695  if ( f.inPolyDomain() || g.inPolyDomain() )
696  {
697  if ( f.mvar() != g.mvar() )
698  {
699  if ( f.mvar() > g.mvar() )
700  return cf_content( f, g );
701  else
702  return cf_content( g, f );
703  }
704  if (isOn(SW_USE_QGCD))
705  {
706  Variable m;
707  if (
708  (getCharacteristic() == 0) &&
710  )
711  {
712  bool on_rational = isOn(SW_RATIONAL);
713  CanonicalForm r=QGCD(f,g);
714  On(SW_RATIONAL);
715  CanonicalForm cdF = bCommonDen( r );
716  if (!on_rational) Off(SW_RATIONAL);
717  return cdF*r;
718  }
719  }
720 
721  if ( f.inExtension() && getReduce( f.mvar() ) )
722  return CanonicalForm(1);
723  else
724  {
725  if ( fdivides( f, g ) )
726  return abs( f );
727  else if ( fdivides( g, f ) )
728  return abs( g );
729  if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
730  {
731  CanonicalForm d;
732  d = gcd_poly( f, g );
733  return abs( d );
734  }
735  else
736  {
737  CanonicalForm cdF = bCommonDen( f );
738  CanonicalForm cdG = bCommonDen( g );
739  CanonicalForm F = f * cdF, G = g * cdG;
740  Off( SW_RATIONAL );
741  CanonicalForm l = gcd_poly( F, G );
742  On( SW_RATIONAL );
743  return abs( l );
744  }
745  }
746  }
747  if ( f.inBaseDomain() && g.inBaseDomain() )
748  return bgcd( f, g );
749  else
750  return 1;
751 }
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition: cfGcdAlgExt.cc:730
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:43
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:492

◆ gcd_poly()

CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )

gcd_poly() - calculate polynomial gcd.

This is the dispatcher for polynomial gcd calculation. Different gcd variants get called depending the input, characteristic, and on switches (cf_defs.h)

With the current settings from Singular (i.e. SW_USE_EZGCD= on, SW_USE_EZGCD_P= on, SW_USE_CHINREM_GCD= on, the EZ GCD variants are the default algorithms for multivariate polynomial GCD computations)

See also
gcd(), cf_defs.h

Definition at line 492 of file cf_gcd.cc.

493 {
494  CanonicalForm fc, gc;
495  bool fc_isUnivariate=f.isUnivariate();
496  bool gc_isUnivariate=g.isUnivariate();
497  bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
498  fc = f;
499  gc = g;
500  int ch=getCharacteristic();
501  if ( ch != 0 )
502  {
503  if (0) {} // dummy, to be able to build without NTL and FLINT
504  #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
505  if ( isOn( SW_USE_FL_GCD_P)
507  #ifdef HAVE_NTL
508  && (ch>10) // if we have NTL: it is better for char <11
509  #endif
510  &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
511  {
512  return gcdFlintMP_Zp(fc,gc);
513  }
514  #endif
515  #ifdef HAVE_NTL
516  if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
517  {
518  fc= EZGCD_P (fc, gc);
519  }
520  #endif
521  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
522  else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
523  {
524  Variable a;
525  if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
526  fc=modGCDFq (fc, gc, a);
528  fc=modGCDGF (fc, gc);
529  else
530  fc=modGCDFp (fc, gc);
531  }
532  #endif
533  else
534  fc = gcd_poly_p( fc, gc );
535  }
536  else if (!fc_and_gc_Univariate) /* && char==0*/
537  {
538  #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
539  if (( isOn( SW_USE_FL_GCD_0) )
540  &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
541  {
542  return gcdFlintMP_QQ(fc,gc);
543  }
544  else
545  #endif
546  #ifdef HAVE_NTL
547  if ( isOn( SW_USE_EZGCD ) )
548  fc= ezgcd (fc, gc);
549  else
550  #endif
551  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
553  fc = modGCDZ( fc, gc);
554  else
555  #endif
556  {
557  fc = gcd_poly_0( fc, gc );
558  }
559  }
560  else
561  {
562  fc = gcd_poly_0( fc, gc );
563  }
564  if ((ch>0)&&(!hasAlgVar(fc))) fc/=fc.lc();
565  return fc;
566 }
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
Definition: cfEzgcd.cc:876
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:498
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition: cfModGcd.cc:478
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1223
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for Computer Algebra" by Gedde...
Definition: cfModGcd.cc:872
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: cf_defs.h:41
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:37
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:45
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:35
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition: cf_defs.h:49
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:417
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:264
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
int hasAlgVar(const CanonicalForm &f, const Variable &v)

◆ get_max_degree_Variable()

Variable get_max_degree_Variable ( const CanonicalForm f)

get_max_degree_Variable returns Variable with highest degree.

We assume f is not a constant!

Definition at line 260 of file cf_factor.cc.

261 {
262  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
263  int max=0, maxlevel=0, n=level(f);
264  for ( int i=1; i<=n; i++ )
265  {
266  if (degree(f,Variable(i)) >= max)
267  {
268  max= degree(f,Variable(i)); maxlevel= i;
269  }
270  }
271  return Variable(maxlevel);
272 }
static int max(int a, int b)
Definition: fast_mult.cc:264

◆ get_Terms()

CFList get_Terms ( const CanonicalForm f)

Definition at line 289 of file cf_factor.cc.

289  {
290  CFList result,dummy,dummy2;
291  CFIterator i;
293 
294  if ( getNumVars(f) == 0 ) result.append(f);
295  else{
296  Variable _x(level(f));
297  for ( i=f; i.hasTerms(); i++ ){
298  getTerms(i.coeff(), 1, dummy);
299  for ( j=dummy; j.hasItem(); j++ )
300  result.append(j.getItem() * power(_x, i.exp()));
301 
302  dummy= dummy2; // have to initalize new
303  }
304  }
305  return result;
306 }
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:279

◆ getCharacteristic()

int FACTORY_PUBLIC getCharacteristic ( )

Definition at line 70 of file cf_char.cc.

71 {
72  return theCharacteristic;
73 }
STATIC_VAR int theCharacteristic
Definition: cf_char.cc:25

◆ getDefaultExtName()

char getDefaultExtName ( )

Definition at line 249 of file variable.cc.

250 {
251  return default_name_ext;
252 }
STATIC_VAR char default_name_ext
Definition: variable.cc:45

◆ getDefaultVarName()

char getDefaultVarName ( )

Definition at line 244 of file variable.cc.

245 {
246  return default_name;
247 }
STATIC_VAR char default_name
Definition: variable.cc:44

◆ getGFDegree()

int getGFDegree ( )

Definition at line 75 of file cf_char.cc.

76 {
77  //ASSERT( theDegree > 0, "not in GF(q)" );
78  return theDegree;
79 }
STATIC_VAR int theDegree
Definition: cf_char.cc:26

◆ getGFGenerator()

CanonicalForm getGFGenerator ( )

Definition at line 81 of file cf_char.cc.

82 {
83  ASSERT( theDegree > 1, "not in GF(q)" );
84  return int2imm_gf( 1 );
85 }
InternalCF * int2imm_gf(long i)
Definition: imm.h:106

◆ getMipo()

CanonicalForm getMipo ( const Variable alpha,
const Variable x 
)

Definition at line 207 of file variable.cc.

208 {
209  ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
211 }
#define LEVELBASE
Definition: cf_defs.h:25
InternalCF * copyObject()
Definition: int_cf.h:62
InternalPoly * mipo()
Definition: variable.cc:36
STATIC_VAR ext_entry * algextensions
Definition: variable.cc:41

◆ getNumVars()

int getNumVars ( const CanonicalForm f)

int getNumVars ( const CanonicalForm & f )

getNumVars() - get number of polynomial variables in f.

Definition at line 314 of file cf_ops.cc.

315 {
316  int n;
317  if ( f.inCoeffDomain() )
318  return 0;
319  else if ( (n = f.level()) == 1 )
320  return 1;
321  else
322  {
323  int * vars = NEW_ARRAY(int, n+1);
324  int i;
325  for ( i = n-1; i >=0; i-- ) vars[i] = 0;
326 
327  // look for variables
328  for ( CFIterator I = f; I.hasTerms(); ++I )
329  fillVarsRec( I.coeff(), vars );
330 
331  // count them
332  int m = 0;
333  for ( i = 1; i < n; i++ )
334  if ( vars[i] != 0 ) m++;
335 
336  DELETE_ARRAY(vars);
337  // do not forget to count our own variable
338  return m+1;
339  }
340 }
static void fillVarsRec(const CanonicalForm &f, int *vars)
static void fillVarsRec ( const CanonicalForm & f, int * vars )
Definition: cf_ops.cc:296

◆ getTerms()

void getTerms ( const CanonicalForm f,
const CanonicalForm t,
CFList result 
)

get_Terms: Split the polynomial in the containing terms.

getTerms: the real work is done here.

Definition at line 279 of file cf_factor.cc.

280 {
281  if ( getNumVars(f) == 0 ) result.append(f*t);
282  else{
283  Variable x(level(f));
284  for ( CFIterator i=f; i.hasTerms(); i++ )
285  getTerms( i.coeff(), t*power(x,i.exp()), result);
286  }
287 }

◆ getVars()

CanonicalForm getVars ( const CanonicalForm f)

CanonicalForm getVars ( const CanonicalForm & f )

getVars() - get polynomial variables of f.

Return the product of all of them, 1 if there are not any.

Definition at line 350 of file cf_ops.cc.

351 {
352  int n;
353  if ( f.inCoeffDomain() )
354  return 1;
355  else if ( (n = f.level()) == 1 )
356  return Variable( 1 );
357  else
358  {
359  int * vars = NEW_ARRAY(int, n+1);
360  int i;
361  for ( i = n; i >= 0; i-- ) vars[i] = 0;
362 
363  // look for variables
364  for ( CFIterator I = f; I.hasTerms(); ++I )
365  fillVarsRec( I.coeff(), vars );
366 
367  // multiply them all
368  CanonicalForm result = 1;
369  for ( i = n; i > 0; i-- )
370  if ( vars[i] != 0 ) result *= Variable( i );
371 
372  DELETE_ARRAY(vars);
373  // do not forget our own variable
374  return f.mvar() * result;
375  }
376 }

◆ gf_gf2ff() [1/2]

int gf_gf2ff ( int  a)

Definition at line 231 of file gfops.cc.

232 {
233  if ( gf_iszero( a ) )
234  return 0;
235  else
236  {
237  // starting from z^0=1, step through the table
238  // counting the steps until we hit z^a or z^0
239  // again. since we are working in char(p), the
240  // latter is guaranteed to be fulfilled.
241  int i = 0, ff = 1;
242  do
243  {
244  if ( i == a )
245  return ff;
246  ff++;
247  i = gf_table[i];
248  } while ( i != 0 );
249  return -1;
250  }
251 }
VAR unsigned short * gf_table
Definition: gfops.cc:54
bool gf_iszero(int a)
Definition: gfops.h:43

◆ gf_gf2ff() [2/2]

long gf_gf2ff ( long  a)

Definition at line 209 of file gfops.cc.

210 {
211  if ( gf_iszero( a ) )
212  return 0;
213  else
214  {
215  // starting from z^0=1, step through the table
216  // counting the steps until we hit z^a or z^0
217  // again. since we are working in char(p), the
218  // latter is guaranteed to be fulfilled.
219  long i = 0, ff = 1;
220  do
221  {
222  if ( i == a )
223  return ff;
224  ff++;
225  i = gf_table[i];
226  } while ( i != 0 );
227  return -1;
228  }
229 }

◆ gf_isff() [1/2]

bool gf_isff ( int  a)

Definition at line 264 of file gfops.cc.

265 {
266  if ( gf_iszero( a ) )
267  return true;
268  else
269  {
270  // z^a in GF(p) iff (z^a)^p-1=1
271  return gf_isone( gf_power( a, gf_p - 1 ) );
272  }
273 }
VAR int gf_p
Definition: gfops.cc:48
bool gf_isone(int a)
Definition: gfops.h:53
int gf_power(int a, int n)
Definition: gfops.h:222

◆ gf_isff() [2/2]

bool gf_isff ( long  a)

Definition at line 253 of file gfops.cc.

254 {
255  if ( gf_iszero( a ) )
256  return true;
257  else
258  {
259  // z^a in GF(p) iff (z^a)^p-1=1
260  return gf_isone( gf_power( a, gf_p - 1 ) );
261  }
262 }

◆ gf_value()

int gf_value ( const CanonicalForm f)

Definition at line 60 of file singext.cc.

61 {
62  InternalCF * ff = f.getval();
63  return ((intptr_t)ff) >>2;
64 }
virtual class for internal CanonicalForm's
Definition: int_cf.h:47

◆ gmp_denominator()

void FACTORY_PUBLIC gmp_denominator ( const CanonicalForm f,
mpz_ptr  result 
)

Definition at line 40 of file singext.cc.

41 {
42  InternalCF * ff = f.getval();
43  ASSERT( ! is_imm( ff ), "illegal type" );
44  if ( ff->levelcoeff() == IntegerDomain )
45  {
46  mpz_init_set_si( result, 1 );
47  ff->deleteObject();
48  }
49  else if ( ff->levelcoeff() == RationalDomain )
50  {
51  mpz_init_set( result, (InternalRational::MPQDEN( ff )) );
52  ff->deleteObject();
53  }
54  else
55  {
56  ASSERT( 0, "illegal type" );
57  }
58 }
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:65
#define RationalDomain
Definition: cf_defs.h:20
#define IntegerDomain
Definition: cf_defs.h:21
virtual int levelcoeff() const
Definition: int_cf.h:68
int deleteObject()
Definition: int_cf.h:61
static mpz_ptr MPQDEN(const InternalCF *const c)
Definition: int_rat.h:124

◆ gmp_numerator()

void FACTORY_PUBLIC gmp_numerator ( const CanonicalForm f,
mpz_ptr  result 
)

Definition at line 20 of file singext.cc.

21 {
22  InternalCF * ff = f.getval();
23  ASSERT( ! is_imm( ff ), "illegal type" );
24  if ( ff->levelcoeff() == IntegerDomain )
25  {
26  mpz_init_set( result, (InternalInteger::MPI( ff )) );
27  ff->deleteObject();
28  }
29  else if ( ff->levelcoeff() == RationalDomain )
30  {
31  mpz_init_set( result, (InternalRational::MPQNUM( ff )) );
32  ff->deleteObject();
33  }
34  else
35  {
36  ASSERT( 0, "illegal type" );
37  }
38 }
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ‘c’.
Definition: int_int.h:232
static mpz_ptr MPQNUM(const InternalCF *const c)
Definition: int_rat.h:119

◆ hasFirstAlgVar()

bool hasFirstAlgVar ( const CanonicalForm f,
Variable a 
)

check if poly f contains an algebraic variable a

Definition at line 679 of file cf_ops.cc.

680 {
681  if( f.inBaseDomain() ) // f has NO alg. variable
682  return false;
683  if( f.level()<0 ) // f has only alg. vars, so take the first one
684  {
685  a = f.mvar();
686  return true;
687  }
688  for(CFIterator i=f; i.hasTerms(); i++)
689  if( hasFirstAlgVar( i.coeff(), a ))
690  return true; // 'a' is already set
691  return false;
692 }
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679

◆ hasMipo()

bool hasMipo ( const Variable alpha)

Definition at line 226 of file variable.cc.

227 {
228  ASSERT( alpha.level() < 0, "illegal extension" );
229  return (alpha.level() != LEVELBASE && (algextensions!=NULL) && getReduce(alpha) );
230 }

◆ head()

CanonicalForm head ( const CanonicalForm f)
inline

Definition at line 501 of file factory.h.

502 {
503  if ( f.level() > 0 )
504  return power( f.mvar(), f.degree() ) * f.LC();
505  else
506  return f;
507 }
CanonicalForm FACTORY_PUBLIC power(const CanonicalForm &f, int n)
exponentiation

◆ headdegree()

int headdegree ( const CanonicalForm f)
inline

Definition at line 510 of file factory.h.

510 { return totaldegree( head( f ) ); }
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm head(const CanonicalForm &f)
Definition: factory.h:501

◆ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x 
)

homogenize homogenizes f with Variable x

Definition at line 313 of file cf_factor.cc.

314 {
315 #if 0
316  int maxdeg=totaldegree(f), deg;
317  CFIterator i;
318  CanonicalForm elem, result(0);
319 
320  for (i=f; i.hasTerms(); i++)
321  {
322  elem= i.coeff()*power(f.mvar(),i.exp());
323  deg = totaldegree(elem);
324  if ( deg < maxdeg )
325  result += elem * power(x,maxdeg-deg);
326  else
327  result+=elem;
328  }
329  return result;
330 #else
331  CFList Newlist, Termlist= get_Terms(f);
332  int maxdeg=totaldegree(f), deg;
334  CanonicalForm elem, result(0);
335 
336  for (i=Termlist; i.hasItem(); i++)
337  {
338  elem= i.getItem();
339  deg = totaldegree(elem);
340  if ( deg < maxdeg )
341  Newlist.append(elem * power(x,maxdeg-deg));
342  else
343  Newlist.append(elem);
344  }
345  for (i=Newlist; i.hasItem(); i++) // rebuild
346  result += i.getItem();
347 
348  return result;
349 #endif
350 }
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:289

◆ homogenize() [2/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x,
const Variable v1,
const Variable v2 
)

Definition at line 353 of file cf_factor.cc.

354 {
355 #if 0
356  int maxdeg=totaldegree(f), deg;
357  CFIterator i;
358  CanonicalForm elem, result(0);
359 
360  for (i=f; i.hasTerms(); i++)
361  {
362  elem= i.coeff()*power(f.mvar(),i.exp());
363  deg = totaldegree(elem);
364  if ( deg < maxdeg )
365  result += elem * power(x,maxdeg-deg);
366  else
367  result+=elem;
368  }
369  return result;
370 #else
371  CFList Newlist, Termlist= get_Terms(f);
372  int maxdeg=totaldegree(f), deg;
374  CanonicalForm elem, result(0);
375 
376  for (i=Termlist; i.hasItem(); i++)
377  {
378  elem= i.getItem();
379  deg = totaldegree(elem,v1,v2);
380  if ( deg < maxdeg )
381  Newlist.append(elem * power(x,maxdeg-deg));
382  else
383  Newlist.append(elem);
384  }
385  for (i=Newlist; i.hasItem(); i++) // rebuild
386  result += i.getItem();
387 
388  return result;
389 #endif
390 }

◆ icontent()

CanonicalForm icontent ( const CanonicalForm & f )

icontent() - return gcd over all coefficients of f which are in a coefficient domain.

Definition at line 74 of file cf_gcd.cc.

75 {
76  return icontent( f, 0 );
77 }
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition: cf_gcd.cc:49

◆ igcd()

int igcd ( int  a,
int  b 
)

Definition at line 56 of file cf_util.cc.

57 {
58  if ( a < 0 ) a = -a;
59  if ( b < 0 ) b = -b;
60 
61  int c;
62 
63  while ( b != 0 )
64  {
65  c = a % b;
66  a = b;
67  b = c;
68  }
69  return a;
70 }

◆ ilog2()

int ilog2 ( const CanonicalForm a)
inline

Definition at line 493 of file factory.h.

493 { return a.ilog2(); }

◆ ipower()

int FACTORY_PUBLIC ipower ( int  b,
int  m 
)

int ipower ( int b, int m )

ipower() - calculate b^m in standard integer arithmetic.

Note: Beware of overflows.

Definition at line 27 of file cf_util.cc.

28 {
29  int prod = 1;
30 
31  while ( m != 0 )
32  {
33  if ( m % 2 != 0 )
34  prod *= b;
35  m /= 2;
36  if ( m != 0 )
37  b *= b;
38  }
39  return prod;
40 }

◆ irrCharSeries()

ListCFList FACTORY_PUBLIC irrCharSeries ( const CFList PS)

irreducible characteristic series

Definition at line 568 of file cfCharSets.cc.

569 {
570  CanonicalForm reducible, reducible2;
571  CFList qs, cs, factorset, is, ts, L;
572  CanonicalForm sqrf;
573  CFFList sqrfFactors;
574  CFFListIterator iter2;
575  for (CFListIterator iter= PS; iter.hasItem(); iter++)
576  {
577  sqrf= 1;
578  sqrfFactors= sqrFree (iter.getItem());
579  if (sqrfFactors.getFirst().factor().inCoeffDomain())
580  sqrfFactors.removeFirst();
581  for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
582  sqrf *= iter2.getItem().factor();
583  sqrf= normalize (sqrf);
584  L= Union (CFList (sqrf), L);
585  }
586 
587  ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
588 
589  int nr_of_iteration= 0, indexRed, highestlevel= 0;
590 
591  for (CFListIterator iter= PS; iter.hasItem(); iter++)
592  {
593  if (level (iter.getItem()) > highestlevel)
594  highestlevel= level(iter.getItem());
595  }
596 
597  while (!qhi.isEmpty())
598  {
599  sortListCFList (qhi);
600 
601  qs= qhi.getFirst();
602 
603  ListCFList ppi1,ppi2;
604  select (ppi, qs.length(), ppi1, ppi2);
605 
606  inplaceUnion (ppi2, qqi);
607 
608  if (nr_of_iteration == 0)
609  {
610  nr_of_iteration += 1;
611  ppi= ListCFList();
612  }
613  else
614  {
615  nr_of_iteration += 1;
616  ppi= Union (ppi1, ListCFList (qs));
617  }
618 
619  StoreFactors StoredFactors;
620  if (qs.length() - 3 < highestlevel)
621  cs= modCharSet (qs, StoredFactors, false);
622  else
623  cs= charSetN (qs);
624  cs= removeContent (cs, StoredFactors);
625 
626  factorset= StoredFactors.FS1;
627 
628  if (!cs.isEmpty() && cs.getFirst().level() > 0)
629  {
630  ts= irredAS (cs, indexRed, reducible);
631 
632  if (indexRed <= 0) // irreducible
633  {
634  if (!isSubset (cs,qs))
635  cs= charSetViaCharSetN (Union (qs,cs));
636  if (!find (pi, cs))
637  {
638  pi= Union (ListCFList (cs), pi);
639  if (cs.getFirst().level() > 0)
640  {
641  ts= irredAS (cs, indexRed, reducible);
642 
643  if (indexRed <= 0) //irreducible
644  {
645  qsi= Union (ListCFList(cs), qsi);
646  if (cs.length() == highestlevel)
647  is= factorPSet (factorset);
648  else
649  is= Union (factorsOfInitials (cs), factorPSet (factorset));
650  iss= adjoin (is, qs, qqi);
651  }
652  }
653  else
654  iss= adjoin (factorPSet (factorset), qs, qqi);
655  }
656  else
657  iss= adjoin (factorPSet (factorset), qs, qqi);
658  }
659 
660  if (indexRed > 0)
661  {
662  is= factorPSet (factorset);
663  if (indexRed > 1)
664  {
665  CFList cst;
666  for (CFListIterator i= cs ; i.hasItem(); i++)
667  {
668  if (i.getItem() == reducible)
669  break;
670  else
671  cst.append (i.getItem());
672  }
673  is= Union (factorsOfInitials (Union (cst, CFList (reducible))), is);
674  iss= Union (adjoinb (ts, qs, qqi, cst), adjoin (is, qs, qqi));
675  }
676  else
677  iss= adjoin (Union (is, ts), qs, qqi);
678  }
679  }
680  else
681  iss= adjoin (factorPSet (factorset), qs, qqi);
682  if (qhi.length() > 1)
683  {
684  qhi.removeFirst();
685  qhi= Union (iss, qhi);
686  }
687  else
688  qhi= iss;
689  }
690  if (!qsi.isEmpty())
691  return contract (qsi);
692  return ListCFList(CFList (1)) ;
693 }
void removeContent(CanonicalForm &F, CanonicalForm &cF)
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
ListCFList contract(const ListCFList &cs)
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
Definition: cfCharSets.cc:507
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
#define pi
Definition: libparse.cc:1145

◆ is_imm()

int is_imm ( const InternalCF *const  ptr)
inline

Definition at line 215 of file factory.h.

216 {
217  // returns 0 if ptr is not immediate
218  return ( ((int)((intptr_t)ptr)) & 3 );
219 }

◆ isOn()

bool FACTORY_PUBLIC isOn ( int  sw)

switches

Definition at line 1971 of file canonicalform.cc.

1972 {
1973  return cf_glob_switches.isOn( sw );
1974 }
INST_VAR CFSwitches cf_glob_switches
Definition: cf_switches.cc:54
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 244 of file cf_factor.cc.

245 {
246  if (f.level()<=0) return false;
247  for (CFIterator i=f;i.hasTerms();i++)
248  {
249  if (!(i.coeff().inBaseDomain())) return false;
250  }
251  return true;
252 }

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm f)

Definition at line 234 of file cf_factor.cc.

235 {
236  if (f.inBaseDomain()) return true;
237  if (f.level()<0) return false;
238  for (CFIterator i=f;i.hasTerms();i++)
239  {
240  if (!isPurePoly_m(i.coeff())) return false;
241  }
242  return true;
243 }
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:234

◆ lc()

CanonicalForm lc ( const CanonicalForm f)
inline

Definition at line 445 of file factory.h.

445 { return f.lc(); }

◆ Lc()

CanonicalForm Lc ( const CanonicalForm f)
inline

Definition at line 448 of file factory.h.

448 { return f.Lc(); }

◆ LC() [1/2]

CanonicalForm LC ( const CanonicalForm f)
inline

Definition at line 451 of file factory.h.

451 { return f.LC(); }

◆ LC() [2/2]

CanonicalForm LC ( const CanonicalForm f,
const Variable v 
)
inline

Definition at line 454 of file factory.h.

454 { return f.LC( v ); }

◆ lcm()

CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )

lcm() - return least common multiple of f and g.

The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).

Returns zero if one of f or g equals zero.

Definition at line 763 of file cf_gcd.cc.

764 {
765  if ( f.isZero() || g.isZero() )
766  return 0;
767  else
768  return ( f / gcd( f, g ) ) * g;
769 }

◆ leftShift()

CanonicalForm leftShift ( const CanonicalForm F,
int  n 
)

left shift the main variable of F by n

Returns
if x is the main variable of F the result is F(x^n)

Definition at line 697 of file cf_ops.cc.

698 {
699  ASSERT (n >= 0, "cannot left shift by negative number");
700  if (F.inBaseDomain())
701  return F;
702  if (n == 0)
703  return F;
704  Variable x=F.mvar();
706  for (CFIterator i= F; i.hasTerms(); i++)
707  result += i.coeff()*power (x, i.exp()*n);
708  return result;
709 }
bool inBaseDomain() const

◆ level() [1/2]

int level ( const CanonicalForm f)
inline

Definition at line 472 of file factory.h.

472 { return f.level(); }

◆ level() [2/2]

int level ( const Variable v)
inline

Definition at line 188 of file factory.h.

188 { return v.level(); }

◆ linearSystemSolve()

bool linearSystemSolve ( CFMatrix M)

Definition at line 78 of file cf_linsys.cc.

79 {
80  typedef int* int_ptr;
81 
82  if ( ! matrix_in_Z( M ) ) {
83  int nrows = M.rows(), ncols = M.columns();
84  int i, j, k;
85  CanonicalForm rowpivot, pivotrecip;
86  // triangularization
87  for ( i = 1; i <= nrows; i++ ) {
88  //find "pivot"
89  for (j = i; j <= nrows; j++ )
90  if ( M(j,i) != 0 ) break;
91  if ( j > nrows ) return false;
92  if ( j != i )
93  M.swapRow( i, j );
94  pivotrecip = 1 / M(i,i);
95  for ( j = 1; j <= ncols; j++ )
96  M(i,j) *= pivotrecip;
97  for ( j = i+1; j <= nrows; j++ ) {
98  rowpivot = M(j,i);
99  if ( rowpivot == 0 ) continue;
100  for ( k = i; k <= ncols; k++ )
101  M(j,k) -= M(i,k) * rowpivot;
102  }
103  }
104  // matrix is now upper triangular with 1s down the diagonal
105  // back-substitute
106  for ( i = nrows-1; i > 0; i-- ) {
107  for ( j = nrows+1; j <= ncols; j++ ) {
108  for ( k = i+1; k <= nrows; k++ )
109  M(i,j) -= M(k,j) * M(i,k);
110  }
111  }
112  return true;
113  }
114  else {
115  int rows = M.rows(), cols = M.columns();
116  CFMatrix MM( rows, cols );
117  int ** mm = new int_ptr[rows];
118  CanonicalForm Q, Qhalf, mnew, qnew, B;
119  int i, j, p, pno;
120  bool ok;
121 
122  // initialize room to hold the result and the result mod p
123  for ( i = 0; i < rows; i++ ) {
124  mm[i] = new int[cols];
125  }
126 
127  // calculate the bound for the result
128  B = bound( M );
129  DEBOUTLN( cerr, "bound = " << B );
130 
131  // find a first solution mod p
132  pno = 0;
133  do {
134  DEBOUTSL( cerr );
135  DEBOUT( cerr, "trying prime(" << pno << ") = " );
136  p = cf_getBigPrime( pno );
137  DEBOUT( cerr, p );
138  DEBOUTENDL( cerr );
139  setCharacteristic( p );
140  // map matrix into char p
141  for ( i = 1; i <= rows; i++ )
142  for ( j = 1; j <= cols; j++ )
143  mm[i-1][j-1] = mapinto( M(i,j) ).intval();
144  // solve mod p
145  ok = solve( mm, rows, cols );
146  pno++;
147  } while ( ! ok );
148 
149  // initialize the result matrix with first solution
150  setCharacteristic( 0 );
151  for ( i = 1; i <= rows; i++ )
152  for ( j = rows+1; j <= cols; j++ )
153  MM(i,j) = mm[i-1][j-1];
154 
155  // Q so far
156  Q = p;
157  while ( Q < B && pno < cf_getNumBigPrimes() ) {
158  do {
159  DEBOUTSL( cerr );
160  DEBOUT( cerr, "trying prime(" << pno << ") = " );
161  p = cf_getBigPrime( pno );
162  DEBOUT( cerr, p );
163  DEBOUTENDL( cerr );
164  setCharacteristic( p );
165  for ( i = 1; i <= rows; i++ )
166  for ( j = 1; j <= cols; j++ )
167  mm[i-1][j-1] = mapinto( M(i,j) ).intval();
168  // solve mod p
169  ok = solve( mm, rows, cols );
170  pno++;
171  } while ( ! ok );
172  // found a solution mod p
173  // now chinese remainder it to a solution mod Q*p
174  setCharacteristic( 0 );
175  for ( i = 1; i <= rows; i++ )
176  for ( j = rows+1; j <= cols; j++ )
177  {
178  chineseRemainder( MM[i][j], Q, CanonicalForm(mm[i-1][j-1]), CanonicalForm(p), mnew, qnew );
179  MM(i, j) = mnew;
180  }
181  Q = qnew;
182  }
183  if ( pno == cf_getNumBigPrimes() )
184  fuzzy_result = true;
185  else
186  fuzzy_result = false;
187  // store the result in M
188  Qhalf = Q / 2;
189  for ( i = 1; i <= rows; i++ ) {
190  for ( j = rows+1; j <= cols; j++ )
191  if ( MM(i,j) > Qhalf )
192  M(i,j) = MM(i,j) - Q;
193  else
194  M(i,j) = MM(i,j);
195  delete [] mm[i-1];
196  }
197  delete [] mm;
198  return ! fuzzy_result;
199  }
200 }
CanonicalForm mapinto(const CanonicalForm &f)
int int ncols
Definition: cf_linsys.cc:32
VAR bool fuzzy_result
Definition: cf_linsys.cc:75
int nrows
Definition: cf_linsys.cc:32
bool solve(int **extmat, int nrows, int ncols)
Definition: cf_linsys.cc:504
long intval() const
conversion functions
#define DEBOUTENDL(stream)
Definition: debug.h:48
#define DEBOUTSL(stream)
Definition: debug.h:46

◆ make_cf() [1/2]

CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr  n)

Definition at line 66 of file singext.cc.

67 {
68  return CanonicalForm( CFFactory::basic( n ) );
69 }
static InternalCF * basic(int value)
Definition: cf_factory.cc:61

◆ make_cf() [2/2]

CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr  n,
const mpz_ptr  d,
bool  normalize 
)

Definition at line 71 of file singext.cc.

72 {
73  return CanonicalForm( CFFactory::rational( n, d, normalize ) );
74 }
static InternalCF * rational(long num, long den)
Definition: cf_factory.cc:268

◆ make_cf_from_gf()

CanonicalForm make_cf_from_gf ( const int  z)

Definition at line 76 of file singext.cc.

77 {
78  return CanonicalForm(int2imm_gf(z));
79 }

◆ mapdomain()

CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )

mapdomain() - map all coefficients of f through mf.

Recursively descends down through f to the coefficients which are in a coefficient domain mapping each such coefficient through mf and returns the result.

Definition at line 440 of file cf_ops.cc.

441 {
442  if ( f.inBaseDomain() )
443  return mf( f );
444  else
445  {
446  CanonicalForm result = 0;
447  CFIterator i;
448  Variable x = f.mvar();
449  for ( i = f; i.hasTerms(); i++ )
450  result += power( x, i.exp() ) * mapdomain( i.coeff(), mf );
451  return result;
452  }
453 }
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
Definition: cf_ops.cc:440

◆ mapinto()

CanonicalForm mapinto ( const CanonicalForm f)
inline

Definition at line 496 of file factory.h.

496 { return f.mapinto(); }

◆ maxNorm()

CanonicalForm maxNorm ( const CanonicalForm f)

CanonicalForm maxNorm ( const CanonicalForm & f )

maxNorm() - return maximum norm of ‘f’.

That is, the base coefficient of ‘f’ with the largest absolute value.

Valid for arbitrary polynomials over arbitrary domains, but most useful for multivariate polynomials over Z.

Type info:

f: CurrentPP

Definition at line 536 of file cf_algorithm.cc.

537 {
538  if ( f.inBaseDomain() )
539  return abs( f );
540  else {
541  CanonicalForm result = 0;
542  for ( CFIterator i = f; i.hasTerms(); i++ ) {
543  CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
544  if ( coeffMaxNorm > result )
545  result = coeffMaxNorm;
546  }
547  return result;
548  }
549 }
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )

◆ mod()

◆ modCharSet() [1/2]

CFList modCharSet ( const CFList PS,
bool  removeContents 
)

Definition at line 404 of file cfCharSets.cc.

405 {
406  StoreFactors tmp;
407  return modCharSet (PS, tmp, removeContents);
408 }

◆ modCharSet() [2/2]

CFList modCharSet ( const CFList PS,
StoreFactors StoredFactors,
bool  removeContents = true 
)

modified medial set

Definition at line 284 of file cfCharSets.cc.

285 {
286  CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
288  CanonicalForm r, cF;
289  bool noRemainder= true;
290  StoreFactors StoredFactors2;
291 
292  QS= uniGcd (L);
293 
294  while (!RS.isEmpty())
295  {
296  noRemainder= true;
297  CSet= basicSet (QS);
298 
299  initial= factorsOfInitials (CSet);
300 
301  StoredFactors2.FS1= StoredFactors.FS1;
302  StoredFactors2.FS2= Union (StoredFactors2.FS2, initial);
303 
304  RS= CFList();
305 
306  if (CSet.length() > 0 && CSet.getFirst().level() > 0)
307  {
308  tmp= Difference (QS, CSet);
309 
310  for (i= tmp; i.hasItem(); i++)
311  {
312  r= Prem (i.getItem(), CSet);
313  if (!r.isZero())
314  {
315  noRemainder= false;
316  if (removeContents)
317  {
318  removeContent (r, cF);
319 
320  if (!cF.isZero())
321  contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead
322  }
323 
324  removeFactors (r, StoredFactors2, removedFactors);
325  StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors);
326  StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors);
327 
328  removedFactors= CFList();
329 
330  RS= Union (RS, CFList (r));
331  }
332  }
333 
334  if (removeContents && !noRemainder)
335  {
336  StoredFactors.FS1= Union (StoredFactors2.FS1, contents);
337  StoredFactors.FS2= StoredFactors2.FS2;
338  }
339  else
340  StoredFactors= StoredFactors2;
341 
342  QS= Union (CSet, RS);
343 
344  contents= CFList();
345  removedFactors= CFList();
346  }
347  else
348  StoredFactors= StoredFactors2;
349  }
350 
351  return CSet;
352 }
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
Definition: initial.cc:30

◆ mvar()

Variable mvar ( const CanonicalForm f)
inline

Definition at line 475 of file factory.h.

475 { return f.mvar(); }

◆ name()

char name ( const Variable v)
inline

Definition at line 189 of file factory.h.

189 { return v.name(); }
char name() const
Definition: variable.cc:122

◆ neworder()

Varlist neworder ( const CFList PolyList)

◆ newordercf()

CFList newordercf ( const CFList PolyList)

Definition at line 75 of file cfCharSets.cc.

76 {
77  Varlist reorder= neworder (PolyList);
78  CFList output;
79 
80  for (VarlistIterator i=reorder; i.hasItem(); i++)
81  output.append (CanonicalForm (i.getItem()));
82 
83  return output;
84 }
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition: cfCharSets.cc:101
Varlist neworder(const CFList &PolyList)

◆ neworderint()

IntList FACTORY_PUBLIC neworderint ( const CFList PolyList)

Definition at line 88 of file cfCharSets.cc.

89 {
90  Varlist reorder= neworder (PolyList);
91  IntList output;
92 
93  for (VarlistIterator i= reorder; i.hasItem(); i++)
94  output.append (level (i.getItem()));
95 
96  return output;
97 }

◆ num()

CanonicalForm num ( const CanonicalForm f)
inline

Definition at line 478 of file factory.h.

478 { return f.num(); }

◆ Off()

void FACTORY_PUBLIC Off ( int  sw)

switches

Definition at line 1964 of file canonicalform.cc.

1965 {
1966  cf_glob_switches.Off( sw );
1967 }
void Off(int s)
switch 's' off
Definition: cf_switches.h:53

◆ On()

void FACTORY_PUBLIC On ( int  sw)

switches

Definition at line 1957 of file canonicalform.cc.

1958 {
1959  cf_glob_switches.On( sw );
1960 }
void On(int s)
switch 's' on
Definition: cf_switches.h:51

◆ operator%()

◆ operator*()

CF_INLINE CanonicalForm operator* ( const CanonicalForm lhs,
const CanonicalForm rhs 
)
See also
CanonicalForm::operator *=()

Definition at line 524 of file cf_inline.cc.

525 {
526  CanonicalForm result( lhs );
527  result *= rhs;
528  return result;
529 }

◆ operator+()

CF_INLINE CanonicalForm operator+ ( const CanonicalForm lhs,
const CanonicalForm rhs 
)

CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs )

operators +, -, *, /, %(), div(), mod() - binary arithmetic operators.

The binary operators have their standard (mathematical) semantics. As explained for the corresponding arithmetic assignment operators, the operators ‘/’ and ‘%’ return the quotient resp. remainder of (polynomial) division with remainder, whereas ‘div()’ and ‘mod()’ may be used for exact division and term-wise remaindering, resp.

It is faster to use the arithmetic assignment operators (e.g., ‘f += g;’) instead of the binary operators (‘f = f+g;’ ).

Type info:

lhs, rhs: CurrentPP

There are weaker preconditions for some cases (e.g., arithmetic operations with elements from Q or Z work in any domain), but type ‘CurrentPP’ is the only one guaranteed to work for all cases.

Developers note:

All binary operators have their corresponding ‘CanonicalForm’ assignment operators (e.g., ‘operator +()’ corresponds to ‘CanonicalForm::operator +=()’, ‘div()’ corresponds to `CanonicalFormdiv()).

And that is how they are implemented, too: Each of the binary operators first creates a copy of ‘lhs’, adds ‘rhs’ to this copy using the assignment operator, and returns the result.

See also
CanonicalForm::operator +=()

Definition at line 503 of file cf_inline.cc.

504 {
505  CanonicalForm result( lhs );
506  result += rhs;
507  return result;
508 }

◆ operator-()

◆ operator/()

◆ power() [1/2]

CanonicalForm FACTORY_PUBLIC power ( const CanonicalForm f,
int  n 
)

exponentiation

Definition at line 1896 of file canonicalform.cc.

1897 {
1898  ASSERT( n >= 0, "illegal exponent" );
1899  if ( f.isZero() )
1900  return CanonicalForm(0L);
1901  else if ( f.isOne() )
1902  return f;
1903  else if ( f == -1 )
1904  {
1905  if ( n % 2 == 0 )
1906  return CanonicalForm(1L);
1907  else
1908  return CanonicalForm(-1L);
1909  }
1910  else if ( n == 0 )
1911  return CanonicalForm(1L);
1912 
1913  //else if (f.inGF())
1914  //{
1915  //}
1916  else
1917  {
1918  CanonicalForm g,h;
1919  h=f;
1920  while(n%2==0)
1921  {
1922  h*=h;
1923  n/=2;
1924  }
1925  g=h;
1926  while(1)
1927  {
1928  n/=2;
1929  if(n==0)
1930  return g;
1931  h*=h;
1932  if(n%2!=0) g*=h;
1933  }
1934  }
1935 }
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ power() [2/2]

CanonicalForm FACTORY_PUBLIC power ( const Variable v,
int  n 
)

exponentiation

Definition at line 1939 of file canonicalform.cc.

1940 {
1941  //ASSERT( n >= 0, "illegal exponent" );
1942  if ( n == 0 )
1943  return 1;
1944  else if ( n == 1 )
1945  return v;
1946  else if (( v.level() < 0 ) && (hasMipo(v)))
1947  {
1948  CanonicalForm result( v, n-1 );
1949  return result * v;
1950  }
1951  else
1952  return CanonicalForm( v, n );
1953 }
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226

◆ pp()

CanonicalForm pp ( const CanonicalForm & f )

pp() - return primitive part of f.

Returns zero if f equals zero, otherwise f / content(f).

Definition at line 676 of file cf_gcd.cc.

677 {
678  if ( f.isZero() )
679  return f;
680  else
681  return f / content( f );
682 }

◆ Prem()

pseudo remainder of F by G with certain factors of LC (g) cancelled

Definition at line 616 of file cfCharSetsUtil.cc.

617 {
618  CanonicalForm f, g, l, test, lu, lv, t, retvalue;
619  int degF, degG, levelF, levelG;
620  bool reord;
621  Variable v, vg= G.mvar();
622 
623  if ( (levelF= F.level()) < (levelG= G.level()))
624  return F;
625  else
626  {
627  if ( levelF == levelG )
628  {
629  f= F;
630  g= G;
631  reord= false;
632  v= F.mvar();
633  }
634  else
635  {
636  v= Variable (levelF + 1);
637  f= swapvar (F, vg, v);
638  g= swapvar (G, vg, v);
639  reord= true;
640  }
641  degG= degree (g, v );
642  degF= degree (f, v );
643  if (degG <= degF)
644  {
645  l= LC (g);
646  g= g - l*power (v, degG);
647  }
648  else
649  l= 1;
650  while ((degG <= degF) && (!f.isZero()))
651  {
652  test= gcd (l, LC(f));
653  lu= l / test;
654  lv= LC(f) / test;
655  t= g*lv*power (v, degF - degG);
656 
657  if (degF == 0)
658  f= 0;
659  else
660  f= f - LC (f)*power (v, degF);
661 
662  f= f*lu - t;
663  degF= degree (f, v);
664  }
665 
666  if (reord)
667  retvalue= swapvar (f, vg, v);
668  else
669  retvalue= f;
670 
671  return retvalue;
672  }
673 }
CanonicalForm LC(const CanonicalForm &f)
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
CanonicalForm test
Definition: cfModGcd.cc:4096
static CanonicalForm * retvalue
Definition: readcf.cc:126
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ probIrredTest()

int FACTORY_PUBLIC probIrredTest ( const CanonicalForm F,
double  error 
)

given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error

Returns
probIrredTest returns 1 for irreducibility, -1 for reducibility or 0 if the test is not applicable
Parameters
[in]Fsome poly over Z/p
[in]error0 < error < 1

Definition at line 63 of file facIrredTest.cc.

64 {
65  CFMap N;
66  CanonicalForm G= compress (F, N);
67  int n= G.level();
68  int p= getCharacteristic();
69 
70  double sqrtTrials= inverseERF (1-2.0*error)*sqrt (2.0);
71 
72  double s= sqrtTrials;
73 
74  double pn= pow ((double) p, (double) n);
75  double p1= (double) 1/p;
76  p1= p1*(1.0-p1);
77  p1= p1/(double) pn;
78  p1= sqrt (p1);
79  p1 *= s;
80  p1 += (double) 1/p;
81 
82  double p2= (double) (2*p-1)/(p*p);
83  p2= p2*(1-p2);
84  p2= p2/(double) pn;
85  p2= sqrt (p2);
86  p2 *= s;
87  p2= (double) (2*p - 1)/(p*p)-p2;
88 
89  //no testing possible
90  if (p2 < p1)
91  return 0;
92 
93  double den= sqrt (p1*(1-p1))+sqrt (p2*(1-p2));
94  double num= p2-p1;
95 
96  sqrtTrials *= den/num;
97 
98  int trials= (int) floor (pow (sqrtTrials, 2.0));
99 
100  double experimentalNumZeros= numZeros (G, trials);
101 
102  double pmiddle= sqrt (p1*p2);
103 
104  num= den;
105  den= sqrt (p1*(1.0-p2))+sqrt (p2*(1.0-p1));
106  pmiddle *= (den/num);
107 
108  if (experimentalNumZeros < pmiddle)
109  return 1;
110  else
111  return -1;
112 }
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:411
void error(const char *fmt,...)
Definition: emacs.cc:55
double numZeros(const CanonicalForm &F, int k)
evaluate F at k random points in Z/p^n and count the number of zeros that occur
Definition: facIrredTest.cc:24
double inverseERF(double d)
Definition: facIrredTest.cc:42
const signed long floor(const ampf< Precision > &x)
Definition: amp.h:773

◆ prune()

void FACTORY_PUBLIC prune ( Variable alpha)

Definition at line 261 of file variable.cc.

262 {
263  if (alpha.level()==LEVELBASE) return;
264  int last_var=-alpha.level();
265  if ((last_var <= 0)||(var_names_ext==NULL)) return;
266  int i, n = strlen( var_names_ext );
267  ASSERT (n+1 >= last_var, "wrong variable");
268  if (last_var == 1)
269  {
270  delete [] var_names_ext;
271  delete [] algextensions;
272  var_names_ext= 0;
273  algextensions= 0;
274  alpha= Variable();
275  return;
276  }
277  char * newvarnames = new char [last_var+1];
278  for ( i = 0; i < last_var; i++ )
279  newvarnames[i] = var_names_ext[i];
280  newvarnames[last_var] = 0;
281  delete [] var_names_ext;
282  var_names_ext = newvarnames;
283  ext_entry * newalgext = new ext_entry [last_var];
284  for ( i = 0; i < last_var; i++ )
285  newalgext[i] = algextensions[i];
286  delete [] algextensions;
287  algextensions = newalgext;
288  alpha= Variable();
289 }
Definition: variable.cc:19

◆ prune1()

void prune1 ( const Variable alpha)

Definition at line 291 of file variable.cc.

292 {
293  int i, n = strlen( var_names_ext );
294  ASSERT (n+1 >= -alpha.level(), "wrong variable");
295 
296  char * newvarnames = new char [-alpha.level() + 2];
297  for ( i = 0; i <= -alpha.level(); i++ )
298  newvarnames[i] = var_names_ext[i];
299  newvarnames[-alpha.level()+1] = 0;
300  delete [] var_names_ext;
301  var_names_ext = newvarnames;
302  ext_entry * newalgext = new ext_entry [-alpha.level()+1];
303  for ( i = 0; i <= -alpha.level(); i++ )
304  newalgext[i] = algextensions[i];
305  delete [] algextensions;
306  algextensions = newalgext;
307 }

◆ psq()

CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

psq() - return pseudo quotient of ‘f’ and ‘g’ with respect to ‘x’.

‘g’ must not equal zero.

Type info:

f, g: Current x: Polynomial

Developers note:

This is not an optimal implementation. Better would have been an implementation in ‘InternalPoly’ avoiding the exponentiation of the leading coefficient of ‘g’. It seemed not worth to do so.

See also
psr(), psqr()

Definition at line 172 of file cf_algorithm.cc.

173 {
174  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
175  ASSERT( ! g.isZero(), "math error: division by zero" );
176 
177  // swap variables such that x's level is larger or equal
178  // than both f's and g's levels.
179  Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
180  CanonicalForm F = swapvar( f, x, X );
181  CanonicalForm G = swapvar( g, x, X );
182 
183  // now, we have to calculate the pseudo remainder of F and G
184  // w.r.t. X
185  int fDegree = degree( F, X );
186  int gDegree = degree( G, X );
187  if ( fDegree < 0 || fDegree < gDegree )
188  return 0;
189  else {
190  CanonicalForm result = (power( LC( G, X ), fDegree-gDegree+1 ) * F) / G;
191  return swapvar( result, x, X );
192  }
193 }

◆ psqr()

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, const Variable & x )

psqr() - calculate pseudo quotient and remainder of ‘f’ and ‘g’ with respect to ‘x’.

Returns the pseudo quotient of ‘f’ and ‘g’ in ‘q’, the pseudo remainder in ‘r’. ‘g’ must not equal zero.

See ‘psr()’ for more detailed information.

Type info:

f, g: Current q, r: Anything x: Polynomial

Developers note:

This is not an optimal implementation. Better would have been an implementation in ‘InternalPoly’ avoiding the exponentiation of the leading coefficient of ‘g’. It seemed not worth to do so.

See also
psr(), psq()

Definition at line 223 of file cf_algorithm.cc.

224 {
225  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
226  ASSERT( ! g.isZero(), "math error: division by zero" );
227 
228  // swap variables such that x's level is larger or equal
229  // than both f's and g's levels.
230  Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
231  CanonicalForm F = swapvar( f, x, X );
232  CanonicalForm G = swapvar( g, x, X );
233 
234  // now, we have to calculate the pseudo remainder of F and G
235  // w.r.t. X
236  int fDegree = degree( F, X );
237  int gDegree = degree( G, X );
238  if ( fDegree < 0 || fDegree < gDegree ) {
239  q = 0; r = f;
240  } else {
241  divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r );
242  q = swapvar( q, x, X );
243  r = swapvar( r, x, X );
244  }
245 }

◆ psr()

CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

psr() - return pseudo remainder of ‘f’ and ‘g’ with respect to ‘x’.

‘g’ must not equal zero.

For f and g in R[x], R an arbitrary ring, g != 0, there is a representation

LC(g)^s*f = g*q + r

with r = 0 or deg(r) < deg(g) and s = 0 if f = 0 or s = max( 0, deg(f)-deg(g)+1 ) otherwise. r = psr(f, g) and q = psq(f, g) are called "pseudo remainder" and "pseudo quotient", resp. They are uniquely determined if LC(g) is not a zero divisor in R.

See H.-J. Reiffen/G. Scheja/U. Vetter - "Algebra", 2nd ed., par. 15, for a reference.

Type info:

f, g: Current x: Polynomial

Polynomials over prime power domains are admissible if lc(LC(‘g’,‘x’)) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since pseudo remainder and quotient are well-defined if LC(‘g’,‘x’) is not a zero divisor.

For example, psr(y^2, (13*x+1)*y) is well-defined in (Z/13^2[x])[y] since (13*x+1) is not a zero divisor. But calculating it with Factory would fail since 13 is a zero divisor in Z/13^2.

Due to this inconsistency with mathematical notion, we decided not to declare type ‘CurrentPP’ for ‘f’ and ‘g’.

Developers note:

This is not an optimal implementation. Better would have been an implementation in ‘InternalPoly’ avoiding the exponentiation of the leading coefficient of ‘g’. In contrast to ‘psq()’ and ‘psqr()’ it definitely seems worth to implement the pseudo remainder on the internal level.

See also
psq(), psqr()

Definition at line 117 of file cf_algorithm.cc.

118 {
119  CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue;
120  int dr, dv, d,n=0;
121 
122 
123  dr = degree( r, x );
124  if (dr>0)
125  {
126  dv = degree( v, x );
127  if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);}
128  else { l = 1; }
129  d= dr-dv+1;
130  //out_cf("psr(",rr," ");
131  //out_cf("",vv," ");
132  //printf(" var=%d\n",x.level());
133  while ( ( dv <= dr ) && ( !r.isZero()) )
134  {
135  test = power(x,dr-dv)*v*LC(r,x);
136  if ( dr == 0 ) { r= CanonicalForm(0); }
137  else { r= r - LC(r,x)*power(x,dr); }
138  r= l*r -test;
139  dr= degree(r,x);
140  n+=1;
141  }
142  r= power(l, d-n)*r;
143  }
144  return r;
145 }

◆ reduce()

polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M

Definition at line 660 of file cf_ops.cc.

661 {
662  if(f.inBaseDomain() || f.level() < M.level())
663  return f;
664  if(f.level() == M.level())
665  {
666  if(f.degree() < M.degree())
667  return f;
668  CanonicalForm tmp = mod (f, M);
669  return tmp;
670  }
671  // here: f.level() > M.level()
672  CanonicalForm result = 0;
673  for(CFIterator i=f; i.hasTerms(); i++)
674  result += reduce(i.coeff(),M) * power(f.mvar(),i.exp());
675  return result;
676 }
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

◆ reorder() [1/3]

CFFList reorder ( const Varlist betterorder,
const CFFList PS 
)

Definition at line 120 of file cfCharSets.cc.

121 {
122  int i= 1, n= betterorder.length();
123  Intarray v (1, n);
124  CFFList ps= PS;
125 
126  //initalize:
127  for (VarlistIterator j= betterorder; j.hasItem(); j++)
128  {
129  v[i]= level (j.getItem());
130  i++;
131  }
132 
133  // reorder:
134  for (i= 1; i <= n; i++)
135  ps= swapvar (ps, Variable (v[i]), Variable (n + i));
136  return ps;
137 }

◆ reorder() [2/3]

CFList reorder ( const Varlist betterorder,
const CFList PS 
)

Definition at line 101 of file cfCharSets.cc.

102 {
103  int i= 1, n= betterorder.length();
104  Intarray v (1, n);
105  CFList ps= PS;
106 
107  //initalize:
108  for (VarlistIterator j= betterorder; j.hasItem(); j++)
109  {
110  v[i]= level (j.getItem());
111  i++;
112  }
113  // reorder:
114  for (i= 1; i <= n; i++)
115  ps= swapvar (ps, Variable (v[i]), Variable (n + i));
116  return ps;
117 }

◆ reorder() [3/3]

ListCFList reorder ( const Varlist betterorder,
const ListCFList Q 
)

Definition at line 140 of file cfCharSets.cc.

141 {
142  ListCFList Q1;
143 
144  for (ListCFListIterator i= Q; i.hasItem(); i++)
145  Q1.append (reorder (betterorder, i.getItem()));
146  return Q1;
147 }

◆ replaceLc()

CanonicalForm replaceLc ( const CanonicalForm f,
const CanonicalForm c 
)

Definition at line 90 of file fac_util.cc.

91 {
92  if ( f.inCoeffDomain() )
93  return c;
94  else
95  return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
96 }

◆ replacevar()

CanonicalForm FACTORY_PUBLIC replacevar ( const CanonicalForm f,
const Variable x1,
const Variable x2 
)

CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )

replacevar() - replace all occurences of x1 in f by x2.

In contrast to swapvar(), x1 may be an algebraic variable, but x2 must be a polynomial variable.

Definition at line 271 of file cf_ops.cc.

272 {
273  //ASSERT( x2.level() > 0, "cannot replace with algebraic variable" );
274  if ( f.inBaseDomain() || x1 == x2 || ( x1 > f.mvar() ) )
275  return f;
276  else
277  {
278  sv_x1 = x1;
279  sv_x2 = x2;
280  return replacevar_between( f );
281  }
282 }
STATIC_INST_VAR Variable sv_x2
Definition: cf_ops.cc:43
static CanonicalForm replacevar_between(const CanonicalForm &f)
replacevar_between() - replace occurences of sv_x1 in f with sv_x2.
Definition: cf_ops.cc:233
STATIC_INST_VAR Variable sv_x1
static Variable sv_x1, sv_x2;
Definition: cf_ops.cc:43

◆ resultant()

CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

resultant() - return resultant of f and g with respect to x.

The chain is calculated from f and g with respect to variable x which should not be an algebraic variable. If f or q equals zero, zero is returned. If f is a coefficient with respect to x, f^degree(g, x) is returned, analogously for g.

This algorithm serves as a wrapper around other resultant algorithms which do the real work. Here we use standard properties of resultants only.

Definition at line 173 of file cf_resultant.cc.

174 {
175  ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
176 
177  // some checks on triviality. We will not use degree( v )
178  // here because this may involve variable swapping.
179  if ( f.isZero() || g.isZero() )
180  return 0;
181  if ( f.mvar() < x )
182  return power( f, g.degree( x ) );
183  if ( g.mvar() < x )
184  return power( g, f.degree( x ) );
185 
186  // make x main variale
187  CanonicalForm F, G;
188  Variable X;
189  if ( f.mvar() > x || g.mvar() > x ) {
190  if ( f.mvar() > g.mvar() )
191  X = f.mvar();
192  else
193  X = g.mvar();
194  F = swapvar( f, X, x );
195  G = swapvar( g, X, x );
196  }
197  else {
198  X = x;
199  F = f;
200  G = g;
201  }
202  // at this point, we have to calculate resultant( F, G, X )
203  // where X is equal to or greater than the main variables
204  // of F and G
205 
206  int m = degree( F, X );
207  int n = degree( G, X );
208  // catch trivial cases
209  if ( m+n <= 2 || m == 0 || n == 0 )
210  return swapvar( trivialResultant( F, G, X ), X, x );
211 
212  // exchange F and G if necessary
213  int flipFactor;
214  if ( m < n ) {
215  CanonicalForm swap = F;
216  F = G; G = swap;
217  int degswap = m;
218  m = n; n = degswap;
219  if ( m & 1 && n & 1 )
220  flipFactor = -1;
221  else
222  flipFactor = 1;
223  } else
224  flipFactor = 1;
225 
226  // this is not an effective way to calculate the resultant!
227  CanonicalForm extFactor;
228  if ( m == n ) {
229  if ( n & 1 )
230  extFactor = -LC( G, X );
231  else
232  extFactor = LC( G, X );
233  } else
234  extFactor = power( LC( F, X ), m-n-1 );
235 
237  result = subResChain( F, G, X )[0] / extFactor;
238 
239  return swapvar( result, X, x ) * flipFactor;
240 }
#define swap(_i, _j)
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
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g,...

◆ resultantZ()

CanonicalForm resultantZ ( const CanonicalForm A,
const CanonicalForm B,
const Variable x,
bool  prob = true 
)

modular resultant algorihtm over Z

Returns
resultantZ returns the resultant of A and B wrt. x
Parameters
[in]Asome poly
[in]Bsome poly
[in]xsome polynomial variable
[in]probif true use probabilistic algorithm

Definition at line 559 of file cfModResultant.cc.

561 {
562  ASSERT (getCharacteristic() == 0, "characteristic > 0 expected");
563 #ifndef NOASSERT
564  bool isRat= isOn (SW_RATIONAL);
565  On (SW_RATIONAL);
566  ASSERT (bCommonDen (A).isOne(), "input A is rational");
567  ASSERT (bCommonDen (B).isOne(), "input B is rational");
568  if (!isRat)
569  Off (SW_RATIONAL);
570 #endif
571 
572  int degAx= degree (A, x);
573  int degBx= degree (B, x);
574  if (A.level() < x.level())
575  return power (A, degBx);
576  if (B.level() < x.level())
577  return power (B, degAx);
578 
579  if (degAx == 0)
580  return power (A, degBx);
581  else if (degBx == 0)
582  return power (B, degAx);
583 
584  CanonicalForm F= A;
585  CanonicalForm G= B;
586 
587  Variable X= x;
588  if (F.level() != x.level() || G.level() != x.level())
589  {
590  if (F.level() > G.level())
591  X= F.mvar();
592  else
593  X= G.mvar();
594  F= swapvar (F, X, x);
595  G= swapvar (G, X, x);
596  }
597 
598  // now X is the main variable
599 
600  CanonicalForm d= 0;
601  CanonicalForm dd= 0;
603  for (CFIterator i= F; i.hasTerms(); i++)
604  {
605  buf= oneNorm (i.coeff());
606  d= (buf > d) ? buf : d;
607  }
608  CanonicalForm e= 0, ee= 0;
609  for (CFIterator i= G; i.hasTerms(); i++)
610  {
611  buf= oneNorm (i.coeff());
612  e= (buf > e) ? buf : e;
613  }
614  d= power (d, degBx);
615  e= power (e, degAx);
616  CanonicalForm bound= 1;
617  for (int i= degBx + degAx; i > 1; i--)
618  bound *= i;
619  bound *= d*e;
620  bound *= 2;
621 
622  bool onRational= isOn (SW_RATIONAL);
623  if (onRational)
624  Off (SW_RATIONAL);
625  int i = cf_getNumBigPrimes() - 1;
626  int p;
627  CanonicalForm l= lc (F)*lc(G);
628  CanonicalForm resultModP, q (0), newResult, newQ;
630  int equalCount= 0;
631  CanonicalForm test, newTest;
632  int count= 0;
633  do
634  {
635  p = cf_getBigPrime( i );
636  i--;
637  while ( i >= 0 && mod( l, p ) == 0)
638  {
639  p = cf_getBigPrime( i );
640  i--;
641  }
642 
643  if (i <= 0)
644  return resultant (A, B, x);
645 
647 
648  TIMING_START (fac_resultant_p);
649  resultModP= resultantFp (mapinto (F), mapinto (G), X, prob);
650  TIMING_END_AND_PRINT (fac_resultant_p, "time to compute resultant mod p: ");
651 
652  setCharacteristic (0);
653 
654  count++;
655  if ( q.isZero() )
656  {
657  result= mapinto(resultModP);
658  q= p;
659  }
660  else
661  {
662  chineseRemainder( result, q, mapinto (resultModP), p, newResult, newQ );
663  q= newQ;
664  result= newResult;
666  if (test != newTest)
667  {
668  newTest= test;
669  equalCount= 0;
670  }
671  else
672  equalCount++;
673  if (newQ > bound || (prob && equalCount == 2))
674  {
675  result= test;
676  break;
677  }
678  }
679  } while (1);
680 
681  if (onRational)
682  On (SW_RATIONAL);
683  return swapvar (result, X, x);
684 }
CanonicalForm lc(const CanonicalForm &f)
static CanonicalForm oneNorm(const CanonicalForm &F)
const CanonicalForm CFMap CFMap const Variable & x
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
const CanonicalForm & G
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
int status int void * buf
Definition: si_signals.h:59

◆ rootOf()

Variable FACTORY_PUBLIC rootOf ( const CanonicalForm mipo,
char  name 
)

returns a symbolic root of polynomial with name name Use it to define algebraic variables

returns a symbolic root of polynomial with name name.

Note
: algebraic variables have a level < 0

Use it to define algebraic variables

Note
: algebraic variables have a level < 0
: algebraic variables have a level < 0

Definition at line 162 of file variable.cc.

163 {
164  ASSERT (mipo.isUnivariate(), "not a legal extension");
165 
166  int l;
167  if ( var_names_ext == 0 ) {
168  var_names_ext = new char [3];
169  var_names_ext[0] = '@';
170  var_names_ext[1] = name;
171  var_names_ext[2] = '\0';
172  l = 1;
173  Variable result( -l, true );
174  algextensions = new ext_entry [2];
175  algextensions[1] = ext_entry( 0, false );
176  algextensions[1] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
177  return result;
178  }
179  else {
180  int i, n = strlen( var_names_ext );
181  char * newvarnames = new char [n+2];
182  for ( i = 0; i < n; i++ )
183  newvarnames[i] = var_names_ext[i];
184  newvarnames[n] = name;
185  newvarnames[n+1] = 0;
186  delete [] var_names_ext;
187  var_names_ext = newvarnames;
188  l = n;
189  Variable result( -l, true );
190  ext_entry * newalgext = new ext_entry [n+1];
191  for ( i = 0; i < n; i++ )
192  newalgext[i] = algextensions[i];
193  newalgext[n] = ext_entry( 0, false );
194  delete [] algextensions;
195  algextensions = newalgext;
196  algextensions[n] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
197  return result;
198  }
199 }
bool isUnivariate() const
factory's class for polynomials
Definition: int_poly.h:71
CanonicalForm mipo
Definition: facAlgExt.cc:57
char name(const Variable &v)
Definition: factory.h:189
static CanonicalForm conv2mipo(const CanonicalForm &mipo, const Variable &alpha)
Definition: variable.cc:154

◆ setCharacteristic() [1/3]

void FACTORY_PUBLIC setCharacteristic ( int  c)

Definition at line 28 of file cf_char.cc.

29 {
30  if ( c == 0 )
31  {
32  theDegree = 0;
35  }
36  else
37  {
38  theDegree = 1;
41  if (c!=theCharacteristic)
42  {
43  if (c > 536870909) factoryError("characteristic is too large(max is 2^29)");
44  ff_setprime( c );
45  }
47  }
48 }
#define FiniteFieldDomain
Definition: cf_defs.h:19
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
static void settype(int type)
Definition: cf_factory.h:29
VAR bool ff_big
Definition: ffops.cc:16
void ff_setprime(const int p)
Definition: ffops.cc:19

◆ setCharacteristic() [2/3]

void setCharacteristic ( int  c,
int  n 
)

◆ setCharacteristic() [3/3]

void setCharacteristic ( int  c,
int  n,
char  name 
)

Definition at line 61 of file cf_char.cc.

62 {
63  ASSERT( c != 0 && n > 1, "illegal GF(q)" );
64  setCharacteristic( c );
65  gf_setcharacteristic( c, n, name );
66  theDegree = n;
68 }
void setCharacteristic(int c)
Definition: cf_char.cc:28
void gf_setcharacteristic(int p, int n, char name)
Definition: gfops.cc:202

◆ setMipo()

void setMipo ( const Variable alpha,
const CanonicalForm mipo 
)

Definition at line 219 of file variable.cc.

220 {
221  ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
222  algextensions[-alpha.level()]= ext_entry( 0, false );
223  algextensions[-alpha.level()]= ext_entry((InternalPoly*)(conv2mipo( mipo, alpha ).getval()), true );
224 }

◆ setReduce()

void setReduce ( const Variable alpha,
bool  reduce 
)

Definition at line 238 of file variable.cc.

239 {
240  ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
242 }
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
bool & reduce()
Definition: variable.cc:38

◆ sign()

int sign ( const CanonicalForm a)
inline

Definition at line 484 of file factory.h.

484 { return a.sign(); }

◆ size() [1/2]

int size ( const CanonicalForm f)

int size ( const CanonicalForm & f )

size() - return number of monomials in f which are in an coefficient domain.

Returns one if f is in an coefficient domain.

Definition at line 627 of file cf_ops.cc.

628 {
629  if ( f.inCoeffDomain() )
630  return 1;
631  else
632  {
633  int result = 0;
634  CFIterator i;
635  for ( i = f; i.hasTerms(); i++ )
636  result += size( i.coeff() );
637  return result;
638  }
639 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600

◆ size() [2/2]

int size ( const CanonicalForm f,
const Variable v 
)

int size ( const CanonicalForm & f, const Variable & v )

size() - count number of monomials of f with level higher or equal than level of v.

Returns one if f is in an base domain.

Definition at line 600 of file cf_ops.cc.

601 {
602  if ( f.inBaseDomain() )
603  return 1;
604 
605  if ( f.mvar() < v )
606  // polynomials with level < v1 are counted as coefficients
607  return 1;
608  else
609  {
610  CFIterator i;
611  int result = 0;
612  // polynomials with level > v2 are not counted al all
613  for ( i = f; i.hasTerms(); i++ )
614  result += size( i.coeff(), v );
615  return result;
616  }
617 }

◆ size_maxexp()

int size_maxexp ( const CanonicalForm f,
int &  maxexp 
)

Definition at line 641 of file cf_ops.cc.

642 {
643  if ( f.inCoeffDomain() )
644  return 1;
645  else
646  {
647  if (f.degree()>maxexp) maxexp=f.degree();
648  int result = 0;
649  CFIterator i;
650  for ( i = f; i.hasTerms(); i++ )
651  result += size_maxexp( i.coeff(), maxexp );
652  return result;
653  }
654 }
int size_maxexp(const CanonicalForm &f, int &maxexp)
Definition: cf_ops.cc:641

◆ sqrFree()

CFFList FACTORY_PUBLIC sqrFree ( const CanonicalForm f,
bool  sort = false 
)

squarefree factorization

Definition at line 957 of file cf_factor.cc.

958 {
959 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
960  CFFList result;
961 
962  if ( getCharacteristic() == 0 )
963  result = sqrFreeZ( f );
964  else
965  {
966  Variable alpha;
967  if (hasFirstAlgVar (f, alpha))
968  result = FqSqrf( f, alpha );
969  else
970  result= FpSqrf (f);
971  }
972  if (sort)
973  {
974  CFFactor buf= result.getFirst();
975  result.removeFirst();
977  result.insert (buf);
978  }
979  return result;
980 }
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
void sort(CFArray &A, int l=0)
quick sort A
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:49
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25

◆ sqrt()

CanonicalForm sqrt ( const CanonicalForm a)
inline

Definition at line 490 of file factory.h.

490 { return a.sqrt(); }
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.

◆ subResChain()

CFArray subResChain ( const CanonicalForm f,
const CanonicalForm g,
const Variable x 
)

CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

subResChain() - caculate extended subresultant chain.

The chain is calculated from f and g with respect to variable x which should not be an algebraic variable. If f or q equals zero, an array consisting of one zero entry is returned.

Note: this is not the standard subresultant chain but the extended chain!

This algorithm is from the article of R. Loos - 'Generalized Polynomial Remainder Sequences' in B. Buchberger - 'Computer Algebra - Symbolic and Algebraic Computation' with some necessary extensions concerning the calculation of the first step.

Definition at line 42 of file cf_resultant.cc.

43 {
44  ASSERT( x.level() > 0, "cannot calculate subresultant sequence with respect to algebraic variables" );
45 
46  CFArray trivialResult( 0, 0 );
47  CanonicalForm F, G;
48  Variable X;
49 
50  // some checks on triviality
51  if ( f.isZero() || g.isZero() ) {
52  trivialResult[0] = 0;
53  return trivialResult;
54  }
55 
56  // make x main variable
57  if ( f.mvar() > x || g.mvar() > x ) {
58  if ( f.mvar() > g.mvar() )
59  X = f.mvar();
60  else
61  X = g.mvar();
62  F = swapvar( f, X, x );
63  G = swapvar( g, X, x );
64  }
65  else {
66  X = x;
67  F = f;
68  G = g;
69  }
70  // at this point, we have to calculate the sequence of F and
71  // G in respect to X where X is equal to or greater than the
72  // main variables of F and G
73 
74  // initialization of chain
75  int m = degree( F, X );
76  int n = degree( G, X );
77 
78  int j = (m <= n) ? n : m-1;
79  int r;
80 
81  CFArray S( 0, j+1 );
83  S[j+1] = F; S[j] = G;
84 
85  // make sure that S[j+1] is regular and j < n
86  if ( m == n && j > 0 ) {
87  S[j-1] = LC( S[j], X ) * psr( S[j+1], S[j], X );
88  j--;
89  } else if ( m < n ) {
90  S[j-1] = LC( S[j], X ) * LC( S[j], X ) * S[j+1];
91  j--;
92  } else if ( m > n && j > 0 ) {
93  // calculate first step
94  r = degree( S[j], X );
95  R = LC( S[j+1], X );
96 
97  // if there was a gap calculate similar polynomial
98  if ( j > r && r >= 0 )
99  S[r] = power( LC( S[j], X ), j - r ) * S[j] * power( R, j - r );
100 
101  if ( r > 0 ) {
102  // calculate remainder
103  S[r-1] = psr( S[j+1], S[j], X ) * power( -R, j - r );
104  j = r-1;
105  }
106  }
107 
108  while ( j > 0 ) {
109  // at this point, 0 < j < n and S[j+1] is regular
110  r = degree( S[j], X );
111  R = LC( S[j+1], X );
112 
113  // if there was a gap calculate similar polynomial
114  if ( j > r && r >= 0 )
115  S[r] = (power( LC( S[j], X ), j - r ) * S[j]) / power( R, j - r );
116 
117  if ( r <= 0 ) break;
118  // calculate remainder
119  S[r-1] = psr( S[j+1], S[j], X ) / power( -R, j - r + 2 );
120 
121  j = r-1;
122  // again 0 <= j < r <= jOld and S[j+1] is regular
123  }
124 
125  for ( j = 0; j <= S.max(); j++ ) {
126  // reswap variables if necessary
127  if ( X != x ) {
128  S[j] = swapvar( S[j], X, x );
129  }
130  }
131 
132  return S;
133 }
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

◆ swapvar()

swapvar() - swap variables x1 and x2 in f.

Returns the image of f under the map which maps x1 to x2 and x2 to x1. This is done quite efficiently because it is used really often. x1 and x2 should be polynomial variables.

Definition at line 168 of file cf_ops.cc.

169 {
170  ASSERT( x1.level() > 0 && x2.level() > 0, "cannot swap algebraic Variables" );
171  if ( f.inCoeffDomain() || x1 == x2 || ( x1 > f.mvar() && x2 > f.mvar() ) )
172  return f;
173  else
174  {
175  CanonicalForm result = 0;
176  if ( x1 > x2 )
177  {
178  sv_x1 = x2; sv_x2 = x1;
179  }
180  else
181  {
182  sv_x1 = x1; sv_x2 = x2;
183  }
184  if ( f.mvar() < sv_x2 )
185  // we only have to replace sv_x1 by sv_x2
186  swapvar_between( f, result, 1, 0 );
187  else
188  // we really have to swap variables
189  swapvar_rec( f, result, 1 );
190  return result;
191  }
192 }
static void swapvar_rec(const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term)
swapvar_between() - swap occurences of sv_x1 and sv_x2 in f.
Definition: cf_ops.cc:113
static void swapvar_between(const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term, int expx2)
static void swapvar_between ( const CanonicalForm & f, CanonicalForm & result, const CanonicalForm & ...
Definition: cf_ops.cc:58

◆ tailcoeff() [1/2]

CanonicalForm tailcoeff ( const CanonicalForm f)
inline

Definition at line 466 of file factory.h.

466 { return f.tailcoeff(); }

◆ tailcoeff() [2/2]

CanonicalForm tailcoeff ( const CanonicalForm f,
const Variable v 
)
inline

Definition at line 469 of file factory.h.

469 { return f.tailcoeff(v); }

◆ taildegree()

int taildegree ( const CanonicalForm f)
inline

Definition at line 463 of file factory.h.

463 { return f.taildegree(); }

◆ totaldegree() [1/2]

int totaldegree ( const CanonicalForm f)

int totaldegree ( const CanonicalForm & f )

totaldegree() - return the total degree of f.

If f is zero, return -1. If f is in a coefficient domain, return 0. Otherwise return the total degree of f in all polynomial variables.

Definition at line 523 of file cf_ops.cc.

524 {
525  if ( f.isZero() )
526  return -1;
527  else if ( f.inCoeffDomain() )
528  return 0;
529  else
530  {
531  CFIterator i;
532  int cdeg = 0, dummy;
533  // calculate maximum over all coefficients of f, taking
534  // in account our own exponent
535  for ( i = f; i.hasTerms(); i++ )
536  if ( (dummy = totaldegree( i.coeff() ) + i.exp()) > cdeg )
537  cdeg = dummy;
538  return cdeg;
539  }
540 }
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523

◆ totaldegree() [2/2]

int totaldegree ( const CanonicalForm f,
const Variable v1,
const Variable v2 
)

int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 )

totaldegree() - return the total degree of f as a polynomial in the polynomial variables between v1 and v2 (inclusively).

If f is zero, return -1. If f is in a coefficient domain, return 0. Also, return 0 if v1 > v2. Otherwise, take f to be a polynomial in the polynomial variables between v1 and v2 and return its total degree.

Definition at line 554 of file cf_ops.cc.

555 {
556  if ( f.isZero() )
557  return -1;
558  else if ( v1 > v2 )
559  return 0;
560  else if ( f.inCoeffDomain() )
561  return 0;
562  else if ( f.mvar() < v1 )
563  return 0;
564  else if ( f.mvar() == v1 )
565  return f.degree();
566  else if ( f.mvar() > v2 )
567  {
568  // v2's level is larger than f's level, descend down
569  CFIterator i;
570  int cdeg = 0, dummy;
571  // calculate maximum over all coefficients of f
572  for ( i = f; i.hasTerms(); i++ )
573  if ( (dummy = totaldegree( i.coeff(), v1, v2 )) > cdeg )
574  cdeg = dummy;
575  return cdeg;
576  }
577  else
578  {
579  // v1 < f.mvar() <= v2
580  CFIterator i;
581  int cdeg = 0, dummy;
582  // calculate maximum over all coefficients of f, taking
583  // in account our own exponent
584  for ( i = f; i.hasTerms(); i++ )
585  if ( (dummy = totaldegree( i.coeff(), v1, v2 ) + i.exp()) > cdeg )
586  cdeg = dummy;
587  return cdeg;
588  }
589 }

◆ tryFdivides()

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

Definition at line 456 of file cf_algorithm.cc.

457 {
458  fail= false;
459  // trivial cases
460  if ( g.isZero() )
461  return true;
462  else if ( f.isZero() )
463  return false;
464 
465  if (f.inCoeffDomain() || g.inCoeffDomain())
466  {
467  // if we are in a field all elements not equal to zero are units
468  if ( f.inCoeffDomain() )
469  {
470  CanonicalForm inv;
471  tryInvert (f, M, inv, fail);
472  return !fail;
473  }
474  else
475  {
476  return false;
477  }
478  }
479 
480  // we may assume now that both levels either equal LEVELBASE
481  // or are greater zero
482  int fLevel = f.level();
483  int gLevel = g.level();
484  if ( (gLevel > 0) && (fLevel == gLevel) )
485  {
486  if (degree( f ) > degree( g ))
487  return false;
488  bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
489 
490  if (fail || !dividestail)
491  return false;
492  bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail);
493  if (fail || !dividesLC)
494  return false;
495  CanonicalForm q,r;
496  bool divides= tryDivremt (g, f, q, r, M, fail);
497  if (fail || !divides)
498  return false;
499  return r.isZero();
500  }
501  else if ( gLevel < fLevel )
502  {
503  // g is a coefficient w.r.t. f
504  return false;
505  }
506  else
507  {
508  // either f is a coefficient w.r.t. polynomial g or both
509  // f and g are from a base domain (should be Z or Z/p^n,
510  // then)
511  CanonicalForm q, r;
512  bool divides= tryDivremt (g, f, q, r, M, fail);
513  if (fail || !divides)
514  return false;
515  return r.isZero();
516  }
517 }
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
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:221
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

◆ vcontent()

CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )

vcontent() - return content of f with repect to variables >= x.

The content is recursively calculated over all coefficients in f having level less than x. x should be a polynomial variable.

Definition at line 653 of file cf_gcd.cc.

654 {
655  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
656 
657  if ( f.mvar() <= x )
658  return content( f, x );
659  else {
660  CFIterator i;
661  CanonicalForm d = 0;
662  for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
663  d = gcd( d, vcontent( i.coeff(), x ) );
664  return d;
665  }
666 }
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653

Variable Documentation

◆ factoryConfiguration

const char factoryConfiguration[]
extern

◆ factoryError

EXTERN_VAR void(* factoryError) (const char *s) ( const char *  s)

Definition at line 1127 of file factory.h.

◆ singular_homog_flag

EXTERN_VAR int singular_homog_flag

Definition at line 586 of file factory.h.

◆ SW_BERLEKAMP

const int SW_BERLEKAMP =10
static

set to 1 to use Factorys Berlekamp alg.

Definition at line 108 of file factory.h.

◆ SW_FAC_QUADRATICLIFT

const int SW_FAC_QUADRATICLIFT =11
static

Definition at line 110 of file factory.h.

◆ SW_RATIONAL

const int SW_RATIONAL = 0
static

set to 1 for computations over Q

Definition at line 88 of file factory.h.

◆ SW_SYMMETRIC_FF

const int SW_SYMMETRIC_FF = 1
static

set to 1 for symmetric representation over F_q

Definition at line 90 of file factory.h.

◆ SW_USE_CHINREM_GCD

const int SW_USE_CHINREM_GCD =5
static

set to 1 to use modular gcd over Z

Definition at line 98 of file factory.h.

◆ SW_USE_EZGCD

const int SW_USE_EZGCD = 2
static

set to 1 to use EZGCD over Z

Definition at line 92 of file factory.h.

◆ SW_USE_EZGCD_P

const int SW_USE_EZGCD_P = 3
static

set to 1 to use EZGCD over F_q

Definition at line 94 of file factory.h.

◆ SW_USE_FF_MOD_GCD

const int SW_USE_FF_MOD_GCD =7
static

set to 1 to use modular GCD over F_q

Definition at line 102 of file factory.h.

◆ SW_USE_FL_FAC_0

const int SW_USE_FL_FAC_0 =13
static

set to 1 to prefer flints multivariate factorization over Z/p

Definition at line 114 of file factory.h.

◆ SW_USE_FL_FAC_0A

const int SW_USE_FL_FAC_0A =14
static

set to 1 to prefer flints multivariate factorization over Z/p(a)

Definition at line 116 of file factory.h.

◆ SW_USE_FL_FAC_P

const int SW_USE_FL_FAC_P =12
static

set to 1 to prefer flints multivariate factorization over Z/p

Definition at line 112 of file factory.h.

◆ SW_USE_FL_GCD_0

const int SW_USE_FL_GCD_0 =9
static

set to 1 to use Flints gcd over Q/Z

Definition at line 106 of file factory.h.

◆ SW_USE_FL_GCD_P

const int SW_USE_FL_GCD_P =8
static

set to 1 to use Flints gcd over F_p

Definition at line 104 of file factory.h.

◆ SW_USE_NTL_SORT

const int SW_USE_NTL_SORT =4
static

set to 1 to sort factors in a factorization

Definition at line 96 of file factory.h.

◆ SW_USE_QGCD

const int SW_USE_QGCD =6
static

set to 1 to use Encarnacion GCD over Q(a)

Definition at line 100 of file factory.h.