module CTF::Math

Public Class Methods

check_prime(p, count = nil) click to toggle source
# File lib/ctf/math.rb, line 86
def check_prime(p, count = nil)
  return true if [2,3].include?(p)
  return false if p.even? || p < 2

  d, s = p - 1, 0
  d, s = d >> 1, s + 1 while d.even?

  count = [16, p.to_s(4).size].max unless count
  count.times do
    a = rand(2...(p - 1))
    return false if p.gcd(a) != 1
    if (x = mod_pow(a, d, p)) != 1
      return false unless (0...s).inject(false) do |res, r| 
        break true if(x == p - 1)
        x = x * x % p
        next false
      end
    end
  end
  return true
end
chinese_remainder(m1,m2,a,b) click to toggle source
# File lib/ctf/math.rb, line 48
def chinese_remainder(m1,m2,a,b)
  return (m2 * a * mod_inverse(m2,m1) + m1 * b * mod_inverse(m1,m2)) % (m1 * m2)
end
discrete_log(a, b, mod, k = nil) click to toggle source

離散対数 O(k ^ (1/2) * log(mod))

# File lib/ctf/math.rb, line 53
def discrete_log(a, b, mod, k = nil)
  n = ::Math::sqrt(k || mod).ceil + 1
  p, q = 1, b
  inverse = mod_pow(mod_inverse(a, mod), n, mod)
  t = Hash.new
  n.times do |i|
    t[p] = i unless t.key?(q)
    p = p * a  % mod
  end
  n.times do |i|
    return i * n + t[q] if t.key?(q)
    q = (q * inverse) % mod
  end
  return nil # not found
end
discrete_log2(g, e, mod) click to toggle source

Pohlig-Hellman Algorithmによる離散対数 en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm require mod is prime!

# File lib/ctf/math.rb, line 72
def discrete_log2(g, e, mod)
  res = 0
  mod2 = 1
  prime_factorization2(mod - 1).each do |pi, ei|
    m = pi ** ei
    ng = mod_pow(g,(mod - 1) / m, mod)
    ne = mod_pow(e,(mod - 1) / m, mod)
    x = discrete_log(ng, ne, mod, m)
    res = chinese_remainder(mod2, m, res, x % m)
    mod2 *= m
  end
  return res
end
extgcd(a,b) click to toggle source
# File lib/ctf/math.rb, line 36
def extgcd(a,b)
  return [1,0] if b == 0
  y,x = extgcd(b, a % b)
  y -= (a/b)*x
  return [x,y]
end
mod_inverse(a, mod) click to toggle source
# File lib/ctf/math.rb, line 43
def mod_inverse(a, mod)
  x,y = extgcd(a, mod)
  return x % mod
end
mod_pow(a, n, mod) click to toggle source
# File lib/ctf/math.rb, line 26
def mod_pow(a, n, mod)
  ret = 1
  while n > 0
    ret = (ret * a) % mod if n.odd?
    a = (a * a) % mod
    n >>= 1
  end
  ret
end
prime_factorization(n) click to toggle source

素因数分解(試し割り法)

# File lib/ctf/math.rb, line 109
def prime_factorization(n)
  res = []
  Prime.each do |p|
    break if p * p > n
    cnt = 0
    cnt, n = cnt + 1, n / p while n % p == 0
    res << [p,cnt] if cnt > 0
  end
  res << [n, 1] if n > 1
  return res
end
prime_factorization2(n, max_sieve = 65536, rec = true) click to toggle source

素因数分解(Pollards-Rho)

# File lib/ctf/math.rb, line 122
def prime_factorization2(n, max_sieve = 65536, rec = true)
  res = []
  Prime.each do |p|
    break if p > max_sieve
    while n % p == 0
      res << p
      n =  n / p
    end
  end
  if check_prime(n)
    res << n
  elsif n == 1
  else
    [1,51,73].each do |i|
      x,y,d = 2,2,1
      while d == 1
        x = (x * x + i) % n
        y = (((y * y + i) % n) ** 2 + i) % n
        d = n.gcd((x-y).abs)
      end
      next if d == n
      res += prime_factorization2(d, 0, false) + prime_factorization2(n / d, 0, false)
      break
    end
  end
  res = res.sort.uniq.map{|a| [a, res.count(a)]} if rec
  return res
end
root(n, k) click to toggle source
# File lib/ctf/math.rb, line 13
def root(n, k)
  low, high = 0, n + 1
  while low + 1 < high
    mid = (low + high) / 2
    if n < mid ** k
      high = mid
    else
      low = mid
    end
  end
  low
end
sqrt?(n) click to toggle source
# File lib/ctf/math.rb, line 5
def sqrt?(n)
  sqrtint(n) ** 2 == n
end
sqrtint(n) click to toggle source
# File lib/ctf/math.rb, line 9
def sqrtint(n)
  root(n, 2)
end

Public Instance Methods

eulerphi(n, factorized = nil) click to toggle source
# File lib/ctf/math.rb, line 151
def eulerphi(n, factorized = nil)
  factorized = prime_factorization2(n) unless factorized
  phi = n
  factorized.each do |p,k|
    phi = phi - phi / p
  end
  phi
end
order(g, mod) click to toggle source

