## On the distribution of the power generator

HTML articles powered by AMS MathViewer

- by John B. Friedlander and Igor E. Shparlinski PDF
- Math. Comp.
**70**(2001), 1575-1589 Request permission

## 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

- 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 - J. J. Brennan and Bruce Geist,
*Analysis of iterated modular exponentiation: the orbits of $x^\alpha \bmod N$*, Des. Codes Cryptogr.**13**(1998), no. 3, 229–245. MR**1601580**, DOI 10.1023/A:1008289605486 - 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). - 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**, DOI 10.1112/S002461079900736X - J. H. H. Chalk,
*The Vinogradov-Mordell-Tietäväinen inequalities*, Nederl. Akad. Wetensch. Indag. Math.**42**(1980), no. 4, 367–374. MR**597995**, DOI 10.1016/1385-7258(80)90038-4 - Thomas W. Cusick,
*Properties of the $x^2$ mod $N$ pseudorandom number generator*, IEEE Trans. Inform. Theory**41**(1995), no. 4, 1155–1159. MR**1366760**, DOI 10.1109/18.391261 - 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** - 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. - J. B. Friedlander, J. Hansen and I. E. Shparlinski, ‘Character sums with exponential functions’,
*Mathematika*(to appear). - 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). - F. Griffin and I. E. Shparlinski, ‘On the linear complexity profile of the power generator’,
*Preprint*, 1998, 1–11. - 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. - 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. - 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. - N. M. Korobov,
*The distribution of digits in periodic fractions*, Mat. Sb. (N.S.)**89(131)**(1972), 654–670, 672 (Russian). MR**0424660** - 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**, DOI 10.1007/978-94-015-8032-8 - 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 - 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** - 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** - Harald Niederreiter,
*Quasi-Monte Carlo methods and pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), no. 6, 957–1041. MR**508447**, DOI 10.1090/S0002-9904-1978-14532-7 - 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**, DOI 10.1137/1.9781611970081 - H. Niederreiter and I. E. Shparlinski, ‘On the distribution of inversive congruential pseudorandom numbers in parts of the period’,
*Math. Comp.*(to appear). - 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. - H. Niederreiter and I. E. Shparlinski, ‘On the distribution of inversive congruential pseudorandom numbers modulo a prime power’,
*Acta Arithm.*(to appear). - 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. - R. A. Rueppel, ‘Stream ciphers’,
*Contemporary cryptology: The science of information integrity*, IEEE Press, NY, 1992, 65–134. - I. E. Shparlinski, ‘On the linear complexity of the power generator’,
*Designs, Codes and Cryptography*(to appear). - Douglas R. Stinson,
*Cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR**1327060** - Sam Perlis,
*Maximal orders in rational cyclic algebras of composite degree*, Trans. Amer. Math. Soc.**46**(1939), 82–96. MR**15**, DOI 10.1090/S0002-9947-1939-0000015-X

## 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
- MR Author ID: 192194
- Email: igor@ics.mq.edu.au
- 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. - © Copyright 2000 American Mathematical Society
- Journal: Math. Comp.
**70**(2001), 1575-1589 - MSC (2000): Primary 11L07, 11T71, 94A60; Secondary 11T23, 11K45
- DOI: https://doi.org/10.1090/S0025-5718-00-01283-7
- MathSciNet review: 1836920