module Algebra::SplittingField

Public Instance Methods

decompose(pre_facts = nil, var_obj = 'a', no_sq = false) click to toggle source
# File lib/algebra/splitting-field.rb, line 13
def decompose(pre_facts = nil, var_obj = 'a', no_sq = false)
  poly = self
  # poly may have duplicate roots
  ext_field = poly.ground

  polys = pre_facts ? pre_facts.dup : poly.factorize
  roots = []
  # roots == addelems + cmpelems, as set.
  # the difference is ordering.
  addelems = []
  cmpelems = []
  fac = Factors.new

  while fn = polys.shift
    f, n = fn # f: irreducible, n: duplication
    if f.deg <= 1
      fac.push [f, n]
      roots.concat([-f[0] / f[1]] * n) unless f[1].zero?
      cmpelems.concat([-f[0] / f[1]] * n) unless f[1].zero?
    else
      if !no_sq && f.deg == 2
        newF, r, r0 = Algebra.QuadraticExtensionField(ext_field, &f)
        roots.concat([r, r0] * n)

        addelems.push r
        cmpelems.concat([r] * (n - 1))
        cmpelems.concat([r0] * n)

        px, x = Algebra.Polynomial(newF, 'x')
        fac.push [x - r, n]
        fac.push [x - r0, n]
        q = f.convert_to(px) / (x - r) / (x - r0) # scalar
      else
        newF = Algebra.AlgebraicExtensionField(ext_field, var_obj) do |v|
          f.evaluate(v)
        end
        r = newF.var

        roots.concat([r] * n)
        addelems.push r
        cmpelems.concat([r] * (n - 1))

        px, x = Algebra.Polynomial(newF, 'x')
        fac.push [x - r, n]
        q = f.convert_to(px) / (x - r)
      end

      polys_new = q.factorize**n
      polys.each do |g, m|
        g0 = g.convert_to(px)
        fc = g0.factorize
        polys_new.concat fc**m
      end

      ext_field = newF
      polys = polys_new
      var_obj = /^[a-qs-z]\d*$/ =~ var_obj ? var_obj.succ : var_obj + '_'
    end
  end

  mods = if ext_field <= Algebra::AlgebraicExtensionField
           ext_field.def_polys
         else
           []
   end

  proots = addelems + cmpelems

  [ext_field, mods, fac, roots, proots]
end
splitting_field(pre_facts = nil, var_obj = 'a', no_sq = false) click to toggle source
# File lib/algebra/splitting-field.rb, line 84
  def splitting_field(pre_facts = nil, var_obj = 'a', no_sq = false)
    var_obj ||= 'a'
    poly = self
    field, def_polys, fac, roots, proots =
      poly.decompose(pre_facts, var_obj, no_sq)
    roots = roots.collect { |r| field.regulate(r) }
    proots = proots.collect { |r| field.regulate(r) }

    Struct.new(:poly, :field, :roots, :def_polys, :proots)[
poly, field, roots, def_polys, proots
    ]
  end