46 if (
i.getItem() == item)
56 if ((pos > 0) && (pos <= list.
length()))
72 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
82 fq_nmod_poly_factor_t fac;
83 fq_nmod_poly_factor_init(fac,ctx);
84 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
87 fq_nmod_init(r0, ctx);
88 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
89 fq_nmod_neg(r0, r0, ctx);
93 fq_nmod_poly_factor_clear(fac,ctx);
94 fq_nmod_clear(r0, ctx);
98 #elif defined(HAVE_NTL)
106 zz_pE::init (NTL_mipo);
108 zz_pE root= FindRoot (NTL_alpha_mipo);
135 if (
degree(F) == 0)
return F;
151 ASSERT (counter >=
bound,
"alpha is not primitive");
155 dest.
append (alpha_power);
158 alpha_power=
getItem (dest, pos);
184 if (F.
isOne())
return 1;
231 if (F.
isOne())
return F;
243 ASSERT (d%
k == 0,
"multiple of GF degree expected");
245 int ext_field_size=
ipower (
p, d);
247 int diff= (ext_field_size - 1)/(field_size - 1);
255 if (F.
isOne())
return F;
279 ASSERT (d %
k == 0,
"multiple of GF degree expected");
281 int ext_field_size=
ipower (
p, d);
283 int diff= (ext_field_size - 1)/(field_size - 1);
303 if (
degree(F) <= 0)
return F;
319 ASSERT (counter <=
bound,
"alpha is not primitive");
344 bool primitive=
false;
357 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
358 nmod_poly_t FLINT_mipo;
360 #elif defined(HAVE_NTL)
374 bool initialized=
false;
377 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
378 nmod_poly_randtest_monic_irreducible(FLINT_mipo,
FLINTrandom, d+1);
380 #elif defined(HAVE_NTL)
381 BuildIrred (NTL_mipo, d);
394 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
397 nmod_poly_t alpha_mipo;
403 fq_nmod_poly_t FLINT_beta_mipo;
405 fq_nmod_poly_factor_t fac;
406 fq_nmod_poly_factor_init(fac,ctx);
407 fq_nmod_poly_roots(fac, FLINT_beta_mipo, 0, ctx);
410 fq_nmod_init(r0, ctx);
411 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
412 fq_nmod_neg(r0, r0, ctx);
416 fq_nmod_poly_factor_clear(fac,ctx);
417 fq_nmod_clear(r0, ctx);
421 #elif defined(HAVE_NTL)
423 zz_pE::init (alpha_mipo);
424 zz_pEX NTL_beta_mipo= to_zz_pEX (NTL_mipo);
425 zz_pE root= FindRoot (NTL_beta_mipo);
435 return mapUp (F, im_prim_elem,
alpha, prim_elem, dest, source);
443 if (prim_elem ==
alpha)
444 return F (im_prim_elem,
alpha);
445 return mapUp (F, prim_elem,
alpha, im_prim_elem, source, dest);
448#if defined(HAVE_NTL) || defined(HAVE_FLINT)
453 if (primElem ==
alpha)
458 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
466 fq_nmod_poly_t mipo2;
468 fq_nmod_poly_factor_t fac;
469 fq_nmod_poly_factor_init(fac,ctx);
470 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
473 fq_nmod_init(r0, ctx);
474 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
475 fq_nmod_neg(r0, r0, ctx);
479 fq_nmod_poly_factor_clear(fac,ctx);
480 fq_nmod_clear(r0, ctx);
484 #elif defined(HAVE_NTL)
492 zz_pE::init (NTLMipo);
494 zz_pE root= FindRoot (NTLPrimElemMipo);
514 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
522 fq_nmod_poly_t mipo2;
524 fq_nmod_poly_factor_t fac;
525 fq_nmod_poly_factor_init(fac,ctx);
526 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
529 fq_nmod_t r0,FLINTbeta;
530 fq_nmod_init(r0, ctx);
531 fq_nmod_init(FLINTbeta, ctx);
534 fmpz_set_si(FLINTorder,order);
535 for(
int i=0;
i< fac->num;
i++)
538 fq_nmod_poly_get_coeff(r0,fac->poly+
i,0,ctx);
539 fq_nmod_neg(r0,r0,ctx);
541 fq_nmod_pow(r0,r0,FLINTorder,ctx);
543 if (fq_nmod_equal(r0,FLINTbeta,ctx))
549 fmpz_clear(FLINTorder);
551 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
552 fq_nmod_neg(r0,r0,ctx);
555 fq_nmod_poly_factor_clear(fac,ctx);
556 fq_nmod_clear(r0, ctx);
557 fq_nmod_clear(FLINTbeta,ctx);
561 #elif defined(HAVE_NTL)
569 zz_pE::init (NTL_mipo);
572 vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
574 for (
long i= 0;
i < roots.length();
i++)
576 if (
power (roots [
i], order)== NTLBeta)
589#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
598static void minpoly(nmod_poly_t
g,
const nmod_poly_t F,
const nmod_poly_t
h)
601 slong d = nmod_poly_degree(
h);
602 mp_limb_t
p =
h->mod.n;
604 nmod_berlekamp_massey_t bma;
607 nmod_berlekamp_massey_init(bma,
p);
610 for (
i = 0;
i < 2*d;
i++)
612 nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
613 nmod_poly_mulmod(Fpow, Fpow, F,
h);
616 nmod_berlekamp_massey_reduce(bma);
619 FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
620 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
622 nmod_poly_make_monic(
g, nmod_berlekamp_massey_V_poly(bma));
627 nmod_poly_compose_mod(z,
g, F,
h);
628 FLINT_ASSERT(nmod_poly_is_zero(z));
633 nmod_berlekamp_massey_clear(bma);
638#if defined(HAVE_NTL) || defined(HAVE_FLINT)
645 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
646 nmod_poly_t FLINT_F,FLINT_alpha,
g;
650 minpoly(
g,FLINT_F,FLINT_alpha);
656 #elif defined(HAVE_NTL)
666 zz_pE::init (NTLMipo);
668 pows.SetLength (2*d);
672 zz_pE NTLFE= to_zz_pE (NTLF);
674 for (
int i= 0;
i < 2*d;
i++)
677 buf.rep.SetLength (d);
678 pows [
i]=
buf.rep[0];
683 MinPolySeq (NTLMinPoly, pows, d);
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)
Conversion to and from NTL.
#define ASSERT(expression, message)
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...
Compute cyclotomic polynomials and factorize integers by brute force.
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
int findItem(const CFList &list, const CanonicalForm &item)
helper function
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
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
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
VAR void(* factoryError)(const char *s)
int ipower(int b, int m)
int ipower ( int b, int m )
class to iterate through CanonicalForm's
virtual class for internal CanonicalForm's
factory's class for variables
functions to print debug output
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)
INST_VAR CanonicalForm gf_mipo
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
static long imm2int(const InternalCF *const imm)
InternalCF * int2imm_gf(long i)
gmp_float exp(const gmp_float &a)
STATIC_VAR gmp_float * diff
int status int void * buf
void prune(Variable &alpha)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables