%%% Compute the Success probability of the multiple differential cryptanalysis %%%
%%% according to the Corollary 2 of BLONDEAU-GERARD FSE 2011.                  %%%


%%% Parameters:
%%%    pstar: probability $p_*$ for the key candidate
%%%    p    : probability $p$ for other key candidates
%%%    Ns   : number of samples ($N |\Delta_0|/2$)
%%%    l    : size of the list of kept candidates
%%%    n    : total number of candidates

function res=PS(pstar,p,nb_samples,l,n)

%%% First determining the relative threshold that is
%%% computing $F^{-1}((l-1)/(n-2))$

y = (l-1)/(n-2);
taumin = p;
taumax = min(10*pstar,1);
tau = (taumin+taumax)/2;

while abs(log(hybridcdf_comp(tau,p,nb_samples)) - log(y)) > 0.01 * log(2)
  if hybridcdf_comp(tau,p,nb_samples) > y
    taumin = tau;
  else
    taumax = tau;
  end
  tau = (taumin+taumax)/2;
  if  ( (taumax - taumin) < 1/nb_samples )
    break
  end
end

tau = floor(tau*nb_samples) / nb_samples;

if (hybridcdf_comp(tau,p,nb_samples) > y)
  tau = (tau*nb_samples + 1) / nb_samples;
end

%%% Now we compute the success probability

if (tau < 0)
  res = 0
else
  if (tau < pstar)
    res = 1-hybridcdf(tau,pstar,nb_samples);
  else
    res = hybridcdf_comp((tau*nb_samples-1)/nb_samples,pstar,nb_samples);
  end  
end

end