任意のランダムな整数を生成します
ランダム性の正式な概念についてはあまり経験がないので、事前に謝罪します。
タイトルはそのほとんどを示しています。妥当な時間内にランダムな整数を生成したいのですが、同じ頻度であるかどうかに関係なく、すべての整数が表示される可能性があります。アドオンとして、これらの生成された数値を格納するための無限のメモリスペースがあっても、これをどのように行うことができるかは明らかではないため、コンピュータメモリは問題ではありません。私は実際に適切なアルゴリズムを理解することに何の進歩もありませんでしたが、ここに私の観察があります。
任意の実数をランダムに生成できる場合は、floor関数などの関数を使用して任意の整数を生成できます。任意の間隔の間に任意の実数をランダムに生成できる場合$[a,b]$、次に、次のような漸近関数を使用できます。 $\tan$ 任意の実数を生成します。
一般に、整数と同じかそれ以上のカーディナリティを持つ集合Sがあり、S内で要素をランダムに生成できる場合、Sのメンバーを整数にマッピングすることで任意の整数をランダムに生成できます。
素数の間隔シーケンスのように、ランダムで任意の大きさの整数を含むシーケンスがありますが、簡単に計算できないことは知っています。
しかし、それは私が考えることができることに関してはそれについてです。問題の簡単な解決策がなくても驚くことではありませんが、それが不可能な理由があれば、私も聞きたいと思います。
回答
計算を停止できないため、任意のサイズは意味がありません。
ランダムな整数のすべてのビットに対してコインを投げると、コインの投げは終わりがないことがわかります。
任意のサイズで遊ぶときは注意が必要です。数学的には、$x$ ランダムな整数、つまり $x \stackrel{R}{\leftarrow} \mathbb Z$ただし、これの値を見つけようとすると、その生成に直面します。均一なランダム整数が必要な場合は、明らかに失敗します。
ここで、次のような制限があると仮定します $0\color{red}{<} x \leq 2^L$次に、LFSRを使用して、範囲内の乱数を生成できます。サイズのあるLFSRの場合$L$ 最大である場合、それは周期的であり、 $2^L-1$。この期間にそれはすべての可能な訪問します$L$-すべてゼロの状態を除くビット数。その時から種を手に入れて使い始めることができます。
LFSRは、暗号論的に安全なランダム疑似ジェネレーター（CSPRNG）とはほど遠いことに注意してください。ただ持っている$2L$ Berlakamp-Massayアルゴリズムにより、LFSRからのビット出力は次のビットを決定するのに十分です。実際には、ガウスの消去法で十分ですが、BMの方がはるかに高速です。