- There is no efficient algorithm for distinguishing squares from pseudo-squares with for all .
- There is no efficient algorithm with

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.

2002-12-14