module Algebra::ChineseRemainderTheorem

Public Instance Methods

decompose_on_cofactors_modp(c, ary, cofacts) click to toggle source
# File lib/algebra/chinese-rem-th.rb, line 25
def decompose_on_cofactors_modp(c, ary, cofacts)
  # c: Polynomial/Zp
  # ary: Array of Polynomial/Zp
  # cofacts: cofacts of ary
  # OutPut: coeff.inner_product(cofacts of ary) == c

  pf = c.ground
  prime = c.ground.char
  coeffs = ary.collect(&:zero)
  d1, *ds = decompose_on_factors(c, cofacts)
  # normalize
  ds_new = []
  ds.each_with_index do |d, i|
    fq, fr = d.divmod(ary[i + 1])
    d1 += fq * ary[0]
    ds_new << fr
  end
  coeffs = [d1] + ds_new

  #    p c == coeffs.inner_product(cofacts)
  coeffs
end
decompose_on_cofactors_p_adic(c, ary, cofacts, prime, k) click to toggle source
# File lib/algebra/chinese-rem-th.rb, line 82
def decompose_on_cofactors_p_adic(c, ary, cofacts, prime, k)
  # c: Polynomial/Intger
  # ary: Array of Polynomial/Integer
  # OutPut: coeff.inner_product(cofacts of ary) === c mod prime**k

  raise if ary.find { |f| (f.lc % prime).zero? }
  #    cofacts = mk_cofacts(ary)
  coeffs = ary.collect(&:zero)
  0.upto k - 1 do |j|
    e = prime**j
    c1 = (c - coeffs.inner_product(cofacts)) / e
    coeffs1 = decomp_on_cofactors_over_p_adic_int_first(c1,
                                                        ary, prime, cofacts)
    coeffs.each_index do |i|
      coeffs[i] += coeffs1[i] * e
    end
  end
  #    p c - coeffs.inner_product(cofacts)
  coeffs
end
decompose_on_factors(c, ary) click to toggle source

return coeffs s.t. coeffs.inner_product(ary) == c entries of c and ary must be euclidian ring

# File lib/algebra/chinese-rem-th.rb, line 8
def decompose_on_factors(c, ary)
  f1, *fs = ary
  k, *coeffs = f1.gcd_ext_all(*fs)
  q, r = c.divmod(k)
  unless r.zero?
    print 'c = '
    p c
    print 'k = '
    p k
    print 'ary = '
    p ary
    raise "#{c} is not expressed by parameters"
  end
  d1, *ds = coeffs.collect { |x| x * q }
  [d1] + ds # this is ok
end
mk_cofacts(ary) click to toggle source
# File lib/algebra/chinese-rem-th.rb, line 74
def mk_cofacts(ary)
  tot = ary.first.unity
  ary.each { |f|; tot *= f; }
  cofacts = []
  ary.each { |f|; cofacts.push tot / f; }
  cofacts
end

Private Instance Methods

decomp_on_cofactors_over_p_adic_int_first(c, ary, prime, cofacts) click to toggle source
# File lib/algebra/chinese-rem-th.rb, line 48
def decomp_on_cofactors_over_p_adic_int_first(c, ary, prime, cofacts)
  pf = Polynomial.reduction(Integer, prime, 'x')
  ary_Zp = ary.collect { |f| pf.reduce(f) }
  cofacts_Zp = cofacts.collect { |f| pf.reduce(f) }
  c_zp = pf.reduce(c)

  d1, *ds = decompose_on_factors(c_zp, cofacts_Zp)

  # normalize
  ds_new = []
  ds.each_with_index do |d, i|
    fq, fr = d.divmod(ary_Zp[i + 1])
    d1 += fq * ary_Zp[0]
    ds_new << fr
  end
  coeffs = [d1] + ds_new
  ring = c.class
  coeffs.collect { |f| lifting(f, ring) }
end
lifting(f, ring) click to toggle source
# File lib/algebra/chinese-rem-th.rb, line 68
def lifting(f, ring)
  f.project(ring) { |c, _i| c.lift }
end