Generator liczb pseudolosowych

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

Generator liczb pseudolosowych (ang. pseudo-random number generator lub PRNG) – program lub podprogram, który na podstawie niewielkiej ilości informacji (ziarno, zarodek, ang. seed) generuje deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.

Sygnał to abstrakcyjny model dowolnej mierzalnej wielkości zmieniającej się w czasie, generowanej przez zjawiska fizyczne lub systemy. Tak jak wszystkie zjawiska może być opisany za pomocą aparatu matematycznego, np. poprzez podanie pewnej funkcji zależnej od czasu. Mówimy, że sygnał niesie informację lub też umożliwia przepływ strumienia informacji.Szyfr strumieniowy – nazywany także algorytmem strumieniowym, algorytmem potokowym lub szyfrem strumieniowym; jest to algorytm symetryczny, który szyfruje oddzielnie każdy bit wiadomości. Algorytm ten składa się z generatora strumienia bitowego, będącego kluczem szyfrującym oraz elementu dodającego (na przykład operacji XOR).

Generatory liczb pseudolosowych nie generują ciągów prawdziwie losowych – generator inicjowany ziarnem, które może przyjąć różnych wartości, jest w stanie wyprodukować co najwyżej różnych ciągów liczb. Co więcej, ponieważ rozmiar zmiennych reprezentujących wewnętrzny stan generatora jest ograniczony (zwykle decyzją programisty, do kilkudziesięciu lub kilkuset bitów; a rzadziej, po prostu rozmiarem pamięci komputera), i ponieważ w związku z tym może on znajdować się tylko w ograniczonej liczbie stanów, bez dostarczania nowych danych z zewnątrz musi po jakimś czasie dokonać pełnego cyklu i zacząć generować te same wartości. Teoretyczny limit długości cyklu wyrażony jest przez gdzie to liczba bitów przeznaczonych na przechowywanie stanu wewnętrznego. W praktyce, większość generatorów ma znacznie krótsze okresy.

Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np.Podprogram (inaczej funkcja lub procedura) - termin związany z programowaniem proceduralnym. Podprogram to wydzielona część programu wykonująca jakieś operacje. Podprogramy stosuje się, aby uprościć program główny i zwiększyć czytelność kodu.

Do wielu zastosowań, opisany powyżej rodzaj deterministycznej pseudolosowości jest w zupełności wystarczający. W grach komputerowych czy algorytmach probabilistycznych (takich jak np. całkowanie Monte Carlo) potrzebne jest jedynie źródło wartości o cechach przybliżonych do liczb prawdziwie losowych, chociaż jakość losowości może być decydująca dla dokładności obliczeń. Dlatego przy zastosowaniu każdego nowego generatora do celów obliczeń numerycznych należy sprawdzić jego własności statystyczne. W przypadku skorzystania z jednego z dobrze zbadanych generatorów można czasem bezpośrednio obliczyć długość cyklu, a pozostałe właściwości (jak np. równomierność rozkładu) są najczęściej znane. Można też skorzystać z jednego ze standardowych testów (test pokerowy, test serii itp). Generatory liczb pseudolosowych występują w niemal każdym hazardowym automacie do gier. Do tej pory powstały zaledwie dwa typy automatów, które nie zawierają generatora, tj. Futura i Futura Eclipse, gdzie rozgrywka nie zawiera elementu losowości.

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.Funkcja skrótu, inaczej: funkcja mieszająca lub funkcja haszująca – jest to funkcja, która przyporządkowuje dowolnie dużej liczbie krótką, zwykle posiadającą stały rozmiar, nie specyficzną, quasi-losową wartość, tzw. skrót nieodwracalny.

Zastosowanie w kryptografii[ | edytuj kod]

Szczególną klasę PRNG stanowią generatory uznane za bezpieczne do zastosowań kryptograficznych. Kryptografia opiera się na generatorach liczb pseudolosowych przede wszystkim w celu tworzenia unikalnych kluczy stałych oraz sesyjnych. Ze względu na fakt, że bezpieczeństwo komunikacji zależy od jakości klucza, od implementacji PRNG stosowanych w takich celach oczekuje się między innymi, że:

Fluktuacja, wahania przypadkowe - przypadkowe, nie dające się przewidzieć, odchylenia od wartości średniej zmiennej losowej (np. wielkości fizycznej) podlegającej stochastycznym zmianom w czasie i nie wykazujące żadnej tendencji.Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.
  • Generowane wartości będą każdorazowo praktycznie nieprzewidywalne dla osób postronnych (np. przez wykorzystanie odpowiednich źródeł danych przy tworzeniu ziarna).
  • Nie będzie możliwe ustalenie ziarna lub stanu wewnętrznego generatora na podstawie obserwacji dowolnie długiego ciągu wygenerowanych bitów.
  • Znajomość dowolnej liczby wcześniej wygenerowanych bitów nie będzie wystarczała, by odgadnąć dowolny przyszły bit z prawdopodobieństwem istotnie wyższym od
  • Dla wszystkich możliwych wartości ziarna, zachowana będzie pewna minimalna, dopasowana do zastosowania długość cyklu PRNG (aby uniknąć ponownego wykorzystania takiego samego klucza).
  • Informacja (łac. informatio – przedstawienie, wizerunek; informare – kształtować, przedstawiać) – termin interdyscyplinarny, definiowany różnie w różnych dziedzinach nauki; najogólniej – właściwość pewnych obiektów, relacja między elementami zbiorów pewnych obiektów, której istotą jest zmniejszanie niepewności (nieokreśloności).MD5 (z ang. Message-Digest algorithm 5 – Skrót wiadomości wersja 5) – algorytm z dziedziny kryptografii. Jest to popularna kryptograficzna funkcja skrótu, która z dowolnego ciągu danych generuje 128-bitowy skrót.


    Podstrony: 1 [2] [3]




    Warto wiedzieć że... beta

    Mersenne Twister to algorytm generatora liczb pseudolosowych opracowany w 1997 przez Makoto Matsumoto i Takuji Nishimura. Generator jest szybki i dostarcza wysokiej jakości liczby pseudolosowe. Został zaprojektowany specjalnie dla naprawienia wielu wad, które znajdują się w starszych algorytmach.
    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.
    Metody numeryczne – metody rozwiązywania problemów matematycznych za pomocą operacji na liczbach. Otrzymywane tą drogą wyniki są na ogół przybliżone, jednak dokładność obliczeń może być z góry określona i dobiera się ją zależnie od potrzeb.
    Losowość - w potocznym znaczeniu brak celu, przyczyny, porządku lub przewidywalnego zachowania. Losowy proces to proces, którego wyniki nie dają się dokładnie przewidzieć, a jedynie można opisać ich rozkład.
    Test serii — zwany też testem serii Stevensa lub testem serii Walda-Wolfowitza — jest jednym z nieparametrycznych testów losowości próby. Stosujemy go m. in., gdy chcemy sprawdzić, czy wyniki eksperymentu spełniają postulat losowości próby.
    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
    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).

    Reklama