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

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2011-10-24 23:34]
>* Max Alekseyev [2011-10-24 17:32]:
>> 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).

I just changed this, since that code in now abstracted in RgX_type()...

There are still a few cases where polisirreducible() still calls factor() 
although it doesn't need to [ non prime finite fields in particular ],
but the situation has improved somewhat:

  ? q = vector(1000,i,random(10^4));
  ? for(i=1,#q,factormod(x^q[i]+x+1,2))
  time = 1min, 148 ms.
  ? for(i=1,#q,polisirreducible( (x^q[i]+x+1)*Mod(1,2)   ) )
  time = 5,204 ms.

N.B. The factormod() part has been improved as well. In pari.stable:
  ? for(i=1,#q,factormod( x^q[i]+x+1,2))
  time = 3min, 13,572 ms.

The timings are still unimpressive: they could be improved by implementing
better algorithms, in particular iterated Frobenius (= Shoup-von zur Gathen)

Cheers,

    K.B.
-- 
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`