My Project
Loading...
Searching...
No Matches
Functions
cf_map_ext.h File Reference

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

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
 
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
 
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
 
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 ) $.
 
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 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 mapPrimElem (const CanonicalForm &prim_elem, 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 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
 
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.h.

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:59

◆ 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}

◆ 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)
651 minpoly(g,FLINT_F,FLINT_alpha);
656 return res;
657 #elif defined(HAVE_NTL)
658 if (fac_NTL_char != p)
659 {
661 zz_p::init (p);
662 }
664 int d= degree (getMipo (alpha));
665
667 zz_pE::init (NTLMipo);
669 pows.SetLength (2*d);
670
672 set (powNTLF);
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
685
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

◆ 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}
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
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.

◆ 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
522 // convert mipo2 (alpha)
527 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
528 // roots in fac, #=fac->num
529 int ind=-1;
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);
541 // r^order
543 // ==beta?
545 {
546 ind=i;
547 break;
548 }
549 }
551 // convert
552 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
555 // cleanup
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 }
570 zz_pE::init (NTL_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()

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
[in,out]sourcelook up lists
[in,out]destlook 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

◆ mapPrimElem()

CanonicalForm mapPrimElem ( const CanonicalForm prim_elem,
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]prim_elemprimitive 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 {
459 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
460 // convert mipo1
466 // convert mipo2 (primElemMipo)
471 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
472 // root of first (linear) factor: -absolute Term
475 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
476 fq_nmod_neg(r0, r0, ctx);
477 // convert
479 // cleanup
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 }
493 zz_pE::init (NTLMipo);
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()

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 ) $
[in,out]sourcelook up lists
[in,out]destlook 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}

◆ 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
[in,out]betas.a.
[in,out]failfailure due to integer factorization failure?

Definition at line 343 of file cf_map_ext.cc.

344{
345 bool primitive= false;
346 fail= false;
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)
361 #elif defined(HAVE_NTL)
362 if (fac_NTL_char != p)
363 {
365 zz_p::init (p);
366 }
368 #else
369 factoryError("NTL/FLINT missing: primitiveElement");
370 return CanonicalForm(0);
371 #endif
373 primitive= false;
374 fail= false;
375 bool initialized= false;
376 do
377 {
378 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
381 #elif defined(HAVE_NTL)
382 BuildIrred (NTL_mipo, d);
384 #endif
385 if (!initialized)
386 beta= rootOf (mipo2);
387 else
388 setMipo (beta, mipo2);
390 if (primitive)
391 break;
392 if (fail)
393 return 0;
394 } while (1);
395 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
397 // convert alpha_mipo
403 // convert beta_mipo (mipo2)
409 // root of first (linear) factor: -absolute Term
412 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
413 fq_nmod_neg(r0, r0, ctx);
414 // convert
416 // cleanup
421 return r1;
422 #elif defined(HAVE_NTL)
424 zz_pE::init (alpha_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