My Project
Loading...
Searching...
No Matches
cf_map_ext.cc
Go to the documentation of this file.
1// -*- c++ -*-
2//*****************************************************************************
3/** @file cf_map_ext.cc
4 *
5 * This file implements functions to map between extensions of finite fields
6 *
7 * @par Copyright:
8 * (c) by The SINGULAR Team, see LICENSE file
9 *
10 * @author Martin Lee
11 * @date 16.11.2009
12**/
13//*****************************************************************************
14
15
16#include "config.h"
17
18
19#include "cf_assert.h"
20#include "debug.h"
21
22#include "canonicalform.h"
23#include "cf_util.h"
24#include "imm.h"
25#include "cf_iter.h"
26
27#ifdef HAVE_NTL
28#include "NTLconvert.h"
29#endif
30
31#ifdef HAVE_FLINT
32#include "FLINTconvert.h"
33#endif
34
35// cyclotomoic polys:
36#include "cf_cyclo.h"
37
38#include "cf_map_ext.h"
39
40/// helper function
41int findItem (const CFList& list, const CanonicalForm& item)
42{
43 int result= 1;
44 for (CFListIterator i= list; i.hasItem(); i++, result++)
45 {
46 if (i.getItem() == item)
47 return result;
48 }
49 return 0;
50}
51
52/// helper function
53CanonicalForm getItem (const CFList& list, const int& pos)
54{
55 int j= 1;
56 if ((pos > 0) && (pos <= list.length()))
57 {
58 for (CFListIterator i= list; j <= pos; i++, j++)
59 {
60 if (j == pos)
61 return i.getItem();
62 }
63 }
64 return 0;
65}
66
67/// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
68/// primitive element, returns the image of \f$ \alpha \f$
69static inline
71{
72 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
73 // convert mipo1
74 nmod_poly_t mipo1;
76 fq_nmod_ctx_t ctx;
77 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
78 nmod_poly_clear(mipo1);
79 // convert mipo2 (alpah)
80 fq_nmod_poly_t mipo2;
82 fq_nmod_poly_factor_t fac;
83 fq_nmod_poly_factor_init(fac,ctx);
84 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
85 // root of first (linear) factor: -absolute Term
86 fq_nmod_t r0;
87 fq_nmod_init(r0, ctx);
88 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
89 fq_nmod_neg(r0, r0, ctx);
90 // convert
92 // cleanup
93 fq_nmod_poly_factor_clear(fac,ctx);
94 fq_nmod_clear(r0, ctx);
95 fq_nmod_poly_clear(mipo2,ctx);
97 return r1;
98 #elif defined(HAVE_NTL)
99 int p= getCharacteristic ();
100 if (fac_NTL_char != p)
101 {
103 zz_p::init (p);
104 }
105 zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
106 zz_pE::init (NTL_mipo);
107 zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
108 zz_pE root= FindRoot (NTL_alpha_mipo);
109 return convertNTLzzpE2CF (root, beta);
110 #else
111 factoryError("NTL/FLINT missing: mapUp");
112 return CanonicalForm(0); // to avoid warnings
113 #endif
114}
115
116
117/// the CanonicalForm G is the output of map_up, returns F considered as an
118/// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
119/// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
120/// isomorphic to \f$ F_{p}(\alpha ) \f$
121static inline
123mapDown (const CanonicalForm& F, const Variable& alpha, const
124 CanonicalForm& G, CFList& source, CFList& dest)
125{
127 int counter= 0;
128 int pos;
129 int p= getCharacteristic();
130 int d= degree(getMipo(alpha));
131 int bound= ipower(p, d);
134 CanonicalForm alpha_power;
135 if (degree(F) == 0) return F;
136 if (F.level() < 0 && F.isUnivariate())
137 {
138 buf= F;
139 remainder= mod (buf, G);
140 ASSERT (remainder.isZero(), "alpha is not primitive");
141 pos= findItem (source, buf);
142 if (pos == 0)
143 source.append (buf);
144 buf2= buf;
145 while (degree (buf) != 0 && counter < bound)
146 {
147 buf /= G;
148 counter++;
149 if (buf == buf2) break;
150 }
151 ASSERT (counter >= bound, "alpha is not primitive");
152 if (pos == 0)
153 {
154 alpha_power= power (alpha, counter);
155 dest.append (alpha_power);
156 }
157 else
158 alpha_power= getItem (dest, pos);
159 result = alpha_power;
160 return result;
161 }
162 else
163 {
164 for (CFIterator i= F; i.hasTerms(); i++)
165 {
166 buf= mapDown (i.coeff(), alpha, G, source, dest);
167 result += buf*power(F.mvar(), i.exp());
168 }
169 return result;
170 }
171}
172
173/// helper function
174static inline
176{
177 if (F.isZero())
178 return 0;
179 int exp;
182 if (F.inBaseDomain())
183 {
184 if (F.isOne()) return 1;
185 buf= F.getval();
186 exp= imm2int(buf);
188 return result;
189 }
190 for (CFIterator i= F; i.hasTerms(); i++)
191 result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
192 return result;
193}
194
196{
199 prune (beta);
200 return result;
201}
202
204{
207
208 if (F.inCoeffDomain())
209 {
210 if (F.inBaseDomain())
211 return F.mapinto();
212 else
213 {
214 for (CFIterator i= F; i.hasTerms(); i++)
215 {
216 buf= int2imm_gf (i.exp());
217 result += i.coeff().mapinto()*CanonicalForm (buf);
218 }
219 }
220 return result;
221 }
222 for (CFIterator i= F; i.hasTerms(); i++)
223 result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
224 return result;
225}
226
227/// GF_map_up helper
228static inline
230{
231 if (F.isOne()) return F;
233 if (F.inBaseDomain())
234 return power(F, k);
235 for (CFIterator i= F; i.hasTerms(); i++)
236 result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
237 return result;
238}
239
241{
242 int d= getGFDegree();
243 ASSERT (d%k == 0, "multiple of GF degree expected");
244 int p= getCharacteristic();
245 int ext_field_size= ipower (p, d);
246 int field_size= ipower ( p, k);
247 int diff= (ext_field_size - 1)/(field_size - 1);
248 return GFPowUp (F, diff);
249}
250
251/// GFMapDown helper
252static inline
254{
255 if (F.isOne()) return F;
257 int exp;
259 if (F.inBaseDomain())
260 {
261 buf= F.getval();
262 exp= imm2int (buf);
263 if ((exp % k) == 0)
264 exp= exp/k;
265 else
266 return -1;
267
268 buf= int2imm_gf (exp);
269 return CanonicalForm (buf);
270 }
271 for (CFIterator i= F; i.hasTerms(); i++)
272 result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
273 return result;
274}
275
277{
278 int d= getGFDegree();
279 ASSERT (d % k == 0, "multiple of GF degree expected");
280 int p= getCharacteristic();
281 int ext_field_size= ipower (p, d);
282 int field_size= ipower ( p, k);
283 int diff= (ext_field_size - 1)/(field_size - 1);
284 return GFPowDown (F, diff);
285}
286
287/// map F in \f$ F_{p} (\alpha ) \f$ which is generated by G into some
288/// \f$ F_{p}(\beta ) \f$ which is generated by H
289static inline
291 const Variable& alpha, const CanonicalForm& H,
292 CFList& source, CFList& dest)
293{
295 int counter= 0;
296 int pos;
297 int p= getCharacteristic();
298 int d= degree (getMipo(alpha));
299 int bound= ipower(p, d);
302 CanonicalForm H_power;
303 if (degree(F) <= 0) return F;
304 if (F.level() < 0 && F.isUnivariate())
305 {
306 buf= F;
307 remainder= mod (buf, G);
308 ASSERT (remainder.isZero(), "alpha is not primitive");
309 pos= findItem (source, buf);
310 if (pos == 0)
311 source.append (buf);
312 buf2= buf;
313 while (degree (buf) != 0 && counter < bound)
314 {
315 buf /= G;
316 counter++;
317 if (buf == buf2) break;
318 }
319 ASSERT (counter <= bound, "alpha is not primitive");
320 if (pos == 0)
321 {
322 H_power= buf*power (H, counter);
323 dest.append (H_power);
324 }
325 else
326 H_power= getItem (dest, pos);
327 result = H_power;
328 return result;
329 }
330 else
331 {
332 for (CFIterator i= F; i.hasTerms(); i++)
333 {
334 buf= mapUp (i.coeff(), G, alpha, H, source, dest);
335 result += buf*power(F.mvar(), i.exp());
336 }
337 return result;
338 }
339}
340
343{
344 bool primitive= false;
345 fail= false;
346 primitive= isPrimitive (alpha, fail);
347 if (fail)
348 return 0;
349 if (primitive)
350 {
351 beta= alpha;
352 return alpha;
353 }
355 int d= degree (mipo);
356 int p= getCharacteristic ();
357 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
358 nmod_poly_t FLINT_mipo;
359 nmod_poly_init(FLINT_mipo,p);
360 #elif defined(HAVE_NTL)
361 if (fac_NTL_char != p)
362 {
364 zz_p::init (p);
365 }
366 zz_pX NTL_mipo;
367 #else
368 factoryError("NTL/FLINT missing: primitiveElement");
369 return CanonicalForm(0);
370 #endif
371 CanonicalForm mipo2;
372 primitive= false;
373 fail= false;
374 bool initialized= false;
375 do
376 {
377 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
378 nmod_poly_randtest_monic_irreducible(FLINT_mipo, FLINTrandom, d+1);
379 mipo2=convertnmod_poly_t2FacCF(FLINT_mipo,Variable(1));
380 #elif defined(HAVE_NTL)
381 BuildIrred (NTL_mipo, d);
382 mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
383 #endif
384 if (!initialized)
385 beta= rootOf (mipo2);
386 else
387 setMipo (beta, mipo2);
388 primitive= isPrimitive (beta, fail);
389 if (primitive)
390 break;
391 if (fail)
392 return 0;
393 } while (1);
394 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
395 nmod_poly_clear(FLINT_mipo);
396 // convert alpha_mipo
397 nmod_poly_t alpha_mipo;
398 convertFacCF2nmod_poly_t(alpha_mipo,mipo);
399 fq_nmod_ctx_t ctx;
400 fq_nmod_ctx_init_modulus(ctx,alpha_mipo,"t");
401 nmod_poly_clear(alpha_mipo);
402 // convert beta_mipo (mipo2)
403 fq_nmod_poly_t FLINT_beta_mipo;
404 convertFacCF2Fq_nmod_poly_t(FLINT_beta_mipo,mipo2,ctx);
405 fq_nmod_poly_factor_t fac;
406 fq_nmod_poly_factor_init(fac,ctx);
407 fq_nmod_poly_roots(fac, FLINT_beta_mipo, 0, ctx);
408 // root of first (linear) factor: -absolute Term
409 fq_nmod_t r0;
410 fq_nmod_init(r0, ctx);
411 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
412 fq_nmod_neg(r0, r0, ctx);
413 // convert
415 // cleanup
416 fq_nmod_poly_factor_clear(fac,ctx);
417 fq_nmod_clear(r0, ctx);
418 fq_nmod_poly_clear(FLINT_beta_mipo,ctx);
420 return r1;
421 #elif defined(HAVE_NTL)
422 zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
423 zz_pE::init (alpha_mipo);
424 zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
425 zz_pE root= FindRoot (NTL_beta_mipo);
426 return convertNTLzzpE2CF (root, alpha);
427 #endif
428}
429
431mapDown (const CanonicalForm& F, const CanonicalForm& prim_elem, const
432 CanonicalForm& im_prim_elem, const Variable& alpha, CFList& source,
433 CFList& dest)
434{
435 return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
436}
437
439mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& /*beta*/,
440 const CanonicalForm& prim_elem, const CanonicalForm& im_prim_elem,
441 CFList& source, CFList& dest)
442{
443 if (prim_elem == alpha)
444 return F (im_prim_elem, alpha);
445 return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
446}
447
448#if defined(HAVE_NTL) || defined(HAVE_FLINT)
450mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
451 const Variable& beta)
452{
453 if (primElem == alpha)
454 return mapUp (alpha, beta);
455 else
456 {
457 CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
458 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
459 // convert mipo1
460 nmod_poly_t mipo1;
462 fq_nmod_ctx_t ctx;
463 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
464 nmod_poly_clear(mipo1);
465 // convert mipo2 (primElemMipo)
466 fq_nmod_poly_t mipo2;
467 convertFacCF2Fq_nmod_poly_t(mipo2,primElemMipo,ctx);
468 fq_nmod_poly_factor_t fac;
469 fq_nmod_poly_factor_init(fac,ctx);
470 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
471 // root of first (linear) factor: -absolute Term
472 fq_nmod_t r0;
473 fq_nmod_init(r0, ctx);
474 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
475 fq_nmod_neg(r0, r0, ctx);
476 // convert
478 // cleanup
479 fq_nmod_poly_factor_clear(fac,ctx);
480 fq_nmod_clear(r0, ctx);
481 fq_nmod_poly_clear(mipo2,ctx);
483 return r1;
484 #elif defined(HAVE_NTL)
485 int p= getCharacteristic ();
486 if (fac_NTL_char != p)
487 {
489 zz_p::init (p);
490 }
491 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
492 zz_pE::init (NTLMipo);
493 zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
494 zz_pE root= FindRoot (NTLPrimElemMipo);
495 return convertNTLzzpE2CF (root, beta);
496 #else
497 factoryError("NTL/FLINT missing: mapPrimElem");
498 #endif
499 }
500}
501#endif
502
504map (const CanonicalForm& primElem, const Variable& alpha,
505 const CanonicalForm& F, const Variable& beta)
506{
507 CanonicalForm G= F;
508 int order= 0;
509 while (!G.isOne())
510 {
511 G /= primElem;
512 order++;
513 }
514 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
515 // convert mipo
516 nmod_poly_t mipo1;
518 fq_nmod_ctx_t ctx;
519 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
520 nmod_poly_clear(mipo1);
521 // convert mipo2 (alpha)
522 fq_nmod_poly_t mipo2;
524 fq_nmod_poly_factor_t fac;
525 fq_nmod_poly_factor_init(fac,ctx);
526 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
527 // roots in fac, #=fac->num
528 int ind=-1;
529 fq_nmod_t r0,FLINTbeta;
530 fq_nmod_init(r0, ctx);
531 fq_nmod_init(FLINTbeta, ctx);
532 convertFacCF2Fq_nmod_t(FLINTbeta,beta,ctx);
533 fmpz_t FLINTorder;
534 fmpz_set_si(FLINTorder,order);
535 for(int i=0;i< fac->num;i++)
536 {
537 // get the root (-abs.term of linear factor)
538 fq_nmod_poly_get_coeff(r0,fac->poly+i,0,ctx);
539 fq_nmod_neg(r0,r0,ctx);
540 // r^order
541 fq_nmod_pow(r0,r0,FLINTorder,ctx);
542 // ==beta?
543 if (fq_nmod_equal(r0,FLINTbeta,ctx))
544 {
545 ind=i;
546 break;
547 }
548 }
549 fmpz_clear(FLINTorder);
550 // convert
551 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
552 fq_nmod_neg(r0,r0,ctx);
554 // cleanup
555 fq_nmod_poly_factor_clear(fac,ctx);
556 fq_nmod_clear(r0, ctx);
557 fq_nmod_clear(FLINTbeta,ctx);
558 fq_nmod_poly_clear(mipo2,ctx);
560 return r1;
561 #elif defined(HAVE_NTL)
562 int p= getCharacteristic ();
563 if (fac_NTL_char != p)
564 {
566 zz_p::init (p);
567 }
568 zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
569 zz_pE::init (NTL_mipo);
570 zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
571 zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
572 vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
573 long ind=-1;
574 for (long i= 0; i < roots.length(); i++)
575 {
576 if (power (roots [i], order)== NTLBeta)
577 {
578 ind= i;
579 break;
580 }
581 }
582 return (convertNTLzzpE2CF (roots[ind], beta));
583 #else
584 factoryError("NTL/FLINT missing: map");
585 return CanonicalForm(0);
586 #endif
587}
588
589#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
590/*
591 g is in Fp[x]
592 F is in Fp[t]
593 h is in Fp[t]
594 In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
595 g(F(t)) = 0 mod h(t)
596 i.e. g is the minpoly of the element F(t) of the finite field.
597*/
598static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
599{
600 slong i;
601 slong d = nmod_poly_degree(h);
602 mp_limb_t p = h->mod.n;
603 nmod_poly_t Fpow;
604 nmod_berlekamp_massey_t bma;
605
606 nmod_poly_init(Fpow, p);
607 nmod_berlekamp_massey_init(bma, p);
608
609 nmod_poly_one(Fpow);
610 for (i = 0; i < 2*d; i++)
611 {
612 nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
613 nmod_poly_mulmod(Fpow, Fpow, F, h);
614 }
615
616 nmod_berlekamp_massey_reduce(bma);
617
618 /* something went horribly wrong if V does not kill the whole sequence */
619 FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
620 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
621
622 nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
623#if WANT_ASSERT
624 {
625 nmod_poly_t z;
626 nmod_poly_init(z, p);
627 nmod_poly_compose_mod(z, g, F, h);
628 FLINT_ASSERT(nmod_poly_is_zero(z));
630 }
631#endif
632 nmod_poly_clear(Fpow);
633 nmod_berlekamp_massey_clear(bma);
634}
635#endif
636
637
638#if defined(HAVE_NTL) || defined(HAVE_FLINT)
641{
642 ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
643
644 int p=getCharacteristic();
645 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
646 nmod_poly_t FLINT_F,FLINT_alpha,g;
648 convertFacCF2nmod_poly_t(FLINT_F,F);
650 minpoly(g,FLINT_F,FLINT_alpha);
651 nmod_poly_clear(FLINT_alpha);
652 nmod_poly_clear(FLINT_F);
655 return res;
656 #elif defined(HAVE_NTL)
657 if (fac_NTL_char != p)
658 {
660 zz_p::init (p);
661 }
662 zz_pX NTLF= convertFacCF2NTLzzpX (F);
663 int d= degree (getMipo (alpha));
664
665 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
666 zz_pE::init (NTLMipo);
667 vec_zz_p pows;
668 pows.SetLength (2*d);
669
670 zz_pE powNTLF;
671 set (powNTLF);
672 zz_pE NTLFE= to_zz_pE (NTLF);
673 zz_pX buf;
674 for (int i= 0; i < 2*d; i++)
675 {
676 buf= rep (powNTLF);
677 buf.rep.SetLength (d);
678 pows [i]= buf.rep[0];
679 powNTLF *= NTLFE;
680 }
681
682 zz_pX NTLMinPoly;
683 MinPolySeq (NTLMinPoly, pows, d);
684
685 return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
686 #else
687 factoryError("NTL/FLINT missing: findMinPoly");
688 #endif
689}
690#endif
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...
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
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
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:255
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition: NTLconvert.cc:799
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
Conversion to and from NTL.
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
int getGFDegree()
Definition: cf_char.cc:75
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
bool isPrimitive(const Variable &alpha, bool &fail)
checks if alpha is a primitive element, alpha is assumed to be an algebraic variable over some finite...
Definition: cf_cyclo.cc:131
Compute cyclotomic polynomials and factorize integers by brute force.
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
Definition: cf_map_ext.cc:450
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
Definition: cf_map_ext.cc:175
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:276
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
Definition: cf_map_ext.cc:342
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition: cf_map_ext.cc:640
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition: cf_map_ext.cc:123
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition: cf_map_ext.cc:70
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
Definition: cf_map_ext.cc:229
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition: cf_map_ext.cc:203
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition: cf_map_ext.cc:240
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
Definition: cf_map_ext.cc:195
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
Definition: cf_map_ext.cc:504
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
Definition: cf_map_ext.cc:253
This file implements functions to map between extensions of finite fields.
GLOBAL_VAR flint_rand_t FLINTrandom
Definition: cf_random.cc:25
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
InternalCF * getval() const
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool inBaseDomain() const
CanonicalForm mapinto() const
bool isUnivariate() const
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: variable.h:33
functions to print debug output
Variable alpha
Definition: facAbsBiFact.cc:51
return result
Definition: facAbsBiFact.cc:75
#define slong
CanonicalForm res
Definition: facAbsFact.cc:60
Variable beta
Definition: facAbsFact.cc:95
CanonicalForm H
Definition: facAbsFact.cc:60
CanonicalForm mipo
Definition: facAlgExt.cc:57
CanonicalForm buf2
Definition: facFqBivar.cc:73
int j
Definition: facHensel.cc:110
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition: fac_util.cc:115
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR Poly * h
Definition: janet.cc:971
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45
int status int void * buf
Definition: si_signals.h:59
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162