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)
| and is a primitive element, returns the image of
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 , WARNING: make sure coefficients of F are really elements of a subfield of which is isomorphic to
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 to a polynomial over , 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 to a polynomial over , 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 which is generated by G into some which is generated by H
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 | mapDown (const CanonicalForm &F, const CanonicalForm &prim_elem, const CanonicalForm &im_prim_elem, const Variable &alpha, CFList &source, CFList &dest)
| map F from to . We assume and F in .
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 to . We assume .
CanonicalForm | mapPrimElem (const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
| compute the image of a primitive element of in . We assume .
CanonicalForm | map (const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
| map from to such that is mapped onto
CanonicalForm | findMinPoly (const CanonicalForm &F, const Variable &alpha)
| compute minimal polynomial of 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] | F | some poly over F_p(alpha) where alpha is a root of a Conway poly

Definition at line 204 of file cf_map_ext.cc.

{
CanonicalForm result= 0;
InternalCF* buf;
if (F.inCoeffDomain())
{
if (F.inBaseDomain())
return F.mapinto();
else
{
for (CFIterator i= F; i.hasTerms(); i++)
{
buf= int2imm_gf (i.exp());
result += i.coeff().mapinto()*CanonicalForm (buf);
}
}
return result;
}
for (CFIterator i= F; i.hasTerms(); i++)
result += Falpha2GFRep (i.coeff())*power (F.mvar(), i.exp());
return result;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
i
int i
Definition cfEzgcd.cc:132
Falpha2GFRep
CanonicalForm Falpha2GFRep(const CanonicalForm &F)
change representation by residue classes modulo a Conway polynomial to representation by primitive el...
Definition cf_map_ext.cc:204
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition canonicalform.cc:104
CanonicalForm::mapinto
CanonicalForm mapinto() const
Definition canonicalform.cc:210
InternalCF
virtual class for internal CanonicalForm's
Definition int_cf.h:47
result
return result
Definition facAbsBiFact.cc:76
int2imm_gf
InternalCF * int2imm_gf(long i)
Definition imm.h:106
buf
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.

{
int result= 1;
for (CFListIterator i= list; i.hasItem(); i++, result++)
{
if (i.getItem() == item)
return result;
}
return 0;
}
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396

## findMinPoly()

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

compute minimal polynomial of via NTL

Returns
  findMinPoly computes the minimal polynomial of F

Parameters

  [in] | F | an element of
  [in] | alpha | algebraic variable

Definition at line 641 of file cf_map_ext.cc.

{
ASSERT (F.isUnivariate() && F.mvar()==alpha,"expected element of F_p(alpha)");
int p=getCharacteristic();
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
nmod_poly_t FLINT_F,FLINT_alpha,g;
nmod_poly_init(g,p);
convertFacCF2nmod_poly_t(FLINT_F,F);
convertFacCF2nmod_poly_t(FLINT_alpha,getMipo(alpha));
minpoly(g,FLINT_F,FLINT_alpha);
nmod_poly_clear(FLINT_alpha);
nmod_poly_clear(FLINT_F);
CanonicalForm res=convertnmod_poly_t2FacCF(g,Variable(1));
nmod_poly_clear(g);
return res;
#elif defined(HAVE_NTL)
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTLF= convertFacCF2NTLzzpX (F);
int d= degree (getMipo (alpha));
zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo(alpha));
zz_pE::init (NTLMipo);
vec_zz_p pows;
pows.SetLength (2*d);
zz_pE powNTLF;
set (powNTLF);
zz_pE NTLFE= to_zz_pE (NTLF);
zz_pX buf;
for (int i= 0; i < 2*d; i++)
{
buf= rep (powNTLF);
buf.rep.SetLength (d);
pows [i]= buf.rep[0];
powNTLF *= NTLFE;
}
zz_pX NTLMinPoly;
MinPolySeq (NTLMinPoly, pows, d);
return convertNTLzzpX2CF (NTLMinPoly, Variable (1));
#else
factoryError("NTL/FLINT missing: findMinPoly");
#endif
}
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition FLINTconvert.cc:208
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
res
CanonicalForm res
Definition facAbsFact.cc:60
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
getMipo
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.

{
int j= 1;
if ((pos > 0) && (pos <= list.length()))
{
for (CFListIterator i= list; j <= pos; i++, j++)
{
if (j == pos)
return i.getItem();
}
}
return 0;
}
List::length
int length() const
Definition ftmpl_list.cc:273
j
int j
Definition facHensel.cc:110

## GF2FalphaHelper()

CanonicalForm GF2FalphaHelper | ( | const CanonicalForm & | F,
|  | const Variable & | alpha )

inline static

helper function

Definition at line 176 of file cf_map_ext.cc.

{
if (F.isZero())
return 0;
int exp;
CanonicalForm result= 0;
InternalCF* buf;
if (F.inBaseDomain())
{
if (F.isOne()) return 1;
buf= F.getval();
exp= imm2int(buf);
result= power (alpha, exp).mapinto();
return result;
}
for (CFIterator i= F; i.hasTerms(); i++)
result += GF2FalphaHelper (i.coeff(), alpha)*power (F.mvar(), i.exp());
return result;
}
GF2FalphaHelper
static CanonicalForm GF2FalphaHelper(const CanonicalForm &F, const Variable &alpha)
helper function
Definition cf_map_ext.cc:176
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::getval
InternalCF * getval() const
Definition canonicalform.cc:34
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
imm2int
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349

## 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] | F | some poly over GF
  [in] | alpha | root of a Conway poly

Definition at line 196 of file cf_map_ext.cc.

{
Variable beta= rootOf (gf_mipo);
CanonicalForm result= GF2FalphaHelper (F, beta) (alpha, beta);
prune (beta);
return result;
}
beta
Variable beta
Definition facAbsFact.cc:95
rootOf
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
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
gf_mipo
INST_VAR CanonicalForm gf_mipo
Definition gfops.cc:56

## GFMapDown()

CanonicalForm GFMapDown | ( | const CanonicalForm & | F,
|  | int | k )

maps a polynomial over to a polynomial over , d needs to be a multiple of k

Definition at line 277 of file cf_map_ext.cc.

{
int d= getGFDegree();
ASSERT (d % k == 0, "multiple of GF degree expected");
int p= getCharacteristic();
int ext_field_size= ipower (p, d);
int field_size= ipower ( p, k);
int diff= (ext_field_size - 1)/(field_size - 1);
return GFPowDown (F, diff);
}
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
k
int k
Definition cfEzgcd.cc:99
GFPowDown
static CanonicalForm GFPowDown(const CanonicalForm &F, int k)
GFMapDown helper.
Definition cf_map_ext.cc:254
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
diff
STATIC_VAR gmp_float * diff
Definition mpr_complex.cc:45

## GFMapUp()

CanonicalForm GFMapUp | ( | const CanonicalForm & | F,
|  | int | k )

maps a polynomial over to a polynomial over , d needs to be a multiple of k

Definition at line 241 of file cf_map_ext.cc.

{
int d= getGFDegree();
ASSERT (d%k == 0, "multiple of GF degree expected");
int p= getCharacteristic();
int ext_field_size= ipower (p, d);
int field_size= ipower ( p, k);
int diff= (ext_field_size - 1)/(field_size - 1);
return GFPowUp (F, diff);
}
GFPowUp
static CanonicalForm GFPowUp(const CanonicalForm &F, int k)
GF_map_up helper.
Definition cf_map_ext.cc:230

## GFPowDown()

CanonicalForm GFPowDown | ( | const CanonicalForm & | F,
|  | int | k )

inline static

GFMapDown helper.

Definition at line 254 of file cf_map_ext.cc.

{
if (F.isOne()) return F;
CanonicalForm result= 0;
int exp;
InternalCF* buf;
if (F.inBaseDomain())
{
buf= F.getval();
exp= imm2int (buf);
if ((exp % k) == 0)
exp= exp/k;
else
return -1;
buf= int2imm_gf (exp);
return CanonicalForm (buf);
}
for (CFIterator i= F; i.hasTerms(); i++)
result += GFPowDown (i.coeff(), k)*power (F.mvar(), i.exp());
return result;
}

## GFPowUp()

CanonicalForm GFPowUp | ( | const CanonicalForm & | F,
|  | int | k )

inline static

GF_map_up helper.

Definition at line 230 of file cf_map_ext.cc.

{
if (F.isOne()) return F;
CanonicalForm result= 0;
if (F.inBaseDomain())
return power(F, k);
for (CFIterator i= F; i.hasTerms(); i++)
result += GFPowUp (i.coeff(), k)*power (F.mvar(), i.exp());
return result;
}

## map()

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

map from to such that is mapped onto

Returns
  map returns the image of primElem such that the above described properties hold

Parameters

  [in] | primElem | primitive element of
  [in] | alpha | algebraic variable
  [in] | F | an element of , whose minimal polynomial defines a field extension of of degree
  [in] | beta | algebraic variable, root of F's minimal polynomial

Definition at line 505 of file cf_map_ext.cc.

{
CanonicalForm G= F;
int order= 0;
while (!G.isOne())
{
G /= primElem;
order++;
}
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
// convert mipo
nmod_poly_t mipo1;
convertFacCF2nmod_poly_t(mipo1,getMipo(beta));
fq_nmod_ctx_t ctx;
fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
nmod_poly_clear(mipo1);
// convert mipo2 (alpha)
fq_nmod_poly_t mipo2;
convertFacCF2Fq_nmod_poly_t(mipo2,getMipo(alpha),ctx);
fq_nmod_poly_factor_t fac;
fq_nmod_poly_factor_init(fac,ctx);
fq_nmod_poly_roots(fac, mipo2, 0, ctx);
// roots in fac, #=fac->num
int ind=-1;
fq_nmod_t r0,FLINTbeta;
fq_nmod_init(r0, ctx);
fq_nmod_init(FLINTbeta, ctx);
convertFacCF2Fq_nmod_t(FLINTbeta,beta,ctx);
fmpz_t FLINTorder;
fmpz_set_si(FLINTorder,order);
for(int i=0;i< fac->num;i++)
{
// get the root (-abs.term of linear factor)
fq_nmod_poly_get_coeff(r0,fac->poly+i,0,ctx);
fq_nmod_neg(r0,r0,ctx);
// r^order
fq_nmod_pow(r0,r0,FLINTorder,ctx);
// ==beta?
if (fq_nmod_equal(r0,FLINTbeta,ctx))
{
ind=i;
break;
}
}
fmpz_clear(FLINTorder);
// convert
fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
fq_nmod_neg(r0,r0,ctx);
CanonicalForm r1=convertFq_nmod_t2FacCF(r0,beta,ctx);
// cleanup
fq_nmod_poly_factor_clear(fac,ctx);
fq_nmod_clear(r0, ctx);
fq_nmod_clear(FLINTbeta,ctx);
fq_nmod_poly_clear(mipo2,ctx);
fq_nmod_ctx_clear(ctx);
return r1;
#elif defined(HAVE_NTL)
int p= getCharacteristic ();
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
zz_pE::init (NTL_mipo);
zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
zz_pE NTLBeta= to_zz_pE (convertFacCF2NTLzzpX (beta));
vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
long ind=-1;
for (long i= 0; i < roots.length(); i++)
{
if (power (roots [i], order)== NTLBeta)
{
ind= i;
break;
}
}
return (convertNTLzzpE2CF (roots[ind], beta));
#else
factoryError("NTL/FLINT missing: map");
return CanonicalForm(0);
#endif
}
convertFacCF2Fq_nmod_t
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...
Definition FLINTconvert.cc:442
convertFacCF2Fq_nmod_poly_t
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
Definition FLINTconvert.cc:526
convertFq_nmod_t2FacCF
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
Definition FLINTconvert.cc:479
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition NTLconvert.cc:1064
convertNTLzzpE2CF
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
Definition NTLconvert.cc:799
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)
G
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 to . We assume and F in .

