thank you aaron. The rabin test is also very much similar, but it needs to calculate all the prime divisors of n which is the degree of the polynomial.
kasun On Mon, Feb 8, 2010 at 5:48 AM, Aaron S. Meurer <[email protected]> wrote: > 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] <sympy%[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] <sympy%[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.
