My Project
Loading...
Searching...
No Matches
cf_map_ext.cc File Reference

This file implements functions to map between extensions of finite fields. More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "canonicalform.h"
#include "cf_util.h"
#include "imm.h"
#include "cf_iter.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"
#include <flint/fq_nmod_poly_factor.h>
#include "cf_cyclo.h"
#include "cf_map_ext.h"

Go to the source code of this file.

Functions

int findItem (const CFList &list, const CanonicalForm &item)
 helper function
 
CanonicalForm getItem (const CFList &list, const int &pos)
 helper function
 
static CanonicalForm mapUp (const Variable &alpha, const Variable &beta)
 $ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and $ \alpha $ is a primitive element, returns the image of $ \alpha $
 
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 $ F_{p}(\alpha ) $, WARNING: make sure coefficients of F are really elements of a subfield of $ F_{p}(\beta ) $ which is isomorphic to $ F_{p}(\alpha ) $
 
static CanonicalForm GF2FalphaHelper (const CanonicalForm &F, const Variable &alpha)
 helper function
 
CanonicalForm GF2FalphaRep (const CanonicalForm &F, const Variable &alpha)
 changes representation by primitive element to representation by residue classes modulo a Conway polynomial
 
CanonicalForm Falpha2GFRep (const CanonicalForm &F)
 change representation by residue classes modulo a Conway polynomial to representation by primitive element
 
static CanonicalForm GFPowUp (const CanonicalForm &F, int k)
 GF_map_up helper.
 
CanonicalForm GFMapUp (const CanonicalForm &F, int k)
 maps a polynomial over $ GF(p^{k}) $ to a polynomial over $ GF(p^{d}) $ , d needs to be a multiple of k
 
static CanonicalForm GFPowDown (const CanonicalForm &F, int k)
 GFMapDown helper.
 
CanonicalForm GFMapDown (const CanonicalForm &F, int k)
 maps a polynomial over $ GF(p^{d}) $ to a polynomial over $ GF(p^{k})$ , d needs to be a multiple of k
 
static CanonicalForm mapUp (const CanonicalForm &F, const CanonicalForm &G, const Variable &alpha, const CanonicalForm &H, CFList &source, CFList &dest)
 map F in $ F_{p} (\alpha ) $ which is generated by G into some $ F_{p}(\beta ) $ which is generated by H
 
CanonicalForm primitiveElement (const Variable &alpha, Variable &beta, bool &fail)
 determine a primitive element of $ F_{p} (\alpha ) $, $ \beta $ is a primitive element of a field which is isomorphic to $ F_{p}(\alpha ) $
 
CanonicalForm mapDown (const CanonicalForm &F, const CanonicalForm &prim_elem, const CanonicalForm &im_prim_elem, const Variable &alpha, CFList &source, CFList &dest)
 map F from $ F_{p} (\beta ) $ to $ F_{p}(\alpha ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and F in $ F_{p}(\alpha ) $.
 
CanonicalForm mapUp (const CanonicalForm &F, const Variable &alpha, const Variable &, const CanonicalForm &prim_elem, const CanonicalForm &im_prim_elem, CFList &source, CFList &dest)
 map F from $ F_{p} (\alpha ) $ to $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $.
 
CanonicalForm mapPrimElem (const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
 compute the image of a primitive element of $ F_{p} (\alpha ) $ in $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $.
 
CanonicalForm map (const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
 map from $ F_p(\alpha) $ to $ F_p(\beta) $ such that $ F\in F_p(\alpha) $ is mapped onto $ \beta $
 
CanonicalForm findMinPoly (const CanonicalForm &F, const Variable &alpha)
 compute minimal polynomial of $ F\in F_p(\alpha)\backslash F_p $ via NTL
 

Detailed Description

This file implements functions to map between extensions of finite fields.

Copyright:
(c) by The SINGULAR Team, see LICENSE file
Author
Martin Lee
Date
16.11.2009

Definition in file cf_map_ext.cc.

Function Documentation

◆ Falpha2GFRep()

CanonicalForm Falpha2GFRep ( const CanonicalForm & F)

change representation by residue classes modulo a Conway polynomial to representation by primitive element

Parameters
[in]Fsome poly over F_p(alpha) where alpha is a root of a Conway poly

Definition at line 204 of file cf_map_ext.cc.

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}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int i
Definition cfEzgcd.cc:132
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
class to iterate through CanonicalForm's
Definition cf_iter.h:44
factory's main class
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
bool inBaseDomain() const
CanonicalForm mapinto() const
virtual class for internal CanonicalForm's
Definition int_cf.h:47
return result
InternalCF * int2imm_gf(long i)
Definition imm.h:106
int status int void * buf
Definition si_signals.h:69

◆ findItem()

int findItem ( const CFList & list,
const CanonicalForm & item )

helper function

Definition at line 42 of file cf_map_ext.cc.

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}
ListIterator< CanonicalForm > CFListIterator

◆ findMinPoly()

CanonicalForm findMinPoly ( const CanonicalForm & F,
const Variable & alpha )

compute minimal polynomial of $ F\in F_p(\alpha)\backslash F_p $ via NTL

Returns
findMinPoly computes the minimal polynomial of F
Parameters
[in]Fan element of $ F_p(\alpha)\backslash F_p $
[in]alphaalgebraic variable

Definition at line 641 of file cf_map_ext.cc.

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}
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
VAR long fac_NTL_char
Definition NTLconvert.cc:46
int degree(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
int p
Definition cfModGcd.cc:4086
g
Definition cfModGcd.cc:4098
#define ASSERT(expression, message)
Definition cf_assert.h:99
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
bool isUnivariate() const
factory's class for variables
Definition factory.h:127
Variable alpha
CanonicalForm res
Definition facAbsFact.cc:60
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207

◆ getItem()

CanonicalForm getItem ( const CFList & list,
const int & pos )

helper function

Definition at line 54 of file cf_map_ext.cc.

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}
int length() const
int j
Definition facHensel.cc:110

