33#include <flint/fq_nmod_poly_factor.h>
47 if (
i.getItem() == item)
57 if ((pos > 0) && (pos <= list.
length()))
73 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
83 fq_nmod_poly_factor_t fac;
84 fq_nmod_poly_factor_init(fac,ctx);
85 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
88 fq_nmod_init(r0, ctx);
89 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
90 fq_nmod_neg(r0, r0, ctx);
94 fq_nmod_poly_factor_clear(fac,ctx);
95 fq_nmod_clear(r0, ctx);
99 #elif defined(HAVE_NTL)
107 zz_pE::init (NTL_mipo);
109 zz_pE root= FindRoot (NTL_alpha_mipo);
136 if (
degree(F) == 0)
return F;
152 ASSERT (counter >=
bound,
"alpha is not primitive");
156 dest.
append (alpha_power);
159 alpha_power=
getItem (dest, pos);
185 if (F.
isOne())
return 1;
232 if (F.
isOne())
return F;
244 ASSERT (d%
k == 0,
"multiple of GF degree expected");
246 int ext_field_size=
ipower (
p, d);
248 int diff= (ext_field_size - 1)/(field_size - 1);
256 if (F.
isOne())
return F;
280 ASSERT (d %
k == 0,
"multiple of GF degree expected");
282 int ext_field_size=
ipower (
p, d);
284 int diff= (ext_field_size - 1)/(field_size - 1);
304 if (
degree(F) <= 0)
return F;
320 ASSERT (counter <=
bound,
"alpha is not primitive");
345 bool primitive=
false;
358 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
359 nmod_poly_t FLINT_mipo;
361 #elif defined(HAVE_NTL)
375 bool initialized=
false;
378 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
379 nmod_poly_randtest_monic_irreducible(FLINT_mipo,
FLINTrandom, d+1);
381 #elif defined(HAVE_NTL)
382 BuildIrred (NTL_mipo, d);
395 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
398 nmod_poly_t alpha_mipo;
404 fq_nmod_poly_t FLINT_beta_mipo;
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);
411 fq_nmod_init(r0, ctx);
412 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
413 fq_nmod_neg(r0, r0, ctx);
417 fq_nmod_poly_factor_clear(fac,ctx);
418 fq_nmod_clear(r0, ctx);
422 #elif defined(HAVE_NTL)
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);
436 return mapUp (F, im_prim_elem,
alpha, prim_elem, dest, source);
444 if (prim_elem ==
alpha)
445 return F (im_prim_elem,
alpha);
446 return mapUp (F, prim_elem,
alpha, im_prim_elem, source, dest);
449#if defined(HAVE_NTL) || defined(HAVE_FLINT)
454 if (primElem ==
alpha)
459 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
467 fq_nmod_poly_t mipo2;
469 fq_nmod_poly_factor_t fac;
470 fq_nmod_poly_factor_init(fac,ctx);
471 fq_nmod_poly_roots(fac, mipo2, 0, ctx);
474 fq_nmod_init(r0, ctx);
475 fq_nmod_poly_get_coeff(r0,fac->poly,0,ctx);
476 fq_nmod_neg(r0, r0, ctx);
480 fq_nmod_poly_factor_clear(fac,ctx);
481 fq_nmod_clear(r0, ctx);
485 #elif defined(HAVE_NTL)
493 zz_pE::init (NTLMipo);
495 zz_pE root= FindRoot (NTLPrimElemMipo);
515 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
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);
530 fq_nmod_t r0,FLINTbeta;
531 fq_nmod_init(r0, ctx);
532 fq_nmod_init(FLINTbeta, ctx);
535 fmpz_set_si(FLINTorder,order);
536 for(
int i=0;
i< fac->num;
i++)
539 fq_nmod_poly_get_coeff(r0,fac->poly+
i,0,ctx);
540 fq_nmod_neg(r0,r0,ctx);
542 fq_nmod_pow(r0,r0,FLINTorder,ctx);
544 if (fq_nmod_equal(r0,FLINTbeta,ctx))
550 fmpz_clear(FLINTorder);
552 fq_nmod_poly_get_coeff(r0,fac->poly+ind,0,ctx);
553 fq_nmod_neg(r0,r0,ctx);
556 fq_nmod_poly_factor_clear(fac,ctx);
557 fq_nmod_clear(r0, ctx);
558 fq_nmod_clear(FLINTbeta,ctx);
562 #elif defined(HAVE_NTL)
570 zz_pE::init (NTL_mipo);
573 vec_zz_pE roots= FindRoots (NTL_alpha_mipo);
575 for (
long i= 0;
i < roots.length();
i++)
577 if (
power (roots [
i], order)== NTLBeta)
590#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
599static void minpoly(nmod_poly_t
g,
const nmod_poly_t F,
const nmod_poly_t
h)
602 slong d = nmod_poly_degree(
h);
603 mp_limb_t
p =
h->mod.n;
605 nmod_berlekamp_massey_t bma;
608 nmod_berlekamp_massey_init(bma,
p);
611 for (
i = 0;
i < 2*d;
i++)
613 nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
614 nmod_poly_mulmod(Fpow, Fpow, F,
h);
617 nmod_berlekamp_massey_reduce(bma);
620 FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
621 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));
623 nmod_poly_make_monic(
g, nmod_berlekamp_massey_V_poly(bma));
628 nmod_poly_compose_mod(z,
g, F,
h);
629 FLINT_ASSERT(nmod_poly_is_zero(z));
634 nmod_berlekamp_massey_clear(bma);
639#if defined(HAVE_NTL) || defined(HAVE_FLINT)
646 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20503)
647 nmod_poly_t FLINT_F,FLINT_alpha,
g;
651 minpoly(
g,FLINT_F,FLINT_alpha);
657 #elif defined(HAVE_NTL)
667 zz_pE::init (NTLMipo);
669 pows.SetLength (2*d);
673 zz_pE NTLFE= to_zz_pE (NTLF);
675 for (
int i= 0;
i < 2*d;
i++)
678 buf.rep.SetLength (d);
679 pows [
i]=
buf.rep[0];
684 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)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
void FACTORY_PUBLIC prune(Variable &alpha)
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
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