乱数について

Cの標準ライブラリのrand()では、seedが同じなら
発生する乱数系列も同じになってしまいますよね？
完全な(？)乱数を発生させるにはどうしたらいいんでしょうか？
time()と%演算子を利用するしか思い付きません。

>完全な(？)乱数を発生させるにはどうしたらいいんでしょうか？

無理です。

go to 初心者板

早いレスありがとうございます。
了解しました。
＞2,3

ハード的に実現してるのがありますよね。
熱雑音拾ってそれを種にしてるの

Win32なら::GetProcessTimes()の結果を
めるせんぬついすたーに仕込む．

時間を種にするんだよ。
unsigned long seed;
time_t t;
time(&t);
seed = t;

んで、あとは
unsigned long rnd()
{
return seed *= 69069;
}
とかすれば良し。
69069という値には意味があるので、適当な値ではダメ。

あと::GetTickCount()も追加しておこう．

time()は1も考え付いてるよーで。

time()だと同時に複数走らせたらかぶるじゃん．

ムカーシ読んだ技術書で
放射線源とガイガーカウンタ組み合わせた
乱数発生器の解説を読んだ気がするんだけど、、、
ルディーラッカーとかのＳＦ小説と混同してるかもしれない

昔の三国志みたくHit space key.

Pen4とかには乱数発生器が付いてるそうだけど
これは使われてるの？

>7
seedが偶数なら常に偶数（奇数も同様）にしかならないが、
そういうのも乱数と呼ぶのか？

時刻とか熱雑音使っちゃうと、乱数の再現性がなくなっちゃうよね。

＞15
乱数の再現性ってなんじゃい？

アホ発見>16

>>11
”ソフトウエア”ですな。♪ビーバッパルーラ〜

ゲームなんかのときはシードも保存してるけど

Rレジスタの値をつかえ

　int c1, c2;
　int a, b;
　c1 = GetTickCount();
　a = 0;
　for( b=0; b<100000; b++){
　　a += 400;
　　a /= 3;
　　/* ていうか，このあたりは適当に... */
　}
　c2 = GetTickCount();
　printf("%d\n", c2-c1 );

これ，わりと値がバラけるんですよね。
私の環境（Pentium200MHz）では 27〜111 くらいでバラバラに。
・・やっぱし邪道っす？

ファイアーエムブレム(聖戦の系譜以降)なんかは擬似乱数の性質を逆に利用して
リセットして同じことを繰り返しても結果はおなじなんてシステムにしてた。

>10
プロセスID(のたぐい)を足すべし。

>>10
staticで使え。まぁ、同じタイミングで２アプリ起動されたらアウトだけどネ。
そのへんはユーザーの入力使ったり。＜この辺がボロっぷり暴露してんな、俺。
>>23
ナイス。そうしてｐｌｚ。

>>14
まぁ0〜((2^32)-1)の値が欲しい場合はまずいだろうが、
通常は定数で割って上部のビットを使用するから、問題ナシ。

>>24
自分は擬似乱数サーバクラスをSingletonで作って
コンストラクタでGetTickCount(), Time()で初期化するってのを
やってるよ．

おっしゃるとおりスレッドハンドル辺りを足すぐらいでいい鴨．

Mersenne Twister
ttp://www1.odn.ne.jp/synsyr/mt.html

↑がいしゅつだし、原典のほうを書こうよ。
でもGCAはお世話になってます。

乱数について:7

623次元に均等だとかはどうでもいいのですが、再現性や規則性のない
seedを作る方法が知りたいです、、、age

>>29
完全な乱数なんてないよ。
周期が長いのとか、いろいろのってるので、アルゴリズム辞典を見たら？

周期がいくら長くても、種から結果が推測できては、パスワード生成など
には使えないですよね。
time() だと同じ秒で実行すると同じ結果になるし、getpid() でも所詮
何万種類のパターンしかできません。
熱雑音とかマニアックな方法じゃなくて、もっと手軽で実用的な乱数生成
の仕方はないのでしょうか。

今のところ思い付くのは、パケットの送受信にかかる時間とか、
WWWサーバのログの大きさとかなんですけど。

>>31
あの〜、再現性がないと暗号を復元できないと思うんですが。
大丈夫ですか？
アルゴリズム辞典のやり方でも２の５４乗通りのパターンができるやつ
が載っているので、そっち応用してください。

暗号の話ではなくて、単に推測しづらいパスワードを作りたいだけなんです（泣
生成したパスワードはどっかに保存しておく所存です。

ユーザの入力を種にすれば、UNIXの crypt とかでもよいのでしょうが、
ユーザの入力に頼らずに種を作りたいのです。

>>32
統計的に大きく偏ると思われ。
数学的に解決した方が良いかと。

