Tag Info

New answers tagged


Yes, a function $f$ is said to be negligible if for every polynomial function $p(n)$ there exits some constant $N$ such that $f(n) < \frac{1}{p(n)}$ for all $n > N$. If $\frac{1}{n!} < \frac{1}{p(n)}$ then $n! > p(n)$, for all polynomials $p(n)$ and suitable $N$ such that $n>N$. Thus, you'd only have to prove the second segment of the ...


Hint: you can notice that $n! > 2^n$ (except for very small $n$).


To be negligible is not a property of fixed numbers, it is a property of functions of some parameter. It does not make sense to talk about a probability being negligible unless you give a parameter relative to which the probability is negligible. In cryptography we will often consider probability being negligible in the security parameter of the given ...


First of all, keep in mind that all meaningful probabilities must be between $0$ and $1$. In particular, this means that, if $X$ and $Y$ are probabilities, $0 \le XY \le \min(X, Y)$. In cryptography, a probability is considered "negligible" if it is very small. What actually counts as "negligible" depends on context, but typically, we're talking about ...

Top 50 recent answers are included