# What's the function poly() ??

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

• Can you give one example of a place this is used, ideally also a quote with a bit of context? – pjs36 Feb 5 '17 at 20:09
• 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$. – angryavian Feb 5 '17 at 20:10
• @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. – mallea Feb 5 '17 at 20:12