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!

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.

• In the case that n results in the numbers to test being a lot larger, could you give an example of how we would do the modular arithmetic (I'm assuming this is the modular exponentiation) – mino Apr 24 '13 at 14:08
• @mino, added a short paragraph address where exactly the exponentiation is (you've already done it ;) ). – Luke Mathieson Apr 24 '13 at 14:15
• Great - thank you. First time playing around with Miller-Rabin. :-) – mino Apr 24 '13 at 14:17
• Correction: he's found an $a$ which shows $n$ is composite. That is, $32^{340}\equiv 1(341)$ and $32^{170}\equiv 1(341)$ but $32^{85}\equiv 32(341)$ and 32 is not $\pm 1$. Only composites have more than two square roots of 1. 341 is not a strong pseudoprime to the base 32. – Armadillo Jim Jan 28 '17 at 2:03

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