Mathematics of Computation

Author(s): John B. Friedlander; Igor E. Shparlinski.
Journal: Math. Comp. 70 (2001), 1575-1589.
MSC (2000): Primary 11L07, 11T71, 94A60; Secondary 11T23, 11K45
Posted: October 17, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: We present a new method to study the power generator of pseudorandom numbers modulo a Blum integer

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

1.: L. Blum, M. Blum and M. Shub, `A simple unpredictable pseudorandom number generator', SIAM J. Comp., 15 (1986), 364-383. MR 87k:65007
2.: J. J. Brennan and B. Geist, `Analysis of iterated modular exponentiation: The orbit of $x^\alpha \bmod N$ ', Designs, Codes and Cryptography, 13 (1998), 229-245. MR 99b:11086
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.: R. Canetti, J. B. Friedlander and I. E. Shparlinski, `On certain exponential sums and the distribution of Diffie-Hellman triples', J. London Math. Soc., 59 (1999), 799-812. MR 2000g:11079
5.: J. H. H. Chalk, `The Vinogradov-Mordell-Tietäväinen inequalities', Indag. Math., 42 (1980), 367-374. MR 82d:10053
6.: T. W. Cusick, `Properties of the $x^2 \bmod N$ pseudorandom number generator', IEEE Trans. Inform. Theory, 41 (1995), 1155-1159. MR 96k:65006
7.: T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier, Amsterdam, 1998. MR 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, `On the distribution of digits in periodic fractions', Math. USSR - Sbornik, 18 (1972), 659-676. MR 54:12619
17.: N. M. Korobov, Exponential sums and their applications, Kluwer Acad. Publ., Dordrecht, 1992. MR 93a:11068
18.: J. C. Lagarias, `Pseudorandom number generators in cryptography and number theory', Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, 42 (1990), 115-143. MR 92f:11109
19.: R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, Cambridge, 1997. MR 97i:11115
20.: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, 1997. MR 99g:94015
21.: H. Niederreiter, `Quasi-Monte Carlo methods and pseudo-random numbers', Bull. Amer. Math. Soc., 84 (1978), 957-1041. MR 80d:65016
22.: H. Niederreiter, Random number generation and Quasi-Monte Carlo methods, SIAM Press, Philadelphia, 1992. MR 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.: D. R. Stinson, Cryptography: Theory and Practice, CRC Press, Boca Raton, FL, 1995. MR 96k:94015
30.: I. M. Vinogradov, Elements of Number Theory, Dover Publ., NY, 1954. MR 15:933e

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: 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
Posted: 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 of article: Copyright 2000, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS