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