Which of the following values are needed for computing $5^{166} \mod 41$ using fast exponentiation.
The values given are : $$\begin{array}{c|c|} & \text{$5^{2^i} \pmod {41}$} \\ \hline \text{ 1} & 5 \\ \hline \text{2} & 25 \\ \hline \text{3} & 10 \\ \hline \text{4} & 18 \\ \hline \text{5} & 37 \\ \hline \text{6} & 30 \\ \hline \text{7} & 9 \\ \hline \end{array}$$
Let's rewrite the table:
$i=1\rightarrow5^{10_2}\equiv5(\mod 41)\\ i=2\rightarrow5^{100_2}\equiv25(\mod 41)\\ i=3\rightarrow5^{1000_2}\equiv10(\mod 41)\\ i=4\rightarrow5^{10000_2}\equiv18(\mod 41)\\ i=5\rightarrow5^{100000_2}\equiv37(\mod 41)\\ i=6\rightarrow5^{1000000_2}\equiv30(\mod 41)\\ i=7\rightarrow5^{10000000_2}\equiv9(\mod 41)$
Now let's turn $166$ into its binary form: $10100110_2$. So, $5^{166}=5^{10100110_2}$ Consider that for $i=k$, $5^{2^k}$ is used if the $(8-k)^{\text{th}}$ bit of $10100110_2$ is $1$ (Example: $5^{2^4}$ is used if the $4$th bit is $1$, which it's not). So, the ones which are used are number $1,2,5,7$.
