Well, one can do better
than fully factoring into
irreducible factors to tell whether a
polynomial is irreducible.
Berlekamp's algorithm recursively tries
to factor a polynomial.
In order to tell whether a polynomial
is irreducible over a finite field,
one only needs to run one
factorization step of Berlekamp's algorithm.
This should in general be
much faster than what "factor" does.
Unfortunately I am not fluent enough
in Lisp to reuse Maxima's Lisp code.
If someone could help...
I need this in my next update of the
GF package for finite fields.
Fabrizio
On Wed, 1 Apr 2009, Richard Fateman wrote:
> Fabrizio Caruso wrote:
>> Hi
>>
>> Is there a function that tests whether
>> a polynomial is irreducible?
>>
>
>> In particular I am interested
>> in polynomials over a finite field
>> with prime number of elements.
>>
> There is no test that will ALWAYS work, short of factoring.
>
>> I would like to avoid having to
>> use "factor" and count the factors
>> nor reimplement Berlekamp's algorithm.
>>
>>
> Why would you reimplement this? Use the code in Maxima.
>
>
>