>>35
マウスカーソルの位置も取得して計算するとか
時間＋pid＋位置＋・・・すべて一致するのはあまりないとおもう

WindowsならCoCreateGuid をタネにしたら

じゃ これでどう？

#include<stdio.h>
#include<windows.h>

static WORD randbuf[16]; // 256bit
WORD rand16(void)
{　　// p=55 τ=127-7=120
static WORD　rw=7;　　　　　　　
　 WORD　topb　=randbuf[rw　];
　 WORD　nw=(rw+8-1) & 7;
　 WORD　nextb =randbuf[nw　];
　　topb　= (topb<<8)|( nextb>>(16-8) );
　　topb^=nextb;
　　randbuf[rw]=　topb ;
　　　　　　rw = nw;
return　topb^ randbuf[rw+8];
}
void rand32Init(void) { CoCreateGuid((GUID *)randbuf);}

int charc(WORD c)
{　WORD a='Z'-'A'+1;
c %= a+10;
if(c>=a) return '0'+c-a;
　return 'A'+c;
}

int main()
{
int i;
rand32Init();
for(i=0;i<100;i++) rand16();//シャッフルする
for(i=0;i<16;i++)

　printf("%c",charc(rand16() )) ;
　printf("\n");
return;
}

あれ？
topb　= (topb<<8)|( nextb>>(16-8) );
は
topb = (topb<<(15))|( nextb>>(16-1) );

かな？　まあいいや、無理にM系列にするより
何かワラらない系列の方が解析しにくいかもね

>>38-40
ありがとうございます。
厚かましいようですが、UNIX上でやる方法も知りたいです。
作成したプログラムのソースを配布すると、パスワードを生成するアルゴリズム
は周知になると思いますが、それに基づいて生成されたパスワードは予測できない
ようにしたいのです。

麻衣はウニックスの事は知らないもん

でも、ようは WORD は 符号無し16bitで定義する事と
rand32initで 256bit分出鱈目な値で埋めるればOK
時計の他に、NICのアドレスとか、CPUのカウンタとかIDとか
思いつくもの全部使えばいい。


最初１００回ループしてる個所を固定回数じゃなくて　別の適当な
プロセスを走らせてそのプロセスが帰ってくる迄とか適当にばらつ
くような回数に変更すれば完璧かな

>>41
DESとかビット列がばらけるので予測が困難だと聞きましたが、違うのでしょうか？
そんなに予測不可能にしたいというなら、
DESの三重使用とか、複数の暗号を組み合わせて使うというのではまずいのでしょうか。

※素人考えですいません。

言いたい事は、

時計とか本人の名前とかを　暗号化すりゃいいんじゃないの？

という事かい？
　そりゃそうだ

そりゃそうだけど、この場合復号しなくていいから
より問題は単純だ

{0,1,2,3,4,5,6,7,8,9}も、
{1,1,1,1,1,1,1,1,1,1}も、
「これは乱数だ」と言い張れば乱数です。

CPUはたまに計算を間違える事があるから
それを利用するってのはどうだろう
まずCPUを熱暴走ギリギリにして・・・

unixでなら /dev/random を乱数発生器として使えるものが
あるようです。全部で使えるとは思わないけど

１、適当にpingを送って　応答が帰って来るまでの時間
２、ウエーブデバイスがあれば 16bit精度で入力してみる
　　マルチメディアタイマは水晶が別なので、CPU側で時間を計る
３、アナログジョイステックデバイスがあれば　現在のCRの値
４、別のプロセスでファイルの入出力（HD/FDに）をさせ
　　て、その処理にかかる時間を測定する

を全部試して非常に大きなタネを作ればいい

ランダムな外部入力(キー入力、マウスクリックなど)
をいろいろ集めてmd5でハッシュして作り出せ
ってゆーか、gnupgやopensslや
unixの/dev/randomのソース見ろヴぉけ

なんか、乱数と疑似乱数の区別ついてないやつ多いね
ちなみに、linuxの/dev/randomのソースコードは、
http://lsd.linux.cz/LSD.cgi?Version=2.4.0-test10&Arch=i386&File=drivers/char/random.c
opensslはこのあたり
http://www.jp.freebsd.org/cgi/cvsweb.cgi/src/crypto/openssl/
からたどってくれ

http://www.gnupg.org/
http://www.openssl.org

DES暗号は政府レベルなら無理矢理解読可能だそうです。
http://www.genpaku.org/crackdes/cracking-desj.html

このスレの話では、そこまで高度のセキュリティが必要でないようですが。

ありがとうございます > all
/dev/urandom ってのをつかってできました。（Linux）

/* #include は省略 */
#define MY_RAND_BYTES 3
#define MY_RAND_MAX 256 * 256 * 256

