Ü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 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?
Also pi as a variable name issue...
> + 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...
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.
