Puncte:0

Maparea numărului în număr cu entropie algoritmică mare - cum se face?

drapel tf
Tom

Trebuie să parametrizez niște PRNG, să presupunem că am nevoie de numere pe 32 de biți. Dar când numerele nu par foarte aleatorii, dau rezultate proaste. Creatorii SplitMix au avut o problemă similară (rețineți că din câte am înțeles nu au rezolvat-o corect):

https://www.pcg-random.org/posts/bugs-in-splitmix.html

Așa că am nevoie de o funcție care să transforme să spunem numărul 1 în ceva de genul 10011110001101110111100110111001. Dar numărul 10100111101101010110001111100101 cu o complexitate algoritmică bună ar putea fi similară (desigur, Kolmorov ar putea avea aceeași complexitate algoritmică).

Deci hashing prin înmulțire: x = x*2654435769 mod 2^32 nu este opțiunea, deoarece putem găsi inversul multiplicativ modular, care ne-ar da 1 sau ceva rău oricum. Am încercat să folosesc bit mixer de la PCG:

uint32_t RXSMXS(uint32_t rxs)
{
    uint8_t r;

    r = rxs >> 28;
    rxs = rxs ^ (rxs >> (4 + r));
    rxs = rxs*277803737;
    returnează rxs^(rxs >> 22);
}

Dar se pare că este și reversibil 1 la 1 (problema este bijecția, nu reversibilitatea în sine). Același murmur32:

uint32_t murmur32(uint32_t z)
{
z ^= (z >> 16);
z *= 0x85ebca6bul;
z ^= (z >> 13);
z *= 0xc2b2ae35ul;
returnează z ^ (z >> 16);
}

Este reversibil și bijetcion, nu-i așa (ca să putem găsi intrări care ne dau rezultate atât de proaste pe cât ne dorim)?

Deci, există o metodă bine cunoscută și eficientă pentru a face acest lucru? Adică - luați un număr cu o complexitate scăzută (sau mare) de Kolmogorov și scoateți un număr cu complexitate mare de Kolmogorov. Bineînțeles că o astfel de funcție/mapping nu ar fi bijecție, pentru că doar aruncăm câteva valori. Deci diferitele chei/coeficienți vor produce uneori aceleași rezultate.

Ideea mea este să definesc jumătate din număr ca o constantă, de exemplu să fie cei mai mulți biți semnificativi: 10011110001101110000000000000000 și apoi alegeți aleatoriu biții mai puțin semnificativi (atunci ar putea fi fiecare număr de 16 biți). Și apoi pune-l în mixerul de biți ca murmur32 sau altceva. Dar încă nu avem nicio garanție că murmur32 nu va transforma, de exemplu, 1001111000110111000000000000011 în 1, 2 sau 3. Așa că poate nu voi folosi un mixer (dar astfel de numere ar putea avea entropia algoritmică greșită în biți cel puțin semnificativi).

Aveți idei mai bune, dar eficiente?

Puncte:1
drapel in

Se pare că doar cereți o funcție de hash securizată.

Spui în mod explicit că vrei să calculezi ușor într-o singură direcție și greu de inversat. Pe care o numim în mod normal această cerință rezistență preimagine. Este greu de găsit $x$ astfel încât $f(x)=y$.

Desigur, dacă valoarea inițială este aleasă dintr-un grup mic (entropie scăzută), vom putea să o găsim prin căutare exhaustivă.

Rețineți că numărul 1 nu este o entropie scăzută. Entropia este pe distribuții sau colecție de valori, nu numere simple.

Tom avatar
drapel tf
Tom
Mă gândesc mai degrabă la complexitatea lui Kolmogorov a numărului binar cunoscut și sub denumirea de entropie algoritmică sau complexitate algoritmică. Nu sunt sigur dacă este similară cu funcția de entropie binară (nu sunt atât de pasionat de matematică). Și nu trebuie să fie sigur. Am scris despre inversarea gândirii la bijecție, mă refeream la revenirea la intrare, folosind un număr. Mă voi schimba puțin în întrebarea mea.

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.