Hi, On Sat, Mar 13, 2010 at 10:44:51AM +0100, Kasun Samarasinghe wrote: > hi, > > this is a further clarification. In rabins test there are two conditions > checked. both of them > has to be satisfied. In my implementation for the irreducible polynomials > passed one of them > are not satisfied. the condition which is not satisfying is > > let f in GF(p) be the polynomial passed with a degree n and f | (x**p**n - > x). > > the implementation of the condition check goes like below > > n = gf_degree(f) > h = g = gf_pow([K.one, K.zero], p, p, K) > > this is performed earlier > > j = gf_sub(gf_pow(h,n,p,K) ,[K.one, K.zero],p,K) > > if gf_rem(j,f,p,K) == [K.zero]: > return True > else: > return False > > am i doing anything wrong here? >
one obvious wrong thing is this: if gf_rem(j,f,p,K) == [K.zero]: As said previously, a zero polynomial is [], not [K.zero], so you can just check: if not gf_rem(j,f,p,K): or: if gf_rem(j,f,p,K) == []: When not sure, you can use gf_strip() to remove leading zeros, e.g.: In [28]: from sympy.polys.galoistools import gf_strip In [29]: gf_strip([ZZ.zero, ZZ.zero, ZZ.one]) Out[29]: [1] But remember that on the level of gf_ (and dup_, dmp_, sdp_) functions it is not acceptable to write: if gf_rem(j,f,p,K) == gf_strip([K.zero]): because on this level we need to fight for every function call, for every microsecond. > regards, > kasun > > > On Tue, Mar 9, 2010 at 8:52 PM, Mateusz Paprocki <matt...@gmail.com> wrote: > > > Hi, > > > > On Tue, Mar 09, 2010 at 08:36:18PM +0100, Kasun Samarasinghe wrote: > > > Hi, > > > > > > I m working on the comments, I think i can find out the problems in the > > > algorithm implementation. > > > > > > In the implementation I need to have a polynomial x^(p^ni) to test the > > gcd > > > with the given polynomial. In this situation it takes a long time using > > the > > > gf_pow function. My values are > > > p = 11, ni = {6,4}. Is it because it raises to a large power or is it a > > > problem with my code. > > > > > > > this is a natural thing that gf_pow will be slow because the exponent is > > huge and increasing, and you repeat a lot of computations unnecessarily. > > In the literature there is a method suggested to overcome this problem. > > In general you will need to compute gf_pow only once, at the beginning > > of the algorithm (x**p). > > > > > Kasun > > > > > > On Tue, Mar 9, 2010 at 1:07 PM, Mateusz Paprocki <matt...@gmail.com> > > wrote: > > > > > > > Hi, > > > > > > > > On Sun, Mar 07, 2010 at 02:07:29PM +0100, Kasun Samarasinghe wrote: > > > > > hi, > > > > > I have attached the patch with this for rabin's test for > > irreducibility > > > > > test. Please give me some comments on that. > > > > > > > > > > > > > def gf_irreducible_rabin(f, p, K): > > > > """Test for the irreducibility of a polynomial over `GF(p)[x]`. > > > > > > > > This is an implementation of the Rabin's irreducibility test > > > > for monic polynomials, which is another probabilistic algortihm. > > > > This test is based on the following theorem > > > > > > > > Let p1,p2,...pn be the prime divisors of n, and denote ni = n/pi, > > > > for 1<i<k. A polynomial f in GF(p) of degree n is irreducible in > > > > GF(p), if and only if gcd(f, x^(p^ni)-x mod f ) = 1 for 1 <i<k, and > > > > x^(p^ni)-x | f. > > > > > > > > References > > > > ========== > > > > M O Rabin, Probabilistic algorithims in finite fields. SIAM J Comp., > > > > 273 - 280, 1980. > > > > > > > > """ > > > > from sympy import primefactors > > > > n = gf_degree(f) > > > > if n <= 1: > > > > return True > > > > > > > > for pi in primefactors(n): > > > > g = gf_pow([1,0], pi^(n/pi), p, K) > > > > h = gf_sub(g,[1,0],p,K) > > > > > > > > if gf_gcd(f, h, p, K)!= K.one and gf_rem(g, h, p, K)!= K.zero: > > > > return False > > > > > > > > return True > > > > > > > > A few comments: > > > > > > > > 1. > > > > > > > > (...) a polynomial in `GF(p)[x]`. > > > > > > > > or > > > > > > > > (...) a polynomial over `GF(p)`. > > > > > > > > btw. This might be inconsistent in SymPy after all. > > > > > > > > 2. (...) irreducibility test for monic polynomials (...) > > > > > > > > You say this is for monic polynomials but you don't check this or > > > > make the input polynomial monic anywhere. This will work anyway > > > > because gf_gcd() returns always monic (unique) output (and this > > > > is a general rule for gcd functions in SymPy). > > > > > > > > 3. Missing `from sympy import primefactors` > > > > > > > > 4. [1, 0] must be [K.one, K.zero] because otherwise you introduce > > > > inconsistency to SymPy's ground types with can have bad implications > > > > if your algorithm is used in more complicated context. > > > > > > > > 5. if gf_gcd(f, h, p, K)!= K.one (...) > > > > > > > > No, K is coefficient (ground) domain so it should read != [K.one] > > > > (note that zero polynomial is [] not [K.zero]). > > > > > > > > 6. g = gf_pow([1,0], pi^(n/pi), p, K) > > > > > > > > Should be ** instead of ^, or this is some kind of trick I don't catch? > > > > > > > > 7. M O Rabin, Probabilistic algorithims in finite fields (...) > > > > > > > > Spell check docstrings and comments! > > > > > > > > 8. > > > > References > > > > ========== > > > > M O Rabin, Probabilistic algorithims in finite fields. SIAM J Comp., > > > > 273 - 280, 1980. > > > > > > > > The above doesn't comply with how bibliographic items are written in > > > > polys module, e.g.: > > > > > > > > .. [Geddes92] K. Geddes, S. Czapor, G. Labahn, Algorithms for > > > > Computer Algebra, First Edition, Springer, 1992, pp. 343-347 > > > > > > > > 9. Even with corrections applied the algorithm doesn't work, e.g.: > > > > > > > > In [1]: from sympy.polys.galoistools import * > > > > > > > > In [2]: f = gf_irreducible(6, 11, ZZ) > > > > > > > > In [3]: gf_irreducible_rabin(f, 11, ZZ) > > > > Out[3]: True > > > > > > > > In [4]: gf_irreducible_rabin(gf_pow(f, 2, 11, ZZ), 11, ZZ) > > > > Out[4]: True > > > > ^^^^ Should be False. > > > > > > > > Lets compare with SymPy's irreducibility testing function: > > > > > > > > In [5]: gf_irreducible_p(f, 11, ZZ) > > > > Out[5]: True > > > > > > > > In [6]: gf_irreducible_p(gf_pow(f, 2, 11, ZZ), 11, ZZ) > > > > Out[6]: False > > > > > > > > > Kasun > > > > > > > > > > On Sat, Mar 6, 2010 at 8:32 AM, Ondrej Certik <ond...@certik.cz> > > wrote: > > > > > > > > > > > On Fri, Mar 5, 2010 at 3:00 PM, Kasun Samarasinghe > > > > > > <kwsamarasin...@gmail.com> wrote: > > > > > > > hi, > > > > > > > how can i patch the modification i done using git? > > > > > > > > > > > > I created some video tutorials here: > > > > > > > > > > > > http://code.google.com/p/sympy/wiki/GitTutorials > > > > > > > > > > > > Ondrej > > > > > > > > > > > > -- > > > > > > You received this message because you are subscribed to the Google > > > > Groups > > > > > > "sympy" group. > > > > > > To post to this group, send email to sy...@googlegroups.com. > > > > > > To unsubscribe from this group, send email to > > > > > > sympy+unsubscr...@googlegroups.com<sympy%2bunsubscr...@googlegroups.com> > > <sympy%2bunsubscr...@googlegroups.com<sympy%252bunsubscr...@googlegroups.com> > > >< > > > > sympy%2bunsubscr...@googlegroups.com<sympy%252bunsubscr...@googlegroups.com> > > <sympy%252bunsubscr...@googlegroups.com<sympy%25252bunsubscr...@googlegroups.com> > > > > > > > >. > > > > > > 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 sy...@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > sympy+unsubscr...@googlegroups.com<sympy%2bunsubscr...@googlegroups.com>< > > sympy%2bunsubscr...@googlegroups.com<sympy%252bunsubscr...@googlegroups.com> > > >. > > > > > 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 sy...@googlegroups.com. > > > To unsubscribe from this group, send email to > > sympy+unsubscr...@googlegroups.com <sympy%2bunsubscr...@googlegroups.com>. > > > 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 sy...@googlegroups.com. > To unsubscribe from this group, send email to > sympy+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > -- Mateusz
signature.asc
Description: This is a digitally signed message part