State precisely the Miller-Rabin primality test.

(i) Let $p$ be a prime $\geqslant 5$, and define

$$N=\frac{4^{p}-1}{3}$$

Prove that $N$ is a composite odd integer, and that $N$ is a pseudo-prime to the base 2 .

(ii) Let $M$ be an odd integer greater than 1 such that $M$ is a pseudo-prime to the base 2 . Prove that $2^{M}-1$ is always a strong pseudo-prime to the base 2 .