Paper 2019/638 Original: eprint.iacr.org/2019/638 ↗
On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2022-03-15: last updated
- 2019-06-03: published
- Short URL
- https://ia.cr/2019/638
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2019/638,
author = {Ferucio Laurentiu Tiplea and Sorin Iftene and George Teseleanu and Anca-Maria Nica},
title = {On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/638},
year = {2019},
url = {https://eprint.iacr.org/2019/638}
}