Apa yang membuat generator pseudorandom, yang berkualitas tinggi?

8

Membaca jawaban untuk pertanyaan SO ini: Mengapa kita tidak menggabungkan generator bilangan acak? , itu berbicara tentang

PRNG yang sangat tinggi (Pseudo Random Number Generator)

jadi itu membuat saya bertanya-tanya apa yang merupakan PRNG berkualitas tinggi, saya berasumsi Anda dapat meringkasnya karena menjadi "lebih acak", tetapi

  • Pertanyaan1: Kualitas PRNG mana yang digunakan untuk menggambarkan seberapa 'acak' atau 'baik' itu?

  • Pertanyaan2: Jika Anda memiliki PRNG 'kualitas buruk', apakah ada cara untuk menjadikannya lebih baik?

randomness pseudo-random-generators random-number-generator Jose
sumber
Relevan stackoverflow.com/questions/2130621/...
adrianN
2
Anda juga perlu membedakan PRNG biasa dari RNG yang aman secara kriptografis.
adrianN
1
PRNG adalah 'lebih baik' jika lebih sulit untuk membedakan outputnya dari bit yang benar-benar acak.
Yuval Filmus

Jawaban:

9

Ada beberapa kriteria untuk kualitas PRNG:

  • Seberapa cepat. Ini termasuk seberapa cepat untuk mengaturnya, dan seberapa cepat untuk menghasilkan bit tunggal (diamortisasi).
  • Betapa sulitnya menebak bit berikutnya yang diberikan semua bit sebelumnya.
  • Betapa sulitnya untuk membedakan antara output PRNG dan bit yang benar-benar acak.

Dua kriteria terakhir sangat terkait.

Jika Anda memiliki PRNG kualitas buruk, Anda sering dapat membuatnya lebih baik dengan amplifikasi kekerasan . Ambil beberapa salinan PRNG (menggunakan kunci acak berbeda) dan XOR bersama-sama. Dalam banyak (walaupun tidak semua) hal ini akan secara signifikan meningkatkan kualitasnya.

Yuval Filmus
sumber
Hanya pertanyaan lain: Mengapa menggunakan PRNG yang akan menyebabkan urutan yang sama jika benih yang sama digunakan dua kali, dan tidak hanya mendapatkan benih baru (misalnya cpu clock) setiap kali nomor acak baru diperlukan? bukankah pendekatan ini lebih acak?
Jose
2
@ Jose Ini sesuai desain. Dalam banyak kasus, Anda ingin dapat menghasilkan urutan yang sama persis berkali-kali. Dua contoh adalah percobaan Monte Carlo (yang harus dapat diulang) dan kriptografi (di mana kami ingin dua pengguna memiliki urutan acak yang sama, digunakan sebagai kunci).
Yuval Filmus
Eksperimen Monte Carlo jarang membutuhkan PRNG kriptografi.
Xavier Combelle
2

Ada beberapa pertimbangan praktis: Seberapa mudah digunakan? Seberapa cepat? Seberapa mudah untuk menghasilkan urutan angka acak yang berbeda? Seberapa mudah untuk memutar ulang angka acak (misalnya, jika Anda menghasilkan 10 miliar angka acak, dapatkah Anda menghasilkan 10 miliar angka acak yang sama persis lagi?)

Pertanyaan besar: Apakah angka yang dihasilkan berperilaku seperti urutan angka acak? PRNG pertama yang pernah saya gunakan memiliki properti aneh yang memiliki dua nilai berturut-turut, yang kedua lebih besar dengan probabilitas sekitar 0,6. Tidak terlalu acak. Jadi, Anda dapat menjalankan semua jenis uji statistik dan memeriksa apakah generator nomor acak Anda berperilaku secara acak. Semakin berperilaku seperti acak, semakin baik.

Dan kemudian muncul keacakan kriptografis. Jika saya memberi Anda n angka acak terakhir, dan pengetahuan lengkap bagaimana generator angka acak berperilaku, dapatkah Anda memprediksi angka acak berikutnya? Jika ya, itu membuatnya tidak cocok dalam situasi di mana Anda memiliki musuh.

gnasher729
sumber
0

Saya akan menambahkan distribusi seragam ke daftar kualitas yang diinginkan.

Maciek Łoziński
sumber
Secara umum dipahami bahwa PRNG menghasilkan distribusi yang seragam (atau hampir).
vonbrand