Historia generatorów liczb losowych

Oś czasu w skrócie

1. ok. 3000 p.n.e.

   Kości do gry

   Kości w Shahr-e Sukhteh na terenie dzisiejszego Iranu należą do najstarszych znanych.

2. 1654

   Pascal i Fermat

   Listy o podziale stawki w przerwanej grze dają początek rachunkowi prawdopodobieństwa.

3. 1890

   Francis Galton

   Opisuje w Nature, jak losować wartości do eksperymentów statystycznych za pomocą kości.

4. 1927

   L. H. C. Tippett

   Wydaje pierwszą drukowaną tablicę liczb losowych.

5. ok. 1946

   John von Neumann

   Proponuje metodę środka kwadratu, jeden z pierwszych algorytmów dla komputera.

6. 1949

   Derrick H. Lehmer

   Opisuje generator kongruencyjny, z którego wyrosła cała rodzina LCG.

7. 1955

   RAND Corporation

   Publikuje książkę z milionem losowych cyfr.

8. 1957

   ERNIE

   Pierwsze losowanie brytyjskich obligacji Premium Bonds elektronicznym generatorem.

9. 1968

   George Marsaglia

   Pokazuje, że wyniki generatorów kongruencyjnych, w tym RANDU, układają się na płaszczyznach.

10. 1997

    Matsumoto i Nishimura

    Przedstawiają Mersenne Twister, do dziś domyślny generator w wielu językach.

11. 1998

    RANDOM.ORG

    Mads Haahr uruchamia serwis losujący liczby z szumu atmosferycznego.

12. 2012

    Intel RDRAND

    Procesory Intela dostają instrukcję czytającą sprzętowy generator wbudowany w układ.

13. 2026

    ETH Zürich

    Losowość z matematycznym dowodem nieprzewidywalności, oparta na splątaniu i teście Bella.

od ok. 3000 p.n.e.

Kości, losy i filozofowie

Zanim pojawiły się sześcienne kości, rzucano astragalami, czyli kostkami skokowymi owiec i kóz. Mają cztery wyraźne boki, więc dobrze nadawały się do losowania. Kości do gry z Shahr-e Sukhteh, osady z epoki brązu na terenie dzisiejszego Iranu, mają około 4500 do 5000 lat i należą do najstarszych znanych. Kości służyły do gier, ale też do wróżenia i rozstrzygania sporów. Dziś tę samą rolę pełni rzut kostką w przeglądarce.

Równie stare jest losowanie patyczków albo słomek różnej długości. Wróżenie przez rzucanie losów nazywa się kleromancją. W wielu kulturach w ten sposób wybierano urzędników, dzielono ziemię i podejmowano decyzje, których nikt nie chciał brać na siebie.

Przypadek w filozofii

Arystoteles zastanawiał się, czym jest przypadek i czy w ogóle istnieje. Epikur twierdził, że atomy co jakiś czas nieznacznie zbaczają ze swojej drogi bez żadnej przyczyny. Rzymski poeta Lukrecjusz nazwał to odchylenie clinamen i widział w nim wyjaśnienie wolnej woli w świecie, który poza tym rządzi się sztywnymi prawami.

1654–1713

Narodziny rachunku prawdopodobieństwa

Matematyka losowości zaczęła się od pytania hazardzisty. W 1654 roku Blaise Pascal i Pierre de Fermat wymieniali listy o tym, jak sprawiedliwie podzielić stawkę w grze przerwanej przed końcem. Z tej korespondencji wyrósł rachunek prawdopodobieństwa. W 1713 roku ukazało się dzieło Jakoba Bernoulliego Ars Conjectandi z prawem wielkich liczb: przy wielu powtórzeniach częstość wyniku zbliża się do jego prawdopodobieństwa.

Od tego momentu losowość stała się narzędziem nauki. Żeby jednak sprawdzać teorię w praktyce, trzeba było mieć skąd brać dużo losowych wyników. O tym, jak dziś liczy się szanse w codziennych sytuacjach, piszemy w artykule o prawdopodobieństwie w życiu codziennym.

1873–1955

Galton i księgi liczb losowych

Brytyjski uczony Francis Galton zbudował w latach 70. XIX wieku tablicę z kołkami nazywaną quincunxem, dziś znaną jako deska Galtona. Kulki spadają przez rzędy kołków, odbijają się losowo w lewo albo w prawo i układają się na dole w kształt krzywej dzwonowej. Deska nie podaje konkretnych liczb, ale pokazuje, jak z wielu przypadkowych zdarzeń powstaje rozkład normalny.

Do samego losowania Galton użył kości. W 1890 roku opisał w czasopiśmie Nature metodę, w której odczytywał wynik z krawędzi kości, a nie z jej ścianek. Sześcian ma 24 takie pozycje, bo każda z sześciu ścianek ma cztery krawędzie, więc jeden rzut dawał więcej możliwych wyników. Pisał wtedy, że jako narzędzie do losowego wyboru nie znalazł niczego lepszego od kości.

