Module: CTF::Math

Defined in:
lib/ctf/math.rb

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.check_prime(p, count = nil) ⇒ Object 



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# 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) ⇒ Object 



48
49
50
 
# 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) ⇒ Object

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



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# 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) ⇒ Object

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



72
73
74
75
76
77
78
79
80
81
82
83
84
 
# 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) ⇒ Object 



36
37
38
39
40
41
 
# 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) ⇒ Object 



43
44
45
46
 
# 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) ⇒ Object 



26
27
28
29
30
31
32
33
34
 
# 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) ⇒ Object

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



109
110
111
112
113
114
115
116
117
118
119
 
# 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) ⇒ Object

素因数分解(Pollards-Rho)



122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# 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) ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
24
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


5
6
7
 
# File 'lib/ctf/math.rb', line 5

def sqrt?(n)
  sqrtint(n) ** 2 == n
end

.sqrtint(n) ⇒ Object 



9
10
11
 
# File 'lib/ctf/math.rb', line 9

def sqrtint(n)
  root(n, 2)
end

Instance Method Details

#eulerphi(n, factorized = nil) ⇒ Object 



151
152
153
154
155
156
157
158
 
# 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) ⇒ Object

元の位数の計算



161
162
163
164
165
166
167
168
169
170
171
 
# 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