module Algebra::PolynomialFactorization::Zp
Public Instance Methods
factorize_modp()
click to toggle source
module_function :verschiebung, :weak_factors_and_r, :factors_of_sqfree, :factorize
# File lib/algebra/polynomial-factor-zp.rb, line 92 def factorize_modp me = self g = sqfree fs = Factors.new g.factors_of_sqfree.each do |f| i, r = 0, 0 while me.deg > 0 q, r = me.divmod f if r.zero? me = q i += 1 else break end end fs.push [f, i] end # for 'over Zp' if ch = ground.char if me.deg > 0 me.verschiebung.factorize_modp.each do |f_i| f0, i0 = f_i fs.push [f0, i0*ch] end end end fs end
factors_of_sqfree()
click to toggle source
# File lib/algebra/polynomial-factor-zp.rb, line 52 def factors_of_sqfree #self assumed to be square and p-free wf, fact_size = weak_factors_and_r n = deg degwize = (1..n).collect{|i| []} wf.each do |f| degwize[f.deg-1].push f end degwize.each_with_index do |a, i| (i..degwize.size-1).each do |j| b = degwize[j] a.each do |f| b.each do |g| next if f == g h = f.gcd(g) if h.deg > 0 && h.deg < f.deg h = h / h.lc unless degwize[h.deg-1].include? h degwize[h.deg-1].push(h) end end end end end end facts = [] degwize.each_with_index do |a, i| b = [] a.each do |f| b.push f unless facts.find{|g| g.divide?(f)} end facts.concat b break if facts.size == fact_size end facts end
verschiebung()
click to toggle source
# File lib/algebra/polynomial-factor-zp.rb, line 13 def verschiebung x = var ch = ground.char e = ground.zero each_with_index do |c, i| e += x ** (i/ch) * c end e end
weak_factors_and_r()
click to toggle source
# File lib/algebra/polynomial-factor-zp.rb, line 23 def weak_factors_and_r #self asumed to be square and p- free y = var ** ground.char n = deg u = Algebra.SquareMatrix(ground, n).collect_column{|i| a = y ** i % self (0...n).collect{|j| a[j]} } u -= u.unity basis = u.kernel_basis wf = [] basis.each_with_index do |h, i| # next if i == 0 fh = self.class.new(*h) (0...ground.char).each do |s| fhg = (fh - s).gcd(self) if fhg.deg > 0 fhgm = fhg / fhg.lc wf.push(fhgm) unless wf.include? fhgm end end end [wf, basis.size] end