int myrand(int max){
　int fd, val, i;
　unsigned char c;
　assert(max > 0 && max <= MY_RAND_MAX);
　if((fd = open("/dev/urandom", O_RDONLY)) == -1) return -1;
　val = 0;
　for(i = 0; i < MY_RAND_BYTES; i++){
　　if(read(fd, &c, 1) != 1) return -1;
　　val = val * 256 + c;
　}
　close(fd);
　return val % max;
}

あ、
return val % max;
でなくて、
return val % max + 1;
の方がよい気がします。

>>53
/dev/urandomは、速いけど、乱数の精度があまり高くない時もある
暗号に使う場合は/dev/randomつかってね
げーむくらいならどっちでもいいけど

しかし、/dev/random の方は「エントロピープール」とやらが無くなると（すぐ無くなるけど）、
read がブロックする問題が、、、。
もちろん、真の乱数を種にして後は疑似乱数を使うことで乱数発生器の利用回数を減らすこと
はできますけど、ブロックする可能性は消せませんよね。

http://www-6.ibm.com/jp/developerworks/security/000908/j_randomsoft.html
ここにlinuxの/dev/randomの詳しい話しがのってるよ

http://www-6.ibm.com/jp/developerworks/security/000818/j_playing.html
ここには、random()がいかにいいかげんかのってます

/dev/random がない場合はどうすればいいの？

真の乱数といっても３２ビットや１２８ビットじゃないんですか？

有限状態オートマトンであるコンピュータに数学的な真の乱数なんて無理だろ
やっぱ放射性元素とガイガー計数管だな

＞コンピュータに数学的な真の乱数なんて無理だろ
全く持ってその通り。がここでは工学的な話をしてるような気もする。

>>58

>完全に決定論的なマシンであるコンピューターは、 特に変則的な動作は苦手です (欠>陥 OS ソフトウェアの場合を除く)。

うまい！


>>62 たとえば周期がいくつ以上なら「真の乱数」としてみとめられるん？
JIS,ISOあたりに規格でもあるとか？
(暗号関係であってもいいような気もする)

>>64
やっぱ使用目的のシステムによるってコトで、

>>64
周期がある乱数は、疑似乱数といって、まともな暗号にはふつう使いません
だから、/dev/randomがあるのれす

>>65-66
有限状態オートマトンは周期をもたない数列を生成することはできないんだってば
(厳密に言えばどんなスゴイ暗号ソフトが使ってるのも疑似乱数？)
ただコンピュータに実装されているメモリ量からすれば内部状態の数も
超天文学的数字になるし事実上周期がない数列が作れるとみなしてもいいんだろうけど。
でもＣのrand()とか手抜きもいくらでもできるわけで
乱数の品質を計るなんかの基準があってもおかしくはなような気がしたんだ。

>>67
ﾊｧ? どんなに周期が大きくても、ある値から次の値が予測できるようでは、
少なくとも暗号用としては使いものにならないんだって。
だから/dev/randomやらPGPやらは、ちゃんとした乱数発生器(≒人間)を
使ってるんだろ。

ハード的な乱数ってぇと、Z80のRレジスタ使ってたのを思い出すなぁ…

/dev/randomってのは典型的にはどう実装されてるのか
教えてください。
nearly eq to 人間ってことは
バッチ処理マシンでは使えないってこと？

MT（メルセンヌ＝ツイスター）法とかいうのが現在最強って聞いたけど

>>70
linuxの場合、簡単に言うと、キー入力、マウス入力、割り込み、
ブロックデバイスアクセスなどのタイミング情報を集めて、
かき混ぜて出来上がり。詳しくはソース読め。

>>70
ここよめ！！
http://www-6.ibm.com/jp/developerworks/security/000908/j_randomsoft.html
http://lsd.linux.cz/LSD.cgi?Version=2.4.0-test10&Arch=i386&File=drivers/char/random.c

なぜか全部表示されないから、こっち
http://lsd.linux.cz/LSD.cgi?Version=2.4.0-test1&Arch=i386&File=drivers/char/random.c

http://www.ntl.co.jp/randommaster.html

そいえば、うちのジョイバッドってテストすると
いつも数値が揺らいでるけど、あれうまく使えないかな

これは有効なのか？
http://salad.2ch.net/test/read.cgi?bbs=hard&key=983544620&st=428&to=428&nofirst=true
上手くいけば常時まともな乱数が得られて助かるが

よく判らんけど、CDROMのデータをそのまま読んでもノイズじゃないでしょ
それとも音声としてサウンドカードを通して読むという事？
なら、単純にマイク音量を思いっきりあげてノイズをヒラッタ方がいいと思うけど
ホワイトじゃなくてピンクがかっただと思うし、当然電源周波数とか色々入ると思うけど
適応フィルタで取り除けば緩和はすると思う

>>78
試してみます

