lcg-inverse.rb

A = 0x5D588B656C078965
B = 0x269EC3
M = 2**64

#A = 0x41c64e6d
#B = 0x6073
#M = 2**32

# LCGOperator(a, b)はx -> (ax + b) % Mという関数を表すものとする

LCGOperator = Struct.new(:a, :b)
class LCGOperator
  # 合成
  def o(y)
    x = self
    LCGOperator.new((x.a * y.a) % M, (x.a * y.b + x.b) % M)
  end

  # 累乗
  def pow(n)
    x = self
    if n == 0
      LCGOperator.new(1, 0)
    elsif n.odd?
      x.o(x).pow(n/2).o(x)
    else
      x.o(x).pow(n/2)
    end
  end

  # 適用
  def apply(s)
    (self.a * s + self.b) % M
  end
end

inverse = LCGOperator.new(A, B).pow(M-1)
puts "%.16x" % inverse.a
puts "%.16x" % inverse.b

実行結果:
dedcedae9638806d
9b1ae6e9a384e6f9