Q&A
私も英語は得意ではないのですが、マニュアルのpdfを見ると、ほとんどが数学用語ですが、Collision(衝突)、Birthday(誕生日)といった用語もありました。
もしCollisionを「衝突攻撃」、Birthdayを「誕生日攻撃」に関連するものと解釈するなら、BigCrushは暗号に何かしら関連している検定かもしれません。
※BigCrushがTestU01に関連しているということは知っていたので、質問に加えておきます
※どのようなタグをつければいいかわからなかったので、表題の「BigCrush」がC言語で実装されていることから「C」「C++」をつけさせていただきました。
BigCrushという検定
BigCrush、という乱数生成器のための検定があり、XORSHIFT-ADD(XSadd)やPermuted congruential generator(線形合同法を改良した乱数生成器)が合格し、多くの分野で使われるMersenne Twisterは合格できないと聞きます。
BigCrushは、TestU01というライブラリに含まれる検定の1つで、これに合格することは乱数生成器にとって1つのステータスとなるようです。
知りたいこと
- BigCrushとはそもそもどんなテストをするのか？
- BigCrushに合格した乱数生成器を使うメリットは？(Wikipediaを読みましたが、どのようなメリットがあるか書かれていませんでした)
- BigCrushに合格していないMersenne Twister、この乱数生成器を使うデメリットは？
回答2件
0
ベストアンサー
BigCrushはTestU01にある統計的乱数の検定バッテリーのうちの１つで、他にもSmallCrushとCrushがあり、精度と計算時間に応じて好きなバッテリーを選んで使えるようになっています。BigCrushが一番厳しい検定でもって検定していて、計算も時間がかかります。TestU01自体はMarsagliaのdiehard検定などを乱数の専門家でなくても利用しやすい形にしたライブラリです。
- TestU01のBigCrushがどのような検定をするのかは、ユーザガイドに書かれています。それぞれの検定の中身は統計的仮説検定や確率論、情報理論の知識がないと正確に把握できないと思います。
- TestU01のBigCrushをパスした乱数生成法はその意味でもってまともな乱数が作れるということです。TestU01のBigCrushをパスしたからといってパスしていないものより絶対良いと言う保証はありませんが、参考にはなります。
- どの種類のMersenne TwisterがTestU01のBigCrushにパスする・しないのかは知りませんが、もし、Mersenne Twisterよりも速く、BigCrushをパスする乱数生成法があるなら、BigCrushを指標とする意味でMersenne Twisterより使い勝手が良いと言えます。しかし、BigCrushではチェックできない乱数の性質も数多くあるので、BigCrushをパスしたからといって飛びつくのは危険だと思います。そもそもこういう検定のセットは特定の乱数生成方法を合格するように作ることができてしまうので、気をつけなければいけません。BigCrushが公平だと思うなら、信じれば良いと思います。
ちなみにMarsagliaのbirthday spacings testは誕生日攻撃と関係性がないわけではないですが、統計的に見て乱数であるかどうかの統計的検定であって、乱数の暗号的な安全性とは関係ないです。とりあえずモンテカルロ法使いまくりますとかでないかぎり、Mersenne Twisterかxorshift128+かxoshiro256**などを現時点では使えば良いと思います。
Mersenne twisterからxorshift128+に変えた例: https://v8.dev/blog/math-random
ほかにもO'NeilのPCGなどがありますが、論文の形になっておらず、専門家による評価が作者以外のものがあまりないので、自分で判断できない身としては、なんとも言えません。実用上で使用している人もいるようです。その辺の事情をブログに上げている研究者もいるようです。
https://lemire.me/blog/2017/08/15/on-melissa-oneills-pcg-random-number-generator/
と思いましたがxorshift128+が検定を通らない話は最近論文にしたようですね。
https://arxiv.org/abs/1810.05313
投稿2018/11/03 00:18
編集2018/11/03 00:20
総合スコア232
英語が読めないと何かを調べる範囲が極端に狭まります。
難しい質問や検索結果も出ないような質問なら尚更です。
自力で検索した英文の情報を自動翻訳を駆使して独習するスキルが肝要になるでしょうね。
（私も英語は苦手なので苦労しています）
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/11/16 13:48