これは全部内部世界に正解を求めるからだね。
正解はhttp://www.2ch.net/2ch.htmlを読み込んで、
文字を全部足した物を種にする。

STLのアルゴリズムのrandom_shuffleで、独自の乱数生成関数を指定できますが
何か良い乱数生成関数を教えてください。

Mersenne Twister
http://www.math.keio.ac.jp/~matumoto/mt.html

>>80
時間かかっていいなら正しいアプローチかもねぇ。
使いどころが考えにくいけど。バレるし。

>>82
81じゃないけど
いいところ教えてくれてさんくす
GFSR だから M-Sequence と同じで判りやすいね

AESって、なんかNSA用の抜け穴ありそうだ

>>67
周期性を持たない、というだけなら可能じゃないの？
たとえば
1,1,0,1,0,0,1,0,0,0,1,0,0,0,0,...
とか。まあ、この数列でも、「0の数」を示す変数がwrap round
しちゃったら周期的になるけど。

ユーザーが多い端末だったり、WWWサーバだったりしたら、
ps auxwww とかやってそれを種にするとか。
自分専用端末とかだとあんまり意味ないかも。

>>82
Mersenne Twisterなんですが、

>松本-西村はMTを販売用プログラムにも自由に使っていただこうと決めました。そのため、GNU Public Licenseよりも条件のゆるい"Artistic License" の元に配布するコード mt19937.tar を用意致しました。

となってるんですが、Artistic Licenseってどんなのですか？
アーカイブ展開して出てきたライセンス条項読んでみたけど英文なんでよくわかんなかったです。

>>53
下位ビットの方は乱数として不適切だからあまりをつかうのは良くない

と、どっかの本で読んだよ。今はどうか知らないけど

>>89 線形合同法はそ。あげ

>>1

私も同じようなこと考えています。
コンピューターで質の良い乱数を出すにはどうしたらいいか。

コンピュータは、一定以上乱数を出し続けると内部タイマーがリセットされ
同じ乱数がでてくるようになるみたいなんんです。

実験でのデータで大量の乱数を使いたいのですがが、完全にバラバラで、
長時間出力しつづけてもループしない乱数を出せないものでしょうか。

コンピュータでは無理なんかなぁ

>>91

コンピュータでは云々言う前に、数学の問題ってことをわかってください。
現在のところ、完全にランダムな数を生み出しつづける数式が見つかって
いないので、「計算機」であるコンピュータでは完全にランダムな数を生
み出しつづけるプログラムは作れない。

乱数っぽいものなら計算式で書けるようになってきたので、それでどうに
かコンピュータ上で乱数っぽいものを作れるようになってきた。
それが今まで出てきた線形合同法なりMT法なりです。
完全な乱数を生める計算式を作れたら多分ノーベル賞取れます。

実験のデータとかで使うならMT法がいいと思います。
>>82あたりで出てます。
この擬似乱数は非常に周期が長いため、実験とかで使うぶんには
問題ないのではないでしょうか。

>>91
ありがとうございます。
ＭＴ法について勉強してみます。
明日からやることが見つかりました！

ごめんなさい、上のは
>>92
の間違いです。

円周率って乱数じゃない？
循環しない小数は乱数に使えるかな

>>95
使えると思うが計算コストが凄そうな……

3.141592653589793238462643383279502884967

めるせんぬついすたぁ で十分すぎ

πが循環しないことを証明せよ

>>99
いまのところ循環してないからいいんじゃない？

>>99
無理数であることより自明。

なんか、るーぷしてるぞ〜、みんなかこログよめ〜
乱数が出せないはずのコンピュータで乱数を出すために、
/dev/randomや、PGPはいろいろな小技をつかってるってことで

rand

どなたかが公開してた0-255限定の乱数発生器、結構役に立ちました。
ありがとう。

適当な大きさのファイルを作ってCRCをとり、
その結果や、時間等によって、ファイルを一文字ずつ書きかえるとか…。

それなら線形合同法でもいいじゃん

>>106
一応、まだ出てない案(よね…（＾＾；)で、
時間や、その他条件に関わらず、
毎回得られる結果を変えようとしてるので許して。
かなり重そうだけど…。
と言う訳で、少し軽くする為に、ファイルの部分を、
メモリ内に常駐させれば、使える速さになる…かな？
…嫌な常駐だな…。

>>100
πは証明がなされたはずですよ
πに関する話題だけのの本数冊
みかけた　理解は出来なかったけど
でもπの２乗が有理数か無理数かは
解ってないそうだ　不思議なものだね

>>101
厳密には超絶数と言うらしい

循環しない小数があったとして、どうやれば乱数にできるかな。
二進数化していって、数桁ごとに区切るか？

CD-ROMから「王仁三郎　言霊リミックス」を読み出せば乱数です。
必要なら他のと混ぜてね