ランダム化アルゴリズムの設計におけるランダムジェネレーターの考慮事項

Question

ランダム化アルゴリズムの効率（少なくともBPPおよびRPの効率）は、使用されるランダムジェネレーターの品質に依存することはよく知られています。完全なランダムソースは実際には利用できません。すべてのすべての$ 0 < delta leq frac {1} {2} $ ID bpp = $ delta $ -bppおよびrp = $ delta $ -rpホールド知事ランダムソースに使用されるアルゴリズムは、$ delta $ -Randomソースにも直接使用できます。代わりに、いくつかのシミュレーションを実行する必要があります。このシミュレーションは多項式ですが、結果のアルゴリズムは元のアルゴリズムほど効率的ではありません。

さらに、私の知る限り、実際に使用されるランダムジェネレーターは通常、$ delta $ -Sourcesではなく、最悪の場合に非常にひどく振る舞う可能性のある擬似ランダムソースです。

によると ウィキペディア:

一般的な慣行では、ランダム化されたアルゴリズムは、ランダムビットの真のソースの代わりに擬似ランダム数ジェネレーターを使用して近似されます。このような実装は、予想される理論的行動から逸脱する可能性があります。

実際、私が今まで見たランダム化されたアルゴリズムの実装は、擬似ランダムソースを使用して実行される完全なランダムソースのアルゴリズムの単なる実装でした。

私の質問は、この一般的な慣行の正当化があるかどうかです。ほとんどの場合、アルゴリズムが正しい結果を返すことを期待する理由はありますか？ウィキペディアからの引用で言及されている「近似」はどのように正式化できますか？少なくとも予想される場合、言及された偏差は何らかの形で推定できますか？完全なランダムソースで実行されるモンテカルロランダム化アルゴリズムが、擬似ランダムソースで実行されると、行儀の良い確率的アルゴリズムに変わると主張することは可能ですか？または、他にも同様の考慮事項はありますか？

Answer 1

ここに1つの良い正当化があります。暗号化された強度の疑似ランダム数ジェネレーターを使用して、何らかのランダム化されたアルゴリズムで必要なランダムビットを生成するとします。暗号アルゴリズムが安全である限り、結果のアルゴリズムは機能し続けます。

a 暗号化された擬似ランダム数ジェネレーター 短い種子（たとえば、128ビットの真のランダム性）を受け入れ、無制限の数の擬似ランダムビットを生成する暗号化の標準ツールです。それには非常に強力なセキュリティ保証が付属しています。基礎となる暗号化原始が壊れていない限り、擬似ランダムビットは、実行可能なプロセスによって真のランダムビットと完全に区別できません（特に、効率的なアルゴリズムは出力を区別できません。真のランダムビットのシーケンスから）。たとえば、因数分解が難しい場合（またはRSAが安全である場合、またはAESが安全な場合）という保証が得られる場合があります。これは良い擬似ランダムジェネレーターです。

これらの暗号化のプリミティブを破るのは非常に難しいと広く信じられているため、これは非常に強力な保証です。たとえば、非常に多くの数値を考慮する効率的な方法を把握できる場合、それは画期的な結果になります。すべての実用的な目的のために、暗号化のプリミティブが壊れないように振る舞うことができます。これは、すべての実用的な目的のために、暗号化された擬似ランダム数ジェネレーターの出力は、真のランダムビットのシーケンスと基本的に同じであるかのように振る舞うことができることを意味します。特に、これはランダム化されたアルゴリズムで必要なランダム性の良いソースです。

（暗号強度のPRNGを使用するには、シードを形成するために独自に128ビットの真のランダム性を見つける必要があるという事実に光沢がありました。しかし、これは難しくありません。実際、暗号化ツールがありますそのタスクも支援するために。）

実際には、非常に良い擬似ランダムビットを取得することは簡単です

$ cat /dev/urandom

Answer 2

ランダム化アルゴリズムの効率（少なくともBPPおよびRPの効率）は、使用されるランダムジェネレーターの品質に依存することはよく知られています。 私は反対しなければなりません。アンサンブルがあなたに与える良い擬似ランダムシーケンスは、Trullyランダムシーケンスと比較して、アンサンブルからランダムシーケンスを実行するアルゴリズムのパフォーマンスの保証です。そのような保証がない場合、アルゴリズムの動作が不十分であると結論付けることはできません - あなたはただ知りません。

この一般的な慣行の正当化はありますか？ できます。

完全なランダムソースで実行されるモンテカルロランダム化アルゴリズムが、擬似ランダムソースで実行されると、行儀の良い確率的アルゴリズムに変わると主張することは可能ですか？ 複雑さ理論は2つの欠点に苦しんでいます。 1つ目は、何かを証明するのが非常に難しいことです（たとえば、P対NPが開いています）。 2つ目は、主に最悪の分析に関係していることです。まとめて、これらの2つの制限は、実際にアルゴリズムの動作の良いモデルとして複雑さ理論を除外します。