フリップフロップ回路を組み込んだ新たな乱数生成手法 37
ストーリー by hylom
その発想はなかった 部門より
その発想はなかった 部門より
あるAnonymous Coward 曰く、
独ハーゲン大学らの開発チームらが、乱数生成の新しい手法を開発したそうだ（Science Daily、本家記事）。
このアルゴリズムでは、コンピュータメモリのフリップフロップ回路のランダムスイッチングを組み込んだとのこと。フリップフロップはスイッチングの直前は「準安定状態」にあり予測することができず、準安定状態の後メモリに保持されている内容は完全にランダムである。フリップフロップが組み込まれている場合、小さな配列では20倍「ランダム」な数を生成できることが実験で証明されているという。また、配列を故意に曲げようとする試みは、配列全体もしくは単体の要素が乱されるため容易に見分けられるという利点もあるとのこと。
乱数はセキュリティ分野だけでなく天気予報などの気象シミュレーションなどにも使われており、「ランダム」であればあるほどその精度が高まるとされている。
メタステーブル (スコア:2)
ここはメタステーブルとカタカナにしておくのが妥当な訳だと思う。
熱雑音が乱数性の担保になるのかな?
Re: (スコア:0)
ぱっと見てメタスなテーブルに読めるので、メタ・ステーブルとでも書いた方がいいんじゃないですかね。
まあ、準安定で全然構わないとおもいますが、カタカナでそのまま書けというなら判りやすく分けてほしいです。
#個人的にはなるべく日本語にしてもらいたいものだけど。
Re:メタステーブル (スコア:3, 参考になる)
ご存知ないようですが、メタステーブルというよく使われる術語がすでにあるのです。(投稿する前に検索すれば10秒でわかるものを…)
http://www.sophia-it.com/content/%E3%83%A1%E3%82%BF%E3%82%B9%E3%83%86%... [sophia-it.com]
http://www.cqpub.co.jp/term/metastable.htm [cqpub.co.jp]
Re:メタステーブル (スコア:1)
ハード屋じゃないとなかなかお目にかかれないかもね
Re: (スコア:0)
おっと物理屋（っちゅうか物性屋か）も忘れてもらっては困る
非同期のインタフェースめんどくさい (スコア:0)
> ぱっと見てメタスなテーブルに読めるので、メタ・ステーブルとでも書いた方がいいんじゃないですかね。
「メタステーブル」を「メタス」と略して会話していた時期があったので、「メタスなテーブル」って
書かれて、なんのこっちゃわからんかった。
＃メタス以外にもいろいろ対策しなきゃいけないんだよね・・。
Re: (スコア:0)
Meta-stableにいれるタイミング関係が、結果の分布に影響を与えそうですけど、
"完全にランダム"っていっていいんだろうか。
試作レベルでは確率50%に調整できても量産したら偏りそうです。
ショットキーダイオードの雑音から乱数生成っていうのもあったような。
Re:メタステーブル (スコア:1)
Re:メタステーブル (スコア:1, すばらしい洞察)
それって単なるデジタルな発振回路を適当にサンプリングして乱数にしてるだけとしか読めない。
発振回路の時間的なゆらぎってショット雑音とかとはまた違う気がするな。
回路の製造が安定していればしているほど周期的なデータが出てきそうですごく嫌。
コレ単品では使い物にならないだろうし、擬似乱数列のシードにしたり擬似乱数列をさらに乱すとかの用途ならぎりぎり使い物になるけれど、厳密な用途には使えないと思うなぁ…
ツェナーダイオード使ったものはアナログ回路になるとはいえきっちりホワイトノイズになるから適当に作った単体でもそこそこ、組み合わせならかなりの品質が得られるってのが判るんだけど。
Re: (スコア:0)
今回のものはFFを不安定な安定状態(メタステーブル状態)にしてノイズサンプリングしている。
イメージとしては鉛筆を立ててどちらに転ぶかを観測するイメージ。鉛筆が立つという状態は安定状態ではあるが不安定なので最終的にはどちらかに転ぶ。
鉛筆がどちらに転ぶかは外乱によってきまる。
FFの場合はサーマルノイズやクロストークの影響によって決まると考えられるが実際のところはよくわからない。
メタステーブルは回路のバランスが取れていれば取れているほど外乱によって決まる割合が高まるので製造が安定することは乱数品質的に優位になる。
また、ADコンバータを利用する既存の乱数生成回路に対しデジタル回路のみで実装されるので実装が容易になる。
Re: (スコア:0)
「乱数も作れるほど大きいノイズを出すから、コンデンサを付けるのを忘れるな」ってことだったかも。
Spin dice (スコア:1, 参考になる)
MRAMで乱数を発生させる装置もあるのですが、どちらが良いのでしょか。
http://venturewatch.jp/aist/20091130.html [venturewatch.jp]
トンネル磁気抵抗素子を用いた乱数発生器 (スコア:1, 参考になる)
産総研のスピンダイス [semiconjapan.jp]のことも思い出して下さい。
Re:トンネル磁気抵抗素子を用いた乱数発生器 (スコア:1, おもしろおかしい)
コメント#1723958 [srad.jp]のことも思い出してあげてください。
むかし (スコア:0)
手作りしたような人は電源オンのたんびにほぼ似たような
ランダムバターンが画面に出るのを見て
回路にも癖があるんだぁー、と思ったもんです。
D-RAMの場合は0xffのブロックと0x00のブロックが
交互に現れるのはなにか理由があるんでしたっけ？
だいぶ前に国内の研究者から同じ原理の話を聞いたんだけど (スコア:0)
ん？ (スコア:0)
内容を読み出して乱数に使ったってことなのかな？
20倍って? (スコア:0)
何倍とかあるの?
Re:20倍って? (スコア:1)
分布密度とか、「mの次にnのでる確立」がm,nによらず変わらないとか、あるいはよく知らないもっと洗練された方法で定量化できるんじゃないでしょうか?
何らかの方法で。
#たよりなさすぎる
新人。プログラマレベルをポケモンで言うと、コラッタぐらい
Re: (スコア:0)
Re:20倍って? (スコア:1, 参考になる)
乱数ネタだけで教科書が1冊書けるぐらいいろんな評価尺度があります。例えば周期。疑似乱数は発生させ続けるとぐるっと回って同じ系列に戻っちゃうのですが、そこまでの長さが長いほど良い乱数です。
他には、連続した乱数の間の相関関係。単純なアルゴリズムだと、偶数→奇数→偶数→奇数→偶数→奇数・・・と規則的にしか出てこないとか、それをそのまま使っちゃってCPUの手が全部読めちゃうカードゲームとかもありましたね。
その親戚で、3次元空間のランダムな座標を「3つ連続で乱数を発生させてx,y,zとする」でやっちゃうと、全ての(x,y,z)がいくつかの平面上に集まっちゃうという残念さの評価尺度もあるらしいです。空間全体をランダムに飛び回って何かを調べているつもりが、そのいくつかの平面上しか調べられていない、などという残念な結果に陥るとか。これがn次元の場合でも十分にばらけるよ、みたいな評価をするとか書いてありました。
Re: (スコア:0)
完全な乱数って一体なんなんだろう・・・
と考えてはまってしまう
Re: (スコア:0)
Re:20倍って? (スコア:1)
調べもしないで書くけど、乱数列が与えられた時に、それが
・乱数でない確率
を計算することでランダム性を検定したとして、たとえば比較対象（ショボい方）の乱数列がその確率が5%、もう一方（優れてる方）は0.025%だから20倍優れてるっていうような感じのことかも知れません。
Re: (スコア:0)
わかってないなら黙っていればいいのに。
Re: (スコア:0)
お前も分かってないなら黙ってろよ。
分かってるなら、それを書けよ。
あ、俺もか。
よし、この回路を (スコア:0)
論文 (スコア:0)
まず読め。議論はそれからだ。
"A meta-level true random number generator"
Bernhard Fechner and Andre Osterloh,
Int. J. Critical Computer-Based Systems, 1 (2010) 267-279
http://dx.doi.org/10.1504/IJCCBS.2010.031719 [doi.org]
ぼくのかんがえたさいきょうの乱数アルゴリズム (スコア:0)
ロボットアームがさいころを掴む
↓
適当な擬似乱数を生成
↓
擬似乱数に応じた高さにロボットアームがさいころを持ち上げる
↓
さいころを転がす
↓
OCRでさいころの目を読む
Re: (スコア:0)
さいころの品質以上の乱数が得られません
Re: (スコア:0)
Re: (スコア:0)
そのサイコロが六面ダイスだと誰が言った！
Re: (スコア:0)
五進数にするだろこの場合は……
Re: (スコア:0)
Re: (スコア:0)
規則性が無いという (スコア:0)
(1-n)
全体的に雑な研究 (スコア:0)
http://www.tsi.enst.fr/publications/enst/inproceedings-2007-7431.pdf [tsi.enst.fr]
DangerらはFPGAで実装し、NISTテストまで通しているが今回のものはまともに評価できてないので、これで有用性を主張されてもという感じ。
RSラッチのメタスタビリティを利用した物を提案されているが、これは92年ごろから提案されており最近ではFPGAでポストプロセッシングなしで NISTテストを通すものも報告されている。
http://ci.nii.ac.jp/naid/110007131424 [nii.ac.jp]
メタスタビリティベースのTRNGはすでに安定性の改善に焦点が移っており基本原理の確認レベルのこの研究に進歩性があるとは思えない。というかサーベイをろくにやってないのはどうよ。