Randomly generating a "small" polynomial done by generating the coefficients of the polynomial from <math>F_q</math> in a way that either guarantees or makes very likely small coefficients. There are two common ways to do this:
# Using Uniform Sampling - The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let b be an integer that is much less than q. If we randomly choose coefficients from the set: { -b, -b+1, -b+2. ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} the polynomial will be small with respect to the bound (b).
# Using [[Gaussian function|Discrete Gaussian Sampling]] - For an odd value for q, the coefficients of the polynomial are randomly chosen by sampling from the set { -(q-1)/2 to (q-1)/2 } according to a discrete Gaussian distribution with mean 0 and distribution parameter σ. The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. The paper, "Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device," by Dwarakanath and Galbraith provide an overview of this problem.<ref>{{Cite journal|title = Sampling from discrete Gaussians for lattice-based cryptography on a constrained device|url = http://link.springer.com/article/10.1007/s00200-014-0218-3|journal = Applicable Algebra in Engineering, Communication and Computing|date = 2014-03-18|issn = 0938-1279|pages = 159–180|volume = 25|issue = 3|doi = 10.1007/s00200-014-0218-3|first = Nagarjun C.|last = Dwarakanath|first2 = Steven D.|last2 = Galbraith}}</ref>
