Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

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


Authors: Alessandro Conflitti and Igor E. Shparlinski
Journal: Math. Comp. 73 (2004), 1005-1011
MSC (2000): Primary 11K45, 11T71; Secondary 11T23, 94A60
Published electronically: September 2, 2003
MathSciNet review: 2031421
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.


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

  • 1. Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
  • 2. 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
  • 3. 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
  • 4. 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
  • 5. Rainer A. Rueppel, Analysis and design of stream ciphers, Communications and Control Engineering Series, Springer-Verlag, Berlin, 1986. With a foreword by James L. Massey. MR 861124
  • 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 Publications, Inc., New York, 1954. Translated by S. Kravetz. MR 0062138

Similar Articles

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

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


Additional Information

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: https://doi.org/10.1090/S0025-5718-03-01563-1
Keywords: Pseudorandom numbers, subset sum problem, knapsack, exponential sums
Received by editor(s): December 5, 2001
Published electronically: September 2, 2003
Additional Notes: The first author would like to thank Macquarie University for its hospitality during the preparation of this paper
Article copyright: © Copyright 2003 American Mathematical Society