A Hybrid Randomizing Function Based on Elias and Peres Method

배성일; Kim, Minsu

KJC Korea
Journal Central

Journal of The Korea Society of Computer and Information 2021 KCI Impact Factor : 0.62

Korean | English

pISSN : 1598-849X / eISSN : 2383-9945

http://journal.kci.go.kr/jksci

BACK
TOP

Home > Explore Content > All Issues > Article View

16 of 27

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

배성일 ¹, Kim, Minsu ¹

¹홍익대학교

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

Statistics

175 Viewed

12 Downloaded

Tools

Print this page

Download PDF

Export Citation

Sharing

Facebook

Twitter

Issue List

Vol.27 No.7

Vol.27 No.6

Vol.27 No.5

Citation status

KCI Citation Counts (1)
열림/닫힘 버튼
REFERENCES (12)
열림/닫힘 버튼
* 2021년 이후 발행 논문의 참고문헌은 현재 구축 중입니다.

[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