擬似乱数ジェネレータの効率化に関する一考察

山本 博章  

誌名
電子情報通信学会論文誌 D   Vol.J73-D1   No.3   pp.358-365
発行日: 1990/03/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 情報セキュリティ
キーワード: 


本文: PDF(572.6KB)
>>論文を購入


あらまし: 
今,有限集合上の各要素を適当な確率で出力する物理源を考える.本論文では,このような物理源の出力を入力として,その有限集合上の各要素を等確率で出力するジェネレータの効率さについて議論する.ここでいう効率さとは,等確率な出力を得るために必要な入力の数で測る.従って,入力数が少ないほど効率がよいとみる.従来のジェネレータはω((logn)2)個の入力に対し1出力であった(但し,集合の要素数が2の場合は)ω(logn)個の入力に対し1出力である).ここでは,集合の要素数が2以上の場合に対しても,ω(logn)個の入力に対し1出力するより効率的なジェネレータを与える.