Yes, I think that would be where to put the test.
Maybe p_i then. It won't actually conflict with anything, but it can be
confusing.
Aaron Meurer
On Mar 8, 2010, at 10:02 AM, Kasun Samarasinghe wrote:
> hi
>
> I just used pi to correspond to p sub script i. since for each pi we check
> the relevant conditions. I did not see any conflict with other variables.?.
> Also will a test function in test_galoistools would be sufficient?
>
>
> Thank you,
> kasun
>
> On Mon, Mar 8, 2010 at 5:03 PM, Aaron S. Meurer <asmeu...@gmail.com> wrote:
>
> On Mar 8, 2010, at 4:33 AM, Priit Laes wrote:
>
> > Ühel kenal päeval, P, 2010-03-07 kell 14:07, kirjutas Kasun
> > Samarasinghe:
> >> 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.
> > algorithm
> >> + 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.
> >
> > spaces after commas
> > "1 < i < k" looks better than "1<i<k"
> > maybe use some other variable name than pi (which is regularily used as
> > 3.14..)
> > we can use "iff" instead of "if and only if" ;)
> I'm a fan of if and only if over iff personally. Iff is a little too close
> to if that it's easy to mistype/read it.
> >
> > I also found the algorithm:
> > Let p_1, p_2, ..., p_n be all the prime divisors of n, and denote
> > n/p_i = n_i, for 1 <= i <= k. A polynomial f in GF_q(x) of degree n
> > is irreducible in GF_q(x) iff gcd(f, x^{q^{n_i}} - x mod f) = 1,
> > for 1 <= i <= k, and f divides (x^{q^n} - x).
> >
> >> +
> >> + References
> >> + ==========
> >> + M O Rabin, Probabilistic algorthims in finite fields. SIAM J Comp.,
> >
> > algorithms
> >
> >> + 273 - 280, 1980.
> >> +
> >> + """
> >> + n = gf_degree(f)
> >> + if n <= 1:
> >> + return True
> >> +
> >> + for pi in primefactors(n):
> >> + g = gf_pow([1,0], pi^(n/pi), p, K)
> >
> > Is ^ conjuction (logical AND) or power operator?
> I was wondering this too.
> >
> > Also pi as a variable name issue…
> This also confused me, but if it is the commonly used name for this
> algorithm, then it should be fine I think.
> >
> >> + 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
> >
> > Also some tests would be nice because I'm not really sure that
> > current code actually works…
> Yes, definitely.
>
> I would also like to have Matuesz look at it before it goes in, if he is
> around.
>
> Aaron Meurer
> >
> > Cheers,
> > Priit :)
> >
> > --
> > 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.
> >
>
> --
> 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.
>
>
>
> --
> 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.
--
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.