◆ GF2FalphaHelper()

static CanonicalForm GF2FalphaHelper ( const CanonicalForm & F,
const Variable & alpha )
inlinestatic

helper function

Definition at line 176 of file cf_map_ext.cc.

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}
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
CF_NO_INLINE bool isZero() const
InternalCF * getval() const
CF_NO_INLINE bool isOne() const
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
gmp_float exp(const gmp_float &a)

◆ GF2FalphaRep()

CanonicalForm GF2FalphaRep ( const CanonicalForm & F,
const Variable & alpha )

changes representation by primitive element to representation by residue classes modulo a Conway polynomial

Parameters
[in]Fsome poly over GF
[in]alpharoot of a Conway poly

Definition at line 196 of file cf_map_ext.cc.

197{
200 prune (beta);
201 return result;
202}
Variable beta
Definition facAbsFact.cc:95
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
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56

◆ GFMapDown()

CanonicalForm GFMapDown ( const CanonicalForm & F,
int k )

maps a polynomial over $ GF(p^{d}) $ to a polynomial over $ GF(p^{k})$ , d needs to be a multiple of k

Definition at line 277 of file cf_map_ext.cc.

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}
int getGFDegree()
Definition cf_char.cc:75
int k
Definition cfEzgcd.cc:99
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
STATIC_VAR gmp_float * diff

◆ GFMapUp()

CanonicalForm GFMapUp ( const CanonicalForm & F,
int k )

maps a polynomial over $ GF(p^{k}) $ to a polynomial over $ GF(p^{d}) $ , d needs to be a multiple of k

Definition at line 241 of file cf_map_ext.cc.

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}
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.

◆ GFPowDown()

static CanonicalForm GFPowDown ( const CanonicalForm & F,
int k )
inlinestatic

GFMapDown helper.

Definition at line 254 of file cf_map_ext.cc.

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}

◆ GFPowUp()

static CanonicalForm GFPowUp ( const CanonicalForm & F,
int k )
inlinestatic

GF_map_up helper.

Definition at line 230 of file cf_map_ext.cc.

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}

◆ map()

CanonicalForm map ( const CanonicalForm & primElem,
const Variable & alpha,
const CanonicalForm & F,
const Variable & beta )

map from $ F_p(\alpha) $ to $ F_p(\beta) $ such that $ F\in F_p(\alpha) $ is mapped onto $ \beta $

Returns
map returns the image of primElem such that the above described properties hold
Parameters
[in]primElemprimitive element of $ F_p (\alpha) $
[in]alphaalgebraic variable
[in]Fan element of $ F_p (\alpha) $, whose minimal polynomial defines a field extension of $ F_p $ of degree $ F_p (\alpha):F_p $
[in]betaalgebraic variable, root of F's minimal polynomial

