but i need to check the gcd for all ni, where ni=n/pi. here pi are the prime
factors of n. So
i have to call gf_pow for all such numbers. what can i do in that case?
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.
