‘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"

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< CanonicalForm >	CFAFactor

typedef List< CFAFactor >	CFAFList

typedef ListIterator< CFAFactor >	CFAFListIterator

typedef Factor< CanonicalForm >	CFFactor

typedef List< CFFactor >	CFFList

typedef ListIterator< CFFactor >	CFFListIterator

typedef List< CanonicalForm >	CFList

typedef ListIterator< CanonicalForm >	CFListIterator

typedef Array< CanonicalForm >	CFArray

typedef Matrix< CanonicalForm >	CFMatrix

typedef List< CFList >	ListCFList

typedef ListIterator< CFList >	ListCFListIterator

typedef List< int >	IntList

typedef ListIterator< int >	IntListIterator

typedef List< Variable >	Varlist

typedef ListIterator< Variable >	VarlistIterator

typedef Array< int >	Intarray

typedef term *	termList

typedef List< MapPair >	MPList

typedef ListIterator< MapPair >	MPListIterator

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 or 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. must be either or . 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. must be either or . 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

typedef AFactor<CanonicalForm> CFAFactor

Definition at line 530 of file factory.h.

◆ CFAFList

typedef List<CFAFactor> CFAFList

Definition at line 531 of file factory.h.

◆ CFAFListIterator

typedef ListIterator<CFAFactor> CFAFListIterator

Definition at line 532 of file factory.h.

◆ CFArray

typedef Array<CanonicalForm> CFArray

Definition at line 538 of file factory.h.

◆ CFFactor

typedef Factor<CanonicalForm> CFFactor

Definition at line 533 of file factory.h.

◆ CFFList

typedef List<CFFactor> CFFList

Definition at line 534 of file factory.h.

◆ CFFListIterator

typedef ListIterator<CFFactor> CFFListIterator

Definition at line 535 of file factory.h.

◆ CFList

typedef List<CanonicalForm> CFList

Definition at line 536 of file factory.h.

◆ CFListIterator

typedef ListIterator<CanonicalForm> CFListIterator

Definition at line 537 of file factory.h.

◆ CFMatrix

typedef Matrix<CanonicalForm> 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

typedef ListIterator<int> IntListIterator

Definition at line 543 of file factory.h.

◆ ListCFList

typedef List<CFList> ListCFList

Definition at line 540 of file factory.h.

◆ ListCFListIterator

typedef ListIterator<CFList> ListCFListIterator

Definition at line 541 of file factory.h.

◆ MPList

typedef List<MapPair> MPList

Definition at line 986 of file factory.h.

◆ MPListIterator

typedef ListIterator<MapPair> 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

typedef ListIterator<Variable> 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.

{
    // it is not only more general to use `sign()' instead of a
    // direct comparison `f < 0', it is faster, too
    if ( sign( f ) < 0 )
        return -f;
    else
        return f;
}

◆ 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] G poly over Q

Definition at line 262 of file facAbsFact.cc.

{
  //TODO handle homogeneous input, is already done in LIB interface but still...
  ASSERT (getCharacteristic() == 0, "expected poly over Q");
 
  CanonicalForm F= G;
 
  CanonicalForm LcF= Lc (F);
  bool isRat= isOn (SW_RATIONAL);
  if (isRat)
    F *= bCommonDen (F);
 
  Off (SW_RATIONAL);
  F /= icontent (F);
  if (isRat)
    On (SW_RATIONAL);
 
  CFFList rationalFactors= factorize (F);
 
  CFAFList result, resultBuf;
 
  CFAFListIterator iter;
  CFFListIterator i= rationalFactors;
  i++;
  for (; i.hasItem(); i++)
  {
    resultBuf= absFactorizeMain (i.getItem().factor());
    for (iter= resultBuf; iter.hasItem(); iter++)
      iter.getItem()= CFAFactor (iter.getItem().factor(),
                                 iter.getItem().minpoly(), i.getItem().exp());
    result= Union (result, resultBuf);
  }
 
  if (isRat)
    normalize (result);
  result.insert (CFAFactor (LcF, 1, 1));
 
  return result;
}

◆ 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--;
}

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.

{
    if ( f.inCoeffDomain() )
    {
        int exp = 0;
        CanonicalForm result = f;
        mf( result, exp );
        ASSERT( exp == 0, "illegal result, do not know what variable to use" );
        return result;
    }
    else
    {
        CanonicalForm result, coeff;
        CFIterator i;
        int exp;
        Variable x = f.mvar();
        for ( i = f; i.hasTerms(); i++ )
        {
            coeff = i.coeff();
            exp = i.exp();
            mf( coeff, exp );
            if ( ! coeff.isZero() )
                result += power( x, exp ) * coeff;
        }
        return result;
    }
}

◆ 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.

{
  CFList QS= PS, BS, RS;
  CanonicalForm b;
  int cb, degb;
 
  if (PS.length() < 2)
    return PS;
 
  CFListIterator i;
 
  while (!QS.isEmpty())
  {
    b= lowestRank (QS);
    cb= b.level();
 
    BS= Union(CFList (b), BS);
 
    if (cb <= 0)
      return CFList();
    else
    {
      degb= degree (b);
      RS= CFList();
      for (i= QS; i.hasItem(); i++)
      {
        if (degree (i.getItem(), cb) < degb)
          RS= Union (CFList (i.getItem()), RS);
      }
      QS= RS;
    }
  }
 
  return BS;
}

◆ bCommonDen()

CanonicalForm FACTORY_PUBLIC bCommonDen ( const CanonicalForm & f )

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.

{
    if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) )
    {
        // otherwise `bgcd()' returns one
        Off( SW_RATIONAL );
        CanonicalForm result = internalBCommonDen( f );
        On( SW_RATIONAL );
        return result;
    }
    else
        return CanonicalForm( 1 );
}

◆ blcm()

CanonicalForm FACTORY_PUBLIC blcm	(	const CanonicalForm &	f,
		const CanonicalForm &	g
	)

Definition at line 1816 of file canonicalform.cc.

{
    if ( f.isZero() || g.isZero() )
        return CanonicalForm( 0L );
/*
    else if (f.isOne())
        return g;
    else if (g.isOne())
        return f;
*/
    else
        return (f / bgcd( f, g )) * g;
}

◆ cf_getBigPrime()

int FACTORY_PUBLIC cf_getBigPrime ( int i )

Definition at line 39 of file cf_primes.cc.

{
    ASSERT( i >= 0 && i < NUMBIGPRIMES, "index to primes too high" );
    return bigprimes[i];
}

◆ cf_getNumBigPrimes()

int FACTORY_PUBLIC cf_getNumBigPrimes ( )

Definition at line 45 of file cf_primes.cc.

{
    return NUMBIGPRIMES;
}

◆ cf_getNumPrimes()

int FACTORY_PUBLIC cf_getNumPrimes ( )

Definition at line 23 of file cf_primes.cc.

{
    return NUMPRIMES;
}

◆ cf_getNumSmallPrimes()

int FACTORY_PUBLIC cf_getNumSmallPrimes ( )

Definition at line 34 of file cf_primes.cc.

{
    return NUMSMALLPRIMES;
}

◆ cf_getPrime()

int FACTORY_PUBLIC cf_getPrime ( int i )

Definition at line 14 of file cf_primes.cc.

{
    ASSERT( i >= 0 && i < NUMPRIMES, "index to primes too high" );
    if ( i >= NUMSMALLPRIMES )
        return bigprimes[i-NUMSMALLPRIMES];
    else
        return smallprimes[i];
}

◆ cf_getSmallPrime()

int FACTORY_PUBLIC cf_getSmallPrime ( int i )

Definition at line 28 of file cf_primes.cc.

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

◆ 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.

{
#ifdef HAVE_FLINT
  fmpz_mat_t FLINTM;
  convertFacCFMatrix2Fmpz_mat_t(FLINTM,A);
  fmpz_mat_hnf(FLINTM,FLINTM);
  CFMatrix *r=convertFmpz_mat_t2FacCFMatrix(FLINTM);
  fmpz_mat_clear(FLINTM);
  return r;
#elif defined(HAVE_NTL)
  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
  ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
  mat_ZZ WW;
  HNF(WW,*AA,DD);
  delete AA;
  return convertNTLmat_ZZ2FacCFMatrix(WW);
#else
  factoryError("NTL/FLINT missing: cf_HNF");
  return NULL; // avoid warning
#endif
}

◆ 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.

{
#ifdef HAVE_FLINT
  fmpz_mat_t FLINTM;
  convertFacCFMatrix2Fmpz_mat_t(FLINTM,A);
  fmpq_t delta,eta;
  fmpq_init(delta); fmpq_set_si(delta,1,1);
  fmpq_init(eta); fmpq_set_si(eta,3,4);
  fmpz_mat_lll_storjohann(FLINTM,delta,eta);
  CFMatrix *r=convertFmpz_mat_t2FacCFMatrix(FLINTM);
  fmpz_mat_clear(FLINTM);
  return r;
#elif defined(HAVE_NTL)
  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
  ZZ det2;
  LLL(det2,*AA,0L);
  CFMatrix *r= convertNTLmat_ZZ2FacCFMatrix(*AA);
  delete AA;
  return r;
#else
  factoryError("NTL/FLINT missing: cf_LLL");
  return NULL; // avoid warning
#endif
}

◆ charSeries()

ListCFList charSeries ( const CFList & L )

characteristic series

Definition at line 411 of file cfCharSets.cc.

{
  ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
  CFList l, charset, ini;
 
  int count= 0;
  int highestLevel= 1;
  CFListIterator iter;
 
  StoreFactors StoredFactors;
 
  l= L;
 
  for (iter= l; iter.hasItem(); iter++)
  {
    iter.getItem()= normalize (iter.getItem());
    if (highestLevel < iter.getItem().level())
      highestLevel= iter.getItem().level();
  }
 
  tmp= ListCFList (l);
 
  while (!tmp.isEmpty())
  {
    sortListCFList (tmp);
 
    l= tmp.getFirst();
 
    tmp= Difference (tmp, l);
 
    select (ppi, l.length(), ppi1, ppi2);
 
    inplaceUnion (ppi2, qqi);
 
    if (count > 0)
      ppi= Union (ppi1, ListCFList (l));
    else
      ppi= ListCFList();
 
    if (l.length() - 3 < highestLevel)
      charset= charSetViaModCharSet (l, StoredFactors);
    else
      charset= charSetViaCharSetN (l);
 
    if (charset.length() > 0 && charset.getFirst().level() > 0)
    {
      result= Union (ListCFList (charset), result);
      ini= factorsOfInitials (charset);
 
      ini= Union (ini, factorPSet (StoredFactors.FS1));
      sortCFListByLevel (ini);
    }
    else
    {
      ini= factorPSet (StoredFactors.FS1);
      sortCFListByLevel (ini);
    }
 
    tmp2= adjoin (ini, l, qqi);
    tmp= Union (tmp2, tmp);
 
    StoredFactors.FS1= CFList();
    StoredFactors.FS2= CFList();
 
    ppi1= ListCFList();
    ppi2= ListCFList();
 
    count++;
  }
 
  //TODO need to remove superflous components
 
  return result;
}

◆ charSet()

CFList charSet ( const CFList & PS )

characteristic set

Definition at line 187 of file cfCharSets.cc.

{
  CFList QS= PS, RS= PS, CSet, tmp;
  CFListIterator i;
  CanonicalForm r;
 
  while (!RS.isEmpty())
  {
    CSet= basicSet (QS);
 
    RS= CFList();
    if (CSet.length() > 0 && CSet.getFirst().level() > 0)
    {
      tmp= Difference (QS, CSet);
      for (i= tmp; i.hasItem(); i++)
      {
        r= Prem (i.getItem(), CSet);
        if (r != 0)
          RS= Union (RS, CFList (r));
      }
      QS= Union (QS, RS);
    }
  }
 
  return CSet;
}

◆ charSetN()

CFList charSetN ( const CFList & PS )

medial set

Definition at line 216 of file cfCharSets.cc.

{
  CFList QS= PS, RS= PS, CSet, tmp;
  CFListIterator i;
  CanonicalForm r;
 
  while (!RS.isEmpty())
  {
    QS= uniGcd (QS);
    CSet= basicSet (QS);
 
    RS= CFList();
    if (CSet.length() > 0 && CSet.getFirst().level() > 0)
    {
      tmp= Difference (QS, CSet);
      for (i= tmp; i.hasItem(); i++)
      {
        r= Prem (i.getItem(), CSet);
        if (!r.isZero())
          RS= Union (RS, CFList (r));
      }
      QS= Union (CSet, RS);
    }
  }
 
  return CSet;
}

◆ charSetViaCharSetN()

CFList charSetViaCharSetN ( const CFList & PS )

compute a characteristic set via medial set

Definition at line 246 of file cfCharSets.cc.

{
  CFList L;
  CFFList sqrfFactors;
  CanonicalForm sqrf;
  CFFListIterator iter2;
  for (CFListIterator iter= PS; iter.hasItem(); iter++)
  {
    sqrf= 1;
    sqrfFactors= sqrFree (iter.getItem());
    for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
      sqrf *= iter2.getItem().factor();
    L= Union (L, CFList (normalize (sqrf)));
  }
 
  CFList result= charSetN (L);
 
  if (result.isEmpty() || result.getFirst().inCoeffDomain())
    return CFList(1);
 
  CanonicalForm r;
  CFList RS;
  CFList tmp= Difference (L, result);
 
  for (CFListIterator i= tmp; i.hasItem(); i++)
  {
    r= Premb (i.getItem(), result);
    if (!r.isZero())
      RS= Union (RS, CFList (r));
  }
  if (RS.isEmpty())
    return result;
 
  return charSetViaCharSetN (Union (L, Union (RS, result)));
}

◆ 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.

{
  StoreFactors tmp;
  return charSetViaModCharSet (PS, tmp, removeContents);
}

◆ charSetViaModCharSet() [2/2]

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

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

Definition at line 356 of file cfCharSets.cc.

{
  CFList L;
  CFFList sqrfFactors;
  CanonicalForm sqrf;
  CFFListIterator iter2;
  for (CFListIterator iter= PS; iter.hasItem(); iter++)
  {
    sqrf= 1;
    sqrfFactors= sqrFree (iter.getItem());
    for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
      sqrf *= iter2.getItem().factor();
    L= Union (L, CFList (normalize (sqrf)));
  }
 
  L= uniGcd (L);
 
  CFList result= modCharSet (L, StoredFactors, removeContents);
 
  if (result.isEmpty() || result.getFirst().inCoeffDomain())
    return CFList(1);
 
  CanonicalForm r;
  CFList RS;
  CFList tmp= Difference (L, result);
 
  for (CFListIterator i= tmp; i.hasItem(); i++)
  {
    r= Premb (i.getItem(), result);
    if (!r.isZero())
      RS= Union (RS, CFList (r));
  }
  if (RS.isEmpty())
    return result;
 
  return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors,
                               removeContents);
}

