The situation changes dramatically if we only want to estimate the proportion with high probability. If we are willing to accept a .01 probability of an error , Lemma 24 implies we only need to open a randomly chosen sample of envelopes9.
The special feature of problems involving squares and pseudo-squares is that sampling is possible. We saw in our discussion of the Rabin system that every number mod has four square roots. Thus if we choose one of the numbers not divisible10 by or and compute mod n, each square has a chance of being chosen. It is also important that it is possible to sample from (the set of squares and pseudo-squares) even if are not known.
Given this lemma, we can sample in by choosing at random and testing if it is in the set. If not, another is chosen. Since roughly half of is in , this won't take too long.
The different sampling possibilities we have discussed so far have all assumed that only was known. If we are given a single pseudo-square , we can sample among all pseudo-squares by calculating for randomly chosen.
The possibility of doing these various kinds of sampling is closely related to properties 2(a) and (c) in the paper (p. 277).