Loading...
Searching...
No Matches
facFqSquarefree.h
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqSquarefree.h
*
* This file provides functions for squarefrees factorizing over
* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#ifndef FAC_FQ_SQUAREFREE_H
#define FAC_FQ_SQUAREFREE_H
#include "cf_assert.h"
#include "cf_factory.h"
#include "fac_sqrfree.h"
#include "cf_factory.h"
/// squarefree factorization over a finite field
/// @a return a list of squarefree factors with multiplicity
CFFList
squarefreeFactorization
(const CanonicalForm & F, ///<[in] a poly
const Variable & alpha ///<[in] either an algebraic variable,
///< i.e. we are over some F_p (alpha)
///< or a variable of level 1, i.e.
///< we are F_p or GF
);
/// squarefree factorization over \f$ F_{p} \f$.
/// If input is not monic, the leading coefficient is dropped
///
/// @return a list of squarefree factors with multiplicity
inline
CFFList FpSqrf (const CanonicalForm& F, ///< [in] a poly
bool sort= true ///< [in] sort factors by exponent?
)
{
Variable a= 1;
int n= F.level();
CanonicalForm cont, bufF= F;
CFFList bufResult;
CFFList result;
for (int i= n; i >= 1; i++)
{
cont= content (bufF, i);
bufResult= squarefreeFactorization (cont, a);
if (bufResult.getFirst().factor().inCoeffDomain())
bufResult.removeFirst();
result= Union (result, bufResult);
bufF /= cont;
if (bufF.inCoeffDomain())
break;
}
if (!bufF.inCoeffDomain())
{
bufResult= squarefreeFactorization (bufF, a);
if (bufResult.getFirst().factor().inCoeffDomain())
bufResult.removeFirst();
result= Union (result, bufResult);
}
if (sort)
result= sortCFFList (result);
result.insert (CFFactor (Lc(F), 1));
return result;
}
/// squarefree factorization over \f$ F_{p}(\alpha ) \f$.
/// If input is not monic, the leading coefficient is dropped
///
/// @return a list of squarefree factors with multiplicity
inline
CFFList FqSqrf (const CanonicalForm& F, ///< [in] a poly
const Variable& alpha, ///< [in] algebraic variable
bool sort= true ///< [in] sort factors by exponent?
)
{
int n= F.level();
CanonicalForm cont, bufF= F;
CFFList bufResult;
CFFList result;
for (int i= n; i >= 1; i++)
{
cont= content (bufF, i);
bufResult= squarefreeFactorization (cont, alpha);
if (bufResult.getFirst().factor().inCoeffDomain())
bufResult.removeFirst();
result= Union (result, bufResult);
bufF /= cont;
if (bufF.inCoeffDomain())
break;
}
if (!bufF.inCoeffDomain())
{
bufResult= squarefreeFactorization (bufF, alpha);
if (bufResult.getFirst().factor().inCoeffDomain())
bufResult.removeFirst();
result= Union (result, bufResult);
}
if (sort)
result= sortCFFList (result);
result.insert (CFFactor (Lc(F), 1));
return result;
}
/// squarefree factorization over GF.
/// If input is not monic, the leading coefficient is dropped
///
/// @return a list of squarefree factors with multiplicity
inline
CFFList GFSqrf (const CanonicalForm& F, ///< [in] a poly
bool sort= true ///< [in] sort factors by exponent?
)
{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
return FpSqrf (F, sort);
}
/// squarefree part of @a F/g, where g is the product of those squarefree
/// factors whose multiplicity is 0 mod p, if @a F a pth power pthPower= F.
///
/// @return @a sqrfPart returns 1, if F is a pthPower, else it returns the
/// squarefree part of @a F/g, where g is the product of those
/// squarefree factors whose multiplicity is 0 mod p
CanonicalForm
sqrfPart (const CanonicalForm& F, ///< [in] a poly
CanonicalForm& pthPower, ///< [in,out] returns F is F is a pthPower
const Variable& alpha ///< [in] algebraic variable
);
/// p^l-th root extraction, where l is maximal
///
/// @return @a maxpthRoot returns a p^l-th root of @a F, where @a l is maximal
/// @sa pthRoot()
CanonicalForm
maxpthRoot (const CanonicalForm & F, ///< [in] a poly which is a pth power
int q, ///< [in] size of the field
int& l ///< [in,out] @a l maximal, s.t. @a F is
///< a p^l-th power
);
#endif
/* FAC_FQ_SQUAREFREE_H */
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
cf_assert.h
assertions for Factory
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
cf_factory.h
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
result
return result
Definition facAbsBiFact.cc:76
GFSqrf
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:116
maxpthRoot
CanonicalForm maxpthRoot(const CanonicalForm &F, int q, int &l)
p^l-th root extraction, where l is maximal
Definition facFqSquarefree.cc:127
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:77
squarefreeFactorization
CFFList squarefreeFactorization(const CanonicalForm &F, const Variable &alpha)
squarefree factorization over a finite field return a list of squarefree factors with multiplicity
Definition facFqSquarefree.cc:181
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:38
sqrfPart
CanonicalForm sqrfPart(const CanonicalForm &F, CanonicalForm &pthPower, const Variable &alpha)
squarefree part of F/g, where g is the product of those squarefree factors whose multiplicity is 0 mo...
Definition facFqSquarefree.cc:303
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition fac_sqrfree.cc:25
fac_sqrfree.h
squarefree part and factorization over Q, Q(a)
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)