◆ 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.

{
    DEBINCLEVEL( cerr, "chineseRemainder" );
 
    DEBOUTLN( cerr, "log(q1) = " << q1.ilog2() );
    DEBOUTLN( cerr, "log(q2) = " << q2.ilog2() );
 
    // We calculate xnew as follows:
    //     xnew = v1 + v2 * q1
    // where
    //     v1 = x1 (mod q1)
    //     v2 = (x2-v1)/q1 (mod q2)  (*)
    //
    // We do one extra test to check whether x2-v1 vanishes (mod
    // q2) in (*) since it is not costly and may save us
    // from calculating the inverse of q1 (mod q2).
    //
    // u: v1 (mod q2)
    // d: x2-v1 (mod q2)
    // s: 1/q1 (mod q2)
    //
    CanonicalForm v2, v1;
    CanonicalForm u, d, s, dummy;
 
    v1 = mod( x1, q1 );
    u = mod( v1, q2 );
    d = mod( x2-u, q2 );
    if ( d.isZero() )
    {
        xnew = v1;
        qnew = q1 * q2;
        DEBDECLEVEL( cerr, "chineseRemainder" );
        return;
    }
    (void)bextgcd( q1, q2, s, dummy );
    v2 = mod( d*s, q2 );
    xnew = v1 + v2*q1;
 
    // After all, calculate new modulus.  It is important that
    // this is done at the very end of the algorithm, since q1
    // and qnew may refer to the same object (same is true for x1
    // and xnew).
    qnew = q1 * q2;
 
    DEBDECLEVEL( cerr, "chineseRemainder" );
}

◆ 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.

{
    DEBINCLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
 
    ASSERT( x.min() == q.min() && x.size() == q.size(), "incompatible arrays" );
    CFArray X(x), Q(q);
    int i, j, n = x.size(), start = x.min();
 
    DEBOUTLN( cerr, "array size = " << n );
 
    while ( n != 1 )
    {
        i = j = start;
        while ( i < start + n - 1 )
        {
            // This is a little bit dangerous: X[i] and X[j] (and
            // Q[i] and Q[j]) may refer to the same object.  But
            // xnew and qnew in the above function are modified
            // at the very end of the function, so we do not
            // modify x1 and q1, resp., by accident.
            chineseRemainder( X[i], Q[i], X[i+1], Q[i+1], X[j], Q[j] );
            i += 2;
            j++;
        }
 
        if ( n & 1 )
        {
            X[j] = X[i];
            Q[j] = Q[i];
        }
        // Maybe we would get some memory back at this point if
        // we would set X[j+1, ..., n] and Q[j+1, ..., n] to zero
        // at this point?
 
        n = ( n + 1) / 2;
    }
    xnew = X[start];
    qnew = Q[q.min()];
 
    DEBDECLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
}

◆ 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.

{
  CFArray A(2); A[0]=a; A[1]=b;
  CFArray Q(2); Q[0]=q1; Q[1]=q2;
  chineseRemainderCached(A,Q,xnew,qnew,inv);
}

◆ 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.

{
  CanonicalForm p, sum=0L; prod=1L;
  int i;
  int len=n.size();
 
  for (i = 0; i < len; i++) prod *= n[i];
 
  for (i = 0; i < len; i++)
  {
    p = prod / n[i];
    sum += a[i] * chin_mul_inv(p, n[i], i, inv) * p;
  }
 
  xnew = mod(sum , prod);
}

◆ 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.

{
    CanonicalForm result = f;
    int i, n;
    int * degs = degrees( f );
 
    m = CFMap();
    n = i = 1;
    while ( i <= level( f ) ) {
        while( degs[i] == 0 ) i++;
        if ( i != n ) {
            // swap variables and remember the swap in the map
            m.newpair( Variable( n ), Variable( i ) );
            result = swapvar( result, Variable( i ), Variable( n ) );
        }
        n++; i++;
    }
    DELETE_ARRAY(degs);
    return result;
}

◆ 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.

{
    int n = tmax( f.level(), g.level() );
    int i, k, p1, pe;
    int * degsf = NEW_ARRAY(int,n+1);
    int * degsg = NEW_ARRAY(int,n+1);
 
    for ( i = 0; i <= n; i++ )
    {
        degsf[i] = degsg[i] = 0;
    }
 
    degsf = degrees( f, degsf );
    degsg = degrees( g, degsg );
    optvalues( degsf, degsg, n, p1, pe );
 
    i = 1; k = 1;
    if ( pe > 1 )
    {
        M.newpair( Variable(pe), Variable(k) );
        N.newpair( Variable(k), Variable(pe) );
        k++;
    }
    while ( i <= n )
    {
        if ( degsf[i] > 0 && degsg[i] > 0 )
        {
            if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
            {
                M.newpair( Variable(i), Variable(k) );
                N.newpair( Variable(k), Variable(i) );
            }
            k++;
        }
        i++;
    }
    if ( p1 != pe )
    {
        M.newpair( Variable(p1), Variable(k) );
        N.newpair( Variable(k), Variable(p1) );
        k++;
    }
    i = 1;
    while ( i <= n )
    {
        if ( degsf[i] > 0 && degsg[i] == 0 ) {
            if ( i != k )
            {
                M.newpair( Variable(i), Variable(k) );
                k++;
            }
        }
        else if ( degsf[i] == 0 && degsg[i] > 0 )
        {
            if ( i != k )
            {
                M.newpair( Variable(i), Variable(k) );
                k++;
            }
        }
        i++;
    }
 
    DELETE_ARRAY(degsf);
    DELETE_ARRAY(degsg);
}

◆ 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.

{
    M = N = CFMap();
    if ( a.size() == 0 )
        return;
    int maxlevel = level( a[a.min()] );
    int i, j;
 
    // get the maximum of levels in a
    for ( i = a.min() + 1; i <= a.max(); i++ )
        if ( level( a[i] ) > maxlevel )
            maxlevel = level( a[i] );
    if ( maxlevel <= 0 )
        return;
 
    int * degs = NEW_ARRAY(int,maxlevel+1);
    int * tmp = NEW_ARRAY(int,maxlevel+1);
    for ( i = maxlevel; i >= 1; i-- )
        degs[i] = 0;
 
    // calculate the union of all levels occuring in a
    for ( i = a.min(); i <= a.max(); i++ )
    {
        tmp = degrees( a[i], tmp );
        for ( j = 1; j <= level( a[i] ); j++ )
            if ( tmp[j] != 0 )
                degs[j] = 1;
    }
 
    // create the maps
    i = 1; j = 1;
    while ( i <= maxlevel )
    {
        if ( degs[i] != 0 )
        {
            M.newpair( Variable(i), Variable(j) );
            N.newpair( Variable(j), Variable(i) );
            j++;
        }
        i++;
    }
    DELETE_ARRAY(degs);
    DELETE_ARRAY(tmp);
}

◆ content() [1/2]

CanonicalForm FACTORY_PUBLIC content ( const CanonicalForm & f )

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.

{
    if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
    {
        CFIterator i = f;
        CanonicalForm result = abs( i.coeff() );
        i++;
        while ( i.hasTerms() && ! result.isOne() )
        {
            result = gcd( i.coeff(), result );
            i++;
        }
        return result;
    }
    else
        return abs( f );
}

◆ content() [2/2]

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

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.

{
    if (f.inBaseDomain()) return f;
    ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
    Variable y = f.mvar();
 
    if ( y == x )
        return cf_content( f, 0 );
    else  if ( y < x )
        return f;
    else
        return swapvar( content( swapvar( f, y, x ), y ), y, x );
}

◆ 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 ); }

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.

{
    if ( f.inCoeffDomain() )
    {
        if (degs != 0)
          return degs;
        else
          return 0;
    }
    else
    {
        int level = f.level();
        if ( degs == NULL )
            degs = NEW_ARRAY(int,level+1);
        for ( int i = level; i >= 0; i-- )
            degs[i] = 0;
        degreesRec( f, degs );
        return degs;
    }
}

◆ 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.

{
    typedef int* int_ptr;
 
    ASSERT( rows <= M.rows() && rows <= M.columns() && rows > 0, "undefined determinant" );
    if ( rows == 1 )
        return M(1,1);
    else  if ( rows == 2 )
        return M(1,1)*M(2,2)-M(2,1)*M(1,2);
    else  if ( matrix_in_Z( M, rows ) )
    {
        int ** mm = new int_ptr[rows];
        CanonicalForm x, q, Qhalf, B;
        int n, i, intdet, p, pno;
        for ( i = 0; i < rows; i++ )
        {
            mm[i] = new int[rows];
        }
        pno = 0; n = 0;
        TIMING_START(det_bound);
        B = detbound( M, rows );
        TIMING_END(det_bound);
        q = 1;
        TIMING_START(det_numprimes);
        while ( B > q && n < cf_getNumBigPrimes() )
        {
            q *= cf_getBigPrime( n );
            n++;
        }
        TIMING_END(det_numprimes);
 
        CFArray X(1,n), Q(1,n);
 
        while ( pno < n )
        {
            p = cf_getBigPrime( pno );
            setCharacteristic( p );
            // map matrix into char p
            TIMING_START(det_mapping);
            fill_int_mat( M, mm, rows );
            TIMING_END(det_mapping);
            pno++;
            DEBOUT( cerr, "." );
            TIMING_START(det_determinant);
            intdet = determinant( mm, rows );
            TIMING_END(det_determinant);
            setCharacteristic( 0 );
            X[pno] = intdet;
            Q[pno] = p;
        }
        TIMING_START(det_chinese);
        chineseRemainder( X, Q, x, q );
        TIMING_END(det_chinese);
        Qhalf = q / 2;
        if ( x > Qhalf )
            x = x - q;
        for ( i = 0; i < rows; i++ )
            delete [] mm[i];
        delete [] mm;
        return x;
    }
    else
    {
        CFMatrix m( M );
        CanonicalForm divisor = 1, pivot, mji;
        int i, j, k, sign = 1;
        for ( i = 1; i <= rows; i++ ) {
            pivot = m(i,i); k = i;
            for ( j = i+1; j <= rows; j++ ) {
                if ( betterpivot( pivot, m(j,i) ) ) {
                    pivot = m(j,i);
                    k = j;
                }
            }
            if ( pivot.isZero() )
                return 0;
            if ( i != k )
            {
                m.swapRow( i, k );
                sign = -sign;
            }
            for ( j = i+1; j <= rows; j++ )
            {
                if ( ! m(j,i).isZero() )
                {
                    divisor *= pivot;
                    mji = m(j,i);
                    m(j,i) = 0;
                    for ( k = i+1; k <= rows; k++ )
                        m(j,k) = m(j,k) * pivot - m(i,k)*mji;
                }
            }
        }
        pivot = sign;
        for ( i = 1; i <= rows; i++ )
            pivot *= m(i,i);
        return pivot / divisor;
    }
}

◆ div()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div	(	const CanonicalForm &	,
		const CanonicalForm &
	)

◆ euclideanNorm()

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.

{
    ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
            "type error: univariate poly over Z expected" );
 
    CanonicalForm result = 0;
    for ( CFIterator i = f; i.hasTerms(); i++ ) {
        CanonicalForm coeff = i.coeff();
        result += coeff*coeff;
    }
    return sqrt( result );
}

◆ ExtensionLevel()

int ExtensionLevel ( )

Definition at line 254 of file variable.cc.

{
  if( var_names_ext == 0)
    return 0;
  return strlen( var_names_ext )-1;
}

◆ extgcd()

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 )

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.

