# What does it mean “polynomial related”?

Taken from

Cambridge University Press 0521830842 - Foundations of Cryptography: Basic Applications, Volume 2 CHAPTER FIVE - Encryption Schemes

which can be downloaded here

Notation. In the rest of this text, we write $E_e (\alpha)$ instead of $E(e, \alpha)$ and $D_d (\beta)$ instead of $D(d, \beta)$. Sometimes, when there is little risk of confusion, we drop these subscripts. Also, we let $G_1 (1^n)$ (resp., $G_2 (1^n )$) denote the first (resp., second) element in the pair G(1n ). That is, $G(1n ) = (G_1 (1^n ), G_2 (1^n))$. Without loss of generality, we may assume that $|G_1 (1^n )|$ and $|G_2 (1^n > )|$ are polynomially related to n, and that each of these integers can be efficiently computed from the other. (In fact, we may even assume that $|G_1 > (1^n )| = |G_2 (1^n)| = n$; see Exercise 6.)

-

## 1 Answer

It just means that the functions mentioned in your question can be written as a polynomial in $n$ (the independent variable is $n$). For example, $n^2+3n+4$ or something like that. It cannot be an exponential function or super-polynomial in $n$ or sublinear (i.e. $o(n)$).

-
Why can't it be sub-linear? – Zach Langley Apr 10 '11 at 15:19
I've make a mistake with my words. What I've meant to say was sublinear but logarithmic. It is allowed to have $n^{1/2}$ for example. – Marcos Villagra Apr 10 '11 at 23:50