Sharedmax-load.sagewsOpen in CoCalc
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