{
  if (f.isZero())
  {
    a= 0;
    b= 1;
    return g;
  }
  else if (g.isZero())
  {
    a= 1;
    b= 0;
    return f;
  }
#ifdef HAVE_FLINT
  if (( getCharacteristic() > 0 ) && (CFFactory::gettype() != GaloisFieldDomain)
  &&  (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
  {
    nmod_poly_t F1, G1, A, B, R;
    convertFacCF2nmod_poly_t (F1, f);
    convertFacCF2nmod_poly_t (G1, g);
    nmod_poly_init (R, getCharacteristic());
    nmod_poly_init (A, getCharacteristic());
    nmod_poly_init (B, getCharacteristic());
    nmod_poly_xgcd (R, A, B, F1, G1);
    a= convertnmod_poly_t2FacCF (A, f.mvar());
    b= convertnmod_poly_t2FacCF (B, f.mvar());
    CanonicalForm r= convertnmod_poly_t2FacCF (R, f.mvar());
    nmod_poly_clear (F1);
    nmod_poly_clear (G1);
    nmod_poly_clear (A);
    nmod_poly_clear (B);
    nmod_poly_clear (R);
    return r;
  }
#elif defined(HAVE_NTL)
  if (( getCharacteristic() > 0 ) && (CFFactory::gettype() != GaloisFieldDomain)
  &&  (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
  {
    if (fac_NTL_char!=getCharacteristic())
    {
      fac_NTL_char=getCharacteristic();
      zz_p::init(getCharacteristic());
    }
    zz_pX F1=convertFacCF2NTLzzpX(f);
    zz_pX G1=convertFacCF2NTLzzpX(g);
    zz_pX R;
    zz_pX A,B;
    XGCD(R,A,B,F1,G1);
    a=convertNTLzzpX2CF(A,f.mvar());
    b=convertNTLzzpX2CF(B,f.mvar());
    return convertNTLzzpX2CF(R,f.mvar());
  }
#endif
#ifdef HAVE_FLINT
  if (( getCharacteristic() ==0) && (f.level()==g.level())
       && isPurePoly(f) && isPurePoly(g))
  {
    fmpq_poly_t F1, G1;
    convertFacCF2Fmpq_poly_t (F1, f);
    convertFacCF2Fmpq_poly_t (G1, g);
    fmpq_poly_t R, A, B;
    fmpq_poly_init (R);
    fmpq_poly_init (A);
    fmpq_poly_init (B);
    fmpq_poly_xgcd (R, A, B, F1, G1);
    a= convertFmpq_poly_t2FacCF (A, f.mvar());
    b= convertFmpq_poly_t2FacCF (B, f.mvar());
    CanonicalForm r= convertFmpq_poly_t2FacCF (R, f.mvar());
    fmpq_poly_clear (F1);
    fmpq_poly_clear (G1);
    fmpq_poly_clear (A);
    fmpq_poly_clear (B);
    fmpq_poly_clear (R);
    return r;
  }
#elif defined(HAVE_NTL)
  if (( getCharacteristic() ==0)
  && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
  {
    CanonicalForm fc=bCommonDen(f);
    CanonicalForm gc=bCommonDen(g);
    ZZX F1=convertFacCF2NTLZZX(f*fc);
    ZZX G1=convertFacCF2NTLZZX(g*gc);
    ZZX R=GCD(F1,G1);
    CanonicalForm r=convertNTLZZX2CF(R,f.mvar());
    ZZ RR;
    ZZX A,B;
    if (r.inCoeffDomain())
    {
      XGCD(RR,A,B,F1,G1,1);
      CanonicalForm rr=convertZZ2CF(RR);
      if(!rr.isZero())
      {
        a=convertNTLZZX2CF(A,f.mvar())*fc/rr;
        b=convertNTLZZX2CF(B,f.mvar())*gc/rr;
        return CanonicalForm(1);
      }
      else
      {
        F1 /= R;
        G1 /= R;
        XGCD (RR, A,B,F1,G1,1);
        rr=convertZZ2CF(RR);
        a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
        b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
      }
    }
    else
    {
      XGCD(RR,A,B,F1,G1,1);
      CanonicalForm rr=convertZZ2CF(RR);
      if (!rr.isZero())
      {
        a=convertNTLZZX2CF(A,f.mvar())*fc;
        b=convertNTLZZX2CF(B,f.mvar())*gc;
      }
      else
      {
        F1 /= R;
        G1 /= R;
        XGCD (RR, A,B,F1,G1,1);
        rr=convertZZ2CF(RR);
        a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
        b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
      }
      return r;
    }
  }
#endif
  // may contain bug in the co-factors, see track 107
  CanonicalForm contf = content( f );
  CanonicalForm contg = content( g );
 
  CanonicalForm p0 = f / contf, p1 = g / contg;
  CanonicalForm f0 = 1, f1 = 0, g0 = 0, g1 = 1, q, r;
 
  while ( ! p1.isZero() )
  {
      divrem( p0, p1, q, r );
      p0 = p1; p1 = r;
      r = g0 - g1 * q;
      g0 = g1; g1 = r;
      r = f0 - f1 * q;
      f0 = f1; f1 = r;
  }
  CanonicalForm contp0 = content( p0 );
  a = f0 / ( contf * contp0 );
  b = g0 / ( contg * contp0 );
  p0 /= contp0;
  if ( p0.sign() < 0 )
  {
      p0 = -p0;
      a = -a;
      b = -b;
  }
  return p0;
}

◆ 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]	f	univariate poly
[in]	as	irreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  CFFList Output, output, Factors= factorize(f);
  if (Factors.getFirst().factor().inCoeffDomain())
    Factors.removeFirst();
 
  if (as.length() == 0)
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factors;
  }
  if (f.level() <= as.getLast().level())
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factors;
  }
 
  for (CFFListIterator i=Factors; i.hasItem(); i++)
  {
    if (i.getItem().factor().level() > as.getLast().level())
    {
      output= facAlgFunc2 (i.getItem().factor(), as);
      for (CFFListIterator j= output; j.hasItem(); j++)
        Output= append (Output, CFFactor (j.getItem().factor(),
                                          j.getItem().exp()*i.getItem().exp()));
    }
  }
 
  if (!isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);
  return Output;
}

◆ 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]	f	univariate poly
[in]	as	irreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  Variable vf=f.mvar();
  CFListIterator i;
  CFFListIterator jj;
  CFList reduceresult;
  CFFList result;
 
// F1: [Test trivial cases]
// 1) first trivial cases:
  if (vf.level() <= as.getLast().level())
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return CFFList(CFFactor(f,1));
  }
 
// 2) Setup list of those polys in AS having degree > 1
  CFList Astar;
  Variable x;
  CanonicalForm elem;
  Varlist ord, uord;
  for (int ii= 1; ii < level (vf); ii++)
    uord.append (Variable (ii));
 
  for (i= as; i.hasItem(); i++)
  {
    elem= i.getItem();
    x= elem.mvar();
    if (degree (elem, x) > 1)  // otherwise it's not an extension
    {
      Astar.append (elem);
      ord.append (x);
    }
  }
  uord= Difference (uord, ord);
 
// 3) second trivial cases: we already proved irr. of f over no extensions
  if (Astar.length() == 0)
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return CFFList (CFFactor (f, 1));
  }
 
// 4) Look if elements in uord actually occur in any of the minimal
//    polynomials. If no element of uord occures in any of the minimal
//    polynomials the field is an alg. number field not an alg. function field
  Varlist newuord= varsInAs (uord, Astar);
 
  CFFList Factorlist;
  Varlist gcdord= Union (ord, newuord);
  gcdord.append (f.mvar());
  bool isFunctionField= (newuord.length() > 0);
 
  // TODO alg_sqrfree?
  CanonicalForm Fgcd= 0;
  if (isFunctionField)
    Fgcd= alg_gcd (f, f.deriv(), Astar);
 
  bool derivZero= f.deriv().isZero();
  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
  {
    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
    if (getCharacteristic() == 0)
    {
      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
      multiplicity (result, f, Astar);
      if (!isRat && getCharacteristic() == 0)
        Off (SW_RATIONAL);
      return result;
    }
 
    Fgcd= pp (Fgcd);
    Ggcd= pp (Ggcd);
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
  }
 
  if (getCharacteristic() > 0)
  {
    IntList degreelist;
    Variable vminpoly;
    for (i= Astar; i.hasItem(); i++)
      degreelist.append (degree (i.getItem()));
 
    int extdeg= getDegOfExt (degreelist, degree (f));
 
    if (newuord.length() == 0) // no parameters
    {
      if (extdeg > 1)
      {
        CanonicalForm MIPO= generateMipo (extdeg);
        vminpoly= rootOf(MIPO);
      }
      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
      if (extdeg > 1)
        prune (vminpoly);
      return Factorlist;
    }
    else if (isInseparable(Astar) || derivZero) // inseparable case
    {
      Factorlist= SteelTrager (f, Astar);
      return Factorlist;
    }
    else // separable case
    {
      if (extdeg > 1)
      {
        CanonicalForm MIPO=generateMipo (extdeg);
        vminpoly= rootOf (MIPO);
      }
      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
      if (extdeg > 1)
        prune (vminpoly);
      return Factorlist;
    }
  }
  else // char 0
  {
    Variable vminpoly;
    Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factorlist;
  }
 
  return CFFList (CFFactor(f,1));
}

◆ 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.