Parameters

  [in] | F | poly over
  [in] | prim_elem | primitive element of
  [in] | im_prim_elem | image of prim_elem in
  [in] | alpha | alg. variable
  [in,out] | source | look up lists
  [in,out] | dest | look up lists

Definition at line 432 of file cf_map_ext.cc.

{
return mapUp (F, im_prim_elem, alpha, prim_elem, dest, source);
}
mapUp
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]

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

inline static

the CanonicalForm G is the output of map_up, returns F considered as an element over , WARNING: make sure coefficients of F are really elements of a subfield of which is isomorphic to

Definition at line 124 of file cf_map_ext.cc.

{
CanonicalForm buf, buf2;
int counter= 0;
int pos;
int p= getCharacteristic();
int d= degree(getMipo(alpha));
int bound= ipower(p, d);
CanonicalForm result= 0;
CanonicalForm remainder;
CanonicalForm alpha_power;
if (degree(F) == 0) return F;
if (F.level() < 0 && F.isUnivariate())
{
buf= F;
remainder= mod (buf, G);
ASSERT (remainder.isZero(), "alpha is not primitive");
pos= findItem (source, buf);
if (pos == 0)
source.append (buf);
buf2= buf;
while (degree (buf) != 0 && counter < bound)
{
buf /= G;
counter++;
if (buf == buf2) break;
}
ASSERT (counter >= bound, "alpha is not primitive");
if (pos == 0)
{
alpha_power= power (alpha, counter);
dest.append (alpha_power);
}
else
alpha_power= getItem (dest, pos);
result = alpha_power;
return result;
}
else
{
for (CFIterator i= F; i.hasTerms(); i++)
{
buf= mapDown (i.coeff(), alpha, G, source, dest);
result += buf*power(F.mvar(), i.exp());
}
return result;
}
}
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
mapDown
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:124
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc:54
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
List::append
void append(const T &)
Definition ftmpl_list.cc:256
buf2
CanonicalForm buf2
Definition facFqBivar.cc:76
remainder
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 in . We assume .