元の位数の計算

# File lib/ctf/math.rb, line 161
def order(g, mod)
  tmp = eulerphi(mod)
  ret = prime_factorization2(tmp)
  order = 1
  ret.each do |p, k|
    order *= p ** (k - (0..k).select{|i|
      mod_pow(g, tmp / p ** i, mod) == 1
    }.max)
  end
  order
end

Private Instance Methods

check_prime(p, count = nil) click to toggle source
# File lib/ctf/math.rb, line 86
def check_prime(p, count = nil)
  return true if [2,3].include?(p)
  return false if p.even? || p < 2

  d, s = p - 1, 0
  d, s = d >> 1, s + 1 while d.even?

  count = [16, p.to_s(4).size].max unless count
  count.times do
    a = rand(2...(p - 1))
    return false if p.gcd(a) != 1
    if (x = mod_pow(a, d, p)) != 1
      return false unless (0...s).inject(false) do |res, r| 
        break true if(x == p - 1)
        x = x * x % p
        next false
      end
    end
  end
  return true
end
chinese_remainder(m1,m2,a,b) click to toggle source
# File lib/ctf/math.rb, line 48
def chinese_remainder(m1,m2,a,b)
  return (m2 * a * mod_inverse(m2,m1) + m1 * b * mod_inverse(m1,m2)) % (m1 * m2)
end
discrete_log(a, b, mod, k = nil) click to toggle source

離散対数 O(k ^ (1/2) * log(mod))

# File lib/ctf/math.rb, line 53
def discrete_log(a, b, mod, k = nil)
  n = ::Math::sqrt(k || mod).ceil + 1
  p, q = 1, b
  inverse = mod_pow(mod_inverse(a, mod), n, mod)
  t = Hash.new
  n.times do |i|
    t[p] = i unless t.key?(q)
    p = p * a  % mod
  end
  n.times do |i|
    return i * n + t[q] if t.key?(q)
    q = (q * inverse) % mod
  end
  return nil # not found
end
discrete_log2(g, e, mod) click to toggle source

Pohlig-Hellman Algorithmによる離散対数 en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm require mod is prime!

# File lib/ctf/math.rb, line 72
def discrete_log2(g, e, mod)
  res = 0
  mod2 = 1
  prime_factorization2(mod - 1).each do |pi, ei|
    m = pi ** ei
    ng = mod_pow(g,(mod - 1) / m, mod)
    ne = mod_pow(e,(mod - 1) / m, mod)
    x = discrete_log(ng, ne, mod, m)
    res = chinese_remainder(mod2, m, res, x % m)
    mod2 *= m
  end
  return res
end
extgcd(a,b) click to toggle source
# File lib/ctf/math.rb, line 36
def extgcd(a,b)
  return [1,0] if b == 0
  y,x = extgcd(b, a % b)
  y -= (a/b)*x
  return [x,y]
end
mod_inverse(a, mod) click to toggle source
# File lib/ctf/math.rb, line 43
def mod_inverse(a, mod)
  x,y = extgcd(a, mod)
  return x % mod
end
mod_pow(a, n, mod) click to toggle source
# File lib/ctf/math.rb, line 26
def mod_pow(a, n, mod)
  ret = 1
  while n > 0
    ret = (ret * a) % mod if n.odd?
    a = (a * a) % mod
    n >>= 1
  end
  ret
end
prime_factorization(n) click to toggle source

素因数分解(試し割り法)

# File lib/ctf/math.rb, line 109
def prime_factorization(n)
  res = []
  Prime.each do |p|
    break if p * p > n
    cnt = 0
    cnt, n = cnt + 1, n / p while n % p == 0
    res << [p,cnt] if cnt > 0
  end
  res << [n, 1] if n > 1
  return res
end
prime_factorization2(n, max_sieve = 65536, rec = true) click to toggle source

素因数分解(Pollards-Rho)

# File lib/ctf/math.rb, line 122
def prime_factorization2(n, max_sieve = 65536, rec = true)
  res = []
  Prime.each do |p|
    break if p > max_sieve
    while n % p == 0
      res << p
      n =  n / p
    end
  end
  if check_prime(n)
    res << n
  elsif n == 1
  else
    [1,51,73].each do |i|
      x,y,d = 2,2,1
      while d == 1
        x = (x * x + i) % n
        y = (((y * y + i) % n) ** 2 + i) % n
        d = n.gcd((x-y).abs)
      end
      next if d == n
      res += prime_factorization2(d, 0, false) + prime_factorization2(n / d, 0, false)
      break
    end
  end
  res = res.sort.uniq.map{|a| [a, res.count(a)]} if rec
  return res
end
root(n, k) click to toggle source
# File lib/ctf/math.rb, line 13
def root(n, k)
  low, high = 0, n + 1
  while low + 1 < high
    mid = (low + high) / 2
    if n < mid ** k
      high = mid
    else
      low = mid
    end
  end
  low
end
sqrt?(n) click to toggle source
# File lib/ctf/math.rb, line 5
def sqrt?(n)
  sqrtint(n) ** 2 == n
end
sqrtint(n) click to toggle source
# File lib/ctf/math.rb, line 9
def sqrtint(n)
  root(n, 2)
end