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