$\Pr[collision]$ is negligible in $n$
三日唸ってようやく思いついたので, やっと確率の評価が出来た. Impagliazzo and Zuckerman ``How to recycle random bits'' (FOCS '89) *1にRegularity Lemmaが載っているのでそれを使って何とか既存の証明を参考にしながらやりくり. 向こうの証明に難しいところは全部押し付けて初等的に証明した. 後は延々とパラメータの設定か, だるい.
そういえば, [IZ]の4章にLeftover Hash Lemmaという章があって, The following lemma is a somewhat stronger and cleaner version of a lemmn in [ILL]; the strengthenned version and proof found here are due to Rackoff [R]
となってLeftover Hash Lemmaが示されている. 初出がImpagliazzo, Levin, and Luby ``Pseudo-random generation from one-way functions'' (STOC '89)で, ちょい強めのヴァージョンがImpagliazzo and Zuckermanということか. で, そのときに[R]の結果を使ってると. 参考文献見ると[R]ってRabin ``Probabilistic algorithm for testing primality'' (J. of Number Theory 1980)なんだけど, これ間違いかよ. 誰か突っ込めよ(;´Д｀)
昔, Leftover Hash Lemmaを探していた自分を思い出し, 誰かが検索してくることも考えて記録しておく. V. Shoupの``A Computational Introduction to Number Theory and Algebra'' (isbn:0521851548) にも載ってる筈 (Victor Shoup: A Computational Introduction to Number Theory and Algebraからダウンロード出来るpdfは本と同じらしいので)
追記: IntroductionにRabinの素数判定法が確率的アルゴリズムの例として挙げられていた. Rackoffの方が引かれてないのか.
