## On the uniformity of distribution of the RSA pairs

HTML articles powered by AMS MathViewer

- by Igor E. Shparlinski PDF
- Math. Comp.
**70**(2001), 801-808 Request permission

## Abstract:

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

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

## References

- 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 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**, DOI 10.1007/BFb0093404 - 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 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 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** - Saunders MacLane and O. F. G. Schilling,
*Infinite number fields with Noether ideal theories*, Amer. J. Math.**61**(1939), 771–782. MR**19**, DOI 10.2307/2371335

## 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
- Received by editor(s): June 22, 1999
- Published electronically: June 12, 2000
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1813147