Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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)$).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.