    Next: Two versions of QRA Up: Probabilistic Encryption Previous: The magic of sampling   Contents

## 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 , the algorithm may give the wrong answer.

Let be the probability that a given algorithm gives the correct answer for input . We are also interested in , which is the average of over all squares , and , the average over all pseudo-squares, and , the average of over all .

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

The procedure for determining is more elaborate. Suppose we have an algorithm for which . Using Lemma 26, generate a sample of 100 members of , and run the algorithm on each of them. Suppose we get the answer this is a square'' 65 times. There are squares in the sample, on which there have been .6(50) correct responses and 20 incorrect. Pseudo-squares have been identified as squares times, which suggests . Finally .

Lemma 24 or 25 can be used to determine the probability that these estimates come within a specified amount.    Next: Two versions of QRA Up: Probabilistic Encryption Previous: The magic of sampling   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14