Reference Needed: $m$-faced dice with $n$ options I would like to investigate the following question and I am not sure if similar ideas have been investigated. I cannot really find a detail discussion about this matter on the Internet. It will be great if you can tell me what domain I should look into, or you may also give your view on the following questions.

Suppose we have one fair dice. We would like to choose an option randomly from 6 possible options. We roll the dice once then we can decide which option we should choose.

Suppose we now have 8 options. To choose an option randomly, different algorithms can be used.
For example, roll the dice once first.
If the result is odd, we focus on option 1 to 4. Then roll the dice again, if we get 1 to 4, we know which option to use. If it is a 5 or 6, repeat the second step again.
If the result is even, we focus on option 5 to 8. Then roll the dice again, if we get $n$, which $1\leq n\leq 4$, we choose option $n+4$. If it is a 5 or 6, repeat the second step again.
One can check the the probability of choosing each option is exactly $\frac{1}{8}$.

My question now is to investigate if it is possible that for whatever number of options we have, we can always use a dice to choose an option randomly. And is there a general algorithm to follow in order to choose an option?
My second question is more advance. Suppose we have a fair $m$-faced dice and we have $n$ total options. Can we choose an option randomly by using the dice for any $m$ and $n$?

Once again, you don't have to answer the above two questions. I am looking for hints or domain that I should look into. Thank you.
 A: Given an $m$-faced die, you can simulate an $n$-faced die, for any values of $m,n>1$.
Suppose the faces of your $m$-die are $0,1,\dots,m-1$. Then write out $0,1,\dots,n-1$ in base $m$. So each face of your $n$-die is associated with a base-$m$ string of length $\ell=\lceil\log_m(n)\rceil$.
Then roll your $m$-die a total of $\ell$ times consecutively, and record each die roll. This gives you a base-$m$ number with $\ell$ digits. If this matches up with one of $0,1,\dots,n-1$, great. If not, repeat the process again.
It's clear that each of the values $0,\dots,n-1$ are equally likely to show up. Furthermore, you will almost surely require a finite number of rolls. In fact, in expectation you will need $m^\ell/n<m$ rounds.

