My Project
Loading...
Searching...
No Matches
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);
207 return r;
208 }
209#elif defined(HAVE_NTL)
211 && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
212 {
214 {
216 zz_p::init(getCharacteristic());
217 }
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);
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)
#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