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.