본문 바로가기
  • Home

The Sub-Peres Functions for Random Number Generation

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2013, 18(2), pp.19-30
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

배성일 1

1홍익대학교

Accredited

ABSTRACT

We study sub-Peres functions that are defined recursively as Peres function for random number generation. Instead of using two parameter functions as in Peres function, the sub-Peres functions uses only one parameter function. Naturally, these functions produce less random bits, hence are not asymptotically optimal. However, the sub-Peres functions runs in linear time, i.e., in O(n )time rather than O(n logn) as in Peres's case. Moreover, the implementation is even simpler than Peres function not only because they use only one parameter function but because they are tail recursive, hence run in a simple iterative manner rather than by a recursion, eliminating the usage of stack and thus further reducing the memory requirement of Peres's method. And yet, the output rate of the sub-Peres function is more than twice as much as that of von Neumann's method which is widely known linear-time method. So, these methods can be used, instead of von Neumann's method, in an environment with limited computational resources like mobile devices. We report the analyses of the sub-Peres functions regarding their running time and the exact output rates in comparison with Peres function and other known methods for random number generation. Also, we discuss how these sub-Peres function can be implemented.

Citation status

* References for papers published after 2022 are currently being built.

This paper was written with support from the National Research Foundation of Korea.