| Hosted by CoCalc | Download
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