A Hybrid Randomizing Function Based on Elias and Peres Method

배성일; 김민수

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2012, 17(12), pp.149-158
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

배성일 ¹, 김민수 ²

¹홍익대학교
²홍익대학교

ABSTRACT

Proposed is a hybrid randomizing function using two asymptotically optimal randomizing functions: Elias function and Peres function. Randomizing function is an mathematical abstraction of producing a uniform random bits from a source of randomness with bias. It is known that the output rate of Elias function and Peres function approaches to the information-theoretic upper bound. Especially, for each fixed input length, Elias function is optimal. However, its computation is relatively complicated and depends on input lengths. On the contrary, Peres function is defined by a simple recursion. So its computation is much simpler, uniform over the input lengths, and runs on a small footprint. In view of this tradeoff between computational complexity and output efficiency, we propose a hybrid randomizing function that has strengths of the two randomizing functions and analyze it.
KEYWORDS

randomizing function, Elias function, Peres function, random number generation
REFERENCES (12)

[book] Donald E. Knuth / 1998 / The Art of Computer Programming, Seminumerical Algorithms / Addison-Wesley

[book] Benjamin Jun / 1999 / The INTEL Random Number Generator / Cryptography Research, Inc

[book] John von Neumann / 1963 / Various techniques for use in connection with random digits, In Monte Carlo Method, Applied Mathematics Series, In Reprinted in von Neumann’s Collected Works 5 / Pergammon Press : 768~770

[confproc] 배성일 / 2005 / Optimal Random Number Generation from a Biased Coin / ACM : 1079~1088

[journal] Sung-il Pae / 2006 / Randomizing functions: Simulation of discrete probability distribution using a source of unknown distribution / IEEE Transactions on Information Theory 52(11) : 4965~4976

[book] Claude Elwood Shannon / 1964 / The Mathematical Theory of Communication / The University of Illinois Press

[book] Thomas M. Cover / 1991 / Elements of Information Theory. Wiley Series in Telecommunications / John Wiley & Sons

[journal] Peter Elias / 1972 / The efficient construction of an unbiased random sequence / The Annals of Mathematical Statistics 43(3) : 865~870

[journal] B. Y. Ryabko / 2000 / Fast and efficient construction of an unbiased random sequence / IEEE Transactions on Information Theory 46(3) : 1090~1093

[journal] Yuval Peres / 1992 / Iterating von Neumann’s procedure for extracting random bits / Annals of Statistics 20(1) : 590~597

[book] Sung-il Pae / Exact Computation of Output Rate of Peres's Algorithm for Random Number Generation

[thesis] Min-su Kim / 2012 / A Hybrid Randomizing Function Using Peres-Elias Method for Efficient Generation of Random Bits / 석사 / Hongik University
KCI Citation (1)

KJC Korea
Journal Central

Statistics

Tools