[Maxima] irreducibility test
fateman at cs.berkeley.edu
Wed Apr 1 17:51:28 CDT 2009
Fabrizio Caruso wrote:
> 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.
Well, there are 2 algorithms, depending on whether you want to factor
over a large finite field or a small one,
so what to use may depend on the size of the field.
I agree that if you find it has 2 non-trivial factors you have a proof
that it is reducible, so you could stop earlier.
But I suspect that the first step will be by far the most expensive one,
and you would, in any case, be
using Berlekamp's algorithm. Since most "random" polynomials over
largish finite fields
will be irreducible, you will have done all the work to prove it is
You could look at the Cantor-Zassenhaus factoring algorithm.
> Unfortunately I am not fluent enough
> in Lisp to reuse Maxima's Lisp code.
> If someone could help...
I can suggest some tutorial material to help you learn Lisp better :)
More information about the Maxima