Pe comentarii care revizuiesc întrebare originală: OP presupune că 100 de cifre $y_n$ în $\{0,1,2,3,4,5\}$ aflate în posesia lor sunt obținute folosind o expresie C(++) echivalentă cu rand()%6 cu rand() folosind un PRNG (non-criptografic) bazat pe un generator liniar congruențial, cu cod echivalent cu
x lung static nesemnat;
int rand(void) {
x = 214013*x+2531011; // sau este 22695477*x+1
return (int)((x>>16)&0x7FFF);
}
Observa asta $x$ este de cel puțin 32 de biți, dar numai cei 31 de biți de ordin inferior contează din cauza (x>>16)&0x7FFF și C performanță nesemnat lung înmulțirea cu trunchiere a biților de ordin înalt care nu se încadrează în variabilă.
Abstragând detaliile de programare, presupunerea este că $x$ evolueaza per $x_{n+1}:=a\cdot x_n+b\bmod m$ cu $m=2^{31}$ și $(a,b)$ pentru unele constante fixe despre care se crede că fie $(214013,2531011)$ sau $(22695477,1)$. Și rand() scoate biții 30â¦16 din $x$ astfel cel $y_n:=\lfloor x_n/2^{16}\rfloor\bmod 6$ sunt date pentru $n=0$ la $99$ (cu sămânța un număr întreg necunoscut $x_{-1}$ într-un anumit interval imaterial, deoarece numai $x_{-1}\bmod m$ ar conta; și este mai bine să încercăm să găsim $x_0$ oricum).
OP întreabă dacă este posibil să se confirme sau să infirme acea presupunere și (dacă este adevărată) să găsească care $(a,b)$ sunt folosite și prezice ceea ce urmează în succesiune.
da, asta se poate, cu o incredere excelenta. Starea efectivă a PRNG-urilor luate în considerare are 31 de biți, sunt luate în considerare doar două PRNG-uri, acestea sunt acceptabile în scopuri de simulare, astfel încât ar trebui să putem găsi starea lor și care este folosită cu puțin mai mult decât $31+1=32$ un fragment de informație; și primim 100 USD\cdot\log_2(6)\aproximativ 258,5 USD bit, care va da o confirmare din plin.
Cel mai simplu este să încerci pentru ambele presupuneri $(a,b)$, și explorați posibilele valori ale $x_0$. Sunt doar $2^{31}$, știind $y_0$ permite reducerea sistematică a acesteia cu un factor de $6$. Fiecare următor $y_i$ elimină în continuare $5$ candidaţii din $6$. Dacă niciun candidat nu supraviețuiește tuturor $y_i$, ipoteza este infirmata. Dacă se găsește o potrivire, știm care $(a,b)$ am folosit și putem calcula suplimentar $y_i$. O implementare competentă într-un limbaj compilat ar dura ca o secundă pe un computer desktop modern.
Dar poate doriți să spargeți chestia în timp real cu un procesor modern de $0,5 care rulează de la o baterie de $0,2 sau sunteți blocați într-un calculator programabil din anii 1970, sau ENIAC. Observați că $6$ este par, iar divizorul este $2^{16}$. Urmează $y_n\bmod 2$ este un pic $16$ de $x_n$. De asemenea, remarcați că din moment ce $m$ este o putere a doi, schimbarea unui bit în $x_n$ nu se propagă la biți de ordin inferior ai $x_{n+1}$. Dacă urmează acel bit 16 din $x_n$ depinde doar de cei 17 biți mici de $x_0$. Știm bitul 16 din $x_0$, deci trebuie testat cel mult $2^{16}$ candidaţi pentru biţii 15â¦0 din $x_0$. Putem găsi apoi ceilalți 14 biți ca mai sus. Acea diviza și cuceri abordarea ar permite abordarea unor parametri mult mai mari, de ex. variabil X de tip uin64_t și întoarce x>>33, pe un procesor modern.
Mă întreb ce am putea face dacă $a$, $b$ și/sau $m$ erau necunoscute.
Note despre cele de mai sus:
- Folosește convenția dominantă în informatică (și criptografie, cu câteva excepții, cum ar fi DES): biții sunt numărați de la 0 (bit de ordin inferior), astfel încât dacă un întreg nenegativ $v$ este reprezentat în binar ca $k$ biți $b_j$, atunci $v=\sum b_j$ cu $0\le j<k$. În convenția big-endian, bitul 0 este scris în dreapta: $6\times7=42$ în zecimală este 110$\times111=101010$ în binar.
- Variabila computerului
X este de cel puțin 32 de biți, dar numai 31 de biți (de la 0 la 30) contează și sunt utilizați în $x_n$, prin urmare $0\le x_n<m=2^{31}$. Ieșirea de rand() este de cel puțin 16 biți, dar contează doar 15 biți de ordin scăzut (de la 0 la 14), iar toți ceilalți sunt zero, deci $0\le$rand()$\le$RAND_MAX$=2^{15}-1$. Dacă $0\le i<15$ apoi bit $j$ a ieșirii de rand() se potrivește bit $j+16$ de X. Urmează bitul 0 din $y_n$ se potrivește cu bitul 16 din $x_n$.
Comentarii (în afara subiectului) despre codul curent:
- Încearcă să folosească accelerația posibilă de
6 fiind egal. Eu susțin că asta este nu necesar pentru a atinge un timp de execuție în secunde, dacă
- noi explorează posibilele valori ale $x_0$, mai degrabă decât sămânța cu mulți pași înainte.
- folosim asta $x_0$ este de 31 de biți, astfel încât putem restricționa căutarea exterioară la [
0, 0x7fffffff] acesta este $2^{31}$ candidat $x_0$.
- folosim ceea ce știm $y_0$, astfel că $x_0=2^{16}\cdot(6\cdot u+ y_0)+v$ pentru $0\le u<\lceil2^{15}/6\rceil$ și $0\le v<2^{16}$, care se limitează la aproximativ $2^{31}/6$ candidati pentru $x_0$.
- optimizăm testul pentru verificarea candidatului $x_0$ împotriva $y_1$ în bucla interioară pe $v$.
- Esența opțional accelerarea notării
6 este chiar este să găsiți mai întâi biții 16â¦0 din $x_0$ potrivirea valorilor $y_0$ adunat, apoi biți 30â¦17. Codul nu face asta! Cu această accelerare, timpul de execuție s-ar reduce la milisecundă.
- Avem nevoie de valorile depline ale $y_n$ adunate (atât în căutarea neoptimizată, cât și în a doua parte a căutării optimizate), dar nu par să fie disponibile în intrare, ceea ce cred că este $y_n\bmod2$. Mai mult, nu înțeleg de ce este în matrice bidimensională
REZULTAT[3][7].
- Când $x_0$ se găsește, dacă a fost necesar să se găsească sămânța (sau mai degrabă biți 30â¦0 din aceasta) un număr cunoscut de pași înainte, acest lucru poate fi făcut eficient prin întoarcerea LCG folosind $x_{n-1}:=a^{-1}\,(x_n-b)\bmod m$ Unde $a^{-1}$ este inversă modulară de $a$ modulo $m$.
Aici este codul de lucru fără accelerarea opțională (deci capabilă să lucreze cu un modul de reducere final impar $r$ unde intrebarea are 6). Încearcă online!
#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>
#define A 214013 // pentru VC; 22695477 pentru BC
#define B 2531011 // pentru VC; 1 pentru BC
#define R 6 // modul, în [2, 32768]
// static_assert(A > 0 && A % 8 == 5, „Un mod 8 trebuie să fie 5”);
// static_assert(B > 0 && B % 2 == 1, „B mod 2 trebuie să fie 1”);
// static_assert(R >= 2 && R <= 32768, „R trebuie să fie în [2, 32768]”);
// decide modulo, redus când R este o putere a doi
#define M ((uint32_t)(((R-1)&R)!=0 ? 0x8000 : R)<<16)
// Secvența lui yn pentru VC (a=214013, b=2531011), n=6, sămânță=1639326023
// Dacă R este o putere de două, ceil(16/log2(R))+1 intrări sunt suficiente
// În caz contrar, acestea sunt intrările ceil(31/log2(R)), deci 12 pentru R=6.
const int16_t y[] = {
0,5,3,0,4,3,1,0,4,5,4,4,4,5,5,3,0,2,0,5,4,5,0, // 0, 2,5,1,3,5,5,5,
};
// INVA inversă modulară a lui A modulo M
#define INVA (IN_A(IN_A(IN_A(IN_A((uint32_t)A))))&(M-1))
#define IN_A(v) (v*(2-v*A))
int main(void) {
// decide să începem x0 astfel încât să se potrivească cu y0
const uint32_t y0 = y[0], y1 = y[1];
int32_t x0 = (int32_t)(((M >> 16) - y0) / R * R + y0) << 16 | 0xffff;
uint32_t găsit = 0;
printf("generator: ((int)((x = %" PRIu32 " * x + %" PRIu32 ") >> 16) & 0x7fff) %% %u\n",
(uint32_t)A, (uint32_t)B, (nesemnat)R);
în timp ce (x0 >= 0) {
uint32_t x1 = A * (uint32_t)x0 + B;
face {
// assert( (x0 >> 16) % R == y0);
// assert( x1 == A * (uint32_t)x0 + B);
dacă (((x1 >> 16) & 0x7fff) % R == y1) {
uint32_t x = x1;
int n;
pentru (n = 2; n < sizeof(y) / sizeof(*y); ++n)
dacă ((((x = A * x + B) >> 16) & 0x7fff) % R != y[n])
du-te la nxt;
// am găsit o soluție
x = (INVA * ((uint32_t)x0 - B)) & (M - 1);
printf("x0 poate fi %" PRId32 ", adică seed=%" PRIu32
" modulo 0x%" PRIx32 ", rezultând:\n", x0, x, M);
// dovediți punctul arătând rezultatul
pentru (n = 0; n < sizeof(y) / sizeof(*y) + 8; ++n)
printf(" %d", ((int)((x = A * x + B) >> 16) & 0x7fff) % R);
printf("\n");
++găsit;
}
nxt: x1 -= (uint32_t)A;
} în timp ce (((x0--) & 0xffff) != 0);
x0 -= (int32_t)(R - 1) << 16;
}
printf("găsit %" PRIu32 "soluție%s\n", găsită, găsită > 1 ? "s" : "");
întoarce 0;
}
// ceda:
// generator: ((int)((x = 214013 * x + 2531011) >> 16) & 0x7fff) % 6
// x0 poate fi 531633902, adică seed=1639326023 modulo 0x80000000, rezultând:
// 2 3 4 1 5 1 1 5 4 0 3 2 2 5 5 3 5 5 3 4 0 1 1 4 1 3 3 2 5 4 4
// am găsit 1 soluție
