The DSS document includes a recommended algorithm for testing a number for primality.

1. [Choose \(\boldsymbol{w}\) ] Let \(w\) be a random odd integer. Then \((w-1)\) is even and can be expressed in the form \(2^{a} m\) with \(m\) odd. That is, \(2^{a}\) is the largest power of 2 that divides \((w-1)\).

2. [Generate \(\boldsymbol{b}\) ] Let \(b\) be a random integer in the range \(1

3. [Exponentiate] Set \(j=0\) and \(z=b^{m} \bmod w\).

4. [Done?] If \(j=0\) and \(z=1\), or if \(z=w-1\), then \(w\) passes the test and may be prime; go to step 8.

5. [Terminate?] If \(j>0\) and \(z=1\), then \(w\) is not prime; terminate algorithm for this \(w\).

6. [Increase \(j\) ] Set \(j=j+1\). If \(j

7. [Terminate] \(w\) is not prime; terminate algorithm for this \(w\).

8. [Test again?] If enough random values of \(b\) have been tested, then accept \(w\) as prime and terminate algorithm; otherwise, go to step 2.

a. Explain how the algorithm works.

b. Show that it is equivalent to the Miller-Rabin test described in Chapter 8.