- 1 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:19:35 ]
- 擬似乱数発生器について語ろうか。
- 159 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 00:26:39 ]
- >>157
その「まともな暗号」を考えるのがﾑﾂｶｼｲ
- 160 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 10:58:08 ]
- >>159
154で書いた通り、前提として、AESやtwofishを想定していますけれど。
暗号の世界の死屍累々の歴史を見れば、よほどでなければ俺様暗号を作ろうなんて傲慢な気持ちにはなれないですよね。
AES 選考のときも、ドイツテレコムが採用していた暗号が 10秒で即死したり、笑い話に事欠かない世界…怖いですね。
h2np.net/bit/aes-rep.html
- 161 名前：デフォルトの名無しさん mailto:sage [2006/06/01(木) 13:58:02 ]
- >>160
ﾊｧﾊｧ 読んでて興奮するね。
- 162 名前：デフォルトの名無しさん mailto:sage [2006/06/03(土) 04:14:33 ]
- >>160
ｶｺｲｲ!!
- 163 名前：デフォルトの名無しさん mailto:sage [2006/06/03(土) 05:16:05 ]
- >>160
最終的にAESに選ばれたのはそこで名前すら挙がっていなかったRijndaelだというのも
おもしろいな
- 164 名前：デフォルトの名無しさん [2006/06/05(月) 00:58:00 ]
- 高速な乱数の基本はシフトとXORを使うことらしいが
この二つってそんなに演算早いの？
加減算やローテートは遅い部類なの？
- 165 名前：デフォルトの名無しさん mailto:sage [2006/06/05(月) 01:32:04 ]
- シフトとローテイトはCPUレベルではそんな変わらんと思うが
加減算は変わりそう
- 166 名前：デフォルトの名無しさん mailto:sage [2006/06/05(月) 01:42:13 ]
- >>164
命令自体は別に変わらないよ。
M系列でググると分かるけど、
ある周期で全てのビットが0である場合を除いて、
全ての0と1の組み合わせが出現するアルゴリズムがある。
そんでそれはシフトとxorのみで実現する事が出来るというだけ。
これはなかなか自然的な乱数の性質に近くて、
しかもコンピューターに都合のいい形をしている。
で、よく使われる。
加減算やローテートでも実現出来るんじゃないかな。
ただ、周期を大きくするのが難しそうだ。
- 167 名前：デフォルトの名無しさん mailto:sage [2006/06/05(月) 01:53:02 ]
- Pen4なら加減算が倍速でローテートはアホみたく遅い。
使用する環境が決まってるならCPUに特化した乱数ルーチンもアリだと思う。
- 168 名前：デフォルトの名無しさん mailto:sage [2006/06/06(火) 17:33:17 ]
- >>167
そのために、RCなんとかコンテストで、PowerPC とかがクロックの割に健闘したりってことがあった気が。
そういえば、CPU自体が（熱雑音とかを使った？）乱数生成器を持っているやつって、あるのかな？
- 169 名前：デフォルトの名無しさん [2006/06/06(火) 22:10:12 ]
- >>168
ぐぐったら出てきた
ttp://journal.mycom.co.jp/news/2003/01/22/15.html
- 170 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 10:40:12 ]
- こんなのも。どうやって使うのか知らないけれども。
www.intel.co.jp/jp/intel/pr/press99/991116.htm
インテル 820 チップセットは〜インテル(R) ランダム・ナンバ・ジェネレータ（乱数生成器）を搭載しています。
- 171 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 20:49:19 ]
- メルセンヌ・ツイスタをSSE2で高速に計算する方法を思いついた！！
でも…… ワーキングメモリが2.5倍強ほど必要になってしまう…
ただでさえデカイと評判のMTがさらにでかく…
くそっ、SSEに128ビットアライメント縛りなんてものがなければ……
せめて64ビット縛りならいいのに
- 172 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 21:37:59 ]
- PCで使うなら気にするこたねぇだろ
組み込みで使うならともかく
- 173 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 21:46:05 ]
- そだね。
SSE2使おうってCPUならキャッシュで収まるもんね。
気兼ねせず実装することにしますわ。
でもアライメント縛りって本当に鬱陶しいな。スレ違い愚痴ｽﾏｿ
- 174 名前：デフォルトの名無しさん mailto:sage [2006/06/07(水) 23:20:13 ]
- ま、その前提で高速演算できますって機能だから仕方ない。
組み込み系だと日常茶飯事だけどｗ
- 175 名前：デフォルトの名無しさん [2006/06/11(日) 14:44:38 ]
- 「とってもごはん」のMMX版MTって、オリジナル版と出力違ってないか？
- 176 名前：デフォルトの名無しさん [2006/06/11(日) 16:49:37 ]
- >>171
うｐはdvi形式でおｋ
- 177 名前：デフォルトの名無しさん [2006/06/11(日) 17:06:53 ]
- >>175
オリジナルのMTも32bit版と64bit版で出力違うから気にしなくていいと思う
- 178 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 06:13:17 ]
- で、初期化がどーのこーのに難癖つけてた件は結局うやむやのうちに終了しちゃったの？
- 179 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 10:48:14 ]
-
そもそも何で乱数に初期化が必要なんだ？
種から生成するアプローチ以外の方法は無いのか？
- 180 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 16:50:29 ]
- MT-32よりCM-64の方が面白いよ
- 181 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 18:19:34 ]
- ローランド音源かよｗ
- 182 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 18:21:24 ]
- >>178
心配なら暗号論的乱数で初期化汁、そこまで気にしないならどうでもいい、でFA出ちゃったからね。
- 183 名前：デフォルトの名無しさん mailto:sage [2006/06/12(月) 18:57:12 ]
- 線形合同法で十分
場合によっては
- 184 名前：デフォルトの名無しさん mailto:sage [2006/06/13(火) 00:26:32 ]
- いけぬますれ
- 185 名前：デフォルトの名無しさん mailto:sage [2006/06/13(火) 00:48:08 ]
- >>184
そんなこと言ってないでなにか話題提供してくれよ
- 186 名前：デフォルトの名無しさん [2006/06/13(火) 03:09:15 ]
- 擬似乱数について素人ですが、教えて頂けないでしょうか？
(0,1)の擬似乱数をMT19937（作成者のHPからFortranソースを拾ってきた）で発生させて、
その平均値と標準偏差が0.5と0.25になるのを確認しようとしました。
（作者の作成したサンプルデータと同じ結果がでることを確認しました。）
平均値は0.5にかなり近づくんですが、標準偏差が0.28程度になります。
乱数の個数を増やしていくと、0.28程度で収束しているように見えます。
octave（実装されてる乱数生成器）でもやってみたんですが、0.25程度に収束しません。
よろしくお願いします。
- 187 名前：デフォルトの名無しさん mailto:sage [2006/06/13(火) 04:27:11 ]
- [0,1] の一様分布に従う擬似乱数の標準偏差が
1/sqrt(12) に収束するのは別に何もおかしいところが無いわけだが
乱数の話というよりか確率・統計の話だな
- 188 名前：デフォルトの名無しさん [2006/06/13(火) 13:49:37 ]
- 187さんへ
ありがとうございます。
たしかに、1/3-(1/2)**2でも0.288...になりました。
0.25と思い込んでいました。
- 189 名前：デフォルトの名無しさん mailto:sage [2006/06/14(水) 01:07:11 ]
- >>175
それ以前に、メルセンヌツイスタはBSDライセンスのはずなのに
ソースコード中にライセンスについて一切の記述がない事がまずいと思う。
SYN氏、忘れてんのか？
- 190 名前：デフォルトの名無しさん [2006/06/14(水) 01:13:54 ]
- そーいや乱数発生器のライセンスってどうなってるんだ。
AESはフリーなんだっけ？
- 191 名前：デフォルトの名無しさん mailto:sage [2006/06/14(水) 05:53:41 ]
- yes
- 192 名前：デフォルトの名無しさん mailto:sage [2006/06/14(水) 21:52:44 ]
- Rijndaelだけ？他のは？
- 193 名前：デフォルトの名無しさん mailto:sage [2006/06/15(木) 10:46:52 ]
- 自分で調べろ
- 194 名前：デフォルトの名無しさん [2006/07/08(土) 19:10:20 ]
- 量子論的乱数発生器ってある？
- 195 名前：デフォルトの名無しさん mailto:sage [2006/07/08(土) 22:27:59 ]
- Intelの最近のチップセットには内蔵されてるはず
- 196 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 02:16:37 ]
- 詳細規模んう
- 197 名前：デフォルトの名無しさん [2006/07/09(日) 08:39:00 ]
- なんでコンピュータは擬似乱数しか出せないの？
- 198 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 09:45:09 ]
- 真性乱数も出せるだろ、専用のハードウェアがあれば。
- 199 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 12:52:06 ]
- >>197
決定性チューリングマシンだから。
ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか？
- 200 名前：デフォルトの名無しさん [2006/07/09(日) 14:55:03 ]
- >>197
つ /dev/random
- 201 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 19:03:50 ]
- >>199
> ところで非決定性なら一様乱数が得られるアルゴリズムがあるのか？
真性乱数は無理。
というか、非決定性チューリングマシンができてしまうと、
今まで暗号論的擬似乱数と呼んでいたものの前提が全て崩れちまうな。
ttp://ja.wikipedia.org/wiki/%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0
- 202 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 01:33:58 ]
- >>201
えっと、そんなことはないです、オーダー的に。デタラメ言わないで。
- 203 名前：201 mailto:sage [2006/07/10(月) 02:36:50 ]
- >>202
え、なんでだ?
非決定性チューリングマシンとはNP完全な問題を多項式時間で解くマシン、
すなわち、単純な総当たりで解くしかない(=解くには指数時間かかる)と思われていた問題を
多項式時間で解いてしまうことのできるマシンであるから、
RC4などストリーム暗号で使われる暗号論的擬似乱数列も多項式時間で解けちゃうでしょ。
- 204 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 21:01:48 ]
- どうでもいいがWikipediaを参考文献として引き合いに出すのは勘弁してくれｗ
俺が書いた文章だったりするからｗｗｗ
- 205 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 21:13:30 ]
- >>204
嘘書いたの？
- 206 名前：デフォルトの名無しさん mailto:sage [2006/07/11(火) 06:52:21 ]
- 自分の使ってる狭い専門用語を広めるのには便利かもしれないな。
- 207 名前：デフォルトの名無しさん mailto:sage [2006/07/11(火) 13:35:06 ]
- >>109の方法をやってみたら
どの乱数列データもまったく圧縮できないorz
- 208 名前：デフォルトの名無しさん mailto:sage [2006/07/11(火) 18:56:18 ]
- >>205
いやそういう意味じゃないが、非常に照れくさい……
- 209 名前：デフォルトの名無しさん [2006/07/19(水) 03:02:36 ]
- ま、素人はそう考えるわな。
- 210 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 03:07:16 ]
- 間違ってるけど
- 211 名前：デフォルトの名無しさん [2006/07/19(水) 12:52:58 ]
- 一様な乱数のお薦めを見繕ってくれ
- 212 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 13:08:01 ]
- MT
- 213 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 18:00:52 ]
- C99のrand()関数は「ラグ付きフィボナッチ」だと聞いたけど、
どんなアルゴリズムなの？
- 214 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 18:12:33 ]
- アルゴリズムまで規定してたっけ？？＜C99
- 215 名前：デフォルトの名無しさん mailto:sage [2006/07/19(水) 20:30:32 ]
- x_i = a * x_(i-p) + b * x_(i-q) (mod M)
狭義のlagged Fibonacciだとa = b = 1.
- 216 名前：デフォルトの名無しさん [2006/08/26(土) 01:43:17 ]
- 線形合同法と似てない？
- 217 名前：デフォルトの名無しさん [2006/10/08(日) 06:58:26 ]
- >>211
一様では乱数とは言わない。
特定の周波数幅に対するホワイトノイズ乱数というのなら可能。
この場合は特徴があるが、目的に使う限り特徴は現れにくい。
- 218 名前：デフォルトの名無しさん mailto:sage [2006/10/08(日) 07:16:59 ]
- >>217
フィルタ使わずそんなもん発生する事できるのか
是非教えてくれ
- 219 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 18:00:37 ]
- ちょークロックの早いPCM合成チップで生成
- 220 名前：デフォルトの名無しさん [2006/10/09(月) 18:54:49 ]
- ブラム・ブラム・シャブって乱度高そうだな
シャブ打ってラリってそうな響きだ
- 221 名前：デフォルトの名無しさん [2006/10/09(月) 23:00:54 ]
- >>218
例えば想像する対象をサイコロの目としてみる。
１から６まで均等にでる乱数なら可能だろ
その種類だけ格納するテーブルを作って
確立が高い部分か低い部分を再度乱数を求め補正するだけ
原始的な方法で昔から使われている。
記憶容量に依存するが、多重評価することで要求に対するバランスが測定
可能であれば、それを元に補正するだけでいい。
この方法だと周期はでるが、結果として分かっている周期を補正するのは
容易だろう。
任意の偏りがでるかスペクトルを測定し再評価すればいいだけの話だね。
- 222 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 00:38:32 ]
- 統計を取って補正すると、乱数じゃなくなるけど？
時系列で見ると偏ってるからね。
- 223 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 00:45:37 ]
- もともと偏った確率で目が出る疑似乱数に、統計情報を加えて一様乱数にしようとすると、必ず波が出来るよ。
パチンコやスロット台で波が出来るのもこのせい。
- 224 名前：デフォルトの名無しさん [2006/10/10(火) 01:20:57 ]
- >>222
１０年間同じ値が続いても乱数。無限に長い時間からすれば確率的には存在する。
そのぐらい理解しておけ
- 225 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 01:23:04 ]
- >>223
元の擬似乱数にある偏りが表にでただけで偏りがすくないものなら
測定できるような波はでない。
それに波がでたとしてもそれをフィードバックさせるだけで補正は可能。
- 226 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 01:25:25 ]
- まあ、224と225が別人で、まったく逆の方向を指してるのだけはわかった。
- 227 名前：222 mailto:sage [2006/10/10(火) 01:39:12 ]
- >>224
統計を取って補正しちゃうと、それが不可能になるって言ってるんだけど？
- 228 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 19:31:09 ]
- バカな俺に「一様では乱数とは言わない」の意味を教えて下さい。
一様乱数は一様ではないの？
- 229 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 19:40:53 ]
- ja.wikipedia.org/wiki/%E4%B9%B1%E6%95%B0%E5%88%97
- 230 名前：デフォルトの名無しさん [2006/10/10(火) 23:18:00 ]
- 一応乱数
- 231 名前：デフォルトの名無しさん mailto:age [2006/10/13(金) 14:21:51 ]
- >>228
一様だと周期があるということになるのは理解できない？
一様乱数とは有限の範囲内では周期がないが、それ以上だと
周期がある乱数を言う。
>>224
それは自然乱数の本質だな
>>225
これは正規乱数の類だな。上のwikiに解説してあるからしっかり読んでおけ。
- 232 名前：228 mailto:sage [2006/10/13(金) 17:44:49 ]
- >>231
>一様だと周期があるということになるのは理解できない？
はい。
「一様であること」とは「偏りがないこと」と理解しています。なので、
>それ以上だと
>周期がある乱数を言う。
「一様であること」と「周期があること」の関係が解らないでいるのです。
- 233 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 01:15:08 ]
- 数学出来なそうなニオイ…
- 234 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 02:45:28 ]
- 横レスで済まんが、俺もわからないんで、デキるあなたが解説してよ>>233
暗号と情報セキュリティのお勉強はしたけど、正直乱数はよくわからん
- 235 名前：デフォルトの名無しさん [2006/10/14(土) 03:09:53 ]
- >>231が何言ってるのかは全く不明だけど、
特定の有限回の試行での一様性が担保されているなら、
それは全く乱数ではない、というのは自明だと思う。
ところで、疑似乱数は内部状態を有限量のデジタルデータで
持つという仕組み上、有限の周期をもつこともまた自明。
なわけで、一様な疑似乱数＝乱数ではない、ということになる。
のか？
一様だろうがそうでなかろうが、所詮周期があるという点で
「疑似」乱数でしかないわけだけど、一様性が担保されている
場合は、そうでない（一様かどうか不明な）場合と違って、
周期の終わりの方では次にでる数字を推定しやすくなる。
ギャンブルには使いにくい。
- 236 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 08:34:34 ]
- 普通のrandじゃいけない理由は？
- 237 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 09:57:42 ]
- >>236 その「理由」を君が知りたい理由は？
- 238 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 10:04:34 ]
- >>237日本語でおｋ
- 239 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 13:11:10 ]
- ところで、
ttp://www.optoscience.com/maker/id/id.html
の真性乱数発生器ってのはホンモノなの？
熱雑音を利用したチップやボードはよく見かけるけど、
量子乱数ってのはあまり見かけないような気がするッス
どういう仕組みになってるんだろうか…
- 240 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 13:58:00 ]
- 周期が終わったら初期化すればいいじゃない
- 241 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 14:48:04 ]
- >>236
いまどき普通のrandを使う理由は？
- 242 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 14:50:22 ]
- >>241
いまどきじゃないrandが存在する理由は？
- 243 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 17:37:21 ]
- >>242
いまどきじゃない方が便利だから
- 244 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 17:40:53 ]
- 便利かどうかで言えば、便利さは「同じ」だと思うな。
重要なのは、目的を達成するための手段として妥当かどうかだよ。
- 245 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:00:51 ]
- 少なくとも理不尽さを軽減する効果はある。
ユーザ「なんでここで○○が出て来るんだよ！ありえないだろ！！！」
開発者「MTですから、乱数に変な癖は無いですよ」
ユーザ「そうか・・・偶然じゃあしょうがないな・・・」
みたいな。
- 246 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:20:35 ]
- Civシリーズの乱数FAQを思い出すナー
- 247 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:36:06 ]
- メルセンヌ・ツイスタのホームページが存在しないんだけど
作者はもう慶応には居ないってこと？
- 248 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 23:45:00 ]
- >>247
普通に"MT 乱数"とかでググれば出てくると思うが
- 249 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 10:22:55 ]
- civの乱数には波がある
- 250 名前：デフォルトの名無しさん [2006/10/16(月) 12:05:45 ]
- すいません、昭和初期の国産バスの図面を探しているのですが、
適当な資料をご存じの方がいたら教えてください。
- 251 名前：228 mailto:sage [2006/10/16(月) 15:19:19 ]
- >>235
>一様性が担保されているなら
…あ、そうか。やっぱ俺はバカでした。
ありがとうございます。ひとつ賢くなりました。
- 252 名前：デフォルトの名無しさん mailto:age [2006/10/18(水) 17:36:16 ]
- >>251
本物？釣り氏？ｗ
- 253 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 18:18:59 ]
- 一様性が担保されていても、長ーい周期の疑似乱数の最初の方だけ
使うんならあまり問題にならないような気がする。
40万組みのシャフルしたトランプから10枚だけ引くとか。
- 254 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 20:06:33 ]
- ここまでの俺の理解：
（１）周期があるというのは、別に一様にしようがしまいが疑似乱数である限り言えること
（２）一様乱数の場合は、そうでない疑似乱数と比べて
周期の終わりに近づくにつれてさらに予測しやすくなる
（３）>>231が前半二行で（１）以外の情報を伝えたかったのかどうかは不明
- 255 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 23:53:23 ]
- 一様乱数の意味を勘違いしてる人が多いな。
(正しく作られた)サイコロは過去の出目に関係なく、次にある数字が出る
確率はすべて等しい。＝ 一様である。
サイコロを続けて振って得られる数列は一様乱数になる。
ソフトウエアで生成する乱数が原理的に真性乱数になり得ないのは
まったく別の話。一様性とは無関係。
- 256 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 03:41:58 ]
- なるほど、その勘違いした人が大声で解説すると。
悪貨が良貨を駆逐するとはこのことか。
- 257 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 04:10:57 ]
- >>255
やっぱそうなのか
上の話を読んで
「サイコロを６回ふったら、１から６までの目がどれもぴったり１回出る」
が一様乱数かと思って焦ったよ
- 258 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 11:45:46 ]
- >>255
疑似乱数の場合、
＞確率はすべて等しい。＝ 一様である。
ものと、そうでないものがある、というのはわかっていますか？
- 259 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 12:08:06 ]
- なんでこう自分の言いたい内容を明確に書かない臆病者が多いんだろうね？
ム板の特徴なのかな
|
 |