{
  if ( f.inCoeffDomain() )
        return CFFList( f );
#ifndef NOASSERT
  Variable a;
  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
          ( const CanonicalForm & f, const Variable & alpha ) instead");
#endif
  //out_cf("factorize:",f,"==================================\n");
  if (! f.isUnivariate() ) // preprocess homog. polys
  {
    if ( singular_homog_flag && f.isHomogeneous())
    {
      Variable xn = get_max_degree_Variable(f);
      int d_xn = degree(f,xn);
      CFMap n;
      CanonicalForm F = compress(f(1,xn),n);
      CFFList Intermediatelist;
      Intermediatelist = factorize(F);
      CFFList Homoglist;
      CFFListIterator j;
      for ( j=Intermediatelist; j.hasItem(); j++ )
      {
        Homoglist.append(
            CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
      }
      CFFList Unhomoglist;
      CanonicalForm unhomogelem;
      for ( j=Homoglist; j.hasItem(); j++ )
      {
        unhomogelem= homogenize(j.getItem().factor(),xn);
        Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
        d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
      }
      if ( d_xn != 0 ) // have to append xn^(d_xn)
        Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
      if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
      return Unhomoglist;
    }
  }
  CFFList F;
  if ( getCharacteristic() > 0 )
  {
    if (f.isUnivariate())
    {
#ifdef HAVE_FLINT
#ifdef HAVE_NTL
      if (degree (f) < 300)
#endif
      {
        // use FLINT: char p, univariate
        nmod_poly_t f1;
        convertFacCF2nmod_poly_t (f1, f);
        nmod_poly_factor_t result;
        nmod_poly_factor_init (result);
        mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
        F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
        nmod_poly_factor_clear (result);
        nmod_poly_clear (f1);
        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
        return F;
      }
#endif
#ifdef HAVE_NTL
      { // NTL char 2, univariate
        if (getCharacteristic()==2)
        {
          // Specialcase characteristic==2
          if (fac_NTL_char != 2)
          {
            fac_NTL_char = 2;
            zz_p::init(2);
          }
          // convert to NTL using the faster conversion routine for characteristic 2
          GF2X f1=convertFacCF2NTLGF2X(f);
          // no make monic necessary in GF2
          //factorize
          vec_pair_GF2X_long factors;
          CanZass(factors,f1);
 
          // convert back to factory again using the faster conversion routine for vectors over GF2X
          F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
          if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
          return F;
        }
      }
#endif
#ifdef HAVE_NTL
      {
        // use NTL char p, univariate
        if (fac_NTL_char != getCharacteristic())
        {
          fac_NTL_char = getCharacteristic();
          zz_p::init(getCharacteristic());
        }
 
        // convert to NTL
        zz_pX f1=convertFacCF2NTLzzpX(f);
        zz_p leadcoeff = LeadCoeff(f1);
 
        //make monic
        f1=f1 / LeadCoeff(f1);
        // factorize
        vec_pair_zz_pX_long factors;
        CanZass(factors,f1);
 
        F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
        //test_cff(F,f);
        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
        return F;
      }
#endif
#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
      // Use Factory without NTL and without FLINT: char p, univariate
      {
        if ( isOn( SW_BERLEKAMP ) )
          F=FpFactorizeUnivariateB( f, issqrfree );
        else
          F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
        return F;
      }
#endif
    }
    else // char p, multivariate
    {
      if (CFFactory::gettype() == GaloisFieldDomain)
      {
        #if defined(HAVE_NTL)
        if (issqrfree)
        {
          CFList factors;
          Variable alpha;
          factors= GFSqrfFactorize (f);
          for (CFListIterator i= factors; i.hasItem(); i++)
            F.append (CFFactor (i.getItem(), 1));
        }
        else
        {
          Variable alpha;
          F= GFFactorize (f);
        }
        #else
        factoryError ("multivariate factorization over GF depends on NTL(missing)");
        return CFFList (CFFactor (f, 1));
        #endif
      }
      else
      {
        #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
        if (!isOn(SW_USE_FL_FAC_P))
        {
        #endif
        #if defined(HAVE_NTL)
          if (issqrfree)
          {
            CFList factors;
            Variable alpha;
            factors= FpSqrfFactorize (f);
            for (CFListIterator i= factors; i.hasItem(); i++)
              F.append (CFFactor (i.getItem(), 1));
            goto end_charp;
          }
          else
          {
            Variable alpha;
            F= FpFactorize (f);
            goto end_charp;
          }
        #endif
        #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
        }
        #endif
        #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
        nmod_mpoly_ctx_t ctx;
        nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
        nmod_mpoly_t Flint_f;
        nmod_mpoly_init(Flint_f,ctx);
        convFactoryPFlintMP(f,Flint_f,ctx,f.level());
        nmod_mpoly_factor_t factors;
        nmod_mpoly_factor_init(factors,ctx);
        int okay;
        if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
        else           okay=nmod_mpoly_factor(factors,Flint_f,ctx);
        nmod_mpoly_t fac;
        nmod_mpoly_init(fac,ctx);
        CanonicalForm cf_fac;
        int cf_exp;
        cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
        F.append(CFFactor(cf_fac,1));
        for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
        {
          nmod_mpoly_factor_get_base(fac,factors,i,ctx);
          cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
          cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
          F.append(CFFactor(cf_fac,cf_exp));
        }
        nmod_mpoly_factor_clear(factors,ctx);
        nmod_mpoly_clear(Flint_f,ctx);
        nmod_mpoly_ctx_clear(ctx);
        if (okay==0)
        {
          Off(SW_USE_FL_GCD_P);
          Off(SW_USE_FL_FAC_P);
          F=factorize(f,issqrfree);
          On(SW_USE_FL_GCD_P);
          On(SW_USE_FL_FAC_P);
        }
        #endif
        #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
        #ifndef HAVE_NTL
        factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
        return CFFList (CFFactor (f, 1));
        #endif
        #endif
      }
    }
  }
  else // char 0
  {
    bool on_rational = isOn(SW_RATIONAL);
    On(SW_RATIONAL);
    CanonicalForm cd = bCommonDen( f );
    CanonicalForm fz = f * cd;
    Off(SW_RATIONAL);
    if ( f.isUnivariate() )
    {
      CanonicalForm ic=icontent(fz);
      fz/=ic;
      if (fz.degree()==1)
      {
        F=CFFList(CFFactor(fz,1));
        F.insert(CFFactor(ic,1));
      }
      else
      #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503)  && (__FLINT_RELEASE!= 20600)
      {
        // FLINT 2.6.0 has a bug:
        // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
        // use FLINT: char 0, univariate
        fmpz_poly_t f1;
        convertFacCF2Fmpz_poly_t (f1, fz);
        fmpz_poly_factor_t result;
        fmpz_poly_factor_init (result);
        fmpz_poly_factor(result, f1);
        F= convertFLINTfmpz_poly_factor2FacCFFList (result, fz.mvar());
        fmpz_poly_factor_clear (result);
        fmpz_poly_clear (f1);
        if ( ! ic.isOne() )
        {
           // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
           //  first entry is in CoeffDomain
          CFFactor new_first( F.getFirst().factor() * ic );
          F.removeFirst();
          F.insert( new_first );
        }
      }
      goto end_char0;
      #elif defined(HAVE_NTL)
      {
        //use NTL
        ZZ c;
        vec_pair_ZZX_long factors;
        //factorize the converted polynomial
        factor(c,factors,convertFacCF2NTLZZX(fz));
 
        //convert the result back to Factory
        F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
        if ( ! ic.isOne() )
        {
           // according to convertNTLvec_pair_ZZX_long2FacCFFList
           //  first entry is in CoeffDomain
          CFFactor new_first( F.getFirst().factor() * ic );
          F.removeFirst();
          F.insert( new_first );
        }
      }
      goto end_char0;
      #else
      {
        //Use Factory without NTL: char 0, univariate
        F = ZFactorizeUnivariate( fz, issqrfree );
        goto end_char0;
      }
      #endif
    }
    else // multivariate,  char 0
    {
      #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
      if (isOn(SW_USE_FL_FAC_0))
      {
        On (SW_RATIONAL);
        fmpz_mpoly_ctx_t ctx;
        fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
        fmpz_mpoly_t Flint_f;
        fmpz_mpoly_init(Flint_f,ctx);
        convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
        fmpz_mpoly_factor_t factors;
        fmpz_mpoly_factor_init(factors,ctx);
        int rr;
        if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
        else           rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
        if (rr==0) printf("fail\n");
        fmpz_mpoly_t fac;
        fmpz_mpoly_init(fac,ctx);
        CanonicalForm cf_fac;
        int cf_exp;
        fmpz_t c;
        fmpz_init(c);
        fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
        cf_fac=convertFmpz2CF(c);
        fmpz_clear(c);
        F.append(CFFactor(cf_fac,1));
        for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
        {
           fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
           cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
           cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
           F.append(CFFactor(cf_fac,cf_exp));
        }
        fmpz_mpoly_factor_clear(factors,ctx);
        fmpz_mpoly_clear(Flint_f,ctx);
        fmpz_mpoly_ctx_clear(ctx);
        goto end_char0;
      }
      #endif
      #if defined(HAVE_NTL)
      On (SW_RATIONAL);
      if (issqrfree)
      {
        CFList factors= ratSqrfFactorize (fz);
        for (CFListIterator i= factors; i.hasItem(); i++)
          F.append (CFFactor (i.getItem(), 1));
      }
      else
      {
        F = ratFactorize (fz);
      }
      #endif
      #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
      #ifndef HAVE_NTL
      F=ZFactorizeMultivariate(fz, issqrfree);
      #endif
      #endif
    }
 
end_char0:
    if ( on_rational )
      On(SW_RATIONAL);
    else
      Off(SW_RATIONAL);
    if ( ! cd.isOne() )
    {
      CFFactor new_first( F.getFirst().factor() / cd );
      F.removeFirst();
      F.insert( new_first );
    }
  }
 
#if defined(HAVE_NTL)
end_charp:
#endif
  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
  return F;
}

◆ 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.

{
  if ( f.inCoeffDomain() )
    return CFFList( f );
  //out_cf("factorize:",f,"==================================\n");
  //out_cf("mipo:",getMipo(alpha),"\n");
 
  CFFList F;
  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
#ifndef NOASSERT
  Variable beta;
  if (hasFirstAlgVar(f, beta))
    ASSERT (beta == alpha, "f has an algebraic variable that \
                            does not coincide with alpha");
#endif
  int ch=getCharacteristic();
  if (ch>0)
  {
    if (f.isUnivariate())
    {
#ifdef HAVE_NTL
      if (/*getCharacteristic()*/ch==2)
      {
        // special case : GF2
 
        // remainder is two ==> nothing to do
 
        // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
        GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
        GF2E::init (minPo);
 
        // convert to NTL again using the faster conversion routines
        GF2EX f1;
        if (isPurePoly(f))
        {
          GF2X f_tmp=convertFacCF2NTLGF2X(f);
          f1=to_GF2EX(f_tmp);
        }
        else
          f1=convertFacCF2NTLGF2EX(f,minPo);
 
        // make monic (in Z/2(a))
        GF2E f1_coef=LeadCoeff(f1);
        MakeMonic(f1);
 
        // factorize using NTL
        vec_pair_GF2EX_long factors;
        CanZass(factors,f1);
 
        // return converted result
        F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
        return F;
      }
#endif
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
      {
        // use FLINT
        nmod_poly_t FLINTmipo, leadingCoeff;
        fq_nmod_ctx_t fq_con;
 
        nmod_poly_init (FLINTmipo, ch);
        nmod_poly_init (leadingCoeff, ch);
        convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
        fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        fq_nmod_poly_t FLINTF;
        convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
        fq_nmod_poly_factor_t res;
        fq_nmod_poly_factor_init (res, fq_con);
        fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
        F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
        F.insert (CFFactor (Lc (f), 1));
 
        fq_nmod_poly_factor_clear (res, fq_con);
        fq_nmod_poly_clear (FLINTF, fq_con);
        nmod_poly_clear (FLINTmipo);
        nmod_poly_clear (leadingCoeff);
        fq_nmod_ctx_clear (fq_con);
        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
        return F;
      }
#endif
#ifdef HAVE_NTL
      {
        // use NTL
        if (fac_NTL_char != ch)
        {
          fac_NTL_char = ch;
          zz_p::init(ch);
        }
 
        // set minimal polynomial in NTL
        zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
        zz_pE::init (minPo);
 
        // convert to NTL
        zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
        zz_pE leadcoeff= LeadCoeff(f1);
 
        //make monic
        f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
 
        // factorize
        vec_pair_zz_pEX_long factors;
        CanZass(factors,f1);
 
        // return converted result
        F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
        //test_cff(F,f);
        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
        return F;
      }
#endif
#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
      // char p, extension, univariate
      CanonicalForm c=Lc(f);
      CanonicalForm fc=f/c;
      F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
      F.insert (CFFactor (c, 1));
#endif
    }
    else // char p, multivariate
    {
      #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
        // use FLINT
        nmod_poly_t FLINTmipo;
        fq_nmod_ctx_t fq_con;
        fq_nmod_mpoly_ctx_t ctx;
 
        nmod_poly_init (FLINTmipo, ch);
        convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
 
        fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
        fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
 
        fq_nmod_mpoly_t FLINTF;
        fq_nmod_mpoly_init(FLINTF,ctx);
        convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
        fq_nmod_mpoly_factor_t res;
        fq_nmod_mpoly_factor_init (res, ctx);
        fq_nmod_mpoly_factor (res, FLINTF, ctx);
        F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
        //F.insert (CFFactor (Lc (f), 1));
 
        fq_nmod_mpoly_factor_clear (res, ctx);
        fq_nmod_mpoly_clear (FLINTF, ctx);
        nmod_poly_clear (FLINTmipo);
        fq_nmod_mpoly_ctx_clear (ctx);
        fq_nmod_ctx_clear (fq_con);
        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
        return F;
      #elif defined(HAVE_NTL)
      F= FqFactorize (f, alpha);
      #else
      factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
      return CFFList (CFFactor (f, 1));
      #endif
    }
  }
  else // Q(a)[x]
  {
    if (f.isUnivariate())
    {
      F= AlgExtFactorize (f, alpha);
    }
    else //Q(a)[x1,...,xn]
    {
      #if defined(HAVE_NTL) || defined(HAVE_FLINT)
      F= ratFactorize (f, alpha);
      #else
      factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
      return CFFList (CFFactor (f, 1));
      #endif
    }
  }
  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
  return F;
}

◆ factoryError_intern()

void factoryError_intern ( const char * s )

Definition at line 75 of file cf_util.cc.

{
  fputs(s,stderr);
  abort();
}

◆ factoryrandom()

int factoryrandom ( int n )

random integers with abs less than n

Definition at line 180 of file cf_random.cc.

{
    if ( n == 0 )
        return (int)ranGen.generate();
    else
        return ranGen.generate() % n;
}

◆ factoryseed()

void FACTORY_PUBLIC factoryseed ( int s )

random seed initializer

Definition at line 189 of file cf_random.cc.

{
    ranGen.seed( s );
 
#ifdef HAVE_FLINT
    flint_randinit(FLINTrandom);
#endif
}

◆ Farey()

CanonicalForm Farey	(	const CanonicalForm &	f,
		const CanonicalForm &	q
	)

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.

{
  int is_rat=isOn(SW_RATIONAL);
  Off(SW_RATIONAL);
  Variable x = f.mvar();
  CanonicalForm result = 0;
  CanonicalForm c;
  CFIterator i;
#ifdef HAVE_FLINT
  fmpz_t FLINTq;
  fmpz_init(FLINTq);
  convertCF2initFmpz(FLINTq,q);
  fmpz_t FLINTc;
  fmpz_init(FLINTc);
  fmpq_t FLINTres;
  fmpq_init(FLINTres);
#elif defined(HAVE_NTL)
  ZZ NTLq= convertFacCF2NTLZZ (q);
  ZZ bound;
  SqrRoot (bound, NTLq/2);
#else
  factoryError("NTL/FLINT missing:Farey");
#endif
  for ( i = f; i.hasTerms(); i++ )
  {
    c = i.coeff();
    if ( c.inCoeffDomain())
    {
#ifdef HAVE_FLINT
      if (c.inZ())
      {
        convertCF2initFmpz(FLINTc,c);
        fmpq_reconstruct_fmpz(FLINTres,FLINTc,FLINTq);
        result += power (x, i.exp())*(convertFmpq2CF(FLINTres));
      }
#elif defined(HAVE_NTL)
      if (c.inZ())
      {
        ZZ NTLc= convertFacCF2NTLZZ (c);
        bool lessZero= (sign (NTLc) == -1);
        if (lessZero)
          NTL::negate (NTLc, NTLc);
        ZZ NTLnum, NTLden;
        if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
        {
          if (lessZero)
            NTL::negate (NTLnum, NTLnum);
          CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
          CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
          On (SW_RATIONAL);
          result += power (x, i.exp())*(num/den);
          Off (SW_RATIONAL);
        }
      }
#else
      if (c.inZ())
        result += power (x, i.exp()) * Farey_n(c,q);
#endif
      else
        result += power( x, i.exp() ) * Farey(c,q);
    }
    else
      result += power( x, i.exp() ) * Farey(c,q);
  }
  if (is_rat) On(SW_RATIONAL);
#ifdef HAVE_FLINT
  fmpq_clear(FLINTres);
  fmpz_clear(FLINTc);
  fmpz_clear(FLINTq);
#endif
  return result;
}

◆ 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.

{
    // trivial cases
    if ( g.isZero() )
        return true;
    else if ( f.isZero() )
        return false;
 
    if ( (f.inCoeffDomain() || g.inCoeffDomain())
         && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
             || (getCharacteristic() > 0) ))
    {
        // if we are in a field all elements not equal to zero are units
        if ( f.inCoeffDomain() )
            return true;
        else
            // g.inCoeffDomain()
            return false;
    }
 
    // we may assume now that both levels either equal LEVELBASE
    // or are greater zero
    int fLevel = f.level();
    int gLevel = g.level();
    if ( (gLevel > 0) && (fLevel == gLevel) )
        // f and g are polynomials in the same main variable
        if ( degree( f ) <= degree( g )
             && fdivides( f.tailcoeff(), g.tailcoeff() )
             && fdivides( f.LC(), g.LC() ) )
        {
            CanonicalForm q, r;
            return divremt( g, f, q, r ) && r.isZero();
        }
        else
            return false;
    else if ( gLevel < fLevel )
        // g is a coefficient w.r.t. f
        return false;
    else
    {
        // either f is a coefficient w.r.t. polynomial g or both
        // f and g are from a base domain (should be Z or Z/p^n,
        // then)
        CanonicalForm q, r;
        return divremt( g, f, q, r ) && r.isZero();
    }
}

◆ 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.

{
    quot= 0;
    // trivial cases
    if ( g.isZero() )
        return true;
    else if ( f.isZero() )
        return false;
 
    if ( (f.inCoeffDomain() || g.inCoeffDomain())
         && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
             || (getCharacteristic() > 0) ))
    {
        // if we are in a field all elements not equal to zero are units
        if ( f.inCoeffDomain() )
        {
            quot= g/f;
            return true;
        }
        else
            // g.inCoeffDomain()
            return false;
    }
 
    // we may assume now that both levels either equal LEVELBASE
    // or are greater zero
    int fLevel = f.level();
    int gLevel = g.level();
    if ( (gLevel > 0) && (fLevel == gLevel) )
        // f and g are polynomials in the same main variable
        if ( degree( f ) <= degree( g )
             && fdivides( f.tailcoeff(), g.tailcoeff() )
             && fdivides( f.LC(), g.LC() ) )
        {
            CanonicalForm q, r;
            if (divremt( g, f, q, r ) && r.isZero())
            {
              quot= q;
              return true;
            }
            else
              return false;
        }
        else
            return false;
    else if ( gLevel < fLevel )
        // g is a coefficient w.r.t. f
        return false;
    else
    {
        // either f is a coefficient w.r.t. polynomial g or both
        // f and g are from a base domain (should be Z or Z/p^n,
        // then)
        CanonicalForm q, r;
        if (divremt( g, f, q, r ) && r.isZero())
        {
          quot= q;
          return true;
        }
        else
          return false;
    }
}

◆ gcd()

CanonicalForm FACTORY_PUBLIC gcd	(	const CanonicalForm &	f,
		const CanonicalForm &	g
	)

Definition at line 685 of file cf_gcd.cc.

{
    bool b = f.isZero();
    if ( b || g.isZero() )
    {
        if ( b )
            return abs( g );
        else
            return abs( f );
    }
    if ( f.inPolyDomain() || g.inPolyDomain() )
    {
        if ( f.mvar() != g.mvar() )
        {
            if ( f.mvar() > g.mvar() )
                return cf_content( f, g );
            else
                return cf_content( g, f );
        }
        if (isOn(SW_USE_QGCD))
        {
          Variable m;
          if (
          (getCharacteristic() == 0) &&
          (hasFirstAlgVar(f,m) || hasFirstAlgVar(g,m))
          )
          {
            bool on_rational = isOn(SW_RATIONAL);
            CanonicalForm r=QGCD(f,g);
            On(SW_RATIONAL);
            CanonicalForm cdF = bCommonDen( r );
            if (!on_rational) Off(SW_RATIONAL);
            return cdF*r;
          }
        }
 
        if ( f.inExtension() && getReduce( f.mvar() ) )
            return CanonicalForm(1);
        else
        {
            if ( fdivides( f, g ) )
                return abs( f );
            else  if ( fdivides( g, f ) )
                return abs( g );
            if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
            {
                CanonicalForm d;
                d = gcd_poly( f, g );
                return abs( d );
            }
            else
            {
                CanonicalForm cdF = bCommonDen( f );
                CanonicalForm cdG = bCommonDen( g );
                CanonicalForm F = f * cdF, G = g * cdG;
                Off( SW_RATIONAL );
                CanonicalForm l = gcd_poly( F, G );
                On( SW_RATIONAL );
                return abs( l );
            }
        }
    }
    if ( f.inBaseDomain() && g.inBaseDomain() )
        return bgcd( f, g );
    else
        return 1;
}

