Next: The inability to distinguish
Up: Probabilistic Encryption
Previous: Two versions of QRA
QRA talks about the ability to identify squares when only is known.
In the proposed encryption system, a pseudo-square is also announced.
The paper shows (p. 295) that this does not make the problem easier.
Suppose we have an algorithm which takes as input and tries to
decide if is a square. Assume whenever is a pseudo-square.
Choose at random, then use the techniques from Section 7.4
to estimate . Since half the numbers in are pseudo-squares,
you will quickly find a for which .
Translated from LaTeX by Scott Sutherland