The distribution of quadratic residues and non-residues in the Goldwasser–Micali type of cryptosystem

Abstract

We provide unconditional results and conditional ones under the assumption of GRH (Generalized Riemann Hypothesis) on the distribution of quadratic residues and quadratic non-residues in ℤ/Nℤ$\mathbb {Z}/N\mathbb {Z}$, where N=pq$N= pq$ is an RSA modulus used in the Goldwasser–Micali cryptosystem. The paper also discusses cryptographic implications of the results obtained.

Keywords

• quadratic residuosity problem
• goldwasser–micali cryptosystem
• quadratic residues distribution
• 94a60
• 11a15