If you have a uniform sampler for integers in the interval $[0, 2^k)$, such as an LFSR (which is not very uniform, but let's pretend it were) or any cryptographic PRNG truncated to $k$-bit outputs, the standard way to sample from integers in the interval $[0, n)$ when $n < 2^k$ and $n$ is not a power of two is by rejection sampling.
Consider reducing an integer $x$ in $[0, 2^k)$ modulo $n$, giving $y = x \bmod n$. For each of the $n$ possible values of $y$, there are either $\lfloor2^k/n\rfloor$ or $\lceil2^k/n\rceil$ possible values of $x$ giving $y$—that is, either $2^k/n$ rounded down, or $2^k/n$ rounded up, depending on whether or not $y$ has an ‘extra’ representative $x \geq n\cdot\lfloor2^k/n\rfloor$.
For example, if $k = 4$ so $2^k = 16$, and if $n = 3$, then for $x \in \{0,3,6,9,12,15\}$, of which there are $\lceil16/3\rceil = 6$ possibilities, we have $y = 0$. But for $x \in \{1,4,7,10,13\}$ or $x \in \{2,5,8,11,14\}$, of which there are $\lfloor16/3\rfloor = 5$ possibilities each, we have $y = 1$ or $y = 2$, respectively. Thus $\Pr[y = 0] = 6/16$, but $\Pr[y = 1] = \Pr[y = 2] = 5/16$.
x = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
y = 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 *0
If we first sample an integer from $[0, 2^k)$ uniformly at random, and then reduce modulo $n$, the result will be biased toward the values of $y$ that have an extra possible representative $x \geq n\cdot\lfloor2^k/n\rfloor$, such as the representative $x = 15$ for $y = 0$ in the example above. That gives a nonuniform distribution on integers in $[0, n)$. This bias is sometimes called the modulo bias, although it happens whether the map from $x \in [0, 2^k)$ to $[0, n)$ is $x \mapsto x \bmod n$ or anything else—you can never fit 16 pigeons into 3 holes and get the same number of pigeons per hole, no matter what order you put them in.
If we repeatedly sample integers from $[0, 2^k)$ uniformly at random, and reject some fixed subset of them, say $x = 15$ in the example above, then we can ensure that the only set of values for $x$ we will consider divides evenly into equal-size sets of representatives for $y$. It doesn't matter which subset of values for $x$ we reject, as long as they divide evenly—we could also reject $x = 0$, or even $x = 3$.
x = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
y = *0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0
One easy choice is to reject all values of $x$ below $2^k \bmod n$, because that bound can be computed in $k$-bit unsigned integer arithmetic by the simple expression $(-n) \bmod n$, since
\begin{array}{}
2^k \bmod n &= 2^k \bmod n - 0 \\&= 2^k \bmod n - n \bmod n \\&= (2^k - n) \bmod n.
\end{array}
This gives the following algorithm for sampling an integer in $[0, n)$ uniformly at random given a uniform random sampler for integers in $[0, 2^k)$:
- Sample $x$ uniformly at random from integers in $[0, 2^k)$.
- If $x < 2^k \bmod n$, start over.
- Return $x \bmod n$.
