** 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