Negligible function

From CRYPTUTOR

Revision as of 14:37, 3 January 2007; view current revision
←Older revision | Newer revision→
Jump to: navigation, search

A function \mu:\mathbb{N} \rightarrow\mathbb{R}^{+} is negligible if it approaches zero faster than any inverse polynomial. That is,

For all c>0\,, \mu(n) < 1/n^c\, for all sufficiently large n.

Some examples of negligible functions include 1/2^n\,, 1/2^{\sqrt{n}}\,, and 1/n^{\log n}\,.

Note that any polynomial function times a negligible function remains negligible. In this way, if some outcome of an experiment happens with negligible probability (say, an adversary breaking our cryptographic scheme), and we repeat the experiment a polynomial number of times, we will still only encounter that outcome with negligible probability.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Negligible_function"