Parameters

  [in] | primElem | primitive element
  [in] | alpha | algebraic variable
  [in] | beta | algebraic variable

Definition at line 451 of file cf_map_ext.cc.

{
if (primElem == alpha)
return mapUp (alpha, beta);
else
{
CanonicalForm primElemMipo= findMinPoly (primElem, alpha);
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
// convert mipo1
nmod_poly_t mipo1;
convertFacCF2nmod_poly_t(mipo1,getMipo(beta));
fq_nmod_ctx_t ctx;
fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
nmod_poly_clear(mipo1);
// convert mipo2 (primElemMipo)
fq_nmod_poly_t mipo2;
convertFacCF2Fq_nmod_poly_t(mipo2,primElemMipo,ctx);
fq_nmod_poly_factor_t fac;
fq_nmod_poly_factor_init(fac,ctx);
fq_nmod_poly_roots(fac, mipo2, 0, ctx);
// root of first (linear) factor: -absolute Term
fq_nmod_t r0;
fq_nmod_init(r0, ctx);
fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
fq_nmod_neg(r0, r0, ctx);
// convert
CanonicalForm r1=convertFq_nmod_t2FacCF(r0,beta,ctx);
// cleanup
fq_nmod_poly_factor_clear(fac,ctx);
fq_nmod_clear(r0, ctx);
fq_nmod_poly_clear(mipo2,ctx);
fq_nmod_ctx_clear(ctx);
return r1;
#elif defined(HAVE_NTL)
int p= getCharacteristic ();
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (beta));
zz_pE::init (NTLMipo);
zz_pEX NTLPrimElemMipo= convertFacCF2NTLzz_pEX (primElemMipo, NTLMipo);
zz_pE root= FindRoot (NTLPrimElemMipo);
return convertNTLzzpE2CF (root, beta);
#else
factoryError("NTL/FLINT missing: mapPrimElem");
#endif
}
}
findMinPoly
CanonicalForm findMinPoly(const CanonicalForm &F, const Variable &alpha)
compute minimal polynomial of via NTL
Definition cf_map_ext.cc:641

