1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer. I'd conclude that it is "negligible". $\endgroup$ – user153465 May 15 '15 at 15:20
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.