◆ gcd_poly()

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

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.

{
  CanonicalForm fc, gc;
  bool fc_isUnivariate=f.isUnivariate();
  bool gc_isUnivariate=g.isUnivariate();
  bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
  fc = f;
  gc = g;
  int ch=getCharacteristic();
  if ( ch != 0 )
  {
    if (0) {} // dummy, to be able to build without NTL and FLINT
    #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
    if ( isOn( SW_USE_FL_GCD_P)
    && (CFFactory::gettype() != GaloisFieldDomain)
    #ifdef HAVE_NTL
    && (ch>10) // if we have NTL: it is better for char <11
    #endif
    &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
    {
      return gcdFlintMP_Zp(fc,gc);
    }
    #endif
    #ifdef HAVE_NTL
    if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
    {
      fc= EZGCD_P (fc, gc);
    }
    #endif
    #if defined(HAVE_NTL) || defined(HAVE_FLINT)
    else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
    {
      Variable a;
      if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
        fc=modGCDFq (fc, gc, a);
      else if (CFFactory::gettype() == GaloisFieldDomain)
        fc=modGCDGF (fc, gc);
      else
        fc=modGCDFp (fc, gc);
    }
    #endif
    else
    fc = gcd_poly_p( fc, gc );
  }
  else if (!fc_and_gc_Univariate) /* && char==0*/
  {
    #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
    if (( isOn( SW_USE_FL_GCD_0) )
    &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
    {
      return gcdFlintMP_QQ(fc,gc);
    }
    else
    #endif
    #ifdef HAVE_NTL
    if ( isOn( SW_USE_EZGCD ) )
      fc= ezgcd (fc, gc);
    else
    #endif
    #if defined(HAVE_NTL) || defined(HAVE_FLINT)
    if (isOn(SW_USE_CHINREM_GCD))
      fc = modGCDZ( fc, gc);
    else
    #endif
    {
       fc = gcd_poly_0( fc, gc );
    }
  }
  else
  {
    fc = gcd_poly_0( fc, gc );
  }
  if ((ch>0)&&(!hasAlgVar(fc))) fc/=fc.lc();
  return fc;
}

◆ 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.

{
  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
  int max=0, maxlevel=0, n=level(f);
  for ( int i=1; i<=n; i++ )
  {
    if (degree(f,Variable(i)) >= max)
    {
      max= degree(f,Variable(i)); maxlevel= i;
    }
  }
  return Variable(maxlevel);
}

◆ get_Terms()

CFList get_Terms ( const CanonicalForm & f )

Definition at line 289 of file cf_factor.cc.

                                    {
  CFList result,dummy,dummy2;
  CFIterator i;
  CFListIterator j;
 
  if ( getNumVars(f) == 0 ) result.append(f);
  else{
    Variable _x(level(f));
    for ( i=f; i.hasTerms(); i++ ){
      getTerms(i.coeff(), 1, dummy);
      for ( j=dummy; j.hasItem(); j++ )
        result.append(j.getItem() * power(_x, i.exp()));
 
      dummy= dummy2; // have to initalize new
    }
  }
  return result;
}

◆ getCharacteristic()

int FACTORY_PUBLIC getCharacteristic ( )

Definition at line 70 of file cf_char.cc.

{
    return theCharacteristic;
}

◆ getDefaultExtName()

char getDefaultExtName ( )

Definition at line 249 of file variable.cc.

{
    return default_name_ext;
}

◆ getDefaultVarName()

char getDefaultVarName ( )

Definition at line 244 of file variable.cc.

{
    return default_name;
}

◆ getGFDegree()

int getGFDegree ( )

Definition at line 75 of file cf_char.cc.

{
    //ASSERT( theDegree > 0, "not in GF(q)" );
    return theDegree;
}

◆ getGFGenerator()

CanonicalForm getGFGenerator ( )

Definition at line 81 of file cf_char.cc.

{
    ASSERT( theDegree > 1, "not in GF(q)" );
    return int2imm_gf( 1 );
}

◆ getMipo()

CanonicalForm getMipo	(	const Variable &	alpha,
		const Variable &	x
	)

Definition at line 207 of file variable.cc.

{
    ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
    return CanonicalForm( algextensions[-alpha.level()].mipo()->copyObject() )(x,alpha);
}

◆ getNumVars()

int getNumVars ( const CanonicalForm & f )

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

Definition at line 314 of file cf_ops.cc.

{
    int n;
    if ( f.inCoeffDomain() )
        return 0;
    else  if ( (n = f.level()) == 1 )
        return 1;
    else
    {
        int * vars = NEW_ARRAY(int, n+1);
        int i;
        for ( i = n-1; i >=0; i-- ) vars[i] = 0;
 
        // look for variables
        for ( CFIterator I = f; I.hasTerms(); ++I )
            fillVarsRec( I.coeff(), vars );
 
        // count them
        int m = 0;
        for ( i = 1; i < n; i++ )
            if ( vars[i] != 0 ) m++;
 
        DELETE_ARRAY(vars);
        // do not forget to count our own variable
        return m+1;
    }
}

◆ 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.

{
  if ( getNumVars(f) == 0 ) result.append(f*t);
  else{
    Variable x(level(f));
    for ( CFIterator i=f; i.hasTerms(); i++ )
      getTerms( i.coeff(), t*power(x,i.exp()), result);
  }
}

◆ getVars()

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.

{
    int n;
    if ( f.inCoeffDomain() )
        return 1;
    else  if ( (n = f.level()) == 1 )
        return Variable( 1 );
    else
    {
        int * vars = NEW_ARRAY(int, n+1);
        int i;
        for ( i = n; i >= 0; i-- ) vars[i] = 0;
 
        // look for variables
        for ( CFIterator I = f; I.hasTerms(); ++I )
            fillVarsRec( I.coeff(), vars );
 
        // multiply them all
        CanonicalForm result = 1;
        for ( i = n; i > 0; i-- )
            if ( vars[i] != 0 ) result *= Variable( i );
 
        DELETE_ARRAY(vars);
        // do not forget our own variable
        return f.mvar() * result;
    }
}

◆ gf_gf2ff() [1/2]

int gf_gf2ff ( int a )

Definition at line 231 of file gfops.cc.

{
    if ( gf_iszero( a ) )
        return 0;
    else
    {
        // starting from z^0=1, step through the table
        // counting the steps until we hit z^a or z^0
        // again.  since we are working in char(p), the
        // latter is guaranteed to be fulfilled.
        int i = 0, ff = 1;
        do
        {
            if ( i == a )
                return ff;
            ff++;
            i = gf_table[i];
        } while ( i != 0 );
        return -1;
    }
}

◆ gf_gf2ff() [2/2]

long gf_gf2ff ( long a )

Definition at line 209 of file gfops.cc.

{
    if ( gf_iszero( a ) )
        return 0;
    else
    {
        // starting from z^0=1, step through the table
        // counting the steps until we hit z^a or z^0
        // again.  since we are working in char(p), the
        // latter is guaranteed to be fulfilled.
        long i = 0, ff = 1;
        do
        {
            if ( i == a )
                return ff;
            ff++;
            i = gf_table[i];
        } while ( i != 0 );
        return -1;
    }
}

◆ gf_isff() [1/2]

bool gf_isff ( int a )

Definition at line 264 of file gfops.cc.

{
    if ( gf_iszero( a ) )
        return true;
    else
    {
        // z^a in GF(p) iff (z^a)^p-1=1
        return gf_isone( gf_power( a, gf_p - 1 ) );
    }
}

◆ gf_isff() [2/2]

bool gf_isff ( long a )

Definition at line 253 of file gfops.cc.

{
    if ( gf_iszero( a ) )
        return true;
    else
    {
        // z^a in GF(p) iff (z^a)^p-1=1
        return gf_isone( gf_power( a, gf_p - 1 ) );
    }
}

◆ gf_value()

int gf_value ( const CanonicalForm & f )

Definition at line 60 of file singext.cc.

{
    InternalCF * ff = f.getval();
    return ((intptr_t)ff) >>2;
}

◆ gmp_denominator()

void FACTORY_PUBLIC gmp_denominator	(	const CanonicalForm &	f,
		mpz_ptr	result
	)

Definition at line 40 of file singext.cc.

{
    InternalCF * ff = f.getval();
    ASSERT( ! is_imm( ff ), "illegal type" );
    if ( ff->levelcoeff() == IntegerDomain )
    {
        mpz_init_set_si( result, 1 );
        ff->deleteObject();
    }
    else  if ( ff->levelcoeff() == RationalDomain )
    {
        mpz_init_set( result, (InternalRational::MPQDEN( ff )) );
        ff->deleteObject();
    }
    else
    {
        ASSERT( 0, "illegal type" );
    }
}

◆ gmp_numerator()

void FACTORY_PUBLIC gmp_numerator	(	const CanonicalForm &	f,
		mpz_ptr	result
	)

Definition at line 20 of file singext.cc.

{
    InternalCF * ff = f.getval();
    ASSERT( ! is_imm( ff ), "illegal type" );
    if ( ff->levelcoeff() == IntegerDomain )
    {
        mpz_init_set( result, (InternalInteger::MPI( ff )) );
        ff->deleteObject();
    }
    else  if ( ff->levelcoeff() == RationalDomain )
    {
        mpz_init_set( result, (InternalRational::MPQNUM( ff )) );
        ff->deleteObject();
    }
    else
    {
        ASSERT( 0, "illegal type" );
    }
}

◆ 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.

{
  if( f.inBaseDomain() ) // f has NO alg. variable
    return false;
  if( f.level()<0 ) // f has only alg. vars, so take the first one
  {
    a = f.mvar();
    return true;
  }
  for(CFIterator i=f; i.hasTerms(); i++)
    if( hasFirstAlgVar( i.coeff(), a ))
      return true; // 'a' is already set
  return false;
}

◆ hasMipo()

bool hasMipo ( const Variable & alpha )

Definition at line 226 of file variable.cc.

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

◆ head()

CanonicalForm head ( const CanonicalForm & f )

inline

Definition at line 501 of file factory.h.

{
    if ( f.level() > 0 )
        return power( f.mvar(), f.degree() ) * f.LC();
    else
        return f;
}

◆ headdegree()

int headdegree ( const CanonicalForm & f )

inline

Definition at line 510 of file factory.h.

510{ return totaldegree( head( f ) ); }

totaldegree

int totaldegree(const CanonicalForm &f)

int totaldegree ( const CanonicalForm & f )

Definition: cf_ops.cc:523

head

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.

{
#if 0
  int maxdeg=totaldegree(f), deg;
  CFIterator i;
  CanonicalForm elem, result(0);
 
  for (i=f; i.hasTerms(); i++)
  {
    elem= i.coeff()*power(f.mvar(),i.exp());
    deg = totaldegree(elem);
    if ( deg < maxdeg )
      result += elem * power(x,maxdeg-deg);
    else
      result+=elem;
  }
  return result;
#else
  CFList Newlist, Termlist= get_Terms(f);
  int maxdeg=totaldegree(f), deg;
  CFListIterator i;
  CanonicalForm elem, result(0);
 
  for (i=Termlist; i.hasItem(); i++)
  {
    elem= i.getItem();
    deg = totaldegree(elem);
    if ( deg < maxdeg )
      Newlist.append(elem * power(x,maxdeg-deg));
    else
      Newlist.append(elem);
  }
  for (i=Newlist; i.hasItem(); i++) // rebuild
    result += i.getItem();
 
  return result;
#endif
}

◆ 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.

{
#if 0
  int maxdeg=totaldegree(f), deg;
  CFIterator i;
  CanonicalForm elem, result(0);
 
  for (i=f; i.hasTerms(); i++)
  {
    elem= i.coeff()*power(f.mvar(),i.exp());
    deg = totaldegree(elem);
    if ( deg < maxdeg )
      result += elem * power(x,maxdeg-deg);
    else
      result+=elem;
  }
  return result;
#else
  CFList Newlist, Termlist= get_Terms(f);
  int maxdeg=totaldegree(f), deg;
  CFListIterator i;
  CanonicalForm elem, result(0);
 
  for (i=Termlist; i.hasItem(); i++)
  {
    elem= i.getItem();
    deg = totaldegree(elem,v1,v2);
    if ( deg < maxdeg )
      Newlist.append(elem * power(x,maxdeg-deg));
    else
      Newlist.append(elem);
  }
  for (i=Newlist; i.hasItem(); i++) // rebuild
    result += i.getItem();
 
  return result;
#endif
}

◆ icontent()

CanonicalForm FACTORY_PUBLIC icontent ( const CanonicalForm & f )

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.

{
    return icontent( f, 0 );
}

◆ igcd()

int igcd	(	int	a,
		int	b
	)

Definition at line 56 of file cf_util.cc.

{
    if ( a < 0 ) a = -a;
    if ( b < 0 ) b = -b;
 
    int c;
 
    while ( b != 0 )
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

◆ 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.

{
    int prod = 1;
 
    while ( m != 0 )
    {
        if ( m % 2 != 0 )
            prod *= b;
        m /= 2;
        if ( m != 0 )
            b *= b;
    }
    return prod;
}

◆ irrCharSeries()

ListCFList FACTORY_PUBLIC irrCharSeries ( const CFList & PS )

irreducible characteristic series

Definition at line 568 of file cfCharSets.cc.

{
  CanonicalForm reducible, reducible2;
  CFList qs, cs, factorset, is, ts, L;
  CanonicalForm sqrf;
  CFFList sqrfFactors;
  CFFListIterator iter2;
  for (CFListIterator iter= PS; iter.hasItem(); iter++)
  {
    sqrf= 1;
    sqrfFactors= sqrFree (iter.getItem());
    if (sqrfFactors.getFirst().factor().inCoeffDomain())
      sqrfFactors.removeFirst();
    for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
      sqrf *= iter2.getItem().factor();
    sqrf= normalize (sqrf);
    L= Union (CFList (sqrf), L);
  }
 
  ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
 
  int nr_of_iteration= 0, indexRed, highestlevel= 0;
 
  for (CFListIterator iter= PS; iter.hasItem(); iter++)
  {
    if (level (iter.getItem()) > highestlevel)
      highestlevel= level(iter.getItem());
  }
 
  while (!qhi.isEmpty())
  {
    sortListCFList (qhi);
 
    qs= qhi.getFirst();
 
    ListCFList ppi1,ppi2;
    select (ppi, qs.length(), ppi1, ppi2);
 
    inplaceUnion (ppi2, qqi);
 
    if (nr_of_iteration == 0)
    {
      nr_of_iteration += 1;
      ppi= ListCFList();
    }
    else
    {
      nr_of_iteration += 1;
      ppi= Union (ppi1, ListCFList (qs));
    }
 
    StoreFactors StoredFactors;
    if (qs.length() - 3 < highestlevel)
      cs= modCharSet (qs, StoredFactors, false);
    else
      cs= charSetN (qs);
    cs= removeContent (cs, StoredFactors);
 
    factorset= StoredFactors.FS1;
 
    if (!cs.isEmpty() && cs.getFirst().level() > 0)
    {
      ts= irredAS (cs, indexRed, reducible);
 
      if (indexRed <= 0) // irreducible
      {
        if (!isSubset (cs,qs))
          cs= charSetViaCharSetN (Union (qs,cs));
        if (!find (pi, cs))
        {
          pi= Union (ListCFList (cs), pi);
          if (cs.getFirst().level() > 0)
          {
            ts= irredAS (cs, indexRed, reducible);
 
            if (indexRed <= 0) //irreducible
            {
              qsi= Union (ListCFList(cs), qsi);
              if (cs.length() == highestlevel)
                is= factorPSet (factorset);
              else
                is= Union (factorsOfInitials (cs), factorPSet (factorset));
              iss= adjoin (is, qs, qqi);
            }
          }
          else
            iss= adjoin (factorPSet (factorset), qs, qqi);
        }
        else
          iss= adjoin (factorPSet (factorset), qs, qqi);
      }
 
      if (indexRed > 0)
      {
        is= factorPSet (factorset);
        if (indexRed > 1)
        {
          CFList cst;
          for (CFListIterator i= cs ; i.hasItem(); i++)
          {
            if (i.getItem() == reducible)
              break;
            else
              cst.append (i.getItem());
          }
          is= Union (factorsOfInitials (Union (cst,  CFList (reducible))), is);
          iss= Union (adjoinb (ts, qs, qqi, cst), adjoin (is, qs, qqi));
        }
        else
          iss= adjoin (Union (is, ts), qs, qqi);
      }
    }
    else
      iss= adjoin (factorPSet (factorset), qs, qqi);
    if (qhi.length() > 1)
    {
      qhi.removeFirst();
      qhi= Union (iss, qhi);
    }
    else
      qhi= iss;
  }
  if (!qsi.isEmpty())
    return contract (qsi);
  return ListCFList(CFList (1)) ;
}

◆ is_imm()

int is_imm ( const InternalCF *const ptr )

inline

Definition at line 215 of file factory.h.

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

◆ isOn()

bool FACTORY_PUBLIC isOn ( int sw )

switches

Definition at line 1971 of file canonicalform.cc.

{
    return cf_glob_switches.isOn( sw );
}

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm & f )

Definition at line 244 of file cf_factor.cc.

{
  if (f.level()<=0) return false;
  for (CFIterator i=f;i.hasTerms();i++)
  {
    if (!(i.coeff().inBaseDomain())) return false;
  }
  return true;
}

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm & f )

Definition at line 234 of file cf_factor.cc.

{
  if (f.inBaseDomain()) return true;
  if (f.level()<0) return false;
  for (CFIterator i=f;i.hasTerms();i++)
  {
    if (!isPurePoly_m(i.coeff())) return false;
  }
  return true;
}

◆ 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 FACTORY_PUBLIC lcm	(	const CanonicalForm &	f,
		const CanonicalForm &	g
	)

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.

{
    if ( f.isZero() || g.isZero() )
        return 0;
    else
        return ( f / gcd( f, g ) ) * g;
}

◆ 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.

{
  ASSERT (n >= 0, "cannot left shift by negative number");
  if (F.inBaseDomain())
    return F;
  if (n == 0)
    return F;
  Variable x=F.mvar();
  CanonicalForm result= 0;
  for (CFIterator i= F; i.hasTerms(); i++)
    result += i.coeff()*power (x, i.exp()*n);
  return result;
}

◆ 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.

{
    typedef int* int_ptr;
 
    if ( ! matrix_in_Z( M ) ) {
        int nrows = M.rows(), ncols = M.columns();
        int i, j, k;
        CanonicalForm rowpivot, pivotrecip;
        // triangularization
        for ( i = 1; i <= nrows; i++ ) {
            //find "pivot"
            for (j = i; j <= nrows; j++ )
                if ( M(j,i) != 0 ) break;
            if ( j > nrows ) return false;
            if ( j != i )
                M.swapRow( i, j );
            pivotrecip = 1 / M(i,i);
            for ( j = 1; j <= ncols; j++ )
                M(i,j) *= pivotrecip;
            for ( j = i+1; j <= nrows; j++ ) {
                rowpivot = M(j,i);
                if ( rowpivot == 0 ) continue;
                for ( k = i; k <= ncols; k++ )
                    M(j,k) -= M(i,k) * rowpivot;
            }
        }
        // matrix is now upper triangular with 1s down the diagonal
        // back-substitute
        for ( i = nrows-1; i > 0; i-- ) {
            for ( j = nrows+1; j <= ncols; j++ ) {
                for ( k = i+1; k <= nrows; k++ )
                    M(i,j) -= M(k,j) * M(i,k);
            }
        }
        return true;
    }
    else {
        int rows = M.rows(), cols = M.columns();
        CFMatrix MM( rows, cols );
        int ** mm = new int_ptr[rows];
        CanonicalForm Q, Qhalf, mnew, qnew, B;
        int i, j, p, pno;
        bool ok;
 
        // initialize room to hold the result and the result mod p
        for ( i = 0; i < rows; i++ ) {
            mm[i] = new int[cols];
        }
 
        // calculate the bound for the result
        B = bound( M );
        DEBOUTLN( cerr, "bound = " <<  B );
 
        // find a first solution mod p
        pno = 0;
        do {
            DEBOUTSL( cerr );
            DEBOUT( cerr, "trying prime(" << pno << ") = " );
            p = cf_getBigPrime( pno );
            DEBOUT( cerr, p );
            DEBOUTENDL( cerr );
            setCharacteristic( p );
            // map matrix into char p
            for ( i = 1; i <= rows; i++ )
                for ( j = 1; j <= cols; j++ )
                    mm[i-1][j-1] = mapinto( M(i,j) ).intval();
            // solve mod p
            ok = solve( mm, rows, cols );
            pno++;
        } while ( ! ok );
 
        // initialize the result matrix with first solution
        setCharacteristic( 0 );
        for ( i = 1; i <= rows; i++ )
            for ( j = rows+1; j <= cols; j++ )
                MM(i,j) = mm[i-1][j-1];
 
        // Q so far
        Q = p;
        while ( Q < B && pno < cf_getNumBigPrimes() ) {
            do {
                DEBOUTSL( cerr );
                DEBOUT( cerr, "trying prime(" << pno << ") = " );
                p = cf_getBigPrime( pno );
                DEBOUT( cerr, p );
                DEBOUTENDL( cerr );
                setCharacteristic( p );
                for ( i = 1; i <= rows; i++ )
                    for ( j = 1; j <= cols; j++ )
                        mm[i-1][j-1] = mapinto( M(i,j) ).intval();
                // solve mod p
                ok = solve( mm, rows, cols );
                pno++;
            } while ( ! ok );
            // found a solution mod p
            // now chinese remainder it to a solution mod Q*p
            setCharacteristic( 0 );
            for ( i = 1; i <= rows; i++ )
                for ( j = rows+1; j <= cols; j++ )
                {
                    chineseRemainder( MM[i][j], Q, CanonicalForm(mm[i-1][j-1]), CanonicalForm(p), mnew, qnew );
                    MM(i, j) = mnew;
                }
            Q = qnew;
        }
        if ( pno == cf_getNumBigPrimes() )
            fuzzy_result = true;
        else
            fuzzy_result = false;
        // store the result in M
        Qhalf = Q / 2;
        for ( i = 1; i <= rows; i++ ) {
            for ( j = rows+1; j <= cols; j++ )
                if ( MM(i,j) > Qhalf )
                    M(i,j) = MM(i,j) - Q;
                else
                    M(i,j) = MM(i,j);
            delete [] mm[i-1];
        }
        delete [] mm;
        return ! fuzzy_result;
    }
}

◆ make_cf() [1/2]

CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n )

