Pseudolosowość - Pseudorandomness
Pseudolosowy ciąg liczb jest ten, który wydaje się być statystycznie losowo , pomimo że został wytworzony w całkowicie deterministycznej procesie powtarzalnym.
Tło
Generowanie liczb losowych ma wiele zastosowań, takich jak losowe próbkowanie , metody Monte Carlo , gry planszowe czy hazard . Jednak w fizyce większość procesów, takich jak przyspieszenie grawitacyjne, ma charakter deterministyczny, co oznacza, że zawsze dają ten sam wynik z tego samego punktu początkowego. Niektórymi godnymi uwagi wyjątkami są rozpad promieniotwórczy i pomiary kwantowe , które są modelowane jako prawdziwie losowe procesy w fizyce leżącej u ich podstaw. Ponieważ procesy te nie są praktycznymi źródłami liczb losowych, ludzie używają liczb pseudolosowych, które idealnie mają nieprzewidywalny ciąg naprawdę losowy, mimo że są generowane przez proces deterministyczny.
W wielu aplikacjach procesem deterministycznym jest algorytm komputerowy zwany generatorem liczb pseudolosowych , który najpierw musi być zaopatrzony w liczbę zwaną ziarnem losowym . Ponieważ to samo ziarno będzie dawać tę samą sekwencję za każdym razem, ważne jest, aby ziarno było dobrze dobrane i trzymane w ukryciu, zwłaszcza w zastosowaniach zabezpieczających , gdzie nieprzewidywalność wzoru jest cechą krytyczną.
W niektórych przypadkach, w których ważne jest, aby sekwencja była wyraźnie nieprzewidywalna, ludzie korzystali z fizycznych źródeł liczb losowych, takich jak rozpad radioaktywny, atmosferyczny szum elektromagnetyczny zebrany z radia dostrojonego między stacjami lub mieszane czasy naciśnięć klawiszy . Inwestycja czasu potrzebna do uzyskania tych liczb prowadzi do kompromisu: użycie niektórych z tych odczytów fizyki jako zalążka generatora liczb pseudolosowych.
Historia
Przed nowoczesnymi obliczeniami naukowcy wymagający liczb losowych albo generowali je za pomocą różnych środków ( kostki , karty , koła ruletki itp.) albo wykorzystywali istniejące tabele liczb losowych.
Pierwsza próba dostarczenia naukowcom gotowego zestawu losowych cyfr miała miejsce w 1927 r., kiedy Cambridge University Press opublikowało tabelę 41 600 cyfr opracowaną przez LHC Tippett . W 1947 r. firma RAND Corporation wygenerowała liczby za pomocą elektronicznej symulacji koła ruletki; wyniki zostały ostatecznie opublikowane w 1955 roku jako milion losowych cyfr ze 100 000 odchyleń normalnych .
W złożoności obliczeniowej
W informatyki teoretycznej , o dystrybucji jest pseudolosowych przeciwko klasie adwersarzy jeśli nie przeciwnik z klasy można odróżnić je od rozkładu równomiernego o znaczącej przewagi. To pojęcie pseudolosowości jest badane w teorii złożoności obliczeniowej i ma zastosowanie w kryptografii .
Formalnie niech S i T będą zbiorami skończonymi i niech F = { f : S → T } będzie klasą funkcji. Rozkład D na S jest ε- pseudolosowego na F , jeśli dla każdego f w F , w odległości statystycznej między rozkładami i , gdzie i jest próbkowany z D i , gdzie i jest próbkowany z rozkładu równomiernego na S jest najwyżej ε .
W typowych zastosowaniach klasa F opisuje model obliczeń z ograniczonymi zasobami i interesuje nas projektowanie rozkładów D z pewnymi właściwościami, które są pseudolosowe w stosunku do F . Rozkład D jest często określany jako wyjście generatora pseudolosowego .
Zobacz też
- Bezpieczny kryptograficznie generator liczb pseudolosowych
- Lista generatorów liczb losowych
- Pseudolosowa sekwencja binarna
- Zespół pseudolosowy
- Generator liczb pseudolosowych
- Ciąg quasi-losowy
- Generowanie liczb losowych
- Szum pseudolosowy
Bibliografia
- ^ B George Johnson (12 czerwca 2001). „Koneserzy chaosu oferują cenny produkt: losowość” . New York Times .
-
^ SP Vadhan (2012). Pseudolosowość .
pseudolosowość, teoria wydajnego generowania obiektów, które „wyglądają losowo”, mimo że są skonstruowane przy użyciu niewielkiej lub żadnej losowości
- ^ Mark Ward (9 sierpnia 2015). „Liczby losowe w sieci są zbyt słabe, ostrzegają naukowcy” . BBC .
- ^ Jonathan Knudson (styczeń 1998). „Javatalk: podkowy, granaty ręczne i liczby losowe”. Serwer Sun . s. 16-17.
- ^ a b „Milion losowych cyfr” . RAND Korporacja . Źródło 30 marca 2017 .
- ^ Oded Goldreich. Złożoność obliczeniowa: perspektywa koncepcyjna. Wydawnictwo Uniwersytetu Cambridge. 2008.
- ^ „Pseudolosowość” (PDF) .
Dalsza lektura
- Donald E. Knuth (1997) The Art of Computer Programming , Tom 2: Seminumerical Algorithms (wydanie trzecie) . Addison-Wesley Professional, ISBN 0-201-89684-2
- Oded Goldreich. (2008) Złożoność obliczeniowa: perspektywa pojęciowa . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-88473-0 . (Ograniczony podgląd w Książkach Google)
- Vadhan, SP (2012). „Pseudolosowość”. Podstawy i trendy w informatyce teoretycznej . 7 (1–3): 1–336. doi : 10.1561/04000000010 .
Zewnętrzne linki
- HotBits: Oryginalne liczby losowe, generowane przez rozpad radioaktywny
- Używanie i tworzenie liczb losowych o jakości kryptograficznej
- W RFC 1750 szczegółowo omówiono użycie sekwencji liczb pseudolosowych w kryptografii.