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#include <flint/fq_nmod_poly_factor.h>
34#endif
35
36// cyclotomoic polys:
37#include "cf_cyclo.h"
38
39#include "cf_map_ext.h"
40
41/// helper function
42int findItem (const CFList& list, const CanonicalForm& item)
43{
44 int result= 1;
45 for (CFListIterator i= list; i.hasItem(); i++, result++)
46 {
47 if (i.getItem() == item)
48 return result;
49 }
50 return 0;
51}
52
53/// helper function
54CanonicalForm getItem (const CFList& list, const int& pos)
55{
56 int j= 1;
57 if ((pos > 0) && (pos <= list.length()))
58 {
59 for (CFListIterator i= list; j <= pos; i++, j++)
60 {
61 if (j == pos)
62 return i.getItem();
63 }
64 }
65 return 0;
66}
67
68/// \f$ F_{p} (\alpha ) \subset F_{p}(\beta ) \f$ and \f$ \alpha \f$ is a
69/// primitive element, returns the image of \f$ \alpha \f$
70static inline
72{
73 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
74 // convert mipo1
75 nmod_poly_t mipo1;
77 fq_nmod_ctx_t ctx;
78 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
79 nmod_poly_clear(mipo1);
80 // convert mipo2 (alpah)
81 fq_nmod_poly_t mipo2;
83 fq_nmod_poly_factor_t fac;
84 fq_nmod_poly_factor_init(fac,ctx);
85 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
86 // root of first (linear) factor: -absolute Term
87 fq_nmod_t r0;
88 fq_nmod_init(r0, ctx);
89 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
90 fq_nmod_neg(r0, r0, ctx);
91 // convert
93 // cleanup
94 fq_nmod_poly_factor_clear(fac,ctx);
95 fq_nmod_clear(r0, ctx);
96 fq_nmod_poly_clear(mipo2,ctx);
98 return r1;
99 #elif defined(HAVE_NTL)
100 int p= getCharacteristic ();
101 if (fac_NTL_char != p)
102 {
104 zz_p::init (p);
105 }
106 zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
107 zz_pE::init (NTL_mipo);
108 zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
109 zz_pE root= FindRoot (NTL_alpha_mipo);
110 return convertNTLzzpE2CF (root, beta);
111 #else
112 factoryError("NTL/FLINT missing: mapUp");
113 return CanonicalForm(0); // to avoid warnings
114 #endif
115}
116
117
118/// the CanonicalForm G is the output of map_up, returns F considered as an
119/// element over \f$ F_{p}(\alpha ) \f$, WARNING: make sure coefficients of F
120/// are really elements of a subfield of \f$ F_{p}(\beta ) \f$ which is
121/// isomorphic to \f$ F_{p}(\alpha ) \f$
122static inline
124mapDown (const CanonicalForm& F, const Variable& alpha, const
125 CanonicalForm& G, CFList& source, CFList& dest)
126{
128 int counter= 0;
129 int pos;
130 int p= getCharacteristic();
131 int d= degree(getMipo(alpha));
132 int bound= ipower(p, d);
135 CanonicalForm alpha_power;
136 if (degree(F) == 0) return F;
137 if (F.level() < 0 && F.isUnivariate())
138 {
139 buf= F;
140 remainder= mod (buf, G);
141 ASSERT (remainder.isZero(), "alpha is not primitive");
142 pos= findItem (source, buf);
143 if (pos == 0)
144 source.append (buf);
145 buf2= buf;
146 while (degree (buf) != 0 && counter < bound)
147 {
148 buf /= G;
149 counter++;
150 if (buf == buf2) break;
151 }
152 ASSERT (counter >= bound, "alpha is not primitive");
153 if (pos == 0)
154 {
155 alpha_power= power (alpha, counter);
156 dest.append (alpha_power);
157 }
158 else
159 alpha_power= getItem (dest, pos);
160 result = alpha_power;
161 return result;
162 }
163 else
164 {
165 for (CFIterator i= F; i.hasTerms(); i++)
166 {
167 buf= mapDown (i.coeff(), alpha, G, source, dest);
168 result += buf*power(F.mvar(), i.exp());
169 }
170 return result;
171 }
172}
173
174/// helper function
175static inline
177{
178 if (F.isZero())
179 return 0;
180 int exp;
183 if (F.inBaseDomain())
184 {
185 if (F.isOne()) return 1;
186 buf= F.getval();
187 exp= imm2int(buf);
189 return result;
190 }
191 for (CFIterator i= F; i.hasTerms(); i++)
192 result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
193 return result;
194}
195
203
205{
208
209 if (F.inCoeffDomain())
210 {
211 if (F.inBaseDomain())
212 return F.mapinto();
213 else
214 {
215 for (CFIterator i= F; i.hasTerms(); i++)
216 {
217 buf= int2imm_gf (i.exp());
218 result += i.coeff().mapinto()*CanonicalForm (buf);
219 }
220 }
221 return result;
222 }
223 for (CFIterator i= F; i.hasTerms(); i++)
224 result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
225 return result;
226}
227
228/// GF_map_up helper
229static inline
231{
232 if (F.isOne()) return F;
234 if (F.inBaseDomain())
235 return power(F, k);
236 for (CFIterator i= F; i.hasTerms(); i++)
237 result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
238 return result;
239}
240
242{
243 int d= getGFDegree();
244 ASSERT (d%k == 0, "multiple of GF degree expected");
245 int p= getCharacteristic();
246 int ext_field_size= ipower (p, d);
247 int field_size= ipower ( p, k);
248 int diff= (ext_field_size - 1)/(field_size - 1);
249 return GFPowUp (F, diff);
250}
251
252/// GFMapDown helper
253static inline
255{
256 if (F.isOne()) return F;
258 int exp;
260 if (F.inBaseDomain())
261 {
262 buf= F.getval();
263 exp= imm2int (buf);
264 if ((exp % k) == 0)
265 exp= exp/k;
266 else
267 return -1;
268
269 buf= int2imm_gf (exp);
270 return CanonicalForm (buf);
271 }
272 for (CFIterator i= F; i.hasTerms(); i++)
273 result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
274 return result;
275}
276
278{
279 int d= getGFDegree();
280 ASSERT (d % k == 0, "multiple of GF degree expected");
281 int p= getCharacteristic();
282 int ext_field_size= ipower (p, d);
283 int field_size= ipower ( p, k);
284 int diff= (ext_field_size - 1)/(field_size - 1);
285 return GFPowDown (F, diff);
286}
287
288/// map F in \f$ F_{p} (\alpha ) \f$ which is generated by G into some
289/// \f$ F_{p}(\beta ) \f$ which is generated by H
290static inline
292 const Variable& alpha, const CanonicalForm& H,
293 CFList& source, CFList& dest)
294{
296 int counter= 0;
297 int pos;
298 int p= getCharacteristic();
299 int d= degree (getMipo(alpha));
300 int bound= ipower(p, d);
303 CanonicalForm H_power;
304 if (degree(F) <= 0) return F;
305 if (F.level() < 0 && F.isUnivariate())
306 {
307 buf= F;
308 remainder= mod (buf, G);
309 ASSERT (remainder.isZero(), "alpha is not primitive");
310 pos= findItem (source, buf);
311 if (pos == 0)
312 source.append (buf);
313 buf2= buf;
314 while (degree (buf) != 0 && counter < bound)
315 {
316 buf /= G;
317 counter++;
318 if (buf == buf2) break;
319 }
320 ASSERT (counter <= bound, "alpha is not primitive");
321 if (pos == 0)
322 {
323 H_power= buf*power (H, counter);
324 dest.append (H_power);
325 }
326 else
327 H_power= getItem (dest, pos);
328 result = H_power;
329 return result;
330 }
331 else
332 {
333 for (CFIterator i= F; i.hasTerms(); i++)
334 {
335 buf= mapUp (i.coeff(), G, alpha, H, source, dest);
336 result += buf*power(F.mvar(), i.exp());
337 }
338 return result;
339 }
340}
341
344{
345 bool primitive= false;
346 fail= false;
347 primitive= isPrimitive (alpha, fail);
348 if (fail)
349 return 0;
350 if (primitive)
351 {
352 beta= alpha;
353 return alpha;
354 }
356 int d= degree (mipo);
357 int p= getCharacteristic ();
358 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
359 nmod_poly_t FLINT_mipo;
360 nmod_poly_init(FLINT_mipo,p);
361 #elif defined(HAVE_NTL)
362 if (fac_NTL_char != p)
363 {
365 zz_p::init (p);
366 }
367 zz_pX NTL_mipo;
368 #else
369 factoryError("NTL/FLINT missing: primitiveElement");
370 return CanonicalForm(0);
371 #endif
372 CanonicalForm mipo2;
373 primitive= false;
374 fail= false;
375 bool initialized= false;
376 do
377 {
378 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
379 nmod_poly_randtest_monic_irreducible(FLINT_mipo, FLINTrandom, d+1);
380 mipo2=convertnmod_poly_t2FacCF(FLINT_mipo,Variable(1));
381 #elif defined(HAVE_NTL)
382 BuildIrred (NTL_mipo, d);
383 mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
384 #endif
385 if (!initialized)
386 beta= rootOf (mipo2);
387 else
388 setMipo (beta, mipo2);
389 primitive= isPrimitive (beta, fail);
390 if (primitive)
391 break;
392 if (fail)
393 return 0;
394 } while (1);
395 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
396 nmod_poly_clear(FLINT_mipo);
397 // convert alpha_mipo
398 nmod_poly_t alpha_mipo;
399 convertFacCF2nmod_poly_t(alpha_mipo,mipo);
400 fq_nmod_ctx_t ctx;
401 fq_nmod_ctx_init_modulus(ctx,alpha_mipo,"t");
402 nmod_poly_clear(alpha_mipo);
403 // convert beta_mipo (mipo2)
404 fq_nmod_poly_t FLINT_beta_mipo;
405 convertFacCF2Fq_nmod_poly_t(FLINT_beta_mipo,mipo2,ctx);
406 fq_nmod_poly_factor_t fac;
407 fq_nmod_poly_factor_init(fac,ctx);
408 fq_nmod_poly_roots(fac, FLINT_beta_mipo, 0, ctx);
409 // root of first (linear) factor: -absolute Term
410 fq_nmod_t r0;
411 fq_nmod_init(r0, ctx);
412 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
413 fq_nmod_neg(r0, r0, ctx);
414 // convert
416 // cleanup
417 fq_nmod_poly_factor_clear(fac,ctx);
418 fq_nmod_clear(r0, ctx);
419 fq_nmod_poly_clear(FLINT_beta_mipo,ctx);
421 return r1;
422 #elif defined(HAVE_NTL)
423 zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
424 zz_pE::init (alpha_mipo);
425 zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
426 zz_pE root= FindRoot (NTL_beta_mipo);
427 return convertNTLzzpE2CF (root, alpha);
428 #endif
429}
430
432mapDown (const CanonicalForm& F, const CanonicalForm& prim_elem, const
433 CanonicalForm& im_prim_elem, const Variable& alpha, CFList& source,
434 CFList& dest)
435{
436 return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
437}
438
440mapUp (const CanonicalForm& F, const Variable& alpha, const Variable& /*beta*/,
441 const CanonicalForm& prim_elem, const CanonicalForm& im_prim_elem,
442 CFList& source, CFList& dest)
443{
444 if (prim_elem == alpha)
445 return F (im_prim_elem, alpha);
446 return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
447}
448
449#if defined(HAVE_NTL) || defined(HAVE_FLINT)
451mapPrimElem (const CanonicalForm& primElem, const Variable& alpha,
452 const Variable& beta)
453{
454 if (primElem == alpha)
455 return mapUp (alpha, beta);
456 else
457 {
458 CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
459 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
460 // convert mipo1
461 nmod_poly_t mipo1;
463 fq_nmod_ctx_t ctx;
464 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
465 nmod_poly_clear(mipo1);
466 // convert mipo2 (primElemMipo)
467 fq_nmod_poly_t mipo2;
468 convertFacCF2Fq_nmod_poly_t(mipo2,primElemMipo,ctx);
469 fq_nmod_poly_factor_t fac;
470 fq_nmod_poly_factor_init(fac,ctx);
471 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
472 // root of first (linear) factor: -absolute Term
473 fq_nmod_t r0;
474 fq_nmod_init(r0, ctx);
475 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
476 fq_nmod_neg(r0, r0, ctx);
477 // convert
479 // cleanup
480 fq_nmod_poly_factor_clear(fac,ctx);
481 fq_nmod_clear(r0, ctx);
482 fq_nmod_poly_clear(mipo2,ctx);
484 return r1;
485 #elif defined(HAVE_NTL)
486 int p= getCharacteristic ();
487 if (fac_NTL_char != p)
488 {
490 zz_p::init (p);
491 }
492 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
493 zz_pE::init (NTLMipo);
494 zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
495 zz_pE root= FindRoot (NTLPrimElemMipo);
496 return convertNTLzzpE2CF (root, beta);
497 #else
498 factoryError("NTL/FLINT missing: mapPrimElem");
499 #endif
500 }
501}
502#endif
503
505map (const CanonicalForm& primElem, const Variable& alpha,
506 const CanonicalForm& F, const Variable& beta)
507{
508 CanonicalForm G= F;
509 int order= 0;
510 while (!G.isOne())
511 {
512 G /= primElem;
513 order++;
514 }
515 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
516 // convert mipo
517 nmod_poly_t mipo1;
519 fq_nmod_ctx_t ctx;
520 fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
521 nmod_poly_clear(mipo1);
522 // convert mipo2 (alpha)
523 fq_nmod_poly_t mipo2;
525 fq_nmod_poly_factor_t fac;
526 fq_nmod_poly_factor_init(fac,ctx);
527 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
528 // roots in fac, #=fac->num
529 int ind=-1;
530 fq_nmod_t r0,FLINTbeta;
531 fq_nmod_init(r0, ctx);
532 fq_nmod_init(FLINTbeta, ctx);
533 convertFacCF2Fq_nmod_t(FLINTbeta,beta,ctx);
534 fmpz_t FLINTorder;
535 fmpz_set_si(FLINTorder,order);
536 for(int i=0;i< fac->num;i++)
537 {
538 // get the root (-abs.term of linear factor)
539 fq_nmod_poly_get_coeff(r0,fac->poly+i,0,ctx);
540 fq_nmod_neg(r0,r0,ctx);
541 // r^order
542 fq_nmod_pow(r0,r0,FLINTorder,ctx);
543 // ==beta?
544 if (fq_nmod_equal(r0,FLINTbeta,ctx))
545 {
546 ind=i;
547 break;
548 }
549 }
550 fmpz_clear(FLINTorder);
551 // convert
552 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
553 fq_nmod_neg(r0,r0,ctx);
555 // cleanup
556 fq_nmod_poly_factor_clear(fac,ctx);
557 fq_nmod_clear(r0, ctx);
558 fq_nmod_clear(FLINTbeta,ctx);
559 fq_nmod_poly_clear(mipo2,ctx);
561 return r1;
562 #elif defined(HAVE_NTL)
563 int p= getCharacteristic ();
564 if (fac_NTL_char != p)
565 {
567 zz_p::init (p);
568 }
569 zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
570 zz_pE::init (NTL_mipo);
571 zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
572 zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
573 vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
574 long ind=-1;
575 for (long i= 0; i < roots.length(); i++)
576 {
577 if (power (roots [i], order)== NTLBeta)
578 {
579 ind= i;
580 break;
581 }
582 }
583 return (convertNTLzzpE2CF (roots[ind], beta));
584 #else
585 factoryError("NTL/FLINT missing: map");
586 return CanonicalForm(0);
587 #endif
588}
589
590#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
591/*
592 g is in Fp[x]
593 F is in Fp[t]
594 h is in Fp[t]
595 In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that
596 g(F(t)) = 0 mod h(t)
597 i.e. g is the minpoly of the element F(t) of the finite field.
598*/
599static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
600{
601 slong i;
602 slong d = nmod_poly_degree(h);
603 mp_limb_t p = h->mod.n;
604 nmod_poly_t Fpow;
605 nmod_berlekamp_massey_t bma;
606
607 nmod_poly_init(Fpow, p);
608 nmod_berlekamp_massey_init(bma, p);
609
610 nmod_poly_one(Fpow);
611 for (i = 0; i < 2*d; i++)
612 {
613 nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
614 nmod_poly_mulmod(Fpow, Fpow, F, h);
615 }
616
617 nmod_berlekamp_massey_reduce(bma);
618
619 /* something went horribly wrong if V does not kill the whole sequence */
620 FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
621 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
622
623 nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
624#if WANT_ASSERT
625 {
626 nmod_poly_t z;
627 nmod_poly_init(z, p);
628 nmod_poly_compose_mod(z, g, F, h);
629 FLINT_ASSERT(nmod_poly_is_zero(z));
631 }
632#endif
633 nmod_poly_clear(Fpow);
634 nmod_berlekamp_massey_clear(bma);
635}
636#endif
637
638
639#if defined(HAVE_NTL) || defined(HAVE_FLINT)
642{
643 ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
644
645 int p=getCharacteristic();
646 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
647 nmod_poly_t FLINT_F,FLINT_alpha,g;
649 convertFacCF2nmod_poly_t(FLINT_F,F);
651 minpoly(g,FLINT_F,FLINT_alpha);
652 nmod_poly_clear(FLINT_alpha);
653 nmod_poly_clear(FLINT_F);
656 return res;
657 #elif defined(HAVE_NTL)
658 if (fac_NTL_char != p)
659 {
661 zz_p::init (p);
662 }
663 zz_pX NTLF= convertFacCF2NTLzzpX (F);
664 int d= degree (getMipo (alpha));
665
666 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
667 zz_pE::init (NTLMipo);
668 vec_zz_p pows;
669 pows.SetLength (2*d);
670
671 zz_pE powNTLF;
672 set (powNTLF);
673 zz_pE NTLFE= to_zz_pE (NTLF);
674 zz_pX buf;
675 for (int i= 0; i < 2*d; i++)
676 {
677 buf= rep (powNTLF);
678 buf.rep.SetLength (d);
679 pows [i]= buf.rep[0];
680 powNTLF *= NTLFE;
681 }
682
683 zz_pX NTLMinPoly;
684 MinPolySeq (NTLMinPoly, pows, d);
685
686 return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
687 #else
688 factoryError("NTL/FLINT missing: findMinPoly");
689 #endif
690}
691#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)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
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
ListIterator< CanonicalForm > CFListIterator
List< CanonicalForm > CFList
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:4086
g
Definition cfModGcd.cc:4098
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:42
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
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
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
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 ,...
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc:54
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
CanonicalForm GFMapUp(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
CanonicalForm GF2FalphaRep(const CanonicalForm &F, const Variable &alpha)
changes representation by primitive element to representation by residue classes modulo a Conway poly...
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
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
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
void append(const T &)
factory's class for variables
Definition factory.h:127
functions to print debug output
Variable alpha
return result
#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:76
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
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition variable.cc:219
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)
STATIC_VAR gmp_float * diff
int status int void * buf
Definition si_signals.h:69