|
From: Richard Howell-P. <ric...@gm...> - 2008-08-08 08:26:06
|
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
|