Definition at line 66 of file singext.cc.

{
    return CanonicalForm( CFFactory::basic( n ) );
}

◆ 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.

{
    return CanonicalForm( CFFactory::rational( n, d, normalize ) );
}

◆ make_cf_from_gf()

CanonicalForm make_cf_from_gf ( const int z )

Definition at line 76 of file singext.cc.

{
    return CanonicalForm(int2imm_gf(z));
}

◆ mapdomain()

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

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.

{
    if ( f.inBaseDomain() )
        return mf( f );
    else
    {
        CanonicalForm result = 0;
        CFIterator i;
        Variable x = f.mvar();
        for ( i = f; i.hasTerms(); i++ )
            result += power( x, i.exp() ) * mapdomain( i.coeff(), mf );
        return result;
    }
}

◆ 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 )

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.

{
    if ( f.inBaseDomain() )
        return abs( f );
    else {
        CanonicalForm result = 0;
        for ( CFIterator i = f; i.hasTerms(); i++ ) {
            CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
            if ( coeffMaxNorm > result )
                result = coeffMaxNorm;
        }
        return result;
    }
}

◆ mod()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod	(	const CanonicalForm &	,
		const CanonicalForm &
	)

◆ modCharSet() [1/2]

CFList modCharSet	(	const CFList &	PS,
		bool	removeContents
	)

Definition at line 404 of file cfCharSets.cc.

{
  StoreFactors tmp;
  return modCharSet (PS, tmp, removeContents);
}

◆ modCharSet() [2/2]

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

modified medial set

Definition at line 284 of file cfCharSets.cc.

{
  CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
  CFListIterator i;
  CanonicalForm r, cF;
  bool noRemainder= true;
  StoreFactors StoredFactors2;
 
  QS= uniGcd (L);
 
  while (!RS.isEmpty())
  {
    noRemainder= true;
    CSet= basicSet (QS);
 
    initial= factorsOfInitials (CSet);
 
    StoredFactors2.FS1= StoredFactors.FS1;
    StoredFactors2.FS2= Union (StoredFactors2.FS2, initial);
 
    RS= CFList();
 
    if (CSet.length() > 0 && CSet.getFirst().level() > 0)
    {
      tmp= Difference (QS, CSet);
 
      for (i= tmp; i.hasItem(); i++)
      {
        r= Prem (i.getItem(), CSet);
        if (!r.isZero())
        {
          noRemainder= false;
          if (removeContents)
          {
            removeContent (r, cF);
 
            if (!cF.isZero())
              contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead
          }
 
          removeFactors (r, StoredFactors2, removedFactors);
          StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors);
          StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors);
 
          removedFactors= CFList();
 
          RS= Union (RS, CFList (r));
        }
      }
 
      if (removeContents && !noRemainder)
      {
        StoredFactors.FS1= Union (StoredFactors2.FS1, contents);
        StoredFactors.FS2= StoredFactors2.FS2;
      }
      else
        StoredFactors= StoredFactors2;
 
      QS= Union (CSet, RS);
 
      contents= CFList();
      removedFactors= CFList();
    }
    else
      StoredFactors= StoredFactors2;
  }
 
  return CSet;
}

◆ 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(); }

Variable::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.

{
  Varlist reorder= neworder (PolyList);
  CFList output;
 
  for (VarlistIterator i=reorder; i.hasItem(); i++)
    output.append (CanonicalForm (i.getItem()));
 
  return output;
}

◆ neworderint()

IntList FACTORY_PUBLIC neworderint ( const CFList & PolyList )

Definition at line 88 of file cfCharSets.cc.

{
  Varlist reorder= neworder (PolyList);
  IntList output;
 
  for (VarlistIterator i= reorder; i.hasItem(); i++)
    output.append (level (i.getItem()));
 
  return output;
}

◆ 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.

{
    cf_glob_switches.Off( sw );
}

◆ On()

void FACTORY_PUBLIC On ( int sw )

switches

Definition at line 1957 of file canonicalform.cc.

{
    cf_glob_switches.On( sw );
}

◆ operator%()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator%	(	const CanonicalForm &	,
		const CanonicalForm &
	)

◆ operator*()

CF_INLINE CanonicalForm operator*	(	const CanonicalForm &	lhs,
		const CanonicalForm &	rhs
	)

See also: CanonicalForm::operator *=()

Definition at line 524 of file cf_inline.cc.

{
    CanonicalForm result( lhs );
    result *= rhs;
    return result;
}

◆ 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.

{
    CanonicalForm result( lhs );
    result += rhs;
    return result;
}

◆ operator-()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator-	(	const CanonicalForm &	,
		const CanonicalForm &
	)

◆ operator/()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator/	(	const CanonicalForm &	,
		const CanonicalForm &
	)

◆ power() [1/2]

CanonicalForm FACTORY_PUBLIC power	(	const CanonicalForm &	f,
		int	n
	)

exponentiation

Definition at line 1896 of file canonicalform.cc.

{
  ASSERT( n >= 0, "illegal exponent" );
  if ( f.isZero() )
    return CanonicalForm(0L);
  else  if ( f.isOne() )
    return f;
  else  if ( f == -1 )
  {
    if ( n % 2 == 0 )
      return CanonicalForm(1L);
    else
      return CanonicalForm(-1L);
  }
  else  if ( n == 0 )
    return CanonicalForm(1L);
 
  //else if (f.inGF())
  //{
  //}
  else
  {
    CanonicalForm g,h;
    h=f;
    while(n%2==0)
    {
      h*=h;
      n/=2;
    }
    g=h;
    while(1)
    {
      n/=2;
      if(n==0)
        return g;
      h*=h;
      if(n%2!=0) g*=h;
    }
  }
}

◆ power() [2/2]

CanonicalForm FACTORY_PUBLIC power	(	const Variable &	v,
		int	n
	)

exponentiation

Definition at line 1939 of file canonicalform.cc.

{
    //ASSERT( n >= 0, "illegal exponent" );
    if ( n == 0 )
        return 1;
    else  if ( n == 1 )
        return v;
    else  if (( v.level() < 0 ) && (hasMipo(v)))
    {
        CanonicalForm result( v, n-1 );
        return result * v;
    }
    else
        return CanonicalForm( v, n );
}

