Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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

  • 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.

    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
    Similar Articles
    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