**On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography**

*Ferucio Laurentiu Tiplea and Sorin Iftene and George Teseleanu and Anca-Maria Nica*

**Abstract: **We develop exact formulas for the distribution of quadratic residues and non-residues in sets of the form $a+X=\{(a+x)\bmod n\mid x\in X\}$, where $n$ is a prime or the product of two primes and $X$ is a subset of integers with given Jacobi symbols modulo prime factors of $n$. We then present applications of these formulas to Cocks' identity-based encryption scheme and statistical indistinguishability.

**Category / Keywords: **public-key cryptography / Jacobi symbol, probability distribution, statistical distance, identity-based encryption

**Original Publication**** (with minor differences): **Applied Mathematics and Computation

**Date: **received 2 Jun 2019, last revised 16 Dec 2019

**Contact author: **ferucio tiplea at uaic ro, siftene2013@gmail com, george teseleanu@yahoo com, meinsta@yahoo com

**Available format(s): **PDF | BibTeX Citation

**Version: **20191216:191626 (All versions of this report)

**Short URL: **ia.cr/2019/638

[ Cryptology ePrint archive ]