As a concrete example, let's take $m=2$ and $n=7$. Roll our $2$-sided die thrice, the list  of outcomes is $$000,001,010,011,100,101,110,111.$$The first $7$ of these correspond to the faces $0,\dots,6$ of the $7$-sided die. If we roll three $1$s, then we simply ignore the result and go again.
A: We are given a die of $m$ faces, and $n$ options to choose from.  Like in jlammy's answer, let $\ell$ be the number of die rolls.  There are then $m^\ell$ possible outcomes, so we certainly need $m^\ell \geq n$ so that every option has a chance of being chosen.
This answer will tweak jlammy's answer, to be more efficient.  For example, suppose $m=6$ and $n=7$.  If we use $\ell= 2$, there will be $6^2 = 36$ outcomes.  In jlammy's answer, only $7$ of these are used, one for each of the $n=7$ options.  So there is a $\frac{29}{36}$ chance of needing to re-roll.  Instead, we'd like to assign $5$ outcomes to each of the $7$ options.  That way we use $5\cdot 7 = 35$ of the $36$ outcomes, so there is only a $\frac{1}{36}$ chance of needing to re-roll.
To do this, divide $m^\ell$ by $n$, using integer division, so we get a quotient $q$ and a remainder $r$.  Thus $m^\ell = qn+r$, where $0\leq r < n$.  Also, remember that we choose $\ell$ such that $m^\ell \geq n$, which implies $q\geq 1$ (for, if $q\leq 0$ then $m^\ell = qn+r \leq r < n$).  In particular, we have $0\leq r < qn$.
The idea is that each of the $n$ options will be assigned $q$ separate outcomes, with $r$ outcomes left over so the probability of a re-roll will be $\frac{r}{m^\ell}$.  To assign the outcomes, write the die faces as $0, 1, \ldots, m-1$, and the options as $0, 1, \ldots, n-1$.  Now the sequence of $\ell$ die rolls corresponds to an integer written in base-$m$.  Call this number $Z$, so $0\leq Z \leq m^\ell-1$.
If $Z\geq qn$, then re-roll.  Otherwise, assume $0\leq Z\leq qn-1$.  Then divide $Z$ by $q$, and record the quotient (discard the remainder).  That new quotient is the option we select.
Let $p = \frac{r}{m^\ell}$ be the probability of re-rolling, so $0\leq p < 1$.  The expected number of die rolls is
$$\begin{eqnarray*}
E & =& (1-p)(\ell) + p(1-p)(2\ell) + p^2(1-p)(3\ell) + \ldots\\
& =&  \ell (1-p) \left( \sum_{k=1}^\infty k p^{k-1} \right)\\
& =& \ell (1-p) \frac{d}{dp} \sum_{k=1}^\infty  p^k\\
& =& \ell (1-p) \frac{d}{dp} \left(\frac{1}{1-p} - 1 \right) \\
& =& \frac{\ell}{1-p},
\end{eqnarray*}
$$
since $0\leq p < 1$.  Indeed,
$$
E = \frac{\ell}{1-\frac{r}{m^\ell}} = \ell \left(\frac{ m^\ell}{m^\ell - r} \right)  = \ell \left( \frac{qn+r}{qn}\right) = \ell\left(1 + \frac{r}{qn}\right).
$$
Since we know $r< qn$, we get $E< 2\ell$.  But there are $\ell$ die rolls per round of rolling, so the expected number of rounds is less than $2$.  (Compare with the bound of $m$ rounds in jlammy's answer.)
Also, notice that, in terms of minimizing expected number of die rolls, choosing $\ell = \left\lceil \log_m (n)\right\rceil$ may not be optimal.  Above, we have only assumed that $m^\ell \geq n$, so $\ell \geq \left\lceil \log_m(n)\right\rceil$.  We are allowed to choose larger $\ell$ if we want.
For example, suppose $m=6$ and $n=19$.  Then choosing $\ell=2$ gives us $6^2 = 36 = 1\cdot 19 + 17$ outcomes, with a $\frac{17}{36}$ chance of a re-roll.  The expected number of rolls is
$$
2 \left(  \frac{36}{19} \right) = \frac{72}{19}\approx 3.789.
$$
But with $\ell=3$, we have $m^\ell=216 =11\cdot 19 + 7$. So we have expectation
$$
3\left(\frac{216}{209} \right) = \frac{648}{209} \approx 3.100.
$$
In fact $\ell=3$ is optimal for this example.  We must choose $\ell\geq 2$, and notice that we always have $E\geq \ell$.  Thus since we have already found an expectation less than $4$, there is no need to try $\ell$-values that are $4$ or more.  So the only possibilities (for an optimal $\ell$-value) are $\ell=2$ and $\ell=3$, and we have seen that $\ell=3$ is better.
A: A further tweak to mathmandan's scheme is as follows.
For fixed $m,n,\ell$, allocate sequences of $\ell$ numbers from $1,\ldots,m$ to outcomes as before, i.e. choose the largest $k$ such that $kn\leq m^{\ell}$ and allocate $k$ of the smallest (lexicographically) $kn$ sequences to each of $1,\ldots,n$ and the others to "reroll". However, instead of rolling a whole batch $\ell$ and then rerolling if necessary, roll up to $\ell$ dice one by one and stop as soon as you know you will need to reroll. As well as improving the expectation, this can actually change which choice of $\ell$ is best.
For example, with $m=6,n=20$, mathmandan's approach gets $3.6$ with $\ell=2$ and $3.24$ with $\ell=3$, so prefers the latter. However, with $\ell=2$ the reroll combinations are $(4,3),(4,4),\ldots,(6,6)$, so if the first die of the first pair is 5 or 6, you don't need to roll the other one. The expected number of rolls with this modification, $E$, satisfies
$$E=\frac{1}{3}(1+E)+\frac{4}{36}(2+E)+\frac{20}{36}\times2,$$
which gives $E=3$.
(This tweak will also improve the expectation for $\ell=3$ slightly, since you can stop and reroll if your first two rolls are $6,5$ or $6,6$, but it will clearly be worse than $E=3$ for $\ell=2$.)
