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