Manually performing the Miller-Rabin probabilistic primality test

Question

What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.

Answer 1

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 $$

Answer 2

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.