## mapUp() [1/3]

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

inline static

map F in which is generated by G into some which is generated by H

Definition at line 291 of file cf_map_ext.cc.

{
CanonicalForm buf, buf2;
int counter= 0;
int pos;
int p= getCharacteristic();
int d= degree (getMipo(alpha));
int bound= ipower(p, d);
CanonicalForm result= 0;
CanonicalForm remainder;
CanonicalForm H_power;
if (degree(F) <= 0) return F;
if (F.level() < 0 && F.isUnivariate())
{
buf= F;
remainder= mod (buf, G);
ASSERT (remainder.isZero(), "alpha is not primitive");
pos= findItem (source, buf);
if (pos == 0)
source.append (buf);
buf2= buf;
while (degree (buf) != 0 && counter < bound)
{
buf /= G;
counter++;
if (buf == buf2) break;
}
ASSERT (counter <= bound, "alpha is not primitive");
if (pos == 0)
{
H_power= buf*power (H, counter);
dest.append (H_power);
}
else
H_power= getItem (dest, pos);
result = H_power;
return result;
}
else
{
for (CFIterator i= F; i.hasTerms(); i++)
{
buf= mapUp (i.coeff(), G, alpha, H, source, dest);
result += buf*power(F.mvar(), i.exp());
}
return result;
}
}
H
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 to . We assume .

