# Why $q$ in LWE must be polynomial in $n$

I am wondering why the modulus $$q$$ in the LWE problem has to be polynomial in $$n$$.

Another question is whether one can take it to be an arbitrary integer instead of a prime number.

• Are you asking why $q\in O(poly(n))$, or why $q\in \Omega(poly(n))$? Oct 18 '21 at 11:53
• @Ievgeni It is $O(\text{poly}(n)$
– C.S.
Oct 18 '21 at 12:40
• Could you precise where did you see q should be in $O(poly(n))$? Oct 18 '21 at 12:43
• @Ievgeni it is here cims.nyu.edu/~regev/papers/lwesurvey.pdf The section "Parameters" at the end of page 2. Thanks a lot!
– C.S.
Oct 18 '21 at 12:57

I think the answer is in the document you've found the recommendation : "Choosing an exponential modulus $$q$$ has the disadvantage of significantly increasing the size of the input."
• $(\vec a, 〈\vec a, s〉+ e)$ Oct 18 '21 at 13:06