◆ pp()

CanonicalForm FACTORY_PUBLIC pp ( const CanonicalForm & f )

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.

{
    if ( f.isZero() )
        return f;
    else
        return f / content( f );
}

◆ Prem()

CanonicalForm Prem	(	const CanonicalForm &	F,
		const CanonicalForm &	G
	)

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

Definition at line 616 of file cfCharSetsUtil.cc.

{
  CanonicalForm f, g, l, test, lu, lv, t, retvalue;
  int degF, degG, levelF, levelG;
  bool reord;
  Variable v, vg= G.mvar();
 
  if ( (levelF= F.level()) < (levelG= G.level()))
    return F;
  else
  {
    if ( levelF == levelG )
    {
      f= F;
      g= G;
      reord= false;
      v= F.mvar();
    }
    else
    {
      v= Variable (levelF + 1);
      f= swapvar (F, vg, v);
      g= swapvar (G, vg, v);
      reord= true;
    }
    degG= degree (g, v );
    degF= degree (f, v );
    if (degG <= degF)
    {
      l= LC (g);
      g= g - l*power (v, degG);
    }
    else
      l= 1;
    while ((degG <= degF) && (!f.isZero()))
    {
      test= gcd (l, LC(f));
      lu= l / test;
      lv= LC(f) / test;
      t= g*lv*power (v, degF - degG);
 
      if (degF == 0)
        f= 0;
      else
        f= f - LC (f)*power (v, degF);
 
      f= f*lu - t;
      degF= degree (f, v);
    }
 
    if (reord)
      retvalue= swapvar (f, vg, v);
    else
      retvalue= f;
 
    return retvalue;
  }
}

◆ 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]	F	some poly over Z/p
[in]	error	0 < error < 1

Definition at line 63 of file facIrredTest.cc.

{
  CFMap N;
  CanonicalForm G= compress (F, N);
  int n= G.level();
  int p= getCharacteristic();
 
  double sqrtTrials= inverseERF (1-2.0*error)*sqrt (2.0);
 
  double s= sqrtTrials;
 
  double pn= pow ((double) p, (double) n);
  double p1= (double) 1/p;
  p1= p1*(1.0-p1);
  p1= p1/(double) pn;
  p1= sqrt (p1);
  p1 *= s;
  p1 += (double) 1/p;
 
  double p2= (double) (2*p-1)/(p*p);
  p2= p2*(1-p2);
  p2= p2/(double) pn;
  p2= sqrt (p2);
  p2 *= s;
  p2= (double) (2*p - 1)/(p*p)-p2;
 
  //no testing possible
  if (p2 < p1)
    return 0;
 
  double den= sqrt (p1*(1-p1))+sqrt (p2*(1-p2));
  double num= p2-p1;
 
  sqrtTrials *= den/num;
 
  int trials= (int) floor (pow (sqrtTrials, 2.0));
 
  double experimentalNumZeros= numZeros (G, trials);
 
  double pmiddle= sqrt (p1*p2);
 
  num= den;
  den= sqrt (p1*(1.0-p2))+sqrt (p2*(1.0-p1));
  pmiddle *= (den/num);
 
  if (experimentalNumZeros < pmiddle)
    return 1;
  else
    return -1;
}

◆ prune()

void FACTORY_PUBLIC prune ( Variable & alpha )

Definition at line 261 of file variable.cc.

{
  if (alpha.level()==LEVELBASE) return;
  int last_var=-alpha.level();
  if ((last_var <= 0)||(var_names_ext==NULL)) return;
  int i, n = strlen( var_names_ext );
  ASSERT (n+1 >= last_var, "wrong variable");
  if (last_var == 1)
  {
    delete [] var_names_ext;
    delete [] algextensions;
    var_names_ext= 0;
    algextensions= 0;
    alpha= Variable();
    return;
  }
  char * newvarnames = new char [last_var+1];
  for ( i = 0; i < last_var; i++ )
    newvarnames[i] = var_names_ext[i];
  newvarnames[last_var] = 0;
  delete [] var_names_ext;
  var_names_ext = newvarnames;
  ext_entry * newalgext = new ext_entry [last_var];
  for ( i = 0; i < last_var; i++ )
    newalgext[i] = algextensions[i];
  delete [] algextensions;
  algextensions = newalgext;
  alpha= Variable();
}

◆ prune1()

void prune1 ( const Variable & alpha )

Definition at line 291 of file variable.cc.

{
  int i, n = strlen( var_names_ext );
  ASSERT (n+1 >= -alpha.level(), "wrong variable");
 
  char * newvarnames = new char [-alpha.level() + 2];
  for ( i = 0; i <= -alpha.level(); i++ )
    newvarnames[i] = var_names_ext[i];
  newvarnames[-alpha.level()+1] = 0;
  delete [] var_names_ext;
  var_names_ext = newvarnames;
  ext_entry * newalgext = new ext_entry [-alpha.level()+1];
  for ( i = 0; i <= -alpha.level(); i++ )
    newalgext[i] = algextensions[i];
  delete [] algextensions;
  algextensions = newalgext;
}

◆ psq()

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

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.

{
    ASSERT( x.level() > 0, "type error: polynomial variable expected" );
    ASSERT( ! g.isZero(), "math error: division by zero" );
 
    // swap variables such that x's level is larger or equal
    // than both f's and g's levels.
    Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
    CanonicalForm F = swapvar( f, x, X );
    CanonicalForm G = swapvar( g, x, X );
 
    // now, we have to calculate the pseudo remainder of F and G
    // w.r.t. X
    int fDegree = degree( F, X );
    int gDegree = degree( G, X );
    if ( fDegree < 0 || fDegree < gDegree )
        return 0;
    else {
        CanonicalForm result = (power( LC( G, X ), fDegree-gDegree+1 ) * F) / G;
        return swapvar( result, x, X );
    }
}

◆ 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.

{
    ASSERT( x.level() > 0, "type error: polynomial variable expected" );
    ASSERT( ! g.isZero(), "math error: division by zero" );
 
    // swap variables such that x's level is larger or equal
    // than both f's and g's levels.
    Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
    CanonicalForm F = swapvar( f, x, X );
    CanonicalForm G = swapvar( g, x, X );
 
    // now, we have to calculate the pseudo remainder of F and G
    // w.r.t. X
    int fDegree = degree( F, X );
    int gDegree = degree( G, X );
    if ( fDegree < 0 || fDegree < gDegree ) {
        q = 0; r = f;
    } else {
        divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r );
        q = swapvar( q, x, X );
        r = swapvar( r, x, X );
    }
}

◆ psr()

CanonicalForm psr	(	const CanonicalForm &	rr,
		const CanonicalForm &	vv,
		const Variable &	x
	)

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.

{
  CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue;
  int dr, dv, d,n=0;
 
 
  dr = degree( r, x );
  if (dr>0)
  {
    dv = degree( v, x );
    if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);}
    else { l = 1; }
    d= dr-dv+1;
    //out_cf("psr(",rr," ");
    //out_cf("",vv," ");
    //printf(" var=%d\n",x.level());
    while ( ( dv <= dr  ) && ( !r.isZero()) )
    {
      test = power(x,dr-dv)*v*LC(r,x);
      if ( dr == 0 ) { r= CanonicalForm(0); }
      else { r= r - LC(r,x)*power(x,dr); }
      r= l*r -test;
      dr= degree(r,x);
      n+=1;
    }
    r= power(l, d-n)*r;
  }
  return r;
}

◆ reduce()

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

Definition at line 660 of file cf_ops.cc.

{
  if(f.inBaseDomain() || f.level() < M.level())
    return f;
  if(f.level() == M.level())
  {
    if(f.degree() < M.degree())
      return f;
    CanonicalForm tmp = mod (f, M);
    return tmp;
  }
  // here: f.level() > M.level()
  CanonicalForm result = 0;
  for(CFIterator i=f; i.hasTerms(); i++)
    result += reduce(i.coeff(),M) * power(f.mvar(),i.exp());
  return result;
}

◆ reorder() [1/3]

CFFList reorder	(	const Varlist &	betterorder,
		const CFFList &	PS
	)

Definition at line 120 of file cfCharSets.cc.

{
  int i= 1, n= betterorder.length();
  Intarray v (1, n);
  CFFList ps= PS;
 
  //initalize:
  for (VarlistIterator j= betterorder; j.hasItem(); j++)
  {
    v[i]= level (j.getItem());
    i++;
  }
 
  // reorder:
  for (i= 1; i <= n; i++)
    ps= swapvar (ps, Variable (v[i]), Variable (n + i));
  return ps;
}

◆ reorder() [2/3]

CFList reorder	(	const Varlist &	betterorder,
		const CFList &	PS
	)

Definition at line 101 of file cfCharSets.cc.

{
  int i= 1, n= betterorder.length();
  Intarray v (1, n);
  CFList ps= PS;
 
  //initalize:
  for (VarlistIterator j= betterorder; j.hasItem(); j++)
  {
    v[i]= level (j.getItem());
    i++;
  }
  // reorder:
  for (i= 1; i <= n; i++)
    ps= swapvar (ps, Variable (v[i]), Variable (n + i));
  return ps;
}

◆ reorder() [3/3]

ListCFList reorder	(	const Varlist &	betterorder,
		const ListCFList &	Q
	)

Definition at line 140 of file cfCharSets.cc.

{
  ListCFList Q1;
 
  for (ListCFListIterator i= Q; i.hasItem(); i++)
    Q1.append (reorder (betterorder, i.getItem()));
  return Q1;
}

◆ replaceLc()

CanonicalForm replaceLc	(	const CanonicalForm &	f,
		const CanonicalForm &	c
	)

Definition at line 90 of file fac_util.cc.

{
    if ( f.inCoeffDomain() )
        return c;
    else
        return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
}

◆ 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.

{
    //ASSERT( x2.level() > 0, "cannot replace with algebraic variable" );
    if ( f.inBaseDomain() || x1 == x2 || ( x1 > f.mvar() ) )
        return f;
    else
    {
        sv_x1 = x1;
        sv_x2 = x2;
        return replacevar_between( f );
    }
}

◆ resultant()

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

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.

{
    ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
 
    // some checks on triviality.  We will not use degree( v )
    // here because this may involve variable swapping.
    if ( f.isZero() || g.isZero() )
        return 0;
    if ( f.mvar() < x )
        return power( f, g.degree( x ) );
    if ( g.mvar() < x )
        return power( g, f.degree( x ) );
 
    // make x main variale
    CanonicalForm F, G;
    Variable X;
    if ( f.mvar() > x || g.mvar() > x ) {
        if ( f.mvar() > g.mvar() )
            X = f.mvar();
        else
            X = g.mvar();
        F = swapvar( f, X, x );
        G = swapvar( g, X, x );
    }
    else {
        X = x;
        F = f;
        G = g;
    }
    // at this point, we have to calculate resultant( F, G, X )
    // where X is equal to or greater than the main variables
    // of F and G
 
    int m = degree( F, X );
    int n = degree( G, X );
    // catch trivial cases
    if ( m+n <= 2 || m == 0 || n == 0 )
        return swapvar( trivialResultant( F, G, X ), X, x );
 
    // exchange F and G if necessary
    int flipFactor;
    if ( m < n ) {
        CanonicalForm swap = F;
        F = G; G = swap;
        int degswap = m;
        m = n; n = degswap;
        if ( m & 1 && n & 1 )
            flipFactor = -1;
        else
            flipFactor = 1;
    } else
        flipFactor = 1;
 
    // this is not an effective way to calculate the resultant!
    CanonicalForm extFactor;
    if ( m == n ) {
        if ( n & 1 )
            extFactor = -LC( G, X );
        else
            extFactor = LC( G, X );
    } else
        extFactor = power( LC( F, X ), m-n-1 );
 
    CanonicalForm result;
    result = subResChain( F, G, X )[0] / extFactor;
 
    return swapvar( result, X, x ) * flipFactor;
}

◆ 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]	A	some poly
[in]	B	some poly
[in]	x	some polynomial variable
[in]	prob	if true use probabilistic algorithm

Definition at line 559 of file cfModResultant.cc.

{
  ASSERT (getCharacteristic() == 0, "characteristic > 0 expected");
#ifndef NOASSERT
  bool isRat= isOn (SW_RATIONAL);
  On (SW_RATIONAL);
  ASSERT (bCommonDen (A).isOne(), "input A is rational");
  ASSERT (bCommonDen (B).isOne(), "input B is rational");
  if (!isRat)
    Off (SW_RATIONAL);
#endif
 
  int degAx= degree (A, x);
  int degBx= degree (B, x);
  if (A.level() < x.level())
    return power (A, degBx);
  if (B.level() < x.level())
    return power (B, degAx);
 
  if (degAx == 0)
    return power (A, degBx);
  else if (degBx == 0)
    return power (B, degAx);
 
  CanonicalForm F= A;
  CanonicalForm G= B;
 
  Variable X= x;
  if (F.level() != x.level() || G.level() != x.level())
  {
    if (F.level() > G.level())
      X= F.mvar();
    else
      X= G.mvar();
    F= swapvar (F, X, x);
    G= swapvar (G, X, x);
  }
 
  // now X is the main variable
 
  CanonicalForm d= 0;
  CanonicalForm dd= 0;
  CanonicalForm buf;
  for (CFIterator i= F; i.hasTerms(); i++)
  {
    buf= oneNorm (i.coeff());
    d= (buf > d) ? buf : d;
  }
  CanonicalForm e= 0, ee= 0;
  for (CFIterator i= G; i.hasTerms(); i++)
  {
    buf= oneNorm (i.coeff());
    e= (buf > e) ? buf : e;
  }
  d= power (d, degBx);
  e= power (e, degAx);
  CanonicalForm bound= 1;
  for (int i= degBx + degAx; i > 1; i--)
    bound *= i;
  bound *= d*e;
  bound *= 2;
 
  bool onRational= isOn (SW_RATIONAL);
  if (onRational)
    Off (SW_RATIONAL);
  int i = cf_getNumBigPrimes() - 1;
  int p;
  CanonicalForm l= lc (F)*lc(G);
  CanonicalForm resultModP, q (0), newResult, newQ;
  CanonicalForm result;
  int equalCount= 0;
  CanonicalForm test, newTest;
  int count= 0;
  do
  {
    p = cf_getBigPrime( i );
    i--;
    while ( i >= 0 && mod( l, p ) == 0)
    {
      p = cf_getBigPrime( i );
      i--;
    }
 
    if (i <= 0)
      return resultant (A, B, x);
 
    setCharacteristic (p);
 
    TIMING_START (fac_resultant_p);
    resultModP= resultantFp (mapinto (F), mapinto (G), X, prob);
    TIMING_END_AND_PRINT (fac_resultant_p, "time to compute resultant mod p: ");
 
    setCharacteristic (0);
 
    count++;
    if ( q.isZero() )
    {
      result= mapinto(resultModP);
      q= p;
    }
    else
    {
      chineseRemainder( result, q, mapinto (resultModP), p, newResult, newQ );
      q= newQ;
      result= newResult;
      test= symmetricRemainder (result,q);
      if (test != newTest)
      {
        newTest= test;
        equalCount= 0;
      }
      else
        equalCount++;
      if (newQ > bound || (prob && equalCount == 2))
      {
        result= test;
        break;
      }
    }
  } while (1);
 
  if (onRational)
    On (SW_RATIONAL);
  return swapvar (result, X, x);
}

