[Math] Miller-Rabin Primality Test

modular arithmeticprimality-testprime numbers

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!

Best Answer

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.

Related Solutions

[Math] Miller-Rabin primality test, begginer reading pseudo code

First part of answer:

...
if x = 1 then return composite
...

This is correct, because if $x=1$ then all other squaring operations $x := x^2 \pmod{n}$ in the loop leave $x=1$ and therefore $$a^{2^r\cdot d} \not \equiv -1\pmod{n}$$

Second part: You get $s$ and $d$ from $n-1$ with a loop like this (the loop invariant is $n-1= 2^s d)$

d := n-1;   
s := 0;   
while even(d) do begin
  d := d/2;
  s := s+1;   
end;

Miller Rabin Proof

If you start with $a^{s 2^N} \equiv 1 \bmod n, a^s \not \equiv 1 \bmod n$ then by repeated squaring, at some point you'll obtain $x = a^{2^ms}, x \not \equiv 1 \bmod n, x^2 \equiv 1 \bmod n$, if $n$ is prime this implies $x \equiv -1 \bmod n$

(because for $n=p$ prime the polynomial $x^2-1$ has only two roots in the field $\Bbb{Z/p Z}$)

Best Answer

Related Solutions

[Math] Miller-Rabin primality test, begginer reading pseudo code

Miller Rabin Proof

Related Question