Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

On the Multidimensional Distribution of the Naor-Reingold Pseudo-Random Function


Authors: San Ling, Igor Shparlinski and Huaxiong Wang
Journal: Math. Comp. 83 (2014), 2429-2434
MSC (2010): Primary 11K45, 11T23, 65C10, 94A60
Published electronically: January 17, 2014
MathSciNet review: 3223338
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K45, 11T23, 65C10, 94A60

Retrieve articles in all journals with MSC (2010): 11K45, 11T23, 65C10, 94A60


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

DOI: https://doi.org/10.1090/S0025-5718-2014-02794-4
Keywords: Naor-Reingold pseudo-random function, discrepancy, exponential sums
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).
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.