menghasilkan bilangan bulat acak
Saya mohon maaf sebelumnya karena saya tidak terlalu berpengalaman dengan gagasan formal tentang keacakan.
Judulnya mengatakan sebagian besar: Saya ingin menghasilkan bilangan bulat acak dalam waktu yang wajar, di mana setiap bilangan bulat dapat muncul, apakah dengan frekuensi yang sama atau tidak tidak penting. Sebagai tambahan, memori komputer tidak menjadi masalah, karena bahkan dengan ruang memori tak terbatas untuk menyimpan nomor yang dihasilkan ini, tidak jelas bagaimana seseorang dapat melakukan ini. Saya belum membuat kemajuan apa pun dalam mencari tahu algoritme yang tepat, tetapi inilah pengamatan saya.
Jika Anda dapat menghasilkan bilangan real secara acak, Anda dapat menggunakan fungsi seperti fungsi lantai untuk menghasilkan bilangan bulat apa pun. Jika Anda dapat secara acak menghasilkan bilangan real apa pun di antara interval apa pun$[a,b]$, maka Anda dapat menggunakan fungsi asimtotik seperti $\tan$ untuk menghasilkan bilangan real apa pun.
Secara umum jika saya memiliki himpunan S yang memiliki kardinalitas yang lebih besar atau sama dengan bilangan bulat, dan saya dapat secara acak menghasilkan elemen dalam S, maka saya dapat secara acak menghasilkan bilangan bulat dengan memetakan anggota S ke bilangan bulat.
Saya tahu bahwa ada urutan, seperti urutan celah utama, yang acak dan berisi bilangan bulat besar yang sewenang-wenang, tetapi tidak dapat dihitung dengan mudah.
Namun itu tentang hal itu berkaitan dengan apa yang dapat saya pikirkan. Saya tidak akan terkejut jika tidak ada solusi yang mudah untuk masalah ini, tetapi jika ada yang memiliki alasan mengapa hal ini tidak memungkinkan, saya juga ingin mendengarnya.
Jawaban
Ukuran sewenang-wenang tidak ada artinya karena komputasi tidak dapat berhenti!
Pertimbangkan bahwa Anda melempar koin untuk setiap bit bilangan bulat acak, maka Anda dapat melihat bahwa lemparan koin tidak pernah berakhir.
Seseorang harus berhati-hati saat bermain dengan ukuran sewenang-wenang. Secara matematis Anda dapat mengatakan bahwa biarkan$x$ menjadi bilangan bulat acak, yaitu $x \stackrel{R}{\leftarrow} \mathbb Z$Namun, ketika Anda mencoba menemukan nilai ini, Anda akan menghadapi generasi itu. Jika Anda ingin integer acak seragam maka jelas itu akan gagal!
Sekarang asumsikan bahwa Anda memiliki batas suka $0\color{red}{<} x \leq 2^L$lalu Anda dapat menggunakan LFSR untuk menghasilkan nomor acak dalam jangkauan. Jika LFSR dengan ukuran$L$ maksimal maka periodik dan memiliki periode $2^L-1$. Dalam periode ini ia mengunjungi semua kemungkinan$L$angka -bit kecuali negara semua-nol. Anda bisa mendapatkan benih sejak saat itu dan mulai menggunakannya.
Perhatikan bahwa LFSR masih jauh dari Cryptographically Secure Random Pseudo Generator (CSPRNG). Baru saja$2L$ keluaran bit dari LFSR cukup untuk menentukan bit berikutnya karena algoritma Berlakamp-Massay - dan sebenarnya, eliminasi Gaussian sudah cukup, namun BM jauh lebih cepat-.