My Project
Functions
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 ) More...
 

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 extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )

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

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

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

Definition at line 174 of file cfUnivarGcd.cc.

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

◆ gcd_univar_flint0()

CanonicalForm gcd_univar_flint0 ( const CanonicalForm F,
const CanonicalForm G 
)

Definition at line 61 of file cfUnivarGcd.cc.

62 {
63  fmpz_poly_t F1, G1;
66  fmpz_poly_gcd (F1, F1, G1);
68  fmpz_poly_clear (F1);
69  fmpz_poly_clear (G1);
70  return result;
71 }
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
return result
Definition: facAbsBiFact.cc:75
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.

49 {
50  nmod_poly_t F1, G1;
53  nmod_poly_gcd (F1, F1, G1);
56  nmod_poly_clear (G1);
57  return result;
58 }

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 244 of file cf_factor.cc.

245 {
246  if (f.level()<=0) return false;
247  for (CFIterator i=f;i.hasTerms();i++)
248  {
249  if (!(i.coeff().inBaseDomain())) return false;
250  }
251  return true;
252 }
int i
Definition: cfEzgcd.cc:132
class to iterate through CanonicalForm's
Definition: cf_iter.h:44