# 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-

**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 *aS ^{n}~*'

^{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.