Loading...
Searching...
No Matches
facFqSquarefree.cc
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqSquarefree.cc
*
* This file provides functions for squarefrees factorizing over
* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, as decribed in "Factoring
* multivariate polynomials over a finite field" by L. Bernardin
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#include "config.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_map.h"
#include "cf_util.h"
#include "cf_factory.h"
#include "facFqSquarefree.h"
#ifdef HAVE_NTL
#include "NTLconvert.h"
#endif
#ifdef HAVE_FLINT
#include "FLINTconvert.h"
#endif
static inline
CanonicalForm
pthRoot (const CanonicalForm & F, int q)
{
CanonicalForm A= F;
int p= getCharacteristic ();
if (A.inCoeffDomain())
{
A= power (A, q/p);
return A;
}
else
{
CanonicalForm buf= 0;
for (CFIterator i= A; i.hasTerms(); i++)
buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q);
return buf;
}
}
#ifdef HAVE_NTL
CanonicalForm
pthRoot (const CanonicalForm & F, const ZZ& q, const Variable& alpha)
{
CanonicalForm A= F;
int p= getCharacteristic ();
if (A.inCoeffDomain())
{
zz_p::init (p);
zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
zz_pE::init (NTLMipo);
zz_pX NTLA= convertFacCF2NTLzzpX (A);
zz_pE NTLA2= to_zz_pE (NTLA);
power (NTLA2, NTLA2, q/p);
A= convertNTLzzpE2CF (NTLA2, alpha);
return A;
}
else
{
CanonicalForm buf= 0;
for (CFIterator i= A; i.hasTerms(); i++)
buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
return buf;
}
}
#endif
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
CanonicalForm
pthRoot (const CanonicalForm & F, const fmpz_t& q, const Variable& alpha)
{
CanonicalForm A= F;
int p= getCharacteristic ();
if (A.inCoeffDomain())
{
nmod_poly_t FLINTmipo;
fq_nmod_ctx_t fq_con;
fmpz_t qp;
fq_nmod_t FLINTA;
nmod_poly_init (FLINTmipo, p);
convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
fq_nmod_init2 (FLINTA, fq_con);
convertFacCF2Fq_nmod_t (FLINTA, A, fq_con);
fmpz_init_set (qp, q);
fmpz_divexact_si (qp, qp, p);
fq_nmod_pow (FLINTA, FLINTA, qp, fq_con);
A= convertFq_nmod_t2FacCF (FLINTA, alpha, fq_con);
fmpz_clear (qp);
nmod_poly_clear (FLINTmipo);
fq_nmod_clear (FLINTA, fq_con);
fq_nmod_ctx_clear (fq_con);
return A;
}
else
{
CanonicalForm buf= 0;
for (CFIterator i= A; i.hasTerms(); i++)
buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q, alpha);
return buf;
}
}
#endif
CanonicalForm
maxpthRoot (const CanonicalForm & F, int q, int& l)
{
CanonicalForm result= F;
bool derivZero= true;
l= 0;
while (derivZero)
{
for (int i= 1; i <= result.level(); i++)
{
if (!deriv (result, Variable (i)).isZero())
{
derivZero= false;
break;
}
}
if (!derivZero)
break;
result= pthRoot (result, q);
l++;
}
return result;
}
static inline
CFFList
sqrfPosDer (const CanonicalForm & F, const Variable & x,
CanonicalForm & c)
{
CanonicalForm b= deriv (F, x);
c= gcd (F, b);
CanonicalForm w= F/c;
CanonicalForm v= b/c;
CanonicalForm u= v - deriv (w, x);
int j= 1;
int p= getCharacteristic();
CanonicalForm g;
CFFList result;
while (j < p - 1 && degree(u) >= 0)
{
g= gcd (w, u);
if (!g.inCoeffDomain())
result.append (CFFactor (g, j));
w= w/g;
c= c/w;
v= u/g;
u= v - deriv (w, x);
j++;
}
if (!w.inCoeffDomain())
result.append (CFFactor (w, j));
return result;
}
CFFList
squarefreeFactorization (const CanonicalForm & F, const Variable & alpha)
{
int p= getCharacteristic();
CanonicalForm A= F;
CFMap M;
A= compress (A, M);
Variable x= A.mvar();
int l= x.level();
int k;
if (CFFactory::gettype() == GaloisFieldDomain)
k= getGFDegree();
else if (alpha.level() != 1)
k= degree (getMipo (alpha));
else
k= 1;
Variable buf, buf2;
CanonicalForm tmp;
CFFList tmp1, tmp2;
bool found;
for (int i= l; i > 0; i--)
{
buf= Variable (i);
if (degree (deriv (A, buf)) >= 0)
{
tmp1= sqrfPosDer (A, buf, tmp);
A= tmp;
for (CFFListIterator j= tmp1; j.hasItem(); j++)
{
found= false;
CFFListIterator k= tmp2;
if (!k.hasItem() && !j.getItem().factor().inCoeffDomain()) tmp2.append (j.getItem());
else
{
for (; k.hasItem(); k++)
{
if (k.getItem().exp() == j.getItem().exp())
{
k.getItem()= CFFactor (k.getItem().factor()*j.getItem().factor(),
j.getItem().exp());
found= true;
}
}
if (found == false && !j.getItem().factor().inCoeffDomain())
tmp2.append(j.getItem());
}
}
}
}
bool degcheck= false;;
for (int i= l; i > 0; i--)
if (degree (A, Variable(i)) >= p)
degcheck= true;
if (degcheck == false && tmp1.isEmpty() && tmp2.isEmpty())
return CFFList (CFFactor (F/Lc(F), 1));
CanonicalForm buffer;
#if defined(HAVE_NTL) || (HAVE_FLINT && __FLINT_RELEASE >= 20400)
if (alpha.level() == 1)
#endif
buffer= pthRoot (A, ipower (p, k));
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
else
{
fmpz_t qq;
fmpz_init_set_ui (qq, p);
fmpz_pow_ui (qq, qq, k);
buffer= pthRoot (A, qq, alpha);
fmpz_clear (qq);
}
#elif defined(HAVE_NTL)
else
{
ZZ q;
power (q, p, k);
buffer= pthRoot (A, q, alpha);
}
#else
factoryError("NTL/FLINT missing: squarefreeFactorization");
#endif
tmp1= squarefreeFactorization (buffer, alpha);
CFFList result;
buf= alpha;
for (CFFListIterator i= tmp2; i.hasItem(); i++)
{
for (CFFListIterator j= tmp1; j.hasItem(); j++)
{
tmp= gcd (i.getItem().factor(), j.getItem().factor());
i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
if (!tmp.inCoeffDomain())
{
tmp= M (tmp);
result.append (CFFactor (tmp/Lc(tmp),
j.getItem().exp()*p + i.getItem().exp()));
}
}
}
for (CFFListIterator i= tmp2; i.hasItem(); i++)
{
if (!i.getItem().factor().inCoeffDomain())
{
tmp= M (i.getItem().factor());
result.append (CFFactor (tmp/Lc(tmp), i.getItem().exp()));
}
}
for (CFFListIterator j= tmp1; j.hasItem(); j++)
{
if (!j.getItem().factor().inCoeffDomain())
{
tmp= M (j.getItem().factor());
result.append (CFFactor (tmp/Lc(tmp), j.getItem().exp()*p));
}
}
return result;
}
CanonicalForm
sqrfPart (const CanonicalForm& F, CanonicalForm& pthPower,
const Variable& alpha)
{
if (F.inCoeffDomain())
{
pthPower= 1;
return F;
}
CFMap M;
CanonicalForm A= compress (F, M);
Variable vBuf= alpha;
CanonicalForm w, v, b;
pthPower= 1;
CanonicalForm result;
int i= 1;
bool allZero= true;
for (; i <= A.level(); i++)
{
if (!deriv (A, Variable (i)).isZero())
{
allZero= false;
break;
}
}
if (allZero)
{
pthPower= F;
return 1;
}
w= gcd (A, deriv (A, Variable (i)));
b= A/w;
result= b;
if (degree (w) < 1)
return M (result);
i++;
for (; i <= A.level(); i++)
{
if (!deriv (w, Variable (i)).isZero())
{
b= w;
w= gcd (w, deriv (w, Variable (i)));
b /= w;
if (degree (b) < 1)
break;
CanonicalForm g;
g= gcd (b, result);
if (degree (g) > 0)
result *= b/g;
if (degree (g) <= 0)
result *= b;
}
}
result= M (result);
return result;
}
convertFacCF2Fq_nmod_t
void convertFacCF2Fq_nmod_t(fq_nmod_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory element of F_q to a FLINT fq_nmod_t, does not do any memory allocation for po...
Definition FLINTconvert.cc:442
convertFq_nmod_t2FacCF
CanonicalForm convertFq_nmod_t2FacCF(const fq_nmod_t poly, const Variable &alpha, const fq_nmod_ctx_t)
conversion of a FLINT element of F_q to a CanonicalForm with alg. variable alpha
Definition FLINTconvert.cc:479
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
convertNTLzzpE2CF
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition NTLconvert.cc:799
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
NTLconvert.h
Conversion to and from NTL.
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
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
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
b
CanonicalForm b
Definition cfModGcd.cc:4111
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.
cf_iter.h
Iterators for CanonicalForm's.
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
cf_map.h
map polynomials
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
cf_util.h
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
result
return result
Definition facAbsBiFact.cc:76
w
const CanonicalForm & w
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
allZero
bool allZero
Definition facFactorize.cc:56
found
bool found
Definition facFactorize.cc:55
tmp1
CFList tmp1
Definition facFqBivar.cc:75
buf2
CanonicalForm buf2
Definition facFqBivar.cc:76
tmp2
CFList tmp2
Definition facFqBivar.cc:75
sqrfPosDer
static CFFList sqrfPosDer(const CanonicalForm &F, const Variable &x, CanonicalForm &c)
Definition facFqSquarefree.cc:152
maxpthRoot
CanonicalForm maxpthRoot(const CanonicalForm &F, int q, int &l)
p^l-th root extraction, where l is maximal
Definition facFqSquarefree.cc:127
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
pthRoot
static CanonicalForm pthRoot(const CanonicalForm &F, int q)
Definition facFqSquarefree.cc:37
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
facFqSquarefree.h
This file provides functions for squarefrees factorizing over , or GF.
fq_con
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
j
int j
Definition facHensel.cc:110
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
buf
int status int void * buf
Definition si_signals.h:69
A
#define A
Definition sirandom.c:24
M
#define M
Definition sirandom.c:25
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836