Mathematics of Computation

On the multidimensional distribution of the subset sum generator of pseudorandom numbers

Author(s): Alessandro Conflitti; Igor E. Shparlinski.
Journal: Math. Comp. 73 (2004), 1005-1011.
MSC (2000): Primary 11K45, 11T71; Secondary 11T23, 94A60
Posted: September 2, 2003
Retrieve article in: PDF
This article is available free of charge

Abstract: We show that for a random choice of the parameters, the subset sum pseudorandom number generator produces a sequence of uniformly and independently distributed pseudorandom numbers. The result can be useful for both cryptographic and quasi-Monte Carlo applications and relies on bounds of exponential sums.

1.: M. Drmota and R. Tichy, Sequences, discrepancies and applications, Springer-Verlag, Berlin, 1997. MR 98j:11057
2.: R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, Cambridge, 1997. MR 97i:11115
3.: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of applied cryptography, CRC Press, Boca Raton, FL, 1996. MR 99g:94015
4.: H. Niederreiter, Random number generation and Quasi-Monte Carlo methods, SIAM Press, 1992. MR 93h:65008
5.: R. A. Rueppel, Analysis and design of stream ciphers, Springer-Verlag, Berlin, 1986. MR 88h:94002
6.: R. A. Rueppel, `Stream ciphers', Contemporary cryptology: The science of information integrity, IEEE Press, NY, 1992, 65-134.
7.: R. A. Rueppel and J. L. Massey, `Knapsack as a nonlinear function', IEEE Intern. Symp. of Inform. Theory, IEEE Press, NY, 1985, 46.
8.: I. M. Vinogradov, Elements of number theory, Dover Publ., New York, 1954. MR 15:933e

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

Alessandro Conflitti
Affiliation: Dipartimento di Matematica, Università degli Studi di Roma ``Tor Vergata'', Via della Ricerca Scientifica, I-00133 Roma, Italy
Email: conflitt@mat.uniroma2.it

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-03-01563-1
PII: S 0025-5718(03)01563-1
Keywords: Pseudorandom numbers, subset sum problem, knapsack, exponential sums
Received by editor(s): December 5, 2001
Posted: September 2, 2003
Additional Notes: The first author would like to thank Macquarie University for its hospitality during the preparation of this paper
Copyright of article: Copyright 2003, 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 2009, American Mathematical Society Privacy Statement		Search the AMS