Tablice zamiast rzutów

Rzucanie kośćmi było jednak powolne. W 1927 roku L. H. C. Tippett wydał Random Sampling Numbers, pierwszą drukowaną tablicę liczb losowych. Zawierała ponad 40 tysięcy cyfr i przez lata służyła statystykom do wybierania prób. Największą taką publikacją była książka RAND Corporation z 1955 roku, A Million Random Digits with 100,000 Normal Deviates. Milion cyfr wygenerowało elektroniczne urządzenie przypominające ruletkę, a wyniki dodatkowo przetworzono, żeby usunąć nierówności.

1940–1969

Maszyny losujące

Losowania poborowych w USA

W 1940 roku Stany Zjednoczone wybierały kolejność powoływania do wojska, wyciągając numery w kapsułach ze szklanej misy. Do tej metody wrócono w grudniu 1969 roku, w czasie wojny w Wietnamie, tym razem z datami urodzenia. Kapsuły wsypano do pojemnika miesiąc po miesiącu, od stycznia do grudnia, i wymieszano za słabo. Daty z końca roku trafiały na górę i były wyciągane wcześniej. Statystycy szybko wykazali, że taki wynik przy prawdziwie losowym wyborze byłby bardzo mało prawdopodobny. W następnych losowaniach kapsuły mieszano w obracanych bębnach.

ERNIE

W czerwcu 1957 roku w Wielkiej Brytanii odbyło się pierwsze losowanie Premium Bonds, rządowych obligacji, od których zamiast odsetek wypłaca się nagrody. Zwycięskie numery wybierał ERNIE (Electronic Random Number Indicator Equipment), zaprojektowany przez Tommy'ego Flowersa i Harry'ego Fensoma. Źródłem losowości był szum elektryczny w lampach neonowych. ERNIE był jednym z pierwszych elektronicznych generatorów używanych na tak dużą skalę, a jego kolejne wersje losują nagrody do dziś. Podobnie działa dziś losowanie Lotto na naszej stronie, tyle że wykonuje je program.

1946–1968

Pierwsze generatory w komputerach

Pierwsze komputery potrzebowały losowych liczb do symulacji, na przykład przy obliczeniach metodą Monte Carlo w Los Alamos. Wczytywanie tablic z kart perforowanych było wolne, a komputer działa deterministycznie: wykonuje dokładnie to, co mu zapisano. Trzeba było więc wymyślić wzór, który wytwarza liczby wyglądające na losowe.

Metoda środka kwadratu

Około 1946 roku John von Neumann zaproponował prosty sposób. Bierze się liczbę początkową, czyli ziarno, podnosi do kwadratu i wycina środkowe cyfry wyniku. Te cyfry są kolejną liczbą losową i zarazem nowym ziarnem. Na przykład czterocyfrowe ziarno 1234 daje kwadrat 01522756, a jego środek to 5227. Metoda szybko wpadała w krótkie cykle albo kończyła się na zerze. Von Neumann o tym wiedział i uważał, że łatwiej wykryć błąd w takim prostym generatorze niż w bardziej złożonym.

Generatory kongruencyjne i RANDU

W 1949 roku Derrick H. Lehmer opisał generator, który mnoży poprzednią wartość przez stałą i bierze resztę z dzielenia. Ogólna postać takiego generatora liniowego kongruencyjnego (LCG) wygląda tak:

X(n+1) = (a · X(n) + c) mod m

Jakość takiego generatora zależy od doboru stałych a, c i m. W latach 60. IBM rozpowszechnił na komputerach System/360 generator RANDU z bardzo złym doborem: X(n+1) = 65539 · X(n) mod 2^31. Mnożnik 65539 to 2¹⁶ + 3, co przyspieszało obliczenia na ówczesnym sprzęcie.

W 1968 roku George Marsaglia opublikował pracę Random Numbers Fall Mainly in the Planes. Pokazał, że jeśli z kolejnych wyników generatora kongruencyjnego tworzy się punkty w przestrzeni, punkty leżą na skończonej liczbie płaszczyzn. W przypadku RANDU było ich tylko 15. Mimo to generatora używano jeszcze przez lata, dlatego wyniki części symulacji z tamtego okresu traktuje się dziś z ostrożnością.

od 1986

Algorytmy, których używamy dziś

Mersenne Twister

W 1997 roku Makoto Matsumoto i Takuji Nishimura przedstawili Mersenne Twister. Najpopularniejsza wersja, MT19937, powtarza ciąg dopiero po 2¹⁹⁹³⁷ − 1 liczbach. To liczba pierwsza Mersenne'a, stąd nazwa. Generator jest szybki, dobrze przechodzi testy statystyczne i jest domyślny między innymi w Pythonie, w funkcji mt_rand() w PHP i w wielu pakietach statystycznych. Ma jedną ważną wadę: po zaobserwowaniu 624 kolejnych wyników da się odtworzyć jego stan i przewidzieć wszystkie następne.

