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, 2014 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, 2014 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, 2014 at 2:54

0

Reset to default

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.