본문 바로가기
  • Home

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 : Engineering > Computer Science

배성일 1 Kim, Minsu 1

1홍익대학교

Accredited

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.

Citation status

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