Bill Allombert on Mon, 24 Oct 2011 23:34:38 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: polisirreducible(f*Mod(1,2)) vs. factormod(f,2)


On Mon, Oct 24, 2011 at 07:32:35PM +0400, Max Alekseyev wrote:
> Why polisirreducible(f*Mod(1,2)) is not much faster (if fact, even
> slightly slower) than factormod(f,2) on average?
> Factoring is an overkill for testing irreducibility but that's
> currently not true in PARI/GP.
> 
> ? q = vector(1000,i,random(10^4));
> ? for(i=1,#q,factormod( x^q[i]+x+1,2)   )
> ? ##
>   ***   last result computed in 4min, 6,019 ms.
> ? for(i=1,#q,polisirreducible( (x^q[i]+x+1)*Mod(1,2)   ) )
> ? ##
>   ***   last result computed in 4min, 8,812 ms.

Currently, the implementation of polisirreducible simply call factor().
Probably because this avoided the duplication of the code to compute
the coefficient field (which is a rather fragile operation).

Cheers,
Bill.