Puncte:2

Cum să exploatezi RNG-ul Java pentru a găsi clustere?

drapel sy

introduceți descrierea imaginii aici

În imaginea de mai sus, puteți vedea o grilă de coordonate care conține câteva puncte verzi aleatorii. Fiecare punct are o șansă pseudoaleatorie de 1/10 să fie verde. Ceea ce caut sunt grupuri de aceste puncte verzi pe o rază de ~ 8 (ignorați masca interioară afișată). Altfel spus, caut zone cu densitate mare improbabile din punct de vedere statistic ale acestor puncte verzi. În centrul acestei probleme se află Java RNG găsit în java.util.Random (sursa aici). Codul pentru a determina dacă un punct este verde se rezumă la această funcție hash. Intrările sunt unele constante, $k$, și coordonatele punctului, $x$ și $y$.

sămânță lungă = ((k + (lung) (x * x * 4987142) + (lung) (x * 5947611) + (lung) (y * y) * 4392871L + (lung) (y * 389711) ^ 987234911L) ^ 0x5DEECE66DL) & ((1L << 48) - 1);
int biți, val;
do
{
    sămânță = (sămânță * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    biți = (int)((ulong)seed >> 17);
    val = biți % 10;
} while (biți - val + 9 < 0);

return val == 0;

A fost cercetări minore asupra acestei probleme în trecut, dar nu sunt suficient de informat pentru a contribui în continuare. Ceea ce s-a găsit a fost că potenţial clustere cu dimensiuni mici de 2x2 și 3x3 creează un model atunci când se compară cu diferite $k$ valorile. introduceți descrierea imaginii aici

Acest lucru poate oferi indicii cu privire la coordonatele unei căutări ar trebui să se concentreze mai mult pe calcul, având în vedere un anumit $k$, dar nu sunt convins. De exemplu, iată o hartă termică a dimensiunilor clusterului pentru un anumit $k$. Puteți găsi mai multe informații despre cum au fost derivate aceste imagini Aici.

introduceți descrierea imaginii aici

Începând de acum, verific cu forță brută numărul de cluster al fiecărei coordonate și omit o coordonată dacă clusterul este prea mic pentru ca următorul să aibă un cluster de dimensiune suficientă, ceea ce este majoritatea pentru că caut statistici. valori aberante.

Ceea ce sper este că există un model exploatabil în acest algoritm, este practic să inversați acest hash într-un fel sau există optimizări majore de făcut în metoda mea actuală.

Poate că o posibilă cale de înaintare ar fi să vedem dacă modelul de zăbrele continuă să persistă pentru grupuri din ce în ce mai mari, dar o altă imagine din acea postare pare să indice că s-ar pierde în zgomot.

drapel kr
De ce crezi că această întrebare este legată de criptografie? Codul folosește pseudo RNG. Aceasta înseamnă că pentru aceeași sămânță va produce întotdeauna **aceleași** rezultate. Aceasta este o întrebare de programare pură și se poate răspunde mai bine pe SO.
Paul Uszak avatar
drapel cn
@mentallurg Stai bine. Deși foarte frumos, tema de bază a acestei întrebări este manipularea / exploatarea RNG. Acesta este un atac care este exact la subiect aici. Variabila $k$ variază după definiție și acesta este cheia. Multe dintre forumurile .SE se suprapun, ceea ce cred că este o consecință a creșterii organice necontrolate.
drapel kr
@PaulUszak: Întrebarea este despre **pseudo RNG**. Codul menționat folosește clasa Random care implementează un PRNG. O parte esențială a codului este că pentru fiecare argument nou se calculează o nouă sămânță. Setarea aceleiași semințe duce la generarea de **aceleași** rezultate. Asta nu are nimic de-a face cu manipularea. Și întrebarea este despre modul de **îmbunătățire a performanței**.
Gabe avatar
drapel sy
@mentallurg Cred că această întrebare este foarte mult în spiritul criptografiei. Nu cer cod pentru a îmbunătăți performanța, caut o comandă rapidă generalizată. Ce rost are o etichetă **pseudo-random-generator** dacă întrebările despre PRNG sunt în afara subiectului???
Maarten Bodewes avatar
drapel in
Pot să văd acest lucru ca fiind oarecum util pentru efectuarea analizei PRNG-urilor, deși mă întreb cât de mult se înscrie acest lucru într-o întrebare de cercetare în loc de o întrebare la care se poate răspunde obiectiv fără cercetare.
drapel kr
@Gabe: 1) Eticheta de pe acest site are sens, deoarece generatoarele pseudo-aleatorie sunt folosite pentru multe sarcini criptografice. Dacă PRNG nu este folosit pentru sarcini criptografice, acest site este în afara subiectului. 2) Scrieți „*Sunt doar **forță brută**... Ceea ce sper este că... există **optimizări majore***”. Aceasta înseamnă că căutați optimizarea performanței. Dacă problema ar fi legată de criptografie, aceasta ar fi întrebarea relevantă. Dar, din moment ce nu arătați nicio legătură a problemei dvs. cu criptografie, de asemenea, această optimizare este în afara subiectului acestui site.
the default. avatar
drapel id
Acesta nu este un atac criptografic, dar rescrierea codului, astfel încât să nu recalculeze „deltas” de fiecare dată și să reutilizeze rezultatele calculelor anterioare atunci când incrementează x i-a permis să proceseze aceleași 100 de milioane de bucăți în 2,3 secunde pe un mod mult mai modest. CPU Ryzen 2500U cu 8 fire: https://pastebin.com/UuDpVPQg (compilați cu `-fopenmp` pentru multihtreading). Portarea acestuia înapoi la OpenCL ar trebui să o facă suficient de rapidă pentru majoritatea scopurilor practice.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.