Generator liczb losowych

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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.

Statystyka (niem. Statistik, „badanie faktów i osób publicznych”, z łac. [now.] statisticus, „polityczny, dot. polityki”, od status, „państwo, stan”) – nauka, której przedmiotem zainteresowania są metody pozyskiwania i prezentacji, a przede wszystkim analizy danych opisujących zjawiska, w tym masowe.Symulacja - przybliżone odtwarzanie zjawiska lub zachowania danego obiektu za pomocą jego modelu. Szczególnym rodzajem modelu jest model matematyczny, często zapisany w postaci programu komputerowego, ale czasem niezastąpione jest wykorzystanie modelu fizycznego w zmniejszonej skali np. do badań aerodynamicznych. Symulacja znajduje szerokie zastosowanie w każdej dziedzinie nauki i techniki. Wykorzystywana jest też do celów wojskowych jak i czystej rozrywki np. w grach komputerowych.

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.

Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.Program komputerowy (ang. computer program) - sekwencja symboli opisująca obliczenia zgodnie z pewnymi regułami zwanymi językiem programowania. Program jest zazwyczaj wykonywany przez komputer (np. wyświetlenie strony internetowej), czasami bezpośrednio – jeśli wyrażony jest w języku zrozumiałym dla danej maszyny lub pośrednio – gdy jest interpretowany przez inny program (interpreter). Program może być ciągiem instrukcji opisujących modyfikacje stanu maszyny ale może również opisywać obliczenia w inny sposób (np. rachunek lambda).

Rodzaje[ | edytuj kod]

Ze względu na sposób generowania liczb losowych można wyróżnić dwa rodzaje generatorów:

  1. 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.
  2. 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.

Liczba losowa – liczba otrzymana jako rezultat działania określonego mechanizmu losującego (na przykład przy rzucaniu kostką do gry, tasowaniu kart, ciągnieniu losów z urny itp.). Można je także uzyskiwać za pomocą specjalnie skonstruowanych maszyn lub przy użyciu specjalnych programów komputerowych (generator liczb losowych).Metoda Monte Carlo (MC) jest stosowana do modelowania matematycznego procesów zbyt złożonych (obliczania całek, łańcuchów procesów statystycznych), aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego. Istotną rolę w metodzie MC odgrywa losowanie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie dokonywane jest zgodnie z rozkładem, który musi być znany.

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.

Układ elektroniczny lub obwód elektroniczny – zbiór elementów elektronicznych dyskretnych lub scalonych połączonych elektrycznie tak, aby realizowały określoną funkcję.Proces ergodyczny (stacjonarny proces ergodyczny) - proces stacjonarny dla którego wartości parametrów statystycznych po zbiorze realizacji (czyli wartość średnia, wariancja i funkcja autokorelacji) są równe wartościom tych parametrów z jego dowolnej realizacji czasowej. Proces jest ergodycznym, gdy spełnia warunek:

Literatura[ | 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.
  • Odwrotna dystrybuanta – uogólniona funkcja odwrotna do dystrybuanty danego rozkładu prawdopodobieństwa. Zwykle oznaczana Φ − 1 ( p ) {displaystyle Phi ^{-1}(p)}




    Reklama