On the uniformity of distribution of the RSA pairs

Author:
Igor E. Shparlinski

Journal:
Math. Comp. **70** (2001), 801-808

MSC (2000):
Primary 11T71, 94A60; Secondary 11K38, 11T23

DOI:
https://doi.org/10.1090/S0025-5718-00-01274-6

Published electronically:
June 12, 2000

MathSciNet review:
1813147

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Let $m= pl$ be a product of two distinct primes $p$ and $l$. We show that for almost all exponents $e$ with $\operatorname {gcd} (e, \varphi (m))= 1$ the RSA pairs $(x, x^e)$ are uniformly distributed modulo $m$ when $x$ runs through

- M. Ajtai, ‘Generating hard instances of lattice problems’,
*Electronic Colloq. on Comp. Compl.*, Univ. of Trier,**TR96-007**(1996), 1–29. - W. Banks, F. Griffin, D. Lieman and I. E. Shparlinski, ‘Non-linear complexity of the Naor-Reingold pseudo-random function’,
*Proc. the 2nd Intern. Conf. on Information Security and Cryptology*, Seoul, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, (to appear). - L. Blum, M. Blum, and M. Shub,
*A simple unpredictable pseudorandom number generator*, SIAM J. Comput.**15**(1986), no. 2, 364–383. MR**837589**, DOI https://doi.org/10.1137/0215025 - V. Boyko, M. Peinado and R. Venkatesan, ‘Speeding up discrete log and factoring based schemes via precomputations’,
*Proc. of Eurocrypt’98*, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin,**1403**(1998), 221–234. - R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman and I. E. Shparlinski, ‘On the statistical properties of Diffie–Hellman distributions’,
*Israel J. Math.*, (to appear). - R. Canetti, J. B. Friedlander and I. E. Shparlinski, ‘On certain exponential sums and the distribution of Diffie–Hellman triples’,
*J. London Math. Soc.*, (1999), 799–812. - Thomas W. Cusick, Cunsheng Ding, and Ari Renvall,
*Stream ciphers and number theory*, North-Holland Mathematical Library, vol. 55, North-Holland Publishing Co., Amsterdam, 1998. MR**1634586** - Michael Drmota and Robert F. Tichy,
*Sequences, discrepancies and applications*, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR**1470456** - J. B. Friedlander, D. Lieman and I. E. Shparlinski, ‘On the distribution of the RSA generator’,
*Proc. Intern. Conf. on Sequences and Their Applications (SETA’98), Singapore*, Springer-Verlag, London, 1999, 205–212. - J. B. Friedlander, C. Pomerance and I. E. Shparlinski, ‘Period of the power generator and small values of Carmichael’s function’,
*Math. Comp.*, (to appear). - J. B. Friedlander and I. E. Shparlinski, ‘On the distribution of the power generator’,
*Math. Comp.*, (to appear). - F. Griffin and I. E. Shparlinski, ‘On the linear complexity of the Naor-Reingold pseudo-random function’,
*Proc. 2nd Intern. Conf. on Information and Communication Security*, Sydney, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin,**1726**(1999), 301–308. - F. Griffin and I. E. Shparlinski, ‘On the linear complexity profile of the power generator’, Trans. IEEE Inform. Theory (to appear).
- Russell Impagliazzo and Moni Naor,
*Efficient cryptographic schemes provably as secure as subset sum*, J. Cryptology**9**(1996), no. 4, 199–216. MR**1426279**, DOI https://doi.org/10.1007/s001459900012 - J. C. Lagarias,
*Pseudorandom number generators in cryptography and number theory*, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 115–143. MR**1095554**, DOI https://doi.org/10.1090/psapm/042/1095554 - Michael Luby,
*Pseudorandomness and cryptographic applications*, Princeton Computer Science Notes, Princeton University Press, Princeton, NJ, 1996. MR**1373652** - Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone,
*Handbook of applied cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR**1412797** - M. Naor and O. Reingold, ‘Number-theoretic constructions of efficient pseudo-random functions’,
*Proc. 38th IEEE Symp. on Foundations of Comp. Sci.*, 1997, 458–467. - M. Naor and O. Reingold, ‘Synthesizers and their application to the parallel construction of pseudo-random functions’,
*J. Comp. and Sys. Sci.*,**58**(1999), 336–375. - P. Nguyen, I. E. Shparlinski and J. Stern, ‘Distribution of modular sums and the security of the server aided exponentiation’,
*Preprint*, 2000, 1–16. - P. Nguyen and J. Stern, ‘The hardness of the hidden subset sum problem and its cryptographic implications’,
*Proc. CRYPTO’99*, Santa Barbara, 1999, Springer-Verlag, Berlin,**1666**(1999), 31–46. - I. E. Shparlinski, ‘On the uniformity of distribution of the Naor-Reingold pseudo-random number function’,
*Finite Fields and Their Appl.*(to appear). - I. E. Shparlinski, ‘On the Naor-Reingold pseudo-random number generator from elliptic curves’,
*Appl. Algebra in Engin., Commun. and Computing*(to appear). - I. E. Shparlinski, ‘On the linear complexity of the power generator’,
*Designs, Codes and Cryptography*, (to appear). - I. E. Shparlinski and J. H. Silverman, ‘Linear complexity of the Naor–Reingold pseudo-random number function from elliptic curves’,
*Preprint*, 1999, 1–14. - Douglas R. Stinson,
*Cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR**1327060** - I. M. Vinogradov,
*Elements of Number Theory*, Dover Publ., NY, 1954.

the group of units $\mathbb {Z}_m^*$ modulo $m$ (that is, as in the classical RSA scheme);

the set of $k$-products $x = a_{i_1}\cdots a_{i_k}$, $1 \le i_1 < \cdots < i_k \le n$, where $a_1, \cdots , a_n \in \mathbb {Z}_m^*$ are selected at random (that is, as in the recently introduced RSA scheme with precomputation).

These results are based on some new bounds of exponential sums.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11T71,
94A60,
11K38,
11T23

Retrieve articles in all journals with MSC (2000): 11T71, 94A60, 11K38, 11T23

Additional Information

**Igor E. Shparlinski**

Affiliation:
Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia

MR Author ID:
192194

Email:
igor@ics.mq.edu.au

Keywords:
RSA cryptosystem,
uniform distribution,
precomputation,
exponential sums

Received by editor(s):
June 22, 1999

Published electronically:
June 12, 2000

Article copyright:
© Copyright 2000
American Mathematical Society