0
$\begingroup$

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, 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?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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. $\endgroup$
    – Martin Berger
    Jan 3 '14 at 0:23
  • 1
    $\begingroup$ How are you given the function? As a formula, as a black box, or as something else? $\endgroup$
    – Jeffε
    Jan 3 '14 at 1:37
  • 2
    $\begingroup$ 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.: cs.stackexchange.com/questions/11073/… $\endgroup$
    – Adam Smith
    Jan 3 '14 at 2:54

Your Answer

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

Browse other questions tagged or ask your own question.