Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Is $\frac{1}{n!}$ a negligible function where $n$ is a security parameter?
Application: I have a vector of n>100 elements. I permute it and give it to an adversary. The adversary can break it if it can find the original oder of vector. Its probability to succeed is: $\frac{1}{n!}$. Thus, I need to know whether this probability is negligible.
Hint: you can notice that $n! > 2^n$ (except for very small $n$).
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 statment.
The EASIEST solution is to note that $n!$ can be approximated by Stirling's Approximation as $$\sqrt{2\pi n}\bigg(\frac{n}{e}\bigg)^n$$ and so $$\frac{1}{n!} = \frac{1}{\sqrt{2\pi n}\bigg(\frac{n}{e}\bigg)^n}$$ which is clearly an exponentially decaying function and therefore will always be less than any polynomial function $p(n)$ for such that $n>N$ for suitable $N$.
