Bagaimana saya bisa menentukan nilai awal generator angka pseudo-acak jika urutannya diberikan?

10

Misalkan saya tahu bahwa urutan nomor acak dihasilkan oleh generator congruential linier. Itu adalah,

xn+1=(aXn+c)modm

Jika saya diberi seluruh periode (atau paling tidak sebuah urutan besar yang berdekatan), bagaimana saya bisa merekonstruksi parameter dan yang menghasilkan urutan ini? Saya mencari metode umum yang akan dapat menentukan parameter awal jika generator angka pseudo-acak diketahui.x 0a,c,mx0

random-number-generation inverse-problem Paul
sumber
Apa sebenarnya yang diketahui? Dari subseqensi yang berdekatan Anda tidak bisa mengatakan di mana urutan dimulai , kecuali item diindeks secara berurutan. Jika diketahui, maka dan mudah ditemukan. m a cx0mac
hardmath

Jawaban:

10

Lihat kertas Cara memecahkan Generator Linear Congruential, Haldir ("Tim Rekayasa Terbalik", Desember 2004):

Dalam makalah ini saya akan menyajikan metode yang akan menyelesaikan semua nilai LCG termasuk modulus dengan enam atau lebih nomor output PRNG berturut-turut.

Makalah ini menyertakan kode sumber "bukti konsep" yang ditulis dalam C, menggunakan NTL karya Victor Shoup untuk aritmatika presisi yang diperluas.

hardmath
sumber
Itu kertas yang bagus! :) Apakah Anda tahu metode yang lebih umum yang dapat diterapkan pada generator bilangan acak lainnya, bukan hanya kongruensi linear?
Paul
@ Paul: Tentu saja seseorang dapat menemukan RNG yang mudah "dipecahkan" untuk parameter mereka dari data output yang cukup (masalah terbalik), tetapi akan terlihat bahwa semakin baik RNG (semakin acak penampilan output), semakin sulit yang terbalik masalah akan menjadi. Solusi kasus LCG terkait dengan efek pengelompokan dimensi tertentu yang terkenal, membuat pasangan nilai yang dihasilkan tidak terdistribusi secara seragam. Untuk lebih lanjut lihat Desain Generator Kuat Kriptografis Dengan Mengubah Urutan Linearly Generated
hardmath