Loading...
Searching...
No Matches
cfUnivarGcd.h File Reference

univariate Gcd over finite fields and Z, extended GCD over finite fields and Q More...

`#include <NTL/ZZX.h>`
`#include "NTLconvert.h"`
`#include "FLINTconvert.h"`

Go to the source code of this file.

## Functions

bool | isPurePoly (const CanonicalForm &)
CanonicalForm | gcd_univar_flint0 (const CanonicalForm &, const CanonicalForm &)
CanonicalForm | gcd_univar_flintp (const CanonicalForm &, const CanonicalForm &)
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 ).

## Detailed Description

univariate Gcd over finite fields and Z, extended GCD over finite fields and Q

Note
  if NTL or FLINT are available they are used to compute the (ext)Gcd

Definition in file cfUnivarGcd.h.

## Function Documentation

## 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;
}
convertFmpq_poly_t2FacCF
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
Definition FLINTconvert.cc:294
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition FLINTconvert.cc:208
convertFacCF2Fmpq_poly_t
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
Definition FLINTconvert.cc:320
convertZZ2CF
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition NTLconvert.cc:495
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition NTLconvert.cc:691
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition NTLconvert.cc:285
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1032
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
g
g
Definition cfModGcd.cc:4098
b
CanonicalForm b
Definition cfModGcd.cc:4111
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
f
FILE * f
Definition checklibs.c:9
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::sign
int sign() const
int CanonicalForm::sign () const
Definition canonicalform.cc:1360
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
B
b *CanonicalForm B
Definition facBivar.cc:52
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
R
#define R
Definition sirandom.c:27
A
#define A
Definition sirandom.c:24

## gcd_univar_flint0()

CanonicalForm gcd_univar_flint0 | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G )

Definition at line 61 of file cfUnivarGcd.cc.

{
fmpz_poly_t F1, G1;
convertFacCF2Fmpz_poly_t(F1, F);
convertFacCF2Fmpz_poly_t(G1, G);
fmpz_poly_gcd (F1, F1, G1);
CanonicalForm result= convertFmpz_poly_t2FacCF (F1, F.mvar());
fmpz_poly_clear (F1);
fmpz_poly_clear (G1);
return result;
}
convertFmpz_poly_t2FacCF
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
Definition FLINTconvert.cc:172
convertFacCF2Fmpz_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition FLINTconvert.cc:146
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
result
return result
Definition facAbsBiFact.cc:76
G
STATIC_VAR TreeM * G
Definition janet.cc:31

## gcd_univar_flintp()

CanonicalForm gcd_univar_flintp | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G )

Definition at line 48 of file cfUnivarGcd.cc.

{
nmod_poly_t F1, G1;
convertFacCF2nmod_poly_t (F1, F);
convertFacCF2nmod_poly_t (G1, G);
nmod_poly_gcd (F1, F1, G1);
CanonicalForm result= convertnmod_poly_t2FacCF (F1, F.mvar());
nmod_poly_clear (F1);
nmod_poly_clear (G1);
return result;
}

## isPurePoly()

bool isPurePoly | ( | const CanonicalForm & | f | ) |

Definition at line 248 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;
}
i
int i
Definition cfEzgcd.cc:132
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44