Manually performing the Miller-Rabin probabilistic primality test What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.
 A: First extract all multiples of $2$ from $241-1$
$$
240 = 2^4 \times 15
$$
Next compute $3^{15}$ mod 240
$$
3^{15} \equiv 8 \mod 241
$$
Repeatedly square
$$
3^{30} = (3^{15})^2 \equiv 8^2 = 64 \mod 241 $$
$$
3^{60} = (3^{30})^2 \equiv 64^2 \equiv -1 \mod 241 $$
You can stop here, since
$$
3^{120}= (3^{60})^2 \equiv (-1)^2 \equiv 1\mod 241 $$
$$
3^{240}= (3^{120})^2 \equiv (-1)^2 \equiv 1\mod 241 $$
A: For Miller's test, we use the following form:
$$a^{2^s\cdot d} \equiv 1 \bmod n$$
We are given that $a = 3$ and $n = 241$.  We want to check if $n = 241$ is prime by Miller's test.  Write $n - 1 = 240 = 2^4 \cdot 15$, so that $s = 4$ and $d = 15$.  Select $a = 3$ to be a number.  Then,
$$\begin{aligned}
3^{2^0 \cdot d} &\bmod n \equiv 8 \bmod n \not\equiv 1\bmod n\\
3^{2^1 \cdot d} &\bmod n \equiv 64 \bmod n \not\equiv 1 \bmod n\\
3^{2^2 \cdot d} &\bmod n \equiv 240 \bmod n \equiv -1\bmod n \not\equiv 1 \bmod n\\
3^{2^3 \cdot d} &\bmod n \equiv 1 \bmod n\\
3^{2^4 \cdot d} &\bmod n \equiv 1 \bmod n
\end{aligned}$$
So the test ends for the fourth and fifth lines.
