On the multidimensional distribution of the Naor-Reingold pseudo-random function

San Ling, Igor Shparlinski, Huaxiong Wang

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
17 Downloads (Pure)


We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive anduseful property. Namely, it is proved that for almost all values of parameters itproduces a uniformly distributed sequence. The proof is based on some recentbounds of character sums with exponential functions.

Original languageEnglish
Pages (from-to)2429-2434
Number of pages6
JournalMathematics of Computation
Issue number289
Publication statusPublished - 2014

Bibliographical note

Copyright 2014 American Mathematical Society. First published in Mathematics of computation, vol. 83, no. 289, published by the American Mathematical Society. The original article can be found at http://doi.org/10.1090/S0025-5718-2014-02794-4


  • Discrepancy
  • Exponential sums
  • Naor-Reingold pseudo-random function


Dive into the research topics of 'On the multidimensional distribution of the Naor-Reingold pseudo-random function'. Together they form a unique fingerprint.

Cite this