Function minpoly

factory/cf_map_ext.cc:599–635

g is in Fp[x] F is in Fp[t] h is in Fp[t] In the finite field Fp[t]/h(t), find g(x) in Fp[x] such that g(F(t)) = 0 mod h(t) i.e. g is the minpoly of the element F(t) of the finite field. */

    i.e. g is the minpoly of the element F(t) of the finite field.
*/
static void minpoly(nmod_poly_t g, const nmod_poly_t F, const nmod_poly_t h)
{
    slong i;
    slong d = nmod_poly_degree(h);
    mp_limb_t p = h->mod.n;
    nmod_poly_t Fpow;
    nmod_berlekamp_massey_t bma;

    nmod_poly_init(Fpow, p);
    nmod_berlekamp_massey_init(bma, p);

    nmod_poly_one(Fpow);
    for (i = 0; i < 2*d; i++)
    {
        nmod_berlekamp_massey_add_point(bma, nmod_poly_get_coeff_ui(Fpow, 0));
        nmod_poly_mulmod(Fpow, Fpow, F, h);
    }

    nmod_berlekamp_massey_reduce(bma);

    /* something went horribly wrong if V does not kill the whole sequence */
    FLINT_ASSERT(nmod_poly_degree(nmod_berlekamp_massey_R_poly(bma)) <
                 nmod_poly_degree(nmod_berlekamp_massey_V_poly(bma)));

    nmod_poly_make_monic(g, nmod_berlekamp_massey_V_poly(bma));
#if WANT_ASSERT
    {
        nmod_poly_t z;
        nmod_poly_init(z, p);
        nmod_poly_compose_mod(z, g, F, h);
        FLINT_ASSERT(nmod_poly_is_zero(z));
        nmod_poly_clear(z);
    }
#endif
    nmod_poly_clear(Fpow);
    nmod_berlekamp_massey_clear(bma);
}
#endif