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?
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.
