next up previous contents
Next: Knowing a pseudo-square does Up: Probabilistic Encryption Previous: Determining algorithm performance by

Two versions of QRA

1.
There is no efficient algorithm for distinguishing squares from pseudo-squares with $p_a>1-\epsilon$ for all $a\in Z^1_n$.
2.
There is no efficient algorithm with $p_Z>.5+\epsilon$

It would seem that (1) is not as strong as (2). Note that (2) would rule out an algorithm with $p_S=.9$ and $p_{PS}=.2$. This would be something that says ``this is a square'' most of the time, occasionally correctly identifying a pseudo-square. However, the paper (p. 293) shows that (1) implies (2).


Suppose we are given an algorithm. We estimate $p_S,p_{PS},p_Z$ with high probability using the techniques in Section 7.4. To take a specific example, we will assume we find $p_S=.6$, $p_{PS}=.45$. We want to test whether $a$ is a square. Run the algorithm on $ax^2$for 1000 randomly chosen $x$. If $a$ is a square, the algorithm will say ``this is a square'' $\approx600$ times. If $a$ is a pseudo-square, the answer will be ``this is a square'' $\approx550$ times.

Translated from LaTeX by Scott Sutherland
1998-03-15