<p>In cryptography (and probably in many other areas) there is a huge usage of negligible functions when proving theorems.</p>

<p>Although I know what is a <a href="http://en.wikipedia.org/wiki/Negligible_function" rel="nofollow">negligible function</a>, every time I encounter a function that need to be determined as negligible or not I just don't know how to do that. I just say that the function is negligible if it seems like $c/2^n$ where $c$ is a constant (or known to be negligible).</p>

<p>Can you provide an efficient method to determine quickly if a function is negligible or not?</p>

CC BY-SA 3.0
2014-01-03T00:23:45.973Z
I'm not sure I fully understand your question, but maybe this
tiny bit of algebra helps you: negligible functions are closed
under addition (i.e. if $f, g$ are negligible, then so is the
function $f + g$) and under multiplication with
polynomials (i.e. if $f$ is negligible and $p$ is a polynomial
then the function $n \mapsto f(n)⋅p(n)$ is negligible too). So if
you encounter a function made up by addition of obviously
negligible parts (e.g. $17^{−n}$), and multiplication with
polynomials, you know that the result must also be negligible.
Martin Berger
CC BY-SA 3.0
2014-01-03T01:37:19.867Z
How are you *given* the function?  As a formula, as a black box, or as something else?
Jeffε
CC BY-SA 3.0
2014-01-03T02:54:08.500Z
The textbook by Katz and Lindell has a section on negligible functions and polynomials. Also, a quick web search gives some links that might help you, e.g.: http://cs.stackexchange.com/questions/11073/negligible-function-in-cryptography
Adam Smith
<cc.complexity-theory><cr.crypto-security>
How to determine if a function is negligible?
Bush
# How to determine if a function is negligible?

(Asked by: username_0 on 2014-01-02)

In cryptography (and probably in many other areas) there is a huge usage of negligible functions when proving theorems.

Although I know what is a [negligible function](http://en.wikipedia.org/wiki/Negligible_function), every time I encounter a function that need to be determined as negligible or not I just don't know how to do that. I just say that the function is negligible if it seems like $c/2^n$ where $c$ is a constant (or known to be negligible).

Can you provide an efficient method to determine quickly if a function is negligible or not?

**Tags:** cc.complexity-theory, cr.crypto-security

> **Comments:**
> **username_1**: I'm not sure I fully understand your question, but maybe this tiny bit of algebra helps you: negligible functions are closed under addition (i.e. if $f, g$ are negligible, then so is the function $f + g$) and under multiplication with polynomials (i.e. if $f$ is negligible and $p$ is a polynomial then the function $n \mapsto f(n)⋅p(n)$ is negligible too). So if you encounter a function made up by addition of obviously negligible parts (e.g. $17^{−n}$), and multiplication with polynomials, you know that the result must also be negligible.  
> **username_2**: How are you *given* the function?  As a formula, as a black box, or as something else?  
> **username_3**: The textbook by Katz and Lindell has a section on negligible functions and polynomials. Also, a quick web search gives some links that might help you, e.g.: http://cs.stackexchange.com/questions/11073/negligible-function-in-cryptography  

---

## 0 answers

