On the Multidimensional Distribution of the Naor–Reingold Pseudo-Random Function
HTML articles powered by AMS MathViewer
- by San Ling, Igor Shparlinski and Huaxiong Wang PDF
- Math. Comp. 83 (2014), 2429-2434 Request permission
Abstract:
We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive and useful property. Namely, it is proved that for almost all values of parameters it produces a uniformly distributed sequence. The proof is based on some recent bounds of character sums with exponential functions.References
Additional Information
- San Ling
- Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore
- Email: lingsan@ntu.edu.sg
- Igor Shparlinski
- Affiliation: Department of Computing, Macquarie University, Sydney NSW 2109, Australia
- MR Author ID: 192194
- Email: igor.shparlinski@mq.edu.au
- Huaxiong Wang
- Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore
- Email: hxwang@ntu.edu.sg
- Received by editor(s): July 28, 2012
- Received by editor(s) in revised form: December 17, 2012
- Published electronically: January 17, 2014
- Additional Notes: During the preparation of this paper, the authors were supported by NRF Grant CRP2-2007-03 (Singapore).
The second author was supported in part by ARC Grant DP1092835 (Australia). - © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 83 (2014), 2429-2434
- MSC (2010): Primary 11K45, 11T23, 65C10, 94A60
- DOI: https://doi.org/10.1090/S0025-5718-2014-02794-4
- MathSciNet review: 3223338