Miller-Rabin Primality Test I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular exponentiation at some point but I'm not really sure where or why. 
So given $n = 341$   &    $a = 32$ (randomly chosen),
We have  $n-1 = 340 = 2^2 \times 85$
and then   $32^{(2^0\times 85)}\mod 341 = 32$ (not $1$ or $n-1$)
and $32^{(2^1\times85)}\mod 341 = 1$ (so $n$ could be prime)
My notes say: Remember, we use a recursive function where the exponent for the Fermat test is broken down first. While performing repeated squaring, a test for non-trivial square roots is performed.
Could anybody please help me compute this and explain the steps along the way? Thank you!
 A: So you have $n-1$ in the form $2^{\alpha}\cdot d$ where $d$ is odd, then $n$ is composite if there exists any $a \leq n-2$ such that for all $\beta \in [0,\alpha-1]$ we have
$$a^{2^{\beta}\cdot d} \not\equiv 1, -1 (\text{mod } n)$$
The modular exponentiation comes in when we calculate the first test, $a^{2^{0}\cdot d}$. In your example you have to calculate $32^{85}$ modulo $341$.
What is nice is that after that for any $\rho$ we can get $a^{2^{\rho}\cdot d}$ by squaring the previous test value $a^{2^{\rho-1}\cdot d}$. In your case this doesn't really come into play as your $\alpha$ is only $2$, so we only need to test for $\beta = 0,1$. If you had a different $n$, then $\alpha$ might be a lot larger, and you'd end up doing a lot of modular arithmetic.
In your case though, you've found an $a$ which suggests that $n$ might be prime. However if $n$ is composite, then at most $\frac{1}{4}$ of the possible values for $a$ would give a result suggesting primality (a false positive). So based on this one test, you could declare $341$ is prime with only a $25\%$ chance you are wrong.
What you would do in practice is pick $k$ different values for $a$, then declare $n$ to be prime only if all of them pass the test (if any fails, then $n$ is definitely composite). Then you have only a $4^{-k}$ chance of being wrong.
A: What you're asking for is how to do modular exponentiation. The usual first method is exponentiation by squaring.
Say you have $a\cdot b^n$ mod $m$. First, reduce a and b mod m. In your case you're looking at $a=1,b=32,n=35.$
Now at each step you look at the exponent n. If it is even, use $a\cdot b^{2n}=a\cdot (b^2)^n$ to reduce the exponent. If it is odd, use $a\cdot b^{2n+1}=ab\cdot (b^2)^n$. Reduce everything mod $m$ and loop back until the exponent is 1. Then do the multiplication and reduce one last time.
So $1\cdot32^{35}\equiv1\cdot32\cdot(32^2)^{17}\equiv32\cdot1024^{17}\equiv32\cdot342^{17}\pmod{341}$. Now reduce again...
