Modulo(%)を使用すると乱数の品質に影響しますか?
暗号化や乱数生成において、modulo(%)演算を使用して数値の範囲を制限する場合、生成される乱数の品質が低下する可能性があるかどうかを考察した議論。特に、元の乱数が一様分布であっても、modulo操作によってバイアスが生じるケース(例えば、範囲が割り切れない場合)について解説している。
背景メモ
- これは暗号理論のQ&Aサイトでの質問で、プログラマが疑似乱数生成の際に剰余演算(%)を使って範囲を絞る(例えばrand()%n)と、乱数の品質(均等分布)が損なわれるかどうかを尋ねている。
- 背景にあるのは、多くの言語標準ライブラリのrand()が一様分布(各値が等確率で出現)を保証しているが、nがRAND_MAXを割り切らない場合、剰余法では一部の値が他よりわずかに多く出現する「モジュロバイアス」が生じるという既知の問題。
- 暗号用途ではこの偏りがセキュリティホールになりうるため、付属の回答では「暗号的には使うな」「棄却サンプリング(範囲外の値が出たら取り直す)を使え」といった実務的な対処法が解説されている。
- 質問者・回答者はStack Exchangeコミュニティのユーザーで、特定の有名人ではなく、この問題は暗号エンジニアやセキュアコーディングに関わる開発者の間で広く共有されている知識。