Generator liczb losowych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Generator liczb losowych (ang. random number generator; czasem nazywany generatorem zdarzeń losowych (REG - Random Event Generator) lub generatorem przypadków) - program komputerowy lub układ elektroniczny, generujący stacjonarny i ergodyczny, losowy ciąg elementów binarnych, zorganizowanych zwykle jako ciąg liczb losowych.
Generator liczb losowych jest urządzeniem, które nie produkuje przypadkowych liczb, lecz stany, które wyrażane są później jako liczby, stąd też określane są często poprawniejszą nazwą "generatora zdarzeń losowych" (REG - Random Event Generator).

Rodzaje[edytuj | edytuj kod]

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 programowe (ang. PRNG - Pseudo Random Number Generator) - działające na zasadzie deterministycznego obliczania ciągu liczb, które wyglądają jak liczby losowe (ang. look random).

Zasadniczą zaletą generatora sprzętowego, szczególnie ważną w kryptografii, są nieprzewidywalność (unpredictability) i niereprodukowalność (nonreproductability) 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 skomplikowanych procedur 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.

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). Działaniem generatora liczb losowych może być podawanie liczby z przedziału < 0 , 1 ) o rozkładzie jednostajnym.

Programowe generowanie liczb pseudolosowych[edytuj | edytuj kod]

Algorytmiczne generowanie liczb pseudolosowych jest zadaniem dość trudnym, a większość komputerów i języków programowania posiada bardzo ubogie funkcje (np. generator liniowy (Generator liczb pseudolosowych)), które nie spełniają podstawowych testów (np. rozkładu, okresu itp.).

Ciągi liczb pseudolosowych, uzyskiwane z internetu nie powinny być używane do poważnych celów, zwłaszcza do celów kryptograficznych, np. generacji haseł itp. Wynika to z zagrożenia ich łatwego odtworzenia oraz stąd, że mają one najczęściej nieakceptowalne statystyki w sensie nierównowagi "0" i "1" (bias) oraz silne korelacje między sąsiednimi liczbami (correlation).

Literatura[edytuj | edytuj kod]

  • 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.

Linki zewnętrzne[edytuj | edytuj kod]