Length of Chains in Hashing
reset()

def f(m,n,k) :
ell = m/n
if (ell / (k+1) >= 1) : return 1
return (2*n*exp(-ell)*(ell^k)*(ell+1)) / (factorial(k)*(k+1-ell))

def bin_search_f_k_bdd(m,n,t,k) :
while(true) :
if (f(m,n,k) <= 2^(-t)) : return k
else : k = (k<<1)

def bin_search_f_k_range(m,n,t,k_min,k_max) :
if (k_max == 1) : return k_max
while(true):
if (k_max == k_min+1) : return k_max
k_mid = floor((k_max + k_min)>>1)
if (f(m,n,k_mid) <= 2^(-t)) : k_max = k_mid
else: k_min = k_mid

def bin_search_f_n_bdd(m,n,t,k) :
while(true) :
if (f(m,n,k) <= 2^(-t)) : return n
else : n = (n<<1)

def bin_search_f_n_range(m,k,t,n_min,n_max) :
if (n_max == 2) : return n_max
while(true):
if (n_max == n_min+1) : return n_max
n_mid = floor((n_max + n_min)>>1)
if (f(m,n_mid,k) <= 2^(-t)) : n_max = n_mid
else: n_min = n_mid

### MAIN CODE
#n = input("Enter n: ")
#print "\n"
#m = input("Enter m: ")
#print "\n"
#t = input("Enter bits of security t: ")
#print "\n"

### USER INPUT

# "m" represents the number of messages
#m=10^(3)
# "n" represents the size of the hash function's range
#n=10^(3)
# "t" represents the bits of security needed
#t=20

#k_max = bin_search_f_bdd(m,n,t,1)
#k_min = max(1,k_max>>1)

#k_just = bin_search_f_range(m,n,t,k_min,k_max)

#print "At k=", k_just, "we have security", f(m,n,k_just)
#print bool(f(m,n,k_just)<=2^(-t))
#print bool(f(m,n,k_just-1)<=2^(-t))

#for (m,n,t) in [(10^3,10^3,20)] :
#    k_max = bin_search_f_k_bdd(m,n,t,1)
#    k_min = max(1,k_max>>1)
#
#    k_just = bin_search_f_k_range(m,n,t,k_min,k_max)
#    print "At k=", k_just, "we have security", f(m,n,k_just)

for (m,k,t) in [ (10^3,3,8), (10^3,5,8), (10^3,9,8), (10^3,17,8)
, (10^4,3,8), (10^4,5,8), (10^4,9,8), (10^4,17,8)
, (10^6,3,8), (10^6,5,8), (10^6,9,8), (10^6,17,8)
] :
n_max = bin_search_f_n_bdd(m,1,t,k)     #; print n_max
n_min = max(2,n_max>>1)

n_just = bin_search_f_n_range(m,k,t,n_min,n_max)

print "m=", m
print "\t t=", 2^(-t)
print "\t k=", k
print "\t n=", n_just


m= 1000 t= 1/256 k= 3 n= 146183 m= 1000 t= 1/256 k= 5 n= 5185 m= 1000 t= 1/256 k= 9 n= 751 m= 1000 t= 1/256 k= 17 n= 194 m= 10000 t= 1/256 k= 3 n= 4620047 m= 10000 t= 1/256 k= 5 n= 92124 m= 10000 t= 1/256 k= 9 n= 10190 m= 10000 t= 1/256 k= 17 n= 2332 m= 1000000 t= 1/256 k= 3 n= 4618927102 m= 1000000 t= 1/256 k= 5 n= 29076741 m= 1000000 t= 1/256 k= 9 n= 1844154 m= 1000000 t= 1/256 k= 17 n= 328696