#!/usr/bin/python3
from math import log2, floor, fsum
from gmpy2 import mpq

def factorial(n, limit=1):
  res = mpq(1, 1)
  while n > limit:
    res *= n
    n = n - 1
  return res

# n! / ((n-k)! * k!)
def binomial_coefficient(n, k):
  if k > n-k: k = n-k
  return factorial(n, n-k) / factorial(k)

def binompdf(n, k, p): return binomial_coefficient(n, k) * pow(p, k) * pow(1-p, n-k)
def binomcdf(n, k_min, k_max, p): return sum((binompdf(n, k, p) for k in range(k_min, k_max+1)))

# S and H are lengths in bits. S for the salt, H for the hash.
# wanted_p_success is the success probability that the attacker is allowed to have
def calc_security(S, H, wanted_p_success):
  number_of_salts = pow(2, S)   # how many salts are possible?
  needed_correct_salts = floor(number_of_salts * wanted_p_success)   # floor: underestimate the security
  success_probability = binomcdf(number_of_salts, needed_correct_salts, number_of_salts, mpq(1, pow(2,H)))
  return -log2(success_probability)

print(float(calc_security(13, 9, 0.01)))