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