Determining algorithm performance by sampling

We are interested in algorithms for deciding whether a given number is or is not a square. As with the algorithm in Section 6, there is some probability that, for a given input $a$, the algorithm may give the wrong answer.

Let $p_a$ be the probability that a given algorithm gives the correct answer for input $a$. We are also interested in $p_S$, which is the average of $p_a$ over all squares $a$, and $p_{PS}$, the average over all pseudo-squares, and $p_Z$, the average of $p_a$ over all $a\in Z^1_n$.

If we are given an algorithm, we can easily determine $p_S$ by running it with input $a=x^2$ on a sample of randomly chosen $x$ and counting the number of times the algorithm answers ``this is a square.''

The procedure for determining $p_Z$ is more elaborate. Suppose we have an algorithm for which $p_S=.6$. Using Lemma 26, generate a sample of 100 members of $Z^1_n$, and run the algorithm on each of them. Suppose we get the answer ``this is a square'' 65 times. There are $\sim50$ squares in the sample, on which there have been .6(50) correct responses and 20 incorrect. Pseudo-squares have been identified as squares $65-30=35$ times, which suggests $p_{PS}\approx15/50$. Finally $p_Z=(p_S+p_{PS})/2\approx.45$.

Lemma 24 or 25 can be used to determine the probability that these estimates come within a specified amount.