It would seem that (1) is not as strong as (2). Note that (2) would rule out an algorithm with and . This would be something that says ``this is a square'' most of the time, occasionally correctly identifying a pseudo-square. However, the paper (p. 293) shows that (1) implies (2).
Suppose we are given an algorithm. We estimate with high probability using the techniques in Section 7.4. To take a specific example, we will assume we find , . We want to test whether is a square. Run the algorithm on for 1000 randomly chosen . If is a square, the algorithm will say ``this is a square'' times. If is a pseudo-square, the answer will be ``this is a square'' times.