Tag Info

New answers tagged

0

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 ...


2

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


1

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 ...


2

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