    Next: Determining algorithm performance by Up: Probabilistic Encryption Previous: Weak laws of large   Contents

## The magic of sampling

We have envelopes. Inside each envelope is a piece of paper with 0 or 1 written on it. If we want to know exactly how many envelopes have each number, we have to open them all. Suppose we want to estimate the fraction of the envelopes of each kind, and we want the proportion to be accurate to within .05. Now we need only open envelopes.

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.

Lemma 26   There is an efficient algorithm for deciding if .

The proof of this is difficult, involving quadratic reciprocity'' and the Jacobi symbol.'' The algorithm itself is not that complicated, and is given in the RSA paper.

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).

#### Footnotes

... envelopes9
Lemma 25 and Mathmatica suggest 400 envelopes are enough.
... divisible10
Even though are unknown, the gcd of can be computed.    Next: Determining algorithm performance by Up: Probabilistic Encryption Previous: Weak laws of large   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14