The DSA document includes a recommended algorithm for testing a number for primality. 1. [Choose w] Let w be a random odd integer. Then (w − 1) is even and can be expressed in the form 2am with m odd. That is, 2a is the largest power of 2 that divides (w − 1).
2. [Generate b] Let b be a random integer in the range 1 < b < w.
3. [Exponentiate] Set j = 0 and z = bm mod 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 < a, set z = z2 mod w and go to step 4.
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.

Required:
a. Explain how the algorithm works.
b. Show that it is equivalent to the Miller–Rabin test.