13.4 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 6 b 6 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 7 0 and z = 1, then w is not prime; terminate algorithm for this w. 6. [Increase j] Set j = j + 1. If j 6 a, set z = z2mod 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. a. Explain how the algorithm works. b. Show that it is equivalent to the Miller-Rabin test described in Chapter 8. | |
| View Solution | |
| << Back | Next >> |