Definition at line 505 of file cf_map_ext.cc.

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}
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...
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
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear(prod, fq_con)
STATIC_VAR TreeM * G
Definition janet.cc:31

◆ mapDown() [1/2]

CanonicalForm mapDown ( const CanonicalForm & F,
const CanonicalForm & prim_elem,
const CanonicalForm & im_prim_elem,
const Variable & alpha,
CFList & source,
CFList & dest )

map F from $ F_{p} (\beta ) $ to $ F_{p}(\alpha ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and F in $ F_{p}(\alpha ) $.

Parameters
[in]Fpoly over $ F_{p} (\beta ) $
[in]prim_elemprimitive element of $ F_{p} (\alpha ) $
[in]im_prim_elemimage of prim_elem in $ F_{p} (\beta ) $
[in]alphaalg. variable
source[in,out] look up lists
dest[in,out] look up lists

Definition at line 432 of file cf_map_ext.cc.

435{
436 return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
437}
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71

◆ mapDown() [2/2]

static CanonicalForm mapDown ( const CanonicalForm & F,
const Variable & alpha,
const CanonicalForm & G,
CFList & source,
CFList & dest )
inlinestatic

the CanonicalForm G is the output of map_up, returns F considered as an element over $ F_{p}(\alpha ) $, WARNING: make sure coefficients of F are really elements of a subfield of $ F_{p}(\beta ) $ which is isomorphic to $ F_{p}(\alpha ) $

Definition at line 124 of file cf_map_ext.cc.

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}
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
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
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
int level() const
level() returns the level of CO.
void append(const T &)
CanonicalForm buf2
Definition facFqBivar.cc:76
CanonicalForm remainder(const CanonicalForm &f, const CanonicalForm &g, const modpk &pk)
Definition fac_util.cc:115

◆ mapPrimElem()

CanonicalForm mapPrimElem ( const CanonicalForm & primElem,
const Variable & alpha,
const Variable & beta )

compute the image of a primitive element of $ F_{p} (\alpha ) $ in $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $.

Parameters
[in]primElemprimitive element
[in]alphaalgebraic variable
[in]betaalgebraic variable

Definition at line 451 of file cf_map_ext.cc.

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}
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL

◆ mapUp() [1/3]

static CanonicalForm mapUp ( const CanonicalForm & F,
const CanonicalForm & G,
const Variable & alpha,
const CanonicalForm & H,
CFList & source,
CFList & dest )
inlinestatic

map F in $ F_{p} (\alpha ) $ which is generated by G into some $ F_{p}(\beta ) $ which is generated by H

Definition at line 291 of file cf_map_ext.cc.

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}
CanonicalForm H
Definition facAbsFact.cc:60

◆ mapUp() [2/3]

CanonicalForm mapUp ( const CanonicalForm & F,
const Variable & alpha,
const Variable & beta,
const CanonicalForm & prim_elem,
const CanonicalForm & im_prim_elem,
CFList & source,
CFList & dest )

map F from $ F_{p} (\alpha ) $ to $ F_{p}(\beta ) $. We assume $ F_{p} (\alpha ) \subset F_{p}(\beta ) $.

Parameters
[in]Fpoly over $ F_{p} (\alpha ) $
[in]alphaalg. variable
[in]betaalg. variable
[in]prim_elemprimitive element of $ F_{p} (\alpha ) $
[in]im_prim_elemimage of prim_elem in $ F_{p} (\beta ) $
source[in,out] look up lists
dest[in,out] look up lists

Definition at line 440 of file cf_map_ext.cc.

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}

◆ mapUp() [3/3]

static CanonicalForm mapUp ( const Variable & alpha,
const Variable & beta )
inlinestatic

$ F_{p} (\alpha ) \subset F_{p}(\beta ) $ and $ \alpha $ is a primitive element, returns the image of $ \alpha $

Definition at line 71 of file cf_map_ext.cc.

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}

◆ primitiveElement()

CanonicalForm primitiveElement ( const Variable & alpha,
Variable & beta,
bool & fail )

determine a primitive element of $ F_{p} (\alpha ) $, $ \beta $ is a primitive element of a field which is isomorphic to $ F_{p}(\alpha ) $

Parameters
[in]alphasome algebraic variable
beta[in,out] s.a.
fail[in,out] failure due to integer factorization failure?

Definition at line 343 of file cf_map_ext.cc.

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}
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
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:25
CanonicalForm mipo
Definition facAlgExt.cc:57
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition variable.cc:219