I hope I copy this right. (Thm. 6.6.1 from Abstract Algebra by Beachy and Blair, summarized):
The monic irreducible factors of x**((p**n)**m) - x in GF(p**n)[x] are precisely the monic irreducible polynomials in GF(p)[x] whose degree is a divisor of m, where . In other words, f(x) is irreducible iff gcd(f, x**p**((p**n)**m) - x) != 1 (mod p) Note that when you have n == 1, then it is just x**p - x. I can summarize the proof from the text if you are interested. Aaron Meurer On Feb 7, 2010, at 3:51 PM, Kasun Samarasinghe wrote: > Hi, > > Could you please explain the basis for the implemented irreducibility test. > Is it > > polynomial overr GF(p) is reducible if gcd(f, x^p - x (mod p)) = 1? > > Regards, > Kasun > > On Wed, Feb 3, 2010 at 3:56 PM, Mateusz Paprocki <[email protected]> wrote: > Hi, > > On Wed, Feb 03, 2010 at 02:06:10AM +0100, Kasun Samarasinghe wrote: > > Hi all, > > > > When I examining the galoisplynomail source code I found that irreducibility > > test is not implemented. Is there any special reason? > > basically irreducibility can be tested via factorization and usually you > need those factors in your work anyway, so there was no need to implement > any kind of irreducibility testing (mostly because the main objective for > galoispolys.py is to serve as basis for factorization algorithms over > integers). > > However, for some time I see increasing interest in finite fields in SymPy > so in the new version of polynomials manipulation module (as mentioned by > Vinzent) all this low-level function is exposed to the user. This way > implementing a irreducibility testing algorithm(s) might be a good idea. > > > As I read there are several algorithms for that > > and Rabin's irreducibility test > > is an interesting one. Can we implement that in sympy? > > > > There plenty of them. I went a head and pushed a simple implementation > to polys5 branch (see previous E-mail). There are some examples in the > commit message. Rabin's algorithm or any other, why not, just send a > patch applicable on top of polys5 and will see. > > > Regards, > > Kasun > > > > -- > > You received this message because you are subscribed to the Google Groups > > "sympy" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > > http://groups.google.com/group/sympy?hl=en. > > > > -- > Mateusz > > > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