◆ 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.

{
    ASSERT (mipo.isUnivariate(), "not a legal extension");
 
    int l;
    if ( var_names_ext == 0 ) {
        var_names_ext = new char [3];
        var_names_ext[0] = '@';
        var_names_ext[1] = name;
        var_names_ext[2] = '\0';
        l = 1;
        Variable result( -l, true );
        algextensions = new ext_entry [2];
        algextensions[1] = ext_entry( 0, false );
        algextensions[1] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
        return result;
    }
    else {
        int i, n = strlen( var_names_ext );
        char * newvarnames = new char [n+2];
        for ( i = 0; i < n; i++ )
            newvarnames[i] = var_names_ext[i];
        newvarnames[n] = name;
        newvarnames[n+1] = 0;
        delete [] var_names_ext;
        var_names_ext = newvarnames;
        l = n;
        Variable result( -l, true );
        ext_entry * newalgext = new ext_entry [n+1];
        for ( i = 0; i < n; i++ )
            newalgext[i] = algextensions[i];
        newalgext[n] = ext_entry( 0, false );
        delete [] algextensions;
        algextensions = newalgext;
        algextensions[n] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
        return result;
    }
}

◆ setCharacteristic() [1/3]

void FACTORY_PUBLIC setCharacteristic ( int c )

Definition at line 28 of file cf_char.cc.

{
    if ( c == 0 )
    {
        theDegree = 0;
        CFFactory::settype( IntegerDomain );
        theCharacteristic = 0;
    }
    else
    {
        theDegree = 1;
        CFFactory::settype( FiniteFieldDomain );
        ff_big = c > cf_getSmallPrime( cf_getNumSmallPrimes()-1 );
        if (c!=theCharacteristic)
        {
          if (c > 536870909) factoryError("characteristic is too large(max is 2^29)");
          ff_setprime( c );
        }
        theCharacteristic = c;
    }
}

◆ 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.

{
    ASSERT( c != 0 && n > 1, "illegal GF(q)" );
    setCharacteristic( c );
    gf_setcharacteristic( c, n, name );
    theDegree = n;
    CFFactory::settype( GaloisFieldDomain );
}

◆ setMipo()

void setMipo	(	const Variable &	alpha,
		const CanonicalForm &	mipo
	)

Definition at line 219 of file variable.cc.

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

◆ setReduce()

void setReduce	(	const Variable &	alpha,
		bool	reduce
	)

Definition at line 238 of file variable.cc.

{
    ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
    algextensions[-alpha.level()].reduce() = reduce;
}

◆ 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 )

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.

{
    if ( f.inCoeffDomain() )
        return 1;
    else
    {
        int result = 0;
        CFIterator i;
        for ( i = f; i.hasTerms(); i++ )
            result += size( i.coeff() );
        return result;
    }
}

◆ 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.

{
    if ( f.inBaseDomain() )
        return 1;
 
    if ( f.mvar() < v )
        // polynomials with level < v1 are counted as coefficients
        return 1;
    else
    {
        CFIterator i;
        int result = 0;
        // polynomials with level > v2 are not counted al all
        for ( i = f; i.hasTerms(); i++ )
            result += size( i.coeff(), v );
        return result;
    }
}

◆ size_maxexp()

int size_maxexp	(	const CanonicalForm &	f,
		int &	maxexp
	)

Definition at line 641 of file cf_ops.cc.

{
    if ( f.inCoeffDomain() )
        return 1;
    else
    {
        if (f.degree()>maxexp) maxexp=f.degree();
        int result = 0;
        CFIterator i;
        for ( i = f; i.hasTerms(); i++ )
            result += size_maxexp( i.coeff(), maxexp );
        return result;
    }
}

◆ sqrFree()

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

squarefree factorization

Definition at line 957 of file cf_factor.cc.

{
//    ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
    CFFList result;
 
    if ( getCharacteristic() == 0 )
        result = sqrFreeZ( f );
    else
    {
        Variable alpha;
        if (hasFirstAlgVar (f, alpha))
          result = FqSqrf( f, alpha );
        else
          result= FpSqrf (f);
    }
    if (sort)
    {
      CFFactor buf= result.getFirst();
      result.removeFirst();
      result= sortCFFList (result);
      result.insert (buf);
    }
    return result;
}

◆ sqrt()

CanonicalForm sqrt ( const CanonicalForm & a )

inline

Definition at line 490 of file factory.h.

490{ return a.sqrt(); }

CanonicalForm::sqrt

CanonicalForm sqrt() const

CanonicalForm CanonicalForm::sqrt () const.

Definition: canonicalform.cc:1383

◆ 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.

{
    ASSERT( x.level() > 0, "cannot calculate subresultant sequence with respect to algebraic variables" );
 
    CFArray trivialResult( 0, 0 );
    CanonicalForm F, G;
    Variable X;
 
    // some checks on triviality
    if ( f.isZero() || g.isZero() ) {
        trivialResult[0] = 0;
        return trivialResult;
    }
 
    // make x main variable
    if ( f.mvar() > x || g.mvar() > x ) {
        if ( f.mvar() > g.mvar() )
            X = f.mvar();
        else
            X = g.mvar();
        F = swapvar( f, X, x );
        G = swapvar( g, X, x );
    }
    else {
        X = x;
        F = f;
        G = g;
    }
    // at this point, we have to calculate the sequence of F and
    // G in respect to X where X is equal to or greater than the
    // main variables of F and G
 
    // initialization of chain
    int m = degree( F, X );
    int n = degree( G, X );
 
    int j = (m <= n) ? n : m-1;
    int r;
 
    CFArray S( 0, j+1 );
    CanonicalForm R;
    S[j+1] = F; S[j] = G;
 
    // make sure that S[j+1] is regular and j < n
    if ( m == n && j > 0 ) {
        S[j-1] = LC( S[j], X ) * psr( S[j+1], S[j], X );
        j--;
    } else if ( m < n ) {
        S[j-1] = LC( S[j], X ) * LC( S[j], X ) * S[j+1];
        j--;
    } else if ( m > n && j > 0 ) {
        // calculate first step
        r = degree( S[j], X );
        R = LC( S[j+1], X );
 
        // if there was a gap calculate similar polynomial
        if ( j > r && r >= 0 )
            S[r] = power( LC( S[j], X ), j - r ) * S[j] * power( R, j - r );
 
        if ( r > 0 ) {
            // calculate remainder
            S[r-1] = psr( S[j+1], S[j], X ) * power( -R, j - r );
            j = r-1;
        }
    }
 
    while ( j > 0 ) {
        // at this point, 0 < j < n and S[j+1] is regular
        r = degree( S[j], X );
        R = LC( S[j+1], X );
 
        // if there was a gap calculate similar polynomial
        if ( j > r && r >= 0 )
            S[r] = (power( LC( S[j], X ), j - r ) * S[j]) / power( R, j - r );
 
        if ( r <= 0 ) break;
        // calculate remainder
        S[r-1] = psr( S[j+1], S[j], X ) / power( -R, j - r + 2 );
 
        j = r-1;
        // again 0 <= j < r <= jOld and S[j+1] is regular
    }
 
    for ( j = 0; j <= S.max(); j++ ) {
        // reswap variables if necessary
        if ( X != x ) {
            S[j] = swapvar( S[j], X, x );
        }
    }
 
    return S;
}

◆ swapvar()

CanonicalForm FACTORY_PUBLIC swapvar	(	const CanonicalForm &	f,
		const Variable &	x1,
		const Variable &	x2
	)

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.

{
    ASSERT( x1.level() > 0 && x2.level() > 0, "cannot swap algebraic Variables" );
    if ( f.inCoeffDomain() || x1 == x2 || ( x1 > f.mvar() && x2 > f.mvar() ) )
        return f;
    else
    {
        CanonicalForm result = 0;
        if ( x1 > x2 )
        {
            sv_x1 = x2; sv_x2 = x1;
        }
        else
        {
            sv_x1 = x1; sv_x2 = x2;
        }
        if ( f.mvar() < sv_x2 )
            // we only have to replace sv_x1 by sv_x2
            swapvar_between( f, result, 1, 0 );
        else
            // we really have to swap variables
            swapvar_rec( f, result, 1 );
        return result;
    }
}

◆ 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 )

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.

{
    if ( f.isZero() )
        return -1;
    else if ( f.inCoeffDomain() )
        return 0;
    else
    {
        CFIterator i;
        int cdeg = 0, dummy;
        // calculate maximum over all coefficients of f, taking
        // in account our own exponent
        for ( i = f; i.hasTerms(); i++ )
            if ( (dummy = totaldegree( i.coeff() ) + i.exp()) > cdeg )
                cdeg = dummy;
        return cdeg;
    }
}

◆ 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.

{
    if ( f.isZero() )
        return -1;
    else if ( v1 > v2 )
        return 0;
    else if ( f.inCoeffDomain() )
        return 0;
    else if ( f.mvar() < v1 )
        return 0;
    else if ( f.mvar() == v1 )
        return f.degree();
    else if ( f.mvar() > v2 )
    {
        // v2's level is larger than f's level, descend down
        CFIterator i;
        int cdeg = 0, dummy;
        // calculate maximum over all coefficients of f
        for ( i = f; i.hasTerms(); i++ )
            if ( (dummy = totaldegree( i.coeff(), v1, v2 )) > cdeg )
                cdeg = dummy;
        return cdeg;
    }
    else
    {
        // v1 < f.mvar() <= v2
        CFIterator i;
        int cdeg = 0, dummy;
        // calculate maximum over all coefficients of f, taking
        // in account our own exponent
        for ( i = f; i.hasTerms(); i++ )
            if ( (dummy = totaldegree( i.coeff(), v1, v2 ) + i.exp()) > cdeg )
                cdeg = dummy;
        return cdeg;
    }
}

◆ 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.

{
    fail= false;
    // trivial cases
    if ( g.isZero() )
        return true;
    else if ( f.isZero() )
        return false;
 
    if (f.inCoeffDomain() || g.inCoeffDomain())
    {
        // if we are in a field all elements not equal to zero are units
        if ( f.inCoeffDomain() )
        {
            CanonicalForm inv;
            tryInvert (f, M, inv, fail);
            return !fail;
        }
        else
        {
            return false;
        }
    }
 
    // we may assume now that both levels either equal LEVELBASE
    // or are greater zero
    int fLevel = f.level();
    int gLevel = g.level();
    if ( (gLevel > 0) && (fLevel == gLevel) )
    {
        if (degree( f ) > degree( g ))
          return false;
        bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
 
        if (fail || !dividestail)
          return false;
        bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail);
        if (fail || !dividesLC)
          return false;
        CanonicalForm q,r;
        bool divides= tryDivremt (g, f, q, r, M, fail);
        if (fail || !divides)
          return false;
        return r.isZero();
    }
    else if ( gLevel < fLevel )
    {
        // g is a coefficient w.r.t. f
        return false;
    }
    else
    {
        // either f is a coefficient w.r.t. polynomial g or both
        // f and g are from a base domain (should be Z or Z/p^n,
        // then)
        CanonicalForm q, r;
        bool divides= tryDivremt (g, f, q, r, M, fail);
        if (fail || !divides)
          return false;
        return r.isZero();
    }
}

◆ vcontent()

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

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.

{
    ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
 
    if ( f.mvar() <= x )
        return content( f, x );
    else {
        CFIterator i;
        CanonicalForm d = 0;
        for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
            d = gcd( d, vcontent( i.coeff(), x ) );
        return d;
    }
}

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.

Data Structures

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ CF_INLINE [1/2]

◆ CF_INLINE [2/2]

◆ CF_NO_INLINE [1/2]

◆ CF_NO_INLINE [2/2]

◆ ISTREAM

◆ LEVELBASE

◆ LEVELEXPR

◆ LEVELQUOT

◆ LEVELTRANS

◆ OSTREAM

Typedef Documentation

◆ CFAFactor

◆ CFAFList

◆ CFAFListIterator

◆ CFArray

◆ CFFactor

◆ CFFList

◆ CFFListIterator

◆ CFList

◆ CFListIterator

◆ CFMatrix

◆ Intarray

◆ IntList

◆ IntListIterator

◆ ListCFList

◆ ListCFListIterator

◆ MPList

◆ MPListIterator

◆ termList

◆ Varlist

◆ VarlistIterator

Function Documentation

◆ abs()

Type info:

◆ absFactorize()

◆ apply()

◆ basicSet()

◆ bCommonDen()

Type info:

◆ blcm()

◆ cf_getBigPrime()

◆ cf_getNumBigPrimes()

◆ cf_getNumPrimes()

◆ cf_getNumSmallPrimes()

◆ cf_getPrime()

◆ cf_getSmallPrime()

◆ cf_HNF()

◆ cf_LLL()

◆ charSeries()

◆ charSet()

◆ charSetN()

◆ charSetViaCharSetN()

◆ charSetViaModCharSet() [1/2]

◆ charSetViaModCharSet() [2/2]

◆ chineseRemainder() [1/2]

◆ chineseRemainder() [2/2]

◆ chineseRemainderCached() [1/2]

◆ chineseRemainderCached() [2/2]

◆ compress() [1/3]

◆ compress() [2/3]

◆ compress() [3/3]

◆ content() [1/2]

◆ content() [2/2]

◆ degree() [1/2]

◆ degree() [2/2]

◆ degrees()

◆ den()

◆ deriv()

◆ determinant()

◆ div()

◆ euclideanNorm()

Type info:

◆ ExtensionLevel()