Parameters

  [in] | F | poly over
  [in] | alpha | alg. variable
  [in] | beta | alg. variable
  [in] | prim_elem | primitive element of
  [in] | im_prim_elem | image of prim_elem in
  [in,out] | source | look up lists
  [in,out] | dest | look up lists

Definition at line 440 of file cf_map_ext.cc.

{
if (prim_elem == alpha)
return F (im_prim_elem, alpha);
return mapUp (F, prim_elem, alpha, im_prim_elem, source, dest);
}

## mapUp() [3/3]

CanonicalForm mapUp | ( | const Variable & | alpha,
|  | const Variable & | beta )

inline static

and is a primitive element, returns the image of

Definition at line 71 of file cf_map_ext.cc.

{
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
// convert mipo1
nmod_poly_t mipo1;
convertFacCF2nmod_poly_t(mipo1,getMipo(beta));
fq_nmod_ctx_t ctx;
fq_nmod_ctx_init_modulus(ctx,mipo1,"t");
nmod_poly_clear(mipo1);
// convert mipo2 (alpah)
fq_nmod_poly_t mipo2;
convertFacCF2Fq_nmod_poly_t(mipo2,getMipo(alpha),ctx);
fq_nmod_poly_factor_t fac;
fq_nmod_poly_factor_init(fac,ctx);
fq_nmod_poly_roots(fac, mipo2, 0, ctx);
// root of first (linear) factor: -absolute Term
fq_nmod_t r0;
fq_nmod_init(r0, ctx);
fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
fq_nmod_neg(r0, r0, ctx);
// convert
CanonicalForm r1=convertFq_nmod_t2FacCF(r0,beta,ctx);
// cleanup
fq_nmod_poly_factor_clear(fac,ctx);
fq_nmod_clear(r0, ctx);
fq_nmod_poly_clear(mipo2,ctx);
fq_nmod_ctx_clear(ctx);
return r1;
#elif defined(HAVE_NTL)
int p= getCharacteristic ();
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTL_mipo= convertFacCF2NTLzzpX (getMipo (beta));
zz_pE::init (NTL_mipo);
zz_pEX NTL_alpha_mipo= convertFacCF2NTLzz_pEX (getMipo(alpha), NTL_mipo);
zz_pE root= FindRoot (NTL_alpha_mipo);
return convertNTLzzpE2CF (root, beta);
#else
factoryError("NTL/FLINT missing: mapUp");
return CanonicalForm(0); // to avoid warnings
#endif
}

