2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – mino Apr 24 '13 at 14:08
  • 1
    $\begingroup$ @mino, added a short paragraph address where exactly the exponentiation is (you've already done it ;) ). $\endgroup$ – Luke Mathieson Apr 24 '13 at 14:15
  • $\begingroup$ Great - thank you. First time playing around with Miller-Rabin. :-) $\endgroup$ – mino Apr 24 '13 at 14:17
  • $\begingroup$ 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. $\endgroup$ – Armadillo Jim Jan 28 '17 at 2:03
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.