[flint-devel] Irreducibility test

[Richard Howell-P. <ric...@gm...>]

Here's some code for an irreducibility test, I'm pretty sure it works but I
don't know how I'd test it properly




/**
 * Irreducibility test for polynomials over Z/pZ
 * @param input        Arbitary polynomial
 * @returns    1 if irredicible, 0 if not
*/

int irreducible(zmod_poly_t f)
{
    //printf("input = "); zmod_poly_print(f); printf("\n");
    //see if it is non linear
    if( zmod_poly_length(f) > 2 )
    {
        unsigned long p = zmod_poly_modulus(f);
        unsigned long n = zmod_poly_degree(f);
        //Some polynomials we will need

        zmod_poly_t a,x,x_p,one,x_modf;
        zmod_poly_init(a, p);
        zmod_poly_init(x, p);
        zmod_poly_init(x_p, p);
        zmod_poly_init(one, p);
        zmod_poly_init(x_modf, p);
        //Set up the constant polynomials
        zmod_poly_set_coeff_ui(x, 1, 1);
        zmod_poly_set_coeff_ui(one, 0, 1);
        //compute x^q mod f
        zmod_poly_powmod(x_p, x,  p, f);
        //compute x_q^n mod f
        zmod_poly_powmod(a, x_p, n, f);
        //now reduce x mod f and do the comparison, it is VITAL the
comparison is done mod f
        zmod_poly_mulmod(x_modf, x, one, f);
        //now do the irreducibility test
        if( !zmod_poly_equal(a, x_modf) )
            return 0;
        else
        {
            factor_t* factors;
            z_factor(factors, n);
            for(unsigned long i = 0; i < factors->num; ++i)
            {
                zmod_poly_powmod( a, x_p,  n / factors->p[i], f);
                zmod_poly_sub( a, a, x);
                zmod_poly_gcd( a, a, f);
                if( !zmod_poly_is_one(a))
                    return 0;
            }


        }

        zmod_poly_clear(a);
        zmod_poly_clear(x);
        zmod_poly_clear(x_p);
        zmod_poly_clear(one);
        zmod_poly_clear(x_modf);
    }
    return 1;
}



-- 
Richard