Jak mogę określić początkowe wartości generatora liczb pseudolosowych, jeśli podana jest sekwencja?

Załóżmy, że wiedziałem, że losowa sekwencja liczb została wygenerowana przez liniowy generator kongruencjalny. To jest,

$x_{n+1}=(aX_n+c) \bmod m$

Jeśli jestem biorąc pod uwagę cały okres (lub przynajmniej znaczna przyległe podciąg z nim), w jaki sposób można zrekonstruować parametrów i że wytwarzany tej sekwencji? Szukam ogólnej metody, która byłaby w stanie określić początkowe parametry, jeśli znany jest generator liczb pseudolosowych. $a,c,m$ $x_0$

random-number-generation inverse-problem

— Paweł
źródło

Co dokładnie wiadomo? Na podstawie ciągłej podsekwencji nie można ustalić, od której sekwencji rozpoczyna się

x_{0}

$x_0$ , chyba że elementy są indeksowane w sekwencji. Jeżeli

m

$m$ jest znana, wówczas i

mogą być łatwo wykryte.

a

$a$

c

$c$

— matematyka

Zobacz artykuł Jak złamać liniowy generator zbieżny , Haldir („Zespół inżynierii odwrotnej”, grudzień 2004):

W tym artykule przedstawię metodę, która rozwiąże wszystkie wartości LCG, w tym moduł o sześciu lub więcej kolejnych liczbach wyjściowych PRNG.

Artykuł zawiera kod źródłowy „proof of concept” napisany w C, wykorzystujący NTL Victora Shoupa do rozszerzonej arytmetyki precyzyjnej.

— matematyka
źródło

To był świetny papier! :) Czy znasz bardziej ogólną metodę, która mogłaby mieć zastosowanie do innych generatorów liczb losowych, a nie tylko liniowej zbieżności?

— Paweł

@Paul: Można oczywiście znaleźć RNG, które można łatwo „rozwiązać” dla ich parametrów z wystarczających danych wyjściowych (problem odwrotny), ale wydaje się, że im lepszy RNG (bardziej losowy wygląd wyniku), tym trudniejsze jest odwrócenie problem byłby. Rozwiązanie przypadku LCG wiąże się z pewnymi dobrze znanymi efektami grupowania wymiarowego, co powoduje, że pary generowanych wartości są nierównomiernie rozmieszczone. Aby uzyskać więcej informacji, zobacz Projekt generatora kryptograficznie silnego poprzez przekształcenie sekwencji generowanych liniowo

— hardmath