무작위수생성을 위한 부 페레즈 함수

다국어 초록 (Multilingual 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.

참고문헌 (Reference)

1 배성일, "일라이어스와 페레즈의 방식에 기반한 하이브리드 무작위화 함수" 한국컴퓨터정보학회 17 (17): 149-158, 2012

2 John von Neumann, "Various techniques for use in connection with random digits, In In Monte Carlo Method, Applied Mathematics Series, volume 1" U.S. National Bureau of Standards 36-38, 1951

3 P. Diaconis, "The search for randomness" 2004

4 Peter Elias, "The efficient construction of an unbiased random sequence" 43 (43): 865-870, 1972

5 C. E. Shannon, "The Mathematical Theory of Communication" The University of Illinois Press 1964

6 B. Jun, "The Intel random number generator. White paper prepared for Intel Corporation" Cryptography Research, Inc 1999

7 Sung-il Pae, "Randomizing functions: Simulation of discrete probability distribution using a source of unknown distribution" 52 (52): 965-4976, 2006

8 Sung-il Pae, "Optimal random number generation from a biased coin" 1079-1088, 2005

9 Yuval Peres, "Iterating von Neumann’s procedure for extracting random bits" 20 (20): 590-597, 1992

10 Sung-il Pae, "Exact Computation of Output Rate of Peres's Algorithm for Random Number Generation" 2013

11 T. M. Cover, "Elements of Information Theory. Wiley Series in Telecommunications" John Wiley & Sons 1991

12 P. Diaconis, "Dynamical bias in the coin toss" 49 (49): 211-, 2007

13 Min-su Kim, "A Hybrid Randomizing Function Using Peres-Elias Method for Efficient Generation of Random Bits" Hongik University 2012