Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

On the distribution of the power generator


Authors: John B. Friedlander and Igor E. Shparlinski
Journal: Math. Comp. 70 (2001), 1575-1589
MSC (2000): Primary 11L07, 11T71, 94A60; Secondary 11T23, 11K45
Published electronically: October 17, 2000
MathSciNet review: 1836920
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new method to study the power generator of pseudorandom numbers modulo a Blum integer $m$. This includes as special cases the RSA generator and the Blum-Blum-Shub generator. We prove the uniform distribution of these, provided that the period $t\ge m^{3/4 + \delta}$ with fixed $\delta > 0$ and, under the same condition, the uniform distribution of a positive proportion of the leftmost and rightmost bits. This sharpens and generalizes previous results which dealt with the RSA generator, provided the period $t\ge m^{23/24 + \delta}$. We apply our results to deduce that the period of the binary sequence of the rightmost bit has exponential length.


References [Enhancements On Off] (What's this?)

  • 1. L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364–383. MR 837589 (87k:65007), http://dx.doi.org/10.1137/0215025
  • 2. J. J. Brennan and Bruce Geist, Analysis of iterated modular exponentiation: the orbits of 𝑥^{𝛼}\bmod𝑁, Des. Codes Cryptogr. 13 (1998), no. 3, 229–245. MR 1601580 (99b:11086), http://dx.doi.org/10.1023/A:1008289605486
  • 3. 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).
  • 4. Ran Canetti, John Friedlander, and Igor Shparlinski, On certain exponential sums and the distribution of Diffie-Hellman triples, J. London Math. Soc. (2) 59 (1999), no. 3, 799–812. MR 1709081 (2000g:11079), http://dx.doi.org/10.1112/S002461079900736X
  • 5. J. H. H. Chalk, The Vinogradov-Mordell-Tietäväinen inequalities, Nederl. Akad. Wetensch. Indag. Math. 42 (1980), no. 4, 367–374. MR 597995 (82d:10053)
  • 6. Thomas W. Cusick, Properties of the 𝑥² mod 𝑁 pseudorandom number generator, IEEE Trans. Inform. Theory 41 (1995), no. 4, 1155–1159. MR 1366760 (96k:65006), http://dx.doi.org/10.1109/18.391261
  • 7. 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 (99h:94045)
  • 8. R. Fischlin and C. P. Schnorr, `Stronger security proofs for RSA and Rabin bits', Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1233 (1997), 267-279. CMP 98:09
  • 9. J. B. Friedlander, J. Hansen and I. E. Shparlinski, `Character sums with exponential functions', Mathematika (to appear).
  • 10. 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.
  • 11. 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).
  • 12. F. Griffin and I. E. Shparlinski, `On the linear complexity profile of the power generator', Preprint, 1998, 1-11.
  • 13. F. Griffin, H. Niederreiter and I. E. Shparlinski, `On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders, Proc. the 13th Symp. on Appl. Algebra, Algebraic Algorithms, and Error-Correcting Codes, Hawaii, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1999, v.1719, 87-93.
  • 14. J. Gutierrez, H. Niederreiter and I. E. Shparlinski, `On the multidimensional distribution of inversive congruential pseudorandom numbers in parts of the period', Monatsh. Math. 129 (2000) 31-36. CMP 2000:08
  • 15. J. Håstad and M. Näslund, `The security of individual RSA bits', Proc 39th IEEE Symp. on Foundations of Comp. Sci., 1998, 510-519.
  • 16. N. M. Korobov, The distribution of digits in periodic fractions, Mat. Sb. (N.S.) 89(131) (1972), 654–670, 672 (Russian). MR 0424660 (54 #12619)
  • 17. N. M. Korobov, Exponential sums and their applications, Mathematics and its Applications (Soviet Series), vol. 80, Kluwer Academic Publishers Group, Dordrecht, 1992. Translated from the 1989 Russian original by Yu.\ N. Shakhov. MR 1162539 (93a:11068)
  • 18. 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 (92f:11109), http://dx.doi.org/10.1090/psapm/042/1095554
  • 19. Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M.\ Cohn. MR 1429394 (97i:11115)
  • 20. 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 (99g:94015)
  • 21. Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447 (80d:65016), http://dx.doi.org/10.1090/S0002-9904-1978-14532-7
  • 22. Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997 (93h:65008)
  • 23. H. Niederreiter and I. E. Shparlinski, `On the distribution of inversive congruential pseudorandom numbers in parts of the period', Math. Comp. (to appear).
  • 24. H. Niederreiter and I. E. Shparlinski, `On the distribution and lattice structure of nonlinear congruential pseudorandom numbers', Finite Fields and Their Appl., 5 (1999), 246-253. CMP 99:17
  • 25. H. Niederreiter and I. E. Shparlinski, `On the distribution of inversive congruential pseudorandom numbers modulo a prime power', Acta Arithm. (to appear).
  • 26. H. Niederreiter and I. E. Shparlinski, `On the distribution of pseudorandom numbers and vectors generated by inversive methods', Appl. Algebra in Engin., Commun. and Computing, 10 (2000) 189-202. CMP 2000:11
  • 27. R. A. Rueppel, `Stream ciphers', Contemporary cryptology: The science of information integrity, IEEE Press, NY, 1992, 65-134. CMP 93:08
  • 28. I. E. Shparlinski, `On the linear complexity of the power generator', Designs, Codes and Cryptography (to appear).
  • 29. Douglas R. Stinson, Cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR 1327060 (96k:94015)
  • 30. I. M. Vinogradov, Elements of number theory, Dover Publications, Inc., New York, 1954. Translated by S. Kravetz. MR 0062138 (15,933e)

Similar Articles

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

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


Additional Information

John B. Friedlander
Affiliation: Department of Mathematics, University of Toronto, Toronto, Ontario M5S 3G3, Canada
Email: frdlndr@math.toronto.edu

Igor E. Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
Email: igor@ics.mq.edu.au

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01283-7
PII: S 0025-5718(00)01283-7
Keywords: Pseudorandom numbers, RSA generator, Blum--Blum--Shub, exponential sums
Received by editor(s): April 30, 1999
Received by editor(s) in revised form: November 10, 1999
Published electronically: October 17, 2000
Additional Notes: The first author was supported in part by NSERC grant A5123 and by an NEC grant to the Institute for Advanced Study.
The second author was supported in part by ARC grant A69700294.
Article copyright: © Copyright 2000 American Mathematical Society