Comparison: Fermat, Solovay-Strassen, and Miller-Rabin

Fact 4.30 describes the relationships between Fermat liars, Euler liars, and strong liars (see Definitions 4.7,4.15, and 4.21).

  • 4.30 Fact Let n be an odd composite integer.
  • (i) If a is an Euler liar for 11, then it is also a Fermat liar for n.
  • (ii) If a is a strong liar for n, then it is also an Euler liar for n.

4.31 Example (Fermat, Euler, strong liars) Consider the composite integer n = 65 (= 5 x 13). The Fermat liars for 65 are {1,8.12,14,18,21.27,31.34,38,44,47,51.53,57,64}. The Euler liars for 65 are {1,8,14,18,47,51,57,64}, while the strong liars for 65 are

{1,8,18,47,57,64}. □

For a fixed composite candidate n, the situation is depicted in Figure 4.1. This set-

Relationships between Fermat, Euler, and strong liars for a composite integer n

Figure 4.1: Relationships between Fermat, Euler, and strong liars for a composite integer n.

ties the question of the relative accuracy of the Fermat, Solovay-Strassen, and Miller-Rabin tests, not only in the sense of the relative correctness of each test on a fixed candidate n, but also in the sense that given n, the specified containments hold for each randomly chosen base a. Thus, from a correctness point of view, the Miller-Rabin test is never worse than the Solovay-Strassen test, which in turn is never worse than the Fermat test. As the following result shows, there are, however, some composite integers n for which the Solovay-Strassen and Miller-Rabin tests are equally good.

4.32 Fact If n = 3 (mod 4), then a is an Euler liar for n if and only if it is a strong liar for n.

What remains is a comparison of the computational costs. While the Miller-Rabin test may appear more complex, it actually requires, at worst, the same amount of computation as Fermat's test in terms of modular multiplications; thus the Miller-Rabin test is better than Fermat’s test in all regards. At worst, the sequence of computations defined in MILLER- RABIN(n,l) requires the equivalent of computing aSn~'1/2 mod n. It is also the case that MILLER-RABIN(n,l) requires less computation than SOLOVAY-STRASSEN(n,l), the latter requiring the computation of a(«-D/2 mod n and possibly a further Jacobi symbol computation. For this reason, the Solovay-Strassen test is both computationally and conceptually more complex.

  • 4.33 Note (Miller-Rabin is better than Solovay-Strassen) In summary, both the Miller-Rabin and Solovay-Strassen tests are correct in the event that either then input is actually prime, or that they declare their input composite. There is, however, no reason to use the Solovay- Strassen test (nor the Fermat test) over the Miller-Rabin test. The reasons for this are summarized below.
  • (i) The Solovay-Strassen test is computationally more expensive.
  • (ii) The Solovay-Strassen test is harder to implement since it also involves Jacobi symbol computations.
  • (iii) The error probability for Solovay-Strassen is bounded above by (|)f, while the error probability for Miller-Rabin is bounded above by ({)'.

(iv) Any strong liar for n is also an Euler liar for n. Hence, from a correctness point of view, the Miller-Rabin test is never worse than the Solovay-Strassen test.

 
Source
< Prev   CONTENTS   Source   Next >