Generatory kryptograficzne

Tam, gdzie od losowości zależy bezpieczeństwo, potrzebne są generatory, których wyników nie da się przewidzieć nawet po obejrzeniu długiego fragmentu ciągu. W 1986 roku Lenore Blum, Manuel Blum i Michael Shub opisali generator Blum Blum Shub. Jego bezpieczeństwo opiera się na trudności rozkładu dużych liczb na czynniki, ale jest zbyt wolny do większości zastosowań.

W praktyce przyjęły się konstrukcje szybsze. Yarrow, zaprojektowany w 1999 roku przez Johna Kelseya, Bruce'a Schneiera i Nielsa Fergusona, trafił między innymi do FreeBSD i macOS. Jego następcę, Fortunę, opisali Ferguson i Schneier w 2003 roku. FreeBSD przeszedł na nią w wersji 11, a Apple opisuje swój obecny generator jako konstrukcję wywodzącą się z Fortuny. Dziś każdy system operacyjny ma generator kryptograficzny zasilany entropią ze sprzętu. Z takiego źródła korzysta nasz generator haseł. Różnice między rodzajami generatorów opisujemy dokładniej w artykule o generatorach pseudolosowych i kryptograficznych.

od 1998

Losowość ze sprzętu i fizyki

Algorytm zawsze pozostaje algorytmem: z tego samego ziarna da ten sam ciąg. Prawdziwie losowe liczby wymagają pomiaru czegoś, czego nie da się przewidzieć. W 1998 roku Mads Haahr z Trinity College w Dublinie uruchomił RANDOM.ORG, serwis, który losuje liczby z atmosferycznego szumu radiowego odbieranego przez zwykłe radia.

W 2012 roku procesory Intela z rodziny Ivy Bridge dostały instrukcję RDRAND, która odczytuje liczby ze sprzętowego generatora wbudowanego w układ. Systemy operacyjne zwykle nie podają tych liczb programom bezpośrednio. Mieszają je z innymi źródłami entropii i dopiero tym zasilają generator kryptograficzny. Takie połączenie, w którym wolne źródło fizyczne dostarcza ziarna szybkiemu algorytmowi, jest dziś standardem.

Generatory kwantowe

Generatory kwantowe korzystają z tego, że wynik niektórych pomiarów kwantowych jest z natury nieprzewidywalny. Najprostszy przykład to foton wysłany na płytkę, która połowę światła przepuszcza, a połowę odbija. To, który z dwóch detektorów go zarejestruje, daje bit 0 albo 1. Takie urządzenia są dostępne komercyjnie. Od 2019 roku nagrody Premium Bonds losuje ERNIE 5, który korzysta z kwantowego generatora szwajcarskiej firmy ID Quantique i czerpie losowość ze światła.

Kolejnym krokiem jest losowość certyfikowana, czyli taka, której nieprzewidywalność wynika z praw fizyki, a nie z zaufania do producenta urządzenia. W 2026 roku zespół z ETH Zürich uzyskał takie liczby, łącząc splątanie kwantowe z testem Bella. Opisujemy to w artykule o idealnie losowych liczbach.

Głośne wpadki

Słaby generator rzadko widać na pierwszy rzut oka. Wyniki wyglądają na losowe, dopóki ktoś nie przyjrzy się im z odpowiedniej strony. Oprócz RANDU i loterii z 1969 roku dwa przypadki szczególnie zapadły w pamięć specjalistom od bezpieczeństwa.

Debian i OpenSSL, 2006–2008

Zmiana wprowadzona przez opiekunów pakietu w Debianie odcięła generator OpenSSL od prawie wszystkich źródeł entropii. Przez blisko dwa lata system tworzył klucze SSH i certyfikaty z bardzo małej puli możliwych wartości. Błąd wykrył w maju 2008 roku Luciano Bello i klucze z tego okresu trzeba było wygenerować od nowa.

Dual_EC_DRBG, 2006–2015

Generator oparty na krzywych eliptycznych trafił w 2006 roku do standardu NIST. Kryptografowie od początku zwracali uwagę, że może mieć ukrytą furtkę. Dokumenty ujawnione przez Edwarda Snowdena w 2013 roku wzmocniły te podejrzenia wobec NSA. NIST zalecił odejście od generatora, a w 2015 roku usunął go z poprawionej wersji standardu.

Obie historie mają wspólny morał dla programistów: do kluczy, tokenów i haseł używa się sprawdzonego generatora kryptograficznego systemu operacyjnego i nie poprawia się go na własną rękę. Jak losują liczby współczesne programy, opisujemy w artykule o algorytmach losowania w komputerach.

Często zadawane pytania