Inne

Liczby pseudolosowe – czym są?

by admin

Liczby pseudolosowe to liczby generowane przez algorytm deterministyczny, który tworzy sekwencję o mniej więcej takich samych właściwościach statystycznych , jak sekwencja liczb wygenerowana w procesie losowym. Algorytm ten nazywa się generatorem liczb pseudolosowych (PRNG, z angielskiego generator liczb pseudolosowych).

Sekwencje liczb pseudolosowych są zwykle generowane przez komputer i wykorzystywane w algorytmach opartych na procesach losowych, takich jak metody typu Monte Carlo czy aplikacje kryptograficzne. Z drugiej strony, gdy wymagane są naprawdę losowe sekwencje liczb, używany jest sprzętowy generator liczb losowych.

Ciąg 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 nie może być zdefiniowany jako pseudolosowy, ponieważ spełnia warunek równego rozkładu (na przedziale [1 ,10 ], ale nie niezależności: pary kolejnych elementów nie są równomiernie rozłożone na zbiorze wszystkich możliwych par liczb od 1 do 10, ale wszystkie mają postać ( n , n + 1 ) (dlatego rysując je na wykresie kartezjańskim wszystkie są ułożone na tej samej linii). Sekwencja pseudolosowa mogłaby zamiast tego mieć postać 3, 2, 10, 9, 6, 8, 1, 5, 4, 7: w tym przypadku pary kolejnych elementów wydają się być rozłożone dość równomiernie w zbiorze par liczby od 1 do 10, nawet jeśli długość ciągu jest zbyt krótka, aby można go było dokładnie zweryfikować.

Niektóre aplikacje wymagają innych właściwości statystycznych oprócz tych. W szczególności w przypadku zastosowań kryptograficznych istotne jest, aby algorytm nie pozwalał na odtworzenie całej sekwencji po zaobserwowaniu jej części: w przeciwnym razie atakujący mógłby odtworzyć klucz kryptograficzny wygenerowany z sekwencji i odszyfrować chronione przez niego informacje. Generatory spełniające to wymaganie nazywane są kryptograficznie bezpiecznym PRNG (CSPRNG ).

Inną istotną właściwością generatora liczb losowych jest jego okres , czyli liczba elementów, po których ciąg się powtarza. Generalnie im dłuższy okres, tym lepsza jakość generatora, chociaż dla większości zastosowań okres 2^32 -1(około 4 miliardów), które uzyskuje się dla wielu powszechnie używanych generatorów, jest więcej niż wystarczające.

Algorytmy generowania

Istnieje kilka klas generatorów liczb pseudolosowych, które różnią się rodzajem zastosowanego algorytmu. Prawie we wszystkich wytwarzają ciąg liczb całkowitych równomiernie rozłożonych od 0 do pewnej wartości maksymalnej lub liczb rzeczywistych od 0 do 1 (te ostatnie można zawsze uzyskać z tych pierwszych, po prostu dzieląc przez wartość maksymalną).

Przed użyciem generator musi zostać zainicjowany poprzez przypisanie odpowiedniej wartości do parametru numerycznego lub grupy parametrów, która nazywa się seed. Za każdym razem, gdy użyjesz tego samego nasiona, zawsze otrzymasz dokładnie tę samą sekwencję. Okres generatora nie może zatem przekroczyć liczby możliwych wartości ziarna: na przykład generator, którego ziarno jest przechowywane w pojedynczej 32 – bitowej zmiennej może mieć maksymalny okres 2^32 (zwykle wartość zero nie jest dozwolona i dlatego obowiązują wartości możliwe) 2^32 – 1).

Wymagana jest dokładna analiza matematyczna, aby wygenerowane liczby miały niezbędne właściwości statystyczne. Robert R. Coveyou z Oak Ridge National Laboratory napisał artykuł: „Generowanie liczb losowych jest zbyt ważne, aby pozostawić je przypadkowi”.

Główne klasy generatorów w obecnym użytkowaniu:

  • liniowe generatory kongruencyjne ( LCG ): jest to pierwsza klasa w kolejności czasu, która była używana i nadal najbardziej rozpowszechniona.
  • opóźnione generatory Fibonacciego : są w stanie generować bardzo długie sekwencje. Wśród nich jest algorytm Mersenne Twister , który ma okres 2^{19937}-1}.
  • rejestry tłumaczeń z liniowym sprzężeniem zwrotnym.
  • uogólnione rejestry tłumaczeń opinii.

Więcej na ten temat dowiesz się z serwisu: https://generator-liczb.com.pl/