Rabin-Miller primality testing algorithm

The Miller-Rabin algorithm works as follows on input $N$. We assume $N$ is a positive odd integer.

• It computes $k$ such that $2^k$ is the largest power of $2$ dividing $N-1$.
• Then it picks random $1\leq a\le N-1$. If ${\rm gcd}(a,n)\neq 1$ it outputs "composite."
• Otherwise it computes the sequence

  $$a^{N-1}\ {\rm mod}\ N, a^{(N-1)/2}\ {\rm mod}\ N,\dots,a^{(N-1)/2^k}\ {\rm mod}\ N.$$ (3)

  
  
  If the sequence (4) does not start with $1$ it outputs "composite." If the first element in the sequence which is not $1$ is not $-1$ then it outputs "composite." Otherwise it outputs "don't know."