## primitiveElement()

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

Parameters

  [in] | alpha | some algebraic variable
  [in,out] | beta | s.a.
  [in,out] | fail | failure due to integer factorization failure?

Definition at line 343 of file cf_map_ext.cc.

{
bool primitive= false;
fail= false;
primitive= isPrimitive (alpha, fail);
if (fail)
return 0;
if (primitive)
{
beta= alpha;
return alpha;
}
CanonicalForm mipo= getMipo (alpha);
int d= degree (mipo);
int p= getCharacteristic ();
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
nmod_poly_t FLINT_mipo;
nmod_poly_init(FLINT_mipo,p);
#elif defined(HAVE_NTL)
if (fac_NTL_char != p)
{
fac_NTL_char= p;
zz_p::init (p);
}
zz_pX NTL_mipo;
#else
factoryError("NTL/FLINT missing: primitiveElement");
return CanonicalForm(0);
#endif
CanonicalForm mipo2;
primitive= false;
fail= false;
bool initialized= false;
do
{
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
nmod_poly_randtest_monic_irreducible(FLINT_mipo, FLINTrandom, d+1);
mipo2=convertnmod_poly_t2FacCF(FLINT_mipo,Variable(1));
#elif defined(HAVE_NTL)
BuildIrred (NTL_mipo, d);
mipo2= convertNTLzzpX2CF (NTL_mipo, Variable (1));
#endif
if (!initialized)
beta= rootOf (mipo2);
else
setMipo (beta, mipo2);
primitive= isPrimitive (beta, fail);
if (primitive)
break;
if (fail)
return 0;
} while (1);
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
nmod_poly_clear(FLINT_mipo);
// convert alpha_mipo
nmod_poly_t alpha_mipo;
convertFacCF2nmod_poly_t(alpha_mipo,mipo);
fq_nmod_ctx_t ctx;
fq_nmod_ctx_init_modulus(ctx,alpha_mipo,"t");
nmod_poly_clear(alpha_mipo);
// convert beta_mipo (mipo2)
fq_nmod_poly_t FLINT_beta_mipo;
convertFacCF2Fq_nmod_poly_t(FLINT_beta_mipo,mipo2,ctx);
fq_nmod_poly_factor_t fac;
fq_nmod_poly_factor_init(fac,ctx);
fq_nmod_poly_roots(fac, FLINT_beta_mipo, 0, ctx);
// root of first (linear) factor: -absolute Term
fq_nmod_t r0;
fq_nmod_init(r0, ctx);
fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
fq_nmod_neg(r0, r0, ctx);
// convert
CanonicalForm r1=convertFq_nmod_t2FacCF(r0,alpha,ctx);
// cleanup
fq_nmod_poly_factor_clear(fac,ctx);
fq_nmod_clear(r0, ctx);
fq_nmod_poly_clear(FLINT_beta_mipo,ctx);
fq_nmod_ctx_clear(ctx);
return r1;
#elif defined(HAVE_NTL)
zz_pX alpha_mipo= convertFacCF2NTLzzpX (mipo);
zz_pE::init (alpha_mipo);
zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
zz_pE root= FindRoot (NTL_beta_mipo);
return convertNTLzzpE2CF (root, alpha);
#endif
}
isPrimitive
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
FLINTrandom
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:23
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
setMipo
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition variable.cc:219