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
