Generator liczb losowych
Generator liczb losowych (ang. random number generator, RNG) – program komputerowy lub układ elektroniczny generujący stacjonarny i ergodyczny, losowy ciąg elementów binarnych zorganizowanych zwykle jako ciąg liczb losowych.
Generatory liczb losowych są ważnymi współczesnymi narzędziami badawczymi, używanymi w wielu dziedzinach, m.in. w kryptografii lub statystyce do symulacji procesów (przybliżone obliczenia matematyczne i symulacje fizyczne przy użyciu metody Monte Carlo).
Wynikiem działania generatora liczb losowych zwykle są liczby z przedziału o rozkładzie jednostajnym. Z generatora o takim rozkładzie można uzyskać generator o dowolnym innym rozkładzie, obliczając odwrotną dystrybuantę pożądanego rozkładu z wyników pierwszego generatora.
Rodzaje
Ze względu na sposób generowania liczb losowych można wyróżnić dwa rodzaje generatorów:
- Generatory sprzętowe (ang. TRNG – True Random Number Generator) – działające na zasadzie obrazowania właściwości i parametrów fizycznego procesu stochastycznego, najczęściej szumu elektrycznego. Generatory takie nie produkują samych liczb, lecz stany, które dopiero później interpretowane są jako liczby, stąd też określane bywają generatorami zdarzeń losowych (ang. random event generator, REG) lub generatorami przypadków.
- Generatory programowe (ang. PRNG – Pseudo Random Number Generator) – działające na zasadzie deterministycznego obliczania ciągu liczb, które wyglądają na losowe.
Zasadniczymi zaletami generatorów sprzętowych, szczególnie ważną w kryptografii, są nieprzewidywalność i niereprodukowalność generowanych ciągów, wynikające z unikatowości realizacji fizycznego procesu stochastycznego w danym przedziale czasu.
Liczby pochodzące z generatora programowego zwane są liczbami pseudolosowymi, ponieważ faktycznie nie są dziełem przypadku, lecz wynikiem obliczeń matematycznych.
Największą zaletą generatorów pseudolosowych jest ich szybkość, często też mają lepsze właściwości statystyczne niż generatory sprzętowe. Należy jednak zwrócić uwagę na fakt, że mając kontrolę lub znając wartości podawane na wejście generatora oraz jego stan wewnętrzny, bez trudu można przewidzieć zwracane przezeń liczby. Z tego powodu decydując się na zastosowanie w systemie kryptograficznym generatora liczb pseudolosowych, należy zachować szczególną ostrożność przy doborze zarówno samego algorytmu, jak i sposobu inicjowania oraz rodzaju wartości podawanych na jego wejście.
Literatura
- Andriej N. Kołmogorow, Boris W. Gniedenko: Rozkłady graniczne sum zmiennych losowych niezależnych. Warszawa: PWN, 1957.
- William Feller: Wstęp do rachunku prawdopodobieństwa. Cz. 1 i 2. Warszawa: PWN, 2006 i 2009.
- Jerzy Seidler: Nauka o informacji. T. 1 i 2. Warszawa: WNT, 1983.
- Dobiesław Bobrowski: Ciągi losowe. Poznań: WN UAM, 2002.
- Donald E. Knuth: Sztuka programowania. T. 2. Warszawa: WNT, 2002.
- Ryszard Zieliński, Robert Wieczorkowski: Komputerowe generatory liczb losowych. Warszawa: WNT, 1997.
- Marek Leśniewicz: Sprzętowa generacja losowych ciągów binarnych. Warszawa: WAT, 2009. ISBN 978-83-61486-31-2.