Nombor pseudo-rawak ialah nombor khas yang dijana oleh penjana khas. Penjana Bit Rawak Deterministik (PRNG), juga dikenali sebagai Penjana Bit Rawak Deterministik (DRBG), ialah algoritma untuk menjana urutan nombor yang sifatnya menghampiri ciri-ciri jujukan nombor rawak. Urutan PRNG yang dijana tidak benar-benar rawak, kerana ia ditentukan sepenuhnya oleh nilai benih yang dipanggil benih PRNG, yang mungkin termasuk nilai yang benar-benar rawak. Walaupun jujukan yang lebih hampir kepada rawak boleh dijana menggunakan penjana nombor rawak perkakasan, penjana nombor pseudo-rawak adalah penting dalam amalan untuk kelajuan penjanaan nombor dan kebolehulangannya.
Permohonan
PRNG adalah penting kepada aplikasi seperti simulasi (cth untuk Monte Carlo), permainan elektronik (cth untuk penjanaan prosedur), dan kriptografi. Aplikasi kriptografi memerlukan outputdata tidak dapat diramalkan daripada maklumat awal. Algoritma yang lebih kompleks diperlukan yang tidak mewarisi kelinearan PRNG mudah.
Terma dan Syarat
Sifat statistik yang baik adalah keperluan utama untuk mendapatkan PRNG. Secara umum, analisis matematik yang teliti diperlukan untuk memastikan bahawa RNG menjana nombor yang cukup hampir kepada rawak agar sesuai untuk kegunaan yang dimaksudkan.
John von Neumann memberi amaran terhadap salah tafsir PRNG sebagai penjana yang benar-benar rawak dan bergurau bahawa "Sesiapa yang menganggap kaedah aritmetik untuk menjana nombor rawak sudah tentu berada dalam keadaan berdosa."
Gunakan
PRNG boleh dilancarkan dari keadaan awal yang sewenang-wenangnya. Ia akan sentiasa menjana urutan yang sama apabila dimulakan dengan keadaan ini. Tempoh PRNG ditakrifkan seperti berikut: maksimum ke atas semua keadaan awal panjang awalan urutan tidak berulang. Tempoh dihadkan oleh bilangan keadaan, biasanya diukur dalam bit. Oleh kerana panjang tempoh berpotensi meningkat dua kali ganda dengan setiap bit "keadaan" ditambah, adalah mudah untuk mencipta PRNG dengan tempoh yang cukup besar untuk banyak aplikasi praktikal.
Jika keadaan dalaman PRNG mengandungi n bit, tempohnya boleh tidak lebih daripada 2n hasil, ia adalah lebih pendek. Bagi sesetengah PRNG, tempoh boleh dikira tanpa memintas keseluruhan tempoh. Daftar Anjakan Maklum Balas Linear (LFSR) biasanyadipilih supaya mempunyai kala bersamaan dengan 2n − 1.
Penjana kongruen linear mempunyai tempoh yang boleh dikira menggunakan pemfaktoran. Walaupun PPP akan mengulangi keputusannya selepas ia mencapai penghujung tempoh, keputusan berulang tidak bermakna bahawa akhir tempoh telah dicapai, kerana keadaan dalamannya mungkin lebih besar daripada output; ini amat jelas untuk PRNG dengan output bit tunggal.
Kemungkinan ralat
Ralat yang ditemui oleh PRNG yang rosak terdiri daripada yang halus (dan tidak diketahui) kepada yang jelas. Contohnya ialah algoritma nombor rawak RANDU, yang telah digunakan pada kerangka utama selama beberapa dekad. Ia adalah kelemahan yang serius, tetapi ketidakcukupannya tidak disedari untuk jangka masa yang panjang.
Di banyak kawasan, kajian penyelidikan yang telah menggunakan pemilihan rawak, simulasi Monte Carlo atau kaedah lain berdasarkan RNG adalah kurang boleh dipercayai berbanding hasil GNPG berkualiti rendah. Malah pada hari ini, berhati-hati kadangkala diperlukan, seperti yang dibuktikan oleh amaran dalam International Encyclopedia of Statistical Science (2010).
Kajian kes yang berjaya
Sebagai ilustrasi, pertimbangkan bahasa pengaturcaraan Java yang digunakan secara meluas. Sehingga 2017, Java masih bergantung pada Penjana Kongruen Linear (LCG) untuk PRNGnya.
Sejarah
PRNG pertama yang mengelakkan masalah serius dan masih berjalan dengan agak pantas,ialah Mersenne Twister (dibincangkan di bawah), yang diterbitkan pada tahun 1998. Sejak itu, PRNG berkualiti tinggi lain telah dibangunkan.
Tetapi sejarah nombor pseudo-rawak tidak berakhir di situ. Pada separuh kedua abad ke-20, kelas standard algoritma yang digunakan untuk PRNG termasuk penjana kongruen linear. Kualiti LCG diketahui tidak mencukupi, tetapi kaedah yang lebih baik tidak tersedia. Press et al (2007) menyifatkan keputusannya seperti berikut: "Jika semua kertas saintifik yang keputusannya diragui kerana [LCG dan berkaitan] hilang dari rak perpustakaan, akan ada jurang sebesar penumbuk anda pada setiap rak."
Pencapaian utama dalam penciptaan penjana pseudo-rawak ialah pengenalan kaedah berdasarkan berulang linear dalam medan dua elemen; pengayun tersebut digandingkan dengan daftar anjakan maklum balas linear. Ia berfungsi sebagai asas untuk penciptaan penderia nombor pseudo-rawak.
Khususnya, ciptaan Mersen Twister pada tahun 1997 mengelakkan banyak masalah dengan penjana terdahulu. Mersenne Twister mempunyai tempoh 219937−1 lelaran (≈4.3 × 106001). Ia telah terbukti diedarkan secara seragam dalam (sehingga) 623 dimensi (untuk nilai 32-bit), dan pada masa pengenalannya adalah lebih pantas daripada penjana bunyi statistik lain yang menghasilkan jujukan nombor rawak pseudo.
Pada tahun 2003, George Marsaglia memperkenalkan keluarga penjana xorshift juga berdasarkan pengulangan linear. Penjana ini sangatpantas dan - digabungkan dengan operasi bukan linear - mereka lulus ujian statistik yang ketat.
Pada tahun 2006, keluarga penjana WELL telah dibangunkan. Penjana BAIK dalam erti kata lain meningkatkan kualiti Twister Mersenne, yang mempunyai ruang keadaan yang terlalu besar dan pemulihan yang sangat perlahan daripadanya, menjana nombor pseudo-rawak dengan banyak sifar.
Cryptography
PRNG yang sesuai untuk aplikasi kriptografi dipanggil PRNG selamat kriptografi (CSPRNG). Keperluan untuk CSPRNG ialah penyerang yang tidak mengetahui benih hanya mempunyai kelebihan kecil dalam membezakan jujukan keluaran penjana daripada jujukan rawak. Dalam erti kata lain, walaupun PRNG hanya diperlukan untuk lulus ujian statistik tertentu, CSPRNG mesti lulus semua ujian statistik yang terhad kepada masa polinomial dalam saiz benih.
Walaupun bukti sifat ini melebihi tahap teori kerumitan pengiraan semasa, bukti kukuh boleh diberikan dengan mengurangkan CSPRNG kepada masalah yang dianggap sukar, seperti pemfaktoran integer. Secara umum, semakan bertahun-tahun mungkin diperlukan sebelum algoritma boleh disahkan sebagai CSPRNG.
Telah ditunjukkan bahawa kemungkinan NSA telah memasukkan pintu belakang yang tidak simetri ke dalam penjana nombor pseudo-rawak Dual_EC_DRBG yang diperakui NIST.
Algoritma pseudo-rawaknombor
Kebanyakan algoritma PRNG menghasilkan jujukan yang diagihkan sama rata oleh mana-mana beberapa ujian. Ini adalah soalan terbuka. Ia adalah salah satu pusat dalam teori dan amalan kriptografi: adakah terdapat cara untuk membezakan output PRNG berkualiti tinggi daripada urutan yang benar-benar rawak? Dalam tetapan ini, penyelesai mengetahui bahawa sama ada algoritma PRNG yang diketahui telah digunakan (tetapi bukan keadaan ia dimulakan), atau algoritma yang benar-benar rawak telah digunakan. Dia mesti membezakan antara mereka.
Keselamatan kebanyakan algoritma dan protokol kriptografi yang menggunakan PRNG adalah berdasarkan andaian bahawa adalah mustahil untuk membezakan antara penggunaan PRNG yang sesuai dan penggunaan jujukan yang benar-benar rawak. Contoh paling mudah bagi kebergantungan ini ialah sifir strim, yang paling kerap berfungsi dengan meninggalkan atau menghantar mesej teks biasa dengan output PRNG, menghasilkan teks sifir. Mereka bentuk PRNG yang mencukupi secara kriptografi adalah amat sukar kerana ia mesti memenuhi kriteria tambahan. Saiz tempohnya ialah faktor penting dalam kesesuaian kriptografi PRNG, tetapi bukan satu-satunya.
PRNG komputer awal yang dicadangkan oleh John von Neumann pada tahun 1946 dikenali sebagai kaedah kuasa dua min. Algoritma adalah seperti berikut: ambil sebarang nombor, kuasa duakannya, keluarkan digit tengah nombor yang terhasil sebagai "nombor rawak", kemudian gunakan nombor ini sebagai nombor permulaan untuk lelaran seterusnya. Sebagai contoh, menduakan nombor 1111 memberi1234321, yang boleh ditulis sebagai 01234321, nombor 8 digit ialah kuasa dua bagi nombor 4 digit. Ini memberikan 2343 sebagai nombor "rawak". Keputusan mengulangi prosedur ini ialah 4896, dan seterusnya. Von Neumann menggunakan 10 digit nombor, tetapi prosesnya adalah sama.
Kelemahan "petak tengah"
Masalah dengan kaedah "mean square" ialah semua jujukan akhirnya berulang, ada yang sangat cepat, contohnya: 0000. Von Neumann tahu tentang ini, tetapi dia mendapati pendekatan yang mencukupi untuk tujuannya, dan bimbang bahawa "pembetulan" matematik hanya akan menyembunyikan ralat dan bukannya mengalih keluarnya.
Von Neumann mendapati penjana nombor rawak dan pseudo-rawak perkakasan tidak sesuai: jika mereka tidak merekodkan output yang dijana, mereka tidak boleh disemak untuk ralat kemudian. Jika mereka menulis keputusan mereka, mereka akan kehabisan memori terhad komputer yang tersedia dan dengan itu keupayaan komputer untuk membaca dan menulis nombor. Jika nombor ditulis pada kad, ia akan mengambil masa yang lebih lama untuk menulis dan membaca. Pada komputer ENIAC yang dia gunakan, kaedah "petak tengah" dan menjalankan proses mendapatkan nombor rawak semu beberapa ratus kali lebih cepat daripada membaca nombor daripada kad tebuk.
Min kuasa dua sejak itu telah digantikan oleh penjana yang lebih kompleks.
Kaedah inovatif
Inovasi terbaharu ialah menggabungkan min kuasa dua dengan jujukan Weil. Kaedah ini memastikan produk berkualiti tinggi dalamtempoh yang lama. Ia membantu untuk mendapatkan formula nombor rawak pseudo terbaik.
