In cryptographic context, we often observe the function $\mathsf{poly}$.

For example , let $n$ be an integer, this function is called in a manner such as $\mathsf{poly}$(n).

What's the exact meaning of $\mathsf{poly}$(n) ??

  • 1
    $\begingroup$ Can you give one example of a place this is used, ideally also a quote with a bit of context? $\endgroup$ – pjs36 Feb 5 '17 at 20:09
  • 5
    $\begingroup$ If it is used to describe the time/space complexity of an algorithm, it is not a function, just a shorthand to mean that the complexity is a polynomial function of $n$, e.g. $n^{100}$ or $5n^5+n^2+n$. This is to contrast it with exponential complexity like $2^n$. $\endgroup$ – angryavian Feb 5 '17 at 20:10
  • $\begingroup$ @pjs36 For example, || gh mod f|| < poly(n)||g|$|\cdot$||h||, where $g,h$ are any polynomials over $\mathbb{Z}[x], f$ is a irreducible polynomial, and || $\cdot$|| represents l1-norm of some poly. $\endgroup$ – mallea Feb 5 '17 at 20:12

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.